Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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:

\begin{equation} \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} \end{equation}

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$): \begin{equation} \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} \end{equation}

If $n+k$ is even (so $n$ is odd, since $\gcd(n, k)=1$) \begin{equation} \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) \end{equation} where \begin{equation} \epsilon_{m}= \begin{cases} 1 & \text{if} \; m \equiv 1 \pmod 4 \\ i & \text{if} \; m \equiv 3 \pmod 4 \end{cases} \end{equation} 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.


\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}


\begin{equation} \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} \end{equation}

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

$n, k$ are both odd: \begin{equation} \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) \end{equation}

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 \begin{equation} \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) \end{equation}

If $n+k \equiv 1 \pmod 4$, we have $\epsilon_{n+k}=1$, \begin{equation} (-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) \end{equation}

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

\begin{equation} \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} \end{equation}

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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