Let $A$ a set with $|A|=n$ that contains only perfect squares of integers. What lower bounds can we give for $|A+A|$?

I think the lower bound $\gg \frac{n^2}{\sqrt{log \,n}}$ holds (this would be the best bound possible, with "equality" for $A=\{1^2,2^2,...n^2\}$). However, this estimate seems really hard.

I couldn't even prove the bound $|A+A|>Cn$ for all constant $C$ (for big $n$). I think proving this bound would already be a good start. Any idea or technique related to the problem is appreciated.

Thanks in advance.


This is a well-known (and difficult) problem.

The current record is $|A+A| \geq \log(|A|)^{c\log\log(|A|)}|A|$ due to Schoen (in 2011), using his near optimal form of Freiman's theorem. Note this is just shy of a power gain.

See Chang's paper On problems of Erdos and Rudin for more discussion of this and related questions.

  • $\begingroup$ I was thinking about posting that link. This is really well known. Right now the problem keeps getting a new answer. :( $\endgroup$ – pie314271 Nov 28 '13 at 2:19
  • 6
    $\begingroup$ @user43400, I made your answer a comment (which it properly is), even though it wasn't very constructive. If you have something enlightening to add as a proper answer, please be our guest. You can comment yourself on other answers once you have 50 points of reputation. $\endgroup$ – Todd Trimble Nov 28 '13 at 2:25

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.