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 $\F$ and any additive character $\chi:\F \to \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{|\F|}$, but it breaks down when the degree of $f$ exceeds $\sqrt{|\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 $\F_{p^n}$ of small characteristic: we prove that if $f(x)=g(x)+h(x)$ where $\deg(g) \ll \sqrt{|\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 subcode 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.

(1) Fixed a mistake: the result holds only for affine invariant codes of up to quasi-polynomial size (and not exponential size, as was claimed in the first draft).
(2) Added a proof that in this regime all affine invariant codes are indeed codes (i.e. have good distance).

In this work we consider linear codes which are locally testable
in a sublinear number of queries. We give the first general family
of locally testable codes of exponential size. Previous results of
this form were known only for codes of quasi-polynomial size (e.g.
Reed-Muller codes). We accomplish this by showing that any affine
invariant code $\mathcal{C}$ over $\mathbb{F}_{p^n}$ of size $p^{p^{\Omega(n)}}$
is locally testable using $poly(\log_p{|\mathcal{C}|}/n)$ queries.
Previous general result for affine invariant codes were known only
for sparse codes, i.e. codes of size $p^{O(n)}$. The main new
ingredients used in our proof are a new extension of the Weil bound for character
sums, and a Fourier-analytic approach for estimating the weight
distribution of affine invariant codes.