How to calculate Gauss sum?

Question

Consider sum: $\displaystyle G_{N}(N) = \sum_{j = 0}^{N-1}e^{2\pi i\frac{j^2}{N}}$.

As we know :

$\displaystyle G_{N}(N) = \begin{equation*} \begin{cases} (1+i)\sqrt{N},&\text{if N = 4k} \\ \sqrt{N}, &\text{if N = 4k + 1} \\ 0, &\text{if N = 4k + 2} \\ i\sqrt{N}, &\text{if N = 4k + 3} \end{cases} \end{equation*}$

My attempt:

$\displaystyle\sum_{a < x\le b}f(x) = \int_{a}^{b}f(x)dx + p(b)f(b) - p(a)f(a) -\int_{a}^{b}p(x)f'(x)dx$, where $p(x) = \frac{1}{2} - \{x\}$. It's easy to show this equation. So we could represent our sum as :

$\displaystyle \int_{0}^{N-1}{e^{2\pi i\frac{x^2}{N}}dx} - \int_{0}^{N-1}(\frac{1}{2}+[x] -x)e^{2\pi i\frac{x^2}{N}}\frac{4\pi i x}{N} = \frac{\sqrt{N}erfi(\sqrt{\frac{2\pi i}{N}})}{2\sqrt{2i}} + ...$

How can I calcualte second sum. And what about erfi?

Edit:

I added the tah GAP since GAP users might be interested in this.

Answer 1

It took a while before I found this out but here it is. I only give an answer for odd primes $p$, but I think that is already complicated enough. I use the GAP system as my proof is more an algorithm. I suppose that the steps can be repeated in other mathematical software since they are relatively elementary. I will work with the examples $p = 11,13$ but will always add theoretical back-ground information.

• Step 1: assemble the basic information:

  p := 11;; F := CF(p);; z := E(p);; G := GaloisGroup(F);; H := Group(G.1^2);;
  ru := Orbit(G, z);; O := Orbits(H, ru);; S := O[1];; T := O[2];;
  s := Sum(S);; t := Sum(T);; 
  

Here we establish the basic information: the prime $p = N$, the cyclotomic field $\Bbb F$, its Galois group $G$ and its subgroup $H$ of index $2$. $H$ has two orbits in the set of p-th roots of unity, one, $S$, consisting with $\zeta = e^{\frac{2\pi i}{p}}$ with coefficients in the quadratic residues of $\Bbb Z_p^*$ and sum $s$ and an orbit $T$ with coefficients of $\zeta$ in the quadradic non-residues. Note that the original Gauss sum $G_p(p) = 1 - 2s$. The factor $2$ due to the fact that each term $\zeta^{j^2}$ occurs a second time as $\zeta^{(n-j)^2}$. If we expand the term $1$ then we have that $G_p(p) = s - t$. Note that $s$ and $t$ are conjugates so that $(s-t)^2$ is invariant under $G$ so is real. It corresponds to the number $\pm p$ we are looking for:

(s-t)^2;
 13

• Step 2: Proof, part 1, the orbits:

Let $\mathcal O_s$ be the orbit of $\zeta$ of the group $H$ and $\mathcal O_t$ the conjugate orbit under $G$. Let $C$ be the cartesian product $\mathcal O_s \times \mathcal O_t$. It has $(\frac{p-1}{2})^2$ elements. The stabilizer of any tuple under $H$ is the trivial group so there are $\frac{p-1}{2}$ $ H$-orbits each of $\frac{p-1}{2}$ elements. We have two cases to consider $p = 4k +1$ and $p = 4k + 3$. In the first case there are two types of $H$-orbits. Those who give (after multiplication of the tuples) all elements of $\mathcal O_s$ or those who give elements of $\mathcal O_t$, this is due to the action of $H$. Moreover all the elements of an orbit are different due to the action of $H$. If we make the product of each tuple in each $H$-orbit half of the $H$-orbits become $\mathcal O_s$ and the other half become $\mathcal O_t$. In the case $p = 4k+3$ we have three types of orbit: apart from the two types of the former case we have one additional orbit containing the tuple (\zeta, \zeta^{p-1}) which does not occur in the former case. After multiplying tuples of this orbit this gives a set of $\frac{p-1}{2}=2k+1$ ones.

• Step 3: evaluating and summing the orbits:

Since $s+p=-1$ we have that $s$ and $t$ are roots of the polynomial $f = X^2 +x +sl $ so that $s-l = \operatorname{discr(f)}$

Case $p = 4k+1$. After multiplying tuples we have $k$ sets equal to $\mathcal O_s$ and as many sets equal to $\mathcal O_t$, summing up their elements then gives $sl = -k$ so the discriminant becomes $1-4(-k)=p$.

Case $p = 4k+3$ After multiplying tuples we have $1$ set that sums up to $2k+1$, and, as in previous case $2k$ sets that sum up to $-k$. Now we have $sl = 2k + 1 - k = k+1$ and so the discriminant $= 1 -4(k+1) = -p$.

• Verification:

  #case p = 13
  gap> car := Cartesian(O);;
  gap> Orbits(H, car, OnTuples);
      [ [ [ E(13), E(13)^11 ], [ E(13)^4, E(13)^5 ], [ E(13)^3, E(13)^7 ],
        [ E(13)^12, E(13)^2 ], [ E(13)^9, E(13)^8 ],
        [ E(13)^10, E(13)^6 ] ],
  [ [ E(13)^12, E(13)^11 ], [ E(13)^9, E(13)^5 ],
        [ E(13)^10, E(13)^7 ], [ E(13), E(13)^2 ], [ E(13)^4, E(13)^8 ],
        [ E(13)^3, E(13)^6 ] ],
  [ [ E(13)^12, E(13)^8 ], [ E(13)^9, E(13)^6 ],
        [ E(13)^10, E(13)^11 ], [ E(13), E(13)^5 ], [ E(13)^4, E(13)^7 ],
        [ E(13)^3, E(13)^2 ] ],
  [ [ E(13)^12, E(13)^7 ], [ E(13)^9, E(13)^2 ], [ E(13)^10, E(13)^8 ],
        [ E(13), E(13)^6 ], [ E(13)^4, E(13)^11 ], [ E(13)^3, E(13)^5 ] ],
  [ [ E(13)^12, E(13)^6 ], [ E(13)^9, E(13)^11 ],
        [ E(13)^10, E(13)^5 ], [ E(13), E(13)^7 ], [ E(13)^4, E(13)^2 ],
        [ E(13)^3, E(13)^8 ] ],
    [ [ E(13)^12, E(13)^5 ], [ E(13)^9, E(13)^7 ], [ E(13)^10, E(13)^2 ],
                [ E(13), E(13)^8 ], [ E(13)^4, E(13)^6 ], [E(13)^3,E(13)^11 ]
   ] ]
  
  gap> List(last, o->Set(List(o, Product)));
  [ [ E(13)^12, E(13)^10, E(13)^9, E(13)^4, E(13)^3, E(13) ],
  [ E(13)^12, E(13)^10, E(13)^9, E(13)^4, E(13)^3, E(13) ],
  [ E(13)^11, E(13)^8, E(13)^7, E(13)^6, E(13)^5, E(13)^2 ],
  [ E(13)^11, E(13)^8, E(13)^7, E(13)^6, E(13)^5, E(13)^2 ],
  [ E(13)^11, E(13)^8, E(13)^7, E(13)^6, E(13)^5, E(13)^2 ],
  [ E(13)^12, E(13)^10, E(13)^9, E(13)^4, E(13)^3, E(13) ] ]
  gap> Sum(List(last, Sum));
  -3
  gap> s*t;
  -3
  

And for case $p = 11$:

gap> car := Cartesian(O);;
gap> Orbits(H, car, OnTuples);
[ [ [ E(11), E(11)^10 ], [ E(11)^4, E(11)^7 ], [ E(11)^5, E(11)^6 ],
      [ E(11)^9, E(11)^2 ], [ E(11)^3, E(11)^8 ] ],
  [ [ E(11)^9, E(11)^10 ], [ E(11)^3, E(11)^7 ], [ E(11), E(11)^6 ],
      [ E(11)^4, E(11)^2 ], [ E(11)^5, E(11)^8 ] ],
  [ [ E(11)^9, E(11)^8 ], [ E(11)^3, E(11)^10 ], [ E(11), E(11)^7 ],
      [ E(11)^4, E(11)^6 ], [ E(11)^5, E(11)^2 ] ],
  [ [ E(11)^9, E(11)^7 ], [ E(11)^3, E(11)^6 ], [ E(11), E(11)^2 ],
      [ E(11)^4, E(11)^8 ], [ E(11)^5, E(11)^10 ] ],
  [ [ E(11)^9, E(11)^6 ], [ E(11)^3, E(11)^2 ], [ E(11), E(11)^8 ],
      [ E(11)^4, E(11)^10 ], [ E(11)^5, E(11)^7 ] ] ]
gap> List(last, o->List(o, Product));
[ [ 1, 1, 1, 1, 1 ], 
[ E(11)^8, E(11)^10, E(11)^7, E(11)^6, E(11)^2 ],
[ E(11)^6, E(11)^2, E(11)^8, E(11)^10, E(11)^7 ],
[ E(11)^5, E(11)^9, E(11)^3, E(11), E(11)^4 ],
[ E(11)^4, E(11)^5, E(11)^9, E(11)^3, E(11) ] ]
 gap> Sum(List(last, Sum));
 3
 gap> s*t;
 3