7
$\begingroup$

It is well-known that the number of irreducible monic polynomials of degree $n$ over the finite field of $q$ elements is given by the formula $$\frac{1}{n}\sum_{d\mid n}\mu\left(\frac{n}{d}\right)q^{d}.$$ Here $\mu(\cdot)$ is the Moebius function.

A polynomial $f(t)\in k[t]$ ($k$ any field) is called even if $f(-t)=f(t)$. I was wondering if the number of monic irreducible even polynomials of a given degree $n=2m$ is known.

What I have managed to show is that within the field extension ${\bf F}_{q^{2m}}\mid {\bf F}_q$, assuming $q$ is odd, it holds that $x\in {\bf F}_{q^{2m}}$ has an even minimal polynomial over ${\bf F}_q$ iff there exists $\sigma\in{\mathrm{ Gal}}({\bf F}_{q^{2m}}\mid {\bf F}_q)$ such that $\sigma(x)=-x$.

Proof- Let $m(t)\in{\bf F}_q[t]$ be the minimal polynomial of $x$. If $m(-x)=0$ then, by the fact that ${\bf F}_{q^{2m}}\mid{\bf F}_q$ is Galois, such an automorphism $\sigma$ exists.

Conversely, suppose $\sigma(x)=-x$, and define $f(t)=\frac{1}{2}(m(t)-m(-t))\in {\bf F}_q[t]$. Then $f(x)=\frac{1}{2}(m(x)-m(\sigma(x)))=0$. Since $\deg(f)\le \deg(m)$ this implies that either $f(t)=0$ or $f(t)=m(t)$. But note that $f(t)=-f(-t)$, and hence $m(t)=-m(-t)$. In particular, $m(0)=-m(-0)=-m(0)$, which means that $m(0)=0$, a contradiction to $m$ being irreducible.$\square$

Now, I'm pretty sure that this statement and proof are valid, and I'm pretty sure that they have some value in the enumeration I'm looking for, but I'm not sure how to apply it.

Would appreciate any help.

Thank you :)

$\endgroup$
  • $\begingroup$ Looks good so far! Because $x$ is in the fixed field of $\sigma^2$ we can further conclude that for the minimal polynomial of $x$ to be of degree $n$, it is necessary that $x$ is a solution of $x^{q^m}+x=0$. But, this is not a sufficient criterion, because we then also include the solutions of $x^{q^d}+x=0$ where $d\mid m$ and $m/d$ is an odd integer. It seems to me that we then get a similar exclusion-inclusion (in other words a sum involving Möbius function), but only over the subset of factors $d$ of $m$ such that $m/d$ is odd. $\endgroup$ – Jyrki Lahtonen Jun 20 '16 at 20:04
  • $\begingroup$ (cont'd) Because $x^{q^m}+x\mid x^{q^{2m}}-x$ when $q$ is odd, counting the number of solutions is easy. For example if $q=3$, $n=2m=6$, then in the field $K=\Bbb{F}_{3^6}$ the equation $x^{27}+x=0$ has $27$ solutions. Three of those are solutions of $x^3+x=0$, and must be left out. Therefore there are $24$ element in the field $K$ such that their minimal polynomials over the prime field are even and of degree six. Each of those elements has six conjugates $K$, so it looks like you get $24/6=4$ irreducible even polynomials of degree six in $\Bbb{F}_3[x]$. $\endgroup$ – Jyrki Lahtonen Jun 20 '16 at 20:09
  • $\begingroup$ Excellent, thank you very much! It's late here, so I'll read it thoroughly in the morning, but I think I have an intuition into how to continue form your comments. Please do post an answer, so that I can accept it. Thanks again :) $\endgroup$ – kneidell Jun 20 '16 at 20:23
4
$\begingroup$

Building on the good foundation laid out by the OP (and promoting my comments to an answer).

Indeed, the minimal polynomial of an element $x$ in some extension field $L$ of $K=\Bbb{F}_q$ is even, iff $x$ and $-x$ are conjugates. When we are interested in irreducible even polynomials of degree $n=2m$, we want $L=K(x)$. If $\sigma(x)=-x$, then $$\sigma^2(x)=\sigma(-x)=x,$$ and $x$ is thus in the fixed field of $\sigma^2$, and $\sigma^2$ is the identity mapping on $K(x)$. Let $F:z\mapsto z^q$ be the Frobenius automorphism of $L/K$. Basic Galois theory of finite fields then tells us that we must have $\sigma=F^m$. In other words we get the necessary condition $$ -x=\sigma(x)=x^{q^m}\Leftrightarrow x^{q^m}+x=0.\qquad $$

Lemma 1. If $z\in L, z\neq0,$ is a zero of $P(T)=T^{q^m}+T$, then $[K(z):K]=2d$ such that $d\mid m$ and $m/d$ is an odd integer. Furthermore, $z$ is then a zero of the polynomial $R(T)=T^{q^d}+T$.

Proof. Because $-z=-z+P(z)=z^{q^m}$, the elements $z$ and $-z$ are $K$-conjugates. Therefore the minimal polynomial of $z$ is even (by the OP's result), so its degree is $2d$ for some integer $d$. Because $z\in L$ we also have $2d\mid n=2m$, and $d\mid m$. By our earlier argument we have both $F^m(z)=-z$ and $F^d(z)=-z$. If $\ell=m/d$ we thus get $$ -z=F^m(z)=(F^d)^\ell(z)=(-1)^\ell z. $$ Therefore $\ell$ must be odd. QED.

Denote by $S_m$ the set $$ S_m:=\{z\in\overline{K}\mid z^{q^m}+z=0, z\neq0\}. $$

Lemma 2. If $d\mid m$ and $m/d=\ell$ is an odd integer, then $S_d\subseteq S_m$.

Proof. If $z\in S_d$, then $F^d(z)=-z$. Repeating the above calculation we see that $F^m(z)=-z$, and hence $z\in S_m$. QED.

Because an irreducible polynomial from $K[T]$ of degree $n=2m$ has $2m$ distinct zeros in $\overline{K}$, the following result is now immediate.

Proposition. Let $N_m$ be the number of even irreducible polynomials of degree $2m$ in $K[T]$. Then we have $$ 2m N_m=|S(m)\setminus\bigcup_{d\mid m, 2\nmid (m/d)}S(d)|. $$

Lemma 3. The polynomial $P(T)=T^{q^m}+T$ has $q^m$ distinct zeros in $L$.

Proof. Because $P'(T)=1$, the zeros of $P(T)$ in $\overline{K}$ are all simple. Because $P(T)^{q^m}-P(T)=T^{q^{2m}}-T$, and the zeros of the r.h.s. polynomial are exactly the elements of $L$, we see that all the zeros of $P(T)$ are in $L$. QED.

The inclusion-exclusion formula then gives us the following formula (Möbius inversion)

Corollary. $$ N_m=\frac1{2m}\sum_{d\mid m, 2\nmid (m/d)}\mu(\frac m d)(q^d-1). $$

$\endgroup$
  • $\begingroup$ Need to use $q^d-1$ to account for the trivial solution $x=0$ that does not have an even minimal polynomial :-) $\endgroup$ – Jyrki Lahtonen Jun 20 '16 at 21:48

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.