This post continues my series on favorite theorems from the twenty-first century. For an overview of the categories and my earlier selections, see this post.
My choice for 2004 in combinatorics is Kevin Ford’s solution of an old problem of Erdős concerning the number of distinct entries in a multiplication table. The problem has an exceptionally elementary formulation, but its solution draws on delicate ideas from analytic and probabilistic number theory. Ford’s paper was first submitted in 2004 and appeared in the 2008 volume of the Annals of Mathematics (Ford 2008).
For a positive integer , define Thus is the number of distinct products appearing in the multiplication table.
There are cells in the table, but many of them contain the same integer. Commutativity accounts for the elementary coincidence , but this explains only a constant factor: the number of unordered pairs is still of order . The real source of repetition is that the same integer can admit several substantially different factorizations. For example, provided the relevant factors lie in the table.
Erdős asked how much these coincidences reduce the number of distinct entries. He proved that so the multiplication table occupies an asymptotically vanishing proportion of the integers up to (Erdős 1965). His work in fact identified the main logarithmic exponent in the weaker form where This was already a remarkable result, but it did not determine the full order of magnitude. Indeed, every fixed power of can be absorbed into the factor . The remaining problem was therefore to identify the secondary logarithmic factor.
Ford resolved this problem up to multiplicative constants.
Equivalently, The exponent is quite small, so the density tends to zero very slowly. Nevertheless, the theorem shows that the average multiplicity of a value in the table tends to infinity: Thus the table becomes increasingly repetitive, although only at a polylogarithmic rate.
The connection between multiplication tables and the distribution of divisors is the central idea. For real numbers , let and define In other words, counts the positive integers not exceeding that possess at least one divisor in the interval .
The critical divisor estimate established by Ford is The multiplication-table theorem follows from this estimate by a dyadic decomposition. More precisely,
For the lower bound, suppose that has a divisor Then the complementary divisor satisfies so occurs in the multiplication table.
For the upper bound, write an entry as with . The factor belongs to one of the dyadic intervals and then Consequently, is counted by the corresponding term in the sum. Ford’s uniform estimate for controls the main part of this sum, while the remaining terms are handled by elementary estimates. The geometric decay in ensures that the entire sum has the same order of magnitude as its first few terms.
The unusual constant and the power of reflect the fine structure of the divisors of a typical integer. A rough heuristic helps explain their appearance. Suppose that the part of an integer formed from the relevant small prime factors is squarefree and has prime factors. It then has divisors. If the logarithms of these divisors were distributed uniformly over an interval of length comparable to , one would expect a divisor to fall in once The critical number of prime factors is therefore
The usual Poisson heuristic for the number of prime factors, together with Stirling’s formula, gives This calculation produces both the constant and the first factor .
The uniform-distribution model is, however, too optimistic. Divisors are strongly clustered on a logarithmic scale. In order for the divisors to spread far enough to meet a prescribed interval, the ordered logarithms of the prime factors must satisfy a sequence of barrier conditions. Ford relates this problem to the distribution of uniform order statistics and to a corresponding random-walk avoidance problem. The probability of satisfying the necessary conditions is of order Multiplying this additional factor by the Poisson estimate explains the full power
Theorem is therefore only one consequence of a much broader theory developed in (Ford 2008). Ford determines the order of magnitude of throughout the full range of the parameters , , and . He also studies the number of integers having exactly divisors in . In the principal ranges covered by the paper, and in particular for fixed-ratio intervals such as , the quantities for fixed have the same order of magnitude as . This also disproved an Erdős conjecture according to which integers having exactly one divisor in should become negligible among those having at least one.
What makes Ford’s theorem especially appealing is the distance between its statement and its proof. The question can be explained using nothing more than an ordinary multiplication table, yet the answer depends on the statistical distribution of prime factors, the geometry of sets of divisors, uniform order statistics, and random-walk estimates. The theorem reveals that the apparent repetitions in a multiplication table are governed by a subtle and unexpectedly rigid probabilistic structure.