The numbers that fool every base

Necklaces that prove a theorem showed why $a^{p} \equiv a \pmod p$ for every prime $p$, and the exponent that is smaller than Euler’s found the composite numbers that obey the same congruence for every base: the Carmichael numbers. Alwin Korselt characterised them in 1899 without finding one — $n$ is such a number exactly when it is squarefree and $p - 1$ divides $n - 1$ for every prime $p$ dividing $n$ — and Robert Carmichael found the first, 561, in 1910. That essay built a few from three primes chosen to fit. This one asks how many there are.

The question has a definite history. For eighty years after Carmichael it was not known whether there were infinitely many. William Alford, Andrew Granville and Carl Pomerance proved in 1994 that there are, and that their number up to $x$ eventually exceeds $x^{2/7}$. How many there really are is still a measurement, and the measurement disagrees sharply with the best heuristic anyone has.

Korselt’s criterion, row by row #

The table shows why the criterion works. For $561 = 3 \times 11 \times 17$, the numbers $2$, $10$ and $16$ all divide $560$. By Fermat’s theorem $a^{2} \equiv 1 \pmod 3$, $a^{10} \equiv 1 \pmod{11}$ and $a^{16} \equiv 1 \pmod{17}$ for every $a$ not divisible by those primes. Since each exponent divides 560, $a^{560} \equiv 1$ modulo each of the three primes, and therefore modulo their product. No base coprime to 561 can expose it.

Every row of the table works the same way, and every row has at least three prime factors. Two cannot work. If $n = pq$ with $p < q$, then $n - 1 = p(q - 1) + (p - 1)$, and for $q - 1$ to divide this it would have to divide $p - 1$, which is smaller. Squarefreeness is forced as well. If $p^2$ divided $n$, the multiplicative group modulo $p^2$ has an element of order $p$, and $p$ does not divide $n - 1$.

So finding Carmichael numbers is a sieve problem. For every odd $n$ up to some bound, factor it, check that it is squarefree with at least three prime factors, and check the divisibilities. With a table of smallest prime factors for every number up to ten million, that takes about a second, and it finds 105 Carmichael numbers below $10^7$. That matches the published count exactly, as do the intermediate counts of 1, 7, 16 and 43 below $10^3$ to $10^6$.

What the group of units sees #

Korselt’s criterion has a cleaner form in the language of the exponent that is smaller than Euler’s. The residues coprime to $n$ form a group under multiplication, and the smallest exponent $\lambda(n)$ that sends every one of them to 1 is Carmichael’s function. For a prime $p$ the group is cyclic, generated by a residue whose powers are all of them, so $\lambda(p) = p - 1$. For a squarefree product of primes the group splits into the product of the groups for each prime, and $\lambda(n)$ is the least common multiple of the numbers $p - 1$.

So a squarefree $n$ fools every base exactly when $\lambda(n)$ divides $n - 1$. For 561 the least common multiple of 2, 10 and 16 is 80, which divides 560 seven times. For a prime $p$ itself, $\lambda(p) = p - 1$, and the condition is automatic. A Carmichael number is a composite whose group of units has an exponent small enough to hide inside $n - 1$, so that the group looks, from the point of view of exponentiation, like the group of a prime.

That makes the count a question about how often the least common multiple of the $p - 1$ is small compared with the product of the $p$. If the primes dividing $n$ all have $p - 1$ built from the same few small primes, the least common multiple stays small while the product grows. That is the property the 1994 construction exploits on purpose.

How many, to ten to the twenty-first #

Beyond ten million the counting needs much more careful searches. Richard Pinch, over two decades, extended the complete enumeration to $10^{21}$ by generating candidates from their prime factors rather than testing every number.

The counts run 255 below $10^8$, 646 below $10^9$, 1,547 below $10^{10}$, and 20,138,200 below $10^{21}$. On logarithmic axes they form a gently curving line. The curve rises a little more steeply as $x$ grows, so the count is growing faster than any fixed power it has passed. It overtook $x^{2/7}$ early and $x^{1/3}$ between $10^{14}$ and $10^{15}$.

There are far fewer Carmichael numbers than primes — about $2.1 \times 10^{19}$ primes below $10^{21}$ against twenty million Carmichael numbers. They are rare enough that a Fermat test in a random base almost never meets one by chance. They are common enough that any test used systematically will, which is why practical primality testing moved from Fermat’s test to the Miller–Rabin test that the Euclid-number primes were checked with. That test has no Carmichael-like exceptions: every composite number fails it for at least three-quarters of bases.

The exponent, measured and predicted #

The most informative single number is the exponent $\ln C(x)/\ln x$, the power of $x$ that the count equals at each size.

It rises from $0.21$ at $10^4$ through $0.30$ at $10^8$ and $0.33$ at $10^{14}$ to $0.348$ at $10^{21}$, every step up and every step smaller than the last. The proved results say it eventually exceeds $2/7 \approx 0.286$, by Alford, Granville and Pomerance, and, by Glyn Harman’s refinement of their method, eventually exceeds $0.3324$. The measured curve has already passed both.

Paul Erdős gave a heuristic in 1956 that predicts something completely different. He argued that the exponent should tend to one: that $C(x) = x^{1 - o(1)}$, so the Carmichael numbers are, on a logarithmic scale, nearly as numerous as all numbers. His argument was the construction later made rigorous in 1994. Choose a number $L$ with very many small divisors, collect the primes $p$ for which $p - 1$ divides $L$, and multiply subsets of them. Any product that is congruent to 1 modulo $L$ is a Carmichael number, by Korselt. If $L$ has enough divisors, there are so many such primes that many products land on 1 modulo $L$, and the count of those products is nearly as large as $x$.

The gap between $0.35$ and $1$ is not evidence against Erdős. Pomerance refined the heuristic to a precise prediction, $C(x) = x \cdot L(x)^{-1 + o(1)}$ for an explicit function $L(x)$ that grows more slowly than any power of $x$. The correction $L(x)^{-1}$ is so large at feasible sizes that the predicted exponent at $10^{21}$ is not far from what is measured. The exponent is predicted to approach one so slowly that no computation will ever see it get there. The measurement and the conjecture are compatible, and neither can test the other.

How the 1994 proof builds them #

Alford, Granville and Pomerance turned Erdős’s sketch into a proof in three moves. First, choose a number $L$ that is a product of many small primes, so that $L$ has an enormous number of divisors. Second, show that there are many primes $p$ for which $p - 1$ divides $L$. A prime of the form $dk + 1$ for a divisor $d$ of $L$ is such a prime, and the theorem that every class gets its equal share of primes, in a strong quantitative form, supplies enough of them. Third, show that some product of these primes is congruent to 1 modulo $L$.

Any such product is a Carmichael number. Each factor $p$ has $p - 1$ dividing $L$, and the product $n$ is 1 modulo $L$, so $p - 1$ divides $n - 1$ for every factor — Korselt’s criterion. The third step is a statement about the multiplicative group modulo $L$. When a sequence of elements of a finite group is long enough, some nonempty subsequence multiplies to the identity, and the length needed is bounded by a group constant, the Davenport constant. It is the multiplicative cousin of the theorem of Erdős, Ginzburg and Ziv that solutions that come in multiples of p proved from Chevalley and Warning’s counting: among enough elements of a finite abelian group, some nonempty selection always combines to the identity, and nothing about the elements themselves needs to be known beyond the group they live in. With far more primes than that constant, there are not just one but very many products equal to 1 modulo $L$, and counting them gives the lower bound $x^{2/7}$.

The construction explains both the many factors and the difficulty with three. The Carmichael numbers it produces are products of many primes, because the subsequence that multiplies to 1 is long, and nothing in the argument controls its length closely enough to force exactly three. It also explains why the bound is a power of $x$ rather than something close to $x$: the step that finds primes with $p - 1$ dividing $L$ is the weakest, and every improvement in the exponent since 1994 has come from finding more of them.

How many prime factors #

The construction Erdős described multiplies many primes together, and the counts by number of factors show the drift beginning.

Below ten million, 47 Carmichael numbers have three prime factors, 55 have four, and only three have five. Pinch’s tables show the typical number of factors climbing as $x$ grows, and the three-factor ones becoming a small minority. That is the trend Erdős’s construction requires. If most Carmichael numbers are products of many primes, chosen so that their product is 1 modulo some highly divisible $L$, then the factor count must grow.

The three-factor Carmichael numbers behave differently. Their count up to $x$ is known to be at most about $x^{7/20}$, a little more than $x^{1/3}$, by work of Roger Heath-Brown, and is conjectured to grow roughly like $x^{1/3}$. Whether there are infinitely many Carmichael numbers with exactly three prime factors is not known. The 1994 proof produces Carmichael numbers with enormous numbers of factors, and it cannot be made to stop at three.

Fooling one base, and fooling all #

A Carmichael number fools Fermat’s test in every base. A base-2 pseudoprime fools it only in base 2: an odd composite $n$ with $2^{n-1} \equiv 1 \pmod n$. Every Carmichael number is one, and there are more of them.

Below ten million there are 750 base-2 pseudoprimes, of which 105 are Carmichael numbers. The share has fallen from a third at a thousand, where 561 is one of three, to 14% at ten million, and it keeps falling. Most numbers that fool base 2 do so because the order of 2 modulo each of their prime factors happens to divide $n - 1$. That is a property of the single base 2, and it fails for base 3 or base 5 almost every time.

The figure shows why combining a few bases works so well in practice, and why it is not quite enough in principle. Each extra base removes most of the survivors that are not Carmichael numbers, and none of those that are, so the survivors converge on exactly that set. A number that fools both base 2 and base 3 is rarer still, but the Carmichael numbers fool every combination. A test made of Fermat checks in a fixed list of bases always has exceptions, and they are the Carmichael numbers.

Chernick’s family, and the conjecture it needs #

The construction in the exponent that is smaller than Euler’s was a family found by Jack Chernick in 1939: if $6k + 1$, $12k + 1$ and $18k + 1$ are all prime, their product is a Carmichael number.

Korselt’s criterion is easy to check for the product. $n - 1 = 36k(36k^2 + 11k + 1)$ is divisible by $6k$, $12k$ and $18k$. The first case, $k = 1$, gives $7 \times 13 \times 19 = 1{,}729$, the third Carmichael number and Ramanujan’s taxicab number. Below $k = 100{,}000$ there are 842 values of $k$ that work, starting $1, 6, 35, 45, 51, 55, 56, 100$.

Whether there are infinitely many is a case of Dickson’s conjecture, the statement that a set of linear forms with no fixed obstruction is simultaneously prime infinitely often — the same kind of statement as the patterns primes are allowed to make. The conjecture comes with a predicted rate: a constant times the sum of $1/(\ln 6k \cdot \ln 12k \cdot \ln 18k)$. A constant fitted at a tenth of the range predicts 850 by $k = 100{,}000$, against 842 found. The heuristic works as well as such heuristics usually do and is exactly as unprovable. That is why Chernick’s family could never establish infinitude, and why the 1994 proof built Carmichael numbers with many factors by an entirely different route.

What the counts cannot settle #

Every count here to ten million is exact and verified against the published values, and Pinch’s counts beyond are quoted as published. What no count can settle is the limit of the exponent. The measurements show it rising and slowing, and both the proved lower bound and Erdős’s prediction fit them — the first because the exponent has passed it, the second because the predicted approach to one is slow enough to hide below $10^{21}$, and below any size a search will ever reach.

The counts also say nothing about the structure of individual Carmichael numbers beyond their factor counts. Questions such as whether there are infinitely many Carmichael numbers in every arithmetic progression that allows them were settled by extensions of the 1994 method; others, such as whether every number of prime factors from three up occurs infinitely often, remain open. The counts cannot speak to any of them.

Still open: three factors, and the true rate #

Whether there are infinitely many Carmichael numbers with exactly three prime factors is open, and it would follow from Dickson’s conjecture applied to Chernick’s family or to its relatives. The true rate of growth is open too. Erdős’s heuristic and Pomerance’s refinement predict an exponent tending to one; the proofs give a lower bound near one third; the counts give 0.348 at $10^{21}$ and no way to extrapolate.

There is also a question about the strong pseudoprimes, the composites that pass the Miller–Rabin test for a given base. Unlike Carmichael numbers, none passes for every base, but for every finite list of bases there are composites that pass all of them. The smallest such composite for the first $k$ prime bases is known for $k$ up to about thirteen. How fast it grows with $k$ governs whether a deterministic version of the test with a short list of bases can be proved correct, and that is open except under the generalised Riemann hypothesis.

Rare, infinite and still being counted #

The numbers that fool Fermat’s test in every base were found in 1910, proved infinite in 1994, and counted to $10^{21}$, where there are twenty million of them. Their count grows like a power of $x$ that has climbed from a fifth to a third, past what is proved and nowhere near what the heuristic predicts. They thin out among the base-2 pseudoprimes and gain prime factors as they grow, as the heuristic’s construction requires. The simplest family of them, Chernick’s, depends on a conjecture about primes in patterns that is as believable and as unproved as the rest. Korselt’s criterion explains why each one works, and the group of units explains why they are possible at all: a composite whose unit group has a small enough exponent looks, to every Fermat test, exactly like a prime. How many there are is still a matter of counting them, and the counting has run eleven orders of magnitude past the point where a direct sieve gives out without reaching the regime that the heuristic is about.