Two contradictory conjectures concerning Carmichael numbers

DOI10.1090/S0025-5718-01-01355-2MaRDI QIDQ2781234zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Granville, Carl Pomerance

Publication date 19 March 2002

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/s0025-5718-01-01355-2

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

Mathematics Subject Classification ID

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

Review text

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 [\textit{W. R. Alford, A. Granville} and \textit{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\). NEWLINENEWLINENEWLINEThe 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)\). NEWLINENEWLINENEWLINEThe 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. NEWLINENEWLINENEWLINESection 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: NEWLINENEWLINENEWLINEAssume 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. NEWLINENEWLINENEWLINEWrite \(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, NEWLINE\[NEWLINEC_k^0(x)\leq \frac{1}{k!} x^{1/k} e^{\log x/\log\log (x^{1/k})}.NEWLINE\]NEWLINE 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 NEWLINE\[NEWLINE27\lambda x^{1/3}/\log^3 xNEWLINE\]NEWLINE with NEWLINE\[NEWLINE\lambda:= \frac{243}{2} \prod_{p>3} \Biggl( \frac{1-3/p} {(1-1/p)^3} \Biggr) \cong 77.1727.NEWLINE\]NEWLINE Finally, in Section 9 the authors shown (unconditionally) that NEWLINE\[NEWLINEC_k(x)\ll x^{2/3} (\log x)^{(2^{k-2}-1)/3}NEWLINE\]NEWLINE and that this estimate holds uniformly for all \(k\geq 3\). NEWLINENEWLINENEWLINEThe 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\).

Recommendations

Cites work

Cited in

(31)

This page was built for publication: Two contradictory conjectures concerning Carmichael numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2781234)