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.



Back to list of publications.