The same bell on thinner sets

How many primes a typical number has set out the Erdős–Kac theorem. Count the distinct primes dividing a number $m$ and call the count $\omega(m)$. For a typical $m$ near $N$, $\omega(m)$ is about $\log \log N$, and across all the numbers up to $N$ it is spread in a bell curve whose variance is also $\log \log N$. The model behind the theorem is that each prime $p$ divides a random number with probability $1/p$, independently of the others, so that $\omega$ is a sum of many small independent coin tosses — a bell curve assembled out of coin flips, with the coins weighted by $1/p$.

That essay ended by naming the sets the model has no obvious claim on: the numbers one less than a prime, $p - 1$, and the values $n^2 + 1$. Both are thin. Among the numbers near twenty million about one in sixteen is one less than a prime, and the squares plus one are thinner still — only two thousand of them below four million. More to the point, neither set is random with respect to small primes. Every $p - 1$ is even. No $n^2 + 1$ is divisible by 3. The coin tosses that make the bell are not fair coins for these sets, and it is not obvious that they are coins at all.

The bell is there on all three. Heini Halberstam proved in 1956 that it must be: the Erdős–Kac theorem holds for the shifted primes $p - 1$ and for the values of any irreducible polynomial, $n^2 + 1$ among them, with the same leading $\log \log$ for the mean and the variance. What the figures add is the size of the differences between the three sets, which the theorem’s leading term does not see, and an account of where each difference comes from.

Counting the prime factors of the squares plus one exactly #

The count for whole numbers is easy: add one to every multiple of every prime up to twenty million, and the total at each $m$ is $\omega(m)$. The count for $p - 1$ is read from the same table. The numbers $n^2 + 1$ need more care, because they reach four million million and no table goes that far.

The method uses a fact from two squares and a lattice. An odd prime $p$ divides some $n^2 + 1$ exactly when $-1$ is a square modulo $p$, which happens exactly when $p$ leaves remainder 1 on division by 4 — the same primes that are sums of two squares. For each such $p$ up to two million there are two residues $r$ with $r^2 \equiv -1$, found by raising any non-residue to the power $(p - 1)/4$, and $p$ divides $n^2 + 1$ exactly when $n \equiv \pm r$. So for each prime the multiples are two arithmetic progressions, and stepping through them marks every $n$ the prime divides. The two squares actually produced used the same square root of $-1$ to construct the two squares themselves.

After every prime up to two million has been divided out of $n^2 + 1$, what remains is either 1 or a single prime. It cannot be a product of two primes above two million, since that product would exceed $n^2 + 1$. So $\omega(n^2 + 1)$ is the number of small primes marked plus one if anything is left, exactly, for all two million values.

How Halberstam’s argument goes #

The proof for whole numbers that how many primes a typical number has described works by moments. Write $\omega$ as a sum, over the primes $q$ up to some bound, of the indicator that $q$ divides the number. The $k$-th moment of that sum expands into counts of numbers divisible by a product of $k$ chosen primes, and for whole numbers the count of multiples of $q_1 q_2 \cdots q_k$ up to $N$ is $N/(q_1 \cdots q_k)$ with an error of at most 1. The indicators therefore behave, moment by moment, exactly like independent coins with probabilities $1/q$, and a sum of independent coins whose variance grows without bound has moments approaching the bell’s.

Halberstam’s insight was that the same expansion works for any set in which the members divisible by a product of distinct primes can be counted with a small error, and that the probabilities then multiply. For $n^2 + 1$ the number of $n \le x$ for which $q_1 \cdots q_k$ divides $n^2 + 1$ is $x \cdot \rho(q_1)\cdots\rho(q_k)/(q_1 \cdots q_k)$ plus an error bounded by the number of residues, by the Chinese remainder theorem. For $p - 1$ the count of primes $p \le x$ with $p \equiv 1$ modulo $q_1 \cdots q_k$ is the number of primes in an arithmetic progression, and its error term is the delicate part: it needs the primes to be spread evenly over residue classes for many moduli at once, on average, which is a theorem of the Bombieri–Vinogradov kind. In both cases the coins are unfair but still independent, in the sense the moments need, and that is enough.

Which primes divide which numbers #

The three sets differ first in how often each small prime divides their members.

For whole numbers, a prime $q$ divides one number in $q$. For the numbers $p - 1$, $q$ divides $p - 1$ exactly when $p$ leaves remainder 1 on division by $q$; primes larger than $q$ are spread evenly over the $q - 1$ non-zero remainders, by Dirichlet’s theorem in its quantitative form, so the share is $1/(q - 1)$ — slightly more than $1/q$, and for $q = 2$ it is all of them. For $n^2 + 1$, the share is the number of solutions of $x^2 \equiv -1$ modulo $q$, divided by $q$: two solutions when $q \equiv 1 \pmod 4$, none when $q \equiv 3$, one when $q = 2$.

The squares plus one are therefore lopsided in a way the other sets are not. Half the primes never divide them at all, and the other half divide them twice as often as they divide a random number. Adding up the probabilities, $\sum_q \rho(q)/q$ over the primes up to $x$ grows like $\log \log x$ exactly as $\sum_q 1/q$ does, because the primes are split evenly between the two remainders modulo 4 — that is the content of Dirichlet’s theorem again, applied to the modulus 4. The losses and the gains cancel in the leading term. What survives is a constant.

The cancellation can be stated exactly. Dirichlet’s theorem in Mertens’s form says that the reciprocals of the primes $q \equiv 1 \pmod 4$ up to $x$ add to $\tfrac12 \log \log x$ plus a constant, and so do the reciprocals of the primes $q \equiv 3 \pmod 4$. The squares plus one take twice the first sum and none of the second, $2 \cdot \tfrac12 \log\log x$, which is $\log \log x$ again. Had the primes favoured one remainder over the other, even slightly in the limit, the leading term itself would change; that they do not is the theorem that makes the bell’s location the same for all three sets. The numbers $p - 1$ need nothing so delicate: each probability $1/(q-1)$ exceeds $1/q$ by about $1/q^2$, and those excesses form a convergent series from the start.

Three averages and three constants #

The mean of $\omega$ over each set is the sum of those probabilities, and each sum is $\log \log$ of the size plus a constant.

For whole numbers the constant is Franz Mertens’s, $0.2615$, from the asymptotic $\sum_{q \le x} 1/q = \log \log x + 0.2615 + o(1)$. For $p - 1$ every prime contributes $1/(q - 1) - 1/q = 1/(q(q-1))$ extra, and these extras add to $0.7731$, so the constant is $1.035$ — a typical $p - 1$ has one more prime factor than a typical number of the same size, most of it the 2 that every $p - 1$ carries. For $n^2 + 1$ the extras are $(\rho(q) - 1)/q$, positive for half the primes and negative for the other half, and they add to $-0.335$; the constant is $-0.073$, and a typical square plus one has slightly fewer prime factors than a typical number its size.

The averages approach their lines from below, and slowly. At twenty million the whole numbers sit 0.027 below Mertens’s constant and the $p - 1$ are 0.113 below theirs; the squares plus one, followed out to four million million, are 0.013 below. The gaps are of the order of one over the logarithm of the size, the next term in Mertens’s theorem, and they shrink as the figure moves right. The constants were computed independently of the averages, by summing the probabilities of the previous figure over the primes up to twenty million, and the averages head for them.

The variances, far behind #

The variance does not cooperate so readily.

The theorem says the variance is $\log \log$ of the size plus lower-order terms, and the lower-order terms are large. At twenty million the variance for whole numbers is 1.14 against a $\log \log$ of 2.82, as the previous essay found; for $p - 1$ it is 0.94; for $n^2 + 1$ at four million million it is 1.34 against 3.37. The variance has lower-order terms of its own, and for all three sets they are negative and comparable to the leading term at every size a computation can reach. The ordering of the three is itself informative. The numbers $p - 1$ have the largest mean and the smallest variance, and the reason is the prime 2: it divides every one of them, so it adds one to the count and nothing to the spread. The prime 3 divides exactly half of them, the fairest coin possible, and the larger primes divide them a little more often than they divide random numbers. A coin that always lands the same way contributes no variance, and $p - 1$ has one such coin and several nearly fair ones in place of the whole numbers’ lopsided small primes. The bells in the hero figure are standardised by each set’s actual spread, not by $\sqrt{\log \log}$; standardised by the theorem’s spread they would be far too narrow.

That is the slow convergence how fast the bell arrives measured for sums of independent terms, made worse here because the number of effective terms is $\log \log N$, which is about three for every size that has ever been computed. The theorem is about a limit in which $\log \log N$ is large, and $\log \log N$ reaches 5 only when $N$ has about 65 digits.

How many have exactly k #

The constant shifts show up as shifts of the whole distribution.

Whole numbers between ten and twenty million most often have three distinct prime factors. The numbers $p - 1$ in the same range most often have four — every one of them is even, and the 2 is one factor for free. The squares plus one, though a hundred thousand times larger, most often have three: the primes 3, 7, 11, 19, … that never divide them hold the count down, and although their $\log \log$ is about half a unit larger than the whole numbers’, their negative constant spends a third of a unit of it, and their mean is only about a quarter higher. The case $k = 1$ for $p - 1$ is empty except at $p = 3$ and $p = 5$ and the other primes one more than a power of two: $p - 1$ is even, so $\omega(p - 1) = 1$ means $p - 1$ is a power of 2, and $p$ is a Fermat prime.

One prime factor, and an open problem #

The case $k = 1$ for the squares plus one is famous. It is the question whether $n^2 + 1$ is prime.

Godfrey Hardy and John Littlewood conjectured in 1923 that the number of $n \le x$ with $n^2 + 1$ prime is about $\tfrac12 C \int_2^x dt/\log t$, where $C$ is a product over primes of exactly the probabilities in the second figure, $\prod_q (1 - \rho(q)/q)/(1 - 1/q)$, which comes out at $1.3728$. The count up to two million is 102,205; the prediction is 102,302. The ratio has settled within a few per cent of 1 from $x = 3{,}000$ on. The prediction is built from the same arithmetic as the averages: the chance that $n^2 + 1$ escapes every small prime, corrected prime by prime for how often each one divides it. The constant is larger than 1 because half the primes can never divide a square plus one, so a square plus one is about 1.37 times likelier to be prime than a random whole number of the same size — half of them are even, but so are half of all numbers, and the prime 2 neither helps nor hurts; the primes that divide it twice as often pull the other way, and the product of all the corrections settles at 1.3728. It is the same lopsidedness that moved the average count of prime factors down, seen at the other end of the distribution.

Whether there are infinitely many primes of the form $n^2 + 1$ is not known. Edmund Landau listed it in 1912 as one of four problems about primes that seemed unattackable, and it still is; which way a prime’s two squares point met it as the case $b = 1$ of a question about primes $a^2 + b^2$. The contrast with the bell curve is the point of the figure. That the number of prime factors of $n^2 + 1$ follows a bell curve with mean and variance $\log \log n$ is a theorem; that the number is 1 infinitely often is a conjecture with no proof in sight. Halberstam’s theorem is about typical behaviour and needs only that most values have about the expected count, which a sieve can show. Landau’s problem is about a rare event, values with the fewest possible factors, and the sieve that cannot finish explained why sieves cannot by themselves detect primes in a thin sequence: they cannot tell numbers with one prime factor from numbers with two, a limitation two halves a sieve cannot tell apart made precise.

Still open: the sets a sieve cannot reach #

Halberstam’s method handles any set in which the members divisible by each small prime can be counted with a good error term, and $p - 1$ and polynomial values both qualify. For other natural sets it is not known whether the bell holds. For sets that grow exponentially or faster, such as the numbers $k! + 1$, a sieve has nothing to work with: the members up to $x$ number about $\log x / \log \log x$, far too few for the averaging every method here depends on, and very little is known about how their prime factors are distributed. And for all the sets in this essay, the joint behaviour of $\omega$ at neighbouring members — whether the counts for $n^2 + 1$ and $(n+1)^2 + 1$ are independent, as for whole numbers they are in the limit — depends on correlations between primes in polynomial sequences, the question the patterns primes are allowed to make showed is decided by remainders when it is decided at all.

A model that survives being made unfair #

The Erdős–Kac theorem looked like a statement about randomness — fair coins, one per prime. On the numbers one less than a prime and on the squares plus one the coins are not fair: one prime divides every member, half the primes divide none, the other half divide twice as often. The bell survives all of it, because the leading term depends only on the total probability, $\sum \rho(q)/q$, and that total grows like $\log \log$ for every set whose primes are spread evenly over remainders. What the unfairness changes is a constant, computed in advance from the probabilities and found again in the averages: 0.2615, 1.035 and −0.073. The one question the model cannot answer is the one it answers worst — how often the count is exactly one.