A bound for the number of integer solutions to a simple inequality 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.
 A: $|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$.
