Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-10-30T13:59:20Z No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T12:29:01Z (GMT) No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) / Made available in DSpace on 2018-11-23T12:29:01Z (GMT). No. of bitstreams: 1 ednailtonsantossilva.pdf: 606910 bytes, checksum: 393b9af5bb01a2b06e9ebb6ee0eee4cb (MD5) Previous issue date: 2018-09-13 / O objetivo desse trabalho é apresentar algumas classes clássicas e outras mais recentes de polinômios de permutação sobre corpos finitos. A fim de atingir esse objetivo, apresentamos a construção e uma lista de propriedades de corpos finitos, bem como uma introdução à teoria dos polinômios sobre corpos finitos. / The main goal of this text is to present some known classes of permutation polynomials over finite fields. With this goal, we begin by presenting the construction and some properties of finite fields, as well as an introduction to the theory of polynomials over finite fields.

The problem of polynomial representability of functions is central to many branches of mathematics. If the underlying set is a finite field, every function can be represented as a polynomial. In this thesis we consider polynomial representability over a special class of finite rings, namely, Zpn, where p is a prime and n is a positive integer. This problem has been studied in literature and the two notable results were given by Carlitz(1965) and Kempner(1921).While the Kempner’s method enumerates the set of distinct polynomial functions, Carlitz provides a necessary and sufficient condition for a function to be polynomial using Taylor series. Further, these results are existential in nature. The aim of this thesis is to provide an algorithmic characterization, given a prime p and a positive integer n, to determine whether a given function over Zpn is polynomially representable or not. Note that one can give an exhaustive search algorithm using the previous results. Our characterization involves describing the set of polynomial functions over Zpn with a ‘suitable’ generating set. We make use of this result to give an non-exhaustive algorithm to determine whether a given function over Zpn is polynomial representable.nβ

Soit q ⩾ 2 une puissance première fixe. L’objectif principal de cette thèse est d’étudier le comportement asymptotique de la fonction arithmétique Π_q(n,k) comptant le nombre de polynômes moniques de degré n et ayant exactement k facteurs irréductibles (avec multiplicité) sur le corps fini F_q. Warlimont et Car ont montré que l’objet Π_q(n,k) est approximativement distribué de Poisson lorsque 1 ⩽ k ⩽ A log n pour une constante A > 0. Plus tard, Hwang a étudié la fonction Π_q(n,k) pour la gamme complète 1 ⩽ k ⩽ n. Nous allons d’abord démontrer une formule asymptotique pour Π_q(n,k) en utilisant une technique analytique classique développée par Sathe et Selberg. Nous reproduirons ensuite une version simplifiée du résultat de Hwang en utilisant la formule de Sathe-Selberg dans le champ des fonctions. Nous comparons également nos résultats avec ceux analogues existants dans le cas des entiers, où l’on étudie tous les nombres naturels jusqu’à x avec exactement k facteurs premiers. En particulier, nous montrons que le nombre de polynômes moniques croît à un taux étonnamment plus élevé lorsque k est un peu plus grand que logn que ce que l’on pourrait supposer en examinant le cas des entiers. Pour présenter le travail ci-dessus, nous commençons d’abord par la théorie analytique des nombres de base dans le contexte des polynômes. Nous introduisons ensuite les fonctions arithmétiques clés qui jouent un rôle majeur dans notre thèse et discutons brièvement des résultats bien connus concernant leur distribution d’un point de vue probabiliste. Enfin, pour comprendre les résultats clés, nous donnons une discussion assez détaillée sur l’analogue de champ de fonction de la formule de Sathe-Selberg, un outil récemment développé par Porrit et utilisons ensuite cet outil pour prouver les résultats revendiqués. / Let q ⩾ 2 be a fixed prime power. The main objective of this thesis is to study the asymptotic behaviour of the arithmetic function Π_q(n,k) counting the number of monic polynomials that are of degree n and have exactly k irreducible factors (with multiplicity) over the finite field F_q. Warlimont and Car showed that the object Π_q(n,k) is approximately Poisson distributed when 1 ⩽ k ⩽ A log n for some constant A > 0. Later Hwang studied the function Π_q(n,k) for the full range 1 ⩽ k ⩽ n. We will first prove an asymptotic formula for Π_q(n,k) using a classical analytic technique developed by Sathe and Selberg. We will then reproduce a simplified version of Hwang’s result using the Sathe-Selberg formula in the function field. We also compare our results with the analogous existing ones in the integer case, where one studies all the natural numbers up to x with exactly k prime factors. In particular, we show that the number of monic polynomials grows at a surprisingly higher rate when k is a little larger than logn than what one would speculate from looking at the integer case. To present the above work, we first start with basic analytic number theory in the context of polynomials. We then introduce the key arithmetic functions that play a major role in our thesis and briefly discuss well-known results concerning their distribution from a probabilistic point of view. Finally, to understand the key results, we give a fairly detailed discussion on the function field analogue of the Sathe-Selberg formula, a tool recently developed by Porrit and subsequently use this tool to prove the claimed results.