Let $G$ be a graph with vertices as elements of $A$, and for every integer $1\le k \le n$, choose two vertices $a$ and $b$ where $a+b=k^2$. If $a,b$ are distinct, draw an edge between them. Assuming the contrary, we have $|V|\le n^{0.666}$, and $|E|\ge n-|V| \ge n^{0.9995}$ for sufficiently large $n$. Call $(a,b,c)$ an edge pair if $a-b$ and $b-c$ are edges. By Jensen’s inequality, there are at least $|V|{\frac{2|E|}{V}\choose 2}\ge n^{1.3325}$ edge pairs. Looking at the ${|V|\choose 2}\le n^{1.332}$ possible pairs of vertices $(a,c)$, by pigeonhole, there is one pair where there are $m\ge n^{0.0005}$ vertices $b_1,b_2,\cdots b_m$ where all $(a,b_i,c)$ are edge pairs. Each of these edge pairs represents a distinct solution to $(x-y)(x+y)=x^2-y^2=c-a$, where $|c-a|<n^2$. It is known that for any $\epsilon>0$, there exists integer $N_\epsilon$ where the number of distinct factors of $k<N_\epsilon$ is less than $N_\epsilon^\epsilon$. So by taking $\epsilon=0.0002$ and sufficiently large $n>N_\epsilon$, the number of distinct solutions to the equation is less than $n^{2\cdot 0.0002}<n^{0.0005}$, a contradiction.

mzy wrote: Let $G$ be a graph with vertices as elements of $A$, and for every integer $1\le k \le n$, choose two vertices $a$ and $b$ where $a+b=k^2$. If $a,b$ are distinct, draw an edge between them. Assuming the contrary, we have $|V|\le n^{0.666}$, and $|E|\ge n-|V| \ge n^{0.9995}$ for sufficiently large $n$. Call $(a,b,c)$ an edge pair if $a-b$ and $b-c$ are edges. By Jensen’s inequality, there are at least $|V|{\frac{2|E|}{V}\choose 2}\ge n^{1.3325}$ edge pairs. Looking at the ${|V|\choose 2}\le n^{1.332}$ possible pairs of vertices $(a,c)$, by pigeonhole, there is one pair where there are $m\ge n^{0.0005}$ vertices $b_1,b_2,\cdots b_m$ where all $(a,b_i,c)$ are edge pairs. Each of these edge pairs represents a distinct solution to $(x-y)(x+y)=x^2-y^2=c-a$, where $|c-a|<n^2$. It is known that for any $\epsilon>0$, there exists integer $N_\epsilon$ where the number of distinct factors of $k<N_\epsilon$ is less than $N_\epsilon^\epsilon$. So by taking $\epsilon=0.0002$ and sufficiently large $n>N_\epsilon$, the number of distinct solutions to the equation is less than $n^{2\cdot 0.0002}<n^{0.0005}$, a contradiction. Can someone explain in a more detailed way the part of: It is known that for any $\epsilon>0$, there exists integer $N_\epsilon$ where the number of distinct factors of $k<N_\epsilon$ is less than $N_\epsilon^\epsilon$. So by taking $\epsilon=0.0002$ and sufficiently large $n>N_\epsilon$, the number of distinct solutions to the equation is less than $n^{2\cdot 0.0002}<n^{0.0005}$

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, so we get contradiction when $n$ is big enough.$\Box$