Abstract
The celebrated Weil bound for character sums says that for any lowdegree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform. The goal of higherorder Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"?
Previously, most of the work in this area was over fields of prime order. We extend the tools of higherorder Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are:
1. If P: K^n > K is a polynomial of degree <= d, and E[chi(P(x))] > K^{s} for some s > 0 and nontrivial additive character chi, then P is a function of O_{d, s}(1) many nonclassical polynomials of weight degree < d. The definition of nonclassical polynomials over nonprime fields is one of the contributions of this work.
2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n > K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field.
The tools of higherorder Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas.
(i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code.
(ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n > K can be decomposed as a particular composition of lesser degree polynomials.
(iii) For any fixed finite field K, we prove that all locally characterized affineinvariant properties of functions f: K^n > K are testable with onesided error.
BibTeX  Entry
@InProceedings{bhattacharyya_et_al:LIPIcs:2016:6646,
author = {Arnab Bhattacharyya and Abhishek Bhowmick and Chetan Gupta},
title = {{On HigherOrder Fourier Analysis over NonPrime Fields}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {23:123:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6646},
URN = {urn:nbn:de:0030drops66463},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.23},
annote = {Keywords: finite fields, higher order fourier analysis, coding theory, property testing}
}
Keywords: 

finite fields, higher order fourier analysis, coding theory, property testing 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 