# Trick for the sum-product problem

Yesterday I read the Quanta article How a Strange Grid Reveals Hidden Connections Between Simple Numbers about the sum-product problem:

Let $$A$$ be a set of integers. Erdös and Szemerédi conjectured that for any $$\epsilon>0$$, there exists a $$c_{\epsilon}>0$$ such that

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

The Quanta article talks about recent progress in proving this conjecture. While I was reading the article, I was inspired to try to use the identity

$$xy=((x+y)^2-x^2-y^2)/2$$

to try to prove this conjecture, since I see squaring and adding numbers as more primitive operations than multiplying two numbers. Using this identity and the fact that $$|(A+A)^2|=|A+A|$$, I found that:

$$|A \cdot A|+|A+A| = |A \cdot A|+|(A+A)^2|=|\{x^2+y^2-(x+y)^2:x,y \in A\}|+|\{(x+y)^2:x,y \in A\}| \geq |\{x^2+y^2:x,y \in A\}| = |A^2+A^2|$$.

So to prove the conjecture, it suffices to prove that for any $$\epsilon>0$$, there exists a $$c_{\epsilon}>0$$ such that

$$|A^2+A^2|=|\{x^2+y^2: x,y \in A\}|\geq c_{\epsilon}|A|^{2-\epsilon}$$.

A lot is known about the sum of two squares. Not every number can be expressed as the sum of two squares, but many can. My question is is there a known number $$n \leq 2$$ such that for any $$\epsilon>0$$, there exists a $$c_{\epsilon}>0$$ such that

$$|A^2+A^2|\geq c_{\epsilon}|A|^{n-\epsilon}$$?

Has this strategy been tried before?

• Clearly $n=1$ works because LHS is at least |A|. Clearly, no larger $n$ works because $A$ could be $\{\sqrt{1},\sqrt{2},\dotsc,\sqrt{n}\}$. – Boris Bukh Mar 22 '19 at 18:14
• @Seva, if you tell me how it's wrong, I will withdraw the question. – Craig Feinstein Mar 22 '19 at 18:43
• @CraigFeinstein So you are interested in behavior of $B+B$ for $B$ being a set of squares. That is, as far as I know, open. This is related to the question of whether squares is a $\Lambda(4)$-set. – Boris Bukh Mar 22 '19 at 18:58
• Well, unless I am mistaken, here is a counterexample. Take $A=\{0,1,2\}$, $f(x,y)=x$, and $g(x,y)=100y$. Then $|\{f(x,y)\}|=|\{g(x,y)\}|=3$, while $|\{f(x,y)+g(x,y)\}|=9$. – Seva Mar 22 '19 at 19:39
• @Seva it looks like you are correct. Thank you. – Craig Feinstein Mar 22 '19 at 19:46

Your question is a well-known and difficult open problem. See Lower bounds for $|A+A|$ if $A$ contains only perfect squares. To repeat my answer from that question, the best lower bound to date is: $$|A^2+A^2| \geq |A| (\log |A| )^{c \log \log |A|}$$ due to Schoen in 2011 using his bounds on Freiman's theorem.
• Sanders has improved the lower bound (via improving the bounds for Freiman's theorem) to $\lvert A\rvert \exp((\log \lvert A\rvert)^{c})$ for some constant $c>0$, see Theorem 11.7 of arxiv.org/pdf/1011.0107.pdf – Thomas Bloom Apr 1 '19 at 7:05