On the Carlitz rank of permutation polynomials

A well-known result of Carlitz, that any permutation polynomial ℘(x) of a finite field Fq is a composition of linear polynomials and the monomial xq−2, implies that ℘(x) can be represented by a polynomial Pn(x)=(⋯((a0x+a1)q−2+a2)q−2⋯+an)q−2+an+1, for some n⩾0. The smallest integer n, such that Pn(x) represents ℘(x) is of interest since it is the least number of “inversions” xq−2, needed to obtain ℘(x). We define the Carlitz rank of ℘(x) as n, and focus here on the problem of evaluating it. We also obtain results on the enumeration of permutations of Fq with a fixed Carlitz rank.