Posted by: Izabella Laba | June 24, 2008

The sum-product problem

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.

Posted in research math

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

Responses

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

By: D on June 25, 2008
at 9:21 pm

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

By: Izabella Laba on June 25, 2008
at 9:31 pm

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

By: Anonymous on June 26, 2008
at 5:17 pm

Amazing! thanks..

By: Gil Kalai on July 1, 2008
at 7:28 am

[...] 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 [...]

By: Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more on July 17, 2008
at 11:29 am

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!

By: gowers on July 29, 2008
at 8:43 am

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

By: gowers on July 29, 2008
at 8:45 am

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.

By: Izabella Laba on July 29, 2008
at 9:53 am

Leave a response






Your response:

Categories