Let $N$ be a large natural number. Define an expoential sum $$ I_m=\sum_{x,y=1}^N e^{2\pi i\frac{x^2-y^2}{N}m}, \,\, m=1,2,...,N-1. $$
The trivial bound for $I_m$ is $N^2$, as there are $N^2$ terms. My question is can we do better? Is it possible to have $$ |I_m|<C N^{2-\delta} $$ for some positive $\delta$ and $C$ (indepdent of $m$)? And what about the case when x^2-y^2 is replaced with P(x)-P(y) for a general nonlinear polynomial?
We set $$e_N(\theta) := e^{2 \pi I \theta/N}.$$ Your sum which is equal to $$\left|\sum_x e_N(x^2 m)\right|^2$$ and is known as a Gauss sum. Gauss himself studied these extensively. Following him, we use the substitution $x = y+h$, $$\sum_{x,y} e_N((x^2 - y^2)m) = \sum_{y,h} e_N((2hy + h^2)m) = N \sum_h e_N(mh^2) 1_{N | 2hm}$$ Now $N | 2hm$ for $h = 1, \ldots , N$ if and only if $N / \gcd(2m , N)$ divides $h$. Letting $h = k N / \gcd(2m , N)$ we get the above is $$= N \sum_{k=1}^{\gcd(N , 2m)} e_N(\left(\frac{N }{ gcd(2m, N)}\right)^2 k^2m) \leq N\gcd(N , 2m).$$ Note that the above is an inequality for $N$ odd, so we cannot expect a uniform bound without knowing further information about $\gcd(N , 2m)$. For instance if $m = 0$ there is no cancellation. Note if $N$ is prime and $m \neq 0$, then we have square root cancellation ($\delta = C = 1$ in your notation).
For general polynomials, you should look at the Weil conjectures. This handles the case when $N$ is prime, getting square root cancellation just like in the Gauss sums above.
