Let be a set of real numbers. We will write and . What can we
say about the minimum size of or ? It’s easy to prove that , and
the equality holds if and only if is an arithmetic progression.
Similarly, , and the equality holds if and only if is a
geometric progression. On the one hand, both of the lower bounds
above are sharp; but on the other hand, the sets minimizing and
look quite different. In fact, if is an arithmetic progression,
then the product set is rather large, with . Conversely, if is a
geometric progression, then must be large. Erdös and Szemerédi
conjectured that at least one of and must always be large.
Specifically, it is expected that for any we must have The
reason for this post is that, just very recently, Jozsef
Solymosi proved the estimate improving the previously known
bounds, the most recent of which was also due to himself.
(Earlier results were due to Erdös, Szemerédi, Nathanson, Ford,
and Elekes.) You might or might not call Solymosi’s proof
“simple”, depending on how you define tha