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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.