Let $\mathbb F = \mathrm{GF}(p^r)$ be finite field for $p$ an odd prime, and define $$ \begin{align} Q &= \bigl\{ u^2 \,\big|\, u \in \mathbb F^\times \bigr\} \\ N &= \mathbb F^\times \smallsetminus Q \end{align} $$ As $\mathbb F^\times$ is a cyclic group of even order, we have $\lvert Q \rvert = \lvert N \rvert = \tfrac{1}{2}(p^r - 1)$. A classic result of number theory for the case $r = 1$ is that $$ \# \bigl\{ q \in Q \;\big|\; q+1 \in Q \bigr\} = \begin{cases} (p-5)/4, & \text{if $p \equiv 1 \pmod{4}$}; \\[1ex] (p-3)/4, & \text{if $p \equiv 3 \pmod{4}$}. \end{cases} $$ Is there a corresponding result for $r > 1$ as well, and how is it shown?

  • $\begingroup$ This is known. Too busy to derive the result now, sorry. Basically you want to look at the number of solutions of the equation $x^2=1+y^2$ which is equivalent to $(x-y)(x+y)=1$. Then you use $x-y$ and $x+y$ as new variables. This is a bijective linear substitution in odd characteristic. You do need to observe what happens to the solutions, where one of the variables is zero. IIRC you just replace $p$ with $p^r$ everywhere. $\endgroup$ – Jyrki Lahtonen Apr 11 '15 at 4:43
  • $\begingroup$ @JyrkiLahtonen: Thanks! I found a yet simpler, turn-the-crank sort of proof once it occurred to me that the answer might possibly be a straightforward extension of the standard result (and that the standard result might not only be well-known but might also itself be proven simply). $\endgroup$ – Niel de Beaudrap Apr 11 '15 at 6:35

We can in fact adapt a standard proof of the result for $r = 1$, such as the one presented in this answer to the related question for the integers modulo $p$. Below, let $\chi: \def\F{\mathbb F}\F \to \{-1,0,+1\}$ be the quadratic character of $\F^\times$ extended to the whole field, so that $$ \chi(a) = \begin{cases} +1 & \text{for $a \in Q$}, \\ -1 & \text{for $a \in N$}, \\ 0 & \text{for $a = 0$}. \end{cases} $$ Let $C = \# \bigl\{ q \in Q \,\big|\, q+1 \in Q \bigr\}$: then we have $$ C = \sum_{a \in \F}\Bigl(\frac{1+\chi(a)}2 \Bigr)\Bigl(\frac{1+\chi(a{+}1)}{2}\Bigr) - \frac{1}{2} - \Bigl(\frac{1 +\chi(-1)}{4}\Bigr), $$ where the first subtracted term is to correct for the $a = 0$ contribution, and the second subtracted term is to correct for the $a = -1$ contribution. Since $\lvert N \rvert = \lvert Q \rvert$, we have $$ \sum_{a \in \F} \chi(a) = \sum_{a \in \F} \chi(a+1) = 0; $$ then because $\chi$ is a multiplicative homomorphism, and as $a^{-1} \in Q \iff a \in Q$, we have
$$\begin{align} C &= \frac{\lvert \F \rvert}{4} + \frac{1}{4}\sum_{a \in \F} \chi(a) \chi(a+1) -\frac{1}{2} - \Bigl(\frac{1 + \chi(-1)}{4}\Bigr) \\&= \frac{1}{4}\biggl[\lvert \F \rvert + \sum_{a \in \F^\times} \chi\bigl(a^{-1}(a+1)\bigr) - 2 - \Bigl(1 + \chi(-1)\Bigr)\biggr] \\&= \frac{1}{4}\biggl[ p^r - 3 - \chi(-1) + \sum_{a \in \F^\times} \chi\bigl(1+a^{-1}\bigr) \biggr] \\&= \frac{1}{4}\biggl[ p^r - 3 - \chi(-1) + \!\sum_{\! b \in \F \smallsetminus \{1\}\!\!} \chi(b) \biggr] \\&= \frac{1}{4}\Bigl[ p^r - 4 - \chi(-1) \Bigr], \end{align} $$ which is precisely the same as for the case as $r=1$ (in which $\chi(-1) = +1$ for $p \equiv 1 \pmod{4}$ and $\chi(-1) = -1$ otherwise) except with an included exponent. In particular: as $$ \chi(-1) = \begin{cases} +1 &\text{if $\F\:\!{:}\:\!\mathbb Z_p$ is an even degree extension or $p \equiv 1 \pmod{4}$}; \\ -1 &\text{otherwise}, \end{cases} $$ we have $\chi(-1) = +1$ if $p^r \equiv 1 \pmod{4}$, and $\chi(-1) = -1$ otherwise. Thus we have $$ C = \begin{cases} (p^r-5)/4, & \text{if $p^r \equiv 1 \pmod{4}$}; \\[1ex] (p^r-3)/4, & \text{if $p^r \equiv 3 \pmod{4}$}. \end{cases} $$


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.