Two contradictory conjectures concerning Carmichael numbers. (English) Zbl 0991.11067

Granville, Andrew; Pomerance, Carl

Math. Comput. 71, No. 238, 883-908 (2002).

The paper under review contains some impressive conjectures and theorems about Carmichael numbers. We first recall that if \(a>1\) is an integer, then an integer \(n\) which is not prime but which satisfies Fermat’s Little Theorem with respect to \(a\); namely \(a^n\equiv a\pmod n\), is called a base \(a\) pseudoprime. If \(n\) is a base \(a\) pseudoprime for all \(a\), then \(n\) is called a Carmichael number, and the smallest example of such a number is 561, which was found by Carmichael himself in 1910. Until 1994, it was not even known that there were infinitely many Carmichael numbers when this was shown to be so in the seminal paper [W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. (2) 139, 703–722 (1994; Zbl 0816.11005)], where it was shown that for large \(x\) there are more than \(x^{2/7}\) Carmichael numbers smaller than \(x\). P. Erdős conjectured that there should be \(x^{1-o(1)}\) Carmichael numbers up to \(x\) and gave some heuristics to support this conjecture. On the other hand, from data available to him, D. Shanks highly doubted this and in fact he was even sceptical that one might even find an \(x\) so that there are more than \(\sqrt{x}\) Carmichael numbers up to \(x\).
The comparison of these contradictory conjectures is the main starting point of the paper under review. The main object under investigation in this paper is the number of Carmichael numbers up to \(x\) with a fixed number of primes. That is, let \(C(x)\) be the number of Carmichael numbers up to \(x\), and for a fixed integer \(k\geq 3\) let \(C_k(x)\) be the number of Carmichael numbers up to \(x\) with exactly \(k\) prime factors. The whole paper is concerned with the understanding of the function \(C_k(x)\).
The paper is organized as follows. In Sections 1 and 7 the authors make a total of seven conjectures. For example, Conjecture 3 asserts that if \(3\leq k\leq y:= \log x/\log\log x\), then \(C_k(x)= \frac{x^{1/k}} {k!} k^y(\log\log x)^{O(y)}\). Sections 2, 3, 4, 5, and 7 contain several results, some of them conditional such as most of the results from Section 7, as well as heuristics to support all these conjectures.
Section 6 contains five unconditional results (three theorems and two corollaries) that give upper bounds for the number of imprimitive Carmichael numbers with a fixed number of divisors \(k\). The notion of primitive versus imprimitive Carmichael number is introduced in this paper on page 887 and reads as follows:
Assume that \(n:= p_1p_2\cdot\dots\cdot p_k\) is a Carmichael number and the ratios \(p_1-1\: p_2-1\:\dots\: p_k-1= a_1\: a_2\:\dots\: a_k\) are given with \(\text{gcd} (a_1,\dots, a_k)=1\). Then \(p_i= ga_i+1\) for some integer \(g\) and now the condition that \(\text{lcm} (p_1-1,\dots, p_k-1)\mid n-1\) puts a polynomial relation on \(g\) modulo \(A:= \text{lcm} (a_1,\dots, a_k)\). Thus, the number \(g\) can belong to certain arithmetical progressions \(s\pmod A\) with \(s< A\). If \(s\) itself has the property that all numbers \(sa_i+1\) are primes, then we obtain a Carmichael number which is call primitive. The other ones are called imprimitive.
Write \(C_k^0(x)\) for the number of imprimitive Carmichael numbers with \(k\) prime factors up to \(x\). Then the results from Section 6 show that \(C_k^0(x)\) is small, for example, \[ C_k^0(x)\leq \frac{1}{k!} x^{1/k} e^{\log x/\log\log (x^{1/k})}. \] In Section 8 the authors make a very precise conjecture as to the exact order of magnitude of \(C_3(x)\), which is conjectured to be \[ 27\lambda x^{1/3}/\log^3 x \] with \[ \lambda:= \frac{243}{2} \prod_{p>3} \Biggl( \frac{1-3/p} {(1-1/p)^3} \Biggr) \cong 77.1727. \] Finally, in Section 9 the authors shown (unconditionally) that \[ C_k(x)\ll x^{2/3} (\log x)^{(2^{k-2}-1)/3} \] and that this estimate holds uniformly for all \(k\geq 3\).
The paper contains also several tables showing the values of \(C(x)\), \(C_k(x)\), for \(3\leq k\leq 10\), \(\log C(X)/ \log x\), etc. for \(x= 10^t\) and \(3\leq t\leq 20\) (some tables are in smaller ranges). While the computations do show that \(\log C(x)/ \log x\) is increasing, the speed of convergence is, to quote the paper, “agonizingly slow” and the largest value of this ratio is \(.33700\) at \(x=10^{16}\), so there might be some time until one will find an \(x\) with this ratio larger than \(.5\).

Reviewer: Florian Luca (Morelia)

MSC:

11Y35	Analytic computations
11N60	Distribution functions associated with additive and positive multiplicative functions
11N05	Distribution of primes

Keywords:

Carmichael numbers; pseudoprime; upper bounds; number of imprimitive Carmichael numbers; primitive Carmichael numbers; exact order of magnitude of \(C_3(x)\)

Citations:

Zbl 0816.11005

References:

[1]	W. R. Alford and J. Grantham, Carmichael numbers with exactly \(k\) prime factors (to appear).
[2]	W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703 – 722. · Zbl 0816.11005
[3]	W. R. Alford, Andrew Granville, and Carl Pomerance, On the difficulty of finding reliable witnesses, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1 – 16. · Zbl 0828.11074
[4]	R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, Math. Comp. 66 (1997), no. 220, 1705 – 1708. · Zbl 0902.11036
[5]	E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning ”factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1 – 28. · Zbl 0513.10043
[6]	Ivan Damgård, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), no. 203, 177 – 194. · Zbl 0788.11059
[7]	P. Erdos, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. · Zbl 0074.27105
[8]	P. Erdos and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math 62 (1940), 738-742. · JFM 66.0172.02
[9]	W. Galway, The density of pseudoprimes with two prime factors (to appear).
[10]	A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc. 39 (1992), 696-700.
[11]	G. H. Hardy and J. E. Littlewood, Some problems on partitio numerorum III. On the expression of a number as a sum of primes, Acta Math. 44 (1923), 1-70. · JFM 48.0143.04
[12]	Aleksandar Ivić and Gérald Tenenbaum, Local densities over integers free of large prime factors, Quart. J. Math. Oxford Ser. (2) 37 (1986), no. 148, 401 – 417. · Zbl 0604.10024
[13]	Yong Li, Galois fields and computation, Neimenggu Shida Xuebao Ziran Kexue Ban 2 (1991), 13 – 18 (Chinese, with English summary).
[14]	R. G. E. Pinch, The Carmichael numbers up to \(10^{16}\) (to appear). · Zbl 0780.11069
[15]	R. G. E. Pinch, The pseudoprimes up to \(10^{12}\) (to appear). · Zbl 1032.11060
[16]	Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587 – 593. · Zbl 0511.10002
[17]	C. Pomerance, Two methods in elementary analytic number theory, Number Theory and Applications , NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Reidel, Dordrecht, 1989, pp. 135-161. · Zbl 0683.10003
[18]	Carl Pomerance, Carmichael numbers, Nieuw Arch. Wisk. (4) 11 (1993), no. 3, 199 – 209. · Zbl 0806.11005
[19]	Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to 25\cdot 10\(^{9}\), Math. Comp. 35 (1980), no. 151, 1003 – 1026. · Zbl 0444.10007
[20]	A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185 – 208; erratum 5 (1958), 259 (French). · Zbl 0082.25802
[21]	-, Sur certaines hypothèses concernant les nombres premiers. Erratum, Acta Arith. 5 (1959), 259.
[22]	Daniel Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea Publishing Co., New York, 1985. · Zbl 0997.11503