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 of prime order and a degree d (with ), and a large dimension n. Let be a polynomial in n variables over of degree at most d. Let us say that P is *equidistributed* if it takes on each of its values close to equally often, in the sense that

for all , for some small (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 .
- 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 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 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 for some bounded k and “independent” polynomials 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 . 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 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.]

## 11 comments

Comments feed for this article

23 November, 2007 at 5:22 pm

Jonathan Vos Post“… in the sense that no non-trivial linear combination of these polynomials cannot be expressed efficiently in terms of lower degree polynomials.”

That double negative allows simplification to: “in the sense that every non-trivial linear combination of these polynomials can be expressed efficiently in terms of lower degree polynomials.”?

23 November, 2007 at 5:25 pm

Terence TaoSorry, the “cannot” should have been a “can”. It’s fixed now.

24 November, 2007 at 2:58 am

Emmanuel KowalskiThe equidistribution statement is fascinating…

It is interesting to compare it with what follows directly by applying the results of Deligne on exponential sums over finite fields; say for , after using additive characters modulo to detect the condition , the trivial character gives the expected main term for the number of solutions , and the rest is a sum of exponential sums of the type

with , for which one can apply the Riemann Hypothesis of Deligne to get cancellation. However, the dependency on the degree is not necessarily well-controlled in general.

A good example of what can happen is if the homogeneous part of degree of is non-singular (what is often called a Deligne polynomial from the side of algebraic geometry). Then Deligne showed that for non zero modulo , we have

and this, plugged into the remainder term, leads to equidistribution _only_ for

, roughly. So even in this very favorable case, your result is much stronger.

Note that Deligne’s bound is best possible in general, and so by using the type of assumptions (high-rank) in your paper, one may hope to improve this. In the other direction, your result implies some control of the “dual” expressions for the exponential sums (after applying the trace formula) which it would be really interesting to understand on the algebraic-geometry side.

25 November, 2007 at 10:05 am

Terence TaoDear Emmanuel: thanks for the comments! I had not realised that Deligne’s estimates were still so powerful in high dimension (the condition is fairly similar to our own condition , and we don’t have anywhere near as good explicit constants in our bounds, due to a heavy reliance on regularity lemmas).

The property of being non-singular is somewhat analogous to having “maximal” rank, though I am not sure what the precise connection is. For instance, if , where all polynomials are homogeneous and of low degree, then the level set contains the level set as a singularity if k is not too large compared with the dimension n and the degrees of the various polynomials. But perhaps the non-singularity hypothesis is not strong enough to detect all possible efficient representations of the polynomial in terms of lower degree polynomials.

25 November, 2007 at 10:41 pm

Emmanuel KowalskiThe non-singular case is the easiest to understand, but there are other more general results (mostly by Nick Katz), though they are more complicated to state (for instance in his paper “Estimates for ‘singular’ exponential sums”, IMRN 16, 1999).

In terms of being best possible, here is what happens for the non-singular case: then, for each

, there exist numbers , …, , each with

, so that

where . So having equidistribution here beyond means some additional compensation must exist in the sum over .

The worst case in Deligne’s theory would have something like

(except in degenerate cases where the polynomial is constant over ), for some absolute constant (the dependency on also depends in such generality on works of Bombieri, Adolphson and Sperber.)

I will read your paper to see if I see further connections…

11 April, 2008 at 9:09 pm

Conference update, part I « The Accidental Mathematician[...] Ben Green gave an update on the inverse Gowers conjecture. For the norm, this conjecture was proved by Green and Tao in 2005. Last year, Lovett-Meshulam-Samorodnitsky and (independently and about the same time) Green-Tao found finite fields counterexamples for norms with . However, these examples only work in finite fields of low characteristics. In a recent paper on distribution of polynomials over finite fields, Green and Tao proved that this particular type of counterexamples can’t occur if the characteristic of the fields is large enough; in particular there is still a good chance that the conjecture will be true in . (See Terry’s blog post on the subject.) [...]

27 October, 2008 at 12:41 pm

Alexhi every body, i’m searching about some implementation (code source) about multivaraite polynomial over finite fields can anyone help me ?

plese, thx

14 December, 2009 at 3:38 pm

Approximate bases, sunflowers, and nonstandard analysis « What’s new[...] over finite fields, which came up when studying the equidistribution of such polynomials (in this paper with Ben Green). The second comes up when is dealing not with a single finite collection of vectors, but rather [...]

20 May, 2010 at 9:44 pm

254B, Notes 5: The inverse conjecture for the Gowers norm I. The finite field case « What’s new[...] cases (a fact first observed by Lovett, Meshulam, and Samorodnitsky, and independently by Ben Green and myself), for instance if and ; this is ultimately due to the existence in those cases of non-classical [...]

11 January, 2011 at 6:59 am

The inverse conjecture for the Gowers norm over finite fields in low characteristic « What’s new[...] the mean of is large). Applying a general equidistribution theorem of Kaufman and Lovett (based on this earlier paper of Green and myself) this implies that is a function of a bounded number of multilinear forms of lower degree. Using [...]

7 December, 2013 at 4:06 pm

Ultraproducts as a Bridge Between Discrete and Continuous Analysis | What's new[…] infinitary statements, by giving an easy case of the polyomial regularity lemma, introduced by Ben Green and myself. Given a finite-dimensional vector space over a field and a natural number , we define a […]