What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

# An inverse theorem for the uniformity seminorms associated with the action of F^infty_p

19 January, 2009 in math.DS, paper | Tags: characteristic factor, cocycles, finite fields, Gowers uniformity norm, polynomials, Tamar Ziegler, Vitaly Bergelson

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.

### Recent Comments

Sandeep Murthy on An elementary non-commutative…
Luqing Ye on 245A, Notes 2: The Lebesgue…
Frank on Soft analysis, hard analysis,…
andrescaicedo on Soft analysis, hard analysis,…
Richard Palais on Pythagoras’ theorem
The Coffee Stains in… on Does one have to be a genius t…
Benoît Régent-Kloeck… on (Ingrid Daubechies) Planning f…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
%anchor_text% on Books
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245A, Notes 2: The Lebesgue…

## 6 comments

20 January, 2009 at 1:18 am

bengreen

A tour de force which I shall enjoy reading on a forthcoming train journey. But please, please can you think of an alternative to the triangle-with-a-dot notation for multiplicative derivative?

Dear Terry, the paper is extremely well written and indeed a joy to read (even to an outsider like me). One typo: on page 8 (eq 1.2) there’s an extra 0 in the matrix.

Do you expect the sharpest constant $c=c(p,k,\delta)$ in theorem 1.27 to have a nice explicit form (at least for k=1 or k=p)?

Finally I’d humbly concur that the current notation for the multiplicative derivative is a bit heavy to the eye, a trick to make the black dot a little smaller would to use the \scriptscriptsize command, here’s a wordpress try without preview: either this $\Delta\!\!\!\!{\scriptscriptstyle \bullet}$ or that $\Delta\!\!\!\!\!{\scriptscriptstyle \bullet}$.

Thanks for the correction! We actually had a lot of trouble deciding on the notation for the multiplicative derivative; we had considered $\dot \Delta_h$ or $\Delta^\times_h$ or ${\Delta\!\!\!\cdot\ \ \!\!}_h$ but felt that the dots were too inconspicuous. I guess we erred in the other direction instead. I like the scriptsize idea (though my version of LaTeX is so far refusing to acknowledge \scriptscriptsize), I’ll try to see if I can centre the dot in the middle of the triangle. [update: OK, I managed to jerry rig this: ${\Delta\!\!\!\!\!\!\hbox{\raisebox{0.4ex}{\tiny\ \ \textbullet}}\ \ \!\!}_h$.]

(Alternatively, since we use multiplicative differentiation far more often than additive differentiation, another option is to make $\Delta_h$ default to multiplicative and use some other notation for additive. But we felt that this might be confusing since $\Delta_h$ denotes additive differentiation in many other places in the literature. Anyway, I welcome further suggestions.)

[...] with respect to the shift . (This need to consider families is an issue that also comes up in the finite field ergodic theory analogue of the inverse conjectures, due to the unbounded number of generators in that case, but [...]

[...] handle the general case, which was worked out in two papers, one by myself and Ziegler, and one by Bergelson, Ziegler, and myself. It turns out that it is convenient to phrase these arguments in the language of ergodic theory. [...]

[...] for the Gowers norm, this time for vector spaces over a fixed finite field of prime order; with Vitaly Bergelson, we had previously established this claim when the characteristic of the field was large, so the [...]

Cancel
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 148, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9227424263954163, "perplexity_flag": "head"}