$ S^2= \left(\sum_{j=0}^{p-1} \epsilon^{j^2}\right)^2$ where $p$ are prime number, $\epsilon $ is primitive p-th root of unity.

Question

Let $p$ are prime number, $\epsilon $ is primitive p-th root of unity. Calculate: $$ S^2= \left(\sum_{j=0}^{p-1} \epsilon^{j^2}\right)^2$$

$p=3;p=5$ the result are real number.

$\epsilon^{j^2}=\epsilon^{(p-j)^2}$

Answer 1

Turns out there is, in fact, a much better (and most importantly closed) expression for $S^2$, namely: $$S^2 = \begin{cases} 0 & p = 2 \\ p & p \equiv 1 \pmod{4} \\ -p & p \equiv 3 \pmod{4} \end{cases}$$ Having computed the value of $S^2$ for $p = 3, \: 5$, you can easily check that, at least in those cases, the above claim is true.

Now let's get to the proof. The case $p = 2$ is to be done manually (simple verification). Hence suppose that $p$ is odd. If we expand the initial formula for $S^2$ (i.e. we expand the square), what we get eventually is something of the form $$\sum_{k = 0}^{p - 1} f(k)\epsilon^k \tag{$\star$}$$ Here, $f(k)$ is the number of ordered pairs $(a, \: b) \in \{0, \: 1, \: \dots, \: p - 1\}$ such that $a^2 + b^2 \equiv k \pmod{p}$.

So the question is: can we find $f(k)$ explicitly? Yes, but it's not obvious. Indeed, we shall take advantage of the following

Lemma. Let $p$ be a prime number and $Q \in \mathbb{Z}[x]$ be a polynomial of degree $p - 1$ whose leading coefficient is $a$. Then $$\sum_{i = 0}^{p - 1} Q(i) \equiv -a \pmod{p}$$ Proof involves generators modulo $p$ and is actually not that difficult, yet I'm not going to write it here not to diverge from the scope of the answer (still, I could add it later if someone requests).

Ok, now the fun starts... Fix $1 \le k \le p - 1$, and let:

• $A$ be the set of all $x$ ($0 \le x \le p - 1$) such that $k - x^2$ is a nonzero quadratic residue modulo $p$;
• $B$ be the set of all $x$ such that $k - x^2$ is not a quadratic residue modulo $p$;
• $C$ be the set of all $x$ such that $k - x^2 \equiv 0 \pmod{p}$.

Why is this distinction useful? Because, having fixed $a$, the equation $a^2 + b^2 \equiv 0 \pmod{p}$ can be rewritten as $b^2 \equiv k - a^2 \pmod{p}$, which has two solutions (namely $b = \pm\sqrt{k - a^2}$) if $a \in A$, no solution if $a \in B$ and just one ($b = 0$) if $a \in C$. So we're particularly interested in the values of $|A|$ and $|C|$

First, note that $|C|$ is either $0$ (if $k$ in not a QR) or $2$ (if $k$ is a QR, since then $x = \pm\sqrt{k}$ are solutions): in any case, it's even, and since $|A| + |B| + |C| = p$ is odd, $|A| + |B|$ must be odd, which means that $|A| - |B|$ is odd too.

Recall Euler's criterion: for every $x$, we have $$x^{(p - 1)/2} \equiv \begin{cases} 0 & x \equiv 0 \pmod{p} \\ 1 & x \: \text{is a nonzero QR} \\ -1 & x \: \text{is not a QR} \end{cases} \pmod{p}$$ Thus $\displaystyle |A| - |B| \equiv \sum_{i = 0}^{p - 1} (k - i^2)^{(p - 1)/2}$. But $(k - x^2)^{(p - 1)/2}$ turns out to be a polynomial of degree $p - 1$ with integer coefficients and leading coefficient $(-1)^{(p - 1)/2}$, so from the previous lemma we get $$|A| - |B| \equiv \sum_{i = 0}^{p - 1} (k - i^2)^{(p - 1)/2} \equiv -(-1)^{(p - 1)/2} = (-1)^{(p + 1)/2} \pmod{p}$$ Since, obviously, $|A| - |B|$ is bounded between $-p$ and $p$, it can be nothing but $(-1)^{(p + 1)/2}$ and $(-1)^{(p + 1)/2} \pm p$; but the fact that it's odd excludes the latter two possibilities, thus is must be $|A| - |B| = (-1)^{(p + 1)/2}$.

Let's now split things in two different cases (remember that we're still examining $k \ne 0$, $k = 0$ will be treated later).

1. $k$ is not a QR. As said before, in this case $|C| = 0$, and so $|A| + |B| = p$. Then $\displaystyle |A| = \frac{(|A| + |B|) + (|A| - |B|)}{2} = \frac{p + (-1)^{(p + 1)/2}}{2}$ and the number of solutions of the equation is $f(k) = 2|A| + |C| = p + (-1)^{(p + 1)/2}$.
2. $k$ is a QR. Then $|C| = 2$ and $|A| + |B| = p - 2$, so $\displaystyle |A| = \frac{p - 2 + (-1)^{(p + 1)/2}}{2}$. Hence $f(k) = 2|A| + |C| = (p - 2 + (-1)^{(p + 1)/2}) + 2 = p + (-1)^{(p + 1)/2}$.

We've come up with this amazing conclusion: for every $1 \le k \le p - 1$, $f(k) = p + (-1)^{(p + 1)/2}$.

What about $f(0)$? This is, again, the number of solutions to $a^2 + b^2 \equiv 0 \pmod{p}$. Obviously $(0, \: 0)$ is the unique solution with $a = 0$. If $a \ne 0$, we want $b^2 \equiv -a^2 \pmod{p}$. It is well known that $-1$ is QR modulo $p$ iff $p \equiv 1 \pmod{4}$: so if this is the case, then $-a^2$, being the product of two QRs, is itself a QR and the $2(p - 1)$ pairs $(a, \: \pm\sqrt{-a^2})$ are all the nonzero solutions; otherwise $-a^2$ is always a non-QR, so that there are no solutions except for the trivial one. Summing this up: $$f(0) = \begin{cases} 2p - 1 & p \equiv 1 \pmod{4} \\ 1 & p \equiv 3 \pmod{4} \end{cases}$$

Now we're ready to conclude. Having found the explicit value of $f(k)$, we can go back to $(\star)$. It is convenient to distinguish once again the cases $p \equiv \pm 1 \pmod{4}$.

• If $p \equiv 1 \pmod{4}$, $$\begin{align*} S^2 & \stackrel{(\star)}{=} \sum_{k = 0}^{p - 1} f(k)\epsilon^k = \\ & = (2p - 1) + (p - 1)(\epsilon + \epsilon^2 + \cdots + \epsilon^{p - 1}) = \\ & = p + (p - 1)(1 + \epsilon + \epsilon^2 + \cdots + \epsilon^{p - 1}) = \\ & = p \end{align*}$$
• If $p \equiv 3 \pmod{4}$, $$\begin{align*} S^2 & \stackrel{(\star)}{=} \sum_{k = 0}^{p - 1} f(k)\epsilon^k = \\ & = 1 + (p + 1)(\epsilon + \epsilon^2 + \cdots + \epsilon^{p - 1}) = \\ & = -p + (p + 1)(1 + \epsilon + \epsilon^2 + \cdots + \epsilon^{p - 1}) = \\ & = -p \end{align*}$$

Which proves the claim true.

Answer 2

Define $f(x)=\sum_{j=1}^{(p-1)/2} x^{j^2\pmod p}$.

Then your $S = 1+2f(\epsilon)$.

Also, if $a$ is a non-square modulo $p$, then:

$$1+f(\epsilon^{a})+f(\epsilon)=\sum_{j=0}^{p-1} \epsilon^j=0$$

We also have that $$f(\epsilon)-f(\epsilon^a)=\sum_{j=1}^{p-1}\left(\frac{j}p\right)\epsilon^j\tag{1}$$

If $p\equiv 3\pmod 4$, (1) is clearly imaginary since $e^j$ and $e^{p-j}$ are conjugates and $e^{j}-e^{p-j}$ is thus imaginary.

If $p\equiv 1\pmod 4$ then $e^j+e^{p-j}$ is the sum of conjugates, and hence real.

Adding, we get $S=2f(\epsilon)+1=f(\epsilon)-f(\epsilon^a)$ is either real or imaginary.

In particular, $S$ is imaginary if and only if $p\equiv 3\pmod 4$.

It is also never $0$. If $2f(x)+1$ is zero at $\epsilon$ then it is zero for $\epsilon^k$ for all $k=1,\dots,p-1$, but it is a polynomial of degree at most $p-1$ which is not divisible by $1+x+\cdots+x^{p-1}$.

---

The exact value of $S$ is:

$$S=\begin{cases}0&\quad p=2\\2\sum\limits_{j=1}^{(p-1)/2}\left(\frac{j}p\right)\cos\frac{2\pi j}{p}&\quad p\equiv 1\pmod{4}\\ 2i\sum\limits_{j=1}^{(p-1)/2}\left(\frac{j}p\right)\sin\frac{2\pi j}{p}&\quad p\equiv 3\pmod 4 \end{cases}$$