On the cycle structure of permutation polynomials

Official URL: http://192.168.1.20/record=b1225695 (Table of Contents)

L. Carlitz observed in 1953 that for any a € F*q, the transposition (0 a) can be represented by the polynomial Pa(x) = -a[2](((x - a)[q-2] + a-[1])[q-2] - a)[q-2] which shows that the group of permutation polynomials over Fq is generated by the linear polynomials ax + b, a, b € Fq, a≠0, and x[q-2]. Therefore any permutation polynomial over Fq can be represented as Pn = (...((a[0]x + a[1])[q-2] +a[2]) [q-2] ... + a[n])[q-2] + a[n+1], for some n ≥ 0. In this thesis we study the cycle structure of permutation polynomials Pn, and we count the permutations Pn, n ≤ 3, with a full cycle. We present some constructions of permutations of the form Pn with a full cycle for arbitrary n. These constructions are based on the so called binary symplectic matrices. The use of generalized Fibonacci sequences over Fq enables us to investigate a particular subgroup of Sq, the group of permutations on Fq. In the last chapter we present results on this special group of permutations.