How many quadratic residues of $\mathbb{F}_{p^n}$ are in the kernel of a morphism $\mathbb{F}_{p^n}^+\to \mathbb{F}_p^+$?

Question

Given an odd prime $p$ and a positive integer $n$, let $QR$ be the set of non-zero quadratic residues in the finite field $\mathbb{F}_{p^n}$. Suppose we have a non-trivial (additive) group homomorphism $f\colon \mathbb{F}_{p^n}^+\to \mathbb{F}_p^+$, where $\mathbb{F}_q^+$ denotes the additive group of the field $\mathbb{F}_q$. Then what can we say about the cardinality of $QR\cap \operatorname{ker}(f)$?

Very limited calculations suggest the answer is always $(p^{n-1}-1)/2$ when $n$ is odd. But things appear to change when $n$ is even. For $p=5$ and $n=2$, the cardinality can be either $0$ or $4$, for example. The odd case seems consistent with this vague understanding I have of the quadratic residues being semi-randomly distributed through half of the field (so of the $p^{n-1}-1$ non-zero elements of the kernel, then it seems reasonable to suspect that half of them would be residues); but I'm not sure how to formally establish this, or see how $n$ being even changes things.

Answer 1

This is an entertaining soup of basic facts about character sums over finite fields. But let me first record the following fact from the comments:

Fact 1. To each element $z\in\Bbb{F}_{p^n}$ we get a homomorphism $f_z$ from the additive group of $\Bbb{F}_{p^n}$ to the additive group of the prime field $\Bbb{F}_p$ from the recipe $$f_z(x)=tr(zx),$$ where $tr$ is the trace map defined by $$tr(x)=x+x^p+x^{p^2}+\cdots+x^{p^{n-1}}=\sum_{\sigma\in Gal(\Bbb{F}_{p^n}/\Bbb{F}_p)}\sigma(x).$$ Furthermore, distinct choices of $z$ yield different homomorphisms, and all the homomorphisms between these groups are of this form.

Proof. This is textbook stuff. The bigger additive group is an $n$-dimensional vector space over the prime field. Hence the homomorphisms are exactly the elements of the dual space, and there are exactly $p^n$ of them. The mapping $f_z$ is a homomorphism of additive groups because it is the sum of such beasts. If $z\neq0$ then the kernel of $f_z$ cannot have more than $p^{n-1}$ elements, because it is given by a polynomial of degree $p^{n-1}$. As $f_z-f_{z'}=f_{z-z'}$ we get as a corollary that $f_z\neq f_{z'}$ whenever $z\neq z'$. Therefore we have listed all the $p^n$ homomorphisms. QED.

I also need to list the following leading actors:

• The canonical additive character $e:\Bbb{F}_{p^n}^+\to\Bbb{C}^*$ $$e(x)=e^{2\pi i tr(x)/p}.$$
• The unique quadratic multiplicative character of order two (= the Legendre character) $\eta:\Bbb{F}_{p^n}\to\{0,\pm1\}$: $$ \eta(x)=\begin{cases} 0,&\ \text{if $x=0$,}\\ +1,&\ \text{if $x$ is a non-zero square,} \\-1,&\ \text{if $x$ is a non-square.}\end{cases} $$
• The basic geometric sum: $$\sum_{a=0}^{p-1}e(ax)=\begin{cases}p,\ \text{if $tr(x)=0$,}\\0,\ \text{otherwise.}\end{cases}$$
• The Gauss' sum $$G(p^n)=\sum_{x\in\Bbb{F}_{p^n}}e(x)\eta(x).$$

The value of the Gauss' sum is well-known (search for Gauss' sign problem and Hasse-Davenport relation): $$ \begin{aligned} G(p)&=\begin{cases}\sqrt p,&\ \text{if $p\equiv1\pmod4$},\\ i\sqrt p,&\ \text{if $p\equiv-1\pmod4$.}\end{cases}\\ G(p^n)&=-(-G(p))^n. \end{aligned} $$

Fact 2. Let $f_z:\Bbb{F}_{p^n}^+\to\Bbb{F}_p^+$ be the above homomorphism, $z\neq0$. Let $N(z)$ be the number of non-zero squares in the kernel of $f_z$. Then $$2p N(z)=\sum_{a=0}^{p-1}\sum_{y\in\Bbb{F}_{p^n}, y\neq0}e(azy)(1+\eta(y)).$$

Proof. Here $1+\eta(y)=2$ when $y$ a non-zero square, and $1+\eta(y)=0$ otherwise, so this follows from the basic geometric sum. QED.

Next I will concentrate on evaluating that character sum. Let's first fix a value for $a$, and let's include $y=0$ into the summation (so that we can apply the orthogonality of characters).

• If $a=0$, then $\sum_{y\in\Bbb{F}_{p^n}}e(azy)(1+\eta(y))=p^n$, because we can ignore the factor $e(azy)=1$, and $\eta$ takes both values $\pm1$ equally often, i.e. $(p^n-1)/2$ times.
• OTOH if $a\neq0$ then $$ \begin{aligned} \sum_{y\in\Bbb{F}_{p^n}}e(azy)(1+\eta(y))&= \sum_{y\in\Bbb{F}_{p^n}}e(azy)+\sum_{y\in\Bbb{F}_{p^n}}e(azy)\eta(y)\\ &=\sum_{y\in\Bbb{F}_{p^n}}e(azy)\eta(y),\qquad\text{by orthogonality of characters the other sum vanishes}\\ &=\sum_{x\in\Bbb{F}_{p^n}}e(x)\eta(x/(az)),\qquad\text{by the change of variable $x=ayz$}\\ &=\eta(1/(az))\sum_{x\in\Bbb{F}_{p^n}}e(x)\eta(x),\qquad\text{by multiplicativity of $\eta$}\\ &=\eta(a)\eta(z) G(p^n). \end{aligned} $$

Let me record that in a sum $\sum_{y\in\Bbb{F}_{p^n}}e(azy)(1+\eta(y))$ the contribution of $y=0$ is always equal to $+1$. Using all of the above in Fact 2, we get the following result:

$2pN(z)=p^n+\sum_{a=1}^{p-1}\eta(a)\eta(z) G(p^n)\quad -p.$

With the aid of this formula we can explain some of your observations:

• If $n$ is odd, then exactly one half of the non-zero elements $a$ of the prime field, namely the quadratic residues modulo $p$, are squares in $\Bbb{F}_{p^n}$. This is because the rest of them are squares of elements of $\Bbb{F}_{p^2}$, but those are now excluded. Therefore $\sum_{a=1}^{p-1}\eta(a)=0$, and $$ N(z)=\frac{p^n-p}{2p}=\frac12(p^{n-1}-1). $$
• But if $n$ is even, then $\eta(a)=+1$ for all $a=1,2,\ldots,p-1$. In this case we get $$ N(z)=\frac{p^n+(p-1)\eta(z)G(p^n)-p}{2p}. $$ The extra term with the Gauss' sum has absolute value $(p-1)p^{n/2}$. Its sign depends on the choice of $z$, i.e. on the choice of the homomorphism. In your example case of $p=5,n=2$ we get, all in line with your experimental data, $$ N(z)=\frac{25\pm4\cdot5-5}{2\cdot5}=4\ \text{or}\ 0. $$

Answer 2

Listing what I can do without character sums. Hopefully this can also be completed later. At the moment it is anything but a full solution.

Again, let $f_z:\Bbb{F}_{p^n}\to\Bbb{F}_p$ be the homomorphism $f_z(x)=tr(zx)$, and let $N(z)$ be the number of non-zero squares in the kernel of $f_z$.

A key observation is that a non-zero square $y^2\in \operatorname{ker}(f_z)$ if and only if the non-zero square $(cy)^2\in\operatorname{ker}(f_{z/c^2})$. This implies immediately that for all $z,c\in \Bbb{F}_{p^n}^*$ we have $$ N(z)=N(z/c^2). $$ So if $g$ is a primitive element, i.e. a generator of the multiplicative group $\Bbb{F}_{p^n}^*$, then $N(z)=N(1)$ whenever $z$ is a square, and $N(z)=N(g)$ whenever $z$ is a non-square.

On the other hand each and every non-zero element of $\Bbb{F}_{p^n}$ is, by basic linear algebra, in the kernel of exactly $p^{n-1}$ distinct homomorphisms (including the zero homomorphism) from $\Bbb{F}_{p^n}\to\Bbb{F}_p$. Therefore, counting the number of pairs $(z,x)$ where $x$ is a non-zero square in the kernel of $f_z$ in the two obvious ways, gives $$ p^{n-1}\left(\frac{p^n-1}2\right)=\left(\frac{p^n-1}2\right)\left(N(1)+N(g)+1\right). $$ In other words, we have the equation $$ N(1)+N(g)=p^{n-1}-1. $$

This means that if we can determine the number $N(1)$, then we have completely solved the main problem.

Unfortunately I don't know how to calculate $N(1)$ without character sums. Except in the case $n=2$. Let me share.

An element $x\in\Bbb{F}_{p^2}$ is in the kernel of $f_1$ if and only if $$ 0=tr(x)=x^p+x. $$ Assuming, as we do, that $x\neq0$ this is equivalent to the equation $$x^{p-1}=-1.\qquad(*)$$ Because $g$ was a generator (of order $p^2-1$), we can write $x=g^t$. It is well known that $g^{(p^2-1)/2}=-1$. Therefore $(*)$ is equivalent to $$ g^{(p^2-1)/2}=-1=x^{p-1}=g^{t(p-1)}, $$ which is, in turn, equivalent to the congruence $$ t(p-1)\equiv \frac{p^2-1}2\pmod {p^2-1}. $$ Cancelling the obvious factor $p-1$ leaves us with the congruence $$ t\equiv\frac{(p+1)}2\pmod {p+1}.\qquad(**) $$ Because $p+1$ is even, the solutions of $(**)$ are either all even or all odd according to the parity of $(p+1)/2$. Therefore, when $n=2$, the non-zero elements in the kernel of $f_1$ are either all squares or all non-squares. The former case occurs when $p\equiv-1\pmod4$ and the latter when $p\equiv1\pmod4$.

Summary #1: When $n=2$ we have the simple result that $N(1)=p-1, N(g)=0$, if $p\equiv-1\pmod4$. If $p\equiv1\pmod 4$, then the reverse holds, and $N(1)=0, N(g)=p-1$.

---

What about the case of $n>2$? The kernel of $f_z$ is always a subspace over the prime field. We can thus partition the non-zero elements of the kernel into 1-dimensional subspaces, rays if you wish, over the prime field. If $n$ is an odd number, then (see also my other answer) exactly one half of the non-zero elements of the prime field are squares in the field $\Bbb{F}_{p^n}$. Therefore, along each and every one of those rays, exactly one half of the elements are squares, and the other half are non-squares. This explains Zibadawa Timmy's observation:

Summary #2: When $2\nmid n$ we have $N(1)=N(g)=(p^{n-1}-1)/2$.

What's missing is a simple counting argument for $N(1)$ when $2\mid n$, $n\ge4$. Calling it a day.