Asgar Jamneshan, Or Shalom, and myself have just uploaded to the arXiv our preprints “A Host–Kra {{\bf F}^\omega_2}-system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the {U^6({\bf F}^n_2)} norm” and “The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the {U^k} Gowers uniformity norms on finite abelian groups of bounded torsion“. These two papers are both concerned with advancing the inverse theory for the Gowers norms and Gowers-Host-Kra seminorms; the first paper provides a counterexample in this theory (in particular disproving a conjecture of Bergelson, Ziegler and myself), and the second paper gives new positive results in the case when the underlying group is bounded torsion, or the ergodic system is totally disconnected. I discuss the two papers more below the fold.

— 1. System of order {5} which is not Abramov of order {5} —

I gave a talk on this paper recently at the IAS; the slides for that talk are available here.

This project can be motivated by the inverse conjecture for the Gowers norm in finite fields, which is now a theorem:

Theorem 1 (Inverse conjecture for the Gowers norm in finite fields) Let {p} be a prime and {k \geq 1}. Suppose that {f: {\bf F}_p^n \rightarrow {\bf C}} is a one-bounded function with a lower bound {\|f\|_{U^{k+1}({\bf F}_p^n)} \geq \delta > 0} on the Gowers uniformity norm. Then there exists a (non-classical) polynomial {P: {\bf F}_p^n \rightarrow {\bf T}} of degree at most {k} such that {|{\bf E}_{x \in {\bf F}_p^n} f(x) e(-P(x))| \gg_{p,k,\delta} 1}.

This is now known for all {p,k} (see this paper of Ziegler and myself for the first proof of the general case, and this paper of Milicevic for the most recent developments concerning quantitative bounds), although initial results focused on either small values of {k}, or the “high characteristic” case when {p} is large compared to {k}. One approach to this theorem proceeds via ergodic theory. Indeed it was observed in this previous paper of Ziegler and myself that for a given choice of {p} and {k}, the above theorem follows from the following ergodic analogue:

Conjecture 2 (Inverse conjecture for the Gowers-Host-Kra semi-norm in finite fields) Let {p} be a prime and {k \geq 1}. Suppose that {f \in L^\infty(X)} with {X} an ergodic {{\bf F}_p^\omega}-system with positive Gowers-Host-Kra seminorm {\|f\|_{U^{k+1}(X)}} (see for instance this previous post for a definition). Then there exists a measurable polynomial {P: X \rightarrow {\bf T}} of degree at most {k} such that {f} has a non-zero inner product with {e(P)}. (In the language of ergodic theory: every {{\bf F}_p^\omega}-system of order {k} is an Abramov system of order {k}.)

The implication proceeds by a correspondence principle analogous to the Furstenberg correspondence principle developed in that paper (see also this paper of Towsner for a closely related principle, and this paper of Jamneshan and I for a refinement). In a paper with Bergelson and Ziegler, we were able to establish Conjecture 2 in the “high characteristic” case {p \geq k+1}, thus also proving Theorem 1 in this regime, and conjectured that Conjecture 2 was in fact true for all {p,k}. This was recently verified in the slightly larger range {p \geq k-1} by Candela, Gonzalez-Sanchez, and Szegedy.

Even though Theorem 1 is now known in full generality by other methods, there are still combinatorial reasons for investigating Conjecture 2. One of these is that the implication of Theorem 1 from Corollary 2 in fact gives additional control on the polynomial {P} produced by Theorem 1, namely that it is some sense “measurable in the sigma-algebra generated by {f}” (basically because the ergodic theory polynomial {P} produced by Conjecture 2 is also measurable in {X}, as opposed to merely being measurable in an extension of {X}). What this means in the finitary setting of {{\bf F}_p^n} is a bit tricky to write down precisely (since the naive sigma-algebra generated by the translates of {f} will mostly likely be the discrete sigma-algebra), but roughly speaking it means that {P} can be approximated to arbitrary accuracy by functions of boundedly many (random) translates of {f}. This can be interpreted in a complexity theory sense by stating that Theorem 1 can be made “algorithmic” in a “probabilistic bounded time oracle” or “local list decoding” sense which we will not make precise here.

The main result of this paper is

Theorem 3 Conjecture 2 fails for {p=2, k=5}. In fact the “measurable inverse theorem” alluded to above also fails in this case.

Informally, this means that for large {n}, we can find {1}-bounded “pseudo-quintic” functions {f: {\bf F}_2^n \rightarrow {\bf C}} with large {U^6({\bf F}^2_n)} norm, which then must necessarily correlate with at least one quintic {e(P)} by Theorem 1, but such that none of these quintics {e(P)} can be approximated to high accuracy by functions of (random) shifts of {f}. Roughly speaking, this means that the inverse {U^6({\bf F}_2^n)} theorem cannot be made locally algorithmic (though it is still possible that a Goldreich-Levin type result of polynomial time algorithmic inverse theory is still possible, as is already known for {U^k({\bf F}^n)} for {k=2,3,4}; see this recent paper of Kim, Li and Tidor for further discussion).

The way we arrived at this theorem was by (morally) reducing matters to understanding a certain “finite nilspace cohomology problem”. In the end it boiled down to locating a certain function {\rho: C^6( {\mathcal D}^2({\bf F}_2^2)) \rightarrow \frac{1}{2}{\bf Z}/{\bf Z}} from a {2^{2(1+6+\binom{6}{2})}}-element set {C^6( {\mathcal D}^2({\bf F}_2^2))} to a two-element set which was a “strongly {2}-homogeneous cocycle” but not a “coboundary” (these terms are defined precisely in the paper). This strongly {2}-homogeneous cocycle {\rho} can be expressed in terms of a simpler function {\psi: C^1( {\mathcal D}^2({\bf F}_2^2)) \rightarrow {\bf T}} that takes values on a {2^4}-element space {C^1( {\mathcal D}^2({\bf F}_2^2))}. The task of locating {\psi} turned out to be one that was within the range of our (somewhat rudimentary) SAGE computation abilities (mostly involving computing the Smith normal form of some reasonably large integer matrices), but the counterexample functions {\psi, \rho} this produced were initially somewhat opaque to us. After cleaning up these functions by hand (by subtracting off various “coboundaries”), we eventually found versions of these functions which were nice enough that we could verify all the claims needed in a purely human-readable fashion, without any further computer assistance. As a consequence, we can now describe the pseudo-quintic {f: {\bf F}_2^n \rightarrow {\bf C}} explicitly, though it is safe to say we would not have been able to come up with this example without the initial computer search, and we don’t currently have a broader conceptual understanding of which {p,k} could potentially generate such counterexamples. The function {f} takes the form

\displaystyle f = e( \frac{\binom{R}{2} Q}{2} + P )

where {Q: {\bf F}_2^n \rightarrow {\bf F}_2} is a randomly chosen (classical) quadratic polynomial, {R: {\bf F}_2^n \rightarrow {\bf Z}/4{\bf Z}} is a randomly chosen (non-classical) cubic polynomial, and {P: {\bf F}_2^n \rightarrow \frac{1}{2^5} {\bf Z}/{\bf Z}} is a randomly chosen (non-classical) quintic polynomial. This function correlates with {e(P)} and has a large {U^6({\bf F}_2^n)} norm, but this quintic {e(P)} is “non-measurable” in the sense that it cannot be recovered from {f} and its shifts. The quadratic polynomial {Q} turns out to be measurable, as is the double {2R} of the cubic {R}, but in order to recover {P} one needs to apply a “square root” to the quadratic {2R} to recover a candidate for the cubic {R} which can then be used to reconstruct {P}.

— 2. Structure of totally disconnected systems —

Despite the above negative result, in our other paper we are able to get a weak version of Conjecture 2, that also extends to actions of bounded-torsion abelian groups:

Theorem 4 (Weak inverse conjecture for the Gowers-Host-Kra semi-norm in bounded torsion groups) Let {\Gamma} be a bounded-torsion abelian group and {k \geq 1}. Suppose that {f \in L^\infty(X)} with {X} an ergodic {{\bf F}_p^\omega}-system with positive Gowers-Host-Kra seminorm {\|f\|_{U^{k+1}(X)}}. Then, after lifting {\Gamma} to a torsion-free group {\tilde \Gamma}, there exists a measurable polynomial {P: Y \rightarrow {\bf T}} of degree at most {k} defined on an extension {Y} of {X} which has a non-zero inner product with {e(P)}.

Combining this with the correspondence principle and some additional tools, we obtain a weak version of Theorem 1 that also extends to bounded-torsion groups:

Theorem 5 (Inverse conjecture for the Gowers norm in bounded torsion groups) Let {G} be a finite abelian {m}-torsion group for some {m \geq 1} and {k \geq 1}. Suppose that {f: G \rightarrow {\bf C}} is a one-bounded function with {\|f\|_{U^{k+1}(G} \geq \delta > 0}. Then there exists a (non-classical) polynomial {P: G \rightarrow {\bf T}} of degree at most {O_{k,m}(1)} such that {|{\bf E}_{x \in G} f(x) e(-P(x))| \gg_{m,k,\delta} 1}.

The degree {O_{k,m}(1)} produced by our arguments is polynomial in {k,m}, but we conjecture that it should just be {k}.

The way Theorem 4 (and hence Theorem 5) is proven is as follows. The now-standard machinery of Host and Kra (as discussed for instance in their book) allows us to reduce {X} to a system of order {k}, which is a certain tower of extensions of compact abelian structure groups {U_1,\dots,U_k} by various cocycles {\rho_1,\dots,\rho_{k-1}}. In the {m}-torsion case, standard theory allows us to show that these structure groups {U_i} are also {m}-torsion, hence totally disconnected. So it would now suffice to understand the action of torsion-free groups on totally disconnected systems {X}. For the purposes of proving Theorem 4 we have the freedom to extend {X} as we please, and we take advantage of this freedom by “extending by radicals”, in the sense that whenever we locate a polynomial {P: X \rightarrow {\bf T}} in the system, we adjoin to it {d^{th}} roots {Q: X \rightarrow {\bf T}} of that polynomial (i.e., solutions to {dQ=P}) that are polynomials of the same degree as {P}; this is usually not possible to do in the original system {X}, but can always be done in a suitable extension, analogously to how {d^{th}} roots do not always exist in a given field, but can always be located in some extension of that field. After applying this process countably many times it turns out that we can arrive at a system which is {\infty}-divisible in the sense that polynomials of any degree have roots of any order that are of the same degree. In other words, the group of polynomials of any fixed degree is a divisible abelian group, and thus injective in the category of such groups. This makes a lot of short exact sequences that show up in the theory split automatically, and greatly simplifies the cohomological issues one encounters in the theory, to the point where all the cocycles {\rho_1,\dots,\rho_{k-1}} mentioned previously can now be “straightened” into polynomials of the expected degree (or, in the language of ergodic theory, this extension is a Weyl system of order {k}, and hence also Abramov of order {k}). This is sufficient to establish Theorem 4. To get Theorem 5, we ran into a technical obstacle arising from the fact that the remainder map {x \mapsto x \% m = m \{ \frac{x}{m} \}} is not a polynomial mod {m^r} if {m} is not itself a prime power. To resolve this, we established ergodic theory analogues of the Sylow decomposition {\Gamma = \bigoplus_{p|m} \Gamma_p} of abelian {m}-torsion groups into {p}-groups {\Gamma_p}, as well as the Schur-Zassenhaus theorem. Roughly speaking, the upshot of these theorems is that any ergodic {\Gamma}-system {X}, with {\Gamma} {m}-torsion, can be split as the “direct sum” of ergodic {\Gamma_p}-systems {X_p} for primes {p} dividing {m}, where {\Gamma_p} is the subgroup of {\Gamma} consisting of those elements whose order is a power of {p}. This allows us to reduce to the case when {m} is a prime power without too much difficulty.

In fact, the above analysis gives stronger structural classifications of totally disconnected systems (in which the acting group is torsion-free). Weyl systems can also be interpreted as translational systems {G/\Lambda}, where {G} is a nilpotent Polish group and {\Lambda} is a closed cocompact subgroup, with the action being given by left-translation by various elements of {G}. Perhaps the most famous examples of such translational systems are nilmanifolds, but in this setting where the acting group {\Gamma} is not finitely generated, it turns out to be necessary to consider more general translational systems, in which {G} need not be a Lie group (or even locally compact), and {\Lambda} not discrete. Our previous results then describe totally disconnected systems as factors of such translational systems. One natural candidate for such factors are the double coset systems {K \backslash G / \Lambda} formed by quotienting out {G/\Lambda} by the action of another closed group {K} that is normalized by the action of {\Gamma}. We were able to show that all totally disconnected systems with torsion-free acting group had this double coset structure. This turned out to be surprisingly subtle at a technical level, for at least two reasons. Firstly, after locating the closed group {K} (which in general is Polish, but not compact or even locally compact), it was not immediately obvious that {K \backslash G / \Lambda} was itself a Polish space (this amounts to the orbits {KA} of a closed set {A} still being closed), and also not obvious that this double coset space had a good nilspace structure (in particular that the factor map from {G/\Lambda} to {K \backslash G/\Lambda} is a nilspace fibration). This latter issue we were able to resolve with a tool kindly shared to us in a forthcoming work by Candela, Gonzales-Sanchez, and Szegedy, who observed that the nilspace fibration property was available if the quotient groups {K, \Lambda} obeyed an algebraic “groupable” axiom which we were able to verify in this case (they also have counterexamples showing that the nilspace structure can break down without this axiom). There was however one further rather annoying complication. In order to fully obtain the identification of our system with a double coset system, we needed the equivalence

\displaystyle L^\infty(G/\Lambda)^K \equiv L^\infty(K \backslash G / \Lambda)

between bounded measurable functions on {G/\Lambda} which were {K}-invariant up to null sets on one hand, and bounded measurable functions on {K \backslash G/\Lambda} on the other. It is quite easy to embed the latter space isometrically into the former space, and we thought for a while that the opposite inclusion was trivial, but much to our surprise and frustration we were not able to achieve this identification by “soft” methods. One certainly has the topological analogue

\displaystyle C(G/\Lambda)^K \equiv C(K \backslash G / \Lambda)

of this identification, and {L^\infty(K \backslash G / \Lambda)} is the weak closure of {C(K \backslash G / \Lambda)} and {L^\infty(G/\Lambda)} the weak closure of {C(G/\Lambda)}, but this is not quite enough to close the argument; we also need to have a (weakly) continuous projection operator from {C(G/\Lambda)} to {C(G/\Lambda)^K} to make everything work. When {K} is compact (or more generally, locally compact amenable) one could try to do this by averaging over the Haar measure of {K}, or (possibly) by some averages on Folner sets. In our setting, we know that {K} can fail to be locally compact (it can contain groups like {{\bf Z}^{\bf N}}), but we were able to locate a “poor man’s Haar measure” {\mu} on this non-locally compact group {K} that was a compactly supported Radon probability measure acted like a Haar measure when pushed forward to individual orbits {Kx} of {K} on {G/\Lambda}, which turned out to be sufficient to get the averaging we needed (and also to establish the Polish nature of {K \backslash G / \Lambda}).