On product sets of arithmetic progressions

- Mathematics, Stanford University
- More about Max Wenqiang Xu

- Mathematics, Stanford University
- More about Yunkun Zhou

*Discrete Analysis*, July. https://doi.org/10.19086/da.84267.

### Editorial introduction

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 ? (Of course, this means how many *distinct* numbers, or the answer would obviously be .)

A simple lower bound comes from the prime number theorem and the fundamental theorem of arithmetic. Indeed, there are around primes between 1 and and all their products are distinct, which gives a lower bound of around . To obtain a non-trivial upper bound, one can use the fact that almost all integers between 1 and have approximately prime factors, with multiplicity. (This fact is easy to prove: with more sophisticated but still elementary arguments one can obtain the more accurate expression , where is an explicit constant.) It follows that almost all elements of the multiplication table have approximately prime factors, whereas almost all integers between 1 and have approximately prime factors, which shows that the multiplication table has size . 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 , Erdős showed that the multiplication table has size , where is the somewhat surprising constant .

This left the task of understanding the 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 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 , where is the set . The variant generalizes to an arbitrary arithmetic progression.

It is not hard to see that if is an arithmetic progression of length , then the size of depends strongly on . For instance, if for sufficiently large , then it is an easy exercise to show that all the products with are distinct. A similar example is the arithmetic progression , or more generally any arithmetic progression of the form such that there are no small integer combinations of and that make zero. However, these examples are of progressions for which is large, so it is still interesting to look in the other direction and ask whether can be significantly *smaller* than it is when . In 2003, Elekes and Ruzsa conjectured that the answer is no. This paper proves that conjecture, obtaining a lower bound of (for the same constant ) for all arithmetic progressions of length .

Arithmetic progressions are characterized by the property that they have sumsets of size at most . What happens if we relax this minimal-doubling condition and ask instead merely that has *small* doubling – that is, that ? 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 is a dense subset of a multidimensional arithmetic progression . If happens to be one-dimensional (that is, a normal arithmetic progression), then the authors show that where . This can be shown to be best possible by taking to be the set of integers between 1 and with roughly the typical number of prime factors, and using a formula of Sathe and Selberg for the number of integers between 1 and with at most (approximately) prime factors.