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


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?

  • $\begingroup$ 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}\}$. $\endgroup$ – Boris Bukh Mar 22 '19 at 18:14
  • 1
    $\begingroup$ @Seva, if you tell me how it's wrong, I will withdraw the question. $\endgroup$ – Craig Feinstein Mar 22 '19 at 18:43
  • 1
    $\begingroup$ @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. $\endgroup$ – Boris Bukh Mar 22 '19 at 18:58
  • 1
    $\begingroup$ 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$. $\endgroup$ – Seva Mar 22 '19 at 19:39
  • 1
    $\begingroup$ @Seva it looks like you are correct. Thank you. $\endgroup$ – 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.

I think one drawback to your strategy is that the problem you end up with is considerably harder than the original problem. Indeed there are non-trivial polynomial-type lower bounds on the sum-product problem via rather elementary arguments. On the other hand, there isn't any non-trivial polynomial-type lower bound known on the sum of squares problem and Schoen's theorem above relies on two deep results: Freiman's theorem and a deep theorem about squares in arithmetic progressions due to Bombieri, Granville, Pintz using arguments related to Faltings's theorem.

One explanation for this is Boris' first comment / "counterexample". To make progress on the sum of squares problem you need to exploit the fact that the numbers involved are integers, where most of the sum-product technology doesn't distinguish between real numbers and integers (which, generally, is a feature).

  • 2
    $\begingroup$ 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 $\endgroup$ – Thomas Bloom Apr 1 '19 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.