The Number of Irreducible Polynomials and Lyndon Words with Given Trace
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
C. Robert Miers,
Department of Mathematics and Statistics,
University of Victoria, Canada.
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
The trace of a degree n polynomial
f(x) over GF(q) is
the coefficient of x^{n1}.
Carlitz [Proc. AMS, 3 (1952) 693700] 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)
= (SUM µ(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 qary Lyndon words whose characters sum
to t mod q.
This number is given by
L_{q}(n,t) =
(SUM 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.

The postscript file is 236,341 bytes,
the dvi file is 70,800 bytes.

Appeared in SIAM J. Discrete Mathematics, 14
(2001) 240245.

Tables of these numbers can be found on the following COS pages.

Some of the numbers appear in Sloane's database of integer sequences.

Selected citations:

David Pask, Iain Raeburn and Natasha A. Weaver,
Periodic 2graphs arising from subshifts,
Bulletin of the Australian Mathematical Society,
82 (2010) 120138.

Vincent Vajnovszki,
Gray code order for Lyndon words,
Discrete Mathematics and Theoretical Computer Science,
9 (2007) 145152.

Száantó, Csaba,
Hall Numbers and the Composition Algebra of
the Kronecker Algebra,
Algebras and Representation Theory, 9 (2006), no. 5, 465495.

Száantó, Csaba,
A generic Hall algebra of the Kronecker algebra,
Communications in Algebra, 33 (2005), no. 8, 25192540.

Chang, Yaotsu, Chou, WunSeng, Shiue, and Peter J.S.
On the number of primitive polynomials over finite fields,
Finite Fields and their Applications, 11 (2005), no. 1, 156163.

Wensong Chu, Charles Colbourn, and Peter Dukes,
Constructions for Permutation Codes in Powerline Communications,
Designs, Codes and Cryptography,
Volume 32 , Issue 13 MayJuly 2004, Pages: 51  64.

Yucas, Joseph L.; Mullen, Gary L.,
Irreducible polynomials over GF(2) with prescribed coefficients,
Discrete Mathematics, 274 (2004), no. 13, 265279.
Back to list of publications.