On the number of irreducible polynomials of special kinds in finite fields

1.   Introduction

The polynomials of special kinds in finite fields have attracted a lot of research interest (see, e.g., ^[1,2,3,6,9]). Let $\mathbb{F}_q$ be the finite field of $q$ elements with characteristic $p$ and $n\geq1$ be an integer. Let $I_q(n)$ denote the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$ and $\mu(\cdot)$ the M$\rm{\ddot{o}}$bius function. Gauss ^[4] found that

Let $f(x) = x^n+a_1x^{n-1}+\dots+a_n\in \mathbb{F} _q[x]$ be an irreducible polynomial. Suppose that $\alpha$ is a root of $f(x)$, then all the roots of $f(x)$ are $\alpha^{q^i}, i = 0, 1, \dots, n-1$. The trace function of $\alpha$ is defined to be $\mathrm{Tr}(\alpha) = \alpha+\alpha^q+\cdots+\alpha^{q^{n-1}}$. So $-a_1 = \mathrm{Tr}(\alpha)$ and therefore $-a_1$ is also called the trace of $f(x)$. Let $N_q(n)$ denote the number of monic irreducible polynomials of degree $n$ over $\mathbb{F} _q$ with nonzero traces. Suppose $n = mp^e$ with $p\nmid m$. Carlitz ^[1] and Ruskey, Miers and Sawada ^[12] obtained that:

Theorem 1.1. The number of monic irreducible polynomials of degree $n$ over $\mathbb{F} _q$ with nonzero traces is given by

An irreducible polynomial in $\mathbb{F}_q[x]$ is called a normal polynomial if its roots are linearly independent over $\mathbb{F}_q$. All the roots of a normal polynomial of degree $n$ over $\mathbb{F}_{q}$ form a normal basis of $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$. Normal bases over finite fields have proved very useful for fast arithmetic computations with potential applications to coding theory and to cryptography (see, e.g., ^[6] and ^[7]). It is not easy to determine whether a given irreducible polynomial is normal or not. Let $\phi(\cdot)$ denote the Euler totient function. Using Theorem 1.1 and other results, Huang, Han and Cao ^[5] showed that:

Theorem 1.2. The following inequality holds

where $\tau(d)$ is the order of $q$ modulo $d$. Furthermore, the following statements are equivalent:

$\rm{(i)}$ Inequality (1.2) becomes an equality.

$\rm{(ii)}$ $n = p^e$, or $n$ is a prime different from $p$ and $q$ is a primitive root modulo $n$.

$\rm{(iii)}$ Every irreducible polynomial of degree $n$ over $\mathbb{F}_q$ with nonzero trace is a normal polynomial.

Let $f(x)$ be an irreducible polynomial of degree $n$ over $\mathbb{F}_q$ as before. For a positive divisor $n_1$ of $n$, define the $n_1$-traces of $f(x)$ to be $\mathrm{Tr}(\alpha; n_1) = \alpha+\alpha^q+\cdots+\alpha^{q^{n_1-1}}$ where $\alpha$'s are the roots of $f(x)$. Let $N_q^*(n; n_1)$ denote the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$ with nozero $n_1$-traces. Obviously, the function $\mathrm{Tr}(\alpha; n_1)$ generalizes the usual trace function $\mathrm{Tr}(\alpha)$. Gauss's formula (1.1) gives the formula for $N_q^*(n; 1)$ for $n\geq2$ and Theorem 1.1 gives the formula for $N_q^*(n; n)$. In this paper, we obtain the explicit formula for $N_q^*(n; n_1)$ in the general case, including a new proof to Theorem 1.1.

To state our result, we need to introduce more notation and convention.

● Assume that $n = mp^e$ and $n_1 = m_1p^{e_1}$ with $n_1\mid n$ and $p\nmid mm_1$.

● For a positive integer $d$, let $\mathfrak{P}(d)$ denote the set of all distinct positive prime divisors of $d$. Assume that $\mathfrak{P}(n) = \{p_{1}, p_{2}, \ldots, p_{k}\}$ and $p_{k} = p$ if $e\geq1$.

● Without loss of generality, assume that $\{a\in \mathfrak{P}(n):a\in \mathfrak{P}(m_1), a\notin \mathfrak{P}(\frac{m}{m_1})\} = \{p_{1}, \ldots, p_{t}\}$ with $t\leq k$. Write $m_1' = p_{1}\cdots p_{t}$.

The following is the main theorem of this paper.

Theorem 1.3 (Main Theorem). With the above notation and convention, we have

In particular, for $n_1 = 1$,

and for $n_1 = n$,

Let $N_q^0(n; n_1)$ denote the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$ with zero $n_1$-traces. The following corollary is a direct consequence of Theorem 1.3.

Corollary 1.4. With the above notation and convention, we have

Since our method is based on the properties of linearized polynomials in finite fields, we will introduce them in the next section. The proof of Theorem 1.3 will be given in Section 3.

2.   Linearized polynomials

Linearized polynomials are also called $q$-polynomials in the literature. Many definitions and results of this section go back to the fundamental papers of Ore ^[8,9,10,11], and we just list them without examples and proofs for the sake of brevity; see ^[6] for further details.

Let $r$ be a positive integer. A polynomial of the form $L(x) = \sum_{i = 0}^nc_ix^{q^i}$ with coefficients in an extension filed $\mathbb{F} _{q^r}$ of $\mathbb{F} _{q}$ is called a linearized polynomial over $\mathbb{F} _{q^r}$. The polynomials $l(x) = \sum_{i = 0}^nc_ix^i$ and $L(x) = \sum_{i = 0}^nc_ix^{q^i}$ over $\mathbb{F} _{q^r}$ are called $q$-associates of each other. More specially, $l(x)$ is the conventional $q$-associate of $L(x)$ and $L(x)$ is the linearized $q$-associate of $l(x)$. Given two linearized polynomials $L_1(x)$ and $L_2(x)$ over $\mathbb{F} _{q^r}$, we define symbolic multiplication by $L_1(x)\otimes L_2(x) = L_1(L_2(x))$. The ordinary product of linearized polynomials need not to be a linearized polynomial. And the set of linearized polynomials over $\mathbb{F} _q$ forms an integral domain under the operations of symbolic multiplication and ordinary addition.

If $L_1(x)$ and $L_2(x)$ are two linearized polynomials over $\mathbb{F} _{q}$, we say that $L_1(x)$ symbolically divides $L_2(x)$ (or that $L_2(x)$ is symbolically divisible by $L_1(x)$) if $L_2(x) = L_1(x)\otimes L(x)$ for some linearized polynomial $L(x)$ over $\mathbb{F} _{q}$. Similarly, one can define symbolic factorization and symbolic irreducibility for linearized polynomials.

Lemma 2.1. ([6,Lemma 3.59]) Let $L_1(x)$ and $L_2(x)$ be linearized polynomials over $\mathbb{F}_q$ with conventional $q$-associates $l_1(x)$ and $l_2(x)$. Then $l(x) = l_1(x)l_2(x)$ and $L(x) = L_1(x)\otimes L_2(x)$ are $q$-associates of each other.

The following criterion is an immediate consequence of the lemma above.

Corollary 2.2. Let $L_1(x)$ and $L(x)$ be linearized polynomials over $\mathbb{F}_q$ with conventional $q$-associates $l_1(x)$ and $l(x)$. Then $L_1(x)$ symbolically divides $L(x)$ if and only if $l_1(x)$ divides $l(x)$. In particular, $L(x)$ is symbolically irreducible over $\mathbb{F}_q$ if and only if $l(x)$ is irreducible over $\mathbb{F}_q$.

Let $L(x)$ be a linearized polynomial over $\mathbb{F}_q$ with conventional $q$-associate $l(x)$. We write $L(x)^{\otimes e}: = \underbrace{L(x)\otimes\cdots\otimes L(x)}_{e}$ for short. Let $L(x) = \otimes_{i = 1}^r L_i(x)^{\otimes e_i}$ be the symbolic factorization with distinct symbolically irreducible linearized polynomials $L_i(x)$ over $\mathbb{F}_q$, then by Lemma 2.1, $l(x) = \prod_{i = 1}^r l_i(x)^{e_i}$ is the canonical factorization of $l(x)$ in $\mathbb{F}_q[x]$, where $l_i(x)$ is the conventional $q$-associate of $L_i(x)$.

3.   Proof of main theorem

For a positive integer $d$, let $\varphi_d(x)$ denote the $d$th cyclotomic polynomial of degree $\phi(d)$ where $\phi(d)$ is the Euler totient function, and let $\Psi_d(x)$ denote the linearized $q$-associate of $\varphi_d(x)$. The following lemma is well known.

Lemma 3.1. ([6,Theorems 2.45 and 2.47])

As a direct consequence of Lemmas 2.1 and 3.1, we have

Corollary 3.2.

Definition 3.3. We define

and for each ${{p_i}}\in \mathfrak{P}(n)$, we define

Remark 3.4. $\rm(i)$ From the definition of $A_{{p_i}}$, one easily knows that it is just the finite field of size $q^{n/p_i}$. However, since the sets $A$ and $A_{{p_i}}$ will be considered together later, we adopt this notation to keep consistency.

$\rm(ii)$ Let $\alpha\in\mathbb{F}_{q^n}\setminus (\bigcup_{{{p_i}}\in \mathfrak{P}(n)} A_{{p_i}}\bigcup A)$. Then from the definition above, we know that the $n_1$-trace of $\alpha$ over $\mathbb{F}_q$ is nonzero, and that the degree of the minimal polynomial of $\alpha$ over $\mathbb{F}_q$ is just $n$. So $\alpha$ and all its conjugates in $\mathbb{F}_{q^n}$ form the roots of an irreducible polynomial of degree $n$ over $\mathbb{F}_q$ with nonzero $n_1$-traces.

To calculate the intersection of $A$ and $A_{p_i}$'s, we need to factorize the two polynomials $x+x^q+\cdots+x^{q^{n_1-1}}$ and $x^{q^{\frac{n}{{{p_i}}}}}-x$ into irreducible linearized polynomials.

Lemma 3.5.

and

for ${{p_i}}\in \mathfrak{P}(n)$. In particular, if ${{p_i}}\neq p$, then

and

Proof. Using Corollary 3.2 and the factorization

that comes from Lemma 3.1, we get (3.1). Similarly, we can get (3.2), (3.3) and (3.4).

Suppose that $\emptyset\neq J = \{p_{j_1}, \dots, p_{j_r}\}\subseteq \mathfrak{P}(n)$. Without loss of generality, assume that $\{a\in J:a\in \mathfrak{P}(m_1), a\notin \mathfrak{P}(\frac{m}{m_1})\} = \{p_{j_1}, \ldots, p_{j_t}\}$, and $p = p_{j_r}$ if $p\in J$. Observe that if $p\notin J$, then

and if $p = p_{j_r}\in J$, then

We will use the two observations (3.5) and (3.6) in the lemma below.

Lemma 3.6. $\rm{(i)}$ If $\ p\notin J$ or $p = p_{j_r}\in J$ and $e_1 < e$, then

$\rm{(ii)}$ If $p = p_{j_r}\in J$ and $e_1 = e$, then

Proof. To calculate $(\bigcap\nolimits_{j\in J}A_j)\bigcap A$, we first calculate $(\bigcap\nolimits_{j\in J}A_j)$. By (3.2),

If $p\notin J$, then by (3.3) and (3.7),

If $p = p_{j_r}\in J$, then by (3.4) and (3.7),

Now we calculate $(\bigcap\nolimits_{j\in J}A_j)\bigcap\limits A$. Recall the observations (3.5) and (3.6) and that $0\leq e_1\leq e$ which will be used below. If $\ p\notin J$, then by (3.1) and (3.8),

If $p = p_{j_r}\in J$, then by (3.1) and (3.9),

This finishes the proof.

The following lemma plays a vital role in the proof of our main theorem.

Lemma 3.7. $\rm{(i)}$ $|A| = q^{n_1-1}$.

$\rm{(ii)}$ $\big|\bigcap\nolimits_{j\in J}A_j\big| = q^{\frac{n}{p_{j_1}\dots p_{j_r}}}$.

$\rm{(iii)}$ $|(\bigcap\nolimits_{j\in J}A_j)\bigcap A| = q^{\frac{n_1}{pp_{j_{1}}\cdots p_{j_{t}}}}$ if $p\in J$ and $e_1 = e$.

$\rm{(iv)}$ $|(\bigcap\nolimits_{j\in J}A_j)\bigcap A| = q^{\frac{n_1}{p_{j_{1}}\cdots p_{j_{t}}}-1}$ if $p\notin J$ or $e_1 < e$.

Proof. Since (ⅰ) and (ⅱ) are trivial, we only need to prove (ⅲ) and (ⅳ). First consider the case $p\notin J$. Set

By Lemma 3.6 (ⅰ),

Notice that the degree of $G(x)$ is

where we use the fact that $\sum_{d\mid\frac{m_1}{p_{j_1}\dots p_{j_t}}}\phi(d) = \frac{m_1}{p_{j_1}\dots p_{j_r}}$. So $G(x)$ has $q^{\frac{n_1}{p_{j_1}\dots p_{j_t}}-1}$ simple roots. Similarly for the case $p\in J$, and we can get

The result follows.

Now we are in the position to prove our main theorem.

Proof of Theorem 1.3. Write $A_i = A_{p_i}(i = 1, \dots, k)$ for short. Let $\alpha\in \mathbb{F}_{q^{n}}\backslash(\bigcup_{i = 1}^{k}A_{i}\bigcup A)$. By Remark 3.4 (ii), we know that $\mathrm{Tr}(\alpha; n_1)\neq0$ and that the degree of the minimal polynomial of $\alpha$ over $\mathbb{F}_q$ is $n$. Since all the conjugates of $\alpha$ have the same property, namely, $\mathrm{Tr}(\alpha^{q^i}; n_1)\neq0$ and the degree of the minimal polynomial of $\alpha^{q^i}$ over $\mathbb{F}_q$ is $n$ for $i = 0, 1, \dots, n-1$, we have

We first consider the simplest two cases that $e_1 < e$ and $e_1 = e = 0$, in which Lemma 3.7 (iii) is not used that makes the calculation relatively easy. By the inclusion-exclusion principle and Lemma 3.7,

For a positive integer, let $\omega(d)$ denote the number of distinct prime factors of $d$. Recall $\mathfrak{P}(n) = \{p_{1}, p_{2}, \ldots, p_{k}\}$ and $m_1' = p_{1}\cdots p_{t}$. Hence the above equation can be rewritten as

Note that

By (3.10), (3.11) and (3.12), we get

Next we consider the more complicated case that $e_1 = e > 0$, in which Lemma 3.7 (ⅲ) is used that makes the calculation relatively lengthy. We omit some detail due to the similar deduction and notation as above. Note that $p_k = p$ in this case by assumption. By the inclusion-exclusion principle,

By Lemma 3.7,

and

It follows from (3.14), (3.15) and (3.16) that

Similar to (3.12), we have

By (3.10), (3.17) and (3.18), we get

Putting (3.13) and (3.19) together, we obtain

as desired.

Now suppose that $n_1 = 1$ in which $e_1 = 0$. So the case $e_1 = e > 0$ is excluded. For the case $e_1 = e = 0$ and $k = t$, since $t = 1$, we must have $k = 1$ and hence $n = 1$. By (3.20),

For the other cases, by (3.20) we get $N_q^*(n; 1) = \sum_{d|n}\mu(d)q^{\frac{n}{d}}/n = I_q(n)$.

Finally suppose that $n_1 = n$ in which $m_1 = m$ and $e = e_1$. There are two subcases: $e = e_1 = 0$ and $e = e_1 > 0$.

● If $e = e_1 = 0$, then $n = m = n_1 = m_1$, and by (3.20) it is easy to verify that

● If $e = e_1 > 0$, then $k = t+1$ and hence by (3.20),

The proof is complete.

4.   Some remarks

The main contribution of this paper is to provide a new proof to Theorem 1.1 and its generalizations. To be precise, based on the properties of linearized polynomials, we count the monic irreducible polynomials of degree $n$ over $\mathbb{F} _q$ with nozero $n_1$-traces, where $n_1$ is a divisor of $n$. Since $n_1$-traces have the close relationship with the roots (and hence the coefficients) of the associated polynomial, this approach may be adopted to deal with the other enumeration problems concerning the irreducible polynomials with the restricted coefficients in finite fields.

As one reviewer pointed out, the first two cases (i.e. $e_1 = e > 0$ and $k = t+1$, respectively, $e_1 = e = 0$ and $k = t$) in Theorem 1.3 only occur for $n = n_1$. Thus it remains to consider the case $n < n_1$, which can be deduced from the additive version of Hilbert's Theorem 90. However, if we drop out the restriction that the polynomials must be irreducible, i.e., allowing the degree of $\alpha$ in $\mathrm{Tr}(\alpha; n_1)$ to be less than $n$, our approach still works while Hilbert's Theorem 90 may not be valid again.

Acknowledgments

The authors sincerely thank the referees for their helpful comments which led to a substantial improvement of this paper. This work was jointly supported by the National Natural Science Foundation of China (Grant No. 11871291) and Ningbo Natural Science Foundation (Grant No. 2019A610035), and sponsored by the K. C. Wong Magna Fund in Ningbo University.

Conflict of interest

The authors declare that there is no conflict of interest.