0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.