The Number of Irreducible Polynomials and Lyndon Words with Given Trace
Frank Ruskey, C. Robert Miers, Joe Sawada · SIAM Journal on Discrete Mathematics · 2001
The trace of a degree n polynomial f(x) over GF(q) is the coefficient of x n-1 . Carlitz [Proc. Amer. Math. Soc., 3 (1952), pp. 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) = (\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 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) = (\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.