The number of irreducible polynomials and Lyndon words with given trace (Q2719166)

The authors present a new formula for the number of irreducible polynomials of degree \(n\) over \(\text{GF}(q)\) with prescribed non-zero trace \(t\); it is worth noting that the result does not actually depend on \(t\). The authors also define the trace of a \(q\)-ary Lyndon word (i.e., a lexicographically smallest rotation of an aperiodic string over the residues mod \(q\)) as the sum of its characters mod \(q\) and derive a related formula for the number of \(q\)-ary Lyndon words of length \(n\) with prescribed trace. Both proofs use a new form of Möbius inversion.