Polynomials over finite fields which commute with a permutation polynomial (Q1320182): Difference between revisions

For \(q\) a prime power, let \(F_ q\) denote the finite field of order \(q\) and let \(F_ q[x]\) be the ring of polynomials in a single indeterminate over \(F_ q\). For any permutation polynomial \(f\in F_ q[x]\), (\(1-1\) mapping of \(F_ q\) onto itself), the author uses properties of the centralizer ring of a permutation group to characterize those polynomials \(g\in F_ q[x]\) with the property that \(f(g(x))= g(f(x))\). Pólya and de Bruijn enumeration techniques are then used to determine the numbers of such polynomials \(g\) and permutation polynomials \(g\in F_ q[x]\) of degree \(<q\). An algorithm is also given to determine all such polynomials \(g\). As the author points out on page 296, since the centralizer ring of a permutation group and Pólya and de Bruijn enumeration techniques apply to finite sets, one can easily consider extensions to much more general settings. The setting of finite fields is considered here because this special case was first considered by \textit{C. Wells} [Proc. Am. Math. Soc. 46, 347-350 (1974; Zbl 0298.12009)] for translations \(f(x)= x+a\), and the reviewer [Proc. Am. Math. Soc. 84, 315-317 (1982; Zbl 0498.12018)] for linear permutations \(f(x)= bx+a\).