Asgar Jamneshan, Or Shalom, and myself have just uploaded to the arXiv our preprints “A Host–Kra -system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the norm” and “The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the 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 which is not Abramov of order —
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 be a prime and . Suppose that is a one-bounded function with a lower bound on the Gowers uniformity norm. Then there exists a (non-classical) polynomial of degree at most such that .
This is now known for all (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 , or the “high characteristic” case when is large compared to . 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 and , the above theorem follows from the following ergodic analogue:
Conjecture 2 (Inverse conjecture for the Gowers-Host-Kra semi-norm in finite fields) Let be a prime and . Suppose that with an ergodic -system with positive Gowers-Host-Kra seminorm (see for instance this previous post for a definition). Then there exists a measurable polynomial of degree at most such that has a non-zero inner product with . (In the language of ergodic theory: every -system of order is an Abramov system of order .)
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 , thus also proving Theorem 1 in this regime, and conjectured that Conjecture 2 was in fact true for all . This was recently verified in the slightly larger range 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 produced by Theorem 1, namely that it is some sense “measurable in the sigma-algebra generated by ” (basically because the ergodic theory polynomial produced by Conjecture 2 is also measurable in , as opposed to merely being measurable in an extension of ). What this means in the finitary setting of is a bit tricky to write down precisely (since the naive sigma-algebra generated by the translates of will mostly likely be the discrete sigma-algebra), but roughly speaking it means that can be approximated to arbitrary accuracy by functions of boundedly many (random) translates of . 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 . In fact the “measurable inverse theorem” alluded to above also fails in this case.
Informally, this means that for large , we can find -bounded “pseudo-quintic” functions with large norm, which then must necessarily correlate with at least one quintic by Theorem 1, but such that none of these quintics can be approximated to high accuracy by functions of (random) shifts of . Roughly speaking, this means that the inverse 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 for ; 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 from a -element set to a two-element set which was a “strongly -homogeneous cocycle” but not a “coboundary” (these terms are defined precisely in the paper). This strongly -homogeneous cocycle can be expressed in terms of a simpler function that takes values on a -element space . The task of locating 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 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 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 could potentially generate such counterexamples. The function takes the form
where is a randomly chosen (classical) quadratic polynomial, is a randomly chosen (non-classical) cubic polynomial, and is a randomly chosen (non-classical) quintic polynomial. This function correlates with and has a large norm, but this quintic is “non-measurable” in the sense that it cannot be recovered from and its shifts. The quadratic polynomial turns out to be measurable, as is the double of the cubic , but in order to recover one needs to apply a “square root” to the quadratic to recover a candidate for the cubic which can then be used to reconstruct .
— 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 be a bounded-torsion abelian group and . Suppose that with an ergodic -system with positive Gowers-Host-Kra seminorm . Then, after lifting to a torsion-free group , there exists a measurable polynomial of degree at most defined on an extension of which has a non-zero inner product with .
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 be a finite abelian -torsion group for some and . Suppose that is a one-bounded function with . Then there exists a (non-classical) polynomial of degree at most such that .
The degree produced by our arguments is polynomial in , but we conjecture that it should just be .
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 to a system of order , which is a certain tower of extensions of compact abelian structure groups by various cocycles . In the -torsion case, standard theory allows us to show that these structure groups are also -torsion, hence totally disconnected. So it would now suffice to understand the action of torsion-free groups on totally disconnected systems . For the purposes of proving Theorem 4 we have the freedom to extend as we please, and we take advantage of this freedom by “extending by radicals”, in the sense that whenever we locate a polynomial in the system, we adjoin to it roots of that polynomial (i.e., solutions to ) that are polynomials of the same degree as ; this is usually not possible to do in the original system , but can always be done in a suitable extension, analogously to how 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 -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 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 , and hence also Abramov of order ). 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 is not a polynomial mod if is not itself a prime power. To resolve this, we established ergodic theory analogues of the Sylow decomposition of abelian -torsion groups into -groups , as well as the Schur-Zassenhaus theorem. Roughly speaking, the upshot of these theorems is that any ergodic -system , with -torsion, can be split as the “direct sum” of ergodic -systems for primes dividing , where is the subgroup of consisting of those elements whose order is a power of . This allows us to reduce to the case when 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 , where is a nilpotent Polish group and is a closed cocompact subgroup, with the action being given by left-translation by various elements of . Perhaps the most famous examples of such translational systems are nilmanifolds, but in this setting where the acting group is not finitely generated, it turns out to be necessary to consider more general translational systems, in which need not be a Lie group (or even locally compact), and 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 formed by quotienting out by the action of another closed group that is normalized by the action of . 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 (which in general is Polish, but not compact or even locally compact), it was not immediately obvious that was itself a Polish space (this amounts to the orbits of a closed set still being closed), and also not obvious that this double coset space had a good nilspace structure (in particular that the factor map from to 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 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
between bounded measurable functions on which were -invariant up to null sets on one hand, and bounded measurable functions on 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 of this identification, and is the weak closure of and the weak closure of , but this is not quite enough to close the argument; we also need to have a (weakly) continuous projection operator from to to make everything work. When is compact (or more generally, locally compact amenable) one could try to do this by averaging over the Haar measure of , or (possibly) by some averages on Folner sets. In our setting, we know that can fail to be locally compact (it can contain groups like ), but we were able to locate a “poor man’s Haar measure” on this non-locally compact group that was a compactly supported Radon probability measure acted like a Haar measure when pushed forward to individual orbits of on , which turned out to be sufficient to get the averaging we needed (and also to establish the Polish nature of ).
3 comments
Comments feed for this article
10 March, 2023 at 8:49 am
Anonymous
The title seems to have some Latex issuses.
[Title simplified to make it more human readable – T.]
12 March, 2023 at 10:50 am
Chasing integers
Structurally is there a difference between Group algebra and non-classical polynomials when the range is a group? Are there other objects besides groups which serve the purpose?
29 March, 2023 at 10:20 am
Anonymous
Dear, Professor Tao
I have been following you since you were a kid participating in IMO. And in the early days of the old years, I don’t know why I’m always impressed by that child prodigy, ” I thought to myself and strongly believed that this boy would grow up to be one of the greatest mathematicians in the world, he would win Field medal and had many awards in the world “.That’s right, when I heard that you won the Field medal in 2006, I burst into tears because I was so emotional. Back to the problem, I am very impressed with your nearly 200 page paper, I would love to see your 700-800 page paper today. You are very smart, you must know what I mean. I have a strongly faith in you like the heat of the sun.
Time flies so fast, I don’t know what to say more than when you were a cute boy and now you are almost 50 years old. 0ne day, one minute is very precious, Professor Tao ! I hope after you read my words, you think deeply and delete my sentences immediately.
Bye,