Most numbers are missing from the table

Two neighbours share out their small primes asked how the prime factors of $n$ and $n + 1$ are related, and found that the question, simple to state, sits at the frontier of what can be proved about multiplicative structure. This essay asks one that looks even more elementary. Write out the multiplication table up to $N \times N$, as every child does up to ten or twelve. It has $N^2$ cells, each holding a product $ab$ with $a, b \le N$, and every entry is at most $N^2$. How many different numbers does it contain?

Not $N^2$, obviously, since $ab = ba$, so at most about half; and fewer than half, since 12 is $2 \cdot 6$ and $3 \cdot 4$. The surprise is how much fewer, and how the shortfall behaves. Paul Erdős showed in 1955 that the share of numbers up to $N^2$ that appear in the table goes to nought. Kevin Ford found in 2008, after half a century of refinements, exactly how fast — so slowly that no computation will ever see the share come anywhere near nought — and the reason is a fact about prime factors that how many primes a typical number has already measured.

Nine hundred cells, three hundred and eight numbers #

The hero writes out the table up to $30 \times 30$ and shades each cell whose product is new, reading the lower triangle row by row. The upper triangle is pale throughout, since it repeats the lower one by symmetry. Of the 465 cells on or below the diagonal, only 308 are new; the rest repeat a product already met. The most crowded number is 60, which fills ten cells — $2 \cdot 30$, $3 \cdot 20$, $4 \cdot 15$, $5 \cdot 12$, $6 \cdot 10$, and their reflections.

The pattern of new cells is irregular, but its density visibly falls towards the bottom right: a product of two numbers near 30 is a number near 900 with at least two factors near 30, and such numbers usually have other factorisations too, some of them already in the table. In the top rows almost every cell is new, because $1 \cdot b$ and $2 \cdot b$ are small numbers that few other pairs can reach. The table is dense in repeats exactly where its entries are large and have many divisors.

The counts for larger tables are made exactly, with one bit for each number up to $N^2$: run through the table row by row, mark each product, and count the marks. At $N = 10{,}000$ the bitset has a hundred million bits, and the sweep that fills it, adding row $N$’s products $N \cdot b$ for $b \le N$ as the table grows, gives $M(N)$, the number of distinct entries, for every $N$ up to that size at once.

A share that falls, and how slowly #

The share $M(N)/N^2$ starts at 42% for the $10 \times 10$ table, which holds 42 different numbers. At $N = 100$ it is 29.1%; at 1,000, 24.8%; at 10,000, 22.50%, which is 22,504,348 different numbers among the hundred million up to $10^8$. The figure plots every value on a logarithmic scale of $N$, and the fall is steady and slow: each tenfold increase in the table’s size removes only a couple of percentage points, and the losses are shrinking.

The share does go to nought — Erdős proved it — but at a pace the figure can barely register. Ford’s theorem is that $M(N)$ is of the order

$$\frac{N^2}{(\ln N)^{\delta} (\ln\ln N)^{3/2}}, \qquad \delta = 1 - \frac{1 + \ln\ln 2}{\ln 2} = 0.08607\ldots,$$

meaning that $M(N)$ divided by that expression stays between two positive constants for ever. The dashed curve is that expression with its constant fitted at 10,000. It is far from the data at small $N$, which says the asymptotic shape has not yet taken over, and it continues so slowly that a table with a billion rows would still have about 13% of its candidate numbers. The power $(\ln N)^{0.0861}$ is a factor of $1.3$ at a billion and of 2 only when $\ln N$ is about 3,000 — a table with more than a thousand digits in its side.

Why products are rare #

The reason is a mismatch in prime factors. The Hardy–Ramanujan theorem, which how many primes a typical number has checked, says that a typical number $m$ has about $\ln\ln m$ prime factors, and the same bell on thinner sets found the count spread around that value in a bell of width $\sqrt{\ln\ln m}$. A typical number below $N^2$ has about $\ln\ln N^2 = \ln\ln N + \ln 2$ prime factors — barely more than a typical number below $N$. But a product $ab$ of two numbers below $N$ has the prime factors of both, about $2\ln\ln N$ of them. Products are numbers with roughly twice the usual number of prime factors, and such numbers are a thin set: the bell is centred at $\ln\ln N$, and $2\ln\ln N$ is far out in its tail.

The figure shows the mismatch at $N = 1{,}000$. Among all numbers below a million the average number of prime factors, counted with multiplicity, is 3.63, and the histogram peaks at three. Among the 248,082 numbers that appear in the table, the average is 4.99 and the peak is at four; primes, which make up 7.8% of the numbers below a million, are almost absent from the table — only those below a thousand appear, as $1 \cdot p$ — and numbers with six or more prime factors are twice as common in the table as outside it. Even at this modest size the table has visibly drawn its entries from the far side of the bell.

Erdős’s argument in three lines #

The proof that the share goes to nought needs only the bell, and it is short enough to give whole. Split the numbers below $N^2$ by how many prime factors they have. Those with fewer than $1.5\ln\ln N$ prime factors are numbers whose count falls well short of $2\ln\ln N$; those with more are numbers whose count is well above the typical $\ln\ln N$. Every product $ab$ in the table falls into one of two cases: either $a$ or $b$ itself has an unusually small or large number of prime factors for its size, or $ab$ has close to $2\ln\ln N$ of them and so lies in the second group.

The Hardy–Ramanujan inequality bounds both. Numbers below $N$ whose count of prime factors strays far from $\ln\ln N$ are a vanishing share of the numbers below $N$, so the products they contribute are a vanishing share of $N^2$; and numbers below $N^2$ with about twice the typical count are a vanishing share of $N^2$, for the same reason. Together the two cases cover the table, and each is a vanishing share, so $M(N)/N^2$ goes to nought. The argument says nothing about how fast, because “vanishing share” comes from a bell whose tails fall only like a power of $\ln N$; making those tails precise is what produced the exponent $\delta$, and it took the next fifty years.

The largest prime factor gives a cruder obstruction, and it is worth separating from this one. A number below $N^2$ with a prime factor larger than $N$ cannot be a product of two numbers below $N$, since that prime would have to divide one of them. The largest prime in a typical number found the law of that factor, Dickman’s, and by it the numbers below $N^2$ whose largest prime exceeds $\sqrt{N^2}$ make up a share tending to $\ln 2 \approx 0.693$. So at most 31% of the numbers could ever appear, at any size, and the table at 10,000 holds 22.5%. But this obstruction removes a fixed fraction; it cannot make the share go to nought. What drives the share down without limit is the count of prime factors, which no fixed fraction describes.

Where the exponent comes from #

The exponent $\delta = 0.0861$ looks arbitrary and is not. It is a large-deviation rate: the cost, measured in powers of $\ln N$, of a number having many more prime factors than usual. The number of integers up to $x$ with about $u \ln\ln x$ prime factors, for $u > 1$, is roughly $x/(\ln x)^{Q(u)}$ with

$$Q(u) = u\ln u - u + 1,$$

which is nought at $u = 1$, the typical count, and grows on either side. A product $ab$ is in the table only if its prime factors can be split into two groups, one for $a$ and one for $b$, each with product at most $N$. Ford’s analysis shows that the numbers in the table are, overwhelmingly, those with about $u = 1/\ln 2 \approx 1.443$ times the typical number of prime factors — enough factors that a split into two halves of the right sizes becomes likely, few enough that the numbers are not too rare. The cost of that many factors is

$$Q\!\left(\tfrac{1}{\ln 2}\right) = \frac{1}{\ln 2}\ln\frac{1}{\ln 2} - \frac{1}{\ln 2} + 1 = 1 - \frac{1 + \ln\ln 2}{\ln 2} = \delta.$$

The $1/\ln 2$ is the point where the number of ways to split $k$ prime factors into two groups, $2^k$, starts to outweigh how rare it is to have $k$ of them — the base 2 of the split meeting the natural logarithm of the counting. The $(\ln\ln N)^{3/2}$ is a finer correction from the requirement that the two halves be balanced in size, which is a question about the shape of a number’s divisors: whether some divisor falls in a given range.

The same exponent turns up in a problem that does not mention tables. Erdős asked what share of numbers have a divisor between $y$ and $2y$, and Ford’s theorem answers it with the same $\delta$: a number has a divisor in a range like that only if its prime factors can be split to land a product in a window, the same splitting the table needs. Two questions that look unrelated are one question about how the prime factors of a typical number can be divided into two piles.

How many cells each number fills #

The shortfall has a second face. If most numbers below $N^2$ are missing, the table’s million cells are shared out among relatively few numbers, and some must fill many cells. The figure counts, for $N = 1{,}000$, how many cells each entry occupies. 515 numbers appear exactly once, and every one of them is a square: a product $ab$ with $a \ne b$ always appears again as $ba$, so a number appearing once has only the factorisation $a \cdot a$ within the table. 144,208 numbers appear exactly twice, as one pair and its reflection. The most crowded is $27{,}720 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11$, which fills 58 cells: it has 96 divisors, and 58 of them lie between $27.72$ and $1{,}000$, so that both $d$ and $27{,}720/d$ fit in the table.

The counts are a truncated divisor function: the number of divisors $d$ of $m$ with $m/N \le d \le N$. Odd counts occur only for squares, since the divisors pair off as $d$ and $m/d$ except for the square root. The long tail is the numbers with many small prime factors, the highly composite numbers that the shape of a number’s divisors found have divisors spread evenly enough for many to land in the window. The table’s million cells are therefore dominated not by typical numbers but by a minority of highly divisible ones, each filling many cells — the other side of the same mismatch.

The correction, still out of reach #

If Ford’s order of magnitude described the table at the sizes computed, the solid curve would be flat. It is not. Multiplying the share by the full correction gives $0.52$ at $N = 30$, $0.63$ at 100, $0.79$ at 1,000 and $0.90$ at 10,000 — still climbing, though more slowly with each decade. Multiplying by $(\ln N)^\delta$ alone gives a curve that falls instead, from $0.38$ to $0.27$. The truth over this range lies between the two corrections, and Ford’s theorem says that eventually the full correction wins and the solid curve levels off between two positive constants.

That is the reason the problem resisted measurement. Erdős’s 1960 result had the exponent $\delta$ but not the $\ln\ln$ factor; Gérald Tenenbaum’s work in the 1980s narrowed the gap; and the factor $(\ln\ln N)^{3/2}$, which Ford pinned down in 2008, changes by a factor of about $1.75$ between $N = 100$ and $N = 10{,}000$ while the share itself changes by a factor of only $1.3$. At every size a computer can reach, the lower-order corrections are as large as the leading terms, and no numerical experiment could have guessed the right shape. The theorem came from the large-deviation argument above, and the computation can only show that it is consistent with what the table does.

Unique factorisation, used backwards #

The whole problem rests on unique factorisation, and uses it in an unusual direction. Usually the fundamental theorem of arithmetic is a tool for writing a number as a product in one way. Here it is a tool for counting the ways a number can be written as a product of two factors below $N$: those ways are determined by how its unique multiset of prime factors can be split into two groups with products in a window. A number whose prime factors cannot be split that way is missing from the table, and the question of how many numbers are missing becomes a question about the distribution of the multisets of prime factors — which, by Hardy–Ramanujan and its refinements, is understood well enough to give the answer.

In a number system without unique factorisation the question would change character. Among the numbers $a + b\sqrt{-5}$, where $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ in two genuinely different ways, a multiplication table of the elements of size up to $N$ would have more coincidences of a different kind, and counting them would need the ideal classes that the class number essays introduced. The table problem in the ordinary integers is a statement about how the unique factorisations of typical numbers look, and it is answered by the same probabilistic model of prime factors that Erdős and Kac built.

Every product marked, and still too short a range #

The counts are exact. Every product $ab$ with $a, b \le 10{,}000$ is marked in a table of $10^8$ bits, and $M(N)$ is read off for every $N$ along the way; the hero’s 308 is checked against the same count. The prime-factor counts for every number below a million come from a sieve that records each number’s smallest prime factor, and the cell counts from tallying every product of the $1{,}000 \times 1{,}000$ table. Nothing is sampled and nothing is estimated except the fitted constant in Ford’s curve.

The figures cannot show that the share tends to nought, nor that Ford’s shape is right; both are theorems, and the computed range is too short for the leading behaviour to dominate. The large-deviation explanation of $\delta$ is the argument behind the theorem, sketched; the figure on prime factors shows the mismatch it depends on but does not measure the exponent, which would need tables far beyond any computer.

Still open: whether Ford’s ratio has a limit #

Ford’s theorem gives the order of magnitude, not an asymptotic formula: it says that $M(N)(\ln N)^\delta(\ln\ln N)^{3/2}/N^2$ stays between two positive constants, not that it tends to one. Whether that quantity has a limit, and if so what it is, is unknown. The last figure shows it still climbing at 10,000, and nobody knows whether it levels off near 1, or 2, or keeps creeping towards some value far from any computed one.

Higher-dimensional tables raise the same question with different exponents. The number of distinct products $abc$ with $a, b, c \le N$ is also a vanishing share of $N^3$, and Dimitris Koukoulopoulos found its order of magnitude in 2010 with an exponent from the same large-deviation function at a different point, $u = 2/\ln 3$ for three factors, the general rule being $(k - 1)/\ln k$ for $k$ of them. The multiplicative structure behind all of them is the same — how the prime factors of a typical number can be shared among $k$ piles of prescribed sizes — and the finest version of that question, the joint distribution of the sizes of a number’s divisors, is still being worked out.

A table with room for few #

The $N \times N$ multiplication table holds a vanishing share of the numbers up to $N^2$ — 42% at $N = 10$, 22.5% at $N = 10{,}000$ — because a product of two numbers below $N$ has about twice the usual number of prime factors, and numbers like that are rare. Ford’s theorem puts the count at $N^2/((\ln N)^{0.0861}(\ln\ln N)^{3/2})$, where $0.0861 = 1 - (1 + \ln\ln 2)/\ln 2$ is the cost of having $1/\ln 2$ times the typical number of prime factors, the number at which splitting them into two halves becomes likely. The table’s cells are crowded onto highly divisible numbers — 27,720 fills 58 of them — and the share falls so slowly that at every size a computer can reach, the corrections to the theorem are as large as the theorem itself.