In the modern theory of higher order Fourier analysis, a key role are played by the Gowers uniformity norms for . For finitely supported functions , one can define the (non-normalised) Gowers norm by the formula

where denotes complex conjugation, and then on any discrete interval and any function we can then define the (normalised) Gowers norm where is the extension of by zero to all of . Thus for instance (which technically makes a seminorm rather than a norm), and one can calculate where , and we use the averaging notation .The significance of the Gowers norms is that they control other multilinear forms that show up in additive combinatorics. Given any polynomials and functions , we define the multilinear form

(assuming that the denominator is finite and non-zero). Thus for instance where we view as formal (indeterminate) variables, and are understood to be extended by zero to all of . These forms are used to count patterns in various sets; for instance, the quantity is closely related to the number of length three arithmetic progressions contained in . Let us informally say that a form is*controlled*by the norm if the form is small whenever are -bounded functions with at least one of the small in norm. This definition was made more precise by Gowers and Wolf, who then defined the

*true complexity*of a form to be the least such that is controlled by the norm. For instance,

- and have true complexity ;
- has true complexity ;
- has true complexity ;
- The form (which among other things could be used to count twin primes) has infinite true complexity (which is quite unfortunate for applications).

Gowers and Wolf formulated a conjecture on what this complexity should be, at least for linear polynomials ; Ben Green and I thought we had resolved this conjecture back in 2010, though it turned out there was a subtle gap in our arguments and we were only able to resolve the conjecture in a partial range of cases. However, the full conjecture was recently resolved by Daniel Altman.

The (semi-)norm is so weak that it barely controls any averages at all. For instance the average

is not controlled by the semi-norm: it is perfectly possible for a -bounded function to even have vanishing norm but have large value of (consider for instance the parity function ).Because of this, I propose inserting an additional norm in the Gowers uniformity norm hierarchy between the and norms, which I will call the (or “profinite “) norm:

where ranges over all arithmetic progressions in . This can easily be seen to be a norm on functions that controls the norm. It is also basically controlled by the norm for -bounded functions ; indeed, if is an arithmetic progression in of some spacing , then we can write as the intersection of an interval with a residue class modulo , and from Fourier expansion we have If we let be a standard bump function supported on with total mass and is a parameter then (extending by zero outside of ), as can be seen by using the triangle inequality and the estimate After some Fourier expansion of we now have Writing as a linear combination of and using the Gowers–Cauchy–Schwarz inequality, we conclude hence on optimising in we have Forms which are controlled by the norm (but not ) would then have their true complexity adjusted to with this insertion.The norm recently appeared implicitly in work of Peluse and Prendiville, who showed that the form had true complexity in this notation (with polynomially strong bounds). [Actually, strictly speaking this control was only shown for the third function ; for the first two functions one needs to localize the norm to intervals of length . But I will ignore this technical point to keep the exposition simple.] The weaker claim that has true complexity is substantially easier to prove (one can apply the circle method together with Gauss sum estimates).

The well known inverse theorem for the norm tells us that if a -bounded function has norm at least for some , then there is a Fourier phase such that

this follows easily from (1) and Plancherel’s theorem. Conversely, from the Gowers–Cauchy–Schwarz inequality one hasFor one has a trivial inverse theorem; by definition, the norm of is at least if and only if

Thus the frequency appearing in the inverse theorem can be taken to be zero when working instead with the norm.For one has the intermediate situation in which the frequency is not taken to be zero, but is instead major arc. Indeed, suppose that is -bounded with , thus

for some progression . This forces the spacing of this progression to be . We write the above inequality as for some residue class and some interval . By Fourier expansion and the triangle inequality we then have for some integer . Convolving by for a small multiple of and a Schwartz function of unit mass with Fourier transform supported on , we have The Fourier transform of is bounded by and supported on , thus by Fourier expansion and the triangle inequality we have for some , so in particular . Thus we have for some of the major arc form with . Conversely, for of this form, some routine summation by parts gives the bound so if (2) holds for a -bounded then one must have .Here is a diagram showing some of the control relationships between various Gowers norms, multilinear forms, and duals of classes of functions (where each class of functions induces a dual norm :

Here I have included the three classes of functions that one can choose from for the inverse theorem, namely degree two nilsequences, bracket quadratic phases, and local quadratic phases, as well as the more narrow class of globally quadratic phases.

The Gowers norms have counterparts for measure-preserving systems , known as *Host-Kra seminorms*. The norm can be defined for as

*invariant factor*(generated by the (almost everywhere) invariant measurable subsets of ) in the sense that a function has vanishing seminorm if and only if it is orthogonal to all -measurable (bounded) functions. Similarly, the norm is orthogonal to the

*Kronecker factor*, generated by the eigenfunctions of (that is to say, those obeying an identity for some -invariant ); for ergodic systems, it is the largest factor isomorphic to rotation on a compact abelian group. In analogy to the Gowers norm, one can then define the Host-Kra seminorm by it is orthogonal to the

*profinite factor*, generated by the periodic sets of (or equivalently, by those eigenfunctions whose eigenvalue is a root of unity); for ergodic systems, it is the largest factor isomorphic to rotation on a profinite abelian group.

## 24 comments

Comments feed for this article

25 July, 2021 at 6:04 pm

Freddie MannersIs it possible to state precisely, in terms of this norm, what “true complexity” bound would suffice to generalize results of Peluse and Prendiville to general polynomial patterns of true complexity ? They make some statements in their papers but I have not fully translated between those and these more concise statements.

There seemed to be some subtlety about whether you have control in one position or all positions, which determines whether you can get or , but I could be wrong about that.

25 July, 2021 at 8:11 pm

Terence TaoI think in the notation of this blog post, the two papers of Peluse and Prendiville show bounds of the form

for -bounded , where the subscript here denotes a local version of the norm,

This localisation is necessary because of the scenario in which are locally constant at scale at which point the form basically collapses to and one can no longer exploit any further uniformity of the individual functions .

I have heard from Sarah that analogous results are now known for any average involving polynomials of distinct degree, but this work might not be publicly available yet. I’m not sure what the situation is for the polynomial patterns that are suspected to be of complexity but do not have distinct degrees.

25 July, 2021 at 10:53 pm

Frederick MannersI see, thanks — that’s what’s meant above about the first two indices being different and having at best local norm control.

I think my confusion was more about the stage of the argument where you take certain -control statements as a black box, and try to deduce the corresponding instance of the polynomial Szemerédi theorem for these configurations, with as good a bound as possible.

For illustration take . Reading a bit more of the relevant papers, I think the following are true statements in your language above:–

1. the bound

is known, by [Peluse, “Bounds for sets with no polynomial progressions”], and as a black box this inequality enough to deduce polynomial Szemerédi for for densities (by vanilla density increment);

2. the comments in [“A polylogarithmic bound in the non-linear Roth theorem”, Section 7] seem to suggest that if we knew

then we could feed that into the more powerful “multiplicative gain” density increment machine, essentially as a black box, to get a bound (not currently known in the published literature).

I’m not 100% sure this summary is accurate; hopefully I can be corrected if not.

It is a little surprising in this picture (if correct) that you could get control over one but not the others, so either I’ve misunderstood, or it is a (plausible) quirk of the proofs that the lowest-degree polynomial is somehow special. I guess it seems this issue has been resolved in unpublished work and the better bound is now known.

26 July, 2021 at 6:47 am

Terence TaoOne probably needs to talk to Sarah or Sean for the most up to date status of this problem, but it is certainly easier to use the global norm for density increment purposes with polylogarithmic bounds than the local one if it is available to control the multilinear form, and in the case of say it is only the fourth function that has any hope of being controlled by the global norm, for the geometric reason that is the only element of this quadruple that is very well separated (distance ) from the rest of the quadruple for typical values of . But it seems with Sarah and Sean’s approach that is the hardest function to get their estimates for; they initially only get to control the form in terms of and then struggle to move up to and then to . But once they get control by the global norm of I would imagine that their multiplicative-gain density increment approach would work, at least for the first increment, though for subsequent increments one may need to keep careful track of how the coefficients of the (renormalised) polynomials are growing.

27 July, 2021 at 4:10 am

Sean PrendivillePersonally, I am confident that the argument sketched in §7.1 of https://arxiv.org/abs/2003.04122 should yield control of all functions (and hence poly-logarithmic bounds) for distinct-degree progressions.

In order to implement the strategy sketched, it seems like one cannot use Sarah’s very general results (https://arxiv.org/abs/1909.00309) as a black box, and must re-run her arguments with mildly more general hypotheses (although we did not think too hard about bootstrapping her results to give the more general statements required). I could be entirely mistaken, but the obstructions appear to be only technical (albeit lengthy). Sarah or others may have since thought more about this.

25 July, 2021 at 7:00 pm

VivianThank you, Professor Tao

Sent from my iPhone

>

26 July, 2021 at 6:17 am

MarkCan you explain how does

implies

?

26 July, 2021 at 6:48 am

Terence TaoThis follows from estimates on and the triangle inequality (the errors picked up are of size and can be absorbed into the right-hand side by letting be a sufficiently small multiple of ). The estimate follows in turn from the decay and unit mass properties of .

26 July, 2021 at 7:06 am

LillianCould you please give a brief explanation for the inequality

It looks plausible, but I can’t quite convince myself it is correct. For example, I don’t really see where does on the RHS come from?

[Fixed some typos and added further explanation -T.]26 July, 2021 at 9:05 am

yasminDear Prof Tao,

I have two questions:

“The Fourier transform of {1_I * \psi_\delta} is bounded and supported on {[-1/\delta,1/\delta]}”

– What is the normalisation here? Isn’t $(1_I * \psi_\delta)^\hat (0) = (1_I)\hat (0) (\psi_\delta)^ (0) = |I| \sim N$ which is unbounded?

“{\alpha = \frac{a}{q} + O(1/\eta)}”

– Isn’t the O-term here larger than the main term (a/q)?

[Fixed some typos and added further explanation -T.]26 July, 2021 at 9:46 am

John GriesmerIt may be worth mentioning that the true complexity of for ergodic averages was determined by Furstenberg and Weiss [FW96], and for polynomial expressions of the form by Frantzikinakis (arxiv:0606567).

27 July, 2021 at 2:07 pm

AnonymousCould you post your last Friday’s lecture slides on HIM website? You skipped many slides, and would be helpful for students who are new to the subject.

[Slides are now posted – T.]28 July, 2021 at 5:59 am

Ryan NorrisWhen you do the Fourier expansion of psi(h/delta N) (I assume you are thinking of it as function in integer variable h) to obtain coefficient beta, don’t you need an L^1 upper bound of quality O(1) for its Fourier transform to get the desired conclusion? It’s support is [0,1], but the largest value (coming from zeroth coefficient) is delta*N, which doesn’t seem to be good enough. Or did I mess up the normalisation somewhere?

[Because of the rapid decay of the Fourier transform of , the Fourier transform of is effectively localised to an interval of length . -T]28 July, 2021 at 1:03 pm

Lior SilbermanTrivial typo, but in the definition of the multilinear form in the displayed equation after (1), the on the RHS should be an .

[Corrected, thanks – T.]28 July, 2021 at 7:13 pm

Will SawinFor which class of forms does it make sense to define the complexity? I think Gowers and Wolf defined it only for multilinear forms arising from systems of linear equations, which wouldn’t include the Peluse-Prendiville example (or other examples arising in the work of Peluse and Peluse-Prendiville).

I am worried about the following phenomenon: Suppose we have a multilinear form which is controlled very nicely by a norm which is easy to work with, but happens to not be a Gowers norm. Should we really then say it has complexity infinity?

I was also a bit concerned with whether, if we prove a multilinear form is controlled by a simple norm using a complicated inductive process that passes through the first 10 Gowers norm, it is reasonable to say the problem is complexity 0 just because the final statement doesn’t involve any Gowers norms, but I can’t really complain because a version of this occurs already in the paper of Gowers and Wolf.

I guess one would like to have a heuristic conjecture along the lines of “If this multilinear form is controlled by any nice norm, then it is controlled by some Gowers norm”. Is it reasonable to believe this for translation-invariant multilinear forms, say, which would include the progressions and Peluse-Prendiville examples?

28 July, 2021 at 9:39 pm

Freddie Manners“I guess one would like to have a heuristic conjecture along the lines of “If this multilinear form is controlled by any nice norm, then it is controlled by some Gowers norm”.”

It is almost certainly hard to formulate such a conjecture correctly, but I think it should be true-ish in some settings once you eliminate ways in which it is not true.

For instance, I think the case of polynomial multilinear averages over finite fields should be fairly solid. That is, given polynomials , averages

should be controlled by a norm for some “complexity” s depending on the polynomials, such that if it is controlled by any other norm, that norm control is, in some very vague sense, a weaker statement than control.

(In “vague” I include things such as UAP norms or generalized-convolution-cut-norms, which are loosely but not actually equivalent to Gowers norms.)

The point is that you can consider which 1-bounded functions in your norm have . For Gowers norms, these will be phase polynomials for a polynomial of degree . Because there is no such thing as a polynomial of degree 1.5, and because extremal functions of polynomial multilinear averages are also basically phase polynomials, and for other reasons, I’m willing to guess that the Gowers norm hierarchy is the full story, as per your heuristic conjecture.

Certainly one case where things get more complicated is when you allow “functions in more than one variable”. For example, consider the multilinear average

(Feel free to disguise this in terms of multilinear forms by adding spurious plus signs.)

This is controlled by the Schatten-4 norm, or basically any other spectral norm, but the Schatten-4 norm is of interest because it “looks like” a Gowers norm. However, it is certainly meaningful to say that this has true complexity infinity because it fails to be controlled by any true Gowers norm on . But Schatten-4 control is clearly better than nothing. Maybe this realizes your concern.

In general you will have a raft of different possible norm controls, often incomparable, based on what their 100% functions look like (e.g., things like “all at most quadratic functions ” and “all at most trilinear functions ” can all be assigned norms). But they should still be *coarsely* classified by degree: in other words, such norms should always fit between two consecutive Gowers norms, or fall off one end of the list. I think that coarse measure is what should be understood by complexity in this generality, while understanding that it is not the full story.

For polynomial forms in one variable over the integers, you certainly need to include “local” Gowers norms, where certain parameters are constrained to have local sizes, as Terry points out above. I don’t know how fine the hierarchy of such local norms is: it seems plausible that you can mimic the difficulties arising for functions in several variables by using different scales as if they were different variables, but I have not thought hard about this.

Not sure if that answers any of your questions satisfactorily.

31 July, 2021 at 10:28 am

Terence TaoI agree with basically everything Freddie said. In general one would expect the notion of complexity to take values in some weird partially ordered set, where some norms control others but there is no obvious reason why there should be a total ordering. But in the case of one-dimensional averages at a given spatial scale there does seem to be this remarkable phenomenon that there is this one-dimensional hierarchy of Gowers norms that control everything (after belatedly adding this final norm to the hierarchy). For instance, the “ norm” that comes from taking the maximal inner product of against a globally quadratic phase (as opposed to a locally quadratic phase) is intermediate in strength between the and norms (as depicted on the diagram in the blog post, where it is labeled ), but does not seem to be associated as the true complexity of any polynomial average, as far as I know; any average that is sensitive to globally quadratic phases is automatically also sensitive to locally quadratic phases (or degree 2 nilsequences, or bracket quadratic phases) and thus is really controlled by rather than . As such the norm plays only a very minor role in additive combinatorics.

It reminds me a bit of the phenomenon in reverse mathematics, where one would a priori expect a hugely complicated partially ordered set of theories of arithmetic where various theorems in analysis (Bolzano-Weierstrass, Heine-Borel, etc.) naturally live, but instead one ends up with a “big five” of arithmetic theories (, , etc.) which are basically the “complexity” for the vast majority of such theorems.

The situation is currently understood the best in the ergodic theory setting, where the analogue of the notion of complexity is known as the “characteristic factor” – the maximal factor of a given system in which all functions orthogonal to (or equivalently, all functions with vanishing conditional expectation are negligible for a given ergodic average. For any given multiple polynomial average we now know that the characteristic factor is always one of the Host-Kra factors , or the profinite factor (modulo some minor technicalities at small primes where there is “ramification”), though the proof proceeds by first controlling things by some Host-Kra seminorm (the analogue of the Gowers norm in the ergodic setting) of enormous degree and then whittling down the degree. Perhaps as the degree-lowering theory matures we will have a better understanding of where true complexity actually comes from and why the Gowers uniformity hierarchy is pretty much all that shows up, but the phenomenon still only partially understood at present.

As discussed in other comments, the situation seems to be markedly different in the setting of polynomial averages over finite fields, where there are many more algebraic obstructions in play.

31 July, 2021 at 11:04 am

John GriesmerThere are polynomial averages whose characteristic factor is strictly between and (and therefore is not one of the or ): Theorem B of Frantzikinakis’s three polynomials paper shows that the characteristic factor for is the maximal 2 step affine factor of , which is (often) strictly between and .

31 July, 2021 at 12:17 pm

Terence TaoHuh, I was not aware of this very interesting example! On the algebraic side it seems to boil down to the identity

for real which shows that globally quadratic phases are non-negligible for this average, but there isn’t an analogous identity (or near-identity) for locally quadratic functions. So perhaps on the combinatorial side the average is in fact controlled by the norm and not just the norm (and not by the norm), which would be the first example of a “complexity 1.5 pattern” that I am aware of. I stand corrected!

EDIT: a concrete conjecture in this regard would be that

for some and all -bounded , with the obvious definitions for the local norm . There does seem to some chance that the degree lowering machinery could stretch to cover this case without needing to touch the inverse theorem which currently does not enjoy polynoimal bounds.

3 August, 2021 at 4:44 pm

Will SawinIf we look at the average then the identity appears, showing that a cubic phase in any of the first three variables is not negligible.

Are locally quadratic phases non-negligible for these functions? I don’t see why they would be, since they don’t have any special structure when polynomials are multiplied and thus they should only see the three linearly dependent terms , where we know only additive phases contribute.

So maybe the norm relevant for this example is strictly incomparable with the norm?

28 July, 2021 at 10:25 pm

Freddie MannersActually I guess parts of this are not as mysterious as I’m trying to make it. You are essentially asking for a converse to Gowers–Wolf: for (say) a system of linear forms of complexity at index , show that for all there exists such that if then there exist 1-bounded functions such that

The point is that is vacuously and optimally controlled by the “ cut-norm”, namely the supremum of the left-hand side over all 1-bounded functions . Gowers–Wolf asserts that this cut-norm is bounded above (in a very weak sense) by for a suitably chosen ; this would imply the two norms are equivalent (in a very weak sense).

For systems of linear forms, or polynomial forms over finite fields, I would be fairly confident this is true, but am also confident it is not known. For polynomial forms over the integers, I have no idea what to expect.

29 July, 2021 at 5:44 am

Will SawinI think this is not true as you state for polynomial forms over finite fields.

For one, we could have in which case we need to use the multiplicative group Gowers norm and not the additive group Gowers norm. Probably one can even get elliptic Gowers norms to show up as well.

You could say “well, those are all really different types of Gowers norms even if they’re not literally part of the same sequence of norms” but then you could have each of the form for other polynomials and then you would need to know about the average value of your s against the number of ways of representing them as , which is not periodic additively or multiplicatively.

There’s a lot of norms you could potentially need to get the full picture.

29 July, 2021 at 6:53 am

Freddie MannersOf course you are right — I had not considered things like geometric progressions or even more badly-behaved examples. Was the point in your original post that adding “translation-invariant” is a good way to kill these off and fall back into the safe ergodic-theoretic world I probably imagined I lived in?

I think a number of my comments above could wind up being technically correct as stated if I simply bundle all these examples in as “infinite complexity”, but I guess that’s exactly the thing you objected to in the first place.

I think it is a consistent if unambitious world-view to say that “complexity” really means “degree complexity”, and has to do with cases whether the 100% solutions are necessarily phase polynomials of bounded degree; and if not, the “degree complexity” is infinite and you are on your own.

Certainly given your examples, I don’t know how to tell whether a system of polynomial forms has finite degree complexity just by looking at it, and that seems like a very natural question I would like to know the answer to.

29 July, 2021 at 8:14 am

Will SawinI’m not sure if translation-invariant is a good way to kill off all of these, though I suspect it might be. I asked because I thought someone else might know.

For systems of polynomial forms, or, slightly differently, systems of polynomial equations, I a while ago had an idea (inspired by some stuff Jacob Tsimerman told me) of using Galois theory to classify what kind of norms you should need for a given system, based on the theory that the worst-behaved functions for a given system of forms should be characteristic functions of sets of points with a fixed splitting behavior in a Galois cover of the line. But even proving the purely Galois-theoretic statements needed for this idea to make sense proved tricky, let alone making it actually interface with the combinatorics.