Vitaly Bergelson, Tamar Ziegler, and I have just uploaded to the arXiv our paper “An inverse theorem for the uniformity seminorms associated with the action of F^\infty_p“. This paper establishes the ergodic inverse theorems that are needed in our other recent paper to establish the inverse conjecture for the Gowers norms over finite fields in high characteristic (and to establish a partial result in low characteristic), as follows:

Theorem. Let {\Bbb F} be a finite field of characteristic p.  Suppose that X = (X,{\mathcal B},\mu) is a probability space with an ergodic measure-preserving action (T_g)_{g \in {\Bbb F}^\omega} of {\Bbb F}^\omega.  Let f \in L^\infty(X) be such that the Gowers-Host-Kra seminorm \|f\|_{U^k(X)} (defined in a previous post) is non-zero.

  1. In the high-characteristic case p \geq k, there exists a phase polynomial g of degree <k (as defined in the previous post) such that |\int_X f \overline{g}\ d\mu| > 0.
  2. In general characteristic, there exists a phase polynomial of degree <C(k) for some C(k) depending only on k such that |\int_X f \overline{g}\ d\mu| > 0.

This theorem is closely analogous to a similar theorem of Host and Kra on ergodic actions of {\Bbb Z}, in which the role of phase polynomials is played by functions that arise from nilsystem factors of X.  Indeed, our arguments rely heavily on the machinery of Host and Kra.

The paper is rather technical (60+ pages!) and difficult to describe in detail here, but I will try to sketch out (in very broad brush strokes) what the key steps in the proof of part 2 of the theorem are.  (Part 1 is similar but requires a more delicate analysis at various stages, keeping more careful track of the degrees of various polynomials.)

– A model case –

The theorem needs to be proven for all functions f with non-zero Gowers-Host-Kra norm in all ergodic systems, but to simplify the exposition let us look at a fairly specific type of function in a fairly specific type of system.  Namely, we will assume that the system X is a circle extension X = Y \times_\rho S^1 of another ergodic {\Bbb F}^\omega-system Y by a cocycle \rho: {\Bbb F}^\omega \times Y \to S^1, i.e. a measurable function obeying the cocycle identity

\rho(g+h,y) = \rho(g,y) \rho(h,T_g y) (1)

for all g,h \in F^\omega and almost every y \in Y.  The circle extension X is defined as the Cartesian product \{ (y,u): y \in Y, u \in S^1 \} with shift map T_g: (y,u) \mapsto (T_g y, \rho(g,y) u) (here we abuse notation a bit and use T_g to simultaneously denote the action on X and on Y).  The function f\in L^\infty(X) we shall pick is the vertical coordinate function f(y,u) := u.

Finally, we make the assumption that the base space Y (or more precisely, its \sigma-algebra) is already generated by phase polynomials of bounded degree.

Very roughly speaking, we can reduce the general case to the above case by an induction on k, together with some standard theory of Mackey and Furstenberg on isometric extensions and group extensions (cf. my lectures on the topological dynamics counterpart to these topics), and of Furstenberg-Weiss on characteristic factors, together with some Fourier analysis to reduce matters from (abelian) group extensions to circle extensions.  These reductions are standard in the ergodic theory literature, but somewhat technical, and I will not discuss them further here.

– Cocycles and coboundaries –

Our task is to show that the vertical coordinate function f(y,u)=u, which we assume to have non-zero Gowers-Host-Kra seminorm, correlates with some bounded degree polynomial.  To do this, it suffices to express the cocycle \rho in the form

\rho(g,y) = P(g,y) \Delta_g F(y) (2)

for some measurable functions F: Y \to S^1, P: {\Bbb F}^\omega \times Y \to S^1, where \Delta_g F(y) := F(T_g y) \overline{F(y)} and P(g,\cdot) is a phase polynomial of bounded degree for each g \in {\Bbb F}^\omega.  Indeed, we can rearrange (2) as

\Delta_g [ f(y,u) / F(y) ] = P(g,y)

and so all derivatives of f(y,u) / F(y) are phase polynomials of bounded degree, which implies that f(y,u)/F(y) is itself a phase polynomial of bounded degree, thus f(y,u) is the product of F with a phase polynomial of bounded degree.  But F \in L^\infty(Y), which is generated by phase polynomials of bounded degree, and so f(y,u) can be approximated by a linear combination of phase polynomials of bounded degree, and thus in particular must correlate with at least one of them, as desired.

It thus remains to establish (2).  Cocycles of the form \Delta_g F(y) are known as coboundaries, and two cocycles which differ by a coboundary are said to be cohomologous [see my previous post for further discussion].  Thus, our task is to show the cocycle \rho is cohomologous to a phase polynomial of bounded degree.

– The finite type condition –

We have yet to use the hypothesis that the vertical coordinate function f: (y,u) \mapsto u has non-zero U^k(X) norm.   For this, we use a key observation of Host-Kra that this hypothesis implies (in fact it is basically equivalent to) a certain finite type condition on the cocycle \rho.  We derive this condition somewhat informally as follows.  If \|f\|_{U^k(X)} is non-zero, then this means that the expected value of the expression

d^{[k]} f( x ) := \prod_{\omega \in \{0,1\}^k} f(x_\omega)^{\hbox{sgn}(\omega)} (3)

is non-zero, where x = (x_\omega)_{\omega \in \{0,1\}^k} ranges over “k-dimensional parallelopipeds” in X.  (This can be made precise by using the cubic measures \mu^{[k]} of Host and Kra, but let us ignore this technical detail here.)

One way to make a k-dimensional parallelopiped is to start with a (k-1)-dimensional parallelopiped y = (y_\omega)_{\omega \in \{0,1\}^{k-1}}, shift it by a group element g, and glue the two (k-1)-dimensional parallelopipeds together.  When one does so, the quantity (3) simplifies to

d^{[k-1]} \rho(g,y) := \prod_{\omega \in \{0,1\}^k} \rho(g,y_\omega)^{\hbox{sgn}(\omega)}.  (4)

Note that as \rho does not depend on the vertical coordinate u, one can view the y_\omega as living in Y rather than in X.

We expect (4) to have a non-zero average in some sense.  If we define the limiting average

F(y) := {\Bbb E}_g d^{[k-1]} \rho(g,y)

(where {\Bbb E}_g denotes the limit after averaging g along a Følner sequence) we thus expect F to be non-zero at least some of the time; to simplify the discussion let us pretend that it is in fact always non-zero.  The cocycle equation (1) implies that

F( T_g y ) = d^{[k-1]} \rho(g, y) F(y)

and so, after defining F' := F/|F|, we see that d^{[k-1]} \rho(h, y) is a coboundary:

d^{[k-1]} \rho(g,y) = \Delta_g F(y).  (5)

When \rho obeys this condition, we say that it is of type <k-1.  The challenge is now to “integrate” the derivative d^{[k-1]} out of (5) and obtain (2).

– Vertical differentiation –

The parallelopiped-based derivatives d^{[k-1]} are difficult to work with directly (unless k is very small).  It is convenient to replace them with a simpler type of derivative, a “vertical” derivative.  To explain this, we first decompose Y as an extension Y = Z \times_\phi U of a “simpler” system Z (where “simpler” means, roughly speaking, that we can generate it using polynomials of strictly lower degree than what one needs for Y), where U is a compact abelian group and \phi: {\Bbb F}^\omega \times Z \to U is a cocycle.  It turns out that we can always decompose Y in this fashion, because Y is generated by polynomials; furthermore we can make the cocycle \phi a polynomial of bounded degree.

Once one does this, the system Y not only has an action of {\Bbb F}^\omega, but also has an action of the vertical group U, which commutes with the {\Bbb F}^\omega action.  Given any u \in U, we can now define the vertical derivative \Delta_u f of any function f \in L^\infty(Y) by the formula

\Delta_u f(y,v) := f(y,uv) \overline{f(y,v)}.

It turns out that the general theory of cubic measures, as worked out by Host and Kra, allows one to relate vertical derivatives \Delta_u to the parallelogram derivatives d^{[k-1]} (basically, the point is that the group U happens to preserve the cubic measures \mu^{[k-1]} when applied correctly).  Because of this, it is possible to deduce from (5) the “Conze-Lesigne type” equation

\Delta_{u_1} \ldots \Delta_{u_{k-1}} \rho(g,y) = \Delta_g F_{u_1,\ldots,u_{k-1}}(y) (5′)

for all u_1,\ldots,u_{k-1} \in U.  This equation is more tractable than (5) for a number of reasons, one of which being that y now lives in the system Y, rather than being a k-1-dimensional parallelopiped of points in Y.  Our task is now to repeatedly integrate away the vertical derivatives on the left-hand side of (5′) to obtain (2).

This procedure will be done one derivative at a time.  Let us focus on the final step.  For this, we assume that we have already obtained an equation of the form

\Delta_u \rho(g,y) = P_u(g,y) \Delta_g F_u(y) (5”)

for all u \in U, g \in {\Bbb F}^\omega, and almost every y \in Y, where P_u(g,\cdot) is a phase polynomial of bounded degree and F_u(y) is a measurable function taking values in S^1; thus every vertical derivative of \rho is cohomologous to a bounded degree phase polynomial.  (A technical but important point: it is possible to select P_u and F_u so that F_u(y) is jointly measurable in both u and y, and similarly for P_u(g,y).  This is ultimately possible because the space of bounded degree phase polynomials turns out to be discrete modulo constants.)  The task is now to integrate (5”) to obtain (2).  Actually, we will establish a weaker form of (2), namely

\rho(g,y) = P(g,y) \rho'(g,z) \Delta_g F(y) (6)

where y = (z,u) and \rho': {\Bbb F}^\omega \times Z \to S^1 is some measurable function.  One can show that if (6) holds, then \rho' obeys similar properties to the cocycle \rho, in particular the finite type condition (5).   (It turns out to not quite be a cocycle, though, but merely a quasi-cocycle: a cocycle modulo phase polynomials.  This is an important technical difficulty, but let us ignore it for this discussion.)  Since Z is a simpler system than Y, it is possible to combine (6) with a suitable inductive argument to recover (2).

To summarise our progress so far, we are now at the point where every vertical derivative of \rho is cohomologous to a polynomial (equation (5”)), and wish to integrate this information to conclude that \rho itself is cohomologous to a polynomial, times a vertically-invariant function.

– Reduction to the finite U case –

We now analyse the equation (5”) further.  We have a cocycle relation

\Delta_{uv} \rho(g,y) = \Delta_u \rho(g,y) \Delta_v \rho(g,V_u y)

where V_u: (z,v) \mapsto (z,uv) denotes the action of vertical rotation by u.  Inserting this relation into our hypothesis (5”), we see that \Delta_g [F_{uv} / ( F_u V_u F_v )] is a phase polynomial of bounded degree, and thus F_{uv} / (F_u V_u F_v) is also a phase polynomial of bounded degree.  In other words, F_u is a quasi-cocycle in u; it obeys the cocycle equation F_{uv} = F_u V_u F_v modulo phase polynomials of bounded degree.

Suppose temporarily that F_u was a genuine cocycle in u.  Then, it is possible (using some Fourier analysis) to conclude that F_u is in fact a coboundary in u, F_u = \Delta_u F; this is basically because the action of U on Y is free and thus has no non-trivial cohomology.  (One can get some idea of this by looking at the case when U and Y are finite.)  We can now rewrite (5”) as

\Delta_u (\rho(g,y)/\Delta_g F(y)) = P_u(g,y).

In particular, P_u must be a cocycle in U, and is thus also a coboundary: P_u = \Delta_u P.  Since the P_u are phase polynomials of bounded degree, and the cocycle \phi underlying the extension Y = Z \times_\phi U is also a phase polynomial of bounded degree, it is possible to ensure that the “antiderivative” P of the P_u of the phase polynomials of bounded degree is also a polynomial of bounded degree.  (Verifying this “integration lemma” requires a certain amount of algebraic computation – analogous to that required to show that the composition of two polynomials is again a polynomial, as was done for instance in this previous post of mine – but we will ignore this issue here.)  We thus see that \rho(g,y) / (P(g,y) \Delta_g F(y)) has vanishing u derivative for every U, and is thus of the form \rho'(g,z) for some \rho', thus yielding (5”) as desired.  Thus we see that we would be done if F was a genuine cocycle in U.

Unfortunately, F is only a quasi-cocycle in U; the cocycle equation only holds modulo phase polynomials.  However, one can show that the space of phase polynomials (after quotienting out by constants) is discrete and thus at most countable.  (This discreteness is closely related to the local testability of polynomials that was mentioned in a previous post.)  Because of this, and the countable pigeonhole principle, we can find a single polynomial P for which the modified cocycle equation F_{uv} = F_u (V_u F_v) P holds (modulo constants) for a set E of (u,v) of positive measure in U \times U.

Now let us recall a basic fact from measure theory: if E is a positive measure subset of a compact abelian group U, then the difference set E-E contains an open neighbourhood of the origin.  (This is basically because sets of positive measure can be approximated by open sets, as per Littlewood’s principle.).  Using facts like this, and manipulating the above modified cocycle equation a few times, one eventually arrives at the conclusion that F is in fact a genuine cocycle on an open neighbourhood of the origin in U.  (Here I am oversimplifying a number of technical details, which can be found in the paper.  I will mention though that it was crucial here that F_u was measurable in u, a fact alluded to earlier.)

Up until now, we have not used at all any properties of the underlying group {\Bbb F}^\omega (other than that it is abelian, discrete, and amenable).  Now, for the first time, we exploit the finite characteristic.  Because of this finite characteristic, all phase polynomials take values in roots of unity (modulo constants); since Y is given by polynomials, it is possible to show that U is then a torsion group (in fact, one can show it is the direct product of at most countably many cyclic groups).  As a consequence of this, every open neighbourhood of the origin in U contains an open subgroup.  Thus, we have managed to show that F_u is a cocycle, not for u \in U, but rather for u \in U' where U’ is an open subgroup of U.

This is close enough to what we originally wanted that we can try repeating the above arguments.  Doing this, we find at the end of the day that we can “quotient out” U’ from the problem and effectively reduce U to the quotient group U/U’.  Since U is compact and U’ is open, U/U’ is finite.  Thus, we have effectively reduced matters to the case in which U is finite.

– The finite U case –

Now let U be finite.  The classification of finite abelian groups tells us that U is the product of cyclic groups.  For simplicity let us suppose that U is a single cyclic group, and specifically the group C_p of p^{th} roots of unity; this is not the most general case, but it illustrates the method (the general case is handled by a more complicated version of the arguments below).

Let e be the generator of U, thus U = \{1,e,\ldots,e^{p-1}\}.  By the previous arguments, we know that F is a quasi-cocycle in U, thus

F_{e^{j+k}} = F_{e^j} V_e^j F_{e^k} \times P_{j,k} (6)

for some phase polynomial P_{j,k} of bounded degree.  We would like to eliminate the polynomials P_{j,k} from this equation to get a genuine cocycle.

We can partially do this by redefining the F_{e^j} for j=2,3,\ldots,p-1 in terms of F_e by the formula

F_{e^j} := \prod_{i=0}^{j-1} V_e^i F_e.  (7)

One can show (using (6)) that this redefinition does not significantly affect (5”), and now we have the exact cocycle condition

F_{e^{j+k}} = F_{e^j} V_e^j F_{e^k} (8)

whenever 0 \leq j,k and j+k < p.  However, (8) need not hold for all j, k.  In order for this to be true, one must obey the line cocycle condition

\prod_{i=0}^{p-1} V_e^i F_e = 1 (9)

(which would make the definition in (7) periodic in j).  Conversely, if (9) holds then the cocycle given by (7) is a true cocycle in U, thus this condition completely describes the “cohomology” of U-cocycles here.

Now, in general, the F_e that we initially start with need not satisfy (9).  However, by using (6), one can show that the left-hand side of (9), while not identically 1, is at least a phase polynomial of bounded degree.  At this point we use a key algebraic lemma (which I hope to comment more on in a future post): every phase polynomial of bounded degree has a p^{th} root which is also a phase polynomial of bounded (but slightly higher) degree.  Thus we have

\prod_{i=0}^{p-1} V_e^i F_e = Q^p

for some polynomial Q of bounded degree.  But then what we can do is divide each F_e by Q; this does not significantly affect (5”), but now recovers the line cocycle condition (9), and allows us to make F_u a cocycle on U, at which point one can argue as before.

The multidimensional case, when U is a product of cyclic groups, is a little more sophisticated than this; in addition to the line cocycle condition (9), there is an additional “zero curvature” condition \Delta_{e_j} F_{e_i} = \Delta_{e_i} F_{e_j} that has to be obtained before one can build a cocycle in U, but it turns out that a suitably multidimensional generalisation of the formula (7) can ensure this.