Permutation polynomials: iteration of shift and inversion maps over finite fields

Abstract

We show that all permutations in $S_n$ can be generated by affine unicritical polynomials. We use the $\mathrm{PGL}$ group structure to compute the cycle structure of permutations with low Carlitz rank. The tree structure of the group generated by shift and inversion maps is used to study the randomness properties of permutation polynomials.