Ben Green and I have just uploaded our joint paper, “The distribution of polynomials over finite fields, with applications to the Gowers norms“, to the arXiv, and submitted to Contributions to Discrete Mathematics. This paper, which we first announced at the recent FOCS meeting, and then gave an update on two weeks ago on this blog, is now in final form. It is being made available simultaneously with a closely related paper of Lovett, Meshulam, and Samorodnitsky.

In the previous post on this topic, I focused on the negative results in the paper, and in particular the fact that the inverse conjecture for the Gowers norm fails for certain degrees in low characteristic. Today, I’d like to focus instead on the positive results, which assert that for polynomials in many variables over finite fields whose degree is less than the characteristic of the field, one has a satisfactory theory for the distribution of these polynomials. Very roughly speaking, the main technical results are:

  • A regularity lemma: Any polynomial can be expressed as a combination of a bounded number of other polynomials which are regular, in the sense that no non-trivial linear combination of these polynomials can be expressed efficiently in terms of lower degree polynomials.
  • A counting lemma: A regular collection of polynomials behaves as if the polynomials were selected randomly. In particular, the polynomials are jointly equidistributed.

To describe these results more precisely, let us fix a small finite field {\Bbb F} of prime order and a degree d (with d < |{\Bbb F}|), and a large dimension n. Let P: {\Bbb F}^n \to {\Bbb F} be a polynomial in n variables over {\Bbb F} of degree at most d. Let us say that P is equidistributed if it takes on each of its |{\Bbb F}| values close to equally often, in the sense that

| \{ x\in {\Bbb F}^n: P(x) = c \}| = (1 + O(\varepsilon)) |{\Bbb F}|^{n-1}

for all c \in {\Bbb F}, for some small \varepsilon (the exact value of this parameter will not be too relevant for this discussion). A basic question is then: which polynomials P are equidistributed?

For low degree polynomials, the answer can be worked out quickly:

  • If P has degree 0, then it is never equidistributed.
  • If P has degree 1, then it is equidistributed as long as it is not constant (i.e. it is not actually of degree 0). This fact, of course, is the starting point of Fourier analysis on {\Bbb F}^n.
  • If P has degree 2 (i.e. it is basically a quadratic form), then it is equidistributed as long as the quadratic form has high rank, or equivalently that it cannot be efficiently expressed in terms of a few degree 1 polynomials. This can be made more formal and rigorous by computing some Gauss sums over finite fields.

Extrapolating from these examples, we thus see that a polynomial P tends to be equidistributed, unless it is a combination of lower degree polynomials. Conversely, any combination of lower degree polynomials is unlikely to be equidistributed. For instance, if P = Q^2 for some polynomial Q of half the degree, then P cannot be equidistributed, since it only takes on square values. A polynomial P which factors as P=QR for some lower degree polynomials Q, R is likely to be zero about twice as often as one would ordinarily expect, which would again contradict equidistribution. More generally, a polynomial which takes the form P = Q_1 R_1 + \ldots + Q_k R_k for some bounded k and “independent” polynomials Q_1,\ldots,Q_k,R_1,\ldots,R_k is again likely to have slight irregularities in distribution, although the regularity should improve as k increases.

Let us informally say that polynomial P has low rank if it can be expressed as a bounded combination of polynomials of lower degree, and high rank otherwise. Our first main result is:

Equidistribution theorem. Let P be a polynomial of degree less than |{\Bbb F}|. If P is high rank, then it is equidistributed.

(The result may well be true for higher degree polynomials, but our methods do not extend to that case; we need the high characteristic in order to recover a polynomial from its derivatives using a version of the Taylor expansion formula.)

Our argument begins by invoking a recent lemma of Bogdanov and Viola (as discussed previously on this blog), which shows that if P is not equidistributed, then it is very close to a low rank function. The main remaining task is then to obtain a certain rigidity property for low rank polynomials, namely that any polynomial which is sufficiently close to a low rank polynomial, is itself a low rank polynomial. This is done by testing the polynomial on various cubes in order to “correct” for errors; the main difficulty is a combinatorial one, counting the number of “good” cubes and ensuring that they are in sufficiently plentiful supply. This requires using the above equidistribution theorem, but for polynomials of strictly lower degree, allowing for an inductive argument to go through.

The equidistribution theorem implies the counting lemma by standard Fourier analytic techniques, and the regularity lemma is obtained by following the obvious reduction algorithm to eliminate any low rank dependencies among polynomials, similarly to how one can replace a finite collection of linearly dependent vectors with linearly independent ones with the same span, by repeatedly substituting away any dependencies. Putting these lemmas together, one can rather quickly verify the inverse conjecture for the Gowers norm for polynomials of degree less than the characteristic.

The paper also has some assorted related results, such as a Nullstellensatz which shows that a polynomial can only vanish on a “high rank” variety when it is a linear combination (in the ring of polynomials) of its defining polynomials (with sharp control on the degrees of the coefficient polynomials involved in this combination), and a recurrence result which shows that if a collection of boundedly many polynomials of bounded degree vanish at one point, then they must vanish at a large number of other points as well. The usual nullstellensatz of Hilbert requires that the ambient field {\Bbb F} is algebraically closed, which is of course highly false for finite fields; however, the high-rank assumption can compensate for this (so much so, in fact, that one no longer needs to mess around with radicals).

[Update, Nov 20: typo fixed.]

About these ads