Two contradictory conjectures concerning Carmichael numbers
Authors:
Andrew Granville and Carl Pomerance
Journal:
Math. Comp. 71 (2002), 883908
MSC (2000):
Primary 11Y35, 11N60; Secondary 11N05, 11N37, 11N25, 11Y11
Published electronically:
October 4, 2001
MathSciNet review:
1885636
Fulltext 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 persontoperson 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
(95k:11114), http://dx.doi.org/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
(96d:11136), http://dx.doi.org/10.1007/3540586911_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
(98d:11110), http://dx.doi.org/10.1090/S0025571897008570
 [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
(85j:11012), http://dx.doi.org/10.1016/0022314X(83)900021
 [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
(94b:11124), http://dx.doi.org/10.1090/S00255718199311895189
 [8]
P.
Erdös, On pseudoprimes and Carmichael numbers, Publ.
Math. Debrecen 4 (1956), 201–206. MR 0079031
(18,18e)
 [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
(2,42c)
 [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), 696700.
 [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), 170.
 [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
(88a:11092), http://dx.doi.org/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
(92m:11137)
 [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
(83k:10009), http://dx.doi.org/10.1090/S00255718198106287170
 [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. 135161.
 [20]
Carl
Pomerance, Carmichael numbers, Nieuw Arch. Wisk. (4)
11 (1993), no. 3, 199–209. MR 1251482
(94h:11085)
 [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
(82g:10030), http://dx.doi.org/10.1090/S00255718198005728727
 [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
(21 #4936)
 [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
(86j:11001)
 [1]
 W. R. Alford and J. Grantham, Carmichael numbers with exactly prime factors (to appear).
 [2]
 W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 140 (1994), 703722. MR 95k:11114
 [3]
 W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses, Lecture Notes in Computer Sci. 877 (1995), 116. MR 96d:11136
 [4]
 R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, Math. Comp. 66 (1997), 17051708. MR 98d:11110
 [5]
 E. R. Canfield, P. Erdos and C. Pomerance, On a problem of Oppenheim concerning ``Factorisatio Numerorum", J. Number Theory 17 (1983), 128. MR 85j:11012
 [6]
 I. Damgård, P. Landrock and C. Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), 177194. MR 94b:11124
 [8]
 P. Erdos, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201206. MR 18:18e
 [9]
 P. Erdos and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math 62 (1940), 738742. MR 2:42c
 [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), 696700.
 [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), 170.
 [13]
 A. Ivic and G. Tenenbaum, Local densities over integers free of large prime factors, Quart. J. Math. Oxford Ser. (2) 37 (1986), 401417. MR 88a:11092
 [14]
 R. G. E. Pinch, The Carmichael numbers up to , Math. Comp. 61 (1993), 381391. MR 92m:11137
 [15]
 R. G. E. Pinch, The Carmichael numbers up to (to appear).
 [16]
 R. G. E. Pinch, The pseudoprimes up to (to appear).
 [17]
 C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587593. MR 83k:10009
 [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. 135161.
 [20]
 C. Pomerance, Carmichael numbers, Nieuw Arch. Wisk. 11 (1993), 199209. MR 94h:11085
 [21]
 C. Pomerance, J. Selfridge and S. S. Wagstaff Jr., The pseudoprimes to , Math. Comp. 35 (1980), 10031026. MR 82g:10030
 [22]
 A. Schinzel and W. Sierpinski, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185208. MR 21:4936
 [23]
 , Sur certaines hypothèses concernant les nombres premiers. Erratum, Acta Arith. 5 (1959), 259. MR 21:493b
 [24]
 D. Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea, New York, 1985. MR 86j:11001
Similar Articles
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.belllabs.com
DOI:
http://dx.doi.org/10.1090/S0025571801013552
PII:
S 00255718(01)013552
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
