11
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was thinking about posting that link. This is really well known. Right now the problem keeps getting a new answer. :( $\endgroup$
    – user43400
    Commented Nov 28, 2013 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
    Commented Nov 28, 2013 at 2:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .