Two contradictory conjectures concerning Carmichael numbers
HTML articles powered by AMS MathViewer
- by Andrew Granville and Carl Pomerance PDF
- Math. Comp. 71 (2002), 883-908 Request permission
Abstract:
Erdős conjectured that there are $x^{1-o(1)}$ Carmichael numbers up to $x$, whereas Shanks was skeptical as to whether one might even find an $x$ up to which there are more than $\sqrt {x}$ Carmichael numbers. Alford, Granville and Pomerance showed that there are more than $x^{2/7}$ Carmichael numbers up to $x$, and gave arguments which even convinced Shanks (in person-to-person discussions) that Erdős 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 Erdős and the results of Alford, Granville and Pomerance.References
- W. R. Alford and J. Grantham, Carmichael numbers with exactly $k$ prime factors (to appear).
- 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, DOI 10.2307/2118576
- 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, DOI 10.1007/3-540-58691-1_{3}6
- R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, Math. Comp. 66 (1997), no. 220, 1705–1708. MR 1422784, DOI 10.1090/S0025-5718-97-00857-0
- 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, DOI 10.1016/0022-314X(83)90002-1
- 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, DOI 10.1090/S0025-5718-1993-1189518-9
- Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
- Leonard Eugene Dickson, New First Course in the Theory of Equations, John Wiley & Sons, Inc., New York, 1939. MR 0000002
- W. Galway, The density of pseudoprimes with two prime factors (to appear).
- A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc. 39 (1992), 696–700.
- 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.
- 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, DOI 10.1093/qmath/37.4.401
- Yong Li, Galois fields and computation, Neimenggu Shida Xuebao Ziran Kexue Ban 2 (1991), 13–18 (Chinese, with English summary). MR 1138413
- R. G. E. Pinch, The Carmichael numbers up to $10^{16}$ (to appear).
- R. G. E. Pinch, The pseudoprimes up to $10^{12}$ (to appear).
- Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
- 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.
- Carl Pomerance, Carmichael numbers, Nieuw Arch. Wisk. (4) 11 (1993), no. 3, 199–209. MR 1251482
- 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. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- 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 106202, DOI 10.4064/aa-4-3-185-208
- H. S. Vandiver, Certain congruences involving the Bernoulli numbers, Duke Math. J. 5 (1939), 548–551. MR 21
- Daniel Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea Publishing Co., New York, 1985. MR 798284
Additional Information
- Andrew Granville
- Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
- MR Author ID: 76180
- ORCID: 0000-0001-8088-1247
- Email: andrew@math.uga.edu
- Carl Pomerance
- Affiliation: Fundamental Mathematics Research, Bell Laboratories, 600 Mountain Ave., Murray Hill, New Jersey 07974
- MR Author ID: 140915
- Email: carlp@research.bell-labs.com
- 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
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 883-908
- MSC (2000): Primary 11Y35, 11N60; Secondary 11N05, 11N37, 11N25, 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-01-01355-2
- MathSciNet review: 1885636
Dedicated: Dedicated to the two conjecturers, Paul Erdős and Dan Shanks. We miss them both.$^{1}$