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
. 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
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
with p prime and
, the number of elements in
of degree n will be denoted by
. The number of elements in
of degree n which are themselves irreducible will be denoted by
. The number of elements in
of degree n which are reducible will be denoted by
. So
. The classical probability that a random element of
with degree n can be factored is
, and its complement is
. A partition
defines a factorization template for a polynomial of degree n as follows. If
, where
implies
and
, the polynomials belonging to the
-template class all factor into r irreducibles, arranged from left to right in order of weakly decreasing degree
. The number of elements in
of degree n which belong to
will be denoted by
. For example, the number of cubics over
that factor into linear times a quadratic factor would be
. The probability that a random element of
of degree n belongs to the template
is then
. Note that
is the probability that the random polynomial splits over
, and
, so
by definition, and we will consider
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
has degree n, then certainly its leading coefficient, say
, is nonzero. It follows that
is monic of degree n, and any factorization of
can be expressed as
times a factorization of
. 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
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
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
is given by
. Here
is the Möbius function and d is any divisor of the degree n. Recall
is defined by
,
for a product of distinct primes
is 1 if m is even and −1 if it is odd, and finally
for any other
. This formula may be derived using Möbius inversion or more transparently using the Inclusion/Exclusion Principle [4]. For example,
. It is worth noting that if n itself is prime and
, then
. It is also apparent that the numbers
, 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
.
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
. First, the total number of quartics
, and the Gauss formula for
yields
. There are four non-trivial templates:
,
,
, and
. For the splitting template
, corresponding to the factorization
, there are four zeroes to be selected with replacement from q field values available. This yields
possibilities including all various configurations of multiple zeroes. For the
template, corresponding to the factorization
, where
is an irreducible quadratic, there are
possibilities from the Gauss formula for
. Also there are
possibilities for selecting two zeroes with replacement. The number of total selections for the
template is then
. Moving to the
template, we re-use the multiset formula for two factors, but now instead of q choices among field values we have
choices among the available quadratic irreducibles. This gives
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
template is the easiest to enumerate. Again by the Gauss formula there are
choices for the irreducible cubic and q choices for the linear term, giving
possibilities for this template. Summarizing:
1)
2)
3)
4)
5)
6)
We verify
, and after computing the corresponding probability ratios, we have shown:
Proposition 1
If
and
, then:
,
,
,
,
,
.
Proof. Divide the template enumerations by
. 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
. The multiset number counts up the ways a polynomial could split, and the multiset number applied to the various
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
. Suppose
belongs to this family and
, where the
are written in order of (weakly) decreasing degree from left to right. We say
conforms to the template
if
is a partition of n and
. In general, there will be repeated degrees among the
corresponding to repeated parts
in the partition of n. Let
be the set of distinct degrees of the factors of
, and let
be the multiplicity of each
, so that
. For example, if
,
,
, and
, then
,
, and
.
Lemma 1
Let
with
and
with the preceding setup. If
is the multiplicity of the degree
, then the number of canonical factorizations of
conforming to the template
is
.
Proof. The multiset number
is the number of ways a set of
irreducible factors of degree
can be chosen with replacement from the
irreducible polynomials of degree
available to fill the corresponding positions in the template. The choices for each
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
.
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
of degree n over
1) cannot be factored is
.
2) can be factored is
.
3) can be factored as
, where
belongs to the partition
of n, is
.
Proof. 1) The number
of (monic) polynomials over
is
. The number
of irreducible polynomials over
is
. So
.
2) Complementary probability.
3) The number
of factorizations of
conforming to the template
is
by the Lemma, hence
.
6. Low Degree Cases
We now establish probability formulas for
and
(see
above), and derive the multiset formulas up to
to allow the determination of
for specific
. Since there are 42 partitions of 10, anything more than a “surgical” calculation for a particular
or two seems impractical.
Proposition 3
1) If
with
, then
and
.
2) If
with
, then
,
,
, and
.
Proof. 1) From Proposition 2,
. Now the only non-trivial template is
, so
.
2) Likewise,
, and it follows that
. There are two proper templates:
and
. Now
, so
. Also, using
from the quadratic case,
, so
.
Observe from Propositions 1 and 3 that most of the probability that
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
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
irreducible polynomials of degree
in a particular factorization of
. As noted in the Lemma, the pool of polynomials available to make
such selections is
. It follows that there are
ways to do this. To simplify the entries, let us denote
by x.
Enumerators for Irreducible Polynomials over
by Degree
Here are the expressions for
with
via the Gauss formula
. These should be substituted as appropriate for x in the above.
1)
2)
3)
4)
5)
6)
7)
8)
9)
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
with
.
1) What is the probability that
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
?
Solutions:
1)
. Also
. Then the splitting probability is
, which is miniscule.
2) If
has three irreducible quadratic factors, then the remaining factor must be linear. So
. For perspective, this would be
for
. The only irreducible quadratic over
is
, so in this case
would have to be either
or
. Since there are
possible seventh degree polynomials over
, and
, we have a hands-on confirmation of our result.
3) The templates that admit a quintic are
and
. We need to parse the details of these two templates to compute a conditional probability. First,
. Next,
. Now the total number of configurations featuring a quintic is
. It follows that the conditional probability of
having a zero, given that it has an irreducible quintic factor, is
. 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
and
. Then:
1)
and
.
2)
.
Proof. 1)
. By the Gauss formula,
. Then
. Now
unless
, in which case the term contributes
to the sum. For all other divisors of n, since
is at most
, and
, we have
. It follows that
.
2)
.
Hence
and since
, the result follows.
The result in (1) is dramatically different from that of factoring over
, 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
would be about as slim as if the factorization were to be done over
. 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
degrades very rapidly as degree and field cardinality grow.