The sum-product problem

24 06 2008

Let A be a set of real numbers. We will write A+A=\{a+a':\ a,a'\in A\} and A\cdot A=\{aa':\ a,a'\in A\}. What can we say about the minimum size of A+A or A\cdot A?

It’s easy to prove that |A+A|\geq 2|A|-1, and the equality holds if and only if A is an arithmetic progression. Similarly, |A\cdot A|\geq 2|A|-1, and the equality holds if and only if A is a geometric progression. On the one hand, both of the lower bounds above are sharp; but on the other hand, the sets minimizing |A+A| and |A\cdot A| look quite different. In fact, if A is an arithmetic progression, then the product set A\cdot A is rather large, with |A\cdot A|\approx |A|^2. Conversely, if A is a geometric progression, then A+ A must be large.

Erdös and Szemerédi conjectured that at least one of A+A and A\cdot A must always be large. Specifically, it is expected that for any \epsilon>0 we must have

\max(|A+A|, |A\cdot A|)\geq c_\epsilon |A|^{2-\epsilon}.

The reason for this post is that, just very recently, Jozsef Solymosi proved the estimate

\max(|A+A|, |A\cdot A|)\geq \frac{1}{2}|A|^{4/3}(\log|A|)^{-1/3},

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 |A|=n, |A+A|=M, |A\cdot A|=N. Assume also that A\subset (0,\infty), and that the set A/A=\{a/a':\ a,a'\in A\} also has cardinality N. This assumption is, just like Jozsef says, “unjustified and usually false”; however, if we accept the notion that A\cdot A is small if and only if A has “multiplicative structure” (e.g. a geometric progression), it shouldn’t come as a surprise that the sizes of A\cdot A and A/A 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 A/A occurs the same number of times: for every b\in A/A, there are exactly n^2/N pairs a,a'\in A such that a/a'=b. 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 A/A=\{b_1,\dots,b_N\}, where the b_i are arranged in increasing order. For each b_i\in A/A, consider the line L_i:\ y=b_ix in {\bf R}^2. By the above assumption, each such line contains n^2/N points of A\times A. For every two consecutive lines L_i,L_{i+1}, the points (a_1,a_2)+(a_3,a_4):\ (a_1,a_2)\in L_i,\ (a_3,a_4)\in L_{i+1} are all distinct, and there are (n^2/N)^2=n^4/N^2 of them. Moreover, all these points lie in the segment of {\bf R}^2_+ enclosed by the two lines; hence different pairs of consecutive lines generate disjoint sets of points. That’s at least (N-1)n^4/N^2\approx n^4/N points total.

On the other hand, all these points lie in the set (A+A)\times (A+A), the cardinality of which is exactly M^2. It follows that n^4/N\leq M^2, hence M^2N\geq n^4 and at least one of M,N must be greater than or equal to n^{4/3}, as claimed.

Wasn’t that nice?

In addition to a rigorour version of the above argument, Jozsef also has a variant covering the case of \min(|A+B|,|A\cdot B|), where A,B 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.

« Publish or perish, the literary edition Because it’s summer, at last… »


Actions

Information

8 responses

25 06 2008
D (21:21:00) :

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.”

Reply
25 06 2008
Izabella Laba (21:31:19) :

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

Reply
26 06 2008
Anonymous (17:17:18) :

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 \max\{|A+A|,|A\cdot A|\}>|A|^{3/2-\varepsilon}?

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

Reply
1 07 2008
Gil Kalai (07:28:49) :

Amazing! thanks..

Reply
17 07 2008
Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more (11:29:45) :

[...] at least . The exponent 5/4 was improved twice(!!) by Jozsef Solymosi and there is a very nice post about his most recent ingenious proof for a lower bound max (|A+A|, |A A|)  in Izabella [...]

Reply
29 07 2008
gowers (08:43:42) :

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!

Reply
29 07 2008
gowers (08:45:48) :

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

Reply
29 07 2008
Izabella Laba (09:53:52) :

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

Reply

Leave a comment