THE NUMBER OF IRREDUCIBLE POLYNOMIALS AND LYNDON WORDS WITH GIVEN TRACE

F. RUSKEY^{∗}, C.R. MIERS^{†}, AND J. SAWADA^{‡}

Abstract. The trace of a degree n polynomial f(x) over GF (q) is the coefficient of x^{n−1}. Carlitz [Proc. AMS, 3 (1952) 693-700] obtained an expression I_{q}(n, t), for the number of monic irreducible polynomials over GF (q) of degree n and trace t. Using a different approach, we derive a simple explicit expression for I_{q}(n, t). If t > 0, I_{q}(n, t) = (∑ μ(d)q^{n/d})/(qn), where the sum is over all divisors d of n which are relatively prime to q. This same approach is used to count L_{q}(n, t), the number of q-ary Lyndon words whose characters sum to t mod q. This number is given by L_{q}(n, t) = (∑ gcd(d, q)μ(d)q^{n/d})/(qn), where the sum is over all divisors d of n for which gcd(d, q)|t. Both results rely on a new form of Möbius inversion.

Key words. Irreducible polynomial, trace, finite field, Lyndon word, Möbius inversion

AMS subject classifications. 05T06, 11T06

1. Introduction. The trace of a degree n polynomial f(x) over GF (q) is the coefficient of x^{n−1}. It is well known that the number of degree n irreducible polynomials over GF (q) is given by

I_{q}(n) = \frac{1}{n} ∑_{d|n} μ(d)q^{n/d}, (1.1)

where μ(d) is the Möbius function. Less well-known is the formula

I_{2}(n, 1) = \frac{1}{2n} ∑_{{d|n \atop d odd}} μ(d)2^{n/d}, (1.2)

which is the number of degree n irreducible polynomials over GF (2) with trace 1 (this can be inferred from results in Jungnickel [3], Section 2.7). One purpose of this paper is to refine (1.1) and (1.2) by enumerating the irreducible degree n polynomials over GF (q) with a given trace. Carlitz [1] also solved this problem, arriving via a different technique at an expression that is different, but equivalent to the one given below. Our version of the result is stated in Theorem 1.1.

Theorem 1.1. Let q be a power of prime p. The number of irreducible polynomials of degree n > 0 over GF (q) with a given non-zero trace t is

I_{q}(n, t) = \frac{1}{qn} ∑_{{d|n \atop p∤d}} μ(d)q^{n/d}. (1.3)

Note that the expression on the right hand side of (1.3) is independent of t and that I_{q}(n, 0) can be obtained by subtracting

I_{q}(n, 0) = I_{q}(n) − (q − 1)I_{q}(n, 1).

∗Dept. of Computer Science, University of Victoria, research supported in part by NSERC.

e-mail:  fruskey@csr.uvic.ca

†Dept. of Mathematics and Statistics, University of Victoria. e-mail: crmiers@math.uvic.ca ‡Dept. of Computer Science, University of Victoria, research supported in part by a NSERC.

e-mail:  jsawada@csr.uvic.ca

A Lyndon word is the lexicographically smallest rotation of an aperiodic string. If L_{q}(n) denotes the number of q-ary Lyndon words of length n, then it is well known that L_{q}(n) = I_{q}(n). The trace of a Lyndon word is the sum of its characters mod q. Let L_{q}(n, t) denote the number of Lyndon words of trace t. The second purpose of this paper is to obtain an explicit formula for L_{q}(n, t). This result is stated in Theorem 1.2.

Theorem 1.2. For all integers n > 0, q > 1, and t ∈ {0, 1, …, q − 1},

L_{q}(n, t) = \frac{1}{qn} ∑_{{d|n \atop gcd(d,q)|t}} gcd(d, q)μ(d)q^{n/d}.

Note that I_{q}(n, t) = L_{q}(n, s) whenever t ≠ 0 and gcd(n, s) = 1.

In order to prove Theorems 1.1 and 1.2 we need a new form of Möbius inversion. This is presented in the next section.

2. A generalized Möbius inversion formula. The defining property of the Möbius functions is

∑_{d|n} μ(d) = [[n = 1]], (2.1)

where [[P]] for proposition P represents the “Iversonian convention”: [[P]] has value 1 if P is true and value 0 if P is false (see [4], pg. 24).

Definition 2.1. Let R be a set, ℕ = {1, 2, 3, …}, and let {X(d, t)}_{t∈R,d∈ℕ} be a family of subsets of R. We say that {X(d, t)}_{t∈R,d∈ℕ} is recombinant if

(i) X(1, t) = {t} for all t ∈ R, and (ii) {e′ ∈ X(d′, e) : e ∈ X(d, t)} = {e ∈ X(dd′, t)} for all d, d′ ∈ ℕ, t ∈ R. Theorem 2.2. Let {X(d, t)}_{t∈R,d∈ℕ} be a recombinant family of subsets of R.

Let A : ℕ × R → C and B : ℕ × R → C be functions, where C is a commutative ring with identity. Then

A(n, t) = ∑_{d|n} ∑_{e∈X(d,t)} B(\frac{n}{d}, e)

for all n ∈ ℕ and t ∈ R if and only if

B(n, t) = ∑_{d|n} μ(d) ∑_{e∈X(d,t)} A(\frac{n}{d}, e)

for all n ∈ ℕ and t ∈ R.

Proof. Consider the sum, call it S, on the right-hand side of the first equation

S = ∑_{d|n} ∑_{e∈X(d,t)} B(\frac{n}{d}, e)

= ∑_{d|n} ∑_{e∈X(d,t)} ∑_{d′|(n/d)} ∑_{e′∈X(d′,e)} μ(d′)A(\frac{n}{dd′} , e′)

= ∑_{d|n} ∑_{dd′|n} μ(d′) ∑_{e∈X(d,t)} ∑_{e′∈X(d′,e)} A(\frac{n}{dd′} , e′).

Now substitute f = dd′ and use recombination to get

S = ∑_{d|n} ∑_{f|n} [[f = dd′]]μ(\frac{f}{d}) ∑_{e∈X(d,t)} ∑_{e′∈X(d′,e)} A(\frac{n}{f}, e′)

= ∑_{f|n} ∑_{d|f} μ(\frac{f}{d}) ∑_{e∈X(f,t)} A(\frac{n}{f}, e)

= ∑_{f|n} ∑_{e∈X(f,t)} A(\frac{n}{f}, e) ∑_{d|f} μ(\frac{f}{d})

= ∑_{f|n} ∑_{e∈X(f,t)} A(\frac{n}{f}, e)[[f = 1]]
= A(n, t)

Verification in the other direction is similar and is omitted.

Lemma 2.3. Let d ∈ ℕ and e, t members of an additive monoid R. The sets {e : de = t} form a recombinant family.

Proof. Here de means e + e + ⋯ + e (d terms). Suppose that de = t and d′e′ = e. Clearly, dd′e′ = t. Conversely, if dd′e′ = t then d′e′ is equal to some element of R , call it e. Then d′e′ = e and de = t.

Corollary 2.4. For a fixed prime power q, the sets X_{q}(d, t) = {e ∈ GF (q) : de = t} form a recombinant family of subsets of GF (q).

Corollary 2.5. For a fixed integer q, the sets X_{q}(d, t) = {e ∈ ℤ_{q} : de ≡ t(q)} form a recombinant family of subsets of ℤ_{q}, where ℤ_{q} are the integers mod q.

3. Irreducible polynomials with given trace. In this section, the irreducible polynomials with a given trace are counted. We begin by introducing some notation that will be used in the remainder of the paper. We use Jungnickel [3] as a reference for terminology and basic results from finite field theory.

The trace of an element β ∈ GF (q^{n}) over GF (q) is denoted T r(β), and is given by

T r(β) = β + β^{q} + β^{q^{2}} + ⋯ + β^{q^{n−1}}.

If β ∈ GF (q^{n}) and d is the smallest positive integer for which β^{q^{d}} = 1, then f(x) is the minimal polynomial of β, denoted Min(β), where

f(x) = (x − β)(x − β^{q}) ⋯ (x − β^{q^{d−1}}).

The value of d must be a divisor of n.

Let Irr_{q}(n, t) denote the set of all monic irreducible polynomials over GF (q) of degree n and trace t. By a · Irr_{q}(n, t) we denote the multiset consisting of a copies of Irr_{q}(n, t). Classic results of finite field theory imply the following equality of multisets

(3.1)  ⋃_{β∈GF(q^{n})} \{Min(β)\} = ⋃_{d|n} d · Irr_{q}(d) = ⋃_{d|n} \frac{n}{d} · Irr_{q}(\frac{n}{d}),

where Irr_{q}(d) is the set of monic irreducible polynomials of degree d over GF (q). From (3.1) it is easy to derive (1.1) via a standard application of Möbius inversion.

Now we restrict the equality (3.1) to trace t field elements to obtain

⋃_{{β∈GF(q^{n}) \atop T r(β)=t}} \{Min(β)\} = ⋃_{d|n} \frac{n}{d} · \{f ∈ Irr_{q}(\frac{n}{d}) : T r(f^{d}) = t\}

= ⋃_{d|n} \frac{n}{d} · \{f ∈ Irr_{q}(\frac{n}{d}) : d · T r(f) = t\}

= ⋃_{d|n} ⋃_{de=t} \frac{n}{d} · \{f ∈ Irr_{q}(\frac{n}{d}) : T r(f) = e\}

(3.2)  = ⋃_{d|n} ⋃_{de=t} \frac{n}{d} · \{f ∈ Irr_{q}(\frac{n}{d}, e)\}

Note that the equation de = t is asking whether the d-fold sum of e ∈ GF (q) is equal to t ∈ GF (q). We use the notation GF (q^{n}, t) for the set of elements in GF (q^{n}) with trace t, for t = 0, 1, …, q − 1, where q = p^{m} and p is prime. Consider the map ρ that sends α to α + γ, where γ ∈ GF (q^{n}) has trace 1. We claim that ρ(GF (q^{n}, t)) = GF (q^{n}, t + 1), and so the number of elements is the same for each trace value. Thus

|GF (q^{n}, t)| = q^{n−1}.

Taking cardinalities in (3.2) gives

q^{n−1} = ∑_{d|n} ∑_{de=t} \frac{n}{d}I_{q}(\frac{n}{d}, e).

From Theorem 2.2 and Corollary 2.4, we obtain

I_{q}(n, t) = \frac{1}{qn} ∑_{d|n} ∑_{de=t} μ(d)q^{n/d}.

The equation de = t where d is an integer and e, t ∈ GF (q) has a unique solution e if t ≠ 0 and p ∤ d. If t = 0, then there is one solution e = 0 if p ∤ d and there are q solutions if p | d. Thus, if t ≠ 0 then

I_{q}(n, t) = \frac{q − 1}{qn} ∑_{{d|n \atop p∤d}} μ(d)q^{n/d},

thereby proving Theorem 1.1. Otherwise, if t = 0, then

I_{q}(n, 0) = I_{q}(n, 1) + \frac{q − 1}{qn} ∑_{{d|n \atop p|d}} μ(d)q^{n/d}.

4. Lyndon words with given trace. If a = a_{1}a_{2} ⋯ a_{n} is a word, then we define its trace mod q, T r_{q}(a), to be ∑ a_{i} mod q. Let L_{q}(n, t) denote the number of q-ary Lyndon words of length n and trace t mod q. Note that any q-ary string of length n can be expressed as the concatenation of d copies of the rotation of some Lyndon word of length n/d, for some d | n. Note further that there are precisely q^{n−1} words of length n with trace t, because any word of length n − 1 can have a final n-th character appended in only one way to have trace t. It therefore follows that

q^{n−1} = ∑_{d|n} ∑_{de≡t(q)} \frac{n}{d}L_{q}(\frac{n}{d}, e). (4.1)

This can be solved using Theorem 2.2 and Corollary 2.5 to yield

nL_{q}(n, t) = ∑_{d|n} μ(d) ∑_{de≡t(q)} q^{n/d−1}.

Hence

L_{q}(n, t) = \frac{1}{qn} ∑_{{d|n \atop gcd(q,d)|t}} gcd(q, d)μ(d)q^{n/d}. (4.2)

Equation (4.2) is true because de ≡ t(q) has a solution if and only if gcd(d, q) | t. If a solution exists, then it has precisely gcd(d, q) solutions (e.g., [2], Corollary 33.22, pg. 821). This proves Theorem 1.2.

We could also consider the more general question of computing L_{q,r}(n, t), the number of q-ary Lyndon words with trace mod r, and derive similar but more complicated formulae. If M_{q}(n, t) is the number of q-ary length n strings whose characters sum to t, then clearly M_{q}(1, t) = [[0 ≤ t < q]], and for n > 1

M_{q}(n, t) = ∑_{i=0}^{q} M_{q}(n − 1, t − i).

If T_{q,r}(n, t) denotes the number of q-ary length n strings with trace mod r equal to t, then

T_{q,r}(n, t) = ∑_{s≡t(r)} M_{q}(n, s).

Using the same approach as before

L_{q,r}(n, t) = \frac{1}{n} ∑_{d|n} μ(d) ∑_{de≡t(r)} T_{q,r}(\frac{n}{d}, e).

The equation for L_{q,r}(n, t) seems to produce no particularly nice formulae, except in the case seen previously where q = r, or if q = 2. When q = 2, M_{2}(n, t) = \binom{n}{t} and

T_{2,r}(n, t) = ∑_{s≡t(r)} \binom{n}{s}.

However, in this case there is already a well-known formula for the number of Lyndon words with k 1’s, namely

P_{2}(n, k) = \frac{1}{n} ∑_{d|gcd(n,k)} μ(d)\binom{n/d}{k/d},

from which we obtain L_{2,r}(n, t) = ∑_{s≡t(2)} P_{2}(n, s).

5. Final Remarks. Our generalized Möbius inversion theorem can be extended to a Möbius inversion theorem on posets. Background material on Möbius inversion on posets may be found in Stanley [5]. We state here the modified definition of recombinant and the inversion theorem, but omit the proof.

Definition 5.1. Let P be a poset, let R be a set, and let {X(y, x, t)}_{x,y∈P,y⪯x,t∈R} be a family of subsets of R. The family {X(y, x, t)}_{x,y∈P,y⪯x,t∈R} is recombinant if

(i) X(x, x, t) = {t} for all t ∈ R, and (ii) {e′ ∈ X(z, y, e) : e ∈ X(y, x, t)} = {e ∈ X(z, x, t)} for all z ⪯ y ⪯ x ∈

P, t ∈ R.

We note that if P, is the divisor lattice, and R is an additive monoid, then the collection {X(x, y, t)}_{x,y∈P,x≤y,t∈R} where X(x, y, t) = {e ∈ R : (y/x)e = t} is recombinant, as per Lemma 1.

Theorem 5.2. Let P be a poset, R be a set, and {X(y, x, t)}_{x,y∈P,y⪯x,t∈R} be a recombinant family. Let A : P × R → C, and B : P × R → C, be functions where C is a commutative ring with identity. Then

A(x, t) = ∑_{y⪯x} ∑_{e∈X(y,x,t)} B(y, e)

for all x ∈ P and t ∈ R if and only if

B(x, t) = ∑_{y⪯x} μ(y, x) ∑_{e∈X(y,x,t)} A(y, e)

for all x ∈ P and t ∈ R. (Here μ(y, x) is the Möbius function of the poset P.)

Tables of the numbers I_{q}(n, t) and L_{q}(n, t) for small values of q and n may be found on Frank Ruskey’s Combinatorial Object Server (COS) at

www.theory.csc.uvic.ca/~cos/inf/{lyndon.html,irreducible.html}.  They

also appear in Neil Sloane’s On-line Encyclopedia of Integer Sequences (at

http://www.research.att.com/~njas/sequences/) as I_{2}(n, 0) = L_{2}(n, 0) =

A051841, I_{2}(n, 1) = L_{2}(n, 1) = A000048, I_{3}(n, 0) = L_{3}(n, 0) = A046209, I_{3}(n, 1) = L_{3}(n, 1) = A046211, L_{4}(n, 0) = A054664, I_{4}(n, 1) = L_{4}(n, 1) = A054660, L_{5}(n, 0) = A054661, I_{5}(n, 1) = L_{5}(n, 1) = A054662, L_{6}(n, 0) = A054665, L_{6}(n, 1) = A054666, L_{6}(n, 2) = A054667, L_{6}(n, 3) = A054700.

The authors wish to thank Aaron Gulliver for helpful discussions regarding this paper.

REFERENCES

[1] L. Carlitz, A theorem of Dickson on irreducible polynomials, Proc. AMS, 3 (1952) 693-700.

[2] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

[3] Dieter Jungnickel, Finite Fields: structure and arithmetics, B.I. Wissenschaftsverlag, 1993.

[4] D.E. Knuth, R.L. Graham, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[5] Richard P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 1997.