Alford, Granville, and Pomerance
This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Alford, Granville, and Pomerance | |
|---|---|
 | |
| Name | Alford, Granville, and Pomerance |
| Fields | Number theory |
| Notable works | Proof of existence of infinitely many Carmichael numbers (1994) |
| Authors | W. R. Alford; Andrew Granville; Carl Pomerance |
| Year | 1994 |
| Publication | Journal of the London Mathematical Society |
Alford, Granville, and Pomerance.
Alford, Granville, and Pomerance refers to the collaborative work of W. R. Alford, Andrew Granville, and Carl Pomerance, most famously their 1994 paper proving the infinitude of Carmichael numbers. The partnership linked researchers associated with institutions such as University of California, Berkeley, University of Vermont, University of Montreal, University of Waterloo, Ecole Normale Supérieure, Harvard University, and broader communities including participants of the American Mathematical Society, London Mathematical Society, and attendees of conferences like the International Congress of Mathematicians. Their result immediately influenced topics related to Paul Erdős's conjectures, Korselt's criterion, and later computational investigations by groups at RSA Security and in projects using resources like the Great Internet Mersenne Prime Search infrastructure.
Introduction
The trio's central contribution resolved a long-standing question about the distribution of Carmichael numbers by proving there are infinitely many such composite integers. Their argument synthesized tools from analytic number theory associated with Dirichlet's theorem on arithmetic progressions, sieve methods developed in the tradition of Atle Selberg and Brun's sieve, and multiplicative number theory techniques linked to work by Paul Turán, Patrik Gallagher, and Graham, Goldston, Pintz. Alford, Granville, and Pomerance built on earlier computations and heuristics by Robert Carmichael, R. D. Carmichael, P. Erdős, and numerical tabulations that had been extended by researchers at Mathematical Reviews and laboratories such as Bell Labs and AT&T.
Joint Results and Conjectures
Their landmark theorem established that for sufficiently large X there exist more than X^{2/7} Carmichael numbers up to X, thereby proving infinitude. This quantitative bound stimulated conjectures relating to the density of Carmichael numbers, paralleling heuristics proposed by Granville and earlier expectations posed by Erdős and Pomerance himself in unpublished notes. Subsequent conjectures compared the growth rate to functions appearing in the work of Gábor Halász, John Friedlander, and Henryk Iwaniec on primes in arithmetic progressions and to probabilistic models used by K. Ford and Ben Green. The team also suggested refinements analogous to distribution conjectures for twin primes and to the Hardy–Littlewood conjectures in formulating expected asymptotics for Carmichael counting functions.
Key Theorems and Proofs
The primary theorem combined a construction of many integers n satisfying Korselt's criterion with estimates ensuring these integers are composite and squarefree while each p | n implies p-1 | n-1. The proof leveraged estimates for primes in arithmetic progressions to moduli built from selected product sets, invoking versions of the Bombieri–Vinogradov theorem and results attributable to Vinogradov and Bombieri. The argument required control over exceptional zeroes à la Dirichlet L-function zeros and drew on uniformity results related to Siegel zero phenomena studied by Carl Ludwig Siegel and later refinements used by Heath-Brown. A combinatorial sieve step resembled methods in papers by A. Selberg and was informed by probabilistic sieving heuristics from Pomerance's earlier work.
Methods and Techniques
Techniques included construction of large sets of primes obeying congruence conditions specified by product moduli, application of the Large Sieve and of bilinear forms in primes, and deployment of multiplicative function estimates akin to those in Vinogradov and Turán literature. The authors used explicit parameter optimization similar to strategies in work by Montgomery and Vaughan, balancing smoothness conditions inspired by de Bruijn and structural combinatorics reminiscent of Erdős–Kac probabilistic models. Computational verification for small ranges integrated algorithms from computational algebra systems used by researchers at Los Alamos National Laboratory and codebases influenced by projects like PARI/GP and SageMath contributions.
Impact and Subsequent Developments
Their proof reshaped research on pseudoprimes and cryptographic assumptions underlying systems analyzed by Rivest, Shamir, Adleman, and companies such as RSA Security. It prompted refinements: Pomerance and collaborators produced improved lower bounds, Hugh C. Williams and groups offered algorithmic searches yielding large Carmichael examples, and probabilistic models from Granville informed heuristic density predictions. Follow-up work connected to advances in sieve theory by Goldston, Yıldırım, Maynard, and Zhang expanded techniques for primes with prescribed residue properties. The result also influenced educational expositions in texts by Tom Apostol, Iwaniec and Kowalski, and survey chapters in The Princeton Companion to Mathematics.
Selected Problems and Open Questions
Open problems include sharpening the exponent in the lower bound for the counting function of Carmichael numbers to match heuristics proposed by Erdős and Granville; establishing an asymptotic formula analogous to Prime Number Theorem statements for Carmichael counts; and determining the density of Carmichael numbers in arithmetic progressions generalizing Dirichlet-type distribution results. Further questions ask whether methods can extend to pseudoprimes for other bases studied by Euler and Fermat-type analogues, and whether deeper control of exceptional zeros, as in proposed improvements by Hooley and Iwaniec, could yield stronger quantitative theorems. Computational challenges remain for finding Carmichael numbers with prescribed structural properties, inspiring collaborations between number theorists and computational groups at institutions like Microsoft Research and Google.