Tamar Ziegler and I have just uploaded to the arXiv our paper “The inverse conjecture for the Gowers norm over finite fields in low characteristic“, submitted to Annals of Combinatorics. This paper completes another case of the inverse conjecture for the Gowers norm, this time for vector spaces {{\bf F}^n} over a fixed finite field {{\bf F} = {\bf F}_p} of prime order; with Vitaly Bergelson, we had previously established this claim when the characteristic of the field was large, so the main new result here is the extension to the low characteristic case. (The case of a cyclic group {{\bf Z}/N{\bf Z}} or interval {[N]} was established by Ben Green and ourselves in another recent paper. For an arbitrary abelian (or nilpotent) group, a general but less explicit description of the obstructions to Gowers uniformity was recently obtained by Szegedy; the latter result recovers the high-characteristic case of our result (as was done in a subsequent paper of Szegedy), as well as our results with Green, but it is not immediately evident whether Szegedy’s description of the obstructions matches up with the one predicted by the inverse conjecture in low characteristic.)

The statement of the main theorem is as follows. Given a finite-dimensional vector space {V = {\bf F}^n} and a function {f: V \rightarrow {\bf C}}, and an integer {s \geq 0}, one can define the Gowers uniformity norm {\|f\|_{U^{s+1}(V)}} by the formula

\displaystyle \|f\|_{U^{s+1}(V)} := \left( \mathop{\bf E}_{x,h_1,\ldots,h_{s+1} \in V} \Delta_{h_1} \ldots \Delta_{h_{s+1}} f(x) \right)^{1/2^{s+1}}

where {\Delta_h f(x) := f(x+h) \overline{f(x)}}. If {f} is bounded in magnitude by {1}, it is easy to see that {\|f\|_{U^{s+1}(V)}} is bounded by {1} also, with equality if and only if {f(x) = e(P)} for some non-classical polynomial {P: V \rightarrow {\bf R}/{\bf Z}} of degree at most {s}, where {e(x) := e^{2\pi ix}}, and a non-classical polynomial of degree at most {s} is a function whose {s+1^{th}} “derivatives” vanish in the sense that

\displaystyle \partial_{h_1} \ldots \partial_{h_{s+1}} P(x) = 0

for all {x,h_1,\ldots,h_{s+1} \in V}, where {\partial_h P(x) := P(x+h) - P(x)}. Our result generalises this to the case when the uniformity norm is not equal to {1}, but is still bounded away from zero:

Theorem 1 (Inverse conjecture) Let {f: V \rightarrow {\bf C}} be bounded by {1} with {\|f\|_{U^{s+1}(V)} \geq \delta > 0} for some {s \geq 0}. Then there exists a non-classical polynomial {P: V \rightarrow {\bf R}/{\bf Z}} of degree at most {s} such that {|\langle f, e(P) \rangle_{L^2(V)}| := |{\bf E}_{x \in V} f(x) e(-P(x))| \geq c(s,p, \delta) > 0}, where {c(s,p, \delta)} is a positive quantity depending only on the indicated parameters.

This theorem is trivial for {s=0}, and follows easily from Fourier analysis for {s=1}. The case {s=2} was done in odd characteristic by Ben Green and myself, and in even characteristic by Samorodnitsky. In two papers, one with Vitaly Bergelson, we established this theorem in the “high characteristic” case when the characteristic {p} of {{\bf F}} was greater than {s} (in which case there is essentially no distinction between non-classical polynomials and their classical counterparts, as discussed previously on this blog). The need to deal with genuinely non-classical polynomials is the main new difficulty in this paper that was not dealt with in previous literature.

In our previous paper with Bergelson, a “weak” version of the above theorem was proven, in which the polynomial {P} in the conclusion had bounded degree {O_{s,p}(1)}, rather than being of degree at most {s}. In the current paper, we use this weak inverse theorem to reduce the inverse conjecture to a statement purely about polynomials:

Theorem 2 (Inverse conjecture for polynomials) Let {s \geq 0}, and let {P: V \rightarrow {\bf C}} be a non-classical polynomial of degree at most {s+1} such that {\|e(P)\|_{U^{s+1}(V)} \geq \delta > 0}. Then {P} has bounded rank in the sense that {P} is a function of {O_{s,p,\delta}(1)} polynomials of degree at most {s}.

This type of inverse theorem was first introduced by Bogdanov and Viola. The deduction of Theorem 1 from Theorem 2 and the weak inverse Gowers conjecture is fairly standard, so the main difficulty is to show Theorem 2.

The quantity {-\log_{|{\bf F}|} \|e(P)\|_{U^{s+1}(V)}^{1/2^{s+1}}} of a polynomial {P} of degree at most {s+1} was denoted the analytic rank of {P} by Gowers and Wolf. They observed that the analytic rank of {P} was closely related to the rank of {P}, defined as the least number of degree {s} polynomials needed to express {P}. For instance, in the quadratic case {s=1} the two ranks are identical (in odd characteristic, at least). For general {s}, it was easy to see that bounded rank implied bounded analytic rank; Theorem 2 is the converse statement.

We tried a number of ways to show that bounded analytic rank implied bounded rank, in particular spending a lot of time on ergodic-theoretic approaches, but eventually we settled on a “brute force” approach that relies on classifying those polynomials of bounded analytic rank as precisely as possible. The argument splits up into establishing three separate facts:

  1. (Classical case) If a classical polynomial has bounded analytic rank, then it has bounded rank.
  2. (Multiplication by {p}) If a non-classical polynomial {P} (of degree at most {s+1}) has bounded analytic rank, then {pP} (which can be shown to have degree at most {\max(s-p,0)}) also has bounded analytic rank.
  3. (Division by {p}) If {Q} is a non-clsasical polynomial of degree {\max(s-p,0)} of bounded rank, then there is a non-classical polynomial {P} of degree at most {s+1} of bounded rank such that {pQ=P}.

The multiplication by {p} and division by {p} facts allow one to easily extend the classical case of the theorem to the non-classical case of the theorem, basically because classical polynomials are the kernel of the multiplication-by-{p} homomorphism. Indeed, if {P} is a non-classical polynomial of bounded analytic rank of the right degree, then the multiplication by {p} claim tells us that {pP} also has bounded analytic rank, which by an induction hypothesis implies that {pP} has bounded rank. Applying the division by {p} claim, we find a bounded rank polynomial {P'} such that {pP = pP'}, thus {P} differs from {P'} by a classical polynomial, which necessarily has bounded analytic rank, hence bounded rank by the classical claim, and the claim follows.

Of the three claims, the multiplication-by-{p} claim is the easiest to prove using known results; after a bit of Fourier analysis, it turns out to follow more or less immediately from the multidimensional Szemerédi theorem over finite fields of Bergelson, Leibman, and McCutcheon (one can also use the density Hales-Jewett theorem here if one desires).

The next easiest claim is the classical case. Here, the idea is to analyse a degree {s+1} classical polynomial {P: V \rightarrow {\bf F}} via its derivative {d^{s+1} P: V^{s+1} \rightarrow {\bf F}}, defined by the formula

\displaystyle d^{s+1} P( h_1,\ldots,h_{s+1}) := \partial_{h_1} \ldots \partial_{h_{s+1}} P(x)

for any {x,h_1,\ldots,h_{s+1} \in V} (the RHS is independent of {x} as {P} has degree {s+1}). This is a multilinear form, and if {P} has bounded analytic rank, this form is biased (in the sense that the mean of {e(d^{s+1} P)} is large). Applying a general equidistribution theorem of Kaufman and Lovett (based on this earlier paper of Green and myself) this implies that {d^{s+1} P} is a function of a bounded number of multilinear forms of lower degree. Using some “regularity lemma” theory to clean up these forms so that they have good equidistribution properties, it is possible to understand exactly how the original multilinear form {d^{s+1} P} depends on these lower degree forms; indeed, the description one eventually obtains is so explicit that one can write down by inspection another bounded rank polynomial {Q} such that {d^{s+1} P} is equal to {d^{s+1} Q}. Thus {P} differs from the bounded rank polynomial {Q} by a lower degree error, which is automatically of bounded rank also, and the claim follows.

The trickiest thing to establish is the division by {p} claim. The polynomial {Q} is some function {F(R_1,\ldots,R_m)} of lower degree polynomials {R_1,\ldots,R_m}. Ideally, one would like to find a function {F'(R_1,\ldots,R_m)} of the same polynomials with {pF' = F}, such that {F'(R_1,\ldots,R_m)} has the correct degree; however, we have counterexamples that show that this is not always possible. (These counterexamples are the main obstruction to making the ergodic theory approach work: in ergodic theory, one is only allowed to work with “measurable” functions, which are roughly analogous in this context to functions of the indicated polynomials {Q, R_1,\ldots,R_m} and their shifts.) To get around this we have to first apply a regularity lemma to place {R_1,\ldots,R_m} in a suitably equidistributed form (although the fact that {R_1,\ldots,R_m} may be non-classical leads to a rather messy and technical description of this equidistribution), and then we have to extend each {R_j} to a higher degree polynomial {R'_j} with {pR'_j = R_j}. There is a crucial “exact roots” property of polynomials that allows one to do this, with {R'_j} having degree exactly {p-1} higher than {R_j}. It turns out that it is possible to find a function {P = F'(R'_1,\ldots,R'_m)} of these extended polynomials that have the right degree and which solves the required equation {pP=Q}; this is established by classifying completely all functions of the equidistributed polynomials {R_1,\ldots,R_m} or {R'_1,\ldots,R'_m} that are of a given degree.