ON COMPLETE MAPS AND VALUE SETS OF POLYNOMIALS OVER FINITE FIELDS

Leyla Işık
Mathematics, PhD Dissertation, 2015

Thesis Jury

Prof. Dr. Alev Topuzoğlu (Thesis Advisor), Assoc. Dr. Cem Güneri,

Assoc. Dr. Selda Küçükçiftçi, Prof. Dr. Erkay Savaş,

Assoc. Dr. Arne Winterhof

Date &Time: 8th, 2015 –  11 AM

Place: FENS 2019

Keywords : Finite Fields, Permutation Polynomials, Carlitz Rank, Complete Mapping Polynomials, Value Sets, Minimal Value Set of Polynomials, Spectrum.

Abstract

In this thesis we study several aspects of permutation polynomials over finite fields with odd characteristic. We present methods of construction of families of complete mapping polynomials; an important subclass of permutations. Our work on value sets of non-permutation polynomials focus on the structure of the spectrum of a particular class of polynomials.

Our main tool is a recent classification of permutation polynomials of finite field, based on their Carlitz rank.  After introducing the notation and terminology we use, we give basic properties of

permutation polynomials, complete mappings and value sets of polynomials in Chapter 1.

We present our results on complete mappings over finite fields in Chapter 2. Our main result in Section 2.2 shows that when q>2n+1, there is no complete mapping polynomial of Carlitz rank n, whose poles are all in a finite field of q elements. We note the similarity of this result to the well-known Chowla-Zassenhaus conjecture (1968), proven by Cohen (1990), which is on the non-existence of complete mappings of degree d over a finite field with p elements, when p is a prime and is sufficiently large with respect to d.  In Section 2.3 we give a sufficient condition for the construction of a family of complete mappings of Carlitz rank at most n. Moreover, for n=4,5,6 we obtain an explicit construction of complete mappings.

Chapter 3 is on the spectrum of the class of polynomials of the form F(x)=f(x)+x, where f  is a permutation polynomial of Carlitz rank at most n. Upper bounds for the cardinality of value sets of polynomials of the fixed degree d or fixed index l were obtained previously, which depend on d or l respectively. We show, for instance, that the upper bound in the case of a subclass is q-2, i.e., is independent of n.

We end this work by giving examples of complete mappings, obtained by our methods.