# Sum of powers of roots of unity

Let $\omega = e^{\frac{2\pi i}{d}}$, where $d$ is prime. Also let $0 < a < d$ and $0 < b < d$ (note that $a$ and $b$ are non-zero). Is there a nice formula for:

$S = \sum\limits_{j=0}^{d-1} \omega^{aj + bj(j-1)/2}$

Ideally, I'd like to find $\phi$ such that $S = r e^{i \phi}$. I already know that $r = \sqrt{d}$, but I don't know how to express $\phi$ as a function of $a$, $b$ and $d$.

## 1 Answer

Assume that $d > 2$, otherwise answer is obvious.

Let's deal with exponent (from this moment, all divisions are modulo $d$): $$aj + b\frac{j(j-1)}2 = \frac b2 \left(j^2 + \left(\frac{2a}b-1\right)j\right) = \frac b2 \left(j + \frac ab - \frac 12\right)^2 - \frac{(2a-b)^2}{8b}$$ When $j$ runs complete residue system, so does $j + \frac ab - \frac 12$. Then $$S = \omega^{-(2a-b)^2 /(8b)}\sum_{j=0}^{d-1} \omega^{b/2 \cdot j^2},$$ and sum rewrites as $$\sum_{h=0}^{d-1} \left( 1 + \left(\frac hd \right)\right)\omega^{b/2 \cdot h} = \sum_{h=0}^{d-1} \omega^{b/2 \cdot h} + \sum_{h=0}^{d-1} \left(\frac hd \right)\omega^{b/2 \cdot h},$$ where $\left( \frac \cdot d \right)$ denotes Legendre symbol. Left sum vanishes and right is the well-known Gauss sum, which equals to $\left(\frac {b/2}d\right)\sqrt d$ when $d \equiv 1 \pmod 4$ or $\left(\frac {b/2}d\right)i\sqrt d$ when $d \equiv 3 \pmod 4$.

• Thanks, this is certainly helpful! I think there might be a mistake, though. Suppose d=5, so that we're in the first case (d congruent to 1 mod 4), then according to your result, the summation should be fully real. Yet for a=1, b=1, the sum does have an imaginary component as well: http://www.wolframalpha.com/input/?i=sum+e%5E(2*pi*i*(j%2Bj*(j-1)%2F2)%2F5),+j+from+0+to+4 – qpip1982 Oct 29 '17 at 20:34
• $S$ does not equal to just Gauss sum, there is a multiplier $\omega^{-(2a-b)^2/8b}$, and it has imaginary part when $a=b=1$ – G. Strukov Oct 29 '17 at 20:41
• Ah ok, makes sense :D ... I thought that the 3rd equation was rewriting the whole sum together with that multiplier (which kind of confused me). My mistake. Many thanks! – qpip1982 Oct 29 '17 at 20:48