# A Gauss sum like summation

I would like to calculate the following sum.

Let $\zeta$ be a primitive $n$ th root of unity for some integer $n$. Here $n$ is not necessarily prime.

The sum is

$$\sum_{j=1}^n (-1)^j \zeta^{\frac{j^2}{2}}.$$

I know how to find the value of the sum if there is no term $(-1)^j$ using a Gauss sum.

More explicitely, let $\zeta=\exp (2\pi ik/n)$, where $k$ and $n$ are relatively prime integers.

I would like to know the formula for the value of the above sum depending on $k$ and $n$.

I apprciate any help.

-
What is $f{}{}$? – Henning Makholm Mar 5 '13 at 17:59
@HenningMakholm it should have $j$. I fixed it. – Snow Mar 5 '13 at 18:24
With a simple guess-work one finds: $$\sum_{j=1}^n (-1)^j \exp\left(i\frac{2\pi}{n} \frac{j^2}{2} \right) = \sqrt{n} \exp\left(i \pi \frac{1-n}{4}\right)$$ – Sasha Mar 5 '13 at 18:57
@Sasha Could you give me a proof? Also does not the equality depend on $n$ as it does for a gauss sum. – Snow Mar 5 '13 at 20:58
If we write $-1$ as $\exp(i\pi)$, doesn't this work out to be a generalized quadratic Gauss sum so that the magnitude is $\sqrt{n}$ as Sasha tells us it is, and the complex eighth root of unity is the part that requires careful calculation? – Dilip Sarwate Mar 6 '13 at 2:58

Overview: Since my post is long, here is what I will eventually prove:

$$\sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}= \begin{cases} -1 & \text{if n is odd and k is even} \\ \sqrt{n}exp\left(i \pi \frac{1-n}{4}\right)\left( \frac{k}{n}\right) & \text{if n is odd and k is odd} \\ \sqrt{n}exp\left(i \pi \frac{2-k-n}{4}\right)\left( \frac{k}{n+k}\right) & \text{if n is even (so k is odd)} \end{cases}$$

Main argument: It seems that you know how to get the following using Gauss sums:

If $n+k$ is odd (so $\gcd(n+k, 2n)=1$): $$\sum_{j=0}^{2n-1}{exp \left( \frac{2 \pi i j^2(n+k)}{2n} \right)}= \begin{cases} 0 & \text{if n is odd} \\ (1+i)\epsilon_{n+k}^{-1}\sqrt{2n} \left(\frac{2n}{n+k}\right) & \text{if n is even } \end{cases}$$

If $n+k$ is even (so $n$ is odd, since $\gcd(n, k)=1$) $$\sum_{j=1}^{n}{exp \left( \frac{2 \pi i j^2\frac{(n+k)}{2}}{n} \right)}=\sum_{j=0}^{n-1}{exp \left( \frac{2 \pi i j^2\frac{(n+k)}{2}}{n} \right)}=\epsilon_n \sqrt{n} \left( \frac{\frac{n+k}{2}}{n}\right)$$ where $$\epsilon_{m}= \begin{cases} 1 & \text{if} \; m \equiv 1 \pmod 4 \\ i & \text{if} \; m \equiv 3 \pmod 4 \end{cases}$$ for any odd integer $m$, and $\left( \frac{\frac{n+k}{2}}{n}\right)$ and $\left(\frac{2n}{n+k}\right)$ are referring to the Jacobi symbol.

Now,

\begin{align} \sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}& =\sum_{j=1}^{n}{(-1)^{j^2}exp \left( \frac{2 \pi i j^2k}{2n} \right)} \\ & =\sum_{j=1}^{n}{exp \left( \frac{2 \pi i j^2(n+k)}{2n} \right)} \\ & =\frac{1}{2}\left(exp \left( \frac{2 \pi i n^2(n+k)}{2n} \right)-1+\sum_{j=0}^{2n-1}{exp \left( \frac{2 \pi i j^2(n+k)}{2n} \right)}\right) \\ & =\frac{1}{2}\left((-1)^{n(n+k)}-1+\sum_{j=0}^{2n-1}{exp \left( \frac{2 \pi i j^2(n+k)}{2n} \right)}\right) \end{align}

Thus

$$\sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}= \begin{cases} -1 & \text{if n is odd and k is even} \\ \epsilon_n \sqrt{n} \left( \frac{\frac{n+k}{2}}{n}\right) & \text{if n is odd and k is odd} \\ (1+i)\epsilon_{n+k}^{-1}\sqrt{\frac{n}{2}} \left(\frac{2n}{n+k}\right) & \text{if n is even (so k is odd)} \end{cases}$$

This formula is already nice. I shall manipulate to give a different (simpler) expression.

$n, k$ are both odd: $$\left( \frac{\frac{n+k}{2}}{n}\right)=\left( \frac{\frac{n+k}{2}}{n}\right)\left( \frac{2}{n}\right)\left( \frac{2}{n}\right)=\left( \frac{n+k}{n}\right)\left( \frac{2}{n}\right)=\left( \frac{2}{n}\right)\left( \frac{k}{n}\right)=(-1)^{\frac{n^2-1}{8}}\left( \frac{k}{n}\right)$$

If $n \equiv 1 \pmod 4$, then $\epsilon_n=1$ and $$\epsilon_n(-1)^{\frac{n^2-1}{8}}=(-1)^{\frac{n^2-1}{8}}=(-1)^{\frac{n-1}{4}}=(-1)^{\frac{1-n}{4}}=exp\left(i \pi \frac{1-n}{4}\right)$$

If $n \equiv 3 \pmod 4$, then $\epsilon_n=i$ and $$\epsilon_n(-1)^{\frac{n^2-1}{8}}=i(-1)^{\frac{n^2-1}{8}}=i(-1)^{\frac{n+1}{4}}=i(-1)^{-\frac{n+1}{4}}=exp\left(i \pi \left(\frac{1}{2}-\frac{n+1}{4}\right)\right)=exp\left(i \pi \frac{1-n}{4}\right)$$

Thus for the case where $n, k$ both odd, we have $$\sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}=\sqrt{n}exp\left(i \pi \frac{1-n}{4}\right)\left( \frac{k}{n}\right)$$

$n$ is even, then $k$ is odd, so $$\left(\frac{2n}{n+k}\right)=\left(\frac{-2k}{n+k}\right)=\left(\frac{-1}{n+k}\right)\left(\frac{2}{n+k}\right)\left(\frac{k}{n+k}\right)=(-1)^{\frac{(n+k)-1}{2}}(-1)^{\frac{(n+k)^2-1}{8}}\left(\frac{k}{n+k}\right)$$

If $n+k \equiv 1 \pmod 4$, we have $\epsilon_{n+k}=1$, $$(-1)^{\frac{(n+k)-1}{2}}(-1)^{\frac{(n+k)^2-1}{8}}\left(\frac{k}{n+k}\right)=(-1)^{\frac{(n+k)-1}{4}}\left(\frac{k}{n+k}\right)=(-1)^{\frac{1-(n+k)}{4}}\left(\frac{k}{n+k}\right)$$

Thus \begin{align} \frac{1+i}{\sqrt{2}}\epsilon_{n+k}^{-1}\left(\frac{2n}{n+k}\right) & =exp \left( i \pi \frac{1}{4}\right)exp \left( i \pi \frac{1-(n+k)}{4}\right)\left(\frac{k}{n+k}\right) \\ & =exp \left( i \pi \frac{2-k-n}{4}\right)\left(\frac{k}{n+k}\right) \end{align}

If $n+k \equiv 3 \pmod 4$, we have $\epsilon_{n+k}=i$, \begin{align} (-1)^{\frac{(n+k)-1}{2}}(-1)^{\frac{(n+k)^2-1}{8}}\left(\frac{k}{n+k}\right)& =(-1)(-1)^{\frac{(n+k)+1}{4}}\left(\frac{k}{n+k}\right) \\ & =(-1)(-1)^{-\frac{(n+k)+1}{4}}\left(\frac{k}{n+k}\right) \\ & =(-1)^{\frac{3-k-n}{4}}\left(\frac{k}{n+k}\right) \end{align}

Thus \begin{align} \frac{1+i}{\sqrt{2}}\epsilon_{n+k}^{-1}\left(\frac{2n}{n+k}\right) & =exp \left( i \pi \frac{1}{4}\right)exp \left( -i \pi \frac{1}{2}\right)exp \left( i \pi \frac{3-k-n}{4}\right)\left(\frac{k}{n+k}\right) \\ & =exp \left( i \pi \frac{2-k-n}{4}\right)\left(\frac{k}{n+k}\right) \end{align}

Thus for the case where $n$ even, we have $$\sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}=\sqrt{n}exp\left(i \pi \frac{2-k-n}{4}\right)\left( \frac{k}{n+k}\right)$$

Finally, combining, we have

$$\sum_{j=1}^{n}{(-1)^jexp \left( \frac{2 \pi i j^2k}{2n} \right)}= \begin{cases} -1 & \text{if n is odd and k is even} \\ \sqrt{n}exp\left(i \pi \frac{1-n}{4}\right)\left( \frac{k}{n}\right) & \text{if n is odd and k is odd} \\ \sqrt{n}exp\left(i \pi \frac{2-k-n}{4}\right)\left( \frac{k}{n+k}\right) & \text{if n is even (so k is odd)} \end{cases}$$

-