In this paper, two structural results concerning low degree polynomials over finite fields are given. The first states that over any finite field $\mathbb{F}$, for any polynomial $f$ on $n$ variables with degree $d \le \log(n)/10$, there exists a subspace of $\mathbb{F}^n$ with dimension $\Omega(d \cdot n^{1/(d-1)})$ on which $f$ is constant. This result is shown to be tight. Stated differently, a degree $d$ polynomial cannot compute an affine disperser for dimension smaller than $\Omega(d \cdot n^{1/(d-1)})$. Using a recursive argument, we obtain our second structural result, showing that any degree $d$ polynomial $f$ induces a partition of $\mathbb{F}^n$ to affine subspaces of dimension $\Omega(n^{1/(d-1)!})$, such that $f$ is constant on each part.

We extend both structural results to more than one polynomial. We further prove an analog of the first structural result to sparse polynomials (with no restriction on the degree) and to functions that are close to low degree polynomials. We also consider the algorithmic aspect of the two structural results.

Our structural results have various applications, two of which are:

* Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over any finite field any affine extractor is also an extractor for varieties with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over $\mathbb{F}_2$.

* Ben-Sasson and Kopparty [SIAM J. C 2012] proved that any degree $3$ affine disperser over a prime field is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.

The main change was extending the structural result from the binary field to all finite fields. Furthermore, new results concerning the structure of sparse polynomials, and functions that are close to low degree polynomials are given.

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. Stated differently, a degree d polynomial cannot compute an affine disperser for dimension smaller than $\Omega(n^{1/(d-1)})$. Using a recursive argument, we obtain our second structural result, showing that any degree d polynomial f induces a partition of $\mathbb{F}_2^n$ to affine subspaces of dimension $\Omega(n^{1/(d-1)!})$, such that f is constant on each part. We extend both structural results to more than one polynomial, and consider the algorithmic aspect of these results.

Our structural results have various applications:

* Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over $\mathbb{F}_2$, any affine extractor is also an extractor for varieties, with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over $\mathbb{F}_2$.

* Ben-Sasson and Kopparty [SIAM J. Computing 2012] proved that any degree $3$ affine disperser is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.

* Implicit in Razborov's work [CAAML 1988], the existence of a depth $3$ $\mathrm{AC}^0[\oplus]$ circuit that computes an optimal affine extractor was shown. We complement this result by showing that depth $2$ $\mathrm{AC}^0[\oplus]$ circuits cannot compute affine dispersers for sub-polynomial dimension. This can be interpreted as a generalization of our structural results to sparse polynomials (regardless of their degree). We also give an alternative proof for the depth $3$ case.

We deduce several other corollaries from the structural results, one of which states that any excellent affine extractor has small correlation with low degree polynomials. Another is a lower bound on the granularity of the Fourier spectrum of low degree polynomials.