Compositional attractors and enumeration of permutation polynomials over finite fields (Q1194295): Difference between revisions

Let \(R\) denote a finite algebra over the finite field \(\mathbb{F}_ q\) of \(q\) elements. The present paper is concerned with the group, denoted by \(PP_{\mathbb{F}_ q}(R)\), of all permutations of \(R\) which are representable, via substitution, by polynomials from \(\mathbb{F}_ q[x]\). More specifically, the paper gives a formula for the order of the group \(PP_{\mathbb{F}_ q}(R)\). The author first introduces the notion of a compositional attractor of \(R[x]\) which, by definition, is an ideal \(I\) in the ring \(R[x]\) having the additional property that \(f(g(x))\in I\) for all \(f(x)\in I\) and \(g(x)\in R[x]\). Of particular interest are the compositional attractors of the principal ideal domain \(\mathbb{F}_ q[x]\). It is shown that a monic polynomial \(f(x)\in\mathbb{F}_ q[x]\) generates a compositional attractor if and only if there are positive integers \(k_ 1\), \(k_ 2,\dots,k_ t\), such that \(f(x)\) is the least common multiple of the polynomials \(x^{q^{k_ i}}-x\). The author goes on to associate the group \(PP_{\mathbb{F}_ q}(R)\) with a certain compositional attractor \((f(x))\) in \(\mathbb{F}_ q[x]\) and, assuming a knowledge of \(f(x)\), he obtains a formula for the number of elements in the group \(PP_{\mathbb{F}_ q}(R)\) in terms of the factorization of \(f(x)\). The formula given in the paper contains as special cases formulas derived earlier by \textit{L. Carlitz} and \textit{D. R. Hayes} [Acta Arith. 21, 131- 135 (1972; Zbl 0207.051)] for \(R=\mathbb{F}_{q^ n}\) and by the reviewer [J. Comb. Theory, Ser. A 21, 147-154 (1976; Zbl 0337.12016)] for \(R=\mathbb{F}_{q^{n\times n}}\).