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 xn-1.
Carlitz [Proc. AMS, 3 (1952) 693-700] obtained an expression
Iq(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 Iq(n,t).
If t > 0, Iq(n,t)
= (SUM µ(d) qn/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 Lq(n,t),
the number of q-ary Lyndon words whose characters sum
to t mod q.
This number is given by
Lq(n,t) =
(SUM gcd(d,q) µ(d)
qn/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) 240-245.
-
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 2-graphs arising from subshifts,
Bulletin of the Australian Mathematical Society,
82 (2010) 120-138.
-
Vincent Vajnovszki,
Gray code order for Lyndon words,
Discrete Mathematics and Theoretical Computer Science,
9 (2007) 145-152.
-
Száantó, Csaba,
Hall Numbers and the Composition Algebra of
the Kronecker Algebra,
Algebras and Representation Theory, 9 (2006), no. 5, 465-495.
-
Száantó, Csaba,
A generic Hall algebra of the Kronecker algebra,
Communications in Algebra, 33 (2005), no. 8, 2519-2540.
-
Chang, Yaotsu, Chou, Wun-Seng, Shiue, and Peter J.-S.
On the number of primitive polynomials over finite fields,
Finite Fields and their Applications, 11 (2005), no. 1, 156-163.
-
Wensong Chu, Charles Colbourn, and Peter Dukes,
Constructions for Permutation Codes in Powerline Communications,
Designs, Codes and Cryptography,
Volume 32 , Issue 1-3 May-July 2004, Pages: 51 - 64.
-
Yucas, Joseph L.; Mullen, Gary L.,
Irreducible polynomials over GF(2) with prescribed coefficients,
Discrete Mathematics, 274 (2004), no. 1-3, 265-279.
Back to list of publications.