On the number of irreducible factors of degree k dividing a given polynomial over GF(q) (Q915780)

This paper gives a nice approach to the problem of counting the number of irreducible factors of degree k dividing a given polynomial f(x) over GF(q) namely this number is \[ (\sum_{i| k}\mu (k/i)\quad \dim (\ker n(\pi^ i-id)))/\phi (k), \] where \(\pi\) is the Frobenius automorphism of \(R=GF(q)[x]/f(x)GF(q)[x]\) defined by \(\pi\) (class \((g))=class\) \(g^ q\) (in the factor ring). There are two major steps, the first one is to establish that the counting formula \[ \sum^{n}_{\ell =1}\gcd (k,\ell)A(f,\ell)=\dim (\ker n(\pi^ k-id)) \] where A(f,\(\ell)\) is the number of irreducible polynomials of degree \(\ell\) dividing f (Schwarz formula) is a consequence of the formula \(\sum \gcd (k,\ell)a(\pi,\ell)=\) number of all cycles of \(\pi\) where \(\pi\) denotes a permutation \(\pi \in S_ n\) and a(\(\pi\),\(\ell)\) the number of cycles of length \(\ell\) of \(\pi\). This is a consequence of the \(\pi\)- module structure of R [cf. \textit{H. Lüneburg}, On the rational normal form of endomorphisms (1987; Zbl 0635.12012)]. Finally using Schwarz formula and Möbius inversion formula (compared with the other methods which require to compute the inverse of the matrix \(S=(\gcd (i,j)))\) the final result is obtained.