The dynamics of permutations on irreducible polynomials (Q1987105)

Let \(\mathbb{F}_q\) be the finite field with \(q\) elements. In this article the authors consider maps defined by polynomials over \(\mathbb{F}_q\) on the set \(\mathcal{I}\) of monic, irreducible polynomials over \(\mathbb{F}_q\). The authors first define the map \(f \mapsto F\diamond f\) on \(\mathcal{I}\). For a polynomial \(F\in \mathbb{F}_q[x]\), \[ F\diamond f=m_{F(\alpha)}(x) \] where \(\alpha \in \overline{\mathbb{F}}_q\) is a root of \(f(x)\) and \(m_{F(\alpha)}(x)\) denotes the minimal polynomial of \(F(\alpha)\) over \(\mathbb{F}_q\). In Section 3, Theorem 3.3. \(f\in \mathbb{F}_q[x]\) is a monic, irreducible polynomial and it is shown that the map \(f \mapsto F\diamond f\), where \(F\in \mathbb{F}_q[x]\) is a polynomial of degree \(\geq 1\), preserves the degree if and only if \(F(x)=ax^{p^h} + b\), where \(q\) is a power of \(p\). In Theorem 3.4. the authors consider the set of monic, irreducible polynomials \(f\in \mathbb{F}_q[x]\) of a fixed degree \(k\), which they denote by \(\mathcal{I}_k\). Here, \(F \in \mathbb{F}_q[x]\) permutes \(\mathbb{F}_{q^k} \) and it is shown that the map \(f \mapsto F\diamond f\) is degree preserving. Moreover, it is shown that the mapping gives a permutation of the set \(\mathcal{I}_k\). In Section 4, the authors define the set \(\mathbb{G}_k\) as \[ \mathbb{G}_k=\{P\in \mathbb{F}_q[x]: P\;\text{is a permutation polynomial of}\; \mathbb{F}_{q^k}\;\text{and}\; \deg(P)<q^k\}. \] Then it is shown that \(\mathbb{G}_k\) has a group structure with respect to composition modulo \(x^{q^k}-x\). Theorem 4.3 shows that any permutation \(\sigma\) of \(\mathcal{I}_k\) can be represented by a mapping defined by a polynomial \(P \in \mathbb{G}_k\) as \(\sigma(f)=P\diamond f, f \in \mathcal{I}_k\). In Lemma 4.4. for \(P \in \mathbb{G}_k\), an explicit formula for \(P \diamond f\) is given in terms of the compositional inverse of \(P\). The computation of the compositional inverse of \(P\) may not be easy, hence the authors define an alternative mapping. For \(P \in \mathbb{G}_k\) and \(f\in \mathcal{I}_k\), \[ P*f=Q\diamond f \] where \(Q \in \mathbb{G}_k\) is the compositional inverse of \(P\). In Section 5, first the fixed points of the map \(f \mapsto P*f\), \(f\in \mathcal{I}_k\) are considered. The number of fixed points for the special permutation polynomials such as the monomials and the linearized ones are given. In the rest of Section 5, for the same permutation polynomials, results on the invariants of the map \(f \mapsto P*f\) are given. A polynomial \(P\in \mathbb{G}_k\) induces a permutation on \(\mathcal{I}_k\) via the map \(f \mapsto P*f\) and a permutation on \(\mathcal{C}_k=\{\alpha \in \overline{\mathbb{F}_q}: deg(\alpha)=k\}\) via the evaluation map. In Section 6, the authors study the length of the cycles in the corresponding permutations. For the families of monomials, linearized permutation polynomials and the Möbius maps explicit formulas about the cycle decomposition of the corresponding permutations are given. For a polynomial \(f\in \mathcal{I}_k\), the orbit of \(f\) under the map \(f \mapsto P*f\) on \(\mathcal{I}_k\), where \(P\in \mathbb{G}_k\), consists of polynomials in \(\mathcal{I}_k\). Let \(f_0=f, f\in \mathcal{I}_k\) be fixed. For \(i\geq 1\), define \(f_i(x)=P*f_{i-1}\) which is \(\gcd(f_{i-1}(P), x^{q^k}-x)\) using Equation (4.2). The aim is to identify \(P \in \mathbb{G}_k\) such that the previously defined sequence of irreducible polynomials has a long period. In Section 7, monomials and linearized permutations are explored and for these permutations, the authors identify the least possible period for different choices of \(f \in \mathcal{I}_k\).