# Irreducible polynomials from a cubic transformation

Sandro Mattarei<EMAIL_ADDRESS>Charlotte Scott Centre for Algebra
University of Lincoln
Brayford Pool Lincoln, LN6 7TS
United Kingdom  and  Marco Pizzato<EMAIL_ADDRESS>Dipartimento di
Matematica
Università degli Studi di Trento
via Sommarive 14
I-38123 Povo (Trento)
Italy

###### Abstract.

Let $R(x)=g(x)/h(x)$ be a rational expression of degree three over the finite
field $\mathbb{F}_{q}$. We count the irreducible polynomials in
$\mathbb{F}_{q}[x]$, of a given degree, which have the form $h(x)^{\deg
f}\cdot f\bigl{(}R(x)\bigr{)}$ for some $f(x)\in\mathbb{F}_{q}[x]$. As an
application, we recover the number of irreducible transformation shift
registers of order three, previously computed by Jiang and Yang.

###### Key words and phrases:

Irreducible polynomial; Cubic transformation

###### 2000 Mathematics Subject Classification:

Primary 12E05; secondary 12E20

##  1\. Introduction

Let $R(x)$ be a rational expressions of degree $r$ over a finite field
$\mathbb{F}_{q}$. Thus, $R(x)$ has the form $R(x)=g(x)/h(x)$, where $g(x)$ and
$h(x)$ are coprime polynomials in $\mathbb{F}_{q}[x]$ with $\max\\{\deg g,\deg
h\\}=r$. To $R(x)$ (or, to be rigorous, to the pair of polynomials $g(x)$,
$h(x)$, which is determined by $R(x)$ only up to scalar multiples) we
associate a transformation of polynomials in $\mathbb{F}_{q}[x]$, given by
sending a polynomial $f(x)$ in $\mathbb{F}_{q}[x]$ to the polynomial
$f_{R}(x)=h(x)^{n}\cdot f\bigl{(}g(x)/h(x)\bigr{)}$.

The case $r=1$ is of little interest, but quadratic transformations (that is,
with $r=2$) occur naturally. As a notable example, any self-reciprocal
polynomial $F(x)\in\mathbb{F}_{q}[x]$ (which means satisfying $x^{\deg F}\cdot
F(1/x)=F(x)$) which does not have $1$ or $-1$ as a root can be written in the
form $F(x)=x^{\deg f}\cdot f(x+1/x)$ for some polynomial
$f(x)\in\mathbb{F}_{q}[x]$, hence $F(x)=f_{R}(x)$ with $R(x)=(x^{2}+1)/x$.

The number of self-reciprocal irreducible monic polynomials of a given degree
over $\mathbb{F}_{q}$ was determined by Carlitz in [Car67], and later
investigated by various other authors. In particular, in [Ahm11] Ahmadi
extended Carlitz’s formula to a count of irreducible polynomials obtained from
an arbitrary quadratic transformation.

The fact that the counting formula found by Ahmadi is essentially the same as
Carlitz’s formula for the special case $R(x)=(x^{2}+1)/x$, at least for $q$
odd, was given a simple explanation in [MP17]. It depends on the fact that
such enumeration is essentially unaffected when the quadratic rational
expression $g(x)/h(x)$ is replaced with any other obtained from it by
composition, on both sides, with independent Möbius transformations (meaning
rational expressions of degree $1$). We call such rational expressions
equivalent in this paper. It is not hard to see that all quadratic rational
expressions $g(x)/h(x)$ over an algebraically closed field of odd (or zero)
characteristic are equivalent. Over a finite field $\mathbb{F}_{q}$ of odd
characteristic they split into two equivalence classes. However, the rational
expressions in either class happen to give the same enumeration formula for
the irreducible polynomials $F(x)$ obtained from the corresponding
transformations. Incidentally, because in odd characteristic the quadratic
rational expression $(x^{2}+1)/x$ is equivalent to $x^{2}$, that enumeration
formula also counts the number of irreducible polynomial of the form
$f(x^{2})$ over the field $\mathbb{F}_{q}$ with $q$ odd, which is a very
special case of a result of Cohen [Coh69, Theorem 3].

These results motivate an investigation of irreducible polynomials obtained
from a transformation of higher degree, that is, of the form $f_{R}(x)$ where
$R(x)=g(x)/h(x)$ a rational expression of arbitrary degree $r$. The special
case where $g(x)=1$ is of particular relevance for practical applications
because of its direct connection with transformation shift registers (TSRs),
see [CHPW15, Section 3].

In this paper we study the case of cubic transformations. Given coprime
polynomials $g(x),h(x)\in\mathbb{F}_{q}[x]$, following notation in [CHPW15] we
let $\mathcal{I}(g,h,n,q)$ denote the set of monic irreducible polynomials
$f(x)\in\mathbb{F}_{q}[x]$ of degree $n>1$ such that $f_{R}(x)$ is irreducible
in $\mathbb{F}_{q}[x]$. In Section 3 we extend the method used in [Ahm11] for
quadratic transformations, to a general procedure for computing the
cardinality of $\mathcal{I}(g,h,n,q)$ when $R(x)=g(x)/h(x)$ is an arbitrary
cubic rational expression over $\mathbb{F}_{q}$.

Because the procedure of Section 3 involves the number of
$\mathbb{F}_{q}$-rational points of a certain cubic or quartic affine plane
curve over $\mathbb{F}_{q}$ associated with the rational expression $R(x)$, it
is not possible to obtain a general explicit formula for
$|\mathcal{I}(g,h,n,q)|$, covering all cases. This is in contrast with the
case of quadratic transformations as studied in [Ahm11, MP17]. However, we
find explicit formulas in all cases where that is possible, which include
those arising from TSRs.

Because $|\mathcal{I}(g,h,n,q)|$ is unaffected by replacing $R(x)=g(x)/h(x)$
with an equivalent rational expression, as we show in Section 2, it is useful
to have a classification, or at least a partial classification, up to
equivalence, of cubic rational maps over a finite field. Such a classification
is produced in the paper [MP], at least for cubic rational expressions having
at most three ramification points (over the algebraic closure
$\overline{\mathbb{F}}_{q}$). We quote it here as Theorem 3 for characteristic
at least five, where it provides nice representatives for the resulting four
equivalence classes of cubic rational expressions. In Section 4 we find
explicit formulas for $|\mathcal{I}(g,h,n,q)|$ in case $R(x)=g(x)/h(x)$ equals
one of those four representatives. When $R(x)$ has four ramification points
the cubic or quartic curve mentioned above is irreducible of genus one, so we
must content ourselves with an estimate, coming from the Hasse-Weil bound,
which we state in Theorem 14.

A classification of cubic rational expressions up to equivalence is different
in characteristic three or two, and we quote the corresponding results from
[MP] as Theorems 15 and 18. In Sections 5 and 6 we compute
$|\mathcal{I}(g,h,n,q)|$ in those cases. Note that in the case of
characteristic two, which is likely the most important for applications, no
cubic rational expression can have more than three ramification points, hence
Theorem 18 provides a classification of all cubic rational expressions. Still,
a curve of genus one arises in some of the equivalence classes, leading again
to an estimate in those cases rather than an explicit formula.

In the final Section 7 we apply our results to obtain an alternate derivation
of the formulas for the number of irreducible TSRs of order three over
$\mathbb{F}_{q^{m}}$, originally obtained by Jiang and Yang in [JY17].

The research leading to this paper began when the second author was a PhD
student at the University of Trento, Italy, under the supervision of the first
author. Part of these results have appeared among other results in [Piz13].

##  2\. Rational expressions and associated polynomial transformations

Consider a rational expression $R(x)=g(x)/h(x)\in K(x)$, over a field $K$,
where $g(x)$ are $h(x)$ coprime polynomials in $K[x]$. Its degree $\deg R$ is
$\max(\deg g,\deg h)$; the expression will be called linear, quadratic, cubic,
when its degree equals $1,2,3$. It is easy to see that the degree of the
composite of two rational expressions equals the product of their degrees. The
linear rational expressions (which also go by various other names, such as
fractional linear transformations, or Möbius transformations) form a group,
usually called the Möbius group over $K$.

To a rational expression $R(x)$ over the field $K$ we associate a
transformation of polynomials in $K[x]$, which sends (zero to zero if we like,
and) a nonzero polynomial $f(x)$ to the polynomial $f_{R}(x):=h(x)^{\deg
f}\cdot f\bigl{(}g(x)/h(x)\bigr{)}$. Thus, the transformation is given by the
substitution $x\mapsto R(x)$ into $f(x)$, followed with multiplication by the
least power of $h(x)$ required to clear denominators and ensure that
$f_{R}(x)$ is actually a polynomial. Note that $f_{R}(x)$ changes by a nonzero
scalar factor if we rewrite $R(x)=g(x)/h(x)$ in an equivalent form
$\bigl{(}ag(x)\bigr{)}/\bigl{(}ah(x)\bigr{)}$. Hence, strictly speaking,
$f_{R}(x)$ depends on $g(x)$ and $h(x)$ rather than just their quotient
$R(x)$, but we will abuse notation and assume that we have fixed a
representation of $R(x)$ as $g(x)/h(x)$ when using the notation $f_{R}(x)$.

For a rational expression $R(x)$ of arbitrary degree $r$ we clearly have $\deg
f_{R}\leq r\deg f$, but equality need not always hold.

######  Lemma 1.

Let $R(x)=g(x)/h(x)$ be a rational expression of degree $r\geq 1$ over $K$,
and write $g(x)=\sum_{i}g_{i}x^{i}$ and $h(x)=\sum_{i}h_{i}x^{i}$. Then

  * (a)

$\deg f_{R}=r\deg f$ unless $h_{r}\neq 0$ and $f(g_{r}/h_{r})=0$;

  * (b)

$\deg f_{R}=0$ if and only if $h_{r}g(x)-g_{r}h(x)$ is a constant and $f(x)$
is a scalar multiple of a power of $h_{r}x-g_{r}$.

###### Proof.

Writing $f(x)=\sum_{i}f_{i}x^{i}$ and $n=\deg f$, we see that the polynomial
$f_{R}(x)=\sum_{i}f_{i}\,g(x)^{i}\,h(x)^{n-i}$ has degree at most $rn$, and
the coefficient of $x^{rn}$ in it equals
$\sum_{i}f_{i}\,g_{r}^{i}\,h_{r}^{n-i}=h_{r}^{n}\,f(g_{r}/h_{r})$. Assertion
(a) follows.

Regarding Assertion (b), if $f(x)=(h_{r}x-g_{r})^{n}$ then
$f_{R}(x)=\bigl{(}h_{r}g(x)-g_{r}h(x)\bigl{)}^{n}$, and this is a (nonzero)
constant if $h_{r}g(x)-g_{r}h(x)$ is. To prove the converse implication, we
may assume $h_{r}\neq 0$ because of Assertion (a). It is also enough to prove
the statement with $R(x)$ replaced by
$\tilde{R}(x)=\tilde{g}(x)/h(x)=R(x)-g_{r}/h_{r}$, whence
$h_{r}\tilde{g}(x)=h_{r}g(x)-g_{r}h(x)$ has degree less than the degree of
$h(x)$. Thus, suppose $\deg f_{\tilde{R}}=0$, that is,
$f_{\tilde{R}}(x)=f_{R}(x-g_{r}/h_{r})$ is a nonzero constant. Writing
$\tilde{g}(x)=\sum_{i}\tilde{g}_{i}x^{i}$, if $x^{m}$ is the highest power of
$x$ which divides $f(x)$, then the term $f_{m}\,\tilde{g}(x)^{m}\,h(x)^{n-m}$
has higher degree than each other term in the sum
$f_{\tilde{R}}(x)=\sum_{i}f_{i}\,\tilde{g}(x)^{i}\,h(x)^{n-i}$. This forces
$m=n$, and then $f_{n}\tilde{g}(x)^{n}=1$ implies that $\tilde{g}(x)$ is a
constant, as desired. ∎

With natural projective interpretation, Assertion (a) of Lemma 1 says that the
drop in degree $\deg f_{R}<r\deg f$ occurs when the value of $R(x)$ at
$\infty$ is a root of $f(x)$. In particular, this cannot occur when $f$ is
irreducible and $\deg f>1$. Furthermore, because in general
$f_{R}(x)=u_{R}(x)\,v_{R}(x)$ if $f(x)=u(x)\,v(x)$, Assertion (b) of Lemma 1
shows that $f_{R}(x)$ cannot be irreducible unless $f(x)$ is irreducible or,
only in case $h_{r}g(x)-g_{r}h(x)$ is a constant, $f(x)$ is the product of an
irreducible polynomial $u(x)$ and a power of $h_{r}x-g_{r}$. Because in the
latter case we have $f_{R}(x)=u_{R}(x)$, it is harmless to assume $f(x)$ to be
irreducible when studying irreducible polynomials of the form $f_{R}(x)$.

Following notation in [CHPW15] we let $\mathcal{I}(g,h,n,q)$ denote the set of
monic irreducible polynomials $f(x)\in\mathbb{F}_{q}[x]$ of degree $n>1$ such
that $f_{R}(x)$ is irreducible in $\mathbb{F}_{q}[x]$. The possibility of
$n=1$ is deliberately excluded from the notation because this case in
uninteresting and its inclusion would create tedious case distinctions. The
following result shows that our goal of counting irreducible polynomials of
the form $f_{R}(x)$ is not affected by composing $g(x)/h(x)$ with Möbius
transformations on either side.

######  Lemma 2.

Let $R(x)=g(x)/h(x)$ be a rational expression of degree $r\geq 1$ over
$\mathbb{F}_{q}$. Let $A(x)$ and $B(x)$ be linear rational expressions over
$\mathbb{F}_{q}$, and write $(B\circ R\circ
A)(x)=\tilde{R}(x)=\tilde{g}(x)/\tilde{h}(x)$. Then for $n>1$ we have

$|\mathcal{I}(\tilde{g},\tilde{h},n,q)|=|\mathcal{I}(g,h,n,q)|.$

###### Proof.

Because of our restriction $n>1$, according to Lemma 1 we have $\deg
f_{R}=r\deg f=rn$ for every irreducible polynomial $f(x)\in K[x]$ of degree
$n$.

Since the Möbius group is generated (under composition) by the expressions
$ax+b$, with $a\in\mathbb{F}_{q}^{\ast}$ and $b\in\mathbb{F}_{q}$, and
$x\mapsto 1/x$, in order to prove Lemma 2 it suffices to show that its
conclusion holds in the special cases where one of $A(x)$ and $B(x)$ is one of
those special expressions, and the other is $x$ (the identity of the Möbius
group).

When $A(x)=ax+b$ and $B(x)=x$, the polynomial $f_{\tilde{R}}(x)=f_{R}(ax+b)$
is clearly irreducible if and only if $f_{R}(x)$ is. Hence in this case we
have $\mathcal{I}(\tilde{g},\tilde{h},n,q)=\mathcal{I}(g,h,n,q)$.

When $A(x)=1/x$ and $B(x)=x$, up to scalar factors we may take
$\tilde{g}(x)=x^{r}g(1/x)$ and $\tilde{h}(x)=x^{r}h(1/x)$, whence

$f_{\tilde{R}}(x)=\bigl{(}x^{r}h(1/x)\bigr{)}^{\deg f}\cdot
f\bigl{(}g(1/x)/h(1/x)\bigr{)}.$

Because $\deg f_{R}=r\deg f$ this equals the reciprocal polynomial $x^{\deg
f_{R}}f_{R}(1/x)$ of $f_{R}(x)$, which is irreducible if and only $f_{R}(x)$
is. Once again we find
$\mathcal{I}(\tilde{g},\tilde{h},n,q)=\mathcal{I}(g,h,n,q)$.

If $B(x)$ does not equal a scalar multiple of $x$, the sets
$\mathcal{I}(\tilde{g},\tilde{h},n,q)$ and $\mathcal{I}(g,h,n,q)$ are
generally different, because the irreducibility of $f_{\tilde{R}}(x)$ does not
directly relate to the irreducibility of $f_{R}(x)$.

However, when $A(x)=x$ and $B(x)=ax+b$, whence $\tilde{R}(x)=ag(x)/h(x)+b$,
the map $f(x)\mapsto\tilde{f}(x)=f(ax+b)$ is a degree-preserving bijection
from the set of irreducible polynomials $f(x)$ such that $f_{\tilde{R}}(x)$ is
irreducible, onto the set of irreducible polynomials $\tilde{f}$ such that
$\tilde{f}_{R}(x)$ is irreducible, because
$f_{\tilde{R}}(x)=\tilde{f}_{R}(x)$. In particular, the map
$f(x)\mapsto\tilde{f}(x)=a^{-\deg f}f(ax+b)$ gives a bijection from
$\mathcal{I}(\tilde{g},\tilde{h},n,q)$ onto $\mathcal{I}(g,h,n,q)$.

Similarly, when $A(x)=x$ and $B(x)=1/x$, whence $\tilde{R}(x)=h(x)/g(x)$, the
map $f(x)\mapsto\tilde{f}(x)=x^{\deg f}f(1/x)$ is a degree-preserving
bijection from the set of irreducible polynomials $f$ with $\deg f>1$ such
that $f_{\tilde{R}}(x)$ is irreducible, onto the set of irreducible
polynomials $\tilde{f}$ with $\deg\tilde{f}>1$ such that $\tilde{f}_{R}(x)$ is
irreducible, again because $f_{\tilde{R}}(x)=\tilde{f}_{R}(x)$. Here the
assumption $\deg f>1$ serves to exclude the exceptional case $f(x)=x$. As in
the previous case it follows that
$|\mathcal{I}(\tilde{g},\tilde{h},n,q)|=|\mathcal{I}(g,h,n,q)|$, and this
concludes the proof. ∎

According to Lemma 2, for the purpose of counting the irreducible polynomials
of the form $f_{R}(x)$ and a given degree over a finite field
$K=\mathbb{F}_{q}$, we may take advantage of any normalization which replaces
$R(x)$ with some $\tilde{R}(x)=(B\circ R\circ A)(x)$ having a simpler form.
Call two such $R(x)$ and $\tilde{R}(x)$ equivalent.

In [MP] we studied the equivalence classes of cubic rational expressions
$R(x)=g(x)/h(x)$ over a finite field, and gave representatives for those
equivalence classes of expressions having at most three ramification points
(over the algebraic closure $\overline{\mathbb{F}}_{q}$). For the purposes of
this paper, the ramification points of a rational expression $R(x)$ are the
zeroes of its derivative, which are the same as the zeroes of the polynomial
$g^{\prime}(x)h(x)-g(x)h^{\prime}(x)$, together with $\infty$ in case this
polynomial has degree less than $2\deg R-2$. In particular, a cubic rational
expression $R(x)$ has at most four ramification points.

######  Theorem 3 ([MP], Theorem 14).

Let $\mathbb{F}_{q}$ be a finite field of characteristic at least five, and
let $\sigma\in\mathbb{F}_{q}$ be a nonsquare. Then any cubic rational
expression $R(x)$ over $\mathbb{F}_{q}$ with at most three ramification points
(over $\overline{\mathbb{F}}_{q}$) is equivalent to either $x^{3}$, or
$(x^{3}+3\sigma x)/(3x^{2}+\sigma)$, or $x^{3}-3x$, or $x^{3}-3\sigma x$.

The expressions $x^{3}$ and $(x^{3}+3\sigma x)/(3x^{2}+\sigma)$ have two
ramification points ($0$ and $\infty$ in case of the former) and, in fact, are
equivalent over $\mathbb{F}_{q^{2}}$ (see the proof of [MP, Theorem 14]). The
expressions $x^{3}-3x$ and $x^{3}-3\sigma x$ have three ramification points.
The difficulties of extending the above classification up to equivalence to
cubic rational expressions with four ramification points are discussed in [MP,
Remark 15].

##  3\. A general procedure

In this section we describe a method to compute $|\mathcal{I}(g,h,n,q)|$ for a
given cubic transformation $R(x)=g(x)/h(x)$. We will use the following
standard fact, known as Capelli’s lemma, see [Coh69, Lemma 1] for a proof.

######  Lemma 4 (Capelli).

Let $f(x)\in\mathbb{F}_{q}[x]$ be an irreducible polynomial of degree $n$ and
let $g,h\in\mathbb{F}_{q}[x]$. Then $h(x)^{n}\cdot f\bigl{(}g(x)/h(x)\bigr{)}$
is irreducible in $\mathbb{F}_{q}[x]$ if and only if $g(x)-\beta h(x)$ is
irreducible in $\mathbb{F}_{q^{n}}[x]$, where $\beta\in\mathbb{F}_{q^{n}}$ is
any root of $P(x)$.

In what follows we assume, as we may after post-composing with a suitable
Möbius transformation, that $h(x)$ has degree less than three, and that $g(x)$
is monic. The main advantage of this assumption is that $g(x)-\beta h(x)$ is
then always a monic cubic polynomial, irrespectively of the value of $\beta$.

In essence we follow the method used by Ahmadi in [Ahm11] for quadratic
transformations, adjusting his notation to the present more complex cubic
setting. Let $\mathcal{T}(m,q)$ be the set of elements of $\mathbb{F}_{q^{m}}$
which do not belong to any proper subfield. In other words, $\mathcal{T}(m,q)$
consists of the elements of $\mathbb{F}_{q^{m}}$ which have degree $m$ over
$\mathbb{F}_{q}$. According to Lemma 4, we have
$|\mathcal{I}(g,h,n,q)|=|U(n,q)|/n$, where

$U(m,q)=\\{\beta\in\mathcal{T}(m,q):\text{$g(x)-\beta h(x)$ is irreducible
over $\mathbb{F}_{q^{m}}$}\\}.$

An application of Möbius inversion will reduce the calculation of $|U(n,q)|$
to finding the cardinalities of the larger sets

$\overline{U}(m,q)=\\{\beta\in\mathbb{F}_{q^{m}}:\text{$g(x)-\beta h(x)$ is
irreducible over $\mathbb{F}_{q^{m}}$}\\}.$

If $\beta\in\mathcal{T}(m,q)$ with $m$ a divisor of $n$ then
$\beta\in\overline{U}(n,q)$ precisely when $n/m$ is not a multiple of three
(otherwise $\mathbb{F}_{q^{n}}$ contains a cubic extension of
$\mathbb{F}_{q^{m}}$, where $g(x)-\beta h(x)$ has a root). Hence

$|\overline{U}(n,q)|=\sum_{d\mid n,\ 3\nmid d}|U(n/d,q)|,$

and Möbius inversion yields

(1) $|\mathcal{I}(g,h,n,q)|=\frac{1}{n}\sum_{d\mid n,\ 3\nmid
d}\mu(d)|\overline{U}(n/d,q)|.$

We now compute the cardinalities of the sets $|\overline{U}(n/d,q)|$.

######  Lemma 5.

We have $|\overline{U}(n,q)|=(2q^{n}+A-B-2C-2D)/3$, where

  * •

$A$ is the number of distinct roots of $h(x)$ in $\mathbb{F}_{q^{n}}$;

  * •

$B$ is the number of $\beta\in\mathbb{F}_{q^{n}}$ for which $g(x)-\beta h(x)$
has a double root and a simple root in $\mathbb{F}_{q^{n}}$;

  * •

$C$ is the number of $\beta\in\mathbb{F}_{q^{n}}$ for which $g(x)-\beta h(x)$
has a triple root in $\mathbb{F}_{q^{n}}$;

  * •

$D$ is the number of $\beta\in\mathbb{F}_{q^{n}}$ for which $g(x)-\beta h(x)$
has a quadratic irreducible factor in $\mathbb{F}_{q^{n}}[x]$.

###### Proof.

Because reducibility of a cubic polynomial over a field is equivalent to the
polynomial having a root in that field, we have
$|\overline{U}(n,q)|=q^{n}-|V(n,q)|$, where

$V(n,q)=\\{\beta\in\mathbb{F}_{q^{n}}:\text{$g(\gamma)=\beta h(\gamma)$ for
some $\gamma\in\mathbb{F}_{q^{n}}$}\\}.$

To compute $|V(n,q)|$ we perform a double counting on the set

$W(n,q)=\\{(\gamma,\beta)\in\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}:g(\gamma)=\beta
h(\gamma)\\}.$

Note that $g(x)$ and $h(x)$ have no common root because they are coprime. On
the one hand, for every $\gamma\in\mathbb{F}_{q^{n}}$ which is not a root of
$h(x)$ there is a unique $\beta\in\mathbb{F}_{q^{n}}$ such that
$g(\gamma)=\beta h(\gamma)$. Hence $|W(n,q)|=q^{n}-A$, where $A$ is the number
of distinct roots of $h(x)$ in $\mathbb{F}_{q^{n}}$. On the other hand,
counting in terms of $\beta$ and according to the splitting pattern of
$g(x)-\beta h(x)$ we find

$|W(n,q)|=3|V(n,q)|-B-2C-2D.$

Comparing the two expressions for $|W(n,q)|$ yields the desired conclusion. ∎

To proceed further we need a convenient way of computing the quantities
involved in Lemma 5, especially $D$. The discriminant
$\Delta(\beta)=\operatorname{Disc}_{x}\bigl{(}g(x)-\beta h(x)\bigr{)}$ will
help to distinguish between the various factorization patterns of the cubic
polynomial $g(x)-\beta h(x)$ as $\beta$ varies. In particular, $\Delta(\beta)$
vanishes precisely when $g(x)-\beta h(x)$ has a multiple root. Because a
multiple root for a cubic polynomial necessarily lies in the field of
coefficients, $B+C$ equals the number of $\beta\in\mathbb{F}_{q^{n}}$ for
which $\Delta(\beta)=0$. Note that $\Delta(\beta)$ has degree at most four,
and its roots are the finite branch points of the rational expression $R(x)$.

When $g(x)-\beta h(x)$ is separable, in the modern meaning of having distinct
roots in a splitting field, information on its factorization is provided by
its Galois group. We view that as a group of permutations of the roots
(induced by automorphism of the splitting field), hence as a subgroup of the
symmetric group $S_{n}$ once the roots have been arbitrarily numbered. In
characteristic different from two we have the following classical discriminant
criterion.

######  Theorem 6.

A separable polynomial of degree $n$, over a field $K$ of characteristic not
two, has Galois group over $K$ contained in the alternating group $A_{n}$ if
and only if its discriminant is a square in $K$.

For cubic polynomials the following substitute is available, which avoids the
restriction on the characteristic.

######  Theorem 7.

A separable cubic polynomial $x^{3}+ax^{2}+bx+c$, over an arbitrary field $K$,
has Galois group over $K$ contained in the alternating group $A_{3}$ if and
only if its quadratic resolvent

$x^{2}+(ab-3c)x+(a^{3}c+b^{3}+9c^{2}-6abc)$

is reducible over $K$.

This was given as an exercise in [Kap69, page 53], stated there in the special
case where $a=0$. Full details may be found in Keith Conrad’s unpublished
expository paper [Con, Theorem 2.3]. The essence of a proof is that, if
$x_{1},x_{2},x_{3}$ are the roots of $x^{3}+ax^{2}+bx+c$ in a splitting field,
ordered in some arbitrary way, then the roots of the quadratic resolvent are
$\sum_{i=1}^{3}x_{i}^{2}x_{i\pm 1}$, with indices viewed modulo $3$, and those
are interchanged by odd permutations of $x_{1},x_{2},x_{3}$. Because the
quadratic resolvent turns out to have the same discriminant as the cubic
polynomial, this criterion leads back to the more familiar discriminant
criterion when the characteristic of the field is different from two.

######  Lemma 8.

We have $|\overline{U}(n,q)|=(N+A-C)/3$, where $A$ and $C$ are as in Lemma 5,
and

  * •

$N$ is the number of solutions in $\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$
of the equation $x^{2}+s(\beta)x+t(\beta)=0$ (in the unknowns $x$ and
$\beta$), where the left-hand side is the quadratic resolvent of $g(x)-\beta
h(x)$.

If $q$ is odd, then

  * •

$N$ is the number of solutions in $\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$
of the equation $y^{2}-\Delta(\beta)=0$ (in the unknowns $y$ and $\beta$),
where $\Delta(\beta)=\operatorname{Disc}_{x}\bigl{(}g(x)-\beta h(x)\bigr{)}$.

###### Proof.

We have already noted that $B+C$ equals the number of
$\beta\in\mathbb{F}_{q^{n}}$ for which $\Delta(\beta)=0$, which is equivalent
to the quadratic resolvent having a double root in $\mathbb{F}_{q^{n}}$.

Now consider those $\beta\in\mathbb{F}_{q^{n}}$ which are not roots of the
discriminant, whence both $g(x)-\beta h(x)$ and its quadratic resolvent are
separable. According to Theorem 7, the quadratic resolvent is irreducible over
$\mathbb{F}_{q^{n}}$ if and only if the Galois group of $g(x)-\beta h(x)$ over
$\mathbb{F}_{q^{n}}$ is not contained in the alternating group $A_{3}$.
Because Galois groups over a finite field are cyclic (hence the whole $S_{3}$
cannot be a Galois group), this occurs precisely when the Galois group is a
cyclic group of order two, interchanging two of the roots and fixing the third
root. Hence this is equivalent with $g(x)-\beta h(x)$ having a quadratic
irreducible factor in $\mathbb{F}_{q^{n}}[x]$. Therefore, $D$ equals the
number of $\beta\in\mathbb{F}_{q^{n}}$ for which the quadratic resolvent is
irreducible over $\mathbb{F}_{q^{n}}$, and hence has no roots in it.

As a consequence, the remaining case, where the quadratic resolvent has two
distinct roots in $\mathbb{F}_{q^{n}}$, occurs for precisely $q^{n}-B-C-D$
values of $\beta\in\mathbb{F}_{q^{n}}$.

Altogether, we find $N=(B+C)+2(q^{n}-B-C-D)=2q^{n}-B-C-2D$, and combining this
with Lemma 5 proves the first assertion.

The second assertion, for odd $q$, is a consequence of the former because the
equation $y^{2}-\Delta(\beta)=0$ is equivalent to the equation involving the
quadratic resultant via the substitution $x=y+s(\beta)/2$. ∎

In the rest of the paper we will apply the method described in this section to
compute $|\mathcal{I}(g,h,n,q)|$ in various cases, thus applying Lemma 8
followed by Möbius inversion as in Equation (1). The equation
$x^{2}+s(\beta)x+t(\beta)=0$ of Lemma 8, considered over the algebraic closure
$\overline{\mathbb{F}}_{q}$, represents an algebraic curve of degree at most
four. In various instances it will be possible to count the number of
$\mathbb{F}_{q^{n}}$-rational points of the curve explicitly. When interested
only in odd characteristic we will use the simpler equation
$y^{2}-\Delta(\beta)=0$ of Lemma 8.

Because of the final appeal to Möbius inversion, our results will generally
acquire a more compact appearance when expressed in terms of the function

(2) $I(n,q)=\frac{1}{n}\sum_{d\mid n}\mu(d)q^{n/d},$

which counts the number of irreducible monic polynomials of degree $n$ in
$\mathbb{F}_{q}[x]$, for any positive integer $n$. For $m$ a (positive)
divisor of $n$ we have

$\frac{1}{n}\sum_{md\mid n}\mu(d)q^{n/d}=\frac{1}{m}I(n/m,q^{m}).$

This remains valid even when $m$ does not divide $n$ if we stipulate that
$I(n,q)$ should take the value zero whenever $n$ is not a positive integer. In
particular, writing $n_{3}$ for the largest power of $3$ which divides $n$, in
applications of Equation (1) we will take advantage of expressing our results
in terms of the function $I(n^{\prime},q^{\prime})$ using

(3) $\frac{1}{n}\sum_{d\mid n,\ 3\nmid
d}\mu(d)q^{n/d}=\frac{1}{n}\sum_{n_{3}d\mid
n}\mu(d)q^{n/d}=\frac{1}{n_{3}}I(n/n_{3},q^{n_{3}}).$

To avoid several case distinctions in our results, we will allow ourselves to
use the expression for $I(n,q)$ given in Equation (2), which is formally a
polynomial in $q$, for values of $q$ which are not prime powers,
irrespectively of the lack of combinatorial interpretation. In particular,
$I(n,1)$ vanishes unless $n=1$, in which case $I(1,1)=1$. We will also need
$I(n,-1)$, which vanishes except when $n\leq 2$, in which cases $I(1,-1)=-1$
and $I(2,-1)=2$.

In some of our proofs it will be useful to consider $I(n,-q)$, but then

(4) $\displaystyle I(n,q)+I(n,-q)$ $\displaystyle=\frac{1}{n}\sum_{d\mid
n}\mu(d)\bigl{(}1+(-1)^{n/d}\bigr{)}q^{n/d}$
$\displaystyle=\frac{2}{n}\sum_{2d\mid n}\mu(d)(q^{2})^{n/2d}=I(n/2,q^{2}),$

to be read as zero when $n$ is odd according to our convention.

##  4\. Counting polynomials in large characteristics

In this section we will use Lemma 8 to compute $|\mathcal{I}(g,h,n,q)|$ for
any cubic rational expression $R(x)=g(x)/h(x)$ over $\mathbb{F}_{q}$ having at
most three ramification points. According to Lemma 2 it suffices to do that
for the representatives of equivalence classes of such expressions $R(x)$
given in Theorem 3 for characteristic at least five. However, we will cover
smaller characteristics as well in this section when possible and convenient.

The case of $R(x)=x^{3}$ is a special case of a result of Cohen in [Coh69,
Theorem 3], who counted irreducible polynomials of the form $f(x^{r})$. For
completeness we provide a proof of this special case of Cohen’s result, as a
first illustration of our method described in Section 3. Over a finite field
$\mathbb{F}_{q}$ of characteristic three any polynomial $f(x^{3})$ is the cube
of a polynomial, hence is reducible, and so $\mathcal{I}(x^{3},1,n,q)$ is
empty in this case.

######  Theorem 9.

If $q\equiv 1\pmod{3}$, then

$|\mathcal{I}(x^{3},1,n,q)|=\frac{2}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})-I(n/n_{3},1)\bigr{)}.$

If $q\equiv-1\pmod{3}$, then

$|\mathcal{I}(x^{3},1,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/2n_{3},q^{2n_{3}})-I(n/2n_{3},1)\bigr{)}.$

###### Proof.

We prepare for an application of Lemma 8, in the form with the quadratic
resolvent, as that allows characteristic two as well. We have $A=0$ because
$h(x)=1$ has no roots, and $C=1$ because $x^{3}-\beta$ has a triple root only
when $\beta=0$ (as the characteristic is not three here).

The quantity $N$ equals the number of solutions in
$\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation $x^{2}+3\beta
x+9\beta^{2}=0$, where the left-hand side is the quadratic resolvent of
$x^{3}-\beta$. The equation represents a singular conic, consisting of two
lines through the origin, which are defined over $\mathbb{F}_{q^{n}}$ if and
only if $q^{n}\equiv 1\pmod{3}$. Hence we have $N=2q^{n}-1$ if $q^{n}\equiv
1\pmod{3}$, and $N=1$ if $q^{n}\equiv-1\pmod{3}$.

Hence according to Lemma 8 we have $|\overline{U}(n,q)|=2(q^{n}-1)/3$ if
$q^{n}\equiv 1\pmod{3}$, and $|\overline{U}(n,q)|=0$ otherwise. Both cases can
be stated together as

$|\overline{U}(n,q)|=\bigl{(}q^{n}+(\varepsilon
q)^{n}-1-\varepsilon^{n}\bigr{)}/3,$

using the Legendre symbol $\varepsilon=\left(\frac{q}{3}\right)$, hence
$\varepsilon=\pm 1$ according to whether $q\equiv\pm 1\pmod{3}$. Möbius
inversion as given in Equation (1) now yields

(5) $\displaystyle|\mathcal{I}$
$\displaystyle(x^{3},1,n,q)|=\frac{1}{3n}\sum_{d\mid n,\ 3\nmid
d}\mu(d)\bigl{(}q^{n/d}+(\varepsilon q)^{n/d}-1-\varepsilon^{n/d}\bigr{)}.$
$\displaystyle=\frac{1}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})+I(n/n_{3},\varepsilon
q^{n_{3}})-I(n/n_{3},1)-I(n/n_{3},\varepsilon)\bigr{)},$

where we have used Equation (3) to get the final expression. The desired
conclusions follow, using Equation (4) in case $q\equiv-1\pmod{3}$. ∎

######  Remark 10.

The results of Theorem 9 can be stated together as

$|\mathcal{I}(x^{3},1,n,q)|=\frac{2}{3kn_{3}}\bigl{(}I(n/kn_{3},q^{kn_{3}})-I(n/kn_{3},1)\bigr{)},$

where $k$ be the smallest positive integer such that $3\mid q^{k}-1$, hence
$k\in\\{1,2\\}$ and $k\equiv q\pmod{3}$. This statement is more akin to the
statement for the general case of $x^{r}$ given in [Coh69, Theorem 3].

According to Theorem 3, any cubic rational expression $R(x)$, over
$\mathbb{F}_{q}$ of characteristic at least five, having only two ramification
points (over $\overline{\mathbb{F}}_{q}$) is equivalent to either $x^{3}$, or
$(x^{3}+3\sigma x)/(3x^{2}+\sigma)$, where $\sigma$ is any nonsquare in
$\mathbb{F}_{q}$. The following result deals with the latter case.

######  Theorem 11.

Let $\mathbb{F}_{q}$ have characteristic at least five, and let
$\sigma\in\mathbb{F}_{q}$ be a nonsquare. If $q\equiv 1\pmod{3}$, then

$|\mathcal{I}(x^{3}+3\sigma
x,3x^{2}+\sigma,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/2n_{3},q^{2n_{3}})-I(n/2n_{3},1)\bigr{)}.$

If $q\equiv-1\pmod{3}$, then

$|\mathcal{I}(x^{3}+3\sigma
x,3x^{2}+\sigma,n,q)|=\frac{2}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})-I(n/n_{3},-1)\bigr{)}.$

###### Proof.

The polynomial $(x^{3}+3\sigma x)-\beta(3x^{2}+\sigma)$ has quadratic
resolvent $x^{2}-6\beta\sigma
x+9\sigma(3\beta^{4}-5\sigma\beta^{2}+3\sigma^{2})$, but because the
characteristic is odd it will be more convenient to work directly with its
discriminant $\Delta(\beta)=-108\sigma(\beta^{2}-\sigma)^{2}$, and apply Lemma
8 in its second formulation.

The number $A$ of roots of $3x^{2}+\sigma$ in $\mathbb{F}_{q^{n}}$ is given by
$A=1+(-\varepsilon)^{n}$, in terms of the Legendre symbol
$\varepsilon=\left(\frac{q}{3}\right)$. Because the polynomial $(x^{3}+3\sigma
x)-\beta(3x^{2}+\sigma)$ (as a polynomial in $x$, for a given value of
$\beta$) has a triple root in $\mathbb{F}_{q^{n}}$ if and only if
$\beta^{2}=\sigma$, we have $C=1+(-1)^{n}$.

The number $N$ of solutions in $\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of
the quartic equation $y^{2}+108\sigma(\beta^{2}-\sigma)^{2}=0$ can be computed
by assigning values for $\beta$ in $\mathbb{F}_{q^{n}}$ and then solving for
$y$. For a given value of $\beta$, the equation has one solution if
$\beta^{2}=\sigma$, and $1+(-\varepsilon)^{n}$ solutions otherwise. Hence
$N=2+(q^{n}-2)\bigl{(}1+(-\varepsilon)^{n}\bigr{)}$ if $n$ is even, and
$N=q^{n}\bigl{(}1+(-\varepsilon)^{n}\bigr{)}$ if $n$ is odd. In a single
formula, $N=q^{n}+(-\varepsilon q)^{n}-(-\varepsilon)^{n}-\varepsilon^{n}$.

According to Lemma 8 we find

$|\overline{U}(n,q)|=\bigl{(}q^{n}+(-\varepsilon
q)^{n}-(-1)^{n}-\varepsilon^{n}\bigr{)}/3.$

Applying Möbius inversion as in Equation (1), and then Equation (3), we find

$\displaystyle|\mathcal{I}$ $\displaystyle(x^{3}+3\sigma
x,3x^{2}+\sigma,n,q)|$
$\displaystyle=\frac{1}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})+I(n/n_{3},-\varepsilon
q^{n_{3}})-I(n/n_{3},-1)-I(n/n_{3},\varepsilon)\bigr{)}.$

The desired conclusions follow, using Equation (4) in case $q\equiv
1\pmod{3}$. ∎

Note that if $\sigma$ is a nonzero square in $\mathbb{F}_{q}$ (for example
$\sigma=1$), rather than a nonsquare, then $|\mathcal{I}(x^{3}+3\sigma
x,3x^{2}+\sigma,n,q)|=|\mathcal{I}(x^{3},1,n,q)|$, because then the cubic
rational expression $(x^{3}+3\sigma x)/(3x^{2}+\sigma)$ is equivalent to
$x^{3}$ over $\mathbb{F}_{q}$. This suggests an alternate way of recovering
Theorem 9 (for odd $q$), by adapting the above proof to $\sigma$ a nonzero
square in $\mathbb{F}_{q}$ instead of a nonsquare.

######  Remark 12.

According to Theorem 9, the set $\mathcal{I}(x^{3},1,n,q)$ is empty if
$q^{n}\equiv-1\pmod{3}$. A more direct reason is that $f(x^{3})$ cannot be
irreducible in that case because $x^{3}$ induces a permutation of
$\mathbb{F}_{q^{n}}$, which of course commutes with the map
$\alpha\mapsto\alpha^{q}$. Consequently, writing
$f(x)=(x-\alpha)(x-\alpha^{q})\cdots(x-\alpha^{q^{n-1}})$ for some
$\alpha\in\mathbb{F}_{q^{n}}$, the polynomial
$(x-\beta)(x-\beta^{q})\cdots(x-\beta^{q^{n-1}})$, is a factor of $f(x^{3})$,
where $\beta$ is the unique cubic root of $\alpha$ in $\mathbb{F}_{q^{n}}$.
Here we may even be more explicit, as $\beta=\alpha^{(2q^{n}-1)/3}$.

Similarly, according to Theorem 11 the set $\mathcal{I}(x^{3}+3\sigma
x,3x^{2}+\sigma,n,q)$ is empty if $q\equiv 1\pmod{3}$ and $n$ is odd. This can
also be explained directly noting that under those conditions the expression
$R(x)=(x^{3}+3\sigma x)/(3x^{2}+\sigma)$ induces a permutation of
$\mathbb{F}_{q^{n}}$, as can be seen by solving the equation $R(x)=R(y)$ and
finding that for $x\neq y$ it is equivalent to
$-3(xy-\sigma)^{2}=\sigma(x-y)^{2}$. Consequently, one of the factors of
$f_{R}(x)$ over $\mathbb{F}_{q}$, with $f(x)$ as before, has a root
$\gamma\in\mathbb{F}_{q^{n}}$ determined by $R(\gamma)=\alpha$.

Now we turn our attention to cubic rational expressions $R(x)$ with three
ramification points. According to Theorem 3 those are equivalent to either
$x^{3}-3x$ or $x^{3}-3\sigma x$, where $\sigma$ is a nonsquare in
$\mathbb{F}_{q}$. However, this distinction will actually be immaterial for
our count of irreducible polynomials, and so we will treat both cases
together. The special case of the following result where $R(x)=x^{3}-3x$ is
[Chu96, Theorem 4].

######  Theorem 13.

Let $\mathbb{F}_{q}$ have characteristic at least five, and let $\tau$ be a
nonzero element of $\mathbb{F}_{q}$. Then

$|\mathcal{I}(x^{3}-\tau
x,1,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})-I(n/n_{3},\varepsilon)\bigr{)}.$

where $\varepsilon=\left(\frac{q}{3}\right)$ is a Legendre symbol.

###### Proof.

Because the characteristic is odd we will apply Lemma 8 in the form with the
discriminant, which in case of the polynomial $x^{3}-\tau x-\beta$ is
$\Delta(\beta)=4\tau^{3}-27\beta^{2}$. Both quantities $A$ and $C$ vanish
here, and it remains to compute the number $N$ of solutions in
$\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation
$y^{2}+27\beta^{2}-4\tau^{3}=0$ (in the unknowns $y$ and $\beta$). Because
this represents a non-singular conic, it will have precisely $q^{n}+1$ points
in the projective plane over $\mathbb{F}_{q^{n}}$, and subtracting the
$1+\varepsilon^{n}$ points at infinity we find $N=q^{n}-\varepsilon^{n}$.
Hence

$|\overline{U}(n,q)|=\frac{q^{n}-\varepsilon^{n}}{3},$

and the conclusion follows after Möbius inversion. ∎

For cubic rational expressions $R(x)=g(x)/h(x)$ with four rational points we
can only produce an estimate for $|\mathcal{I}(g,h,n,q)|$. This is because
$|\mathcal{I}(g,h,n,q)|$ turns out to depend on the number of
$\mathbb{F}_{q}$-rational points of a curve of genus one associated with
$R(x)$. Because a cubic rational expression $R(x)$ over a field of
characteristic two cannot have four ramification points (see [MP, Section 4],
for example), in the following result $\mathbb{F}_{q}$ has necessarily odd
characteristic.

######  Theorem 14.

Let $R(x)=g(x)/h(x)$ be a cubic rational expression over $\mathbb{F}_{q}$ with
four ramification points (over $\overline{\mathbb{F}}_{q}$). Then
$|\mathcal{I}(g,h,n,q)|=q^{n}/3n+O(q^{n/2}/n)$.

###### Proof.

An application of Lemma 8 involves the number $N$ of solutions in
$\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation
$y^{2}-\Delta(\beta)=0$. Recall that $\Delta(\beta)$ is a polynomial of degree
at most four, and that its roots are precisely the finite ramification points
of $R(x)$. If $\infty$ is a ramification point of $R(x)$, then $h(x)$ has
degree less than three, and then one sees that $\Delta(\beta)$ has degree at
most three. Because we are assuming that $R(x)$ has four ramification points,
$\Delta(\beta)$ is a cubic polynomial with distinct roots. However, if
$\infty$ is not a ramification point of $R(x)$, then $\Delta(\beta)$ is a
quartic polynomial with distinct roots.

Now consider the plane curve with affine equation $y^{2}=\Delta(\beta)$, which
is absolutely irreducible in either case. If $\Delta(\beta)$ has degree three,
then the projective version of the curve is a non-singular curve of genus one,
whose number of its $\mathbb{F}_{q^{n}}$-rational points equals $N+1$. The
Hasse-Weil bound then gives

$|N-q^{n}|\leq 2\sqrt{q^{n}}.$

Together with Equation (1) this yields
$|\mathcal{I}(g,h,n,q)|=q^{n}/3n+O(q^{n/2}/n)$, as desired.

If $\Delta(\beta)$ has degree four, then the projective version of the curve
has a singularity in the point at infinity. According to [AP96, Corollary 2.5]
we have the weaker bound

$|N-q^{n}|\leq 6\sqrt{q^{n}}.$

Here the coefficient $6$ results from having replaced the (geometric) genus of
the curve (which is still $1$ according to Plücker’s formula) with its
arithmetic genus (which is $(d-1)(d-2)/2=3$, where $d=4$ is the degree of the
curve). Together with Equation (1) this yields the same asymptotic estimate of
$|\mathcal{I}(g,h,n,q)|$. ∎

Because of the exact formulas of Theorem 13, $|\mathcal{I}(g,h,n,q)|$
satisfies the same estimate of Theorem 14 when $R(x)=g(x)/h(x)$ has three
ramification points. However, according to Theorems 9 and 11 the asymptotic
estimate becomes twice as large in case $R(x)$ has just two ramification
points.

##  5\. Results in characteristic three

A classification of cubic rational expressions $R(x)$ up to equivalence,
analogous to that of Theorem 3 but over a finite field of characteristic
three, was also obtained in [MP], under the same restriction that $R(x)$ has
at most three ramification points. It reads as follows.

######  Theorem 15 ([MP], Theorem 18).

Let $\mathbb{F}_{q}$ be a finite field of characteristic three, and let
$\sigma\in\mathbb{F}_{q}$ be a nonsquare. Then any cubic rational expression
$R(x)$ over $\mathbb{F}_{q}$ with at most three ramification points is
equivalent to either $x^{3}+x^{2}$, or $x^{3}+x$, or $x^{3}+\sigma x$.

The expression $x^{3}+x^{2}$ has two ramification points, namely, $\infty$
with index three and $0$ with index two. Every cubic rational expression, over
$\mathbb{F}_{q}$ of characteristic three, with precisely two ramification
points, is equivalent to $x^{3}+x^{2}$. Each of the expressions $x^{3}+x$ and
$x^{3}+\sigma x$ has $\infty$ as unique ramification point, with index three.
Every cubic rational expression, over $\mathbb{F}_{q}$ of characteristic
three, with precisely one ramification point, is equivalent to one of those.
Also, those two become equivalent to each other over $\mathbb{F}_{q^{2}}$.
Note that the assumption of having at most three ramification points in
Theorem 15 excludes the inseparable cubic rational expressions, which are
ramified everywhere. Those are easily seen to be all equivalent to $x^{3}$.

Now we apply the method of Section 5 to compute $|\mathcal{I}(g,h,n,q)|$ for
the various representatives of Theorem 15. As mentioned before Theorem 9, the
set $\mathcal{I}(x^{3},1,n,q)$ is empty when $q$ is a power of three. If
$R(x)$ has four distinct ramification points we generally only have the
estimate of Theorem 14, so it remains to cover the cases where $R(x)$ equals
$x^{3}+x^{2}$, or $x^{3}-x$, or $x^{3}-\sigma x$, where $\sigma$ is a
nonsquare in $\mathbb{F}_{q}$.

######  Theorem 16.

Over the field $\mathbb{F}_{q}$ of characteristic three we have

$|\mathcal{I}(x^{3}+x^{2},1,n,q)|=\frac{1}{3n_{3}}I(n/n_{3},q^{n_{3}}).$

###### Proof.

Both quantities $A$ and $C$ of Lemma 8 vanish, and the polynomial
$x^{3}+x^{2}-\beta$ has discriminant $\Delta(\beta)=\beta$. The number $N$ of
solutions in $\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation
$y^{2}-\beta=0$ equals $q^{n}$. Lemma 8 yields $|\overline{U}(n,q)|=q^{n}/3$,
and the conclusion follows by Möbius inversion as given by Equation (1). ∎

######  Theorem 17.

Let $\mathbb{F}_{q}$ have characteristic three, and let
$\sigma\in\mathbb{F}_{q}$ be a nonsquare. Then

$|\mathcal{I}(x^{3}-x,1,n,q)|=\frac{2}{3n_{3}}I(n/n_{3},q^{n_{3}}),$

and

$|\mathcal{I}(x^{3}-\sigma x,1,n,q)|=\frac{1}{3n_{3}}I(n/2n_{3},q^{2n_{3}}).$

###### Proof.

Both quantities $A$ and $C$ of Lemma 8 vanish. We may deal with both cases
together by taking $\tau\in\\{1,\sigma\\}$ (or $\tau$ any nonzero element of
$\mathbb{F}_{q}$). The polynomial $x^{3}-\tau x-\beta$ has discriminant
$\Delta(\beta)=\tau^{3}$, hence independent of $\beta$. The number $N$ of
solutions in $\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation
$y^{2}-\tau^{3}=0$ (in the unknowns $y$ and $\beta$, with the latter not
appearing) is given by $N=\bigl{(}1+\eta_{q}(\tau)^{n}\bigr{)}q^{n}$, where
$\eta_{q}$ is the quadratic character of $\mathbb{F}_{q}$. Hence

$|\overline{U}(n,q)|=\frac{q^{n}+\eta_{q}(\tau)^{n}q^{n}}{3}$

according to Lemma 8, and Möbius inversion yields

$|\mathcal{I}(x^{3}-\tau
x,1,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})+I(n/n_{3},\eta_{q}(\tau)q^{n_{3}})\bigr{)}.$

The desired conclusions follow, using Equation (4) in case $\tau=\sigma$. ∎

As in Remark 12, the fact that $\mathcal{I}(x^{3}-\sigma x,1,n,q)$ is empty
when $n$ is odd in Theorem 17 is also due to $x^{3}-\sigma x$ inducing a
permutation of $\mathbb{F}_{q^{n}}$ in that case.

##  6\. Results in characteristic two

A classification of cubic rational expressions over finite fields of
characteristic two, analogous to Theorem 3, was also obtained in [MP].
However, because no cubic rational expression in characteristic two can have
more than three ramification points (see [MP, Section 4]), in this case the
classification covers all cubic rational expressions, with no restriction.

######  Theorem 18 ([MP], Theorem 19).

Let $\mathbb{F}_{q}$ be a finite field of characteristic two, and let
$\sigma\in\mathbb{F}_{q}$ be an element of absolute trace $1$. If $q$ is a
square then let $\theta$ be a non-cube in $\mathbb{F}_{q}$. Then any cubic
rational expression $R(x)$ over $\mathbb{F}_{q}$ is equivalent to precisely
one of the following:

  * (i)

$x^{3}$, with ramification indices $(3,3)$;

  * (ii)

$\displaystyle\frac{x^{3}+\sigma x+\sigma}{x^{2}+x+\sigma+1}$, with
ramification indices $(3,3)$;

  * (iii)

$x^{3}+x^{2}$, with ramification indices $(3,2)$;

  * (iv)

$(x^{3}+1)/x$ or, only in case $q$ is a square, $(x^{3}+\theta)/x$ or
$(x^{3}+\theta^{2})/x$; all these have ramification indices $(2)$;

  * (v)

$(x^{3}+c)/(x+c)$, with ramification indices $(2,2)$, for a unique
$c\in\mathbb{F}_{q}\setminus\mathbb{F}_{2}$;

  * (vi)

$\displaystyle\frac{x^{3}+bx^{2}+\sigma x+(b+1)\sigma}{x^{2}+x+b+1+\sigma}$,
with ramification indices $(2,2)$, for a unique
$b\in\mathbb{F}_{q}\setminus\mathbb{F}_{2}$.

The cubic expressions of cases (i) and (ii) are equivalent over
$\mathbb{F}_{q^{2}}$. The expressions of case (vi) is equivalent to that of
case (v) with $c=1/b^{2}$. If $q$ is a square then the three expressions of
case (iv) become equivalent over $\mathbb{F}_{q^{3}}$. Thus, over the
algebraic closure $\overline{\mathbb{F}}_{q}$ the above six cases collapse to
three isolated cases and one parametric family, as in [MP, Theorem 10].

In this section we will apply the general method of Section 3 to the
calculation of $|\mathcal{I}(g,h,n,q)|$ in each case of Theorem 18. We will
find explicit formulas in cases (i), (ii), (iii), but only an estimate in the
remaining cases.

Case (i) is covered by Theorem 9. The following result deals with case (ii),
and produces exactly the same formulas as in Theorem 11.

######  Theorem 19.

Let $\mathbb{F}_{q}$ have characteristic two, and let
$\sigma\in\mathbb{F}_{q}$ have absolute trace $1$. If $q\equiv 1\pmod{3}$,
then

$|\mathcal{I}(x^{3}+\sigma
x+\sigma,x^{2}+x+\sigma+1,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/2n_{3},q^{2n_{3}})-I(n/2n_{3},1)\bigr{)}.$

If $q\equiv-1\pmod{3}$, then

$|\mathcal{I}(x^{3}+\sigma
x+\sigma,x^{2}+x+\sigma+1,n,q)|=\frac{2}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})-I(n/n_{3},-1)\bigr{)}.$

###### Proof.

We prepare for an application of Lemma 8 in the form with the quadratic
resolvent. The number $A$ of roots of $x^{2}+x+\sigma+1$ in
$\mathbb{F}_{q^{n}}$ equals $2$ or $0$ according to whether the absolute trace
of $\sigma+1$ as an element of $\mathbb{F}_{q^{n}}$ equals $0$ or $1$.
Consequently, we have $A=1+(-\varepsilon)^{n}$ in terms of the Legendre symbol
$\varepsilon=\left(\frac{q}{3}\right)$. The polynomial $g(x)-\beta
h(x)=x^{3}+\beta x^{2}+(\beta+\sigma)x+(\beta\sigma+\beta+\sigma)$, as a
polynomial in $x$, for a given value of $\beta$, has a triple root in
$\mathbb{F}_{q^{n}}$ if and only if $\beta^{2}+\beta=\sigma$. Hence we have
$C=1+(-1)^{n}$.

The quadratic resolvent of $g(x)-\beta h(x)$ is

$x^{2}+(\beta^{2}+\beta+\sigma)x+\bigl{(}(\sigma+1)\beta^{4}+(\sigma+1)\beta^{3}+(\sigma^{2}+\sigma+1)\beta^{2}+\sigma^{2}\beta+(\sigma^{3}+\sigma^{2})\bigr{)}.$

Over any extension of $\mathbb{F}_{q}$ containing an element $\rho$ with
$\rho^{2}+\rho=\sigma+1$, the quadratic resolvent factorizes as

$\bigl{(}x+\rho\beta^{2}+\rho^{2}\beta+(\rho^{3}+1)\bigr{)}\bigl{(}x+(\rho+1)\beta^{2}+(\rho^{2}+1)\beta+(\rho^{3}+\rho^{2}+\rho)\bigr{)}.$

Equating this to zero yields the equation of the union of two non-singular
conics, which meet in the points $(x,\beta)=(\tau^{3},\tau)$, where
$\tau^{2}+\tau=\sigma$ (hence $\tau$ is as in the proof of [MP, Theorem 19]),
and $(x,\beta)=((\tau+1)^{3},\tau+1)$. Because $\sigma$ is an element of
$\mathbb{F}_{q}$ with absolute trace $1$, the element $\tau$ belongs to
$\mathbb{F}_{q^{n}}$ if and only if $n$ is even.

Furthermore, $\rho$ belongs to $\mathbb{F}_{q^{n}}$ unless $\varepsilon=1$ and
$n$ is odd. If $\rho\in\mathbb{F}_{q^{n}}$, then the number of solutions in
$\mathbb{F}_{q^{n}}\times\mathbb{F}_{q^{n}}$ of the equation associated with
the quadratic resolvent is given by $N=2q^{n}-1-(-1)^{n}$, having taken into
account the possible intersections of the two (affine) conics. However, if
$\rho\not\in\mathbb{F}_{q^{n}}$, then the two conics are only defined over
$\mathbb{F}_{q^{2n}}$ and they are conjugate over $\mathbb{F}_{q^{n}}$.
Because their two intersection points described earlier do not have
coordinates in $\mathbb{F}_{q^{n}}$ in this case, we find $N=0$. In a single
formula encompassing all cases, we have $N=q^{n}+(-\varepsilon
q)^{n}-(-\varepsilon)^{n}-\varepsilon^{n}$.

Noting that $N$, $A$ and $C$ are given by identical expressions as in the
proof of Theorem 11, the conclusion follows exactly as in that proof. ∎

Once again, the fact that Theorem 19 reports no irreducible polynomials if
$q\equiv 1\pmod{3}$ and $n$ is odd can be explained as in Remark 12, because
$R(x)$ induces a permutation of $\mathbb{F}_{q^{n}}$ in that case.

The following result deals with case (iii) of Theorem 18.

######  Theorem 20.

If $q$ is a power of two, then

$|\mathcal{I}(x^{3}+x^{2},1,n,q)|=\frac{1}{3n_{3}}\bigl{(}I(n/n_{3},q^{n_{3}})-I(n/n_{3},\varepsilon)\bigr{)},$

where $\varepsilon=\left(\frac{q}{3}\right)$.

###### Proof.

Both quantities $A$ and $C$ of Lemma 8 vanish. The quadratic resolvent of
$x^{3}+x^{2}-\beta$ equals $x^{2}+\beta x+\beta^{2}+\beta$. Equating this
polynomial to zero yields the equation of a non-singular conic. Over
$\mathbb{F}_{q^{n}}$ the conic has $q^{n}+1$ projective points, of which
$1+\varepsilon^{n}$ points at infinity. Consequently,
$N=q^{n}-\varepsilon^{n}$, hence
$|\overline{U}(n,q)|=(q^{n}-\varepsilon^{n})/3$ according to Lemma 8, and the
conclusion follows by Möbius inversion as usual. ∎

In the remaining cases of Theorem 18, the method of Section 3 leads to
counting points on a certain curve of genus one, and hence we will only lead
to an estimate for $|\mathcal{I}(g,h,n,q)|$. We do that in the following
result, which is analogous to the case of $R(x)$ with four ramification points
in odd characteristic, Theorem 14.

######  Theorem 21.

Let $R(x)=g(x)/h(x)$ be a cubic rational expression, over $\mathbb{F}_{q}$ of
characteristic two, with no ramification point having ramification index $3$.
Then $|\mathcal{I}(g,h,n,q)|=q^{n}/3n+O(q^{n/2}/n)$.

###### Proof.

According to Theorem 18, the cubic rational expression $R(x)$ is equivalent,
over $\mathbb{F}_{q}$, to one of those in cases (iv), (v) or (vi). We consider
each case in turn.

In case (iv) we have $g(x)/h(x)=(x^{3}+c)/x$ with some nonzero
$c\in\mathbb{F}_{q}$. Setting the quadratic resolvent of $g(x)-\beta h(x)$
equal to zero we find the equation $x^{2}+cx=\beta^{3}+c^{2}$. The projective
version of the curve given by this equation is a non-singular curve of genus
one. Similarly to the proof of Theorem 14, the Hasse-Weil bound applies and
gives

$|N-q^{n}|\leq 2\sqrt{q^{n}}.$

Together with Equation (1) this yields
$|\mathcal{I}(g,h,n,q)|=q^{n}/3n+O(q^{n/2}/n)$, as desired.

In case (v), setting the quadratic resolvent of $g(x)-\beta h(x)$ equal to
zero we find the equation

$x^{2}+cx\beta+cx=\beta^{3}+c^{2}\beta^{2}+c^{2},$

with $c\in\mathbb{F}_{q}\setminus\mathbb{F}_{2}$. After checking that the
projective version of the curve is a non-singular curve of genus one, one
concludes as in the previous case.

Finally, in case (vi), the quadratic resolvent leads to an equation of the
form

$x^{2}+(\beta^{2}+\beta+\sigma)x=u(\beta),$

for a certain quartic polynomial $u(\beta)$ with leading coefficient
$b+1+\sigma$, where $b\in\mathbb{F}_{q}\setminus\mathbb{F}_{2}$. Calculations
here are more involved than in previous cases, but with a little help from any
computer algebra system one can show that the projective version of this
equation represents an absolutely irreducible quartic curve, with a
singularity in the point at infinity. As in the proof of Theorem 14, one has

$|N-q^{n}|\leq 6\sqrt{q^{n}},$

and again the desired conclusion follows after applying Möbius inversion. ∎

##  7\. Transformation shift registers

Linear feedback shift registers are used to generate sequences over a finite
field in a range of applications, from pseudo-random number generation to the
design of stream ciphers, see [LN83, Chapter 8, Section 1]. Transformation
shift registers (TSRs) can be considered a generalization of linear feedback
shift registers. We refer the reader to [CHPW15, Section 3] for an
introduction to TFRs, and focus here on the connection between our results and
counting TSRs.

There is a notion of irreducible TSR, and following notation in [CHPW15] we
let $\operatorname{\mathrm{TSRI}}(m,n,q)$ denote the set of irreducible TSRs
of order $n$ over $\mathbb{F}_{q^{m}}$. In [Ram15] Ram related the cardinality
of $\operatorname{\mathrm{TSRI}}(m,n,q)$ to counting irreducible polynomials
of the form $f_{R}(x)$, with $R(x)$ ranging over rational expressions of
degree $n$ of a special form. In the present paper’s notation, and according
to a further development in [CHPW15, Theorem 3.2], we have

(6)
$|\operatorname{\mathrm{TSRI}}(m,n,q)|=\frac{|\mathrm{GL}_{m}(\mathbb{F}_{q})|}{q^{m}-1}\sum_{h(x)}|\mathcal{I}(x^{n},h(x),m,q)|,$

where the summation $\sum_{h(x)}$ runs over all $h(x)\in\mathbb{F}_{q}[x]$
having degree less than $n$ and satisfying $h(0)=1$. Here
$|\mathrm{GL}_{m}(\mathbb{F}_{q})|=\prod_{i=0}^{m-1}(q^{m}-q^{i})$ is the
order of the general linear group. This connection, together with Ahmadi’s
evaluation, in [Ahm11], of $|\mathcal{I}(g(x),h(x),m,q)|$ for the case where
$g(x)/h(x)$ is quadratic, was then used in [CHPW15, Theorem 3.4] to obtain a
new derivation of an explicit formula for
$|\operatorname{\mathrm{TSRI}}(m,2,q)|$, originally found by Ram [Ram15] by a
different method. We use a similar method to recover the formulas for
$|\operatorname{\mathrm{TSRI}}(m,3,q)|$ obtained by Jiang and Yang in [JY17].

Start with noting that if $h(x)$ has degree less than $n$ and satisfies
$h(0)=1$ as above, then $g(x)=(1/x)\circ\bigl{(}x^{n}/h(x)\bigr{)}\circ(1/x)$
is a monic polynomial of degree $n$ and with $g(0)=0$. According Section 2 we
then have

$|\mathcal{I}(x^{n},h(x),m,q)|=|\mathcal{I}(g(x),1,m,q)|.$

In particular, when $n=3$ we have

$|\operatorname{\mathrm{TSRI}}(m,3,q)|=\frac{|\mathrm{GL}_{m}(\mathbb{F}_{q})|}{q^{m}-1}\sum_{a,b\in\mathbb{F}_{q}}|\mathcal{I}(x^{3}+ax^{2}+bx,1,m,q)|,$

which we now in a position to compute using our results of the previous
sections.

######  Theorem 22.

If $q$ is not a power of three, then

$|\operatorname{\mathrm{TSRI}}(m,3,q)|=\frac{q|\mathrm{GL}_{m}(\mathbb{F}_{q})|}{3m(q^{m}-1)}\sum_{d\mid
n,\ 3\nmid
d}\mu(d)\bigl{(}q+\varepsilon^{m/d}\bigr{)}\bigl{(}q^{m/d}-\varepsilon^{m/d}\bigr{)}.$

If $q$ is a power of $3$, then

$|\operatorname{\mathrm{TSRI}}(m,3,q)|=\frac{(q-1)|\mathrm{GL}_{m}(\mathbb{F}_{q})|}{3m(q^{m}-1)}\sum_{d\mid
n,\ 3\nmid d}\mu(d)\left(q+\frac{3+(-1)^{m/d}}{2}\right)q^{m/d}.$

###### Proof.

Suppose first that the characteristic of $\mathbb{F}_{q}$ is at least five.
The polynomial $x^{3}+ax^{2}+bx$ is equivalent to $x^{3}$ if $a^{2}=3b$, and
to $x^{3}-\tau x$ otherwise, where $\tau$ is a nonzero element of
$\mathbb{F}_{q}$. Consequently,

$\sum_{a,b\in\mathbb{F}_{q}}|\mathcal{I}(x^{3}+ax^{2}+bx,1,m,q)|=q|\mathcal{I}(x^{3},1,m,q)|+(q^{2}-q)|\mathcal{I}(x^{3}-\tau
x,1,m,q)|.$

According to Equation (6), using Theorem 9 in its formulation of Equation (5),
and Theorem 13, we find that the above sum equals

$\frac{q}{3m_{3}}\bigl{(}qI(m/m_{3},q^{m_{3}})+I(m/m_{3},\varepsilon
q^{m_{3}})-qI(m/m_{3},\varepsilon)-I(m/m_{3},1)\bigr{)}.$

This can be expanded as

$\frac{q}{3m}\sum_{d\mid n,\ 3\nmid
d}\mu(d)\bigl{(}q+\varepsilon^{m/d}\bigr{)}\bigl{(}q^{m/d}-\varepsilon^{m/d}\bigr{)},$

and leads to the desired conclusion.

Now suppose $\mathbb{F}_{q}$ has characteristic two. Then the polynomial
$x^{3}+ax^{2}+bx$ is equivalent to $x^{3}$ if $a^{2}=b$, and to $x^{3}+x^{2}$
otherwise. It suffices now to replace $\mathcal{I}(x^{3}-\tau x,1,m,q)$ with
$\mathcal{I}(x^{3}-x^{2},1,m,q)$ in the above argument, invoke Theorem 20
instead of Theorem 13, and the desired conclusion follows.

Finally, suppose $\mathbb{F}_{q}$ has characteristic three. If if $a=b=0$ then
the polynomial $x^{3}+ax^{2}+bx$ equals $x^{3}$, but because $f(x^{3})$ cannot
be irreducible this case gives no contribution to our count. If $a\neq 0$,
then $x^{3}+ax^{2}+bx$ is seen to be equivalent to $x^{3}+x^{2}$ (by a linear
substitution in $x$ followed by subtraction of a constant). If $a=0$ and
$b\neq 0$, then $x^{3}+ax^{2}+bx$ is equivalent to either $x^{3}-x$ or
$x^{3}-\sigma x$ according as to whether $-b$ is a square in $\mathbb{F}_{q}$,
or not. Here $\sigma$ is a nonsquare in $\mathbb{F}_{q}$ as in Theorem 17.
Consequently,

$\displaystyle\sum_{a,b\in\mathbb{F}_{q}}|\mathcal{I}(x^{3}+ax^{2}+bx,1,m,q)|$
$\displaystyle=(q^{2}-q)|\mathcal{I}(x^{3}+x^{2},1,m,q)|$
$\displaystyle\quad+\frac{q-1}{2}|\mathcal{I}(x^{3}-x,1,m,q)|$
$\displaystyle\quad+\frac{q-1}{2}|\mathcal{I}(x^{3}-\sigma x,1,m,q)|.$

According to Equation (6), and using Theorems 16 and 17, we find that the
above sum equals

$\frac{q-1}{3m_{3}}\biggl{(}(q+1)I(m/m_{3},q^{m_{3}})+\frac{1}{2}I(m/2m_{3},q^{2m_{3}})\biggr{)}.$

This leads to the desired conclusion after expanding the sums. ∎

As mentioned in [JY17], the results of Theorem 22 can be expressed in terms of
counting polynomials of various types if one so wishes, akin to what we have
done in previous sections. The most pleasant expression is obtained when
$q\equiv 1\pmod{3}$, where we find

$|\operatorname{\mathrm{TSRI}}(m,3,q)|=\frac{|\mathrm{GL}_{m}(\mathbb{F}_{q})|}{q^{m}-1}\cdot\frac{q(q+1)}{3m_{3}}\bigl{(}I(m/m_{3},q^{m_{3}})-I(m/m_{3},1)\bigr{)}.$

## References

  * [Ahm11] Omran Ahmadi, _Generalization of a theorem of Carlitz_ , Finite Fields Appl. 17 (2011), no. 5, 473–480. MR 2831706 (2012f:11231)
  * [AP96] Yves Aubry and Marc Perret, _A Weil theorem for singular curves_ , Arithmetic, geometry and coding theory (Luminy, 1993), de Gruyter, Berlin, 1996, pp. 1–7. MR 1394921
  * [Car67] L. Carlitz, _Some theorems on irreducible reciprocal polynomials over a finite field_ , J. Reine Angew. Math. 227 (1967), 212–220. MR 0215815 (35 #6650)
  * [CHPW15] Stephen D. Cohen, Sartaj Ul Hasan, Daniel Panario, and Qiang Wang, _An asymptotic formula for the number of irreducible transformation shift registers_ , Linear Algebra Appl. 484 (2015), 46–62. MR 3385053
  * [Chu96] W. M. Chu, _Construction of irreducible polynomials using cubic transformation_ , Appl. Algebra Engrg. Comm. Comput. 7 (1996), no. 1, 15–19. MR 1464534
  * [Coh69] Stephen D. Cohen, _On irreducible polynomials of certain types in finite fields_ , Proc. Cambridge Philos. Soc. 66 (1969), 335–344. MR 0244202 (39 #5519)
  * [Con] Keith Conrad, _Galois groups of cubics and quartics in all characteristics_ , unpublished, kconrad.math.uconn.edu/blurbs/galoistheory/cubicquarticallchar.pdf.
  * [JY17] Yupeng Jiang and Jiangshuai Yang, _On the number of irreducible linear transformation shift registers_ , Des. Codes Cryptogr. 83 (2017), no. 2, 445–454. MR 3622678
  * [Kap69] Irving Kaplansky, _Fields and rings_ , The University of Chicago Press, Chicago, Ill.-London, 1969. MR 0269449
  * [LN83] Rudolf Lidl and Harald Niederreiter, _Finite fields_ , Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1983, With a foreword by P. M. Cohn. MR 746963 (86c:11106)
  * [MP] Sandro Mattarei and Marco Pizzato, _Cubic rational expressions over a finite field_ , arXiv:2104.00111.
  * [MP17] by same author, _Generalizations of self-reciprocal polynomials_ , Finite Fields Appl. 48 (2017), 271–288. MR 3705747
  * [Piz13] Marco Pizzato, _Some problems concerning polynomials over finite fields, or algebraic divertissements_ , Ph.D. thesis, University of Trento, Italy, December 2013.
  * [Ram15] Samrith Ram, _Enumeration of linear transformation shift registers_ , Des. Codes Cryptogr. 75 (2015), no. 2, 301–314. MR 3326176


# Yseop at FinSim-3 Shared Task 2021: Specializing Financial Domain Learning
with Phrase Representations

Hanna Abi Akl  Dominique Mariko  Hugues de Mazancourt
Yseop
{habi-akl, dmariko<EMAIL_ADDRESS>
###### Abstract

In this paper, we present our approaches for the FinSim-3 Shared Task 2021:
Learning Semantic Similarities for the Financial Domain. The aim of this
shared task is to correctly classify a list of given terms from the financial
domain into the most relevant hypernym (or top-level) concept in an external
ontology. For our system submission, we evaluate two methods: a Sentence-
RoBERTa (SRoBERTa) embeddings model pre-trained on a custom corpus, and a dual
word-sentence embeddings model that builds on the first method by improving
the proposed baseline word embeddings construction using the FastText model to
boost the classification performance. Our system ranks 2nd overall on both
metrics, scoring 0.917 on Average Accuracy and 1.141 on Mean Rank.

##  1 Introduction

A hypernym or hyperonym is a concept which is superordinate to another one. In
computer science, it is often represented as an IS-A relationship. For
example, animal is a hypernym of cat and equity index is a hypernym of S&P 500
Index Murphy (2003). Hypernymy, i.e. the capability to relate generic terms or
classes to their specific instances, lies at the core of human cognition
Camacho-Collados et al. (2018). Hypernymy modeling has been widely studied in
natural language processing (NLP) for decades. Particularly, results based on
embeddings methods Henderson (2017); Nguyen et al. (2017); Wang and He (2020);
Yu et al. (2015) show promise but the challenge remains in specializing these
embeddings in particular areas such as the financial domain because of
different aspects of language such as precise terms (e.g. abbreviations) and
specific semantics that are badly or not covered at all by general-purpose
models.

The FinSim 2020 shared task Maarouf et al. (2020) was the first task that
attempts to combine hypernym classification methods in the financial domain.
The FinSim-3 Shared Task 2021: Learning Semantic Similarities for the
Financial Domain iterates on the previous editions by proposing an extended
dataset with more diversified financial concepts.

In this paper, we present our approaches which focus on domain-specific
learning embeddings using as little data as possible. Although the shared task
permits the use of external sources, we limit our training to the Financial
Industry Business Ontology (FIBO)111https://spec.edmcouncil.org/fibo/ data as
well as the set of prospectuses in English curated and made available by the
organizers. The corpus size for the latter set is estimated to about 10
million tokens. We explore two methods: the first is based on a custom
sentence-level embeddings training using SRoBERTa Reimers and Gurevych (2019)
and a term-definition dataset compiled from the FIBO website, and the second
is a concatenated sentence-word embeddings model combining the custom SRoBERTa
embeddings with a
FastText222https://radimrehurek.com/gensim/models/fasttext.html word
embeddings model trained on the prospectuses set and the constructed FIBO
dataset.

We also explore and compare empirically the performance of several
classifiers. Our experimental results demonstrate that while the domain-
specific custom embeddings enhance the classification performance, class
imbalances still hinder the recognition of under-represented classes. We
analyze these results based on the number of labels provided in the training
dataset as well as those extracted from the FIBO website.

The rest of this paper is organized as follows. Section 2 introduces the
technical details of our proposed approaches. Section 3 empirically evaluates
the performances of our methods and presents our results. Section 4 provides
the conclusions of our work.

##  2 Proposed Approaches

We make use of custom corpus and exploit sentence-level and word-level
embeddings in the context of phrase representation learning. We also test
several classifiers in our term classification approaches. The general
framework is shown in Figure 1. This framework consists of customized corpus
collections, sentence and word representation learning methods and term
classification strategies. We will elaborate on each component below.

Figure 1: Framework of our proposed approach

###  2.1 Customized Corpus Collection

General word embeddings are trained on domain-independent corpus. However,
different domains have their proper semantics. In order to learn domain-
specific representations for financial data, we base our work on collected
customized corpus. We use the set of English prospectuses provided by the
shared task organizers that contains 203 documents which roughly amounts to an
estimated size of 10 million tokens. We augment this set with an extracted
corpus from the FIBO website that we also use to train the sentence
embeddings.

Sentence embeddings already contain contextual information. However, they
suffer from the same domain specialization problem as word embeddings. We
choose to work with a specialized corpus to generate our sentence embeddings
and use the FIBO website provided by the shared task organizers. Starting from
the predefined tags (Bonds, Forward, Funds, Future, MMIs, Option, Stocks,
Swap, Equity Index, Credit Index, Securities restrictions, Parametric
schedules, Debt pricing and yields, Credit Events, Stock Corporation, Central
Securities Depository, Regulatory Agency), we mine their corresponding FIBO
web pages for the following properties:

  * •

Definition

  * •

Explanatory Note

  * •

Generated Description

  * •

Synonym(s)

We also iterate over their children (n+1) instances found under the ”Direct
subclasses” web page section and collect their associated definitions. We do
the same for the grandchildren (n+2) of the predefined tags at which point we
stop the recursion. From the collected definitions we create a corpus of
definition/tag pairs whereby each definition is associated to its
corresponding tag. Children and grandchildren definitions are associated to
one of the parent tags we started with. We stop the recursion at (n+2) because
iterating further causes an overlap between concept definitions related to one
or more of the predefined tags resulting in imprecise tag associations
depending on the order of the recursion. Limiting the recursion at the (n+2)
stage effectively prevents noise addition caused by such overlaps. The final
compiled dictionary contains a total of 2015 definitions. These definitions
are used to train domain-specific sentence representations.

###  2.2 Phrase Representation Learning

In this component, we combine two representational techniques: word embeddings
and sentence embeddings. By concatenating both word and sentence vectors for a
phrase (i.e. the group of words that make up a term), we hope to capture the
syntactic and semantic properties of the financial domain while trying to
reduce the ambiguity that comes with domain-specific representational
learning. To achieve this practically, we pad the word embeddings vector of
dimension 300 with zeroes to obtain a new word vector of size 768 identical to
the size of the sentence embeddings vector without loss of information stored
by the word vector. Then we concatenate both vectors by performing a term-by-
term addition operation. Our final vector model is of size 768 and combines
the information captured by both the sentence and word embeddings vectors.

For both models, The training is performed on an NVIDIA GeForce RTX 2070 with
Max-Q Design 8GB GPU machine. The construction of each embeddings model is
detailed in the following subsections.

####  2.2.1 Sentence Representation Learning

Figure 2: Basic SentenceTransformer Architecture

We use the version of SRoBERTa provided by Hugging
Face333https://huggingface.co/sentence-transformers/nli-roberta-base-v2 and
train it from scratch by adopting the method for training any BERT-like model
on the STSBenchmark444http://ixa2.si.ehu.eus/stswiki/index.php/STSbenchmark
for the semantic similarity task555https://github.com/UKPLab/sentence-
transformers/blob/master/examples/training/sts/training_stsbenchmark.py. We
split our corpus into 70% train set, 10% dev set and 20% test set. We also
adopt the same model parameters as the STSBenchmark method for our training:

  * •

Training Batch Size: 8

  * •

Number of Epochs: 4

To specialize our model, we use the extracted FIBO corpus of term definitions
described earlier. In terms of pre-processing for each definition, we
transform the text to lowercase and segment it into sentences based on newline
and punctuation delimiters. The SentenceTransformer model has the following
architecture depicted in Figure 2. The depicted architecture consists of one
RoBERTa layer and a pooling layer. We feed the input sentence or text into the
RoBERTa transformer network. RoBERTa produces contextualized word embeddings
for all input tokens in our text. Since we want a fixed-sized output
representation (vector u), we need a pooling layer. Different pooling options
are available, the most basic one being mean-pooling: we simply average all
contextualized word embeddings RoBERTa produces. This gives us a fixed 768
dimensional output vector independently of how long our input text is.

For our training set, each definition is duplicated to match the total number
of predefined tags we have. Each duplicate is then passed as an input sentence
to the SentenceTransformer model along with a label indicating the semantic
similarity with each of the tags. We use a label of 0.8 to indicate a positive
example (i.e. corresponding to a matching definition-tag pair) and 0.3 for
negative examples (i.e. all other duplicate instances of the definition with
the remaining mismatched tags). The labels are chosen to be sufficiently far
apart in value to discriminate especially for ambiguous terms. We feed the
model a total of 317101 definition-label pairs.

####  2.2.2 Word Representation Learning

We augment the corpus compiled from the FIBO web pages with the English
prospectuses set and use a FastText Bojanowski et al. (2017) model to generate
custom domain-specific word embeddings. Between the two versions of custom
word2vec models with dimensions 100 and 300 provided by the shared task
organizers, the model with dimension 300 outperforms the smaller model. We use
this as our starting point to generate two custom embeddings models, the first
based on word2vec and the second on FastText, both of dimension 300, using our
extracted corpus and compare their performance in the classification task. The
results are detailed in Section 3.

###  2.3 Classification Methods

Sentence and word representations are used as features to train classifiers
for term classification. A term is represented by the sum of phrase (sentence
+ word) embeddings for each word contained in the term. To find the best
classifiers, we test two widely used classification methods: Logistic
Regression and Random Forest. Experimental studies will be discussed in
Section 3.

##  3 Experiments

In this section we describe the data provided by the shared task organizers.
We then provide details on the empirical experiments we performed and present
our final results.

###  3.1 Data Description

The training data provided by the task organizers contains a total of 1050
entries where each entry consists of a term and its corresponding label. A
label can be one of the 17 predefined tags. For the test data, there are 326
entries of terms to be correctly classified into the correct tag. The main
difficulty in this classification task lies in the tag distribution: the
chosen labels are not at the same ontological level as Figure 3 demonstrates.

Figure 3: An Example of Label Ontology Hierarchy

The hierarchy shows that while some labels like Forward, Future, Option and
Swap are on the same level, they are not aligned with other labels like Bond.
The same case can be made for Central Securities Depository and Regulatory
Agency in the FIBO ontology. The issue indicates that labels cannot be learned
from a simple IS-A relationship.

To tackle this problem, we enlarge the scope of our mining while collecting
data from the FIBO web pages. Instead of limiting our collections to direct
subclasses of the predefined tags, we search for ”Instances” under
”Ontological characteristic” which allows us to enrich our corpus both
vertically and horizontally and expand term relations as much as possible by
capturing their semantic connections.

###  3.2 Results and Analysis

We design our experiments in order to determine the best model for each of the
components in our proposed framework approach.

For the sentence embeddings module, we pit our SRoBERTa model against other
well-performing models that we pre-train using the same setup described in
Section 2.2. The selection of models is done based on our computational
limitations as well as the
grid666https://www.sbert.net/docs/pretrained_models.html proposed in the
official SentenceTransformers Documentation. We select paraphrase-mpnet-
base-v2, paraphrase-MiniLM-L6-v2 and paraphrase-distilroberta-base-v2 as the
main competitors to SRoBERTa. To measure the performance of each custom
trained model, we treat the classification problem like a semantic similarity
task and use cosine similarity to find the best label for each term embedding.
We evaluate model performance based on the metrics proposed by the shared task
organizers. The results are shown in Table 1.

Model | Accuracy | Mean Rank
---|---|---
paraphrase-mpnet-base-v2 | 0.68 | 1.93
paraphrase-MiniLM-L6-v2 | 0.65 | 2.44
paraphrase-distilroberta-base-v2 | 0.63 | 2.65
SRoBERTa | 0.73 | 1.61
Table 1: Sentence Embeddings Evaluation

The empirical experiment is consistent with the choice of model since SRoBERTa
is specialized in tasks like clustering or semantic search.

For the word embeddings model selection, we adopt the same baseline component
proposed by the task organizers and composed of an embeddings module used as a
feature vector and a logistic regression term classifier. The classifier is
fixed in this experiment. The type of word embeddings is the only variable.
The word2vec-100 and word2vec-300 models are the ones proposed by the task
organizers and trained on the English prospectuses set (which we’ll call
Base). The c-word2vec-300 and c-fasttext-300 models are the models trained on
our custom corpus (which we’ll call Custom) comprised of the FIBO term
definitions and the English prospectuses. Note that each result is the average
of 5 runs and the train/test ratio is 80%/20%. The results are presented in
Table 2.

Model | Corpus | Accuracy | Mean Rank
---|---|---|---
word2vec-100 | Base | 0.76 | 1.43
word2vec-300 | Base | 0.77 | 1.41
c-word2vec-300 | Custom | 0.78 | 1.40
c-fasttext-300 | Custom | 0.82 | 1.33
Table 2: Word Embeddings Evaluation

While training on the custom corpus enhances model performance, the results
validate our choice of FastText as it outperforms word2vec due to the model’s
capability to retain subword information which results in better learning.

Finally, in order to improve term classification, we empirically study the
performance of the classifier component by reversing the conditions of our
previous experiment: we fix the feature vector to our best word embeddings
model (c-fasttext-300) and vary the classifier. We keep the train/test split
at 80%/20% and perform 5 runs. The results are displayed in Table 3.

Model | Accuracy | Mean Rank
---|---|---
Random Forest | 0.80 | 1.45
Logistic Regression | 0.82 | 1.33
Table 3: Classifier Evaluation

From this experimental study, we find that complicated classifiers like Random
Forest achieve worse performances than linear classifiers, so we select
Logistic Regression as the classifier in our submitted systems. This
observation shows that models that learn linear boundaries tend to perform
better for this type of task.

###  3.3 System Submissions

In our submitted systems, we use the SRoBERTa model trained on the extracted
corpus from the FIBO web pages. We submit a first system composed only of
SRoBERTa and a classifier to study the performance of specialized sentence
representations on this type of task. We use the constructed vector resulting
from the concatenation of both the sentence model and the c-fasttext-300 word
model as feature vector to the classifier in our second submission to study
the effect of combining sentence and word information in what we refer to as
phrase representation learning. Logistic regression is used in both
submissions as the classifier. The final results are reported in Table 4. ACC
is short for Accuracy and MR is short for Mean Rank.

yseop_1 In this submission, we combine SRoBERTa as a feature vector with a
Logistic Regression classifier. The dimension of representation for each term
is 768.

yseop_2 In this submission, we concatenate the SRoBERTa model with the padded
c-fasttext-300 to produce a feature vector of size 768. We feed the resulting
feature vector to a Logistic Regression classifier.

| Train Data | Test Data
---|---|---
System | ACC | MR | ACC | MR
yseop_1 | 0.871 | 1.275 | 0.883 | 1.236
yseop_2 | 0.883 | 1.234 | 0.917 | 1.141
Table 4: Final System Submissions

From our submissions, yseop_2 performs best and ranks 2nd overall on both
Average Accuracy and Mean Rank metrics in the shared task.

###  3.4 Data Imbalance

Another issue in this shared task is the problem of data distribution. By
examining our system results, we observe that our framework performs
consistently better for some labels than others. We investigate the reason for
the poor performance on some labels by averaging the accuracy of matched
labels, i.e. labels that were correctly classified as the best choice for an
entry, over 5 runs for our best system. The analysis yields:

  * •

Central Securities Depository: 78.45%

  * •

Credit Index: 79.28%

  * •

Bonds: 87.80%

  * •

Credit Events: 60%

  * •

Funds: 84.31%

  * •

Stock Corporation: 66.80%

  * •

Regulatory Agency: 90.76%

  * •

Debt pricing and yields: 97.94%

  * •

Equity Index: 96.25%

  * •

Swap: 75.18%

  * •

Option: 100%

  * •

Stocks: 45.71%

  * •

Future: 88.46%

  * •

Securities restrictions: 80%

  * •

Parametric schedules: 82.46%

  * •

MMIs: 18.30%

  * •

Forward: 57.38%

This preliminary analysis reveals that while some labels like Option and
Equity Index are over-expressed (the model predicts them correctly most of the
times), others such as MMIs and Stocks are severely under-expressed. These
results lead us to examining the composition of our train set distribution:

  * •

Central Securities Depository: 10.19%

  * •

Credit Index: 12.29%

  * •

Bonds: 5.24%

  * •

Credit Events: 1.71%

  * •

Funds: 2.1%

  * •

Stock Corporation: 2.38%

  * •

Regulatory Agency: 19.52%

  * •

Debt pricing and yields: 5.52%

  * •

Equity Index: 27.24%

  * •

Swap: 3.43%

  * •

Option: 2.29%

  * •

Stocks: 1.62%

  * •

Future: 1.81%

  * •

Securities restrictions: 0.75%

  * •

Parametric schedules: 1.43%

  * •

MMIs: 1.62%

  * •

Forward: 0.86%

The distribution shows a discrepancy in label expression that may explain the
over-prediction of certain labels whenever the model makes a wrong prediction.
However, the train data is one source of our learning and is active at the
classification component of our framework. The other main source of
representation is the extracted corpus collected from FIBO. We propose to
analyze the distribution of label occurrences in the corpus based on the
definitions collected:

  * •

Central Securities Depository: 0.45%

  * •

Credit Index: 0.20%

  * •

Bonds: 13.30%

  * •

Credit Events: 4.27%

  * •

Funds: 4.81%

  * •

Stock Corporation: 2.18%

  * •

Regulatory Agency: 3.24%

  * •

Debt pricing and yields: 10.72%

  * •

Equity Index: 0.35%

  * •

Swap: 4.57%

  * •

Option: 6.00%

  * •

Stocks: 38.41%

  * •

Future: 2.43%

  * •

Securities restrictions: 3.57%

  * •

Parametric schedules: 3.82%

  * •

MMIs: 0.74%

  * •

Forward: 0.94%

The last set of results shows the number of times a label is expressed is not
sufficient to guarantee a good model performance. Some labels that are well
expressed are under-represented in terms of definitions with respect to
others. This effectively splits the data distribution problem in two ways: the
first is balancing uner-represented labels using techniques such as SMOTE and
the second enriching definitions for some labels to improve predictions using
external sources. Both methods merit further exploration.

##  4 Conclusion

In this paper, we studied the task of hypernym identification in the financial
domain. We trained a a phrase representation learning model by specializing
and combining a SRoBERTa sentence embeddings model and a FastText word
embeddings model on a relatively small data set. We also enriched the provided
data by collecting term definitions and term relations for the proposed
hypernyms. Our approach shows that it is possible to specialize a domain-
specific model by combining sentence and word models with a linear classifier
on a relatively small corpus. It would be interesting to explore future
possibilities by exploiting other domain resources or enhancing under-
represented labels and studying their impact on domain-specific learning.

## References

  * Bojanowski et al. [2017] Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov.  Enriching word vectors with subword information, 2017.
  * Camacho-Collados et al. [2018] Jose Camacho-Collados, Claudio Delli Bovi, Luis Espinosa-Anke, Sergio Oramas, Tommaso Pasini, Enrico Santus, Vered Shwartz, Roberto Navigli, and Horacio Saggion.  SemEval-2018 task 9: Hypernym discovery.  In Proceedings of The 12th International Workshop on Semantic Evaluation, pages 712–724, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
  * Henderson [2017] James Henderson.  Learning word embeddings for hyponymy with entailment-based distributional semantics, 2017.
  * Maarouf et al. [2020] Ismail El Maarouf, Youness Mansar, Virginie Mouilleron, and Dialekti Valsamou-Stanislawski.  The FinSim 2020 shared task: Learning semantic representations for the financial domain.  In Proceedings of the Second Workshop on Financial Technology and Natural Language Processing, pages 81–86, Kyoto, Japan, 5 January 2020. -.
  * Murphy [2003] M. Lynne Murphy.  Semantic Relations and the Lexicon: Antonymy, Synonymy and other Paradigms.  Cambridge University Press, 2003.
  * Nguyen et al. [2017] Kim Anh Nguyen, Maximilian Köper, Sabine Schulte im Walde, and Ngoc Thang Vu.  Hierarchical embeddings for hypernymy detection and directionality.  In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 233–243, Copenhagen, Denmark, September 2017\. Association for Computational Linguistics.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks, 2019.
  * Wang and He [2020] Chengyu Wang and Xiaofeng He.  BiRRE: Learning bidirectional residual relation embeddings for supervised hypernymy detection.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3630–3640, Online, July 2020. Association for Computational Linguistics.
  * Yu et al. [2015] Zheng Yu, Haixun Wang, Xuemin Lin, and Min Wang.  Learning term embeddings for hypernymy identification.  In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, page 1390–1397. AAAI Press, 2015.