The Number of Irreducible Polynomials and Lyndon Words with Given Trace

Abstract

The trace of a degree n polynomial f(x) over GF(q) is the coefficient of xn-1 . Carlitz [Proc. Amer. Math. Soc., 3 (1952), pp. 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 \mu(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 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 {\rm gcd}(d,q) \mu(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.