4
$\begingroup$

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?

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

1 Answer 1

5
+50
$\begingroup$

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

$\endgroup$
1
  • 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$ Apr 1, 2019 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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