# On the Iterative Behaviour of the Number of Irreducible Polynomials with
Certain Properties over Finite Fields

Max Schulz
University of Rostock  Germany
<EMAIL_ADDRESS>
###### Abstract

Let $\mathbb{F}_{q}$ be the field with $q$ elements and of characteristic $p$.
For $a\in\mathbb{F}_{p}$ consider the set

$S_{a}(n)=\\{f\in\mathbb{F}_{q}[x]\mid\deg(f)=n,~{}f\text{ irreducible, monic
and}\operatorname{Tr}(f)=a\\}.$

In a recent paper, Robert Granger proved for $q=2$ and $n\geq 2$

$|S_{1}(n)|-|S_{0}(n)|=\begin{cases}0,&\text{if }2\nmid n\\\
|S_{1}(n/2)|,&\text{if }2\mid n\end{cases}$

We will prove a generalization of this result for all finite fields. This is
possible due to an observation about the size of certain subsets of monic
irreducible polynomials arising in the context of a group action of subgroups
of $\operatorname{PGL}_{2}(\mathbb{F}_{q})$ on monic polynomials.
Additionally, it enables us to apply these methods to prove two further
results that are very similar in nature.

## Introduction

Let $\mathbb{F}_{q}$ be the finite field with $q$ elements, $p$ the prime
dividing $q$, $\mathcal{I}_{q}$ the set of monic irreducible polynomials in
$\mathbb{F}_{q}[x]$ and $\mathcal{I}_{q}^{n}$ the set of monic irreducible
polynomials of degree $n$. Moreover, $\operatorname{Tr}_{q/p}$ is the absolut
trace. Since
$\operatorname{Tr}_{q^{n}/p}(\alpha)=\operatorname{Tr}_{q^{n}/p}(\alpha^{q})$
for a root $\alpha$ of $f\in\mathcal{I}_{q}^{n}$ we can define
$\operatorname{Tr}(f):=\operatorname{Tr}_{q^{n}/p}(\alpha)$. For an
$a\in\mathbb{F}_{p}$ consider the set

$S_{a}(n):=\\{f\in\mathcal{I}_{q}^{n}\mid\operatorname{Tr}(f)=a\\}.$

Let $f\in\mathcal{I}_{q}^{n}$ be of the form
$f=x^{n}+\sum_{i=0}^{n-1}a_{i}x^{i}$ then the trace is given by

$\operatorname{Tr}(f)=-\operatorname{Tr}_{q/p}(a_{n-1}).$

In [6] it is proved that for $q=2$ and $n\geq 2$

$|S_{1}(n)|-|S_{0}(n)|=\begin{cases}0,&\text{if }n\equiv 1\pmod{2}\\\
|S_{1}(n/2)|,&\text{otherwise}.\end{cases}$

We are going to prove the following extension of this result:

######  Theorem 1.

For all $n\geq 1$ and all finite fields $\mathbb{F}_{q}$ we have

$\sum\limits_{a\in\mathbb{F}_{p}^{\ast}}|S_{a}(n)|-(p-1)|S_{0}(n)|=\begin{cases}0,&\text{if
}p\nmid n\\\
\sum\limits_{a\in\mathbb{F}_{p}^{\ast}}|S_{a}(n/p)|,&\text{otherwise}\end{cases}$

######  Remark 2.

Note that the balanced case, that is,

$\sum\limits_{a\in\mathbb{F}_{p}^{\ast}}|S_{a}(n)|-(p-1)|S_{0}(n)|=0,$

where $p\nmid n$, is not hard to see. Let $f\in S_{0}(n)$, so
$\operatorname{Tr}(f)=0$ which means that
$\operatorname{Tr}_{q^{n}/p}(\alpha)=0$ for $\alpha$ a root of $f$. Let
$a\in\mathbb{F}_{p}^{\ast}$ and consider an element
$b_{a}\in\mathbb{F}_{q}^{\ast}$ such that
$\operatorname{Tr}_{q^{n}/p}(b_{a})=a$. Such an element exists since
$\operatorname{Tr}_{q^{n}/p}=\operatorname{Tr}_{q/p}\circ\operatorname{Tr}_{q^{n}/q}$
and for all $b\in\mathbb{F}_{q}^{\ast}$

$\operatorname{Tr}_{q^{n}/q}(b)=n\cdot b\neq 0$

if $p\nmid n$, hence $\operatorname{Tr}_{q^{n}/p}$ as a map from
$\mathbb{F}_{q}$ to $\mathbb{F}_{p}$ is surjective as
$\operatorname{Tr}_{q/p}:\mathbb{F}_{q}\to\mathbb{F}_{p}$ and
$\operatorname{Tr}_{q^{n}/q}|_{\mathbb{F}_{q}}:\mathbb{F}_{q}\to\mathbb{F}_{q}$
are surjective. The polynomial $f(x-b_{a})$ has trace $a$, so the map
$f(x)\mapsto f(x-b_{a})$ is a bijection between $S_{0}(n)$ and $S_{a}(n)$,
thus $|S_{0}(n)|=|S_{a}(n)|$ for all $a\in\mathbb{F}_{p}$ and the balanced
case follows. A similar idea does not work for the case that $p\mid n$ since
then $\operatorname{Tr}_{q^{n}/q}|_{\mathbb{F}_{q}}$ is not surjective
anymore.

Another example that exhibits a similar pattern is the following: Let $q$ be
odd and $u,v\in\mathbb{F}_{q}$ with $u\neq v$. Define the following two sets
for $n\geq 2$

$\displaystyle C_{u,v}(n)$
$\displaystyle:=\left\\{f\in\mathcal{I}_{q}^{n}\mid\left(\frac{f(u)\cdot
f(v)}{q}\right)=-1\right\\}$ $\displaystyle D_{u,v}(n)$
$\displaystyle:=\mathcal{I}_{q}^{n}\setminus
C_{u,v}(n)=\left\\{f\in\mathcal{I}_{q}^{n}\mid\left(\frac{f(u)\cdot
f(v)}{q}\right)=1\right\\}.$

Here
$\left(\frac{\cdot}{q}\right):\mathbb{F}_{q}^{\ast}\to\\{1,-1\\}\leq\mathbb{F}_{q}^{\ast}$
denotes the Legendre-Symbol

$\left(\frac{a}{q}\right)=a^{(q-1)/2}=\begin{cases}1,&a\text{ is a square in
}\mathbb{F}_{q}^{\ast}\\\ -1,&\text{otherwise}\end{cases}$

We prove the following theorem:

######  Theorem 3.

Let $q\equiv 1\pmod{2}$. For all $u,v\in\mathbb{F}_{q}$ with $u\neq v$ and
$n\geq 2$ we have

$|C_{u,v}(n)|-|D_{u,v}(n)|=\begin{cases}0,&2\nmid n\\\ |C_{u,v}(n/2)|,&2\mid
n\end{cases}$

In [6] a group action of subgroups of $\operatorname{PGL}_{2}(\mathbb{F}_{q})$
on irreducible polynomials over $\mathbb{F}_{q}$ played a crucial role in some
of the proofs, so we thought that ideas out of our recent paper [12] could be
utilized to prove similar results. Our proof of Theorem 1 relies on a general
underlying principle which can be used to obtain Theorem 3 as well. Explaining
how that principle works is the main goal of this paper. We give a quick
overview:

For an element $A\in\operatorname{GL}_{2}(\mathbb{F}_{q})$ we write
$[A]\in\operatorname{PGL}_{2}(\mathbb{F}_{q})$ as its coset in
$\operatorname{PGL}_{2}(\mathbb{F}_{q})$ and if $A$ is of the form

$A=\left(\begin{array}[]{cc}a&b\\\ c&d\end{array}\right)$

then set

$[A]\circ x=\frac{ax+b}{cx+d}$

as the corresponding linear rational function. For a subgroup
$G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ consider the set of
$G$-invariant rational functions

$\mathbb{F}_{q}(x)^{G}:=\left\\{Q(x)\in\mathbb{F}_{q}(x)\mid Q([A]\circ
x)=Q(x)\text{ for all }[A]\in G\right\\}.$

This is a subfield of $\mathbb{F}_{q}(x)$ with
$[\mathbb{F}_{q}(x):\mathbb{F}_{q}(x)^{G}]=|G|$. Moreover, by Lüroth’s
Theorem, there is a rational function $Q(x)=g(x)/h(x)\in\mathbb{F}_{q}(x)$ of
degree $\deg(Q)=\max\\{\deg(g),\deg(h)\\}=|G|$ such that
$\mathbb{F}_{q}(x)^{G}=\mathbb{F}_{q}(Q(x))$. Note that we always assume that
the numerator and denominator of a rational function have no common factors.
Every such generator $Q$ of $\mathbb{F}_{q}(x)^{G}$ can be normalized so that
$Q=g/h$ with $\deg(g)=|G|$ and $0\leq\deg(h)<\deg(g)$, we call these rational
functions quotient maps for $G$ and in what follows we write $Q_{G}$ for an
arbitrary quotient map for $G$. In [12], we studied the factorization of
rational transformations with quotient maps. A rational transformation of a
polynomial $F$ with a rational function $Q=g/h$ is defined as

$F^{Q}(x):=h(x)^{\deg(F)}\cdot F\left(\frac{g(x)}{h(x)}\right)$ (1)

so it is the numerator polynomial of the rational function $F(Q(x))$. To avoid
ambiguity we set the numerator polynomial $g$ of $Q$ to be monic. Define the
following two sets

$\displaystyle C(Q_{G},n)$ $\displaystyle:=\left\\{f\in\mathcal{I}_{q}^{n}\mid
f^{Q_{G}}\in\mathcal{I}_{q}^{|G|n}\right\\}$ $\displaystyle D(Q_{G},n)$
$\displaystyle:=\mathcal{I}_{q}^{n}\setminus C(Q_{G},n).$

So $C(Q_{G},n)$ is the set of irreducible polynomials $f$ of degree $n$ that
yield irreducible polynomials of degree $|G|\cdot n$ after transformation with
quotient map $Q_{G}$. The following theorem will be the backbone of our proofs
of Theorem 1 and 3:

######  Theorem 4.

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ be a cyclic subgroup of
prime order $s$ and $Q_{G}\in\mathbb{F}_{q}(x)$ a quotient map for $G$. For
all $n>d(G)$ (the number $d(G)$ will be defined before Example 14) we have

$|C(Q_{G},n)|-(s-1)|D(Q_{G},n)|=\begin{cases}0,&\text{ if }s\nmid n\\\
|C(Q_{G},\frac{n}{s})|,&\text{ if }s\mid n\end{cases}$

Both results are immediate consequences of this theorem by choosing the right
cyclic subgroups $G$ and quotient maps $Q_{G}$. The set $C(Q_{G},n)$ can be
occasionally described in terms of arithmetic properties that the coefficients
of irreducible polynomials in $C(Q_{G},n)$ need to have if the quotient map
$Q_{G}$ was chosen carefully.

The first part of this paper is mainly a recollection of ideas and results of
[12]. Afterwards we are going to prove our main theorem about a new
combinatorial relationship between $G$-orbits of irreducible monic polynomials
from which Theorem 4 follows. The last part is dedicated to proving Theorem 1
and 3, as well as looking at one more example.

##  1 Invariant Polynomials and Rational Transformations

Every $[A]\in\operatorname{PGL}_{2}(\mathbb{F}_{q})$ induces a bijective map
on $\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$ via

$[A]\circ v=\frac{av+b}{cv+d},$

i.e. just plugging in $v$ into the linear rational function belonging to
$[A]$. This induces a left group action of
$\operatorname{PGL}_{2}(\mathbb{F}_{q})$ on
$\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$. An intimately related group
action on polynomials is given by

######  Definition 5.

Define
$\ast:\operatorname{PGL}_{2}(\mathbb{F}_{q})\times\mathbb{F}_{q}[x]\to\mathbb{F}_{q}[x]$
with

$[A]\ast f(x)=\lambda_{A,f}(cx+d)^{\deg(f)}f\left(\frac{ax+b}{cx+d}\right).$

The factor $\lambda_{A,f}\in\mathbb{F}_{q}^{\ast}$ makes the output-polynomial
monic.

In other words, $[A]\ast f$ is the normalized $([A]\circ x)$-transformation of
$f$. This transformation and its variations are well-studied objects over
finite fields, see for example [4], [10], [11], [13] and it has some theoretic
applications, see for example [6], [7] and [9].

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ be a subgroup and
$G\circ\infty:=\\{[A]\circ\infty|[A]\in G\\}$ be the $G$-orbit of $\infty$.
Define

$\mathcal{NR}_{q}^{G}:=\\{f\in\mathbb{F}_{q}[x]\mid f\text{ monic and
}f(\alpha)\neq 0\text{ for all }\alpha\in G\circ\infty\\}$

where $f(\infty)=\infty$ if $\deg(f)\geq 1$ and $f(\infty)=f$ if $\deg(f)\leq
0$.

######  Lemma 6 ([12, Lemma 7]).

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$. For all
$f,g\in\mathcal{NR}_{q}^{G}$ and $[A],[B]\in G$ the following hold:

  1. 1.

$\deg([A]\ast f)=\deg(f)$

  2. 2.

$[AB]\ast f=[B]\ast([A]\ast f)$ and $[I_{2}]\ast f=f$, so $\ast$ is a right
group action of $G$ on $\mathcal{NR}_{q}^{G}$

  3. 3.

$[A]\ast(fg)=([A]\ast f)([A]\ast g)$

  4. 4.

$f$ irreducible if and only if $[A]\ast f$ irreducible

The first and forth item show that $G$ also acts on $\mathcal{I}_{q}^{n}$ for
$n\geq 2$ (since $G\circ\infty\subseteq\mathbb{F}_{q}\cup\\{\infty\\}$) and on

$\displaystyle\mathcal{I}_{q}^{G}$
$\displaystyle:=\mathcal{NR}_{q}^{G}\cap\mathcal{I}_{q}.$

We denote a $G$-orbit in $\mathcal{NR}_{q}^{G}$ as $G\ast r:=\\{[A]\ast
r\mid[A]\in G\\}$.

######  Definition 7.

A polynomial $f\in\mathcal{NR}_{q}^{G}$ is called $G$-orbit polynomial if
there is an irreducible polynomial $r\in\mathcal{I}_{q}^{G}$ such that

$f=\prod\limits_{t\in G\ast r}t=:\prod G\ast r$

A $G$-invariant polynomial is a polynomial $f\in\mathcal{NR}_{q}^{G}$ such
that $[A]\ast f=f$ for all $[A]\in G$. Every $G$-invariant polynomial can be
written as the product of $G$-orbit polynomials (which are $G$-invariant by
Lemma 6 3.), so $G$-orbit polynomials can be seen as the atoms of
$G$-invariant polynomials.

Next we want to recollect some facts about rational transformations. For
$Q=g/h$ with $\gcd(g,h)=1$ and $F\in\mathbb{F}_{q}[x]$ we write
$F^{Q}\in\mathbb{F}_{q}[x]$ as the $Q$-transform of $F$ with $Q$ as in (1). It
is obvious that if $F^{Q}$ is irreducible then $F$ has to be irreducible. The
following lemma gives a necessary and sufficient condition for the
irreducibility of $F^{Q}$:

######  Lemma 8 ([3, Lemma 1]).

Let $Q(x)=g(x)/h(x)\in\mathbb{F}_{q}(x)$ and $F\in\mathbb{F}_{q}[x]$. Then
$F^{Q}\in\mathbb{F}_{q}[x]$ is irreducible if and only if
$F\in\mathbb{F}_{q}[x]$ is irreducible and $g(x)-\alpha h(x)$ is irreducible
over $\mathbb{F}_{q}(\alpha)[x]$, where $\alpha$ is a root of $F$.

Now consider a quotient map $Q_{G}\in\mathbb{F}_{q}(x)$ of
$G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$. We have

######  Lemma 9 ([12, Lemma 13 and Lemma 14]).

Let $F\in\mathbb{F}_{q}[x]$ be a monic polynomial, then
$F^{Q_{G}}\in\mathcal{NR}_{q}^{G}$ and $F^{Q_{G}}$ is $G$-invariant. Moreover,
$F^{Q_{G}}$ is of degree $\deg(F^{Q_{G}})=|G|\cdot\deg(F)$.

######  Theorem 10 ([12, Main Theorem, Theorem 22 and Corollary 23]).

Let $F\in\mathbb{F}_{q}[x]$ be monic and irreducible,
$G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ a subgroup and
$Q_{G}=g/h\in\mathbb{F}_{q}(x)$ a quotient map for $G$. Then there is an
irreducible monic polynomial $r\in\mathbb{F}_{q}[x]$ with $\deg(F)|\deg(r)$
and an integer $k>0$ such that

$F^{Q_{G}}(x)=\left(\prod G\ast r\right)^{k}.$

Additionally $F^{Q_{G}}$ is an orbit polynomial, i.e. $k=1$, if $|G\circ
v|=|G|$ for a root $v\in\overline{\mathbb{F}}_{q}$ of $F^{Q_{G}}$. In the case
that $F^{Q_{G}}$ is an orbit polynomial the degree of every irreducible factor
of $F^{Q_{G}}$ can be calculated via

$\deg(r)=\frac{|G|}{|G\ast r|}\cdot\deg(F).$

The polynomials $F\in\mathcal{I}_{q}$ for which $F^{Q_{G}}=(\prod G\ast
r)^{k}$ with $k>1$ are of degree $\deg(F)\leq 2$. To show that we use the fact
that $F^{Q_{G}}$ is an orbit polynomial if every (or equivalently just one)
root $v\in\overline{\mathbb{F}}_{q}$ of $F^{Q_{G}}$ is contained in a regular
$G$-orbit, i.e. $|G\circ v|=|G|$ (Theorem 10) and irreducible polynomials $F$
not satisfying that condition are of degree less than or equal to $2$, as the
following lemma shows:

######  Lemma 11 ([1, Lemma 2.1]).

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ and set

$P_{G}:=\left\\{v\in\overline{\mathbb{F}}_{q}\cup\\{\infty\\}\mid|G\circ
v|<|G|\right\\}.$

We have $P_{G}\subseteq\mathbb{F}_{q^{2}}\cup\\{\infty\\}$ and $|P_{G}|\leq
2(|G|-1)$.

Let $F\in\mathcal{I}_{q}$. Note that if $F^{Q_{G}}$ has roots in non-regular
$G$-orbits, then it only has irreducible factors of degree less than 3 by the
lemma above. Moreover, we know that if $r$ is an irreducible factor of
$F^{Q_{G}}$, then $\deg(F)\mid\deg(r)$, so $\deg(F)\leq 2$, which is exactly
what we wanted to show. Furthermore, there are only finitely many irreducible
monic polynomials $F\in\mathcal{I}_{q}$ such that $F^{Q_{G}}$ is not a
$G$-orbit polynomial but a proper power thereof as the number of non-regular
$G$-orbits in $\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$ is finite.

The next corollary is one of our main tools we make use of in this paper.
Define $\mathcal{I}_{q}^{G}/G$ as the set of $G$-orbits in
$\mathcal{I}_{q}^{G}$, that is,

$\mathcal{I}_{q}^{G}/G:=\\{G\ast r\mid r\in\mathcal{I}_{q}^{G}\\}.$

######  Corollary 12 ([12, Corollary 25]).

The map $\delta_{Q_{G}}:\mathcal{I}_{q}\to\mathcal{I}_{q}^{G}/G$ with
$F\mapsto G\ast r$ such that $F^{Q_{G}}=\prod(G\ast r)^{k}$ is a bijection.

An irreducible monic $G$-invariant polynomial $f$ is a $G$-orbit polynomial,
thus $f$ can be written as $f=F^{Q_{G}}$ for $F$ an irreducible monic
polynomial if a root of $f$ is contained in a regular $G$-orbit by Theorem 10
and Corollary 12.

##  2 Combinatorics of Orbits of Irreducible Polynomials

Set $d(Q_{G})\in\mathbb{N}_{0}$ as the biggest number such that there exists
an irreducible polynomial $F\in\mathcal{I}_{q}$ of degree $d(Q_{G})$ with
$F^{Q_{G}}=\prod(G\ast r)^{k}$ and $k>1$. If no such polynomial exists then
$d(Q_{G}):=0$. Recall that $d(Q_{G})\leq 2$.

######  Remark 13.

If $Q_{G},Q_{G}^{\prime}\in\mathbb{F}_{q}(x)$ are quotient maps for $G$, then
$d(Q_{G})=d(Q_{G}^{\prime})$.

###### Proof.

Let $F\in\mathcal{I}_{q}$ be of degree $d(Q_{G})$ such that $F^{Q_{G}}=(\prod
G\ast r)^{k}$ and $k>1$. It can be shown that there are
$a\in\mathbb{F}_{q}^{\ast}$ and $b\in\mathbb{F}_{q}$ such that
$Q_{G}(x)=aQ_{G}^{\prime}(x)+b$, for reference see [1, Proposition 3.4]. Since
we want the numerator polynomial of quotient maps to be monic we write for
$Q_{G}^{\prime}=g^{\prime}/h^{\prime}$:

$Q_{G}(x)=aQ_{G}^{\prime}(x)+b=\frac{g^{\prime}(x)}{a^{-1}h^{\prime}(x)}+b.$

Thus we have

$\displaystyle F^{Q_{G}}(x)$
$\displaystyle=(a^{-1}h^{\prime}(x))^{\deg(F)}\cdot
F(Q_{G}(x))=h^{\prime}(x)^{\deg(F)}\cdot\left((a^{-1})^{\deg(F)}F(aQ_{G}^{\prime}(x)+b)\right)$
$\displaystyle=h^{\prime}(x))^{\deg(F)}\cdot(\underbrace{[A]\ast
F}_{=:H(x)})^{Q_{G}^{\prime}},$

where

$A=\left(\begin{array}[]{cc}a&b\\\ 0&1\end{array}\right).$

Therefore $H(x)=[A]\ast F(x)$ is an irreducible polynomial of degree
$\deg(H)=\deg(F)=d(Q_{G})$. Additionally,
$H^{Q_{G}^{\prime}}=F^{Q_{G}}=\prod(G\ast r)^{k}$ with $k>1$, so
$d(Q_{G}^{\prime})\geq d(Q_{G})$. Because of symmetry we get
$d(Q_{G}^{\prime})=d(Q_{G})$. ∎

This is why we can write $d(G)$ instead of $d(Q_{G})$. We give an example that
shows that all the values {0,1,2} are possible:

######  Example 14.

As a field we take $\mathbb{F}_{2}$. For $d(G)=0$ we take

$G=\left\\{\left[\left(\begin{array}[]{cc}1&1\\\
0&1\end{array}\right)\right],\left[\left(\begin{array}[]{cc}1&0\\\
0&1\end{array}\right)\right]\right\\}.$

The two possible quotient maps are $Q_{G}(x)=x^{2}+x$ and
$Q_{G}(x)=x^{2}+x+1$. Set

$A=\left(\begin{array}[]{cc}1&1\\\ 0&1\end{array}\right),$

then

$[A]\ast f(x)=f(x+1)$

and

$[A]\circ v=v+1$

for all $v\in\overline{\mathbb{F}}_{2}$ and $[A]\circ\infty=\infty$. Since
$v\neq v+1$ for $v\in\overline{\mathbb{F}}_{2}$ all $G$-orbits in
$\overline{\mathbb{F}}_{2}$ are regular, thus $d(G)=0$ by Theorem 10.

For $d(G)=1$ we choose

$G=\left\\{\left[\left(\begin{array}[]{cc}0&1\\\
1&0\end{array}\right)\right],\left[\left(\begin{array}[]{cc}1&0\\\
0&1\end{array}\right)\right]\right\\}$

with quotient map $Q_{G}(x)=x+1/x=(x^{2}+1)/x$. Note that $d(G)<2$ since
$(x^{2}+x+1)^{Q_{G}}=x^{4}+x^{3}+x^{2}+x+1$ is irreducible. To show that
$d(Q_{G})\geq 1$ we calculate

$x^{Q_{G}}=x^{2}+1=(x+1)^{2}.$

For $d(G)=2$ we can look at

$G=\left\\{\left[\left(\begin{array}[]{cc}1&1\\\
1&0\end{array}\right)\right],\left[\left(\begin{array}[]{cc}0&1\\\
1&1\end{array}\right)\right],\left[\left(\begin{array}[]{cc}1&0\\\
0&1\end{array}\right)\right]\right\\}$

with quotient map $Q_{G}(x)=(x^{3}+x+1)/(x^{2}+x)$. For this case we
conveniently only have to look at

$\displaystyle(x^{2}+x+1)^{Q_{G}}=(x^{2}+x+1)^{3},$

so $d(G)=2$.

Later we will often determine $d(G)$ by using the second part of Theorem 10 in
a contrapositive way, that means:

$F^{Q_{G}}=\prod(G\ast r)^{k}\text{ with }k>1\Rightarrow|G\circ v|<|G|\text{
for a root }v\in\overline{\mathbb{F}}_{q}\text{ of }F^{Q_{G}}.$

Since there are only finitely many non-regular $G$-orbits we only have to
check finitely many irreducible polynomials $F$ of degree $1$ or $2$. In this
paper we only have to check at most $2$ polynomials.

Let

$\omega_{G}(n,k):=|\\{G\ast r\mid r\in\mathcal{I}_{q}^{n}\text{ and }|G\ast
r|=k\\}|$

be the number of $G$-orbits in $\mathcal{I}_{q}^{n}$ of size $k$ and
$N_{q}(n):=|\mathcal{I}_{q}^{n}|$. Our main result is the following:

######  Theorem 15.

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$. For all $m>d(G)$ we get

$N_{q}(m)=\sum\limits_{k\mid|G|}\omega_{G}(m\cdot\frac{|G|}{k},k).$

###### Proof.

Define

$M_{m}(G):=\\{(a,b)\in\mathbb{N}^{2}:~{}b\mid|G|\text{ and }a\cdot b=|G|\cdot
m\\}$

and for $n\geq 1$

$\Omega_{G}(n,k):=\\{G\ast r\mid r\in\mathcal{I}_{q}^{n}\text{ and }|G\ast
r|=k\\},$

so $\omega_{G}(n,k)=|\Omega_{G}(n,k)|$. We want to show that

$\delta_{Q_{G}}(\mathcal{I}_{q}^{m})=\bigcup_{(n,k)\in
M_{m}(G)}\Omega_{G}(n,k).$

for $\delta_{Q_{G}}$ as in Theorem 12. Let $F\in\mathcal{I}_{q}^{m}$, then by
Theorem 12 together with $m>d(G)$ we have that $F^{Q_{G}}=\prod(G\ast r)$ for
$r\in\mathcal{I}_{q}^{G}$ and by Theorem 10

$\deg(r)\cdot|G\ast r|=m\cdot|G|.$

Thus $(\deg(r),|G\ast r|)\in M_{m}(G)$ and

$\delta(F)\in\Omega_{G}(\deg(r),|G\ast r|)\subseteq\bigcup\limits_{(n,k)\in
M_{m}(G)}\Omega_{G}(n,k).$

This shows $\delta(\mathcal{I}_{q}^{m})\subseteq\bigcup_{(n,k)\in
M_{m}(G)}\Omega_{G}(n,k)$. Conversely let $G\ast r\in\Omega_{G}(n,k)$ with
$(n,k)\in M_{m}(G)$, thus $|G\ast r|=k$ and $\deg(r)=n$. Moreover

$\deg(r)\cdot|G\ast r|=n\cdot k=|G|\cdot m$

By Theorem 12 there exists a polynomial $F\in\mathcal{I}_{q}$ such that
$F^{Q_{G}}=\prod(G\ast r)^{l}$ and $l\geq 1$. Hence

$\displaystyle\deg(F^{Q_{G}})$ $\displaystyle=|G|\cdot\deg(F)$
$\displaystyle=l\cdot\deg(r)\cdot|G\ast r|=l\cdot(|G|\cdot m)$

So $\deg(F)=l\cdot m>d(G)$ and as a consequence $l=1$. Therefore the degree of
$F$ is $m$ which shows

$\delta_{Q_{G}}(\mathcal{I}_{q}^{m})\supseteq\bigcup_{(n,k)\in
M_{m}(G)}\Omega_{G}(n,k),$

so both sets are equal. Since $\delta_{Q_{G}}$ is a bijection we get

$\displaystyle N_{q}(m)$
$\displaystyle=|\delta_{Q_{G}}(\mathcal{I}_{q}^{m})|=|\bigcup_{(n,k)\in
M_{m}(G)}\Omega_{G}(n,k)|=\sum\limits_{(n,k)\in M_{m}(G)}|\Omega_{G}(n,k)|$
$\displaystyle=\sum\limits_{(n,k)\in
M_{m}(G)}\omega_{G}(n,k)=\sum\limits_{k\mid|G|}\omega_{G}(m\cdot\frac{|G|}{k},k).$

∎

This formula can be used to obtain the number of irreducible monic
$G$-invariant polynomials, because

$\omega_{G}(|G|\cdot
m,1)=N_{q}(m)-\sum\limits_{\begin{subarray}{c}k\mid|G|,\\\ k\neq
1\end{subarray}}\omega_{G}(m\cdot\frac{|G|}{k},k)$

and the $G$-orbits of size 1 are the irreducible monic $G$-invariant
polynomials. However, as the numbers $\omega_{G}(n,k)$ are hard to compute in
general this formula is not practical. For the exact counting formulae of
$G$-invariant polynomials see [11]. Some special values of $\omega_{G}(n,k)$
are:

  * •

$\omega_{G}(n,1)=0$ if $n>2$ and $|G|\nmid n$ (Theorem 10 and Lemma 11)

  * •

$\omega_{G}(n,1)=0$ if $n>2$ and $G$ is non-cyclic ([11, Theorem 1.3] or [12,
Corollary 35])

  * •

$\omega_{G}(n,k)=\frac{1}{k}|N_{q}(n)|$ if $k\nmid n$ and $|G|=k$ is prime
(use first item and standard group action arguments)

There is one family of subgroups for which Theorem 15 yields an easy counting
formula:

######  Corollary 16.

Let $G\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$ be a cyclic subgroup with
$|G|=s$ and $s$ is prime. For all $m>d(G)$ we have

$N_{q}(m)=\omega_{G}(m,s)+\omega_{G}(m\cdot s,1)$

This is enough to prove Theorem 4.

###### Proof (Theorem 4)..

If $|G|=s$ is prime then $|C(Q_{G},n)|=\omega_{G}(n\cdot s,1)$ and
$|D(Q_{G},n)|=N_{q}(n)-|C(Q_{G},n)|=\omega_{G}(n,s)$ by Corollary 16 and
$n>d(G)$. Thus we have

$\displaystyle|C(Q_{G},n)|-(s-1)|D(Q_{G},n)|$
$\displaystyle=\omega_{G}(ns,1)+(s-1)\omega_{G}(n,s)$
$\displaystyle=\left(\omega_{G}(ns,1)+\omega_{G}(n,s)\right)-s\omega_{G}(n,s)$
$\displaystyle=N_{q}(n)-s\omega_{G}(n,s)=\omega_{G}(n,1)$

For all $n>d(G)$ with $s\nmid n$ we have

$|C(Q_{G},n)|-(s-1)|D(Q_{G},n)|=\omega_{G}(n,1)=0.$

If $s\mid n$ and $n/s>d(G)$ then $|C(Q_{G},n/s)|=\omega_{G}(n,1)$ by Corollary
16. Moreover, if $n>2$ and $s\mid n$ then also
$|C(Q_{G},n/s)|=\omega_{G}(n,1)$ by Theorem 10 since all $G$-invariant
irreducible polynomials $f\in\mathcal{I}_{q}^{n}$ have roots that lie in
regular orbits. That is the case because
$[\mathbb{F}_{q}(\gamma):\mathbb{F}_{q}]=n>2$ for a root $\gamma$ of $f$ and
all non-regular $G$-orbits are contained in
$\mathbb{F}_{q^{2}}\cup\\{\infty\\}$; see Lemma 11. The only cases for $n$
that are left to cover are for $d(G)<n\leq\min\\{2,d(G)\cdot s\\}$. If
$d(G)\in\\{0,2\\}$ there are no such $n$. Thus $d(G)=1$ and because $s>1$ also
$n=2$. Since we still are in the case $s\mid n$ we have $s=2=|G|$. So the last
case we have to cover is $d(G)=1$ and $n=s=2$. Let $F\in\mathcal{I}_{q}$ be of
degree $d(G)=1$ such that $F^{Q_{G}}=\prod(G\ast r)^{k}$ with $k\geq 2$. Then

$\deg(F^{Q_{G}})=|G|\cdot\deg(F)=2=k\cdot|G\ast r|\cdot\deg(r)\geq 2|G\ast
r|\cdot\deg(r)$

so $\deg(r)=1=|G\ast r|$. Hence for all irreducible $G$-invariant polynomials
$f$ of degree 2 there is a polynomial $F$ of degree 1 such that $F^{Q_{G}}=f$
by Corollary 12, so $|C(Q_{G},1)|=\omega_{G}(2,1)$.

In all three subcases of $s\mid n$ we have $|C(Q_{G},n/s)|=\omega_{G}(n,1)$,
which concludes the proof. ∎

##  3 Examples

###  3.1 Proof of Theorem 1

For proving Theorem 1 we need to consider the cyclic subgroup

$G:=\left\langle\left[\left(\begin{array}[]{cc}1&1\\\
0&1\end{array}\right)\right]\right\rangle.$

It has order $p=\operatorname{char}(\mathbb{F}_{q})$ and a quotient map is
$Q_{G}(x)=x^{p}-x$. Note that the $Q_{G}$-transformation of polynomials
$F\in\mathbb{F}_{q}[x]$ with $Q_{G}$ is just the composition of $F$ with
$Q_{G}$, that is, $F^{Q_{G}}(x)=F(Q_{G}(x))$. The condition for
$F(Q_{G}(x))=F(x^{p}-x)$ to be irreducible is well-known and originally due to
Varshamov, see for example [2, Lemma 1.1] and the references therein. For
$F\in\mathcal{I}_{q}^{n}$ and $\alpha\in\overline{\mathbb{F}}_{q}$ a root of
$F$ we have

$F(Q_{G}(x))\in\mathbb{F}_{q}[x]\text{ is
irreducible}\Leftrightarrow\operatorname{Tr}_{q^{n}/p}(\alpha)\neq 0.$

As mentioned in the introduction we can write the condition as follows:

$F(Q_{G}(x))\in\mathbb{F}_{q}[x]\text{ is irreducible
}\Leftrightarrow\operatorname{Tr}(F)\neq 0.$

Hence

$\bigcup\limits_{a\in\mathbb{F}_{p}^{\ast}}S_{a}(n)=C(Q_{G},n)$

and $D(Q_{G},n)=S_{0}(n)$. The number $d(G)=0$ since the only non-regular
$G$-orbit in $\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$ is $\\{\infty\\}$.
Applying Theorem 4 gives

$\displaystyle\left|\bigcup\limits_{a\in\mathbb{F}_{p}^{\ast}}S_{a}(n)\right|-(p-1)|S_{0}(n)|$
$\displaystyle=|C(Q_{G},n)|-(p-1)|D(Q_{G},n)|$
$\displaystyle=\begin{cases}0,&p\nmid n\\\ |C(Q_{G},n/p)|,&p\mid n\end{cases}$
$\displaystyle=\begin{cases}0,&p\nmid n\\\
|\bigcup\limits_{a\in\mathbb{F}_{p}^{\ast}}S_{a}(n/p)|,&p\mid n\end{cases}$

for all $n>d(G)=0$. This proves Theorem 1.

###  3.2 Proof of Theorem 3

Assume $q\equiv 1\pmod{2}$ and let $u,v\in\mathbb{F}_{q}$ such that $u\neq v$.
Consider the matrix

$A_{u,v}:=\left(\begin{array}[]{cc}\frac{1}{2}(u+v)&-uv\\\
1&-\frac{1}{2}(u+v)\end{array}\right).$

Since $[A_{u,v}]^{2}=[I_{2}]$ the cyclic group
$G_{u,v}:=\langle[A_{u,v}]\rangle\leq\operatorname{PGL}_{2}(\mathbb{F}_{q})$
contains only 2 elements. As a quotient map for $G_{u,v}$ we choose

$Q_{G_{u,v}}(x)=\frac{1}{2}(x+[A_{u,v}]\circ x)=\frac{x^{2}-uv}{2x-(u+v)}.$

Note that $Q_{G_{u,v}}(u)=u$ and $Q_{G_{u,v}}(v)=v$ since $[A_{u,v}]\circ u=u$
and $[A_{u,v}]\circ v=v$. Moreover $\\{u\\}$ and $\\{v\\}$ are the only non-
regular $G_{u,v}$-orbits in $\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$, hence
$d(G_{u,v})$ is the highest degree of the two polynomials
$F_{1},F_{2}\in\mathcal{I}_{q}$ (if they exist) such that

$\displaystyle F_{1}^{Q_{G_{u,v}}}(x)$ $\displaystyle=(x-u)^{2}$
$\displaystyle F_{2}^{Q_{G_{u,v}}}(x)$ $\displaystyle=(x-v)^{2}$

by Theorem 10. We chose $Q_{G_{u,v}}$ so that $(x-u)^{Q_{G_{u,v}}}=(x-u)^{2}$
and $(x-v)^{Q_{G_{u,v}}}=(x-v)^{2}$, thus $d(G_{u,v})=1$.

Let $F\in\mathcal{I}_{q}$, then $F^{Q_{G_{u,v}}}$ is irreducible if and only
if

$\displaystyle P(x)$ $\displaystyle:=(x^{2}-uv)-\gamma(2x-(u+v))$
$\displaystyle=x^{2}-2\gamma x+(\gamma(u+v)-uv)\in\mathbb{F}_{q}(\gamma)[x]$

is irreducible for $\gamma\in\overline{\mathbb{F}}_{q}$ a root of $F$ by Lemma
8. A quadratic polynomial over $\mathbb{F}_{q}(\gamma)$ is irreducible if and
only if it has no roots in $\mathbb{F}_{q}(\gamma)$. For $P$ this is
equivalent to $4\gamma^{2}-4(\gamma(u+v)-uv)$ being a non-square in
$\mathbb{F}_{q}(\gamma)=\mathbb{F}_{q^{\deg(F)}}$. Hence

$\displaystyle-1$
$\displaystyle=\left(\frac{4\gamma^{2}-4(\gamma(u+v)-uv)}{q^{\deg(F)}}\right)=\left(\frac{\gamma^{2}-(u+v)\gamma+uv}{q^{\deg(F)}}\right)$
$\displaystyle=\left(\frac{(\gamma-u)(\gamma-v)}{q^{\deg(F)}}\right)=\left((\gamma-u)(\gamma-v)\right)^{\frac{q^{\deg(F)}-1}{2}}$
$\displaystyle=\left((u-\gamma)(v-\gamma)\right)^{\frac{q^{\deg(F)}-1}{q-1}\cdot\frac{q-1}{2}}=\left(\prod\limits_{i=0}^{\deg(F)-1}(u-\gamma^{q^{i}})\right)^{\frac{q-1}{2}}\cdot\left(\prod\limits_{i=0}^{\deg(F)-1}(v-\gamma^{q^{i}})\right)^{\frac{q-1}{2}}$
$\displaystyle=F(u)^{\frac{q-1}{2}}\cdot
F(v)^{\frac{q-1}{2}}=\left(\frac{F(u)\cdot F(v)}{q}\right).$

This calculation is very similar to a calculation trick that Meyn used in [8,
Proof of Theorem 8]. We showed that
$C(Q_{G_{u,v}},n)=\\{f\in\mathcal{I}_{q}^{n}\mid\left(\frac{f(u)f(v)}{q}\right)=-1\\}$,
the rest of the proof of Theorem 3 follows from Theorem 4.

###  3.3 An Example similar to Theorem 3

Let $\mathbb{F}_{q}$ be an arbitrary finite field, $s$ a prime dividing $q-1$
and $c\in\mathbb{F}_{q}$. Define

$\displaystyle T_{c}(n)$ $\displaystyle:=\left\\{f\in\mathcal{I}_{q}^{n}\mid
f(c)^{\frac{q-1}{s}}\neq(-1)^{\frac{(q-1)n}{s}}\right\\}$ $\displaystyle
U_{c}(n)$ $\displaystyle:=\mathcal{I}_{q}^{n}\setminus
T(n)=\left\\{f\in\mathcal{I}_{q}^{n}\mid
f(c)^{\frac{q-1}{s}}=(-1)^{\frac{(q-1)n}{s}}\right\\}.$

We are going to prove the following theorem

######  Theorem 17.

Let $\mathbb{F}_{q}$ be an arbitrary finite field and $s$ a prime dividing
$q-1$. Moreover let $c\in\mathbb{F}_{q}$, then we have for all $n\geq 2$ that

$|T_{c}(n)|-(s-1)|U_{c}(n)|=\begin{cases}0,&\text{ if }s\nmid n\\\
|T_{c}(n/s)|,&\text{ if }s\mid n\end{cases}$

Before we start with the proof we need to formulate a lemma first, which is
folklore.

######  Lemma 18.

Let $\mathbb{F}_{q}$ be an arbitrary finite field, $c\in\mathbb{F}_{q}^{\ast}$
and $s$ a prime dividing $q-1$. The polynomial $x^{s}-c\in\mathbb{F}_{q}[x]$
is irreducible if and only if $c^{\frac{q-1}{s}}\neq 1$.

###### Proof. (Theorem 17).

We consider the following matrix

$A:=\left(\begin{array}[]{cc}a&b\\\ 0&1\end{array}\right).$

where $a\in\mathbb{F}_{q}^{\ast}$ has order $s>1$ which is prime and
$b\in\mathbb{F}_{q}$ is arbitrary. The group $G:=\langle[A]\rangle$ has order
$s$. The fixed points of $[A]$ are $\infty$ and $c:=\frac{-b}{a-1}$ and these
are again the only non-regular orbits in
$\overline{\mathbb{F}}_{q}\cup\\{\infty\\}$. Note that we can obtain every
$c\in\mathbb{F}_{q}$ for fixed $a\in\mathbb{F}_{q}^{\ast}\setminus\\{1\\}$ by
choosing $b=(1-a)\cdot c$. A quotient map for $G$ is

$Q_{G}(x)=(x-c)^{s}+c.$

and $(x-c)^{Q_{G}}=(x-c)^{s}$, so $d(G)=1$.

Let $F\in\mathcal{I}_{q}^{n}$, then $F^{Q_{G}}(x)=F(Q_{G}(x))$ is irreducible
if and only if

$P(x)=Q_{G}(x)-\gamma=(x-c)^{s}+c-\gamma\in\mathbb{F}_{q^{n}}[x]$

is irreducible by Lemma 8, where $\gamma$ is a root of $F$. The polynomial
$P(x)\in\mathbb{F}_{q^{n}}[x]$ is irreducible if and only if
$P(x+c)=x^{s}-(\gamma-c)\in\mathbb{F}_{q^{n}}[x]$ is irreducible. By Lemma 18
this is the case exactly when $(\gamma-c)^{(q^{n}-1)/s}\neq 1$. Now we
calculate:

$\displaystyle 1$
$\displaystyle\neq(\gamma-c)^{\frac{q^{n}-1}{s}}=(-1)^{\frac{q^{n}-1}{q-1}\cdot\frac{q-1}{s}}\cdot(c-\gamma)^{\frac{q^{n}-1}{q-1}\cdot\frac{q-1}{s}}$
$\displaystyle=\left(\prod\limits_{i=0}^{n-1}(-1)^{q^{i}}\right)^{\frac{q-1}{s}}\cdot\left(\prod\limits_{i=0}^{n-1}(c-\gamma^{q^{i}})\right)^{\frac{q-1}{s}}=(-1)^{\frac{(q-1)n}{s}}\cdot
f(c)^{\frac{q-1}{s}}$

Hence $C(Q_{G},n)=T_{c}(n)$, the rest follows from Theorem 4 again. ∎

######  Remark 19.

  1. 1.

If we take $s=2$ the condition in $T_{c}(n)$ is

$(-1)^{\frac{(q-1)n}{2}}\neq
f(c)^{\frac{q-1}{2}}=\left(\frac{f(c)}{q}\right).$

This looks quite similar to the defining condition of $C_{u,v}(n)$ in Theorem
3.

  2. 2.

In Theorem 17 we used the criterion of Lemma 18 for the irreducibility of
binomials of the form $x^{s}-c$ where $s$ is a prime dividing $q-1$. If the
reader is interested in a recent paper that explains the factorization of
polynomials $x^{n}-c\in\mathbb{F}_{q}[x]$ for arbitrary $n$ we refer them to
[5].

## References

  * [1] Antonia W. Bluher  “Explicit Artin maps into $PGL_{2}$”  In _Expositiones Mathematicae_ 40.1, 2022, pp. 45–93
  * [2] Xiwang Cao and Lei Hu  “On the reducibility of some composite polynomials over finite fields”  In _Designs, Codes and Cryptography_ 64, 2012
  * [3] Stephen D. Cohen  “On irreducible polynomials of certain types in finite fields”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 66.2 Cambridge University Press, 1969, pp. 335–344
  * [4] Theodoulos Garefalakis  “On the action of $GL_{2}(\mathbb{F}_{q})$ on irreducible polynomials over $\mathbb{F}_{q}$”  In _Journal of Pure and Applied Algebra_ 215, 2011, pp. 1835–1843
  * [5] Anna-Maurin Graner  “The factorization of $X^{n}-a$ and $f(X^{n})$ over $\mathbb{F}_{q}$”, 2023  arXiv:2306.11183 [math.NT]
  * [6] Robert Granger  “Three proofs of an observation on irreducible polynomials over GF(2)”  In _Finite Fields and Their Applications_ 88, 2023, pp. 102192
  * [7] Giorgos Kapetanakis  “Prescribing coefficients of invariant irreducible polynomials”  In _Journal of Number Theory_ 180, 2017, pp. 615–628
  * [8] Helmut Meyn  “On the Construction of Irreducible Self-Reciprocal Polynomials Over Finite Fields”  In _AAECC 1_ , 1990, pp. 43–53
  * [9] Daniel Panario, Lucas Reis and Qiang Wang  “Construction of irreducible polynomials through rational transformations”  In _Journal of Pure and Applied Algebra_ 224.5, 2020, pp. 106241
  * [10] Lucas Reis  “Möbius-like maps on irreducible polynomials and rational transformations”  In _Journal of Pure and Applied Algebra_ 224, 2019, pp. 169–180
  * [11] Lucas Reis  “On the existence and number of invariant polynomials”  In _Finite Fields and Their Applications_ 61, 2020, pp. 101605
  * [12] Max Schulz  “Rational Transformations and Invariant Polynomials”, 2023  arXiv:2306.13502 [math.NT]
  * [13] Henning Stichtenoth and Alev Topuzoğlu  “Factorization of a class of polynomials over finite fields”  In _Finite Fields and Their Applications_ 18.1, 2012, pp. 108–122