# Counting Irreducible Polynomials of Degreer over F

Authors: Kondwani Magamba; John A. Ryan
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

The problem of finding the number of irreducible monic polynomials of degreer over F
q
n is considered in this paper. By considering the fact that an irreducible polynomial of degree r over F
q
n has a root in a subfield F
q
s of F
q
n
r if and only if (
n
r
/
s
,
r
)
=
1, we show that Gauss’s formula for the number of monic irreducible polynomials can be derived by merely considering the lattice of subfields of F
q
n
r . We also use the lattice of subfields of F
q
n
r to determine if it is possible to generate a Goppa code using an element lying in a proper subfield of F
q
n
r.


---

## Body

## 1. Introduction

In this paper we consider the problem of finding the number,|
P
r
|, of monic irreducible polynomials of degree r over the field F
q
n, where n is a positive integer and q is the power of a prime number. This problem has been discussed by several authors including C. F. Gauss who gave the following beautiful formula:
(1)
|
P
r
|
=
1
r
∑
d
|
r
‍
μ
(
d
)
q
n
r
/
d
,
where d runs over the set of all positive divisors of r including 1 and r and μ
(
k
) is the Möbius function; see [1]. Recently, it has been shown, see [2], that this number can be found by using only basic facts about finite fields and the Principle of Inclusion-Exclusion. This work seeks to emphasize the simplicity of the method given in [2] by using a lattice of subfields. This is done by first of all proving Gauss’s formula using the Principle of Inclusion-Exclusion as was done in [2]. However, we use only one basic fact about where (in which subfields) the roots of irreducible polynomials of degree r over F
q
n can lie. We then show how a lattice of subfields of the field, F
q
n
r, can be used to obtain |
P
r
|. We are particularly interested in the number of roots of irreducible polynomials of degree r over F
q
n because the problem of counting irreducible Goppa codes of length q
n and of degree r depends on this number.


## 2. Preliminaries

### 2.1. The Number of Irreducible Polynomials

Our approach to counting the number of irreducible polynomials of degreer over F
q
n is to count the number of all roots of such polynomials. To this end, we make the following definitions.Definition 1.
One defines the setS
(
n
,
r
) to be the set of all elements in F
q
n
r of degree r over F
q
n.Definition 2.
One defines the setP
r to be the set of all irreducible monic polynomials of degree r over F
q
n.The following theorem is well known.Theorem 3.
|
P
r
| is given by formula (1).For the sake of clarity we state the relationship betweenP
r and S
(
n
,
r
) which immediately leads to the “Gaussian like” count of the number of elements in S
(
n
,
r
). We put this in the following corollary.Corollary 4.
S
(
n
,
r
) is the union of all the roots of the polynomials in P
r and
(2)
|
S
(
n
,
r
)
|
=
∑
d
|
r
‍
μ
(
d
)
q
n
r
/
d
.


### 2.2. Where Elements ofS
(
n
,
r
) Lie

We next identify the subfields ofF
q
n
r where the elements of S
(
n
,
r
) lie. To achieve this we first note that an irreducible polynomial over F
q
n may, in some specific cases, be seen as irreducible over an extension field of F
q
n. To be more specific, we state this in the following theorem.Theorem 5.
An irreducible polynomial overF
q
n of degree r remains irreducible over F
q
n
t if and only if (
r
,
t
)
=
1; see [3].Now, in order to apply Theorem5 to general cases, one makes the following decompositions of n and r.Definition 6.
One definesk to be the largest divisor of n that is relatively prime to r and set l
n
=
n
/
k and defines m to be the largest divisor of r that is relatively prime to n and set l
r
=
r
/
m. Thus n
r
=
k
l
n
l
r
m
=
k
l
m, where l
=
l
n
l
r.With this notation, the following lemma is a direct result of Theorem5.Lemma 7.
S
(
n
,
r
) consists of the elements of  F
q
n
r each of which is a root of an irreducible polynomial of degree r over F
q
k
1
l
n, where k
1 is a divisor of k. In particular, the elements of S
(
n
,
r
) are precisely those elements that lie in a subfield of F
q
n
r of the form F
q
k
1
l
n
r, for some k
1, but not in any subfield of the form F
q
s, where s is not divisible by l
n
r. See [4].It is useful, for our purposes, to think of the subfields identified in Lemma7 in the following way.Corollary 8.
The subfields of the formF
q
s defined in Lemma 7 are the maximal subfields of F
q
n
r such that (
n
r
/
s
,
r
)
≠
1 or the subfields contained in such maximal subfields.


### 2.3. The Principle of Inclusion-Exclusion

Since we will be making extensive use of the “Principle of Inclusion-Exclusion” we state this well known principle in the following theorem; see [5].Theorem 9.
LetA
1
,
A
2
,
…
,
A
n be finite sets. Then
(3)
|
A
1
∪
A
2
∪
⋯
∪
A
n
|
=
∑
1
≤
i
≤
n
|
A
i
|
-
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
+
∑
1
≤
i
<
j
<
k
≤
n
|
A
i
∩
A
j
∩
A
k
|
-
⋯
+
(
-
1
)
n
+
1
|
A
1
∩
A
2
∩
⋯
∩
A
n
|
.


### 2.4. Goppa Codes

This paper is motivated by the unsolved problem of finding an irreducible polynomial which defines a “good” Goppa code of degreer and length q
n or equivalently finding an element of degree r which defines such a code. So it is appropriate for us to define a Goppa code. The following definition is the classical definition found in much of the literature on coding theory.Definition 10.
Letg
(
z
)
∈
F
q
n
[
z
] be irreducible of degree r and let L
=
F
q
n
=
{
ζ
i
:
0
≤
i
≤
q
n
-
1
}. Then the irreducible Goppa code Γ
(
L
,
g
) is defined as the set of all vectors c
_
=
(
c
0
,
c
1
,
…
,
c
q
n
-
1
) with components in F
q which satisfy the condition
(4)
∑
i
=
0
q
n
-
1
‍
c
i
z
-
ζ
i
≡
0
mod
⁡
g
(
z
)
.The polynomialg
(
z
) is called the Goppa polynomial. Since g
(
z
) is irreducible and of degree r over F
q
n, g
(
z
) does not have any root in L and the code is called an irreducible Goppa code of degree r. In this paper g
(
z
) is always irreducible of degree r over F
q
n.


#### 2.4.1. Irreducible Goppa Codes Defined by a Field Element

The following characterization of an irreducible Goppa code is particularly useful for our purposes. It can be shown, see [6], that if α is any root of the Goppa polynomial g
(
z
) then Γ
(
L
,
g
) is completely described by any root α of g
(
z
) and a parity check matrix H
(
α
) is given by
(5)
H
(
α
)
=
(
1
α
-
ζ
0
1
α
-
ζ
1
⋯
1
α
-
ζ
q
n
-
1
)
.
We denote this code by C
(
α
). Since C
(
α
) is completely described by the root α of g
(
z
) the number |
S
| gives an upper bound on the number of irreducible Goppa codes. Furthermore, knowing the various locations (subfields) of the elements of S will facilitate research into finding the element which will give the best Goppa code.


## 2.1. The Number of Irreducible Polynomials

Our approach to counting the number of irreducible polynomials of degreer over F
q
n is to count the number of all roots of such polynomials. To this end, we make the following definitions.Definition 1.
One defines the setS
(
n
,
r
) to be the set of all elements in F
q
n
r of degree r over F
q
n.Definition 2.
One defines the setP
r to be the set of all irreducible monic polynomials of degree r over F
q
n.The following theorem is well known.Theorem 3.
|
P
r
| is given by formula (1).For the sake of clarity we state the relationship betweenP
r and S
(
n
,
r
) which immediately leads to the “Gaussian like” count of the number of elements in S
(
n
,
r
). We put this in the following corollary.Corollary 4.
S
(
n
,
r
) is the union of all the roots of the polynomials in P
r and
(2)
|
S
(
n
,
r
)
|
=
∑
d
|
r
‍
μ
(
d
)
q
n
r
/
d
.


## 2.2. Where Elements ofS
(
n
,
r
) Lie

We next identify the subfields ofF
q
n
r where the elements of S
(
n
,
r
) lie. To achieve this we first note that an irreducible polynomial over F
q
n may, in some specific cases, be seen as irreducible over an extension field of F
q
n. To be more specific, we state this in the following theorem.Theorem 5.
An irreducible polynomial overF
q
n of degree r remains irreducible over F
q
n
t if and only if (
r
,
t
)
=
1; see [3].Now, in order to apply Theorem5 to general cases, one makes the following decompositions of n and r.Definition 6.
One definesk to be the largest divisor of n that is relatively prime to r and set l
n
=
n
/
k and defines m to be the largest divisor of r that is relatively prime to n and set l
r
=
r
/
m. Thus n
r
=
k
l
n
l
r
m
=
k
l
m, where l
=
l
n
l
r.With this notation, the following lemma is a direct result of Theorem5.Lemma 7.
S
(
n
,
r
) consists of the elements of  F
q
n
r each of which is a root of an irreducible polynomial of degree r over F
q
k
1
l
n, where k
1 is a divisor of k. In particular, the elements of S
(
n
,
r
) are precisely those elements that lie in a subfield of F
q
n
r of the form F
q
k
1
l
n
r, for some k
1, but not in any subfield of the form F
q
s, where s is not divisible by l
n
r. See [4].It is useful, for our purposes, to think of the subfields identified in Lemma7 in the following way.Corollary 8.
The subfields of the formF
q
s defined in Lemma 7 are the maximal subfields of F
q
n
r such that (
n
r
/
s
,
r
)
≠
1 or the subfields contained in such maximal subfields.


## 2.3. The Principle of Inclusion-Exclusion

Since we will be making extensive use of the “Principle of Inclusion-Exclusion” we state this well known principle in the following theorem; see [5].Theorem 9.
LetA
1
,
A
2
,
…
,
A
n be finite sets. Then
(3)
|
A
1
∪
A
2
∪
⋯
∪
A
n
|
=
∑
1
≤
i
≤
n
|
A
i
|
-
∑
1
≤
i
<
j
≤
n
|
A
i
∩
A
j
|
+
∑
1
≤
i
<
j
<
k
≤
n
|
A
i
∩
A
j
∩
A
k
|
-
⋯
+
(
-
1
)
n
+
1
|
A
1
∩
A
2
∩
⋯
∩
A
n
|
.


## 2.4. Goppa Codes

This paper is motivated by the unsolved problem of finding an irreducible polynomial which defines a “good” Goppa code of degreer and length q
n or equivalently finding an element of degree r which defines such a code. So it is appropriate for us to define a Goppa code. The following definition is the classical definition found in much of the literature on coding theory.Definition 10.
Letg
(
z
)
∈
F
q
n
[
z
] be irreducible of degree r and let L
=
F
q
n
=
{
ζ
i
:
0
≤
i
≤
q
n
-
1
}. Then the irreducible Goppa code Γ
(
L
,
g
) is defined as the set of all vectors c
_
=
(
c
0
,
c
1
,
…
,
c
q
n
-
1
) with components in F
q which satisfy the condition
(4)
∑
i
=
0
q
n
-
1
‍
c
i
z
-
ζ
i
≡
0
mod
⁡
g
(
z
)
.The polynomialg
(
z
) is called the Goppa polynomial. Since g
(
z
) is irreducible and of degree r over F
q
n, g
(
z
) does not have any root in L and the code is called an irreducible Goppa code of degree r. In this paper g
(
z
) is always irreducible of degree r over F
q
n.


### 2.4.1. Irreducible Goppa Codes Defined by a Field Element

The following characterization of an irreducible Goppa code is particularly useful for our purposes. It can be shown, see [6], that if α is any root of the Goppa polynomial g
(
z
) then Γ
(
L
,
g
) is completely described by any root α of g
(
z
) and a parity check matrix H
(
α
) is given by
(5)
H
(
α
)
=
(
1
α
-
ζ
0
1
α
-
ζ
1
⋯
1
α
-
ζ
q
n
-
1
)
.
We denote this code by C
(
α
). Since C
(
α
) is completely described by the root α of g
(
z
) the number |
S
| gives an upper bound on the number of irreducible Goppa codes. Furthermore, knowing the various locations (subfields) of the elements of S will facilitate research into finding the element which will give the best Goppa code.


## 2.4.1. Irreducible Goppa Codes Defined by a Field Element

The following characterization of an irreducible Goppa code is particularly useful for our purposes. It can be shown, see [6], that if α is any root of the Goppa polynomial g
(
z
) then Γ
(
L
,
g
) is completely described by any root α of g
(
z
) and a parity check matrix H
(
α
) is given by
(5)
H
(
α
)
=
(
1
α
-
ζ
0
1
α
-
ζ
1
⋯
1
α
-
ζ
q
n
-
1
)
.
We denote this code by C
(
α
). Since C
(
α
) is completely described by the root α of g
(
z
) the number |
S
| gives an upper bound on the number of irreducible Goppa codes. Furthermore, knowing the various locations (subfields) of the elements of S will facilitate research into finding the element which will give the best Goppa code.


## 3. Proof of Gauss’s Formula

We now give a new proof of Gauss’s Formula when applied to find the cardinality of the setS which has special significance in the application to Goppa codes. Putting n
=
1 in our proof will give the result proved in [2]. There are many similarities between approach given in [2] and our method. However, the crux of our argument lies on Corollary 8 which in turn is based on Theorem 5. We believe that this slightly different approach brings a little more clarity to the situation.Proof.
Letr
=
r
1
i
1
r
2
i
2
⋯
r
w
i
w be the prime factorisation of r. The maximal subfields F
q
s of F
q
n
r, as in Corollary 8, are of the form
(6)
F
q
n
r
/
r
1
,
F
q
n
r
/
r
2
,
…
,
F
q
n
r
/
r
w
.
Thus, by Corollary 8, |
S
(
n
,
r
)
|
=
|
(
F
q
n
r
/
r
1
∪
F
q
n
r
/
r
2
∪
⋯
∪
F
q
n
r
/
r
w
)
′
|, where the complement is taken in F
q
n
r. As in [2], we note that F
q
n
r
/
r
1
∩
F
q
n
r
/
r
2
=
F
q
n
r
/
r
1
r
2, F
q
n
r
/
r
1
∩
F
q
n
r
/
r
2
∩
F
q
n
r
/
r
3
=
F
q
n
r
/
r
1
r
2
r
3, and so forth. Using the Principle of Inclusion-Exclusion, it follows that
(7)
|
S
(
n
,
r
)
|
=
q
n
r
-
q
n
r
/
r
1
-
q
n
r
/
r
2
-
⋯
-
q
n
r
/
r
w
+
q
n
r
/
r
1
r
2
+
q
n
r
/
r
1
r
3
+
⋯
+
q
n
r
/
r
w
-
1
r
w
⋮
+
(
-
1
)
w
q
n
r
/
r
1
r
2
⋯
r
w
.
Finally, note that |
P
r
|
=
|
S
(
n
,
r
)
|
/
r.


## 4.|
P
r
| Using a Lattice of Subfields of F
q
n
r

We have noted that in order to constructS
(
n
,
r
) a lattice of subfields of F
q
n
r together with Corollary 8 offers a good insight into S
(
n
,
r
). We will put the lattice of subfields of F
q
n
r into their usual hierarchies, where level one is taken by F
q
n
r, and level two contains subfields of F
q
n
r of the form F
q
n
r
/
u
i, where n
r
=
u
1
i
1
u
2
i
2
⋯
u
j
i
j is the prime factorization of n
r. Level three comprises of maximal subfields of the fields in level two and so on. As this is done, all intersections between subfields are marked as this is used in getting S
(
n
,
r
).Observe that the elements ofF
q
s (those not lying in S) described in Corollary 8 are those which lie in subfields of type F
q
n
r
/
r
i, where r
i is a prime divisor of r. We can see the formula for S
(
n
,
r
) taking shape as we have the full splitting field F
q
n
r of all the irreducible polynomials of degree r over F
q
n, the maximal subfields F
q
n
r
/
r
i, and the subfields of F
q
n
r
/
r
i.Formula (7) shows the levels mentioned above. The subfields that need to be considered in order to find |
S
(
n
,
r
)
| can be read off from a lattice of subfields of F
q
n
r in accordance with Corollary 8, that is, subfields of the form F
q
k
1
l
n
r. We illustrate this method with an example.Example 11.
Let us takeq
=
2, n
=
10, and r
=
6. Then, k
=
5, l
n
=
l
r
=
2, m
=
3, and F
q
n
r
=
F
2
60. Hence the subfields in level two which do not contain any elements of S (subfields of the form F
q
n
r
/
r
i) are F
2
30 and F
2
20. While the only proper subfield which does contain elements of S (subfield of the form F
q
k
1
l
n
r) is F
2
12, putting k
1
=
1. So in constructing the set S it is necessary to exclude the two subfields F
2
30 and F
2
20. In level three, we will consider the intersection F
2
30
∩
F
2
20
=
F
2
10 as this has been excluded twice. Thus, the number of elements of degree 6 over F
2
10 is 2
60
-
2
30
-
2
20
+
2
10. The lattice shown in Figure 1 illustrates this example.Figure 1
Lattice of subfields ofF
2
60.Example 12.
Let us takeq
=
2, r
=
30, and n
=
1. In this case k
=
l
n
=
1 and r
=
30. There are no proper subgroups of the form F
q
k
1
l
n
r but rather all maximal subgroups are of the form F
q
n
r
/
r
i and so by Corollary 8 all these maximal subgroups are excluded when constructing the set S. By the Principle of Inclusion-Exclusion, it follows that |
S
(
1,30
)
|
=
2
30
-
2
15
-
2
10
-
2
6
+
2
5
+
2
3
+
2
2
-
2. See Figure 2.Figure 2
Lattice of subfields ofF
2
30.


## 5. Applications to Goppa Codes

We know that an irreducible Goppa code,C
(
α
), is defined by a root α of the Goppa polynomial which is of degree r over F
q
n. Now to find such an α one can search in any of the subfields of the form F
q
k
1
l
n
r. This makes the search easier. We can use a lattice of subfields of F
q
n
r not only to facilitate this search but also to calculate the number of such elements.Example 13.
Let us look again at the example above withq
=
2, n
=
10, and r
=
6. F
2
12 contains elements of S
(
10,6
). The number of elements in S
(
10,6
)
∩
F
2
12 can be easily calculated from the lattice of subfields. It is 2
12
-
2
6
-
2
4
+
2
2. See Figure 3.Figure 3
Lattice of subfields ofF
2
60.


## 6. Conclusion

In this paper we have shown how a lattice of subfields can be used as an alternative to Gauss’s formula for finding the number of monic irreducible polynomials of degreer over F
q
n. The lattice of subfields approach helps to clear the mystery surrounding the rather complicated looking Gaussian formula which involves the Möbius function. We have also shown how this method can be used to obtain a Goppa code C
(
α
), where α lies in a lower field. Using the Principle of Inclusion-Exclusion with the lattice of subfields it is easy to calculate the number of such elements α in any subfield. The lattice of subfields approach simplifies the task of finding Goppa codes and sheds light on the processes involved.



---

*Source: 263179-2014-09-18.xml*