0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – qpip1982 Oct 29 '17 at 20:34
  • $\begingroup$ $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$ $\endgroup$ – G. Strukov Oct 29 '17 at 20:41
  • $\begingroup$ 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! $\endgroup$ – qpip1982 Oct 29 '17 at 20:48

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.