Ben Green, Tamar Ziegler and I have just uploaded to the arXiv our paper “An inverse theorem for the Gowers norm“. This paper establishes the next case of the inverse conjecture for the Gowers norm for the integers (after the case, which was done by Ben and myself a few years ago). This conjecture has a number of combinatorial and number-theoretic consequences, for instance by combining this new inverse theorem with previous results, one can now get the correct asymptotic for the number of arithmetic progressions of primes of length five in any large interval .
To state the inverse conjecture properly requires a certain amount of notation. Given a function and a shift , define the multiplicative derivative
and then define the Gowers norm of a function to (essentially) be the quantity
where we extend f by zero outside of . (Actually, we use a slightly different normalisation to ensure that the function 1 has a norm of 1, but never mind this for now.)
Informally, the Gowers norm measures the amount of bias present in the multiplicative derivatives of . In particular, if for some polynomial , then the derivative of is identically 1, and so is the Gowers norm.
However, polynomial phases are not the only functions with large Gowers norm. For instance, consider the function , which is what we call a quadratic bracket polynomial phase. This function isn’t quite quadratic, but it is close enough to being quadratic (because one has the approximate linearity relationship holding a good fraction of the time) that it turns out that third derivative is trivial fairly often, and the Gowers norm is comparable to 1. This bracket polynomial phase can be modeled as a nilsequence , where is a polynomial orbit on a nilmanifold , which in this case has step 2. (The function F is only piecewise smooth, due to the discontinuity in the floor function , so strictly speaking we would classify this as an almost nilsequence rather than a nilsequence, but let us ignore this technical issue here.) In fact, there is a very close relationship between nilsequences and bracket polynomial phases, but I will detail this in a later post.
The inverse conjecture for the Gowers norm, GI(s), asserts that such nilsequences are the only obstruction to the Gowers norm being small. Roughly speaking, it goes like this:
Inverse conjecture, GI(s). (Informal statement) Suppose that is bounded but has large norm. Then there is an s-step nilsequence of “bounded complexity” that correlates with f.
This conjecture is trivial for s=0, is a short consequence of Fourier analysis when s=1, and was proven for s=2 by Ben and myself. In this paper we establish the s=3 case. An equivalent formulation in this case is that any bounded function of large norm must correlate with a “bracket cubic phase”, which is the product of a bounded number of phases from the following list
(*)
for various real numbers .
It appears that our methods also work in higher step, though for technical reasons it is convenient to make a number of adjustments to our arguments to do so, most notably a switch from standard analysis to non-standard analysis, about which I hope to say more later. But there are a number of simplifications available on the s=3 case which make the argument significantly shorter, and so we will be writing the higher s argument in a separate paper.
The arguments largely follow those for the s=2 case (which in turn are based on this paper of Gowers). Two major new ingredients are a deployment of a normal form and equidistribution theory for bracket quadratic phases, and a combinatorial decomposition of frequency space which we call the sunflower decomposition. I will sketch these ideas below the fold.
— Sketch of proof —
We will use an inductive argument, relying on the known inverse theory for the norm to establish the result.
Let f be a function with large norm. The goal is to show that f correlates with some cubic object, such as something generated from the list (*). By definition of the norm, we already know that the derivatives have large norm for many h. Applying the inverse theorem at the level, we conclude that for many such , correlates with a bracket quadratic phase , which one can write as a bounded product of phases of the form
for various frequencies depending on . To simplify the discussion let us ignore the pure quadratics as lower order terms, and suppose that only a single bracket quadratic is present. We thus have
where we will be vague about exactly what the symbol means here.
A key observation of Gowers is that the cocycle nature of induces some non-trivial relationships between the frequencies . For instance, if f had magnitude 1 throughout, then we would have the identity
which suggests (discarding lower order terms) that one has the relation
(**)
for many h, k. (In practice, one actually obtains a slightly more complicated relationship, in which the additive triple is replaced by an additive quadruple with , but never mind this technicality.)
The relation (**) suggests that one has an identity of the form
modulo lower order terms (and also modulo 1). How can such an identity occur? There are two obvious ways this can happen:
- The are independent of h, and varies linearly in h.
- The are independent of h, and varies linearly in h. (The error caused by the failure of to be exactly linear turns out to be lower order and will be absorbed into the vaguely defined symbol.)
It turns out that one can generalise these scenarios a little bit. Firstly, since we are only seeking structure for many h,k rather than for all h,k, one can replace “linearly in h” in the above scenarios by “bracket-linearly in h”, e.g. could be given by for some real numbers , as this would still be sufficiently close to linear to generate a relation such as (**). Secondly, one could modify the by integers (or more generally, by rational numbers with bounded denominator) without significantly affecting (**) due to the periodicity of the function e() modulo 1. Finally, there are some identities of bracket calculus that show some non-trivial relations between various quadratic expressions , such as
for any non-zero rational q with bounded numerator and denominator, and also the antisymmetry property
(the point being that can be considered a lower order term, as can xy, and vanishes modulo 1).
It turns out though that the above maneuvres basically exhaust all the possible ways in which a relation of the form (**) can occur. There are two main reasons for this:
- One can show that if any two of the three pairs are in “general position”, then no identity of the form (**) can occur.
- If there is a frequency shared in common among all three frequency sets, e.g. if is independent of h, then the other frequency must essentially depend linearly (or bracket-linearly) in h.
The reason for claim 1 ultimately reduces to the following simple algebraic lemma (which we call the “Furstenberg-Weiss trick“, though it has appeared in some other contexts also, for instance in this paper of Hrushovski):
Lemma 1. Let H be a subgroup of a product of three groups. If the projection of H to is surjective, and the projection of H to is surjective, then H contains the subgroup .
Proof. Let be two elements of . By the first surjectivity property, H contains an element of the form where * denotes an unspecified coefficient, and by the second property, H also contains . Taking commutators yields , and the claim follows.
Roughly speaking, the reason why this Lemma implies Claim 1 is because the joint orbit of , , can be controlled, using Ratner’ s theorem (or more precisely, a quantitative version of this theorem that Ben and I worked out a few years ago) by a certain subgroup H of the product of three Heisenberg groups (times an abelian group to take care of lower order errors, but let’s ignore this). The general position hypotheses give us the hypotheses of the lemma, and the conclusion basically tells us that the phase of (say) can be varied independently of the other two phases, which prevents any relation of the form (**) occurring. A related argument also gives Claim 2.
Once one has Claim 1 and Claim 2, a combinatorial argument (which we call the sunflower decomposition) that separates the frequencies into “core” frequencies (shared by many h) and “petal” frequencies (which vary with h, so that the petals for h and petals for k are in general position for most h,k), and then using standard tools from additive combinatorics (notably the Balog-Szemeredi-Gowers lemma and Freiman’s theorem), one eventually concludes (possibly after reshuffling the bracket polynomials a bit, to take care of the ambiguities mentioned earlier) that of the two frequencies that appear, one is independent of h and the other varies bracket linearly in h. Thus we see now that resembles an expression which is the product of a bounded number of terms such as
and permutations. We write this as
for some “trilinear” form T in three variables.
If T was symmetric in all three variables, then would resemble the derivative of (modulo lower order terms), which turns out to imply (after invoking the induction hypothesis GI(2) again) that correlates with (times lower order terms). But by construction, is a bracket cubic, and this would give the claim GI(3).
So one seeks to impose a “symmetry” property on T. The reason for this symmetry ultimately stems from the identity
which suggests that
which, when expanded, gives something reasonably close to the required symmetry property. One can make this argument precise using a carefully chosen sequence of applications of the Cauchy-Schwarz inequality. One initial obstacle is that the desired symmetry only holds for many pairs (h,k), rather than for all pairs (h,k), but it turns out that one can step over this obstacle by using a theorem of Sarkozy, which asserts that if H is a dense subset of [N], then a suitable sumset of bounded length will contain a long arithmetic progression (of size comparable to N). Combining this theorem with the trilinearity properties of T lets one pass from “many” to “all” (or more precisely, “all in a long arithmetic progression”, which is good enough for our purposes).
12 comments
Comments feed for this article
2 December, 2009 at 5:01 pm
Akhil Mathew
I think one of your formulas does not parse (formula (**)). [Corrected, thanks – T.]
2 December, 2009 at 7:33 pm
Anonymous
I use Firefox version 3.5.5 and formula (**) still does not parse. [Strange. I ended up splitting the LaTeX in two, which seems to resolve the glitch.]
2 December, 2009 at 11:25 pm
Américo Tavares
Formula (**) still does not parse. Is it
?
[Grr, I have no idea why the LaTeX keeps reverting to (and why the particular form of the LaTeX is causing errors). Hopefully now it’s fixed for good… -T.]
3 December, 2009 at 2:17 pm
Américo Tavares
Info: I’m currently using IE8 and this formula is OK.
3 December, 2009 at 5:01 am
Emmanuel Kowalski
Lemma 1 (and its proof) is very close to a lemma used by Ribet in “On ell-adic representations associated to modular forms”, Invent. math. 28, 1975 (Lemma 3.3, p. 252 there; Ribet attributes the nice tricky proof to Serre…)
3 December, 2009 at 7:31 am
Thomas Sauvaget
That paper is freely accessible on the Göttinger Digitalisierungszentrum website here.
Back to the U^4 paper: it seems that you reserve the word ‘almost’ (as in ‘almost polynomial nilsequence’) to objects which are close to some exact ones in a measure theoretic sense, while the word ‘approximate’ (as in ‘approximate homomorphism’) is used for algebraic structures, or is there something else implied?
3 December, 2009 at 12:16 pm
Harald
Terry – do you want that power of 2^{s+1} in the second displayed formula?
[Um, no I don’t. Thanks for pointing it out. -T.]
14 December, 2009 at 3:37 pm
Approximate bases, sunflowers, and nonstandard analysis « What’s new
[…] I will also discuss a two variants of both Theorem 1 and Theorem 2 which have actually shown up in my research. The first is that of the regularity lemma for polynomials over finite fields, which came up when studying the equidistribution of such polynomials (in this paper with Ben Green). The second comes up when is dealing not with a single finite collection of vectors, but rather with a family of such vectors, where ranges over a large set; this gives rise to what we call the sunflower lemma, and came up in this recent paper of myself, Ben Green, and Tamar Ziegler. […]
12 February, 2010 at 10:46 pm
An arithmetic regularity lemma, an associated counting lemma, and applications « What’s new
[…] Ziegler have recently established (paper to be forthcoming shortly; the case of our argument is discussed here). The counting lemma is established through the quantitative equidistribution theory of […]
17 May, 2010 at 8:13 am
Anonymous
Hello, May I ask what is the status of your paper with Green and Ziegler proving of the Gowers norm inverse conjecture for all d? I’ve noticed that this is listed as “submitted” in your papers for the Szemeredi birthday conference, however it hasn’t been made publicly available yet.
17 May, 2010 at 8:56 am
Terence Tao
This paper is in the process of being rewritten and should be available within a few weeks.
We already have two more-or-less complete versions of the paper written up already, but we were not happy with the level of exposition with them; they required quite a huge amount of technical machinery and setup, and so we have been working to simplify the argument. (Page counts are only a very crude gauge of complexity, but our first version was 112 pages long; the second version was 86. The third version is likely to be a little longer, but much less dense.)
29 May, 2010 at 2:16 pm
254B, Notes 6: The inverse conjecture for the Gowers norm II. The integer case « What’s new
[…] soon after that. For a discussion of the history of the conjecture, including the cases , see our previous paper. Exercise 21 ( inverse […]