On product sets of arithmetic progressions

On product sets of arithmetic progressions, Discrete Analysis 2023:10, 31 pp.

The multiplication table problem is a very simply stated question of Erdős: how many numbers appear in the multiplication table of the numbers from 1 to $n$? (Of course, this means how many distinct numbers, or the answer would obviously be $n^2$.)

A simple lower bound comes from the prime number theorem and the fundamental theorem of arithmetic. Indeed, there are around $n/\log n$ primes between 1 and $n$ and all their products are distinct, which gives a lower bound of around $\binom{n/\log n}2$. To obtain a non-trivial upper bound, one can use the fact that almost all integers between 1 and $m$ have approximately $\log\log m$ prime factors, with multiplicity. (This fact is easy to prove: with more sophisticated but still elementary arguments one can obtain the more accurate expression $\log\log m + A + O(1/\log m)$, where $A$ is an explicit constant.) It follows that almost all elements of the $n\times n$ multiplication table have approximately $2\log\log n$ prime factors, whereas almost all integers between 1 and $n^2$ have approximately $\log\log(n^2)=\log\log n +\log 2$ prime factors, which shows that the multiplication table has size $o(n^2)$. By running this argument carefully, using what is known about the distribution of the number of prime factors of a random number between 1 and $m$, Erdős showed that the multiplication table has size $n^2/(\log n)^{c+o(1)}$, where $c$ is the somewhat surprising constant $1-\frac{1+\log\log 2}{\log 2}$.

This left the task of understanding the $o(1)$ term in more detail. A remarkable general result of Kevin Ford, proved in 2008, gives as one of its many corollaries that the multiplication table has size $n^2/(\log n)^c(\log\log n)^{3/2}$ up to a multiplicative constant. So most people would regard the problem as fully solved, though in principle one could try to improve the bounds for the multiplicative constant, or even determine it completely, in which case the focus could turn to the additive error term …

This paper concerns a natural variant of the multiplication-table problem. In the terminology of arithmetic combinatorics, the original problem asks for the size of the product set $A.A$, where $A$ is the set $\{1,2,\dots,n\}$. The variant generalizes $A$ to an arbitrary arithmetic progression.

It is not hard to see that if $A$ is an arithmetic progression of length $n$, then the size of $A.A$ depends strongly on $A$. For instance, if $A=\{N+1,N+2,\dots,N+n\}$ for sufficiently large $N$, then it is an easy exercise to show that all the products $(N+r)(N+s)$ with $r\leq s$ are distinct. A similar example is the arithmetic progression $\{N+1,2N+1,\dots,nN+1\}$, or more generally any arithmetic progression of the form $\{a+b,a+2b,\dots,a+nb\}$ such that there are no small integer combinations of $a$ and $b$ that make zero. However, these examples are of progressions $A$ for which $A.A$ is large, so it is still interesting to look in the other direction and ask whether $A.A$ can be significantly smaller than it is when $A=\{1,2,\dots,n\}$. In 2003, Elekes and Ruzsa conjectured that the answer is no. This paper proves that conjecture, obtaining a lower bound of $n^2/(\log n)^c(\log\log n)^{O(1)}$ (for the same constant $c$) for all arithmetic progressions of length $n$.

Arithmetic progressions $A$ are characterized by the property that they have sumsets of size at most $2|A|-1$. What happens if we relax this minimal-doubling condition and ask instead merely that $A$ has small doubling – that is, that $|A+A|=O(|A|)$? This takes us into the realm of sum-product problems, in the special case where the sumset is small. It is known that the product set must be large in such a situation, but in this paper a more precise result is obtained, which proves a special case of another conjecture of Elekes and Ruzsa. By Freiman’s theorem, the small-doubling condition implies that $A$ is a dense subset of a multidimensional arithmetic progression $P$. If $P$ happens to be one-dimensional (that is, a normal arithmetic progression), then the authors show that $|A.A|\geq|A|^2/(\log|A|)^{\theta-o(1)}$ where $\theta=2\log 2-1$. This can be shown to be best possible by taking $A$ to be the set of integers between 1 and $n$ with roughly the typical number $\log\log n$ of prime factors, and using a formula of Sathe and Selberg for the number of integers between 1 and $n^2$ with at most (approximately) $2\log\log n$ prime factors.