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.

I think things got scrambled here

“In fact, if A is an arithmetic progression, then the sumset A+A is rather large, with |A+A|\approx |A|^2. Conversely, if A is a geometric progression, then A\cdot A must be large.”

D- Thanks for the correction! It’s fixed now.

Thanks for the exposition! I wonder whether at some point Jozsef (or somebody else) will come up with an equally simple and lucid argument for ?

As far as typos are concerned – there is a minor one in the very first line (forgotten

latex).Amazing! thanks..

Pingback: Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more

I’m sure I’m being stupid, but I don’t see what you mean by reducing to the case where every element of A/A occurs the same number of times. Surely 1 will occur n times and max A/min A will occur once, whatever the set A is, so you can’t get every element to occur even approximately the same number of times. Or do you mean that you keep A fixed but pass to a subset of A/A, losing at most a log factor, where each element occurs approximately the same number of times, and then argue somehow that “approximately” can be converted into “exactly”?

Thanks for the post, by the way!

Thinking about it further, I’m pretty sure that my guess about what you meant is indeed what you meant.

Tim – You are right, it is indeed impossible for every element of to occur the same number of times, therefore one passes to a subset of (and the corresponding subset of pairs in ) where each occurs roughly the same number of times. Sorry about the imprecise wording.