## 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 rigorous 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.

### 8 responses

25 06 2008

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

25 06 2008

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

26 06 2008

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

1 07 2008

Amazing! thanks..

17 07 2008

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

29 07 2008

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!

29 07 2008

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

29 07 2008

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.