On algebraic and analytic properties of polynomials over finite fields

Abstract

In this work, we provide some new interesting results in the emerging theory of higher-order Fourier analysis. The goal of this theory is to understand the connection between the algebraic structure and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, say Problem 1: what is the tradeoff between the equidistribution of ?(P(x))\chi(P(x))?(P(x)) and its “structure” for any additive character ?\chi? and polynomial PPP over a finite field Specifically, this thesis consists of two major results. Our first result solves Problem 1 over general fields. Previously, most of the work on the problem was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let KKK be a field extension of a prime field Fp\mathbb{F}_pFp. We show: if P:K?KP : K \to KP:K?K is a polynomial of degree ?d\leq d?d, and ?E[?(P(x))]?>?K???| \mathbb{E}[\chi(P(x))] | > |K|^{-elta}?E[?(P(x))]?>?K??? for some ?>0\delta > 0?>0 and non-trivial additive character ?\chi?, then PPP is a function of many non-classical polynomials of weight degree ?d\leq d?d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work. Next, we explore the possibility of using the techniques of higher-order Fourier analysis in practice. Our second result is we design algorithms inspired by higher-order Fourier analysis for decomposing compositions of low-degree polynomials over prime fields. Specifically, our algorithm applies to the case when P=?i=1sQi,1Qi,2P = \sum_{i=1}^s Q_{i,1} Q_{i,2}P=i=1?sQi,1Qi,2 for some s>0s > 0s>0 and randomly chosen quadratic polynomials Qi,1,Qi,2Q_{i,1}, Q_{i,2}Qi,1,Qi,2. The goal here is to retrieve the quadratic polynomials given PPP, and this seems to be out of the reach for known standard factorization algorithms. Finally, we perform experiments for the general polynomial decomposition algorithm in [Bhal14, BHT15] which show that the algorithm can be very inefficient in practice.