A bound for the number of integer solutions to a simple inequality

Question

I am interested in proving an upper bound (expressed as a power of $N$, with $N\rightarrow\infty$ ) for the number of elements of the set $$ A_N=\{(k,l,m,n)\in([N,2N]\cap\mathbb{Z})^4: |k^2+l^2-m^2-n^2|\le|k+l-m-n|\}. $$ My intuition is that the inequality defining this set cannot hold too often unless the quadruple exhibits some form of diagonal behavior, which would suggest a bound of the form $N^{2+\epsilon}$, with arbitrarily small $\epsilon>0$. I can't quite formalize this idea, though.

Answer 1

$|A_N|$ has order of magnitude $N^3$: We use the change of variables $x=k-m$, $y=k+m$, $u=n-l$, $v=n+l$, so that the inequality becomes $|xy-uv|\le |x-u|$. If $x=0$ or $u=0$, there are clearly $\ll N^3$ solutions. Given $x\ge u \ge 1$ and $y$, and assuming $xy\ge uv$, the variable $v$ must satisfy $$ v \in [2N+u,4N-u] \cap \left[ \frac{xy}{u}-\frac{x-u}{u}, \frac{xy}{u}\right]. $$ The other cases are similar. For this intersection to be non-empty, we must have $x/u \asymp 1$, since $y \asymp N$. This implies that the width of the second interval is $O(1)$. Thus there are $O(1)$ choices for $v$, which means that the number of solutions is $O(N^3)$.

To show that there are actually $\gg N^3$ solutions, choose $$ x \in [0.5 N, 0.55 N], \ y\in [2.6N, 2.8N], \ y\equiv x \bmod 2, \ u\in [0.45N,0.5N], \ u\equiv 0 \bmod 2. $$ Then the second interval for $v$ is contained in the first. We need to count the number of $v$ in the second interval such that $v\equiv u \bmod 2$. The number of such $v$ is $$ \ge \left\lfloor \frac{xy}{2u} \right\rfloor - \left\lfloor \frac{xy}{2u}-\frac{x-u}{2u} \right\rfloor = \frac{x-u}{2u} -\psi\left( \frac{xy}{2u} \right) + \psi\left( \frac{xy}{2u} -\frac{x-u}{2u}\right) , $$ where $\psi(t)=t-\lfloor t \rfloor -1/2$. Summing the $\psi$'s over $u$ results in $o(N)$, so their total contribution (after also summing over $x$ and $y$) is $o(N^3)$. Summing the term $(x-u)/(2u)$ over $u,x,y$ contributes $\asymp N^3$.