Two contradictory conjectures concerning Carmichael numbers

Authors:
Andrew Granville and Carl Pomerance

Journal:
Math. Comp. **71** (2002), 883-908

MSC (2000):
Primary 11Y35, 11N60; Secondary 11N05, 11N37, 11N25, 11Y11

Published electronically:
October 4, 2001

MathSciNet review:
1885636

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Erdos conjectured that there are Carmichael numbers up to , whereas Shanks was skeptical as to whether one might even find an up to which there are more than Carmichael numbers. Alford, Granville and Pomerance showed that there are more than Carmichael numbers up to , and gave arguments which even convinced Shanks (in person-to-person discussions) that Erdos must be correct. Nonetheless, Shanks's skepticism stemmed from an appropriate analysis of the data available to him (and his reasoning is still borne out by Pinch's extended new data), and so we herein derive conjectures that are consistent with Shanks's observations, while fitting in with the viewpoint of Erdos and the results of Alford, Granville and Pomerance.

**[1]**W. R. Alford and J. Grantham,*Carmichael numbers with exactly**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. MR**1283874**, 10.2307/2118576**[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. MR**1322705**, 10.1007/3-540-58691-1_36**[4]**R. Balasubramanian and S. V. Nagaraj,*Density of Carmichael numbers with three prime factors*, Math. Comp.**66**(1997), no. 220, 1705–1708. MR**1422784**, 10.1090/S0025-5718-97-00857-0**[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. MR**712964**, 10.1016/0022-314X(83)90002-1**[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. MR**1189518**, 10.1090/S0025-5718-1993-1189518-9**[8]**P. Erdös,*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**0079031****[9]**P. Erdös and M. Kac,*The Gaussian law of errors in the theory of additive number theoretic functions*, Amer. J. Math.**62**(1940), 738–742. MR**0002374****[10]**W. Galway,*The density of pseudoprimes with two prime factors*(to appear).**[11]**A. Granville,*Primality testing and Carmichael numbers*, Notices Amer. Math. Soc.**39**(1992), 696-700.**[12]**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.**[13]**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. MR**868616**, 10.1093/qmath/37.4.401**[14]**Yong Li,*Galois fields and computation*, Neimenggu Shida Xuebao Ziran Kexue Ban**2**(1991), 13–18 (Chinese, with English summary). MR**1138413****[15]**R. G. E. Pinch,*The Carmichael numbers up to*(to appear).**[16]**R. G. E. Pinch,*The pseudoprimes up to*(to appear).**[17]**Carl Pomerance,*On the distribution of pseudoprimes*, Math. Comp.**37**(1981), no. 156, 587–593. MR**628717**, 10.1090/S0025-5718-1981-0628717-0**[19]**C. Pomerance,*Two methods in elementary analytic number theory*, Number Theory and Applications (Banff, 1988; R. A. Mollin, ed.), NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Reidel, Dordrecht, 1989, pp. 135-161.**[20]**Carl Pomerance,*Carmichael numbers*, Nieuw Arch. Wisk. (4)**11**(1993), no. 3, 199–209. MR**1251482****[21]**Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,*The pseudoprimes to 25⋅10⁹*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, 10.1090/S0025-5718-1980-0572872-7**[22]**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). MR**0106202****[23]**-,*Sur certaines hypothèses concernant les nombres premiers*. Erratum, Acta Arith.**5**(1959), 259. MR**21:493b****[24]**Daniel Shanks,*Solved and unsolved problems in number theory*, 3rd ed., Chelsea Publishing Co., New York, 1985. MR**798284**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y35,
11N60,
11N05,
11N37,
11N25,
11Y11

Retrieve articles in all journals with MSC (2000): 11Y35, 11N60, 11N05, 11N37, 11N25, 11Y11

Additional Information

**Andrew Granville**

Affiliation:
Department of Mathematics, University of Georgia, Athens, Georgia 30602

Email:
andrew@math.uga.edu

**Carl Pomerance**

Affiliation:
Fundamental Mathematics Research, Bell Laboratories, 600 Mountain Ave., Murray Hill, New Jersey 07974

Email:
carlp@research.bell-labs.com

DOI:
http://dx.doi.org/10.1090/S0025-5718-01-01355-2

Received by editor(s):
November 11, 1999

Received by editor(s) in revised form:
July 25, 2000

Published electronically:
October 4, 2001

Additional Notes:
The first author is a Presidential Faculty Fellow. Both authors were supported, in part, by the National Science Foundation

Dedicated:
Dedicated to the two conjecturers, Paul Erdős and Dan Shanks. We miss them both.$^{1}$

Article copyright:
© Copyright 2001
American Mathematical Society