zbMATH — the first resource for mathematics

On the Carlitz rank of permutation polynomials. (English) Zbl 1232.11124
Summary: A well-known result of L. Carlitz [Proc. Am. Math. Soc. 4, 538 (1953; Zbl 0052.03704)], that any permutation polynomial \(p(x)\) of a finite field \(\mathbb F_q\) is a composition of linear polynomials and the monomial \(x(q-2)\) implies that \(p(x)\) can be represented by a polynomial \(P_n(x) = (...((a(0)x + a(1))(q-2) + a(2))(q-2)...+ a(n))(q-2) + a(n+1)\). for some \(n\geq 0\). The smallest integer \(n\), such that \(P_n(x)\) represents \(p(x)\) is of interest since it is the least number of “inversions” \(x(q-2)\), needed to obtain \(p(x)\). We define the Carlitz rank of \(p(x)\) as \(n\), and focus here on the problem of evaluating it. We also obtain results on the enumeration of permutations of \(\mathbb F_q\) with a fixed Carlitz rank.

11T06 Polynomials over finite fields
Full Text: DOI
[1] Carlitz, L., Permutations in a finite field, Proc. amer. math. soc., 4, 538, (1953) · Zbl 0052.03704
[2] Comtet, L., Advanced combinatorics, the art of finite and infinite expansions, (1974), Reidel Dordrecht
[3] Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., On the cycle structure of permutation polynomials, Finite fields appl., 14, 593-614, (2008) · Zbl 1153.11057
[4] Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., Enumeration of a class of sequences generated by inversions, () · Zbl 1156.05004
[5] Lidl, R.; Niederreiter, H., Finite fields, Encyclopedia math. appl., vol. 20, (1997), Cambridge Univ. Press Cambridge
[6] Shparlinski, I.E., Finite fields: theory and computation. the meeting point of number theory, computer science, coding theory and cryptography, Math. appl., vol. 477, (1999), Kluwer Acad. Publ. Dordrecht · Zbl 0967.11052
[7] Sloane, N.J., On-line Encyclopedia of integer sequences, published electronically at · Zbl 1044.11108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.