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 that word. The argument, as it stands, is quite elementary and does not use anything more sophisticated than the Cauchy-Schwartz inequality. That doesn’t mean, though, that you or I could have easily found it. Many of the best combinatorialists around have thought about this particular problem and were not able to find an improvement.
Jozsef explains the main idea as follows. Let , , . Assume also that , and that the set also has cardinality . This assumption is, just like Jozsef says, “unjustified and usually false”; however, if we accept the notion that is small if and only if has “multiplicative structure” (e.g. a geometric progression), it shouldn’t come as a surprise that the sizes of and might not be completely unrelated. There are in fact rigorous results of this type, but they are not used in Jozsef’s paper.
We will further assume that every element of occurs the same number of times: for every , there are exactly pairs such that . This again is usually not true, but, at the cost of losing a log factor, we can reduce to this case by pigeonholing.
Now, let , where the are arranged in increasing order. For each , consider the line in . By the above assumption, each such line contains points of . For every two consecutive lines , the points are all distinct, and there are of them. Moreover, all these points lie in the segment of enclosed by the two lines; hence different pairs of consecutive lines generate disjoint sets of points. That’s at least points total.
On the other hand, all these points lie in the set , the cardinality of which is exactly . It follows that , hence and at least one of must be greater than or equal to , as claimed.
Wasn’t that nice?
In addition to a rigorous version of the above argument, Jozsef also has a variant covering the case of , where are different sets, and a result on iterated sumsets of sets whose product sets are very small. If you’re interested, you should check his paper if you have not done so already.