The Degree of the Splitting Field of a Random
Polynomial over a Finite Field
John D. Dixon and Daniel Panario
School of Mathematics and Statistics
Carleton University, Ottawa, Canada
{jdixon,daniel}@math.carleton.ca
Submitted: Aug 30, 2004; Accepted: Sep 22, 2004; Published: Sep 30, 2004
Mathematics Subject Classifications: 11T06, 20B99
Abstract
The asymptotics of the order of a random permutation have been widely studied.
P. Erd¨os and P. Tur´an proved that asymptotically the distribution of the logarithm
of the order of an element in the symmetric group Snis normal with mean 1
2(log n)2
and variance 1
3(log n)3. More recently R. Stong has shown that the mean of the order
is asymptotically exp(Cpn/ log n+O(√nlog log n/ log n)) where C=2.99047 ....
We prove similar results for the asymptotics of the degree of the splitting field of a
random polynomial of degree nover a finite field.
1 Introduction
We consider the following problem. Let Fqdenote a finite field of size qand consider the
set Pn(q) of monic polynomials of degree nover Fq. What can we say about the degree
over Fqof the splitting field of a random polynomial from Pn(q)? Because we are dealing
with finite fields and there is only one field of each size, it is well known that the degree
of the splitting field of f(X)∈P
n(q) is the least common multiple of the degrees of the
irreducible factors of f(X)overFq. Thus the problem can be rephrased as follows.
Let λbe a partition of n(denoted λ⊢n)andwriteλin the form 1k12k2...nknwhere
λhas ksparts of size s. We shall say that a polynomial is of shape λif it has ksirreducible
factors of degree sfor each s.Letw(λ, q) be the proportion of polynomials in Pn(q)which
have shape λ. If we define m(λ) to be the least common multiple of the sizes of the parts
of λ, then the degree of the splitting field over Fqof a polynomial of shape λis m(λ). The
average degree of a splitting field is given by
En(q):=X
λ⊢n
w(λ, q)m(λ).
the electronic journal of combinatorics 11 (2004), #R70 1
An analogous problem arises in the symmetric group Sn.ApermutationinSnis of type
λ=1k12k2...nknif it has exactly kscycles of length sfor each s, and its order is then
equal to m(λ). If w(λ) denotes the proportion of permutations in Snwhich are of type
λ, then the average order of a permutation in Snis equal to
En:= X
λ⊢n
w(λ)m(λ).
We can think of m(λ) as a random variable where λranges over the partitions of nand
the probability of λis w(λ, q)andw(λ) in the respective cases.
Properties of the random variable m(λ) (and related random variables) under the
distribution w(λ) have been studied by a number of authors, notably by Erd¨os and Tur´an
in a series of papers [1, 2, 3] and [4]. In particular, the main theorem of [3] shows that in
this case the distribution of log m(λ) is approximated by a normal distribution with mean
1
2(log n)2and variance 1
3(log n)3in a precise sense. In our notation the theorem reads as
follows. For each real xdefine
Ψn(x):=λ⊢n|log m(λ)≤1
2(log n)2+x
√3(log n)3/2.
Then for each x0>0:
X
λ∈Ψn(x)
w(λ)→1
√2πZx
−∞
e−t2/2dt as n→∞uniformly for x∈[−x0,x
0].
In particular, the mean of the random variable log m(λ) is asymptotic to 1
2(log n)2, but
this does not imply that log En(the log of the mean of m(λ)) is asymptotic to 1
2(log n)2
and indeed it is much larger. The problem of estimating Enwas raised in [4], and the
first asymptotic expression for log Enwas obtained by Goh and Schmutz [6]. The result
of Goh and Schmutz was refined by Stong [9] who showed that
log En=Crn
log n+O√nlog log n
log n,
where C=2.99047... is an explicitly defined constant.
The object of the present paper is to prove analogous theorems for the random variable
m(λ) under the distribution w(λ, q). Actually, it turns out that these theorems hold for
several important classes of polynomials which we shall now describe. Consider the classes:
•M
1(q): the class of all monic polynomials over Fq. In this class the number of
polynomials of degree nis qnfor each n≥1.
•M
2(q): the class of all monic square-free polynomials over Fq.Inthisclassthe
number of polynomials of degree nis (1 −q−1)qnfor each n.
the electronic journal of combinatorics 11 (2004), #R70 2
•M
3(q): the class of all monic square-free polynomials over Fqwhose irreducible
factors have distinct degrees. In this class the number of polynomials of degree n
is a(n, q)qnwhere, for each q,a(n, q)→a(q):=Qk≥1(1 + ik(q)q−k)exp(−1/k)as
n→∞where ik(q) is the number of monic irreducible polynomials of degree kover
Fq(see [7] Equation (1) with j=0).
For x>0 define
Φn(x):=λ⊢n|
log m(λ)−1
2(log n)2
>x
√3(log n)3/2.
Then for each of the classes of polynomials described above we have a weak analogue of
the theorem of Erd¨os and Tur´an quoted above, and an exact analogue of Stong’s theorem.
Theorem 1 Fix one of the classes Mi(q)described above. For each λ⊢n,letw(λ, q)
denote the proportion of polynomials in this class whose factorizations have shape λ. Then
there exists a constant c0>0(independent of the class) such that for each x≥1there
exists n0(x)such that
X
λ∈Φn(x)
wi(λ, q)≤c0e−x/4for all qand all n≥n0(x).(1)
In particular, almost all f(X)of degree nin Mi(q)have splitting fields of degree exp(( 1
2+
o(1))(log n)2)over Fqas n→∞.
Theorem 2 Let Cbe the same constant as in the Goh-Schmutz-Stong theorem. Then
in each of the classes described above the average degree En(q)of a splitting field of a
polynomial of degree nin that class satisfies
log En(q)=Crn
log n+O√nlog log n
log nuniformly in q.
2 Properties of w(λ, q)
First consider the value of w(λ, q) for each of the three classes. Let is=is(q)denotethe
number of monic irreducible polynomials of degree sover Fq. Then (see, for example, [8])
we have qs=Pd|sdidso a simple argument shows that
qs
s≥is≥qs
s(1 + 2q−s/2)−1.
Let λ⊢nhave the form 1k1...nkn.SincePn(q)containsqnpolynomials, and there are
is+k−1
kways to select kirreducible factors of degree s,wehave
w(λ, q)= 1
qn
n
Y
s=1 is+ks−1
ks=
n
Y
s=1
q−sksis+ks−1
ksin M1(q).
the electronic journal of combinatorics 11 (2004), #R70 3
Similarly, since there are (1 −q−1)qnpolynomials of degree nin M2(q), and there are is
k
ways to select kdistinct irreducible factors of degree s,inthiscasewehave
w(λ, q)= 1
(1 −q−1)qn
n
Y
s=1 is
ks=1
(1 −q−1)
n
Y
s=1
q−sksis
ksin M2(q).
Finally, since there are a(n, q)qnpolynomials of degree nin M3(q) and each of these
polynomials has at most one irreducible factor of each degree, we get
w(λ, q)= 1
a(n, q)qn
n
Y
s=1 1
ksiks
s=1
a(n, q)
n
Y
s=1
q−sks1
ksiks
sin M3(q)
when each part in λhas multiplicty ≤1, and w(λ, q) = 0 otherwise. As is well known
we also have
w(λ)= 1
1k12k2...nknk1!k2!...kn!.
We shall use the notation Πnto denote the set of all partitions of n,Π
n,k to denote the
set of partitions 1k12k2...nknin which each ki<kand Π′
n,k to denote the complementary
set of partitions.
It is useful to note that in M1(q)andM2(q)wehavew(λ, q)→w(λ)asq→∞.
However, this behaviour is not uniform in λ. Indeed for each of these two classes the ratio
w(λ, q)/w(λ) is unbounded above and below for fixed qif we let λrange over all partitions
of nand n→∞. This means we have to be careful in deducing our theorems from the
corresponding results for w(λ). In M3(q), we have w(λ, q) = 0 whenever λ∈Π′
n,2,anda
simple computation shows that a(n, q)w(λ, q)→w(λ)asq→∞whenever λ∈Πn,2.
Lemma 3 There exists a constant a0>0such that
1≤1
1−q−1≤a0and 1≤1
a(n, q)≤a0
for all n≥1and all prime powers q>1.
Proof. The first inequality is satisfied whenever a0≥2, so it is enough to prove that
the set of all a(n, q) has a strictly positive lower bound.
We shall use results from [7, Theorems 1 and 2]. In our notation [7] shows that
a(q) increases monotonically with qstarting with a(2) = 0.3967 ..., and that for some
absolute constant cwe have |a(n, q)−a(q)|≤c/n for all n≥1. In particular, a(n, q)≥
a(q)−c/n ≥a(2)−c/n.Thusa(n, q)≥1
2a(2) >0 for all qwhenever n>n
0:= ⌊2c/a(2)⌋.
On the other hand, as we noted above, in M3(q), a(n, q)w(λ, q)→w(λ)asq→∞
whenever λ∈Πn,2and is 0 otherwise. Thus
a(n, q)= X
λ∈Πn
a(n, q)w(λ, q)→X
λ∈Πk,2
w(λ)=b(n), say, as q→∞.
the electronic journal of combinatorics 11 (2004), #R70 4
Evidently, b(n)>0 (it is the probability that a permutation in Snhas all of its cycles of
different lengths). Define b0:= min {b(n)|n=1,2, ..., n0}. Then the limit above shows
that there exists q0such that a(n, q)≥1
2b0whenever n=1,2, ..., n0and q>q
0.
Finally, choose a0≥2 such that 1/a0is bounded above by 1
2a(2), 1
2b0and all a(n, q)
with n=1,2, ..., n0and q≤q0. This value of a0satisfies the stated inequalities.
We next examine some properties of the w(λ, q) which we shall need later. In what
follows, if λ:= 1k1...nkn∈Πnand µ:= 1l1...mlm∈Πm, then the join λ∨µdenotes
the partition of m+nwith ks+lsparts of size s. We shall say that λand µare disjoint
if ksls= 0 for each s.
Lemma 4 Let a0be a constant satisfying the conditions in Lemma 3. Then for each
class Mi(q)we have w(λ∨µ, q)≤a0w(λ, q)w(µ, q)for all λand µ. On the other hand,
if λand µare disjoint, then w(λ∨µ, q)≥a−2
0w(λ, q)w(µ, q).
We also have w(λ∨µ)≤w(λ)w(µ), with equality holding when λand µare disjoint.
Proof. First note that in each of the classes, w(λ∨µ, q) is 0 if either w(λ, q)orw(µ, q)
is 0.Suppose neither of the latter is 0 and put r:= w(λ∨µ, q)/w(λ, q)w(µ, q).
FirstconsidertheclassM1(q). Then rcan be written as a product of terms of the
form is+ks+ls−1
ks+ls/is+ks−1
ksis+ls−1
ls.
The numerator of this ratio counts the number of ways of placing ks+lsindistinguishable
items in isdistinguishable boxes. The denominator counts the number of ways of doing
this when ksof the items are of one type and lsare another, and so is at least as great as
the numerator. Hence we conclude that r≤1<a
0in this case. Moreover, when λand
µare disjoint then each term is equal to 1 and so r=1≥a−2
0. This proves the claim for
the class M1(q). Taking limits as q→∞also gives a proof of the final statement.
Now consider the class M2(q). In this case r/(1 −q−1) can be written as a product
of terms of the form is
ks+ls/is
ksis
ls.
The numerator counts the number of ways to choose ks+lsout of isitems, whilst the
denominator is at least as large as is
ksis−ks
lswhich counts the number of ways to choose
ks+lsitems when ksare of one type and lsare another type. This shows that each term is
at most 1 and so r≤(1 −q−1)≤a0as required. Again, in this case, when the partitions
are disjoint, each term is equal to 1 and so r=1−q−1≥a−2
0. This proves the claim for
the class M2(q), and the proof for the class M3(q) is similar (in this case w(λ∨µ, q)is
0 unless λand µare disjoint).
Lemma 5 For all partitions of the form [sk]and all qwe have
w(sk,q)≤a0
k+1
(2s)k
in each of the classes Mi(q).
the electronic journal of combinatorics 11 (2004), #R70 5