I'm being troubled by this problem on AoPS: https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares In Sumsets, An Irregular Mind, Springer Berlin Heidelberg, 2010, pp. 491–524. https://doi.org/10.1007/978-3-642-14444-8_14, arXiv:0811.1311,
Dujella, A., Elsholtz, C., Sumsets being squares, Acta Math Hung 141, 353–357 (2013). https://doi.org/10.1007/s10474-013-0334-8
but these are somehow different of the above problem.
Let $n$ be a positive integer and $A$ a set of integers such that the set $\{x = a + b\ |\ a, b \in A\}$ contains $\{1^2, 2^2, \dots, n^2\}$. Prove that there is a positive integer $N$ such that if $n \ge N$, then $|A| > n^{0.666}$.
A natural question that arises from this, is if the bound could be improved to $n^{1-\epsilon}$, but I didn't find any reference on the subject, neither made any non trivial progress, any help is appreciated, the following is the last solution on the thread by the user EthanWYX2009
Let $|A|=t,$ we need to prove $t>n^{0.666}.$ If not, $t\le n^{0.666}.$ Construct a graph $G=(A,E).$ For all $k\in [n],$ pick one pair $\{a_1,a_2\}\in E$ such that $a_1+a_2=k^2,a_1,a_2\in A.$ (if the only pair is $a_1=a_2,$ we don't draw it). We have $|E|\ge n-t.$ Now we calculate the number of "angles" of $G.$ By Jensen Inequality, $$\#(\text{angles})=\sum_{a\in A}\binom {\deg a}2\geqslant t\binom{2|E|/t}2>\frac{t(2(n-t)/t-1)^2}2\sim\frac{2n^2}t\in\Omega(n^{1.334})$$ when $n$ is sufficiently large. Now we give an upper bound to get contradiction. If $x,y,z\in A$ such that $\{x,y\},\{y,z\}\in E.$ Let $x+y=u^2,z+y=v^2.$ Then $z-x=(v-u)(v+u),$ so the number of $y$ is at most $\tau (|z-x|).$ Therefore $$\#(\text{angles})\leqslant\sum_{z,x\in A}\tau (|z-x|)\le t^2\cdot Cn^{0.001}\in\mathcal O(n^{1.332})$$ by this on Wikipedia, so we get contradiction when $n$ is big enough.$\Box$
It is conjectured that it could be true to low density sequences of numbers like $\sqrt{N}$ number in $[N]$
