Factorization Patterns in F_q [x]

Thomas Beatty, Nicole Legge

Department of Mathematics, Florida Gulf Coast University, Fort Myers, USA.

DOI: 10.4236/apm.2022.122006                

Abstract

The finite field F_q has q elements, where q = p^k for prime p and k∈N. Then F_q[x] is a unique factorization domain and its polynomials can be bijectively associated with their unique (up to order) factorizations into irreducibles. Such a factorization for a polynomial of degree n can be viewed as conforming to a specific template if we agree that factors with higher degree will be written before those with lower degree, and factors of equal degree can be written in any order. For example, a polynomial f(x) of degree n may factor into irreducibles and be written as (a)(b)(c), where deg a ≥ deg b ≥deg c. Clearly, the various partitions of n correspond to the templates available for these canonical factorizations and we identify the templates with the possible partitions. So if f(x) is itself irreducible over F_q, it would belong to the template [n], and if f(x) split over F_q, it would belong to the template [n] Our goal is to calculate the cardinalities of the sets of polynomials corresponding to available templates for general q and n. With this information, we characterize the associated probabilities that a randomly selected member of F_q[x] belongs to a given template. Software to facilitate the investigation of various cases is available upon request from the authors.

Keywords

Finite Field, Factorization, Polynomial, Degree, Irreducible, Splitting, Partition, Probability

1. Introduction

Our purpose is to develop probability estimates for factorization of polynomials over finite fields. In particular, we will explore the fine structure of patterns in which the irreducible factors appear. Since a polynomial ring over a field is a unique factorization domain, each polynomial has a representation as a product of irreducibles which is unique up to order of factors. To organize our combinatorial perspective, we may tighten up the uniqueness modulo order by imposing an additional minor condition on the degrees of the factors... higher degrees written before lower degrees, and equal degrees written interchangeably. Then any canonical factorization is unique up to the order of factors [1] [2] [3] of the same degree. Each factorization in this manner corresponds to a partition of the degree n of the factored polynomial belonging to ${\mathbb{F}}_q\left[x\right]$. The possible partitions of n induce in a natural way an equivalence relation on the family of irreducible factorizations for a given degree. The equivalence classes can be identified as templates for factorization, and the fact that they are mutually disjoint allows us to take a combinatorial approach to the problem of counting them. Our task is to present a method for enumerating these templates for general q and n, implement the method for selected small n, and use this data to calculate the probability that a randomly selected element of ${\mathbb{F}}_q\left[x\right]$ with specified degree belongs to a particular template. These will include, of course, both the probabilities for splitting and for being irreducible.

Some notation will help. For $q=p^k$ with p prime and $k\in \mathbb{N}$, the number of elements in ${\mathbb{F}}_q\left[x\right]$ of degree n will be denoted by $N\left(q,n\right)$. The number of elements in ${\mathbb{F}}_q\left[x\right]$ of degree n which are themselves irreducible will be denoted by $I\left(q,n\right)$. The number of elements in ${\mathbb{F}}_q\left[x\right]$ of degree n which are reducible will be denoted by $R\left(q,n\right)$. So $N\left(q,n\right)=I\left(q,n\right)+R\left(q,n\right)$. The classical probability that a random element of ${\mathbb{F}}_q\left[x\right]$ with degree n can be factored is

$\pi \left(q,n\right)=\frac{R\left(q,n\right)}{N\left(q,n\right)}$, and its complement is $\bar{\pi }\left(q,n\right)=\frac{I\left(q,n\right)}{N\left(q,n\right)}$. A partition $\lambda ⊢n$ defines a factorization template for a polynomial of degree n as follows. If $\lambda =\left[i_1,\cdots ,i_r\right]$, where $j<m$ implies $i_j\ge i_m$ and ${\displaystyle {\sum }_{j=1}^r}{i}_j=n$, the polynomials belonging to the $\lambda$ -template class all factor into r irreducibles, arranged from left to right in order of weakly decreasing degree $i_j$. The number of elements in ${\mathbb{F}}_q\left[x\right]$ of degree n which belong to $\lambda$ will be denoted by $N\left(q\mathrm{,}n\mathrm{,}\lambda \right)$. For example, the number of cubics over ${\mathbb{F}}_9$ that factor into linear times a quadratic factor would be $N\left(\mathrm{9,3,}\left[\mathrm{2,1}\right]\right)$. The probability that a random element of ${\mathbb{F}}_q\left[x\right]$ of degree n belongs to the template $\lambda$ is then $\beta \left(q,n,\lambda \right)=\frac{N\left(q,n,\lambda \right)}{N\left(q,n\right)}$. Note that $\beta \left(q\mathrm{,}n\mathrm{,}\left[\mathrm{1,1,}\cdots \mathrm{,1}\right]\right)$ is the probability that the random polynomial splits over ${\mathbb{F}}_q$, and $N\left(q\mathrm{,}n\mathrm{,}\left[n\right]\right)=I\left(q\mathrm{,}n\right)$, so $\beta \left(q,n,\left[n\right]\right)=\bar{\pi }\left(q,n\right)$ by definition, and we will consider $\left[n\right]$ an improper or trivial “factorization” template.

2. Monics Are Sufficient

Our life will be made easier in the sequel if we can work with monic polynomials instead of fully general ones. If $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ has degree n, then certainly its leading coefficient, say ${\alpha }_n$, is nonzero. It follows that ${\alpha }_n^{-1}f\left(x\right)=\hat{f}\left(x\right)$ is monic of degree n, and any factorization of $f\left(x\right)$ can be expressed as ${\alpha }_n$ times a factorization of $\hat{f}\left(x\right)$. None of the template structure is changed by this and our study of the possible patterns will not be affected. The probabilities that we calculate are based on ratios of cardinalities of sets of monic polynomials. Any such ratio will be the same for the corresponding general polynomials since the number of nonzero choices $\left(q-1\right)$ for leading coefficient will appear in both the numerator and denominator and hence cancel. From this point on, all polynomials will be assumed to be monic.

3. Irreducibles in ${\mathbb{F}}_q\left[x\right]$

A great help in enumerating the various templates is a formula originally due to Gauss, which extends to values of q which are prime powers. The number of ireducible polynomials of degee n over ${\mathbb{F}}_q$ is given by $I\left(q\mathrm{,}n\right)=\frac{1}{n}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>}n}}\mu \left(\frac{n}{d}\right)q^d$. Here $\mu \left(k\right)$ is the Möbius function and d is any divisor of the degree n. Recall $\mu \mathrm{<mo>\; :\; </mo>}\mathbb{N}\to \left\{-\mathrm{1,0,1}\right\}$ is defined by $\mu \left(1\right)=1$, $\mu \left(p_1\cdots p_m\right)$ for a product of distinct primes $p_i$ is 1 if m is even and −1 if it is odd, and finally $\mu \left(j\right)=0$ for any other $j\in \mathbb{N}$. This formula may be derived using Möbius inversion or more transparently using the Inclusion/Exclusion Principle [4]. For example, $I\left(3,5\right)=\frac{1}{5}{\displaystyle {\sum }_{d|n}}\mu \left(\frac{5}{d}\right)3^d=\frac{1}{5}\left[\mu \left(5\right)3^1+\mu \left(1\right)3^5\right]=48$. It is worth noting that if n itself is prime and $q=p^k$, then $I\left(q,n\right)=\frac{1}{n}\left[\mu \left(1\right)q^n+\mu \left(n\right)q^1\right]=\frac{1}{n}\left[p^{kn}-p^k\right]$. It is also apparent that the numbers $I\left(q,n\right)$, given immediately by the extended Gauss formula, can in principle be recovered for a fixed q and any n by an obvious bootstrapping argument starting with degree $n=2$.

4. Motivating Example

Before we explore the general method, let us illustrate the approach by determining the populations and corresponding probabilities for all the factorization templates of quartics over ${\mathbb{F}}_q\left[x\right]$. First, the total number of quartics $N\left(q,4\right)=q^4$, and the Gauss formula for $n=4$ yields

$I\left(q,4\right)=\frac{1}{4}\left(\mu \left(1\right)q^4+\mu \left(2\right)q^2+\mu \left(4\right)q\right)=\frac{1}{4}\left(q^4-q^2\right)$. There are four non-trivial templates: $\left[\mathrm{1,1,1,1}\right]$, $\left[\mathrm{2,1,1}\right]$, $\left[\mathrm{2,2}\right]$, and $\left[\mathrm{3,1}\right]$. For the splitting template $\left[\mathrm{1,1,1,1}\right]$, corresponding to the factorization $\left(x-r_1\right)\left(x-r_2\right)\left(x-r_3\right)\left(x-r_4\right)$, there are four zeroes to be selected with replacement from q field values available. This yields $N\left(q,4,\left[1,1,1,1\right]\right)=\left(\left(\begin{array}{c}q\\ 4\end{array}\right)\right)=\left(\begin{array}{c}q+3\\ 4\end{array}\right)=\frac{q^4+6q^3+11q^2+6q}{24}$ possibilities including all various configurations of multiple zeroes. For the $\left[\mathrm{2,1,1}\right]$ template, corresponding to the factorization $P_2\left(x\right)\left(x-r_1\right)\left(x-r_2\right)$, where $P_2\left(x\right)$ is an irreducible quadratic, there are $I\left(q\mathrm{,2}\right)=\frac{q^2-q}{2}$ possibilities from the Gauss formula for $n=2$. Also there are $\left(\left(\begin{array}{c}q\\ 2\end{array}\right)\right)=\left(\begin{array}{c}q+1\\ 2\end{array}\right)=\frac{q^2+q}{2}$ possibilities for selecting two zeroes with replacement. The number of total selections for the $\left[\mathrm{2,1,1}\right]$ template is then $\frac{q^4-q^2}{4}$. Moving to the $\left[\mathrm{2,2}\right]$ template, we re-use the multiset formula for two factors, but now instead of q choices among field values we have $I\left(q\mathrm{,2}\right)$ choices among the available quadratic irreducibles. This gives $\left(\left(\begin{array}{c}I\left(q,2\right)\\ 2\end{array}\right)\right)=\frac{{\left[I\left(q,2\right)\right]}^2+I\left(q,2\right)}{2}=\frac{q^4-2q^3+3q^2-2q}{8}$ choices for the two ireducible quadratics, again with replacement. Being able to use the same multiset formulas repeatedly will save a lot of work for the higher degree cases. Finally, the $\left[\mathrm{3,1}\right]$ template is the easiest to enumerate. Again by the Gauss formula there are $I\left(q,3\right)=\frac{1}{3}\left(q^3-q\right)$ choices for the irreducible cubic and q choices for the linear term, giving $\frac{q^4-q^2}{3}$ possibilities for this template. Summarizing:

1) $N\left(q\mathrm{,4}\right)=q^4$

2) $I\left(q,4\right)=N\left(q,4,\left[4\right]\right)=\frac{1}{4}\left(q^4-q^2\right)$

3) $N\left(q\mathrm{,4,}\left[\mathrm{1,1,1,1}\right]\right)\mathrm{<mo>\; =\; </mo>}\frac{q^4+6q^3+11q^2+6q}{24}$

4) $N\left(q\mathrm{,4,}\left[\mathrm{2,1,1}\right]\right)=\frac{q^4-q^2}{4}$

5) $N\left(q\mathrm{,4,}\left[\mathrm{2,2}\right]\right)=\frac{q^4-2q^3+3q^2-2q}{8}$

6) $N\left(q\mathrm{,4,}\left[\mathrm{3,1}\right]\right)=\frac{1}{3}\left(q^4-q^2\right)$

We verify ${\displaystyle {\sum }_{\lambda ⊢4}}N\left(q\mathrm{,4,}\lambda \right)=N\left(q\mathrm{,4}\right)$, and after computing the corresponding probability ratios, we have shown:

Proposition 1

If $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ and $\mathrm{deg}f=4$, then: $\pi \left(q\mathrm{,4}\right)=\frac{3}{4}+\frac{1}{4q^2}$, $\bar{\pi }\left(q\mathrm{,4}\right)=\frac{1}{4}-\frac{1}{4q^2}$, $\beta \left(q\mathrm{,4,}\left[\mathrm{1,1,1,1}\right]\right)=\frac{1}{24}+\frac{1}{4q}+\frac{11}{24q^2}+\frac{1}{4q^3}$, $\beta \left(q\mathrm{,4,}\left[\mathrm{2,1,1}\right]\right)=\frac{1}{4}-\frac{1}{4q^2}$, $\beta \left(q\mathrm{,4,}\left[\mathrm{2,2}\right]\right)=\frac{1}{8}-\frac{1}{4q}+\frac{3}{8q^2}-\frac{1}{4q^3}$, $\beta \left(q\mathrm{,4,}\left[\mathrm{3,1}\right]\right)=\frac{1}{3}-\frac{1}{3q^2}$.

Proof. Divide the template enumerations by $q^4$. Done. $■$

5. General Case

All of the complications typical of the general case are on display in the preceding quartic example. We have seen that the Gauss formula gives a straightforward way to obtain $I\left(q,n\right)$. The multiset number counts up the ways a polynomial could split, and the multiset number applied to the various $I\left(q,n\right)$ in place of q gives the number of ways a multiplicity of irreducible factors of common degree can appear in a factorization template.

Consider the family of polynomials of degree n in ${\mathbb{F}}_q\left[x\right]$. Suppose $f\left(x\right)$ belongs to this family and $f\left(x\right)={\displaystyle {\prod }_{j=1}^r}{g}_j\left(x\right)$, where the $g_j\left(x\right)$ are written in order of (weakly) decreasing degree from left to right. We say $f\left(x\right)$ conforms to the template $\lambda$ if $\lambda =\left[i_1,\cdots ,i_j,\cdots ,i_r\right]$ is a partition of n and $i_j=\mathrm{deg}{g}_j\left(x\right)$. In general, there will be repeated degrees among the $g_j\left(x\right)$ corresponding to repeated parts $i_j$ in the partition of n. Let $\left\{{\delta }_1\mathrm{,}\cdots \mathrm{,}{\delta }_t\right\}$ be the set of distinct degrees of the factors of $f\left(x\right)$, and let $m_k$ be the multiplicity of each ${\delta }_k$, so that ${\displaystyle {\sum }_{k=1}^t}{m}_k{\delta }_k=n$. For example, if $\lambda =\left[\mathrm{3,2,2,2,1,1}\right]$, ${\delta }_1=3$, ${\delta }_2=2$, and ${\delta }_3=1$, then $m_1=1$, $m_2=3$, and $m_1=2$.

Lemma 1

Let $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ with $\mathrm{deg}f\left(x\right)=n$ and $f\left(x\right)={\displaystyle {\prod }_{j=1}^r}{g}_j\left(x\right)$ with the preceding setup. If $m_k$ is the multiplicity of the degree ${\delta }_k$, then the number of canonical factorizations of $f\left(x\right)$ conforming to the template

$\lambda =\left[i_1,\cdots ,i_j,\cdots ,i_r\right]$ is $N\left(q,n,\lambda \right)={\displaystyle {\prod }_{k=1}^t}\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$.

Proof. The multiset number $\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$ is the number of ways a set of $m_k$ irreducible factors of degree ${\delta }_k$ can be chosen with replacement from the $I\left(q,{\delta }_k\right)$ irreducible polynomials of degree ${\delta }_k$ available to fill the corresponding positions in the template. The choices for each ${\delta }_k$ are mutually independent, so the product over all t distinct degrees that occur in the template gives the total number of possible configurations overall, namely $N\left(q,n,\lambda \right)={\displaystyle {\prod }_{k=1}^t}\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$. $■$

So for each partition of the degree n: 1) we identify the distinct parts that appear in each partition (these are the distinct degrees that appear in the template), 2) find their multiplicity, and 3) compute the product in the lemma. We can now state the final result.

Proposition 2

The probability that a randomly selected polynomial $f\left(x\right)$ of degree n over ${\mathbb{F}}_q$

1) cannot be factored is $\bar{\pi }\left(q,n\right)=\frac{1}{n}{\displaystyle {\sum }_{d|n}}\mu \left(\frac{n}{d}\right)q^{d-n}$.

2) can be factored is $\pi \left(q,n\right)=1-\bar{\pi }\left(q,n\right)$.

3) can be factored as ${\displaystyle {\prod }_{j=1}^r}{g}_j\left(x\right)$, where $\mathrm{deg}{g}_j\left(x\right)=i_j$ belongs to the partition $\lambda =\left[i_1,\cdots ,i_j,\cdots ,i_r\right]$ of n, is $\beta \left(q,n,\lambda \right)=\frac{1}{q^n}{\displaystyle {\prod }_{k=1}^t}\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$.

Proof. 1) The number $N\left(q\mathrm{,}n\right)$ of (monic) polynomials over ${\mathbb{F}}_q$ is $q^n$. The number $I\left(q\mathrm{,}n\right)$ of irreducible polynomials over ${\mathbb{F}}_q$ is $\frac{1}{n}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>}n}}\mu \left(\frac{n}{d}\right)q^d$. So $\bar{\pi }\left(q,n\right)=\frac{I\left(q,n\right)}{N\left(q,n\right)}=\frac{1}{n}{\displaystyle {\sum }_{d|n}}\mu \left(\frac{n}{d}\right)q^{d-n}$.

2) Complementary probability.

3) The number $N\left(q\mathrm{,}n\mathrm{,}\lambda \right)$ of factorizations of $f\left(x\right)$ conforming to the template $\lambda$ is $N\left(q,n,\lambda \right)={\displaystyle {\prod }_{k=1}^t}\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$ by the Lemma, hence

$\beta \left(q,n,\lambda \right)=\frac{1}{q^n}{\displaystyle {\prod }_{k=1}^t}\left(\left(\begin{array}{c}I\left(q,{\delta }_k\right)\\ m_k\end{array}\right)\right)$. $■$

6. Low Degree Cases

We now establish probability formulas for $n=2$ and $n=3$ (see $n=4$ above), and derive the multiset formulas up to $n=9$ to allow the determination of $\beta \left(q\mathrm{,}n\mathrm{,}\lambda \right)$ for specific $\lambda ⊢10$. Since there are 42 partitions of 10, anything more than a “surgical” calculation for a particular $\lambda$ or two seems impractical.

Proposition 3

1) If $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ with $\mathrm{deg}f\left(x\right)=2$, then $\pi \left(q\mathrm{,2}\right)=\beta \left(q\mathrm{,2,}\left[\mathrm{1,1}\right]\right)=\frac{1}{2}+\frac{1}{2q}$ and $\bar{\pi }\left(q\mathrm{,2}\right)=\beta \left(q\mathrm{,2,}\left[2\right]\right)=\frac{1}{2}-\frac{1}{2q}$.

2) If $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ with $\mathrm{deg}f\left(x\right)=3$, then $\pi \left(q\mathrm{,3}\right)=\frac{2}{3}+\frac{1}{3q^2}$, $\bar{\pi }\left(q\mathrm{,3}\right)=\frac{1}{3}-\frac{1}{3q^2}$, $\beta \left(q\mathrm{,3,}\left[\mathrm{1,1,1}\right]\right)=\frac{1}{6}+\frac{1}{2q}+\frac{1}{3q^2}$, and $\beta \left(q\mathrm{,3,}\left[\mathrm{2,1}\right]\right)=\frac{1}{2}-\frac{1}{2q}$.

Proof. 1) From Proposition 2, $\bar{\pi }\left(q\mathrm{,2}\right)=\frac{1}{2}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>2}}}\mu \left(\frac{2}{d}\right)q^{d-2}=\frac{1}{2}-\frac{1}{2q}$. Now the only non-trivial template is $\left[\mathrm{1,1}\right]$, so $\pi \left(q\mathrm{,2}\right)=\beta \left(q\mathrm{,2,}\left[\mathrm{1,1}\right]\right)=1-\bar{\pi }\left(q\mathrm{,2}\right)=\frac{1}{2}+\frac{1}{2q}$.

2) Likewise, $\bar{\pi }\left(q,3\right)=\frac{1}{3}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>3}}}\mu \left(\frac{3}{d}\right)q^{d-3}=\frac{1}{3}-\frac{1}{3q^2}$, and it follows that $\pi \left(q\mathrm{,3}\right)=1-\left(\frac{1}{3}-\frac{1}{3q^2}\right)=\frac{2}{3}+\frac{1}{3q^2}$. There are two proper templates: $\left[\mathrm{1,1,1}\right]$ and $\left[\mathrm{2,1}\right]$. Now $N\left(q\mathrm{,3,}\left[\mathrm{1,1,1}\right]\right)=\left(\left(\begin{array}{c}q\\ 3\end{array}\right)\right)=\frac{q^3}{6}+\frac{q^2}{2}+\frac{q}{3}$, so $\beta \left(q\mathrm{,3,}\left[\mathrm{1,1,1}\right]\right)=\frac{N\left(q\mathrm{,3,}\left[\mathrm{1,1,1}\right]\right)}{N\left(q\mathrm{,3}\right)}=\frac{1}{q^3}\left(\frac{q^3}{6}+\frac{q^2}{2}+\frac{q}{3}\right)=\frac{1}{6}+\frac{1}{2q}+\frac{1}{3q^2}$. Also, using $I\left(q\mathrm{,2}\right)=q^2\bar{\pi }\left(q\mathrm{,2}\right)$ from the quadratic case,

$N\left(q\mathrm{,3,}\left[\mathrm{2,1}\right]\right)=\left(\frac{1}{2}\left(q^2-q\right)\right)\left(q\right)=\frac{1}{2}{q}^3-\frac{1}{2}{q}^2$, so $\beta \left(q\mathrm{,3,}\left[\mathrm{2,1}\right]\right)=\frac{1}{2}-\frac{1}{2q}$. $■$

Observe from Propositions 1 and 3 that most of the probability that $f\left(x\right)$ factors at all seems to come from templates that are heavy with high degree factors. The flip side of this is that as n increases for a fixed q the probability of $f\left(x\right)$ splitting or at least factoring into low degree pieces becomes smaller. We comment on this more fully in the Epilogue.

7. Computational Aids

Following are several computational aids for higher degree cases.

Enumerators for Multiple Factors of Same Degree

In the notation of Lemma 1 suppose there are exactly $m_k$ irreducible polynomials of degree ${\delta }_k$ in a particular factorization of $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$. As noted in the Lemma, the pool of polynomials available to make $m_k$ such selections is $I\left(q\mathrm{,}{\delta }_k\right)$. It follows that there are $\left(\left(\begin{array}{c}I\left(q\mathrm{,}{\delta }_k\right)\\ m_k\end{array}\right)\right)$ ways to do this. To simplify the entries, let us denote $I\left(q\mathrm{,}{\delta }_k\right)$ by x.

$m_k=2\left(\left(\begin{array}{c}x\\ 2\end{array}\right)\right)=\frac{1}{2}{x}^2+\frac{1}{2}x$

$m_k=3\left(\left(\begin{array}{c}x\\ 3\end{array}\right)\right)=\frac{1}{6}{x}^3+\frac{1}{2}{x}^2+\frac{1}{3}x$

$m_k=4\left(\left(\begin{array}{c}x\\ 4\end{array}\right)\right)=\frac{1}{24}{x}^4+\frac{1}{4}{x}^3+\frac{11}{24}{x}^2+\frac{1}{4}x$

$m_k=5\left(\left(\begin{array}{c}x\\ 5\end{array}\right)\right)=\frac{1}{120}{x}^5+\frac{1}{12}{x}^4+\frac{7}{24}{x}^3+\frac{5}{12}{x}^2+\frac{1}{5}x$

$m_k=6\left(\left(\begin{array}{c}x\\ 6\end{array}\right)\right)=\frac{1}{720}{x}^6+\frac{1}{48}{x}^5+\frac{17}{144}{x}^4+\frac{5}{16}{x}^3+\frac{137}{360}{x}^2+\frac{1}{6}x$

$m_k=7\left(\left(\begin{array}{c}x\\ 7\end{array}\right)\right)=\frac{1}{5040}{x}^7+\frac{1}{240}{x}^6+\frac{5}{144}{x}^5+\frac{7}{48}{x}^4+\frac{29}{90}{x}^3+\frac{7}{20}{x}^2+\frac{1}{7}x$

$\begin{array}{l}{m}_k=8\left(\left(\begin{array}{c}x\\ 8\end{array}\right)\right)=\frac{1}{40320}{x}^8+\frac{1}{1440}{x}^7+\frac{23}{2880}{x}^6+\frac{7}{144}{x}^5+\frac{967}{5760}{x}^4\\ +\frac{469}{1440}{x}^3+\frac{363}{1120}{x}^2+\frac{1}{8}x\end{array}$

$\begin{array}{l}{m}_k=9\left(\left(\begin{array}{c}x\\ 9\end{array}\right)\right)=\frac{1}{362880}{x}^9+\frac{1}{10080}{x}^8+\frac{13}{8640}{x}^7+\frac{1}{80}{x}^6+\frac{1069}{17280}{x}^5\\ +\frac{89}{480}{x}^4\frac{29531}{90720}{x}^3+\frac{761}{2520}{x}^2+\frac{1}{9}x\end{array}$

Enumerators for Irreducible Polynomials over ${\mathbb{F}}_q$ by Degree

Here are the expressions for $I\left(q\mathrm{,}{\delta }_k\right)$ with $1\le {\delta }_k\le 9$ via the Gauss formula $I\left(q,{\delta }_k\right)=\frac{1}{{\delta }_k}{\displaystyle {\sum }_{d|{\delta }_k}}\mu \left(\frac{{\delta }_k}{d}\right)q^d$. These should be substituted as appropriate for x in the above.

1) $I\left(q,1\right)=q$

2) $I\left(q,2\right)=\frac{1}{2}\left(q^2-q\right)$

3) $I\left(q,3\right)=\frac{1}{3}\left(q^3-q\right)$

4) $I\left(q,4\right)=\frac{1}{4}\left(q^4-q^2\right)$

5) $I\left(q,5\right)=\frac{1}{5}\left(q^5-q\right)$

6) $I\left(q,6\right)=\frac{1}{6}\left(q^6-q^3-q^2+q\right)$

7) $I\left(q,7\right)=\frac{1}{7}\left(q^7-q\right)$

8) $I\left(q,8\right)=\frac{1}{8}\left(q^8-q^4\right)$

9) $I\left(q,9\right)=\frac{1}{9}\left(q^9-q^3\right)$

8. A Higher Degree Example

To illustrate the types of questions that can be answered with the machinery we have developed, consider the following. Suppose we are given a random $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ with $\mathrm{deg}f\left(x\right)=7$.

1) What is the probability that $f\left(x\right)$ splits?

2) What is the probability that it has three irreducible quadratic factors?

3) If it has an irreducible quintic factor, what is the probability that it also has a zero in ${\mathbb{F}}_q$ ?

Solutions:

1) $N\left(q,7\right)=q^7$. Also $\left(\left(\begin{array}{c}I\left(q,1\right)\\ 7\end{array}\right)\right)=\frac{1}{5040}{q}^7+\frac{1}{240}{q}^6+\frac{5}{144}{q}^5+\frac{7}{48}{q}^4+\frac{29}{90}{q}^3+\frac{7}{20}{q}^2+\frac{1}{7}q$. Then the splitting probability is $\beta \left(q\mathrm{,7,}\left[\mathrm{1,1,1,1,1,1,1}\right]\right)=\frac{1}{5040}+\frac{1}{240q}+\frac{5}{144q^2}+\frac{7}{48q^3}+\frac{29}{90q^4}+\frac{7}{20q^5}+\frac{1}{7q^6}$, which is miniscule.

2) If $f\left(x\right)$ has three irreducible quadratic factors, then the remaining factor must be linear. So $\begin{array}{l}\beta \left(q\mathrm{,7,}\left[\mathrm{2,2,2,1}\right]\right)=\left(\frac{1}{q^7}\right)\left(\left(\begin{array}{c}I\left(q\mathrm{,2}\right)\\ 3\end{array}\right)\right)\left(\left(\begin{array}{c}I\left(q\mathrm{,1}\right)\\ 1\end{array}\right)\right)\\ =\left(\frac{1}{q^7}\right)\left(\frac{1}{6}{\left(\frac{q^2-q}{2}\right)}^3+\frac{1}{2}{\left(\frac{q^2-q}{2}\right)}^2+\frac{1}{3}\left(\frac{q^2-q}{2}\right)\right)\left(q\right)\\ =\frac{1}{48}-\frac{1}{16q}+\frac{3}{16q^2}-\frac{13}{48q^3}+\frac{7}{24q^4}-\frac{1}{6q^5}\end{array}$. For perspective, this would be $\frac{1}{64}$ for $q=2$. The only irreducible quadratic over ${\mathbb{F}}_2$ is $x^2+x+1$, so in this case $f\left(x\right)$ would have to be either $x{\left(x^2+x+1\right)}^3$ or $\left(x-1\right){\left(x^2+x+1\right)}^3$. Since there are $2^7=128$ possible seventh degree polynomials over ${\mathbb{F}}_2$, and $\frac{2}{128}=\frac{1}{64}$, we have a hands-on confirmation of our result.

3) The templates that admit a quintic are $\left[\mathrm{5,2}\right]$ and $\left[\mathrm{5,1,1}\right]$. We need to parse the details of these two templates to compute a conditional probability. First, $N\left(q\mathrm{,7,}\left[\mathrm{5,2}\right]\right)=\left(I\left(q\mathrm{,5}\right)\right)\left(I\left(q\mathrm{,2}\right)\right)=\left(\frac{q^5-q}{5}\right)\left(\frac{q^2-q}{2}\right)=\frac{q^7-q^6-q^3+q^2}{10}$. Next, $N\left(q,7,\left[5,1,1\right]\right)=\left(I\left(q,5\right)\right)\left(\left(\begin{array}{c}q\\ 2\end{array}\right)\right)=\left(\frac{q^5-q}{5}\right)\left(\frac{q^2+q}{2}\right)=\frac{q^7+q^6-q^3-q^2}{10}$. Now the total number of configurations featuring a quintic is $N\left(q,7,\left[5,2\right]\right)+N\left(q,7,\left[5,1,1\right]\right)=\frac{q^7-q^3}{5}$. It follows that the conditional probability of $f\left(x\right)$ having a zero, given that it has an irreducible quintic factor, is $\frac{N\left(q\mathrm{,7,}\left[\mathrm{5,1,1}\right]\right)}{N\left(q\mathrm{,7,}\left[\mathrm{5,1,1}\right]\right)+N\left(q\mathrm{,7,}\left[\mathrm{5,2}\right]\right)}=\frac{1}{2}+\frac{1}{2q}$. This should not be surprising, since once the quintic “has occurred” in the factorization, the remaining situation is that of factoring the residual degree available, which parallels the derivation in Proposition 3(1) exactly.

9. Epilogue

We can easily draw several conclusions regarding the limit behavior of three important probability estimates.

Proposition 4

Suppose $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ and $\mathrm{deg}f\left(x\right)=n$. Then:

1) ${\lim }_{q\to \infty }\bar{\pi }\left(q\mathrm{,}n\right)=\frac{1}{n}$ and ${\lim }_{q\to \infty }\pi \left(q\mathrm{,}n\right)=\frac{n-1}{n}$.

2) ${\lim }_{q\to \infty }\beta \left(q\mathrm{,}n\mathrm{,}\left[\mathrm{1,1,}\cdots \mathrm{,1}\right]\right)=\frac{1}{n\mathrm{<mo>\; !\; </mo>}}$.

Proof. 1) $N\left(q\mathrm{,}n\right)=q^n$. By the Gauss formula, $I\left(q\mathrm{,}n\right)=\frac{1}{n}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>}n}}\mu \left(\frac{n}{d}\right)q^d$. Then $\bar{\pi }\left(q,n\right)=\frac{1}{n}{\displaystyle {\sum }_{d\mathrm{<mo>\; |\; </mo>}n}}\mu \left(\frac{n}{d}\right)q^{d-n}$. Now $d-n<0$ unless $d=n$, in which case the term contributes $\frac{1}{n}\mu \left(1\right)=\frac{1}{n}$ to the sum. For all other divisors of n, since $\left|\mu \left(\frac{n}{d}\right)q^{d-n}\right|$ is at most $O\left(\frac{1}{q^{n/2}}\right)$, and ${\lim }_{q\to \infty }\frac{1}{q^{n/2}}=0$, we have ${\lim }_{q\to \infty }\bar{\pi }\left(q,n\right)=\frac{1}{n}$. It follows that ${\lim }_{q\to \infty }\pi \left(q,n\right)=\frac{n-1}{n}$.

2)

$R\left(q,n,\left[1,1,\cdots ,1\right]\right)=\left(\left(\begin{array}{c}q\\ n\end{array}\right)\right)=\left(\begin{array}{c}q+n-1\\ n\end{array}\right)=\frac{1}{n!}{\displaystyle {\prod }_{k=0}^{n-1}}\left(q+k\right)=\frac{1}{n!}\left(q^n+O\left(q^{n-1}\right)\right)$.

Hence $\beta \left(q,n,\left[1,1,\cdots ,1\right]\right)=\frac{1}{n!}+O\left(\frac{1}{q}\right)$ and since ${\lim }_{q\to \infty }\frac{1}{q}=0$, the result follows. $■$

The result in (1) is dramatically different from that of factoring over $\mathbb{Z}$, which becomes less and less likely as the absolute bound on coefficients increases [5]. If q is very large, it may seem that the chances for a proper factorization of $f\left(x\right)$ would be about as slim as if the factorization were to be done over $\mathbb{Z}$. This is not the case, moreover, it becomes even more counterintuitive as q approaches infinity and the likelihood of factorability approaches 1. The companion result in (2) shows that the chance a randomly selected polynomial splits over ${\mathbb{F}}_q$ degrades very rapidly as degree and field cardinality grow.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Dummit, D.S. and Foote, R.M. (2003) Abstract Algebra. 3rd Edition, John Wiley and Sons, Inc., Hoboken, NJ.
[2]	Gallian, J.A. (2010) Contemporary Abstract Algebra. 7th Edition, Brooks-Cole/Cengage Learning, Belmont, CA.
[3]	Hungerford, T.W. (1974) Algebra. Springer Verlag, Berlin. https://doi.org/10.1007/978-1-4612-6101-8_4
[4]	Chebolu, S.K. and Mináč, J. (2011) Counting Irreducible Polynomials over Finite Fields Using the Inclusion-Exclusion Principle. Mathematics Magazine, 84, 369-371. https://doi.org/10.4169/math.mag.84.5.369
[5]	Beatty, T. and von Linden, G. (2020) On Conditional Probabilities of Factoring Quadratics. Advances in Pure Mathematics, 10, 114-124. https://doi.org/10.4236/apm.2020.103008