A Generalized Counting and Factoring Method for Polynomials over Finite Fields

We discuss a transform on the set of rational functions over the finite field \( \mathbb{F}_q \). For a subclass of these functions, the transform yields a polynomial and its factorization as a product of the set of monic irreducible polynomials, all of which share a common property \( P \) that depends on the choice of rational function. A general formula is derived from the factorization for the number of monic irreducible polynomials of degree \( n \) having property \( P \). However, it is also possible in some instances to exploit the properties of the factorization to obtain a “closed” form of the answer more directly. We illustrate the method with four examples, two of which appear in the literature. In particular, we give alternative proofs for a result of L. Carlitz on the number of monic irreducible self-reciprocal polynomials and a remarkable result of S. D. Cohen on the number of \((r, m)\)-polynomials, that is, monic irreducible polynomials of the form \( f(x^r) \) of degree \( mr \). We also give a generalization of the factorization of \( x^{q-1} – 1 \) over \( \mathbb{F}_q \) that includes the factorization of \( x^{(q-1)^2} – 1 \). The new results concern translation invariant polynomials, which lead to a consideration of the orders of elements in \( \overline{\mathbb{F}}_q \), the algebraic closure of \( \mathbb{F}_q \). We show that there are an infinite number of \( \theta \in \overline{\mathbb{F}}_q \) such that \( \text{ord}(\theta) \) and \( \text{ord}(r(\theta)) \) are related, in the sense that given one, one can infer information about the other.