4
$\begingroup$

Can we evaluate the exact form of $g\left(k,n\right)=\sum_{r=0}^{n-1}\exp\left(2\pi i\frac{r^{2}k}{n}\right) $ for general $k$ and $n$? For $k=1$, on MathWorld we have that $g\left(1,n\right)=\left\{ \begin{array}{cc} (1+i)\sqrt{n} & \ \text{when}\ n\equiv0\ \text{mod}\ 4\\ \sqrt{n} & \text{when}\ n\equiv1\ \text{mod}\ 4\\ 0 & \text{when}\ n\equiv2\ \text{mod}\ 4\\ i\sqrt{n} & \text{when}\ n\equiv3\ \text{mod}\ 4 \end{array}\right\} .$

I know how to generalize to all $k$ when $n=p$ is a prime number, but what do we do when $n$ is not prime? Is there a simple way to rewrite it using whether or not $k$ is a square? I have a suspicion it should be fairly close to the form above, any help is appreciated.

Thanks,

1 Answers 1

5

They do not provide a derivation, but this is actually written up in Wikipedia.

I use the standard notation $e(x) = \exp(2 \pi i x)$. Assuming $\gcd(k,n) = 1$, we have $ \sum_{x \in \mathbb{Z}/n \mathbb{Z}} e\left(\frac{kx^2}{n} \right) = \left\{ \begin{array}{lcl} \varepsilon_n \left( \frac{k}{n} \right) \sqrt{n} & & n \equiv 1 \pmod{2}\\ 0 & & n \equiv 2\pmod{4}\\ (1 + i) \varepsilon_k^{-1} \left(\frac{n}{k} \right)\sqrt{n} & & k \equiv 1 \pmod{2}, 4 \mid n \end{array}\right. $ where $\left( \cdot \right)$ and for odd $m$, $ \varepsilon_m = \left\{ \begin{array}{cc} 1 & & m \equiv 1 \pmod{4}\\ i & & m \equiv 3 \pmod{4} \end{array}\right. $ When $\gcd(k,n) > 1$, write k' = k/\gcd(k,n) and n' = n/\gcd(k,n), to see that \sum_{x \in \mathbb{Z}/n \mathbb{Z}} e\left(\frac{kx^2}{n} \right)= \gcd(k,n) \sum_{x \in \mathbb{Z}/ n' \mathbb{Z}} e\left(\frac{k' x^2}{n'} \right) since the variable $x$ runs through $\gcd(k,n)$ copies of the above sum.


Added: I looked through Iwaniec-Kowalski and they have a few notes on the sums, but nothing short worth noting here. These sums are discuss in Chapter 3 (around page 49) of their book. Anyways, I hope this answer is what you were looking for.