Show the upper bound of cardinality of $A$ is $C\sqrt{n\log{n}}$ $\forall l,m,n\in \Bbb{Z_+}$, let $A:=\{k: m+1\leq k\leq m+n\text{ and }l-k^2\text{ is a square number}\}$.
Please prove that the number of elements in $A$ is not more than $C\sqrt{n\log n}$, where $C$ is a positive constant that is independent of $l,m$ and $n$.
 A: This answer is an elaboration of Lucia's comment, all mistakes are mine.
Consider the primes $7\leq p\leq\sqrt{n}$ with $p\equiv 3\pmod{4}$. For each such prime $p$, the number of solutions of the congruence $k^2+m^2\equiv l\pmod{p}$ equals $p+1$ for $p\nmid l$ and $1$ for $p\mid l$, so there are at most $(p+3)/2$ residue classes $k$ mod $p$ for which a corresponding residue class $m$ mod $p$ exists with the congruence being satisfied. In other words, there are at least $(p-3)/2$ forbidden residue classes for $k$ mod $p$, which is a positive proportion (namely at least $2/7$). Now the large sieve in its simplest form gives that
$$ |A| \ll\frac{n}{\pi(\sqrt{n},4,3)}\ll\sqrt{n}\log n.$$
In fact one can show in this way that $|A|\leq (4+o(1))\sqrt{n}\log n$.
Added. Probably the $\log n$ factor can be improved to $\sqrt{\log n}$ by sieving with all the square-free moduli $q\leq\sqrt{n}$ that are composed of the primes $p\equiv 3\pmod{4}$ with $p\neq 3$ (instead of sieving with these primes only), but I have not checked the details.
