Paper Info
Title
New Extension of the Weil Bound for Character Sums with Applications to Coding
Abstract
The Weil bound for character sums is a deep result in Algebraic Geometry with many applications both in mathematics and in the theoretical computer science. The Weil bound states that for any polynomial $f(x)$ over a finite field $\mathbb{F}$ and any additive character $\chi:\mathbb{F} \to \mathbb{C}$, either $\chi(f(x))$ is a constant function or it is distributed close to uniform. The Weil bound is quite effective as long as $\deg(f) \ll \sqrt{|\mathbb{F}|}$, but it breaks down when the degree of $f$ exceeds $\sqrt{|\mathbb{F}|}$. As the Weil bound plays a central role in many areas, finding extensions for polynomials of larger degree is an important problem with many possible applications. In this work we develop such an extension over finite fields $\mathbb{F}_{p^n}$ of small characteristic: we prove that if $f(x)=g(x)+h(x)$ where $\deg(g) \ll \sqrt{|\mathbb{F}|}$ and $h(x)$ is a sparse polynomial of arbitrary degree but bounded weight degree, then the same conclusion of the classical Weil bound still holds: either $\chi(f(x))$ is constant or its distribution is close to uniform. In particular, this shows that the sub code of Reed-Muller codes of degree $\omega(1)$ generated by traces of sparse polynomials is a code with near optimal distance, while Reed-Muller of such a degree has no distance (i.e. $o(1)$ distance), this is one of the few examples where one can prove that sparse polynomials behave differently from non-sparse polynomials of the same degree. As an application we prove new general results for affine invariant codes. We prove that any affine-invariant subspace of quasi-polynomial size is (1) indeed a code (i.e. has good distance) and (2) is locally testable. Previous results for general affine invariant codes were known only for codes of polynomial size, and of length $2^n$ where $n$ needed to be a prime. Thus, our techniques are the first to extend to general families of such codes of super-polynomial size, where we also remove the requirement from $n$ to be a prime. The proof is based on two main ingredients: the extension of the Weil bound for character sums, and a new Fourier-analytic approach for estimating the weight distribution of general codes with large dual distance, which may be of independent interest.
Year
DOI
Venue
2011
10.1109/FOCS.2011.41
Foundations of Computer Science
Keywords
Field
DocType
Reed-Muller codes,polynomials,Reed-Muller codes,Weil bound extension,additive character,algebraic geometry,arbitrary degree,character sums,coding application,computer science,constant function,sparse polynomial,sparse polynomials,super polynomial size,Weil bound,affine invariant codes,character sums,property testing
Prime (order theory),Discrete mathematics,Algebraic geometry,Combinatorics,Finite field,Polynomial,Constant function,Reed–Muller code,Linear code,Mathematics,Bounded function
Conference
ISSN
ISBN
Citations 
0272-5428
978-1-4577-1843-4
9
PageRank 
References 
Authors
0.66
5
2
Name
Order
Citations
PageRank
Tali Kaufman149938.33
Shachar Lovett252055.02