On the cycle stucture of permutation polynomials

Abstract

L. Carlitz (0 a) devrinimininpa(x) = -a^2(((x - a)^(q-2) + a^-1)^(q-2) - a)^(q-2)polinomu tarafından temsil edilebileceğini, dolayısıyla Fq üzerindeki permü-tasyon polinomlarının oluşturduğu grubun doğrusal polinomlar ax+b; a,b,Fq cisminin elemanları,a sıfırdan farklı, vex^(q-2) tarafından gerildiğini göstermiştir. O halde Fq üzerindekiherhangi bir permütasyon polinomu en az bir n içinPn(x) = (... ((a0x + a1)^(q-2) + a2)^(q-2) +...+ an)^(q-2) + an+1;şeklinde yazılabilir.Bu tezde, n<=3 için Pn şeklindeki permütasyon polinomlarının çevrimyapısı incelenmiş ve tam çevrime sahip olanların sayısıyla ilgili sonuçlar eldeedilmiştir.Herhangi bir n tek sayısı için, tam çevrime sahip Pn polinomlarının inşasıiçin ikili simetrik matrisleri kullanan metodlar geliştirilmiştir.Fq üzerinde tanımlı genelleştirilmiş Fibonacci dizilerinin kullanımı permütasyonpolinomları grubunun belirli bir altgrubunu incelenmesine olanaksağlamıstır. Tezin son bölümünde bu özel altgrupla ilgili sonuçlar verilmiştir.

L. Carlitz observed in 1953 that for any a in Fqthe transposition (0 a)can be represented by the polynomialpa(x) = -a2(((x - a)^(q-2) + a^-1)^(q-2) - a)^(q-2)which shows that the group of permutation polynomials over Fq is generatedby the linear polynomials ax + b; a; b in Fq; a nonzero, and x^(q-2).Therefore any permutation polynomial over Fq can be represented asPn = (...((a0x + a1)^(q-2) + a2)^(q-2) +...+ an)^(q-2) + an+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 someconstructions of permutations of the form Pn with a full cycle for arbitraryodd n. These constructions are based on the so called binary symplecticmatrices.The use of generalized Fibonacci sequences over Fq enables us to investigatea particular subgroup of Sq, the group of permutations on Fq. In thelast chapter we present results on this special group of permutations.