MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 16 down vote accepted

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.

share|cite|improve this answer
I was thinking about posting that link. This is really well known. Right now the problem keeps getting a new answer. :( – user43400 Nov 28 '13 at 2:19
@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. – Todd Trimble Nov 28 '13 at 2:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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