Math-Problem-Solving wrote:

Let $A = \{1, 4, \ldots, n^2\}$ be the set of the first $n$ perfect squares of nonzero integers. Suppose that $A \subset B + B$ for some $B \subset \mathbb{Z}$ . Here $B + B$ stands for the set $\{b_1 + b_2 : b_1, b_2 \in B\}$ . Prove that $|B| \geq |A|^{2/3 - \epsilon}$ holds for every $\epsilon > 0$ .

Consider a graph with $B$ as the set of vertices and exactly one edge (potentially a loop) connecting two elements with sum $k^2$ for $1\leq k\leq n$ . For every path of length $2$ the difference of the two ends is the difference of the squares corresponding to the edges. We will count the number of paths of length $2$ in two different ways.

First, for a number $m$ there are at most as many ways to write $m$ as a difference of squares as there are divisors of $m$ since $m=a^2-b^2$ is equivalent to $m=(a+b)(a-b)$ . But for $\tilde{\varepsilon}=3\varepsilon>0$ , there are $O\left(n^{\tilde{\varepsilon}}\right)$ divisors for every positive integer $n$ . So there are $O\left(|B|^2n^{3\varepsilon}\right)$ paths of length $2$ in the graph.

Second, there are $\sum_{v\in B}\frac{d_v(d_v-1)}{2}\geq|B|\cdot\frac{\frac{\sum_{v\in B}d_v}{|B|}\left(\frac{\sum_{v\in B}d_v}{|B|}-1\right)}{2}=|B|\cdot\frac{\frac{2n}{|B|}\left(\frac{2n}{|B|}-1\right)}{2}=\Omega\left(\frac{n^2}{|B|}\right)$ paths of length $2$ in the graph where $d_v$ is the degree of $v$ . (Here we use Jensen's on the convex function $\frac{x(x-1)}{2}$ .)

So the number of length $2$ paths is in both $O\left(|B|^2n^{3\varepsilon}\right)$ and $\Omega\left(\frac{n^2}{|B|}\right)$ . So $|B|$ must be in $\Omega\left(n^{\frac{2}{3}-\varepsilon}\right)$ for every $\varepsilon>0$ .