Quasipolynomial bounds on the inverse theorem for the Gowers -norm
Abstract.
We prove quasipolynomial bounds on the inverse theorem for the Gowers -norm. The proof is modeled after work of Green, Tao, and Ziegler and uses as a crucial input recent work of the first author regarding the equidistribution of nilsequences. In a companion paper, this result will be used to improve the bounds on Szemerédi’s theorem.
1. Introduction
We recall the definition of the Gowers -norm on and . Throughout we let .
Definition 1.1.
Given and , we define
where is the multiplicative discrete derivative (extended to lists by composition). Given a natural number and a function , we choose a number and define via for and otherwise. Then
Remark.
This is known to be well-defined and independent of , and a norm if ; see [27, Lemma B.5].
Our main result is quasi-polynomial bounds on the inverse theorem for the Gowers -norm over the integers. This builds on earlier work [43, Section 8] of the first author which handled the case of the -norm.
Theorem 1.2.
Fix . Suppose that is -bounded and
Then there exists a nilmanifold of degree , complexity at most , and dimension at most as well as a function on which is at most -Lipschitz such that
where we may take
Remark.
Throughout this paper, we will abusively write for ; this is to avoid issues with small numbers.
We have not formally defined a nilmanifold or notions of complexity; our definition is identical to that in work of Green and Tao [29] and will be recalled precisely in Sections 2 and 3.
In the companion paper to this work [46], we will use Theorem 1.2 in order to improve the long standing bounds of Gowers [16, 18] on Szemerédi’s theorem.
Theorem 1.3 (Theorem 1.1 in [46]).
Let denote the size of the largest such that has no -term arithmetic progressions. For , there is such that
1.1. History and previous results
A long standing conjecture of Erdős and Turán [13] stated that . In full generality, this conjecture remained open until a combinatorial tour de force of Szemerédi [54, 55] which established the Erdős and Turán conjecture.
Theorem 1.4.
For , we have that
Due to uses of the van der Waerden theorem and the regularity lemma (which was introduced in this work), Szemerédi’s density saving over the trivial bound was exceedingly small. In particular, Szemerédi’s result provided no improvement on known bounds for van der Waerden’s theorem which was part of Erdős and Turán’s original motivation.
The first result in the effort to prove reasonable bounds for , e.g. giving a density saving of at least a finite iterated logarithmic type, came from work of Roth [50] which proved
Being based on Fourier analysis, the methods used in this paper did not obviously generalize to . An estimate for which was “reasonable” would have to wait until pioneering work of Gowers [16, 18].
The starting point of work of Gowers [16, 18] is noting via an iterative application of the Cauchy–Schwarz inequality that if a set of density in has no -term arithmetic progressions then where is a shifted indicator function of the set. In doing so, Gowers provided the correct notion of “psuedorandomness” generalizing Fourier coefficients which was suitable for understanding arithmetic patterns in subsets of the integers and therefore created “higher order Fourier analysis”. The key technical ingredient in work of Gowers was a certain “local inverse theorem” for the -norm. Gowers proved that given a -bounded function such that , there exists a decomposition of into arithmetic progressions of length roughly and a -bounded function which is constant along these arithmetic progressions such that
i.e., correlates with . This result, coupled with the density increment strategy as introduced by Roth [50], provided the bound
for Szemerédi’s theorem. These bounds have remained the best known for general until this work. For the sake of comparison, a long sequence of works have attacked the special case of , culminating in a recent breakthrough work of Kelley and Meka [41] which proved
the constant was refined to in work of Bloom and Sisask [5]. The only other improvements to the bound of Gowers were due to works of Green and Tao [25, 30] which ultimately established that
and very recent work of the authors [45] which handled the case of Theorem 1.3.
Notice however that the “local inverse theorem” of Gowers only gives correlations on arithmetic progressions of length and that the converse of this result is not true. In particular, a function may have small -norm and still correlate with a function which is constant on progressions of length . To construct such an example, break into consecutive segments of length and include each segment with probability ; while this set with high probability has large “local correlations” it has polynomially small Gowers norm. To obtain a full inverse result (analogous to the quality of Freiman’s theorem, say), one must carefully pin down the global structure as well. Such a task is not straightforward, since the natural generalization of Fourier characters to exponentials of polynomials does not suffice.
A crucial development in the theory towards the inverse conjecture for the Gowers norm was the discovery of the role of nilpotent Lie groups. In groundbreaking work, Furstenberg [14] gave an alternate proof of Szemerédi based on ergodic theory; this work naturally led to seeking to understand certain nonconventional ergodic averages. In works of Conze and Lesigne [11] and Furstenberg and Weiss [15] regarding nonconventional ergodic averages, nilmanifolds where is nilpotent and is a discrete cocompact subgroup were brought to the forefront. Host and Kra [38] and independently Ziegler [62], proved convergence of such nonconventional ergodic averages. Crucial to these works was establishing that such averages are controlled by projections on certain characteristic factors which naturally give rise to nilmanifolds. The role of nilsequences (derived from polynomial sequences on nilmanifolds) was further highlighted in work of Bergelson, Host, and Kra [3].
The statement of the inverse conjecture (without the given quantification) we will prove was first formulated in work of Green and Tao [27]. Conditional on this inverse conjecture and that the Möbius function does not correlate with nilsequences, Green and Tao were able to prove asymptotic counts for all linear patterns in the primes of “finite complexity”, vastly generalizing the celebrated Green–Tao theorem [24]. Both of these conjectures were resolved; the second being resolved in work of Green and Tao [28] while the first was resolved in work of Green, Tao, and Ziegler [34]. We remark the cases and of the inverse conjecture were proven earlier by Green and Tao [23] and Green, Tao, and Ziegler [32] respectively. A crucial ingredient in the cases was work of Green and Tao [29] on the equidistribution behavior of polynomial orbits on nilmanifolds. An alternative approach to the inverse conjecture was initiated by Szegedy [53], involving the development of the theory of nilspaces by Camarena and Szegedy [6]; a detailed treatment of these papers was given by Candela [8, 7]. This nilspace approach has been further developed in works of Gutman, Manners, and Varjú[36, 35, 37]. Both of these approaches to the inverse theorem, however, at least formally, gave no bounds on the complexity or dimension of the nilsequences with which the function correlates in the cases . A third approach due to Manners [47] will be discussed later in this section.
We remark that the study of the inverse conjecture for the Gowers norm makes sense beyond the setting of functions on the interval or on the cyclic group . Work of Bergelson, Tao, and Ziegler [4] and Tao and Ziegler [59, 60] resolved the analogue of the inverse conjecture for the Gowers norm over . Candela and Szegedy [10] gave a version of the inverse conjecture for the Gowers norm over all compact abelian groups. This final work falls within the context of giving proofs which, broadly speaking, attempt to handle various abelian groups in a uniform manner. There has been substantial further work in this rough direction including works of Jamneshan and Tao [40], Jamneshan, Shalom, and Tao [39], and Candela, González-Sánchez, and Szegedy [9].
The inverse theorem has had numerous further applications within additive combinatorics; we highlight just two. First, Tao and Ziegler [61] gave an asymptotic for the number of polynomial patterns in the primes where with top degree terms being distinct. Second, works of Green and Tao [26] and Altman [2, 1] used the inverse conjecture in combination with an arithmetic regularity lemma to establish the true complexity conjectures of Gowers and Wolf [21].
Due to its importance in the theory of additive patterns, establishing quantitative bounds on the inverse theorem for the Gowers norm has been seen as a central problem in additive combinatorics, with Green suggesting it as “perhaps the biggest open question in the subject” [22, Problem 56]. For the case of , work of Green and Tao [23] gave quantitative bounds for the inverse theorem over the integers and work of Sanders [51] combined with the strategy in [23] proves Theorem 1.2 for the case of . For general , until roughly five years ago no quantitative bounds were known for the inverse theorem and this was considered a major open problem. This state of affairs was substantially improved in remarkable work of Manners [47] which proves a version of the inverse theorem where, in the notation of Theorem 1.2,
This result was subsequently used as a crucial input in work of Tao and Teräväinen [57] to give an effective result for the counts of linear equations in the primes. We remark that a quantitative version of the inverse conjecture over finite fields of high characteristic was proven in work of Gowers and Milićević [20, 19].
At the highest level, the quantitative proofs of Manners [47] and Gowers and Milićević [20, 19] examine when the iterated derivatives of a function are with positive probability. Deriving useful information from this hypothesis over finite fields and the integers are very different problems but fundamentally one glues information from higher derivatives together into information regarding lower derivatives iteratively.
Our proof instead operates via induction on and attempts to glue degree nilmanifolds into a degree one exactly as in work of Green, Tao, and Ziegler [34]. Our proof in fact is very closely modeled on their work and borrows large sections of their work essentially verbatim. In fact, we believe that the proof in [34], if appropriately quantified, itself yields a bound involving many iterated exponentials. The primary improvement of our proof over theirs stems from the use of improved quantitative equidistribution results on nilmanifolds [43, 42] rather than the results of [29]. The reason we obtain quasi-polynomial bounds is that our proof, even though it inducts on , gives quasi-polynomial bounds for each step of the induction. Since an iterated composition of finitely many quasi-polynomial functions is still quasi-polynomial, it follows that our bounds should remain quasi-polynomial. In contrast, we believe that the proof in [34], appropriately quantified, results in adding iterated exponentials in each step of the induction, which when iterated totals iterated exponentials. Here the results of [43, 42] play a crucial role in eliminating the logarithms accumulated in the induction step. We further remark that the case of the main theorem (e.g. the -inverse theorem) of the strength in Theorem 1.2 was proven earlier by the first author in [43, Section 8] and may useful stepping stone for reading this paper (although this paper is logically independent).
1.2. Organization of the paper I
We briefly discuss the next three sections of the paper. In Section 2, we define a number of basic notions regarding nilmanifold and set various conventions which will be used throughout the paper. Our conventions differ in various extremely minor ways from those in the work of Green, Tao, and Ziegler [34] but we record them explicitly to recall a number of definitions which will be used throughout the paper. In Section 3, we set various complexity notions that will be given throughout the paper. In the case of nilmanifolds which are given a degree filtration (as is the case in Theorem 1.2), our conventions match those of Green and Tao [29]. Given these notions in hand, we will be in position to outline the main proof in greater detail in Section 4.
Acknowledgements
The first author thanks Terence Tao for advisement. The authors thank Ben Green and Terence Tao for useful discussions regarding [34, 31]. The authors are grateful to Dan Altman, Ben Green, and Zach Hunter for comments. Finally the authors are especially grateful to Sarah Peluse for exceptionally detailed and useful comments on the manuscript.
2. Conventions on nilmanifolds
We will recall a large portion of setup regarding nilsequences. In order to discuss this in a quantitative manner, various complexity notions are required which are formally defined in Section 3. This section contains little more than bare definitions; a number of these concepts are developed and motivated in a beautiful manner in [34, Section 6].
2.1. Basic group theory
We briefly record various basic group theory notations which will be used throughout the paper; our notation is identical to that of [34, Section 3].
Given a group and a subset , we define to be the subgroup generated by the subset . Given a collection of subgroups in , we define to be the smallest subgroup containing all the . Given , we denote the commutator of and to be
Given a sequence of elements , we define the set of -fold commutators inductively. The -fold commutators of the set is simply . For , an -fold commutator is where and are -fold and -fold commutators of and respectively with and . For instance, and are -fold commutators of , , , and .
We let denote that is a subgroup of . Given , we denote the commutator subgroup
The following pair of elementary lemmas will be used throughout the paper to verify various commutator identities; the first is [34, Lemma 3.1].
Lemma 2.1.
Let and be normal subgroups of a nilpotent group . Then is also normal and is generated by the -fold iterated commutators of over all choices of , and .
This implies (see [34, p. 1242]) that for families , which are normal in a nilpotent group ,
We next require that normality and various filtration conditions can be checked at the level of generators.
Lemma 2.2.
Suppose with where and . Then:
-
•
If for all and then is normal in .
-
•
Suppose is a normal subgroup with respect to both and , and suppose for , , we have . Then .
Remark.
Suppose we wish to prove that forms an -filtration (see Definition 2.3). This lemma implies that it suffices to check the commutator filtration conditions simply at the level of generators: if for each we know for all generators for and for , then we can deduce that is normal in using the first bullet point above, and then deduce that using the second bullet point above.
Proof.
For we have hence . Since generates , we find . Since generates , we deduce that is normal in .
For the second item, note that
Repeatedly expanding for into generators proves the result. ∎
Finally, and most importantly, we will require the following versions of the Baker–Campbell–Hausdorff formula (see [34, (3.2)]). Given in a nilpotent group and , we have
(2.1) |
where ranges over all iterated commutators of and with at least copy of each and is a polynomial in and . Furthermore if involves copies of and copies of we have that has degree at most in and degree at most in . Here the have been ordered in some arbitrary manner.
If is a connected, simply connected nilpotent Lie group, then we denote the Lie algebra of as and let denote the exponential map while is the inverse (the exponential map being a homeomorphism in this situation). When we refer to nilpotent Lie groups, they will henceforth be connected and simply connected. For and , we define
The Baker–Campbell–Hausdorff formula also implies that
where ranges over all iterated commutators of and with at least copy of each and is a polynomial with rational coefficients satisfying identical degree constraints to . Finally we require the following, most standard version, of the Baker–Campbell–Hausdorff formula which states that if , then
where the remaining terms in the expansion are iterated commutators in and with all higher terms having at least one “copy” of and within them. In particular, this implies that
(2.2) |
where are all higher order terms have at least one copy of and in them and are -fold commutators with . In all versions of Baker–Campbell–Hausdorff, it is important for us that nilpotency means these expressions are finite.
2.2. Filtrations
We next require the notion of an ordering and an associated filtration (see [34, Definition 6.7]).
Definition 2.3.
An ordering is a set with a distinguished element , binary operation , and a partial order on such that
-
•
is associative and commutative with acting as an identity element;
-
•
has as the minimal element;
-
•
For all , if then ;
-
•
The initial segments are finite for all .
We define the following three orderings, with addition being the standard addition:
-
•
The degree ordering is given by the standard ordering on , denoted for short;
-
•
The degree-rank ordering is given by with the ordering that if or and , denoted for short;
-
•
The multidegree ordering is given by with when for all , denoted for short.
An -filtration of is a collection of subgroups such that and:
-
•
(Nesting) If are such that then ;
-
•
(Commutator) For , we have .
We say that a filtered group has degree (for ) if is trivial for . has degree for a downset if is trivial whenever .
Note that the commutator condition implies nested subgroups are normal within each other. We next define degree, degree-rank, and multidegree filtrations.
Definition 2.4.
Given , we say a group is given a degree filtration of degree if:
-
•
is given a -filtration with degree ;
-
•
.
Given with , is given a degree-rank filtration of degree-rank if:
-
•
is given a -filtration with degree ;
-
•
and for . (We also let for .)
The associated degree filtration with respect to this degree-rank filtration is .
Given , is given a multidegree filtration of multidegree (where is a downset) if:
-
•
is given a -filtration with degree ;
-
•
.
The associated degree filtration with respect to the multidegree filtration is . Here .
Remark.
This definition imposes some additional equalities of subgroups in order to say a group is given a degree-rank filtration versus a -filtration (for example). In particular, the concept of “degree-rank” filtration and -filtration are distinct. The difference is minor, but causes a number of technical checks to be required, most notably in Appendix C. We will almost exclusively operate with these additional conditions; this is so that we can invoke equidistribution theory safely.
We now define polynomial sequences of an -filtered group. The notion of a polynomial sequence for a group given a degree-rank filtration will be the same as treating this ordering as a -filtration; the same applies for degree and multidegree filtrations.
Definition 2.5.
Given a map between groups (not necessarily a homomorphism) and , we define the derivative via for all . If are -filtered, we say that this map is polynomial if for all and , we have
for all choices of and . The space of all polynomial maps with respect to this data is denoted .
We will require various general properties of polynomial sequences established in [34, Appendix B]. We will only consider for and the following -filtrations on .
Definition 2.6.
We define the following filtrations on :
-
•
The (domain) degree filtration is with the degree ordering and , and for ;
-
•
The (domain) multidegree filtration is with the multidegree ordering, , for , and otherwise, where forms the standard basis of ;
-
•
The (domain) degree-rank filtration is with the degree-rank ordering and and otherwise.
We now define the notion of a nilmanifold, which is essentially a compact quotient of a filtered nilpotent Lie group.
Definition 2.7.
We define an -filtered nilmanifold to be the data of a connected, simply connected nilpotent Lie group with -filtration (of Lie subgroups) and discrete cocompact subgroup which is rational with respect to (i.e., is cocompact in for all ). We say it has degree or if has degree or .
If and the -filtration is furthermore a degree filtration with degree , then is a degree nilmanifold. If and the -filtration is furthermore a degree-rank filtration with degree , then is a degree-rank nilmanifold. Finally if and the -filtration is furthermore a multidegree filtration with degree , then is a multidegree nilmanifold.
Remark.
Note that can naturally be given the structure of an -filtered group .
We finally (very occasionally) will require the lower central series of a group .
Definition 2.8.
Given a nilpotent group , define the lower central series inductively via and . The step of is the minimal such that .
2.3. Horizontal tori and Taylor coefficients
The next notion, that of a horizontal character, plays a vital role when discussing the equidistribution of nilsequences.
Definition 2.9.
Given a connected, simply connected nilpotent group and a discrete, cocompact subgroup , a horizontal character is a continuous homomorphism such that . We say a horizontal character is nontrivial when is not identically zero.
Remark.
Throughout the literature on nilmanifolds, horizontal characters are continuous homomorphisms such that annihilates . It is straightforward to prove (via using Mal’cev bases) that these two notions are identical up to taking . The reason we operate with the above definition is that the kernel of as defined is then a subspace of .
We next require the notion of horizontal tori with respect to a degree-rank filtration. These tori will play a starring role in Sections 8, 9, and 10; our definition is exactly that of [34, Definition 9.6].
Definition 2.10.
Let be a degree-rank filtered nilpotent Lie group with filtration . Given a subgroup of , we define various horizontal tori for as
Given a polynomial sequence we define the -th horizontal Taylor coefficient to be
where we take iterated derivatives.
We also require the notion of -th horizontal characters.
Definition 2.11.
Consider a nilmanifold with a degree-rank filtration. A continuous homomorphism is an -th horizontal character if and .
The name Taylor coefficient is also used in the context of Taylor coefficients of polynomial factorizations. The following elementary lemma relates these two notions; we remark that a very closely related proof appears in [26, Lemma A.8].
Lemma 2.12.
Let be given a degree-rank filtration of degree-rank and consider a sequence . Then we may write for elements and for we have
Proof.
The representation of in the specified product form follows immediately from the existence of Taylor expansion, see [34, Lemma B.9].
We next prove for each individually. Notice that it suffices to consider which is , i.e., we consider the group with quotiented filtration. This group is easily seen to be at most -step nilpotent and furthermore for (one should check the cases and manually). Let for and note .
We see that is an -filtration for with for all . Note that where is .
It suffices to prove the claim that with and . If this is the case, then we may modify the filtration by stripping off the top group, which maintains the necessary inductive properties. Iterating this procedure times we obtain the desired Taylor equality.
This claim is a consequence of the Taylor expansion for general polynomial sequences and the Baker–Campbell–Hausdorff formula and counting the depths of nested commutators. The crucial reason that is that any “higher order” terms which arise in the Baker–Campbell–Hausdorff formula and could contribute are in fact annhilated due to for . ∎
We also have the following linearity of the -th Taylor coefficients.
Lemma 2.13.
Remark 2.14.
Note that is abelian and hence additive notation may be used when considering Taylor coefficients.
Proof.
The first claim follows from Lemma 2.12, the Baker–Campbell–Hausdorff formula, and the commutator relationship that . (Note that this is using in the case .)
For the second claim, suppose that
Via iterated applications of the Baker–Campbell–Hausdorff formula and the commutator relationship that , we see that and the result follows. ∎
2.4. Vertical tori and nilcharacters
Given a polynomial sequence on an -filtered Lie group with , we can define a sequence of vectors by considering a smooth vector-valued function on and looking at . However, we will be particularly interested in those which “have a Fourier coefficient” with respect to various subgroups of the center.
Definition 2.15.
Consider a nilmanifold and a function . Given a connected, simply connected subgroup of the center which is rational (i.e., is cocompact in ) and a continuous homomorphism such that , if
we say that has a -vertical character (or -vertical frequency) .
Remark.
Note that is isomorphic to a torus and thus one can modify functions under consideration to have vertical characters via appropriate Fourier decomposition.
A particular case which will arise frequently in our applications comes from the fact that given a filtration satisfying the conditions of Definition 2.4, we have that the “bottom group” is contained in the center. For example, a group given a degree filtration of degree satisfies hence . One special class of functions with a vertical frequency which will be of particular importance is that of nilcharacters.
Definition 2.16.
A nilcharacter of degree and output dimension is the following data. Consider an -filtered nilmanifold of degree such that and an -filtered abelian group . Let and consider function such that:
-
•
for all pointwise;
-
•
for all where is some continuous homomorphism such that .
The values of the nilcharacter are given by where for .
Remark.
We work with vector-valued nilcharacters for precisely the same topological reason given in [34, p. 1254].
2.5. Additional miscellaneous conventions
We end this section with a brief discussion of various miscellaneous conventions. Throughout the paper we use to denote the map (or , abusively) which takes the representative closest to . Furthermore given and we will treat in the obvious manner. As used above, we let denote the exponential function , which is lifted to in the obvious manner.
We use standard asymptotic notation. Given functions and , we write , , , or to mean that there is a constant such that for sufficiently large . We write or to mean that and , and write or to mean as . Subscripts indicate dependence on parameters.
Finally in various arguments throughout the paper it will be convenient to denote appropriately bounded functions as or , and when vector-valued. When using such notation, the functions may change from line to line and within a line may refer to different functions.
3. Various complexity notions
3.1. Rationality of bases and Lipschitz norms
We will now discuss the definitions chosen for complexity of nilmanifolds. We start by defining first- and second-kind coordinates given a basis for .
Definition 3.1.
Consider a connected, simply connected nilpotent Lie group of dimension . Given a basis of and , there exists such that
We define Mal’cev coordinates of first-kind for relative to by
Given there also exists such that
and we define the Mal’cev coordinates of second-kind for relative to by
Note that the above definition does not account for the cocompact subgroup . The next set of definitions account for how “rational” is with respect to itself and .
Definition 3.2.
The height of a number is if with and if is irrational.
Definition 3.3.
Given a nilmanifold of dimension , consider a basis of . is said to be a weak basis of rationality with respect to if:
-
•
There exist rationals of height at most such that
-
•
There exists integer such that
is a Mal’cev basis of with respect to of rationality if:
-
•
There exist rationals of height at most such that
-
•
.
We say that has the degree nesting property if there exist such that if then , and .
Finally we say that a Mal’cev basis is adapted to a sequence of nesting subgroups if
for .
We next state the definition of the Lipschitz property for a function on .
Definition 3.4.
We define a metric on by
where denotes the -norm on , and define a metric on by
Furthermore, for any function we define
Given a function such that we define
Remark.
Note that the metric on is right-invariant. We may omit the subscript for the distance function when clear from context.
3.2. Complexity of nilmanifolds
We now define the complexity of a nilmanifold with respect to either a degree or a degree-rank filtration.
Definition 3.5.
Let be an integer and let . A nilmanifold of degree , dimension , and complexity at most consists of a degree filtration of along with a Mal’cev basis of which satisfies the following:
-
•
is a Mal’cev basis for with respect to of rationality at most ;
-
•
is adapted to the sequence of subgroups .
Analogously a nilmanifold of degree-rank , dimension , and complexity at most consists of a degree-rank filtration of along with a Mal’cev basis of which satisfies the following:
-
•
is a Mal’cev basis for with respect to of rationality at most ;
-
•
is adapted to the sequence of subgroups .
Remark.
The only difference in complexity for a degree versus degree-rank filtration is that we require the Mal’cev basis to be adapted with respect to the appropriate filtration. This definition unfortunately does not extend to the case of multidegree filtrations since the set of subgroups do not nest in a total order. Furthermore note that a degree-rank nilmanifold of complexity is also a degree nilmanifold of the same complexity by taking the associated degree filtration.
Finally, whenever discussing the complexity of nilmanifolds, this is always with respect to a given Mal’cev basis . We will abusively write phrases such as “nilmanifold of complexity ” throughout the paper; such a statement should always be understood with a corresponding implicitly provided adapted Mal’cev basis of the Lie algebra.
Remark.
We will also in passing require the notion of a degree nilmanifold. A degree nilmanifold is simply the trivial group . All scalar-valued functions on degree nilmanifolds are constants and the Lipschitz norm is defined to be the absolute value of this constant.
We will next need the notion of a rational subgroup with respect to a Mal’cev basis; this will be crucial when giving the definition of complexity with respect to a multidegree filtration.
Definition 3.6.
A closed, connected subgroup is -rational with respect to a basis of if has a basis where for with having heights bounded by .
We will repeatedly use the following fact about rational subgroups without further comment.
Fact 3.7.
Suppose is a connected, simply connected nilpotent Lie group of step and dimension with a discrete cocompact subgroup . Suppose that has a weak basis of rationality at most . Let be subgroups which are each -rational and normal in . Then
is an -rational subgroup.
Proof.
Let denote the underlying basis of witnessing low height. By applying Baker–Campbell–Hausdorff, we have that is spanned by taking all -fold commutators of elements in (possibly for different ). Each such element of the Lie algebra is easily seen to be a -rational combination of (using the weak basis property of ). Taking a subset of these commutators which forms a basis of gives the desired result. ∎
We are now in position to define the complexity of a multidegree nilsequence. This definition is admittedly rather artificial but is designed to be the most flexible given various lemmas scattered throughout the literature.
Definition 3.8.
Consider a downset with respect to the multidegree ordering on . Consider a group with a multidegree filtration of degree . Recall the associated degree filtration
and define the associated degree to be . We say a multidegree nilmanifold of dimension with Mal’cev basis has complexity at most if:
-
•
is a Mal’cev basis for with respect to of rationality at most ;
-
•
is adapted to the sequence of subgroups ;
-
•
is an -rational subgroup for all .
We next note the trivial fact that complexity is bounded appropriately with respect to taking direct products; we implicitly invoke this when handling the complexity of direct products.
Fact 3.9.
Consider nilmanifolds , given degree filtrations , and adapted Mal’cev bases each of complexity at most . Then has complexity at most with respect to the Mal’cev basis
may be adapted to the degree filtration by creating an ordering with suffixes
Furthermore given and which are -Lipschitz,
is -Lipschitz on . Analogous statements hold for degree-rank filtrations and multidegree filtrations.
We finally end by noting that quotients by normal subgroups of bounded rationality have appropriate complexity.
Lemma 3.10.
Consider a nilmanifold with given a degree filtration and of complexity at most with respect to an adapted Mal’cev basis .
Suppose that is a normal subgroup of which is -rational with respect to . Then the quotient nilmanifold may be given an adapted Mal’cev basis , where the degree filtration is , which is an -rational combination of
Analogous statements hold for degree-rank filtrations and multidegree filtrations. Finally if and is an -Lipschitz function on which is -invariant then descends to and is -Lipschitz with respect to .
Proof.
We may find a subset such that
is a basis for . Since is -rational with respect to , it follows from Cramer’s rule that for , is a -combination of with . Hence, is a weak Mal’cev basis for of rationality . By [42, Lemma B.11], we may find a Mal’cev basis adapted to with complexity . Now, if and is -Lipschitz on which is -invariant, it follows trivially that descends to a function on . The Lipschitz bounds for follow from [42, Lemma B.3]. ∎
3.3. Size of vertical and horizontal characters
We now define the size of vertical and horizontal characters. We first define the size of a horizontal character.
Definition 3.11.
Given a nilmanifold and a Mal’cev basis , note that any horizontal character can be expressed in the form
for some . We define the size of the horizontal character as .
We next define the size of an -th horizontal character.
Definition 3.12.
Consider a nilmanifold with given a degree-rank filtration of degree-rank and a Mal’cev basis adapted to the degree-rank filtration. Note that any -th horizontal character can be expressed in the form
with for some which is nonzero only on coordinates between . We define the size of the -th horizontal character as .
We finally define the size of a vertical character.
Definition 3.13.
Consider a nilmanifold with given a degree filtration of degree and a Mal’cev basis adapted to the degree filtration. Consider a continuous vertical character from a rational subgroup . We define the height of as
this will be denoted as .
Remark.
We now justify the terminology “height” given for the complexity of a vertical character. Suppose that has complexity (given ) with respect to a degree filtration of degree and is -rational. We have that has a Mal’cev basis which is a -rational combination of by [42, Lemma B.12]; denote this . By [42, Lemma B.9], we have that for ,
With respect to , we have that is an integer vector and the definition of height is equivalent up to a multiplicative factor of to the height of this vector.
3.4. Correlation
We will also require the notion of a sequence being biased of some order.
Definition 3.14.
A function is -biased of correlation , complexity , and dimension if there exists a nilmanifold with a degree filtration such that has dimension at most , has complexity at most , and there exists an -Lipschitz function and a polynomial sequence such that
We will denote this as .
3.5. Miscellaneous complexity notions
We will also require the following definition regarding smoothness norms of polynomial sequences.
Definition 3.15.
Given and , we define
Any polynomial sequence can be expressed uniquely as
with . We define
where .
Remark.
Note that the above definition is only sensitive to the values of .
We now define when a polynomial sequence is rational and smooth.
Definition 3.16.
Consider a nilmanifold given either a degree, degree-rank, or multidegree filtration with Mal’cev basis and a domain polynomial sequence on with respect to the given filtration. We say that is -smooth if:
-
•
;
-
•
for and .
We say that is -rational if there is such that for all we have that
4. Proof outline
We are now in position to discuss the proof of Theorem 1.2; as our proof is closely modeled on that of Green, Tao, and Ziegler [34], the announcement of [33] may prove a useful starting point for certain readers. For various parts of this outline we will restrict to the case of the -inverse theorem and discuss the proof as if the analysis were performed with bracket polynomials.
4.1. Induction on degree and additive quadruples
Suppose that is -bounded such that
Via the inductive definition of the Gowers norm, we have for values of that
Call this set of indices . Applying Theorem 1.2 inductively (when converted to bracket polynomials; see e.g. [45, Proposition 1.4]) we may choose and coefficients etc. such that
we have padded with extra coefficients to make the dimensions not -dependent. Set
4.2. Sunflower and linearization for the top degree-rank
Via bracket polynomial manipulations, we see that the “top degree-rank” term of the above expression is
The heart of the proof is demonstrating that these “top degree-rank terms line up” in an appropriate sense across a dense additive tuples in . Such a conclusion is at least plausible since for generic coefficients the associated bracket polynomial equidistributes, which would violate the given condition on . One possibility where the top degree-rank term is exactly zero is when we can write , , . The heart of the matter is that, up to controlled modifications, this is the only way for that to occur in a robust sense.
The first modification is that we can replace in the above example the expression with or more generally a bracket linear form. The second modification is that we may not get a description that respects the presented structure of the sum. Instead the coordinates of the bracket linear form may only appear in these “fixed”, “fixed”, “bracket linear” triples after a linear change of variables. We prove the existence of this structure in two steps, as in [34]. The first step proves that the bracket form is “fixed”, “fixed”, “-dependent” and the second step then proves that the “-dependent” part in fact has a bracket linear structure. These steps will fall under the names sunflower and linearization respectively.
4.3. Degree-rank iteration
Once we have learned this refined form for , we iterate and then learn the refined form for the next highest degree-rank term , and then finally we learn the refined form for . Given these refined forms, Green, Tao, and Ziegler prove that the top degree terms in fact have the form of a multidegree nilsequence (in variables and ). Finally given such a correlation, a symmetrization argument as in [34] concludes the proof. We remark here that while terms such as and correspond to Taylor coefficients on the top degree horizontal torus, terms such as belong to the second horizontal torus, and to the third horizontal torus. Furthermore to handle terms of the form correctly we must realize such terms via a degree-rank nilmanifold, hence the need for the finer degree-rank notion.
4.4. Nilcharacters and horizontal tori
We now make this description more precise in terms of nilcharacters and horizontal tori. Let be a nilcharacter of degree-rank ; here should be thought of as an “almost” degree-rank nilcharacter and as an “almost” degree-rank nilcharacter. The sunflower step proves that the nilsequence can be realized as a bracket polynomial whose top degree-rank part is a sum of terms with iterated brackets where each term consists of -independent phases of , and possibly one -dependent phase of . Here, “phase” will correspond to components of the Taylor coefficients of , . This corresponds to showing that the -th horizontal torus contains vector spaces such that:
-
•
and ;
-
•
If , then whenever and there are at least two indices such that .
Here we have implicitly descended an iterated commutator to the vector spaces which corresponds to a multilinear form in this case. Such a result is proven via combining quantitative equidistribution theory of nilsequences [43, 42] with a “Furstenberg–Weiss argument” as in [32, 34, 43]; see [56] for further examples of the Furstenberg–Weiss argument.
The linearization step then proves that the remaining -dependent phases are “bracket linear” in . In practice, we require an additional case that the -dependent phase may be a petal phase: a top degree-rank term with the petal phase can be realized as a “lower order term”, or more precisely a bracket phase with at most iterated brackets or of total degree at most . Thus, the statement we ultimately prove is that we may decompose a subspace of the -th horizontal torus into the sum of three linearly disjoint vector spaces , , and such that:
and the projection of onto is bracket linear. In addition, we require that if , then whenever and either for at least one index or for at least two distinct indices . Thus even though we have not improved our understanding of the Taylor coefficients on we have the improved the vanishing of the top degree-rank commutator bracket on this vector space. The linearization step is proved by a combination of quantitative equidistribution theory of nilmanifolds [43, 42] and inverse sumset theory. We refer the reader to [43] for a simpler case of the argument given here.
4.5. Quantitative bounds
The heart of this paper is performing the sunflower and linearization steps efficiently. Green, Tao, and Ziegler [34] accomplish this (when unwinding the correspondence between nilmanifolds and bracket polynomials) via iteratively learning relations between the coefficients and performing a dimension reduction argument.111This is performed in [34, Section 10] via a “rank minimality” argument; this requires passing to an ultralimit. When performed in finitary language this becomes a dimension reduction argument and is also present in the proof of [34, Theorem D.5]. Furthermore, the underlying equidistribution theorem used in the work of Green, Tao, and Ziegler [34], proven in work of Green and Tao [29], relies on an induction on dimension argument. The use of any induction on dimension argument essentially immediately results in iterated logarithms and thus must be avoided.
The use of induction on dimension in the equidistribution theorem was avoided in work of the first author [43, 42]. The key point in Sections 8 and 9 therefore is to perform the sunflower and linearization steps without any use of induction on dimension. The precise details, while mainly utilizing elementary linear algebra, require a bit of precision. This argument, extending the case of the -inverse theorem from [43], demonstrates that a dimension-independent number of applications of equidistribution theory is sufficient to derive the necessary decrease in degree-rank. (Note that the argument in [34] morally uses that one can in fact assume that there are no “short linear relations” between various coefficients, but such a result necessitates exponential in dimension dependencies in the exponent.) Another crucial point in our work is that the length of the associated bracket linear form that is obtained not “very long”. This is, by now, a standard consequence of the quasi-polynomial bounds of Sanders [52] towards the polynomial Bogolyubov conjecture.
We finally remark that the quantitative equidistribution theorem we use is slightly different than the one derived in work of the first author [43, 42]. The work of the first author is most naturally phrased as factoring ill-distributed polynomial sequences into a smooth part, a rational part, and a polynomial sequence which (up to taking a certain quotient) lives in a lower step nilmanifold. For our purposes, it is critical to instead lower the degree of the nilmanifold. This is most easily seen from the above bracket polynomial example where we are attempting to linearize a function of the form
At this step we wish to linearize instead of handling the terms ; the term, while having the highest degree, does not correspond to the highest step part of the nilmanifold. This phenomenon only occurs when proving the -inverse theorem for . Thus a crucial ingredient in our work is bootstrapping, as a black box, the efficient version of equidistribution with respect to step in order to obtain an efficient version of equidistribution with respect to degree; this is Theorem 5.4.
4.6. Organization of the paper II
In Section 5 we prove the necessary quantitative equidistribution theorem with respect to degree. In Section 6, we perform the setup and give various definitions which will be used to perform the sunflower and linearization steps. In Section 7, we derive that many additive quadruples exhibit a bias. In Section 8 we perform the sunflower step while in Section 9 we perform the linearization step. In Sections 10 and 11 we then convert information regarding the Taylor coefficients into correlation with a multidegree nilsequence and a nilsequence of lower degree-rank. Iterating this argument we eventually obtain correlation with a mutltidegree nilsequence. In Section 12, we symmetrize this nilsequence to obtain Theorem 1.2.
Appendix A collects certain standard results regarding approximate homomorphisms (this is ultimately where work of Sanders [52] is invoked). In Appendix B, we collect a number of miscellaneous propositions which are deferred throughout the paper. Finally in Appendix C we collect a number of propositions regarding nilcharacters.
5. Efficient equidistribution theory of nilsequences
In order to state the primary equidistribution input of this paper we will need the notion of when an element in and a horizontal character are orthogonal.
Definition 5.1.
Consider a nilmanifold , a horizontal character , and . We say that and are orthogonal if .
The primary equidistribution input into our results will be the following result of the first author [42, Theorem 3]. This result is ultimately the driving force of this paper.
Theorem 5.2.
Fix an integer , , , and . Suppose that is a dimension , at most -step connected, simply connected nilpotent Lie group with a given degree filtration, and the nilmanifold is complexity at most with respect to this filtration. Let be a polynomial sequence on with respect to this filtration.
Furthermore suppose that and has -vertical frequency such that the height of is bounded by . Suppose that and
There exists an integer such that:
-
•
We have horizontal characters with heights bounded by ;
-
•
For all , we have
-
•
For any such that are orthogonal to all of , we have
Remark 5.3.
Remark.
Let . The crucial property of the lemma output is that
is trivially seen to be at most -step nilpotent. (Note that if is abelian then we have that is trivial.) This is due to the fact that defining and for yields and . Additionally, the statement in [42, Theorem 3] assumes is exactly -step nilpotent and is nonzero. In the case when is strictly less than -step nilpotent, taking no horizontal characters (i.e., ) gives the desired statement. Furthermore when is zero we may similarly take no horizontal characters and note that the final statement is vacuous.
The following variant of Theorem 5.2 will essentially be the primary equidistribution tool in our paper. For the sake of argumentation, we first prove the result in the case when the vertical frequency considered lives on a -dimensional torus and then bootstrap to the general case.
This theorem and its proof are motivated by [34, Lemma E.11]. The key point is that Theorem 5.2 allows us to give a procedure that relies on an induction on step rather than an induction on dimension. The main technical issue is at each stage we pass to a quotient group given by quotienting the kernel of a certain vertical character and thus we must iteratively “lift” these factorizations.
Theorem 5.4.
Let be an integer, , , and . Suppose that is dimension , is -step nilpotent with a given degree filtration, and the nilmanifold is complexity at most with respect to this filtration.
Suppose that is a -dimensional subgroup of the center which is -rational with respect to . Further suppose that has a nonzero -vertical character with , , , and is a polynomial sequence with respect to the degree filtration such that . Then if
there exists a factorization
such that:
-
•
;
-
•
lives in an -rational subgroup such that ;
-
•
is an -rational polynomial sequence;
-
•
is an -smooth polynomial sequence.
Proof.
The proof proceeds by iteratively “simplifying” to live on successively lower-step nilmanifolds. We treat as constant and allow implicit constants to depend on .
Step 1: Iteration setup. We will define a sequence of parameters and (where the domain of at stage will be ) satisfying:
During the iteration, we have a sequence of nilpotent Lie groups
such that is at most -step nilpotent with associated lattice and is complexity at most . This in particular will imply that there are at most stages in the iteration. We also maintain a sequence of subgroups
which are -rational subgroups of .
We will define homomorphisms , where is a -frequency (recall denotes the lower central series filtration of a group ). will be an appropriately rational subgroup of . We will always maintain the invariant that . We will furthermore maintain that the function has a -character given by descending on via .
We inductively maintain the following pair of relations:
-
•
;
-
•
;
where and are polynomial sequences living in and respectively.
The iteration terminates when . Before termination note that since is -dimensional. Note that this in particular ensures that before the termination of the iteration, is well-defined even though is not fully defined on the image of ! Using the invariant that we also have that (defined on ) naturally descends to . We define .
Furthermore at each stage of the iteration we have that
where:
-
•
and are polynomial sequences lying in ;
-
•
is a polynomial sequence lying in ;
-
•
is -rational;
-
•
is -smooth.
Finally, in each stage of the iteration we will maintain a function such that
Throughout the iterations, nilmanifolds at stage will have complexity bounded by , is -Lipschitz, and various horizontal and vertical characters constructed will have size and height bounded by . The starting conditions are , , , , , , , , (and ), and .
Step 2: Applying equidistribution. We now run a single step of the iteration. We have
By definition, we have that has a -frequency (a descent of ); this is not sufficient to apply Theorem 5.2. We perform an additional Fourier-analytic step to obtain a -vertical frequency. Since is -Lipschitz, via [42, Lemma A.6] we may write
such that
-
•
has -vertical frequency ;
-
•
;
-
•
is -Lipschitz on .
Given this representation, recall that has (appropriately descended) as a -vertical frequency. We abusively write this as . Therefore
where represents the Haar measure on . Thus may be decomposed into a sum of functions with -vertical characters up to an error of . Furthermore, each vertical character in question must agree with on . If not, then the corresponding integral in the second line will average to and we may remove it.
Applying Pigeonhole, there exists such that
(5.1) |
We have the following trichotomy:
-
•
is nonzero and ;
-
•
is nonzero and ;
-
•
in .
We define (in particular we let ). Let . We now apply Theorem 5.2 to (5.1), obtaining horizontal characters . Let their common kernel be and let . Note that in the case when is abelian, we do not necessarily have that are trivial on . However replacing by (and abusively referring to this as ), we may then replace by which instead cutout and note that may be taken to be -height integer combination of . We abusively rename these characters as and then proceed with the proof in this edge abelian case.
By applying [42, Lemma A.1], we obtain a factorization of into three nilsequences which are “smooth”, supported on a rational subgroup, and “rational”. We may change variables and then apply to obtain
where:
-
•
, and is at most -step nilpotent. Furthermore is trivially seen to be -rational with respect to ;
-
•
is an -rational polynomial sequence within ;
-
•
is -smooth.
We remark that changing variables is easily seen to not affect the smoothness and rationality in a substantial manner due to the bounds on . We can see that the step of decreases appropriately.
Step 3: Lifting the factorization data. Note that can be defined via a set of horizontal characters of such that
and we let . Note that the are the natural descentions of as we have are trivial on ; this is precisely why we earlier modified the characters in the abelian case.
We define
The trivial (but key) point is that . The key issue is noting that the map is well-defined; this is because by induction so that we are allowed to apply to any such values. We further see that because and is the subgroup of such that the image under is precisely in the intersection of kernels defining within .
Recall by induction that
and thus
Applying , we find that that there exists a nonzero integer such that
(5.2) |
We now claim that is a horizontal character on . It is a homomorphism since the are homomorphisms and it is well-defined by the above. In addition, we may inductively show that and . Hence , which verifies the property of being a horizontal character. That the horizontal character has appropriately bounded height is an immediate consequence of induction and the fact that .
Now we use this data to construct the required factorization. By applying [42, Lemma A.1] with the horizontal characters defined on with the hypotheses (5.2), we may write
where:
-
•
takes values in ;
-
•
and take values in ;
-
•
is an -rational polynomial sequence;
-
•
is -smooth.
Then denote the least common multiple of the periods of the different directions for ; note that such periods exist and we have by [42, Lemma B.14]. Divide into boxes of common difference . By Pigeonhole there exists such that
Note that
Since the differences we are considering are divisible by , there is such that
for all , where and . Since we have that
Step 4: Completing the induction. The first key polynomial sequence we shall define is
Note that is normal within and since we have that takes on values in as desired. Further let and ; these are trivially seen to lie in and have the necessary rationality and smoothness properties due to the above analysis.
We now break into a collection of boxes of length . There exists a box such that
Taking sufficiently small, we may replace the initial “smooth” polynomial sequence by where such that
The new function is given by descending from to (and later we may implicitly restrict to ). Explicitly, for we have
which is possible because has vertical frequency . Therefore we have
(5.3) |
We let
and we may replace with in (5.3).
We now check that , which is one of the invariants we are maintaining (we take ). We will have to distinguish between cases:
-
•
If is nonzero and note that . This is due to the fact that restricted to is (the descended version of) which is nonzero as given.
-
•
If is nonzero and then note that .
-
•
If then note that as (appropriately descended) was nonzero we have that is forced in this case. The result then follows as in the previous step.
Now, if then we continue with the iteration and do not terminate. If we have reached termination, we therefore have that . We claim that this implies that (and therefore we may take the output group to be ). For the sake of contradiction, instead suppose (since is -dimensional). Applying we have that
which contradicts the termination condition.
Finally, note that if then when viewed as a function on is seen to have a nonzero vertical character (which is given by descending on in through in the obvious manner), so one can continue in the iteration in this case.
Step 5: Fixing the value at . To see that this completes the proof, if the iteration terminates at some stage then note that
Using that the product of smooth sequences are appropriately smooth and analogously for rational sequences allows us to deduce the necessary outputs. However, we have not guaranteed that the values of the factorization are the at . For this, let with and . We then have that
As , we have that satisfies and is -rational. Thus
and note that takes value in the conjugated subgroup which is -rational by [42, Lemma B.15]. Note however that despite modifying the output group via conjugation, we have as desired. ∎
We now remove the assumption of a -dimensional vertical torus via a reduction to this case.
Corollary 5.5.
Let be an integer, , , and . Suppose that is dimension , is -step nilpotent with a given degree filtration, and the nilmanifold is complexity at most with respect to this filtration.
Suppose that is a subgroup of the center which is -rational. Further suppose that has a nonzero -vertical character with , , , and is a polynomial sequence with respect to the degree filtration. Then if
there exists a factorization
such that:
-
•
lives in an -rational subgroup such that ;
-
•
is an -rational polynomial sequence;
-
•
is an -smooth polynomial sequence.
Furthermore if then we may take .
Proof.
We first reduce to the case where as is standard. We factor such that and . Replacing by and by we may clearly reduce to the case where at the cost of replacing by which leaves the conclusion unchanged.
Using Lemma 3.10 to bound the complexity of and noting that descends to an -Lipschitz function on , by Theorem 5.4 we have that
where satisfy:
-
•
;
-
•
lives in an -rational subgroup such that ;
-
•
is an -rational polynomial sequence;
-
•
is an -smooth polynomial sequence.
We now “lift” this factorization. Consider the Mal’cev basis for . For each element we may lift to such that:
-
•
;
-
•
;
-
•
is an -rational combination of the elements of .
Writing as
where , we lift via the above mapping on to
where and analogously for .
We easily see that is an -smooth polynomial sequence, that is an -rational polynomial sequence, and that takes values in the subgroup . Furthermore is seen to be -rational and . Finally note that and analogously for . Therefore
as polynomial sequences. Thus
gives the desired factorization noting that and is central and therefore may be commuted to the right. ∎
6. Setup for Sunflower and Linearization Iteration
We now set up the iteration which will take up the bulk of the following four sections. The idea is to inductively assume the statement of Theorem 1.2 for (i.e., the quantitative inverse theorem for the -norm) and the remaining goal is to prove it for . The key step is to show that for many , correlates with a multidegree nilcharacter; this is a quantitative version of [34, Theorem 7.1]. For the remainder of the analysis until Section 12 we will be concerned with the notion of a correlation structure, which can be thought of as refining the notion in Definition 3.14 with intermediate bracket information.
Definition 6.1.
A correlation structure associated to the function with parameters , , , and and degree-rank is the following data:
-
•
A subset such that ;
-
•
A multidegree nilcharacter that lives on a nilmanifold where has a -vertical frequency . Furthermore has dimension bounded by and complexity bounded by , the function underlying is -Lipschitz, has height bounded by , and the output dimension of is bounded by . We let denote the underlying polynomial sequence of ;
-
•
A collection of degree-rank nilcharacters which live on where every has the same -vertical frequency . Furthermore has dimension bounded by and complexity bounded by (with Mal’cev basis ), the function underlying is -Lipschitz, has height bounded by , and has output dimension bounded by . We let denote the polynomial sequence underlying . Finally, the function underlying , which we will denote , is independent of ;
-
•
The polynomial sequences satisfy ;
-
•
For all we have
If the input function we are considering for the proof of Theorem 1.2 satisfies
then our proof will always maintain bounds of the form
on intermediate correlation structures, although the precise dependence may decay over roughly stages (wherein we reduce from to ).
To get started, we first note that given a function with large -norm we may associate to it a correlation structure of degree-rank ; this is little more than chasing definitions and applying induction.
Lemma 6.2.
Fix and . Assume Theorem 1.2 for . Let be a -bounded function such that
Then there exists a degree-rank correlation structure associated to with parameters , , , and such that
Proof.
Note that implies that
this implicitly uses that and that is identically zero for .
Therefore there exists with such that
for .
By induction on Theorem 1.2, we may assume that for all such there exists with degree filtration and an associated polynomial sequence such that
where has complexity bounded by and dimension bounded by . We may take
Note that via writing where and , we have that
Note that has and is appropriately Lipschitz (as has appropriately bounded coordinates by [42, Lemma B.2]). Therefore without loss we may assume that for all .
Next note that there are only nilmanifolds of dimension at most with degree filtration of complexity bounded by (up to isomorphism). This follows from Lie’s third theorem on the correspondence between Lie algebras and connected, simply connected Lie groups and counting the total possible number of different structure constants and filtration choices for the Lie algebra. Therefore by Pigeonhole we may assume, at the cost of decreasing the size of set by a multiplicative factor of , that (and the corresponding filtration) is independent of .
We next remove the dependence on for the function . Let be a parameter to be chosen later; by applying Lemma B.3 we may write
where , every is supported on at most many terms, and are -Lipschitz. Furthermore each is supported on a width cube near the origin (in Mal’cev coordinates); see the third item of Lemma B.3 for a precise description. Since is an -Lipschitz function, and choosing to be sufficiently small with respect to , we find that
by taking to be the mean of on the support of . Note that . Pigeonholing over and decreasing and the size of by appropriate factors of , we may assume that for all .
We finally want to replace by a nilcharacter with a vertical frequency and the claimed output dimension bound. We first give a degree-rank filtration induced by its degree filtration. This is done via [34, Example 6.11] (i.e., is generated by iterated commutators which either have filtration depths adding to greater than or adding to exactly with at least participating elements). Lemma 2.1 guarantees each subgroup is -rational. Via [42, Lemma B.11], we may give a Mal’cev basis adapted to this degree-rank filtration with complexity .
Via Fourier expansion (see [42, Lemma A.6]) and the triangle inequality we may additionally assume that has a vertical -frequency 222We apply [42, Lemma A.6] to the degree filtration . with height at most . Given , there exists a nilcharacter by Lemma B.4 with vertical frequency , output dimension bounded by , and such that each coordinate is -Lipschitz. The function demonstrates that without loss of generality, we may assume is a coordinate of a nilcharacter.
To complete the deduction, we take to be the trivial nilmanifold and to be a constant sequence. ∎
The heart of this paper is the following quantification of [34, Theorem 7.2], the proof of which is the goal of the next few sections culminating in Section 11.2.
Lemma 6.3.
Fix and . Suppose is a -bounded function and .
Furthermore suppose that there exists a degree-rank correlation structure associated to with parameters , , , and . Then there exists a degree-rank correlation structure associated to with parameters , , , and such that
Combining Lemma 6.3 along with the observation that degree-rank nilmanifolds induce a degree filtration (coming from the groups ), we immediately obtain the following. In particular, these can now be “hidden” inside the nilmanifolds implicit in .
Theorem 6.4.
Fix and . Assume Theorem 1.2 for . Let be a -bounded function such that
Then the following data exists:
-
•
A subset of size at least ;
-
•
A multidegree nilcharacter which lives on a nilmanifold where has a -vertical frequency . Furthermore has dimension bounded by and complexity bounded by , the function underlying is -Lipschitz, has height bounded by , and the output dimension of is bounded by ;
-
•
For all we have that
Furthermore, we can find such data satisfying
Remark.
The case when is small (i.e., ) is handled via noting that for many and then applying Fourier analysis. Such an analysis always loses factors of and thus is only useful in this crude edge case. We will not comment further on such issues.
7. On a Cauchy–Schwarz Argument of Gowers
The proof of Lemma 6.3 is performed in a sequence of stages. We first deduce that the functions correlating with are not arbitrary. Indeed for many additive quadruples we have that the associated tensor product of exhibits correlation with a degree nilsequence.
We first need the following elementary Fourier-analytic lemma which converts correlation on long progressions to correlation with a major-arc Fourier phase; this is essentially [32, Lemma 3.5(ii)].
Lemma 7.1.
Let . Suppose that is -bounded and there exists an arithmetic progression of length with common difference within such that
Then there exists such that and
Proof.
Extend to be zero beyond the interval . Let be the arithmetic progression of length with common difference centered at . We have
Via Fourier inversion, we have
Now via standard bounds on linear exponential sums, we have
Since , we have that
Therefore, taking sufficiently large we have that
Thus
which is exactly the desired conclusion (recalling that ). ∎
The following lemma is due ultimately to Gowers but essentially appears as [32, Proposition 6.1]. We include the proof for the sake of completeness.
Lemma 7.2.
Suppose , are -bounded, and are all -bounded. Suppose that
Then there exists such that and
Proof.
Note that we assume that for and that for via replacing with ; we will remove this truncation at the end of the argument. We extend these functions by to where is a prime between and .
By Cauchy–Schwarz, we have
Expanding, this is equivalent to
We set , , and and find that
This implies that
Recall the box-norm inequality that for which are -bounded, we have
(7.1) |
Applying this for each fixed , we have that
Take , , , . Note that and and noting that and range over the whole cyclic group, this is exactly
Since identically for , we in fact have
For the inner sum, recall that we “truncated” with . In particular, extracting the truncation term we have that
Via an application of Lemma 7.1, there exist choices of with such that
Rounding to a lattice of spacing and Pigeonholing then gives the desired result. ∎
The next proof will require defining the notion when two nilcharacters are “equivalent” (i.e., have the same symbol in a quantified sense of [34, Appendix E]).
Definition 7.3.
We say nilcharacters are -equivalent for multidegree if have output dimensions bounded by and all coordinates of
can be represented as sums of at most nilsequences of multidegree such that the underlying functions of each nilsequence are -Lipschitz and the underlying nilmanifolds have complexity bounded by and dimension bounded by .
The key reason for the definition of equivalence is the following proposition, which states that given equivalent nilcharacters and , correlations with them are equivalent modulo introducing a term of multidegree . This is a finitary quantification of [34, Lemma E.7].
Lemma 7.4.
Given a function and nilcharacters which are -equivalent for multidegree , if
then
where can be taken to be one of the nilsequences used as part of a represention of one of the coordinates in . In particular, is a nilsequence of multidegree such that underlying nilmanifold has complexity bounded by and dimension bounded by and the underlying function has Lipschitz constant bounded by .
Remark.
The additional condition that can be taken to be an explicit nilsequence occurring in a witness for the equivalence of is used primarily to allow us to Pigeonhole the choice of in cases where we may need to apply this statement “on average”.
Proof.
Notice that since is a nilcharacter, we have that the trace of
is the constant function . Furthermore note that the trace is the sum of at most coordinates of and therefore
Consider the coordinate of which achieves the above, and in particular the associated coordinate of that contributes. Applying the definition of equivalence and the triangle inequality, there exists of the desired form such that
We are now in position to prove the quantification of [34, Proposition 7.3]. We remark that there was an error in the published version of [34, Proposition 8.3] which affected the proof of [34, Proposition 7.3]. We quantify a closely related approach to that given in the erratum [31]. For our proof we require various quantifications of [34, Appendix E]; all of these are completely mechanical.
Lemma 7.5.
Fix and . Let is a -bounded function. Suppose that has a correlation structure with parameters , , , and and associated nilcharacters and . Then for at least quadruples with we have
with
Remark 7.6.
For , the same statement holds modulo a correction term of where is such that .
Proof.
By definition of correlation structures we have for that
where is a nilsequence of degree whose underlying function is at most -Lipschitz on a nilmanifold of complexity at most and dimension at most . Setting to be zero for we have
Twisting by an appropriate -dependent constant complex phase so as to make the values be realized as positive real numbers, we may assume that
By Lemma C.5, we have that is -equivalent for degree to some which is a multidegree nilcharacter with output dimension, complexity of underlying nilmanifold, Lipschitz constant of underlying function for each coordinate, and vertical frequency height all bounded by . ( has total arguments.) Thus, applying Lemma 7.4, we have that
where is a degree nilsequence where the underlying function has Lipschitz norm and complexity of underlying nilmanifold bounded while the dimension of the underlying nilmanifold is bounded by . The nilsequence can also be viewed as a multidegree nilsequence. (I.e., we take the union of the down-sets generated by these elements.) Furthermore, the underlying function has Lipschitz norm and complexity of underlying nilmanifold bounded while the dimension of the underlying nilmanifold is bounded by .
Thus, applying Lemma C.6 (splitting) we have
where are degree nilsequences in where complexity and Lipschitz constant are bounded by and the dimension of the underlying nilmanifold is bounded by while is -bounded. Therefore, applying Lemma 7.2, we have
We may combine to form which is degree in and with identical complexity bounds to modulo changing implicit constant. Additionally, we may twist by an -dependent complex phase to bring the outer expectation inside the norm. Thus we have
By Lemma C.5, is -equivalent for degree to
where there are copies of and copies of and we have a similar expansion for . Note that all terms in this expansion except for may be absorbed into . Therefore applying Lemma 7.4, we have that
here is a degree nilsequence where the underlying function has Lipschitz norm and complexity of underlying nilmanifold bounded by while the dimension of the underlying nilmanifold is bounded by and we have folded certain terms into while guaranteeing it is a degree nilsequence (and the complexity bounds have not changed modulo implicit constants). Finally via Lemma C.5, we have that
and are -equivalent for degree . Thus applying Lemma 7.4, we have
here we have folded in various terms into and the complexity bounds have not changed modulo implicit constants. Note that by Lemma C.2, is a degree nilsequence in and thus may abusively also be absorbed into . Finally noting that a degree nilsequence may also be viewed as a multidegree nilsequence and thus applying Lemma C.6 we have
where is an -bounded function and has been modified but the underlying complexity bounds have not changed modulo implicit constants. Note is degree .
We now reparameterize with
By approximating with regions where we take to live in short intervals, there exist intervals each of density in such that
where is a degree nilsequence. Now by Cauchy–Schwarz, duplicating the variable and denoting the copies by , we obtain
Note that every term not involving was removed using appropriate boundedness. Now we may Pigeonhole on and deduce
Let , , , and (abusively). We have
where is a degree nilsequence (for each fixed ) where the underlying nilmanifold and Lipschitz constant of underlying function are bounded by and the dimension is bounded by .
Therefore, by the triangle inequality we have that
Finally, the last term is the indicator of an -dependent interval. Applying Lemma 7.1 (and noting that allows us to fold in the major arc Fourier term) completes the proof. ∎
8. Sunflower Step
For the next stage of our proof, as outlined in Section 4, we wish to provide more structure on -dependent nilcharacters given information about additive quadruples as established in Section 7. As setup we will require the notion of a rational subspace with respect to a specified basis, and establish some basic control over Taylor coefficients of bounded polynomial sequences.
Definition 8.1.
A vector subspace is -rational with respect to given the basis (of ) if there exists a basis of such that each is a linear combination of elements of with coefficients of height at most .
Lemma 8.2.
Consider a nilmanifold given a degree-rank filtration of degree rank , dimension , and complexity at most . Let denote the underlying adapted Mal’cev basis and assign the basis
for . Suppose is a polynomial sequence such that
for . Then for , we have
Proof.
We may write
where . By Lemma 2.12, we have
We have that
for all by [42, Lemmas B.1, B.3]. This implies that
This is exactly the -th discrete derivative and thus terms coming from with vanish. This implies that
where the basis we assign to is . The result follows by dividing by and noting, by say [45, Lemma 2.6], that the distance in first- and second-kind coordinates is comparable. ∎
We now come to the first of two crucial arguments in this paper where we “improve” the correlation structure. At the cost of restricting the set , we force the Taylor coefficients of , the polynomial sequences underlying the , to live in certain restricted subspaces and their differences to lie in an even finer restriction.
This step is closely related to the “sunflower” arguments of [32, Step 1] and [34, Lemma 11.3]; a quantitative version for the -inverse theorem due to the first author can be found in [43]. The precise statement of the lemma should also be compared with [34, Theorem 11.1(i)]. We note however that unlike [32, 34], our proof is completely free of any iteration (or equivalently passing to a subgroup where polynomial sequences are “totally equidistributed”, which necessitates too much loss in the relevant parameters).
Thus, the crucial point of the following technical statement is the final condition, which essentially captures that two -dependent frequencies in the improved correlation structure cannot “simultaneouly” affect the bottom degree-rank portion.
Lemma 8.3.
Fix and . Let be a -bounded function. Suppose that has a degree-rank correlation structure with parameters , , , and and that and data labeled as in Definition 6.1. Furthermore let .
We output a new degree-rank correlation structure for with parameters
with set , with multidegree nilcharacter on , with -dependent nilcharacters having underlying polynomial sequences on . This correlation structure satisfies:
-
•
is given the multidegree filtration
if or . For we set
We have . We have for some appropriate value of ;
-
•
There exists a collection of -vector spaces which are all -rational with respect to for each ;
-
•
For and we have
-
•
is -Lipschitz and has the same vertical frequency as ;
-
•
For integers , suppose that and for at least two distinct indices we have and . Then for which is any -fold commutator of , we have
Remark.
Consider with for and . Fixing any -fold commutator of , repeated application of the commutator version of Baker–Campbell–Hausdorff (e.g. (2.2)) implies that
where the associated commutator has the same “form” as that defining . (All higher terms are annihilated since has degree-rank .) Note that this implies that one can define the associated commutator given inputs in and furthermore we see that the associated commutator form on the Lie algebra is a multilinear form of the vector arguments (since and are real vector spaces and the commutator bracket on the Lie algebra is multilinear).
Proof.
We first note that the statement of the lemma is trivial for since we may take ; it is impossible to have two distinct indices in the final bullet point. Taking and completes the proof in this case. For , the only possible case is and therefore for the remainder of the proof we will consider . Similarly, if is trivial, the result is once again immediate. Thus throughout the remainder of the proof we will assume that and is nontrivial.
Step 1: Setup for invoking equidistribution theory. By Lemma 7.5, we have
for at least fraction of additive quadruples . Furthermore is a polynomial sequence on a group which has a degree filtration, dimension bounded by , and the complexity of and the Lipschitz constant of the function for are bounded by . Note that a priori and the associated Mal’cev basis depend on . However, applying Pigeonhole on the choice of the associated structure constants allows us to assume, at the cost of passing to a density subset of the additive quadruples, that is independent of . Finally, we may assume as usual that via by-now standard manipulations.
We now consider the group . may naturally be given a degree-rank product filtration (where we use [34, Example 6.11] to assign a degree-rank structure) and Mal’cev basis. Furthermore if we have that the five-fold function has a vertical frequency . (Note that for all .)
For the sake of convenience, we set
and note that the function is seen to be -Lipschitz on . Note that by the second item of Lemma 2.13, we immediately have that
for and analogously for .
Step 2: Invoking equidistribution theory. By applying Corollary 5.5 (since is nonzero), there exists a -rational subgroup of such that and such that
where:
-
•
;
-
•
takes values in ;
-
•
is -rational (with respect to the lattice );
-
•
for .
By passing to a subset of additive quadruples of density we may in fact assume that the group is independent of under consideration.
We define
where is the natural projection map to the four-fold product. Since (due to the output of Corollary 5.5), we have
for where the commutator bracket is taken with respect to and denotes any possible -fold commutator bracket.
Since has been given a degree-rank filtration, we have that in fact
where we abusively descend to . Less formally, we are noting that the final coordinate of elements in play no role in commutators of the depth being considered.
Step 3: Furstenberg–Weiss commutator argument. We now perform the crucial Furstenberg–Weiss commutator argument. Given , we define with the coordinates represented in increasing order of index.
We define
Note that and may (abusively) be viewed as subspaces of . The crucial claim is that
if , each , and for two distinct indices we have that and . Note that lives on and the commutator brackets are taken with respect to , not . The Furstenberg–Weiss commutator argument is required to capture precisely this difference.
Note that an element lifts to an element of the form . Furthermore note that “lifts” to an element of the form while lifts to an element of the form .
Given the above setup, we have
To see this note that the iterated commutator of elements in (with any elements in ) remains in the subgroup ; an analogous fact holds true for . Since we assumed that our commutator contains elements in both and , the commutator must in fact live in , and the first coordinates of the desired commutators is trivially seen to match.
Recalling that we have
and noting that descends to on the subgroup , we have
as claimed.
Step 4: Finding and which extend to many “good” . Recall that we are looking at the at least fraction of additive quadruples which are such that lives on a specified subgroup . Call this set of quadruples .
So by Markov, there are at least many which extend to at least quadruples in . Thus there are at least pairs of additive tuples of the form
By averaging, there exists a pair of pairs and such that there are at least many which live in such additive tuples. We fix such a pair of pairs and define to denote the set of such that and .
Step 5: Extracting coefficient data. Consider and define
Recall and assign the basis to (viewed as a vector space). Finally we assign the basis to .
By Lemma 2.13, we have
Therefore, by Lemma 8.2, for all we have
where and are positive integers bounded by . Here we have identified the basis (for ) with the standard basis vectors in and taken the metric on the latter (for the notion of ). At the cost of shrinking the set by a multiplicative factor of we may assume that and for all .
We now consider a basis for which is in row-echelon form where one orders the coordinates corresponding to second copy of (in the four-fold ) at the front, then the third copy, and then the first copy. In particular, the “final block” of basis vectors span . Note that one can take such such that the coordinates are integers bounded by due to the rationality of .
For , we have
(8.1) | ||||
(8.2) |
where . For each basis vector where the first nonzero element is either in coordinates corresponding to second or third copy of , there exists a dual vector which is zero on the coordinates corresponding to the first copy of and whose inner product with all of but is zero.
Call this vector and note one may take to have integral coordinates bounded by and divisible by . Then from (8.1) and (8.2),
where is an nonzero integer bounded by . (That is, is within of an integer.)
We may now use this information about such indices in conjunction with (8.1) and (8.2). We deduce that for all ,
where is an integer of size bounded by . Analogously,
where is an integer bounded by . Putting it together, we may deduce that
with a nonzero integer bounded by . To see this, simply construct a bounded integral basis of the orthogonal complement of (treated as a subspace of the dual space to ). Then the two input inequalities imply that any basis vector for the intersection space dual will map to a near-integral scalar, which gives the claim.
Now by Lemma 2.13 we therefore have
(8.3) |
It is also trivial by restricting the factorization to the first coordinate that
(8.4) |
with a nonzero integer bounded by .
Step 6: Extracting initial factorizations. For the remainder of the proof fix . Given we have
Note that and may each be defined as the kernel of a set of -th horizontal characters (on ) of height at most . Recall (8.3) and (8.4). Scaling the horizontal characters by at most and applying Lemma B.2, we may write
where:
-
•
;
-
•
and ;
-
•
are -rational;
-
•
for .
Therefore
By Lemma 2.13, we have
We say that have matching rational parts if
is a polynomial sequence valued in . By restricting to an appropriate subset of density , we may assume that all have matching rational parts. (This is most easily seen in first-kind coordinates: if and have all coefficients differing by where is an appropriate integer of size bounded by then two sequences match up to a polynomial sequence in .)
So, ultimately we may assume that for all we have
where:
-
•
;
-
•
and for all ;
-
•
is -rational
-
•
takes values in ;
-
•
for .
Step 7: Removing periodic and smooth pieces of factorization. Let be the period of and define where is to be chosen later. We break into a collection of arithmetic progressions with difference and length between and ; there are at most such progressions. Call these progressions and note that
where is the degree nilsequence coming from the condition from the original correlation structure. For we may write
here we are using that takes values in so may be dropped for the remainder of the analysis.
Since is the period of , we may replace by a value for each progression where for and . Then
Furthermore as is sufficiently smooth we may replace with the constant and have
as long as was chosen sufficiently small.
By the triangle inequality there exists some which is distance at least from the ends of the interval such that
By paying a -fraction in the size of we may assume that the choice of index is independent of , hence writing . Furthermore note that there is a -net of size for the set of satisfying . If the net size is chosen small enough, we may shift to a nearby value in the net without much loss. Then we can pay a -fraction in the size of to Pigeonhole onto a single point in the net, writing .
Overall, for all we have
for some at least from the endpoints of the interval. Thus by Lemma 7.1, for each there exists with and
(8.5) |
Rounding to a net of distance and paying a -fraction in the size of to Pigeonhole the resulting point, we may write for all . We are now finally in position to define the output data. Define
Note that is the polynomial sequence underlying , and . It is easy to check the relevant properties of Definition 6.1 to see that we obtain a degree-rank correlation structure with appropriately modified underlying parameters (we set to be the final refined version of ); in particular, (8.5) demonstrates the necessary correlation fact.
Finally, taking
we finish the proof: in particular, the result from Step 3 demonstrates the final item of the conclusion, and the result from Step 6 demonstrates the third item. ∎
9. Linearization Step
We now come to the second crucial argument of this paper. Prior this stage we have modified the degree-rank to one in which various Taylor coefficients of for (upon factoring) differ only on certain special subspaces. In this next stage, we deduce that either these Taylor coefficients differ on a further refined subspace which is seen to be essentially “annhilated” by or has a certain “bracket linear” form. This step is ultimately where we invoke the results of Sanders [52] on quasi-polynomial bounds for the Bogolyubov lemma.
This step is closely modeled after [32, Step 2] and the closely related proof of [34, Lemma 11.5]; a quantitative version for the -inverse theorem due to the first author can be found in [43]. The precise statement of the lemma should also be compared with [34, Theorem 11.1(ii)].
Lemma 9.1.
Fix and . Let be a -bounded function. Suppose that has a degree rank correlation structure with parameters , , , and and that . Furthermore let .
We output a new degree-rank correlation structure for with parameters
with set , with multidegree nilcharacter on , with -dependent nilcharacters having underlying polynomial sequences on . This correlation structure satisfies:
-
•
is given the multidegree filtration
if or . For , we set
We have . We have for some appropriate value of ;
-
•
There is a collection of -vector spaces for each ;
-
•
If then , i.e., the three spaces are linearly disjoint;
-
•
There exist bases , , and of the corresponding spaces which are composed of -rational combinations of elements of ;
-
•
For and we have
with and where is a prime in ;
-
•
is -Lipschitz and has the same vertical frequency as ;
-
•
For any integers , suppose that for all . If for at least one index we have , then if is any -fold commutator of we have
Furthermore, if instead for at least two indices we have and , then if is any -fold commutator of we have
Remark.
The projection map is well-defined due to the linear disjointness condition. Furthermore we have written Taylor coefficients with additive notation, since can be identified with .
Proof.
For the majority of the proof we will assume ; we indicate the minor changes required for for the end of the proof (and the case is not used in the proof of Theorem 1.2). Note that the case when is trivial follows via taking , and to be trivial, , and ; therefore we may assume that is nontrivial for the remainder of the proof.
Step 1: Applying Lemma 8.3 and linear-algebraic setup. We apply Lemma 8.3 and treat the resulting correlation structure as the input to the lemma. Up to changing implicit constants in the output this leaves the lemma unchanged except for noting that
which is defined on the group . In particular, we will abusively overwrite notation and relabel the resulting from the application of Lemma 8.3 as , as , and as and thus assume the output properties without further comment.
It will also be crucial to define certain linear-algebraic operators of . Consider a basis for , an extension to a basis of , and then to such that all basis elements are -rational combinations of the basis . In particular, write
Given , there is a unique linear combination
We define
By construction , , , and for . We also (abusively) extend the operator to and in the obvious manners by acting on each copy of separately (and zeroing out basis elements ).
Step 2: Invoking equidistribution theory. Applying Lemma 7.5 when , we have
for a density of additive tuples. We define , , and as in the proof of Lemma 8.3 and as before we may assume that . Define
By applying Corollary 5.5, we have
with
-
•
;
-
•
takes values in ;
-
•
is -rational;
-
•
for .
where and is a -rational subgroup of . By passing to a subset of additive quadruples of density we may in fact assume that the group is independent of under consideration.
Step 3: Linear algebra deductions from equidistribution theory. Note that at present the subgroup does not account for the deductions given in Lemma 8.3; these initial deductions are designed essentially to account for this. Let be the natural projection to the four-fold product. We define the following set of vector spaces:
By inspection, we have hence . Note that
whenever one has that and denotes any possible -fold commutator bracket. This is a consequence of the fact that and noting that . Note that we are implicitly using that is trivial on as well, and we abusively descend to .
We now claim that
if for all and there is at least one index such that .
To prove this, note by the final bullet point of Lemma 8.3 and multilinearity that
The first equality uses that every bracket with at least two has two terms so is , the second equality uses , and the third equality follows by noting that
and . Now, we may ultimately deduce
because and .
Finally, let for is as in the proof of Lemma 8.3 (namely, an appropriate projection map). We have
This follows because if
then
Step 4: Constructing a decomposition of . We will now decompose into a pair of subspaces. On one of these subspaces we will deduce an improved vanishing for the commutator while on the other subspace we will deduce an approximate linearity for . Let
Note that may abusively be viewed as a subspace of (instead of ) and under this identification .
The key claim in our analysis is if , for all indices , and for at least one index we have
To prove this, note that and and using the last bullet point of Lemma 8.3, we have
similar to the argument in Step 3.
Next note that for all and therefore
Therefore we may lift for to where . We lift to which has the form .
Note that we have
where in the first equality we have used for all that and the result from Step 3, in the second equality that has the final three coordinates identically zero, and in the final equality that and the final item of Lemma 8.3.
The desired decomposition of spaces for the lemma will have
The fact is deduced from . will be constructed explicitly in the next step but is chosen so that
and . Given these properties of , note that the above analysis, along with Lemma 8.3, establishes the final bullet point for our output.
Step 5: Controlling approximate homomorphisms. Recall and there is a natural isomorphism of groups
Using this as an identification, we may write
where and (i.e., corresponding dual vector spaces). Note that the annihilators all have the special form of since
Note that
since is equivalent under this identification to . Without loss of generality we may assume that for , vectors are independent in (and they must span the orthogonal space to within ).
By appropriate scaling, we may assume is an integer bounded by for . We extend each to an operator on by setting for . Possibly at the cost of another scaling, we may assume that . We extend in an analogous manner to by setting for and . Again, we may scale such that . The crucial point here is that now and are -th horizontal characters of height at most .
We have
and thus
after Pigeonholing appropriately. Here distance is in after expressing both of these expressions in the basis and is an integer bounded by . We have used Lemma 2.13 and the properties of the original factorization; a very similar argument appears in Step 5 of the proof of Lemma 8.3.
Furthermore note that
by Lemma 8.3. So if we choose a set of horizontal characters of height relative to which cut out as their common kernel, then noting that and applying Lemma B.2 we may assume that
(9.1) |
and have identical properties up to changing implicit constants. We will assume this refined property of the factorization for the remainder of our analysis.
Given the factorization of , we thus deduce (taking an appropriate least common multiple)
(9.2) |
for all where is an integer bounded by . Here we have used that is equal for all by Lemma 8.3.
We define functions via
Note that for the additive quadruples on which we have (9.2), we are exactly in the situation necessary to apply results on approximate homomorphisms.
In particular, we may apply Lemma A.1. We see that there exists having density at least such that for all and , we have
(9.3) |
where:
-
•
;
-
•
where is a prime between and .
At this point, for each we find elements for which are -rational combinations of such that
(9.4) |
for such that . We define
We see that there are no nontrivial linear relations between and since and . There are no linear relations between and as lies in the joint kernel of the and therefore using (9.4) one can prove any such relation is trivial. Furthermore, by construction we have . Finally ; this implicitly uses .
Step 6: Constructing the desired factorizations and completing the proof. Using the refined factorization (9.1) implies that
since . Applying in the first coordinate then implies that
(9.5) |
for where distance is in after expressing values in terms of . Here is an integer bounded by . Furthermore recall from Lemma 8.3 that
(9.6) |
for .
Let be such that . Then for , we define
(9.7) |
By construction and Lemma 2.13, for we have
where and . The first line comes from (9.6), the second line from (9.5), and the third from (9.3) and (9.7), in conjunction with (9.4).
We now fix an element . For each we write
By applying Lemma B.2, we may write
where are -rational, are -smooth, and we have using the first and third lines above and using the second and third lines above. (Recall that is cut out by the .) Additionally, these sequences are the identity at .
Therefore, for we have
So, for we deduce using Lemma 2.13 and the above analysis that
Furthermore note that is sufficiently smooth and is appropriately rational. This nearly gives the desired result except we need to remove the rational and smooth parts exactly as in Step 7 of Lemma 8.3; we omit the details, although note that the only difference between and the output is a conjugation by a fixed element which leaves all properties unchanged and the Fourier phase on the part of may be modified. Additionally, the set will be made smaller by acceptable factors due to Pigeonhole.
Step 7: Handling the exceptional case . In this exceptional case, we have and , and is nontrivial. The difference here versus the prior analysis is that the error term is replaced by with by using the Remark 7.6 regarding Lemma 7.5 for .
We take , , , and . is defined as before. Taking , by Corollary 5.5 we may factor
where is -smooth, is -rational, and lies in a -rational subgroup such that . Note however that
where is the natural projection. Let and note that can be defined as the joint kernel of certain horizontal characters of height (namely, ones defining along with one of the form ). Since is small and is the only part in the fifth coordinate, arguments similar to before allow us to refine the first factorization (up to changing implicit constants) and instead assume that lies in .
Furthermore note that if we have that as and agree on the initial four groups. At this point we are exactly in the situation of the earlier analysis and we may complete the proof.333Various simplifications are possible in the case since the underlying groups are all abelian here; in particular, invoking Corollary 5.5 reduces to summing a geometric series. ∎
We remark that modulo minor annoyances, the strategy of using Lemma 7.5, deducing an approximate homomorphism, and then applying results coming from the Bogolyubov lemma was introduced by Gowers [16] in his seminal work on four-term arithmetic progressions. It was similarly applied in work of Green and Tao [23] on the -inverse theorem. In a certain sense, the previous two sections can be thought of as showing that, given an appropriate equidistribution theorem and defining a number of notions for nilmanifolds, this analysis can be modified to make sense in the greater generality of nilmanifolds where the group is not abelian.
10. Setup for extracting a -nilsequence
Before diving into the formal proof, we motivate how we extract the “top degree-rank” part and why lifting to the universal nilmanifold plays a role in our argument at this stage. We remark that Green, Tao, and Ziegler [34] work with the universal nilmanifold throughout their argument (in the form of a representation of a degree-rank nilcharacter; see [34, Definition 9.11]).
Recall the bracket polynomial -inverse sketch discussed in Section 4; we started with functions
which correlate with . At this point, we have proven that
is equivalent to a bracket polynomial up to lower order terms of degree-rank of the form
Our goal at this stage is to isolate
in the next section we will then convert this “top degree–rank” bracket phase into a –nilsequence.
The reason lifting to a universal nilmanifold proves so technically useful is that it enables us to isolate various components of the horizontal tori as “separate subgroups”. For the sake of simplicity, consider a -step group in the -inverse case given the degree-rank filtration , , where the remaining groups are trivial. In this case, the output of Lemma 9.1 gives the linearly disjoint subspaces , , of such that the commutator of any two elements in vanishes and the commutator of any element of and vanishes.
Let denote the rational basis of and and be analogous. We also have a decomposition of our polynomial
where
Therefore we may write
with pointwise. The top order term which we seek to isolate is heuristically similar to
Note that given the factorization of , we have established no control over and . This may suggest that we wish to quotient out by the subgroup in order to kill these terms; note however that now abelian and such a projection “kills” the higher order degree-rank term calculated above. This suggest that the group is “too large” a quotient. The solution is to “enlarge” the group so that the subgroup and the subgroup that corresponds to the remaining phases are disjoint. We can then quotient by . This disjointness is accomplished by lifting to the universal nilmanifold of degree-rank .
10.1. Unwinding the output of Lemma 9.1
We first require the following elementary lemma regarding lattice elements when presented in first-kind coordinates.
Lemma 10.1.
Fix an integer . Consider a nilmanifold of dimension with a Mal’cev basis of which is -rational and such that has the degree nesting property. Then there exists a positive integer such that if then
Proof.
Note that . By [42, Lemma B.1], is a degree polynomial with coefficients of height at most . The desired result then follows by taking to the least common multiple of all denominators of all coefficients present in this polynomial (since there are only total coefficients). Note that the polynomial corresponding to has no constant term by observing the image of . ∎
We next require the following additional elementary lemma which gives a Taylor series expansion which is “graded by the Mal’cev basis”.
Lemma 10.2.
Consider a nilmanifold of degree with an adapted Mal’cev basis and a polynomial sequence . There exists a representation
where .
Proof.
Note via Baker–Campbell–Hausdorff and existence of Taylor expansions, we may write
with . Let and . Then iteratively define by the following process: write . Then let
and write
in order to define . There exists a valid choice of at each step since is a filtered Mal’cev basis and there exists a valid choice of for by Baker–Campbell–Hausdorff. This process terminates with the identity sequence, and unraveling gives the desired. ∎
Remark.
Note that in the above proof, the reason we do not use the basis is that is not a linear combination of polynomials of the form for and hence the Baker–Campbell–Hausdorff to construct fails (one needs lower-degree terms with ).
We now explicitly unwind, for the sake of clarity, the conclusion of Lemma 9.1. We will use the notation and conclusions here throughout the Sections 10 and 11. Suppose we have a -bounded function with a degree-rank correlation structure with parameters .444We apologize to the reader; there is a rather incredible amount of data which is floating around at this point. The crucial details to track are data regarding Taylor coefficient and the associated decompositions of the vector spaces corresponding to horizontal tori. Then by Lemma 9.1 and some relabeling there exists a degree-rank correlation structure with parameters
and
-
•
A subset with ;
-
•
A multidegree nilcharacter with a frequency with height at most . Furthermore lives on a nilmanifold with dimension bounded by , output dimension bounded by , complexity bounded by by , and the function underlying is -Lipschitz. We let denote the underlying polynomial sequence;
-
•
A collection of degree-rank nilcharacters with a frequency with of height at most . Furthermore lives on a nilmanifold with dimension bounded by , output dimension bounded by , has complexity bounded by and the function underlying (which is independent of ) is -Lipschitz. We let denote the underlying polynomial sequence and we have ;
-
•
For all , we have
-
•
Then there exists a collection of subspaces for which are -rational with respect to ;
-
•
If then ;
-
•
Let a sequence of integral linear combinations of such that . We may let the coefficients of be -bounded and .
-
•
Let be a sequence of integral linear combinations of such that . We may let the coefficients of are -bounded and .
-
•
Let be a sequence of integral linear combinations of such that . We may let the coefficients of be -bounded and let .
-
•
For and , we have
where
where and where is a prime in .
-
•
For any integers , suppose that for all . If for at least one index we have , then if is any -fold commutator of , we have
Furthermore, if instead for at least two indices we have and , then if which is any -fold commutator of we have
We have relabeled as by , by , by , by , and by . We have applied Lemma 10.1 and scaling to guarantee that .
Let denote the filtered Mal’cev basis given for . Via Lemma 10.2, for we may define
and define via
Using Lemma 10.2 again, we may write
The fact that when applying Lemma 10.2 for we observe no coefficients for corresponding to basis elements in follows from the fact that and have Taylor coefficients which match exactly for .
We now reach the first stage of “rewriting” where we realize the nilsequence on a universal nilmanifold.
10.2. Rewriting degree-rank nilsequences on the universal nilmanifold
We recall the universal nilmanifold of a given degree-rank (see [34, Definition 9.1]).
Definition 10.3.
The universal nilmanifold of degree-rank and the associated discrete cocompact subgroup are defined as follows. We write where with . We specify by formal generators of the Lie algebra for and where with the relations:
-
•
Any -fold commutator of with vanishes;
-
•
Any -fold commutator of with and vanishes.
The associated discrete group which we will be concerned with is which is the discrete group generated by for and .
Remark.
Note that in this definition, depends only on ; however, the quotient we will consider later depends on . Furthermore, we have presented as a Lie algebra and not as a Lie group; via the general theory of nilpotent Lie algebras this is sufficient. Note that the Lie algebra defined is trivially seen to be nilpotent. By the Birkhoff Embedding Theorem (see remark following [12, Theorem 1.1.11]), we may realize any real nilpotent Lie algebra as a Lie subalgebra of the real strictly upper triangular matrices. The proof of [12, Theorem 1.2.1] then realizes the real strictly upper triangular matrices as a logarithm of a connected, simply connected Lie group where the exponential map is bijective. The Baker–Campbell–Hausdorff formula then demonstrates is the logarithm of a connected, simply connected subgroup (and by construction the logarithm is a bijection between and ). The group constructed is unique up to isomorphism by Lie’s third theorem.
We first prove the fact that may be given a degree-rank filtration and that has reasonable complexity.
Lemma 10.4.
Let and define by taking the group generated by all -fold iterated commutators of with , and either or and .
Then forms a valid degree-rank filtration of . Furthermore the dimension of is bounded by and one may find an adapted Mal’cev basis such that the complexity of is at most .
Proof.
We will be brief with details; that the associated filtration is valid follows via a straightforward computation with Lemma 2.2. Note as in the set of generators always. Also, since for all generators we have .
To establish the complexity bounds, the key point is noting that taking all -fold iterated commutators of with or and gives a spanning set for . This immediately gives the specified dimension bound. These generators are not linearly independent; however, all relations are generated by either antisymmetry () or the Jacobi identity () applied to the set of generators specified.
To simplify matters, note that all linear relations can be reduced to those between these generators with the “same type” (i.e., relations between the set of -fold commutators of a given set of generators ). These can be collected into disconnected non-interacting “components” which are in size. We may take a linearly spanning set within each group; each generator not in the spanning set may be written as a linear combination of height . Define to be the union of all these spanning elements in . This gives us a basis. Note the subspaces are clearly compatible with natural subsets of these “components” and their associated spanning sets, demonstrating that the basis is appropriate adapted to these vector spaces .
The last matter to check is that there exists such that . This follows by noting that each element may be written as
with . We prove the first implication first; we prove that may be written as a linear combination of iterated commutators where -fold commutators have denominator bounded by . This is trivial to prove inductively via Baker–Campbell–Hausdorff and noting that all -fold commutators vanish.
For the reverse direction, consider expressions of the form
where ranges over all possible iterated commutators (here e.g. ) where are sufficiently divisible integers. Let be defined as the commutator of the exponential of associated elements; e.g. . Choose a generator with the fewest number of commutators in such that . It is straightforward to see via Baker–Campbell–Hausdorff that there is an integer such that if are all divisible by then
has each still divisible by and (without introducing backwards corrections).
The desired result then follows from [42, Lemma B.11], noting that is the degree-rank ordering forming a nested sequence of subgroups. ∎
We now represent the nilsequences on the universal nilmanifold. We define
Note that and trivially .
Recall that is the filtered Mal’cev basis and , , are representative of , , and respectively.
We define a homomorphism by defining the map on generators. Define
That this is a homomorphism is an immediate consequence of the fact that the only relations on the universal nilmanifold are forced on the group since it has degree-rank .
The function with which will be concerned is
This is well-defined since ; it suffices to check that the generators map to within but this is trivial by construction. (This is precisely why we scaled , , and so that when exponentiated they live within .)
We now note a series of basic properties of and the homomorphism .
Lemma 10.5.
Given the above setup we have:
-
•
for all ;
-
•
has a vertical frequency with height at most ;
-
•
is -Lipschitz
-
•
Consider with . If for at least one index we have , then
Furthermore, if instead for two indices we have and then
Proof.
The first property is trivial. For the second property, note that is an -filtered homomorphism (e.g. ). Thus given , we have
and therefore we may set . To check the complexity of it suffices to check the magnitude of on where we use Remark 5.3 to convert between this notion and the notion of height defined. The resulting magnitude is bounded because , , are appropriately bounded integral combinations of elements in which itself has bounded complexity.
We omit a careful justification that has an appropriately bounded Lipchitz constant. The crucial point is that the Mal’cev basis constructed in Lemma 10.4 is made up of appropriately bounded linear combinations of commutators of and each such commutator is seen to map to a bounded element of since maps each generator to a bounded element.
The final property is an immediate consequence of the properties of , , and established in Lemma 9.1 and recorded above. The additional generators which are lifted to the “petal” position on the -th level come from and otherwise we have only artificially placed certain elements in the “linear” class upward to the “” class. (These will correspond to the constant terms in the linear part of the nilsequences.) ∎
We now lift the polynomial sequences in question to the universal nilmanifold. We define:
We define
The key claim, which is trivial by construction, is the following equality.
Claim 10.6.
Given the above setup, we have
Proof.
The final equality is by definition of . The first equality follows by checking that by construction. Therefore since is a homomorphism we conclude that . ∎
Note that at this stage we have simply replace the group in our correlation structure with as the cost of replacing by and by .
This may seem as if we have gone backwards, the key point is that in Lemma 10.5 we have encoded various “vanishing conditions” on the commutator brackets at the level of the generators of the group. This will allow us to translate the “vanishing conditions” obtained in Lemma 9.1 into realizing we can, up to a degree-rank -error term.
10.3. Passing to a quotient nilmanifold
We now construct two additional nilmanifolds; there are essentially and certain quotients constructed in [34, Section 12].555There is a minor issue in [34, p. 1309] when defining ; we follow the definitions given in the erratum [31].
Definition 10.7.
We define as the Lie subgroup of where is spanned by:
-
•
Any -fold commutator of with at least one index such that ;
-
•
Any -fold commutator of with for at least two distinct indices .
We then define as and .
Remark 10.8.
Note that we may set in the definition of ; in particular for . Additionally, may be realized as the following. Consider formal generators of a Lie algebra, for , with the property that:
-
•
Any -fold commutator of with either or and vanishes;
-
•
Any -fold commutator of with for at least two distinct indices vanishes.
This realization is given by taking .
We first check that is well-defined.
Claim 10.9.
For , is a well-defined normal subgroup of .
Proof.
It is clear from definition that is closed under brackets, so forms a Lie subalgebra within . Thus is indeed a Lie subgroup. To prove that is normal it suffices to prove that it is furthermore a Lie algebra ideal, i.e., .
Recall that is spanned by all the -fold commutators (although as discussed in Lemma 10.4 this is not a basis). It suffices to check the containment at the level of generators of the respective Lie algebras. The result then follows since taking a commutator does not decrease the number of “petal” or “linear” generators. ∎
We also have the following complexity bound on . This may be done via the Lie algebra presentation given in Remark 10.8 and repeating the proof in Lemma 10.4, or via noting that is a sufficient rational subgroup of and applying Lemma 3.10. We omit the details.
Lemma 10.10.
Given the above setup, let and note that has a degree-rank filtration given by
Furthermore the dimension of is bounded by and one may find an adapted Mal’cev basis such that the complexity of is .
A key point in this analysis is that this quotient is compatible with .
Lemma 10.11.
Given the above setup, define via
for all . The map is well-defined and in fact is a vertical character of of height at most .
Proof.
To be well-defined as a map, it suffices to show that . This comes exactly from the final item of Lemma 10.5. That is a vertical character then follows as .
To bound the height of note that taking a quotient by maps to in the sense of Remark 10.8. Furthermore the construction of has the property that are sufficiently rational combinations of -fold commutators of with . By Baker–Campbell–Hausdorff, we have that the -fold commutator of is the same as the corresponding one for . However, maps the latter commutator to a sufficiently bounded integer by the complexity bound on and the result follows. ∎
We will require
(10.1) |
note that
Furthermore we have
pointwise. Finally we define
For the remainder of this section and Section 11, fix a nilcharacter on with a -vertical frequency . Furthermore by Lemma B.4666The lemma is stated for degree filtrations. However, one can give the degree filtration a vertical nilcharacter with respect to this filtration is a vertical nilcharacter with respect to the original degree-rank filtration. is adapted to this degree-filtration (as it is adapted to the original degree-rank filtration). we may take which is –Lipschitz with output dimension bounded by .
The reason it will be sufficient to study will be the following lemma which proves that it is equal to up a term which is lower-order in degree-rank.
Lemma 10.12.
Given the above setup, let
which is given the degree-rank filtration
Define . We have:
-
•
is a polynomial sequence on with respect to the given degree-rank filtration;
-
•
The function
for is -invariant;
-
•
has complexity bounded by ;
-
•
Each coordinate of is -Lipschitz.
Remark 10.13.
The second item implies that is -invariant and thus can be realized on a degree-rank nilmanifold with being the lattice.
Proof.
It is trivial to verify that the degree-rank filtration on is valid. Noting that
is a valid Mal’cev basis for bounds the complexity of . The complexity bounds on follow by noting that is appropriately Lipschitz on and similar for . For , we note that each coordinate of is appropriately rational with respect to the Mal’cev basis for , by construction.
Furthermore for we have
where in the final line we have used the definition of .
Finally to verify that is a polynomial sequence with respect to this degree-rank filtration, note via Taylor expansion (e.g. [34, Lemma B.9]) that all polynomial sequences with respect to of the form where is a polynomial sequence with respect to (and its specified degree-rank filtration). The result then follows due to the property
noted above, which was by construction. ∎
11. Extracting a -nilsequence
The goal of this section is to realize
as a multidegree nilsequence in . We accomplish this via a construction of Green, Tao, and Ziegler [34, Section 12] and then use this construction in order to complete the proof of Lemma 6.3. After this, the main business of the paper is essentially done and all that remains to prove Theorem 1.2 is the symmetrization argument which will be carried out in the next section.
11.1. Constructing the -nilsequence
Our analysis at this point is essentially verbatim that of [34, pp. 1313-1315]. We reproduce the details here (and discuss various complexity issues which are completely routine in the appendix). For the sake of simplicity, we may clean up notation from (10.1) and write
where we have abusively reindexed various coefficients but nothing else.
We now define to be the Lie subgroup of such that is the subspace generated by all -fold iterated commutators (with ) of with for exactly one index . We have the following pair of basic observations.
Claim 11.1.
We have that is well-defined, abelian, and normal with respect to .
Proof.
Similar to the proof of Claim 10.9, is well-defined and normal. The only modification to the proof is noting that a commutator of with at least two indices with vanishes by the definition of .
To see that is abelian, it suffices to prove that the commutator of any pair of generators is the identity. This immediately follows from the fact that commutators with at least two generators of the form with vanish. ∎
Due to normality, acts on via conjugation. In particular, we define with the group law given by
We now introduce a manner in which the additive group , with elements denoted
acts on . Specifically, we will define an action on this group for all and use this to construct
This action will allow us to simultaneously “raise” parts of to various different fractional powers of , allowing us to incorporate our “-linear” family of nilsequences into a multidegree nilsequence (in variables ).
For each , we define the homomorphism from to itself on generators. We map for and while is fixed for and . The defining relations of are preserved by this transformation, so this is easily seen to be a well-defined homomorphism. At the Lie algebra this transformation is essentially replacing appropriate by .
For and we have
and for we have
This are trivial since is abelian.
We next claim that if and then
(11.1) |
To prove this note that it suffices to prove the claim for powers of generators of the groups and (since conjugation and are homomorphisms). If the result is trivial due to the abelian property, and if (and is the power of a generator) then by definition so as desired.
We now define by
The map is clearly bijective and we have
so to check this is a group action it suffices to show gives a valid homomorphism of . This follows because
by (11.1), while
where we have used that is abelian and normal.
We are now in position to define the group of interest which will support the multidegree nilsequence. Let
where multiplication is given by
This is seen to be a connected, simply connected Lie group. We give it a multidegree filtration defined by:
-
•
If then ;
-
•
If then ;
-
•
or equivalently just ;
-
•
If then ;
-
•
.
Claim 11.2.
is a valid multidegree filtration on .
Proof.
Note that
and therefore . We next check various commutator relations. First note that
This follows because if we have hence
Therefore it suffices to verify that
We first tackle the first claim, in which we may reduce to the case . We wish to show
if , , and . Via Lemma 2.2, it suffices to prove is normal in and and then check at the level of generators.
To check normality, we have
and the result follows noting that are normal in for all .
Since
and it suffices to check the claim on generators, we may reduce to the case where exactly one of and exactly one of are the identity. The result is clear when are trivial, and the case when are trivial follows from the fact that we have a valid filtration on . In the remaining cases we may assume by symmetry that and . We have
and we see that the final coordinate satisfies . We have finished verifying the first claim.
Now note that is a normal subgroup of , since is abelian. Thus combining with the first claim gives the second claim, namely
for .
The only nontrivial case left is and for the second claim. Furthermore, combining what we know it suffices to check the case when is the element from . Note however that
and the fact that if and then . This follows because if then is in the same group. ∎
Writing , we define
To see this is a group, observe that for we have if all coordinates of are integral. This is clear for the generators of and the rest follows from recalling that “taking -th powers” is a homomorphism on .
We now define the relevant functions which will be used to represent . Let , where the implicit constants are chosen sufficiently large.
Let be a -bounded, -periodic function such that:
-
•
if ;
-
•
if ;
-
•
is -Lipschitz.
Define such that for all and we have . Using that where is a prime between and , we see that there are at most indices which do not satisfy the criterion and choosing sufficiently small, we may assume that is at least half the size of .
Given , we may find such that for all . Define
we check that this in fact gives a well-defined function on . Note that if and then and hence is unique. Furthermore note that
and trivially
if . Now recall that
We set
and define
is seen to be a polynomial sequence with respect to the filtration given to as each piece is trivially a polynomial sequence and the polynomial sequences form a group under pointwise multiplication (see [34, Corollary B.4]).
Note that for all we have
writing
where . This is precisely the desired sense, discussed earlier, in which we have used the group action to “raise” parts of to -fractional powers.
Therefore, for all we have
(11.2) |
We now state various complexity claims regarding and the Lipschitz nature of the function . We defer the rather uninspiring task of checking these bounds to the end of Appendix B.
Lemma 11.3.
Given the above setup, we have that has the structure of a multidegree nilmanifold and it may be given a basis of complexity bounded by . Furthermore is -Lipschitz under this metric.
11.2. Extracting correlation
We now complete the proof of Lemma 6.3. The proof is little more than stitching results proven in this and the previous section and noting that if two nilcharacters “differ by a lower degree-rank term” then one may pass from to the other at the cost of introducing a lower order term. (This is essentially [34, Lemma E.7].)
Proof of Lemma 6.3.
We return to the correlation structure discussed in Section 10 (that is output by Lemma 9.1). Again, we will abuse notation slightly as discussed. So, for all (where ) we have
where is a complexity nilsequence of degree and dimension at most . We adopt the notation developed in Sections 10 and 11. Applying Claim 10.6, we have
Next note that
has trace equal to as is a nilcharacter. Since the output dimension of is bounded by , we have for all that
Using (11.2), we in fact may write for that
Now we may pay a cost of in the size of by Pigeonhole to choose a single coordinate function of , call it , such that
By Lemma 10.12 and using Remark 10.13, can be realized on a nilmanifold with a degree-rank filtration. Furthermore the function underlying is has Lipschitz constant bounded by and the nilmanifold it lives on has dimension at most and complexity bounded by due to Lemma 10.12.
By applying [42, Lemma A.6] with subgroup corresponding to the degree-rank and Pigeonholing in the associated vertical frequency, we may assume that has a vertical frequency with height bounded by ; this may reduce the subset of under consideration by a further admissible fraction. We then extend to a nilcharacter by using Lemma B.4777We have that lives on the group . We may give it the degree filtration and we apply Lemma B.4 to this filtration to get a nilcharacter . We then embed by taking the underlying function, call it , and taking the nilcharacter .; we refer to this nilcharacter as and note it is a degree-rank nilcharacter with appropriate complexity. We thus have
By Pigeonholing in once again we may pass to , which is a fixed coordinate of ,
on a fraction of indices. lives on the group and via [42, Lemma A.6], Pigeonholing in so that we have the same frequency, and embedding in a nilcharacter via Lemma B.4 similar to the above argument, we have for all that
where is a multidegree nilcharacter on with vertical frequency height, output dimension, and Lipschitz constant of each coordinate bounded by while the dimension of the underlying nilmanifold is bounded by .
This completes the proof with being the new multidegree nilcharacter, being the degree-rank nilcharacter and noting that the density of indices which remain is at least . ∎
12. Symmetrization argument
We now perform the necessary symmetrization argument. In particular, at this stage in the argument due to Theorem 6.4 we have shown that for many , correlates with which is a multidegree nilcharacter. We now demonstrate that is “symmetric up to lower order terms” in and (after multilinearizing the variable) via an argument of Green, Tao, and Ziegler [34], which in turn is closely related to an earlier argument of Green and Tao [23] which proved such a result for the -norm. Our treatment is slightly simpler than in [34]. Importantly, this argument is fundamentally based on a finite number of applications of Cauchy–Schwarz and a single call to equidistribution theory and therefore naturally comes with good bounds.
All references to Appendix C are simply quantified versions of lemmas which appear in the work of Green, Tao, and Ziegler [34, Appendix E] and a discussion of the correspondence is given more carefully in Appendix C. The reader may benefit from glancing at the statements in Appendix C or those in [34, Appendix E].
For the remainder of this section and Appendix C, to lighten statements, we say a nilsequence has complexity if the underlying nilmanifold has complexity , the underlying function is -Lipschitz, and the dimension of is bounded by . We will say a nilcharacter has complexity if the underlying nilmanifold has complexity , the output dimension of is bounded by , the underlying function has all coordinates being -Lipschitz, the vertical character underlying has height bounded by , and the dimension of is bounded by . In this section, will always be of the form while the underlying will be of the form in our analysis, where the implicit constants may, by abuse of notation, vary from line to line.
We now recall the output of Theorem 6.4. We have
Here is a degree nilsequence and is a multidegree nilcharacter. Furthermore has complexity while has complexity .
Our first step is to multilinearize in the variable, replacing it by a multidegree nilcharacter which is symmetric in the final variables.
Lemma 12.1.
Fix . Suppose that
with being a periodic multidegree -nilcharacter and are degree nilsequences each of complexity .
There exists a multidegree nilcharacter (with ones), a degree nilsequence, and there exist which are degree nilcharacters all having complexity complexity such that
Furthermore is symmetric in the final coordinates, i.e., for any we have
Proof.
This is essentially an immediate consequence of multilinearization (see e.g. [34, Theorem E.10]). By applying Lemma C.5, there is multidegree nilcharacter of complexity such that and are -equivalent for degree . Furthermore is symmetric in the final coordinates.
Thus applying Lemma 7.4 (and the remark following), there exists a nilsequence of degree and complexity such that
Note that a degree nilsequence of complexity in two variables is also a multidegree nilsequence of complexity via taking the filtration . Therefore by Lemma C.6 and the first item of Lemma C.2, there exist nilsequences and of degree and respectively and complexity such that
Now, is a degree nilsequence of complexity . Applying [42, Lemma A.6], we may replace this product by which is a degree nilsequence of complexity with a vertical frequency of height . Finally apply Lemma B.4 and embed as a coordinate of a nilcharacter of complexity , similar to in the proof of Lemma 6.3. We thus have
where and have the appropriate properties. ∎
We are now in position to complete the proof of Theorem 1.2 via a symmetrization argument. Our argument is analogous to that of Green, Tao, and Ziegler [34, Section 13] modulo certain minor simplifications to the underlying Cauchy–Schwarz arguments.
Proof of Theorem 1.2.
We may assume that . The case is trivial, is standard Fourier analysis, and the case follows from work of Sanders [52] (see [44, Theorem 8]). Furthermore, throughout the analysis we will assume implicitly that ; in the case when is small one may deduce the statement via Fourier analysis. We proceed by induction, assuming that the inverse theorem is known for smaller .
By Theorem 6.4 and then Lemma 12.1 we may assume that
(12.1) |
Here is a multidegree nilcharacter which is symmetric in the final variables, is a degree nilsequence, and are degree nilcharacters with complexities bounded by complexity . For , we take to be the constant function (which is a degree nilcharacter) throughout the argument. Additionally, we may use differently indexed versions of functions that are defined at intermediate stages of the argument; although an abuse of notation, it will always be clear from context.
Step 1: Initial setup for Cauchy–Schwarz argument. For the sake of shorthand, we will denote where there are copies of the variable . By Lemma 7.2 (taking and , we have
for some . Note that Lemma 7.2 is stated for scalar function; here we are using that we may Pigeonhole on coordinates of the vector before using Lemma 7.2.
We next change variables with , , , and . The above then implies that
By the first item of Lemma C.3, and are -equivalent for degree . We use that precisely here so that this is a well-defined term.
Therefore by Lemma 7.4, there exists a collection of degree nilsequences each of complexity such that
We will use to denote vector-valued functions (which may vary term to term) with coordinates which are -bounded such that the dimension is bounded by . The key point is that nearly all terms may be folded into -bounded terms. In particular, we have
Noting that may be twisted by an appropriate complex phase depending on , we may in fact assume that
By applying Pigeonhole in , we may fix such that
Taking the coordinate which achieves the infinity norm, we may assume that are in fact all scalar and thus
we have dropped in one subscript here.
By applying the second item of Lemma C.3 and the second item of Lemma C.2, we have that and are -equivalent for degree . Thus by Lemma 7.4 there exists a nilsequence of degree and complexity such that
Note that a degree nilsequence in variables is a multidegree -nilsequence. Therefore applying Lemma C.6 and applying Pigeonhole, we may adjust and the -bounded functions and remove and thus we may assume that
note that and have all been modified but we have abusively maintained the same notation. In particular, is degree .
By Lemma C.4, the second item of Lemma C.2, and Lemma C.1 (and symmetry of in the final coordinates), we have that and
are -equivalent for degree . In this notation there are copies of and copies of . Now by Lemma 7.4, we have
where is a new degree nilsequence of complexity . Applying Lemma C.6 as before, we may adjust and the -bounded functions and remove this term to have that
Note that the only terms of which involve all of with appearing at least times have exactly one copy of , one copy of and exactly times. Therefore taking the coordinate of
which achieves the infinity norm and adjusting , , and adding a term we have
Step 2: Cauchy–Schwarz to remove -bounded functions. Applying Cauchy–Schwarz to each coordinate of the associated vector, duplicating the variable , and using that is -bounded, we find that
By Lemma C.4, Lemma C.2, and Lemma C.1, we have that
are -equivalent for degree . Therefore by Lemma 7.4, there exists a degree nilsequence of complexity such that
Note that ranges in the set . Take sufficiently small. Then there exists such that such that
This implies that
By applying the first item of Lemma C.3, Lemma C.4, Lemma C.2, and Lemma C.1 we have that
and
are equivalent for degree . Thus by Lemma 7.4 and letting denote a degree nilsequence in of complexity we have that
Here we have “folded” in via Lemma C.2 in . We may collapse various -bounded functions (and pass to the coordinates of and which achieve the norm) and obtain
here the are degree nilsequences of complexity . Furthermore as is a degree nilsequence, we have that it is a multidegree nilsequence. Therefore by Lemma C.6 and Lemma C.2, we may remove at the cost of adjusting and to obtain
This implies that
as . Note that the final indicator may be absorbed into to obtain
Define and we have
Applying Cauchy–Schwarz in , then , and then (analogously to as in Lemma 7.2) we may remove the bounded functions and we have
where denotes conjugation and the are degree at most nilsequences of complexity . Applying Pigeonhole in and applying Lemma C.2 to specialize variables, reindexing to , and taking the maximal coordinate we have
Here is degree at most in while and are multidegree and all have complexity . Finally by the triangle inequality we have
Step 3: Converse of the inverse theorem and polarization. By the converse of the inverse theorem, see Lemma B.5, we have that
Expanding out the definition of the -norm, we find that
The crucial point is that by repeatedly applying Lemma C.4, Lemma C.2, and Lemma C.1 we have that
and
are -equivalent for degree . Therefore by Lemma 7.4, there exists a nilsequence of degree and complexity such that
Via Fourier expansion (a multidimensional version of the argument in Lemma 7.1), we may fold in into .888To be precise, we convolve with where is sufficiently small. This function has the necessary Fourier decay to apply the analysis in Lemma 7.1 We reduce to
Applying Pigeonhole in and applying the first item of Lemma C.2, we reduce to
(12.2) |
once again we have abusively updated , which has degree .
Step 4: Invoking equidistribution theory. This is the unique moment we have the ability to apply equidistribution theory; up to this point we have been applying “elementary” facts regarding nilsequences. Let
and let denote the vertical frequency of on the multidegree nilmanifold . We write
on the multidegree nilmanifold . Note that
may be viewed as a polynomial sequence on where is given a degree filtration. is given a degree filtration where the -th group is
Note that has -vertical frequency , noting that . By applying Corollary 5.5 with (LABEL:eq:main-2) to
and restricting the factorization to , we have
where
-
•
lives in an -rational subgroup such that ;
-
•
is an -rational polynomial sequence;
-
•
is -smooth.
Note that when apply Corollary 5.5 the vertical frequency of the function we have is and we obtain ; we may divide by to obtain the above. Additionally, we have implicitly used that is trivial in the part and abuse notation to descend to .
Let and note that therefore
Step 5: The finishing touch. We now recall from (12.1) that
here we have restricted to a coordinate of and we treat it as a degree nilsequence (rather than using the nilcharacter). By applying Pigeonhole there exist such that
By Lemma C.3, we have that
are -equivalent for degree . Applying Lemma C.6 (splitting) and adjusting , we may instead assume that
for of degree and of degree . Now define
Since this is a nilcharacter, we automatically know
We define
which yields
By applications of Lemma C.4, Lemma C.2, and Lemma C.1 we have that and
are -equivalent for degree . (There are many ’s in the first term and many ’s in the second term.) Applying Lemma C.6, we may approximate each coordinate as a sum of products of multidegree and nilsequences in variables . Furthermore, by the second item of Lemma C.2 this new nilsequence is of similar type. So, folding everything into of degree and the of degree , we find
Furthermore note by Lemma C.3 that
are -equivalent for degree . Applying Lemma 7.4 and Lemma C.6 and adjusting and yet again we have
Now by Lemma C.3 we have that
are -equivalent for degree . Thus applying Lemma 7.4 and Lemma C.6 and adjusting and once again we have
This is finally where we may apply our earlier factorization for . Recall that
where is -periodic and is -smooth. Let denote the period of (i.e., changing any argument by a multiple of keeps its coset the same) and take where the implicit constant is sufficiently large. Break into arithmetic progressions of length roughly and common difference ; call these . There exist and such that
where and is -rational.
By Pigeonhole, there exists an index such that
As is -rational and bounded, it takes on only possible values. Thus by Pigeonhole, there is such that and is -rational such that
where . Finally, rounding to a -net and noting it is -bounded, there exists such that
and , as long as was chosen small enough.
By Lemma 7.1, there exists such that
As , we may absorb into and obtain
Replacing with and writing , we have
Now takes values in such that . The key point is to note that is right-invariant under since it has -vertical frequency . Note that has complexity bounded by due to [42, Lemma B.15]. Furthermore is -Lipschitz on by [42, Lemma B.9, B.15]. Taking the quotient by gives that each coordinate of may be realized a complexity nilsequence of degree .
Applying Pigeonhole in the coordinates of and then Lemma C.6 to approximate as a sum of products of multidegree and nilsequences in variables . So again folding everything into of degree and the of degree , we find
The functions and are vector-valued, but by Pigeonhole there exist coordinates are coordinates of the vectors and such that
Since is a nilsequence of degree and complexity , by the converse of the inverse theorem (see Lemma B.5) we have that
By the Gowers–Cauchy–Schwarz inequality (e.g. [17, Lemma 3.8]), we have that
By induction, there is a nilsequence of degree and complexity such that
Now recall that
Each coordinate of is a degree nilsequence of complexity ; say -th coordinate is and thus we have
This is equivalent to
Note the condition
and thus there such that
The desired nilsequence is then
which is seen to have degree and complexity . We have finally won. ∎
Appendix A On approximate homomorphisms
In this section, we give a number of basic results regarding approximate homomorphisms. The results in this section are, by now, well known consequences of work of Sanders [52]. The proof we give is essentially that in [43], modulo being forced to deal with slight error terms and operating over . We dispose of these error terms via a rounding trick of Green, Tao, and Ziegler [32, Appendix C].
Lemma A.1.
Fix , let and let functions be such that there are at least additive tuples with
for all . Then there exists with such that
for all , for appropriate choices of , , and where is a prime between and .
We deduce the result from the following variant which is the same statement modulo not having an error term.
Lemma A.2.
Fix . Let and be such that there are at least additive tuples with
Then there exists with such that
for all , for appropriate choices of , , and where is a prime between and .
We briefly give the deduction, and then in the sequel focus on Lemma A.2.
Proof of Lemma A.1 given Lemma A.2.
Round each value of to the nearest point in the lattice to form (breaking ties arbitrarily). We have that
for at least additive tuples.
Note however that
and that there are at most lattice points in which are at most in the -th direction from the origin in all directions. Thus there is a vector such that
for at least additive tuples. Applying Lemma A.2 with , , , and immediately gives the desired result. ∎
We now require the notion of a Bohr set in an abelian group.
Definition A.3.
Given an abelian group and a set , we define the Bohr set of radius to be
We first require the fact that the four-fold sumset of a set with small doubling contains a Bohr set of small dimension and large radius. This is an immediate consequence of work of Sanders [52, Theorem 1.1] which produces a large symmetric coset progression and a proposition of Milićević [48, Propositon 27] which produces a Bohr set inside a large symmetric coset progression. This is explicitly [48, Corollary 28].
Lemma A.4.
Let be such that . Then there exists with and such that .
We next require the notion of a Freiman homomorphism.
Definition A.5.
A function (with and being subsets of possibly different abelian groups) is a -Freiman homorphism if for all satisfying
we have
When is not specified, we will implicitly have .
We will also require the follow basic lemma which converts the Freiman homomorphism on a Bohr set into a “bracket” linear function on a slightly smaller Bohr set; the proof is a simplification of [23, Proposition 10.8].
Lemma A.6.
Consider and with Freiman homomorphism . Taking , we have for all that
for appropriate choices of .
Proof.
By [23, Proposition 10.5], we have that
where is a proper generalized arithmetic progression of rank . Furthermore for are linearly independent as vectors in .
Note that for , we have
(A.1) |
Furthermore letting denote we have that
we have used crucially that here. Therefore, by a simple inductive argument we see
if for all .
By the above linear independence, there exists such that and for . Therefore if is such that , we have that
The lemma then follows by plugging into (A.1). ∎
We now recall the definition of additive energy.
Definition A.7.
Given (finite) subsets of an abelian group , define the additive energy to be
and let .
Note that one has the trivial bound . Furthermore via a standard Cauchy–Schwarz argument (similar to e.g. [58, Corollary 2.10]) we have
Proof of Lemma A.2.
Let , which is a graph (i.e., for every there is at most one with ). By assumption we have
We have
and therefore . By Balog–Szemerédi–Gowers (see [23, Theorem 5.2]), there is such that while .
Let . Since is a graph, we have that . However by the Plünnecke–Ruzsa inequality (e.g. [23, Theorem 5.3]) and thus .
Now, by abuse of notation we may view as a subset of . We claim there exists with such that ; we give a proof which is essentially identical to that in [23, Lemma 8.3]. Note that given any we have
This follows immediately from noting that if has an irrational coordinate the probability tends to by Weyl’s equidistribution criterion while if is rational the limiting probability is at most say . Choosing an integer vector which kills at least of the set iteratively then immediately gives the desired lemma.
Let be defined as . Now let . By averaging there exists a cube such that
with , so . Fix such a cube .
We claim that is a graph. For the sake of contradiction suppose not. Then there exist and such that
However,
by definition of . Since , it follows that
as desired.
Let denote the projection of onto the first coordinate. Since is an -Freiman homomorphism on (because is a graph), we have that is a Freiman homorphism on (where is extended via linearity). We now view (which is a subset of integers) as a subset of where is a prime in . Note here that and thus when viewed as a subset of is still a graph. Note that .
By Lemma A.4, we have that contains a Bohr set with . Then by applying Lemma A.6 to each coordinate of on with , we have that
(A.2) |
for all , for appropriate choices of . Here .
We now undo this transformation and we abusively view as a subset of integers in instead of , noting that the fractional part remains identical in both cases. As a slight technical annoyance, might not intersect . But, by Pigeonhole there exists such that . (This requires a lower bound on the size of a Bohr set, see [58, Lemma 4.20].)
Fix such that and consider any such that we have that
since is a graph (note that ). Thus we have
The second line holds since are viewed as fixed and hence we may apply (A.2).
So, letting be the set of values where , this nearly gives the desired result. The only issue is that there are shifts inside the brackets. Note that
Given this, we may Pigeonhole possible values into one of cases based on the corresponding shift for each . Applying the above relation with and and taking the most common case then gives the desired result. ∎
Appendix B Miscellaneous deferred results
We first require the following elementary lemma which will be used in the following deduction.
Lemma B.1.
Fix an integer . Consider vectors with integer coordinates bounded by and such that for . We may write where has coordinates which are rationals with denominators bounded by , , and for .
Proof.
Note that by passing to a subset we may assume that are linearly independent. By Cramer’s rule, there exist which have coordinates which are height rationals such that . Taking and we immediately have the desired result. Recall that we have chosen the fractional part to live within . ∎
We now prove the following elementary lemma which takes a set of horizontal characters (at potentially different levels) and produces a factorization.
Lemma B.2.
Consider a nilmanifold of degree-rank of dimension and complexity . Consider a polynomial sequence such that and consider a set of horizontal characters for and where is an -th horizontal character of height at most . Furthermore suppose that for all ,
Then one may factor
where:
-
•
;
-
•
;
-
•
is -rational;
-
•
for .
Proof.
By the classification of polynomial sequences in terms of coordinates of the second-kind, we have that
for some . Note that
and note that each can be descended to a linear map on with the property that and . That descends uses the fact that for , which follows from Baker–Campbell–Hausdorff.
We next require the following result regarding the existence of a nilmanifold partition of unity. As a remark, a similar statement (e.g. with ) appears as [45, Lemma 2.4]. The proof there, strangely, does not adapt in a straightforward manner to here.
Lemma B.3.
Fix and a nilmanifold of degree , dimension , and complexity . There exists an index set and a collection of nonnegative smooth functions for such that:
-
•
For all , we have ;
-
•
;
-
•
For each , there exists so that for any there exists such that ;
-
•
are -Lipschitz on ;
-
•
For any , is contained in the support of at most terms.
Proof.
We will prove the statement inductively based on the degree of the nilmanifold. For degree nilmanifolds , note that .There exists a set of function such that:
-
•
;
-
•
;
-
•
are -Lipschitz.
Taking , we have that
where denotes the -th coordinate of . For we take
and note that this function is -invariant since multiplying by an element in shifts all coordinates by an integer. Furthermore, by [42, Lemma B.3] we have that the standard -metric on is equivalent to up to a factor of . This completes the proof in this case.
When considering the case of a degree filtration on , suppose that is the given filtration. Note that if is the adapted Mal’cev basis for then
is a valid Mal’cev basis for . Furthermore define . The complexity of is always bounded by by definition. The filtration on is lower degree.
By induction, we have functions with such that
and satisfying various other appropriate properties. We may lift these functions to via
Note that this is well-defined since .
We view each as a function on which only depends on the first coordinates and such that the support is only within some . This is via identifying the fundamental domain of via Mal’cev coordinates of the second-kind (see the proof of [42, Lemma B.6]). We let denote this identification. (Note that the choice of depends on , which we will fix through the remainder of the proof.)
We now have
where and are defined as above.
The fact that each piece
is -invariant on the right is trivial by construction, and the sum of squares property is trivial.
Identifying with a function where , we may identify with a function on the fundamental domain (with respect to second-kind coordinates) of the form
To check that this function is sufficiently Lipschitz, we note that each element has a unique representative in this domain.
Consider and ; by multiplying by the lattice we may assume that are in the specified fundamental domain. Furthermore if we immediately win as is -bounded. We claim that if then . In particular, note that
and that
which gives the desired contradiction assuming that various implicit constants defining are chosen appropriately.
Now we may assume that are such that
else both function values vanish (again supposing is sufficiently small). This is because is equivalent to (up to a factor of ) for bounded elements by [42, Lemma B.3]), and due to the condition on the support of .
In particular, are seen to lie in the interior of the domain. The result then follows immediately noting that is appropriately Lipschitz and is an appropriately Lipschitz function on . The claim that is contained in the support of at most terms follows trivially by construction. ∎
Given this we are now in position to show the existence of nilcharacters on .
Lemma B.4.
Fix and a nilmanifold of degree , dimension , and complexity . Fix a vertical -frequency with height bounded by . There exists a nilcharacter with frequency such that the output dimension is bounded by and each coordinate is -Lipschitz.
Proof.
Let and . Apply Lemma B.3 on with to obtain for . For , we may take the coordinates of to be
In general, for appropriate depending on , we have that is naturally identified with a unique point inside as in the proof of Lemma B.3 and we let denote this map. The key point is to write
and note that as before. Here we have identified with an integer vector using the last elements of the Mal’cev basis and extending by . Note that this is trivially a function on and by construction it has the -vertical frequency . The only technical point is verifying that this function is indeed Lipschitz, which we check for each coordinate .
Consider and . If the Lipschitz condition is obviously satisfied. Thus at least one value is nonzero, and without loss of generality we may assume . Furthermore, noting that is -bounded, we may assume that . As , possibly shifting on the right by an element in the lattice allows us to assume
Via an argument analogous to that in the proof of Lemma B.3, there exists such that ,
and . Since is an appropriately Lipschitz function on the torus if , the desired result follows immediately. ∎
We will also require the following converse of the -inverse theorem; this is verbatim in [32, Appendix G] modulo various complexity details being omitted.
Lemma B.5.
Fix and let be a degree nilmanifold of dimension and complexity , and let be a polynomial sequence with respect to this filtration. Furthermore let satisfy . If is a -bounded function such that
then
Proof.
In the degenerate case when , we take a degree nilsequence of complexity to be a constant function bounded by . This implies that
and by Cauchy–Schwarz we have
By unwinding definitions this implies the case .
For larger , by applying [42, Lemma A.6] we may assume that
where is a -Lipschitz function with -vertical frequency bounded in height by , after Pigeonhole. Cauchy–Schwarz implies that
Note that we may rewrite this as
where we extend by in the usual manner. We define
and note that this has a filtration by [42, Lemma A.3] (with ). Let and note that
is invariant under . Note that is -Lipschitz on and on , and is a nilmanifold of appropriate complexity by [42, Lemma A.3].
Let
with and . Define
this is easily seen to be a polynomial sequence with respect to . Thus
Define and note that it is -Lipschitz on and on by [42, Lemma B.4]. Applying the triangle inequality and restricting to we have
Since is invariant under , passing to gives a nilmanifold of degree and complexity . Thus we may apply by induction, and deduce that
Since
the desired result follows. ∎
We now check the deferred Lemma 11.3.
Proof of Lemma 11.3.
We first construct a weak basis for . Note that each element in may be written as
Consider and consider -fold commutators of with or , and at most one generator has . We define the type of the commutator to be given by the multiset and we say that said type is linear if for exactly one index . We define the degree of a commutator to be . As discussed in Lemmas 10.4 and 10.10, commutators of all types span and commutators of linear type span , and all relations between these elements are spanned by relations between commutators of the same type of height .
Given this, for each collection of commutators of a given type choose a subset which “spans the type” (similar to in the proof of Lemma 10.4). Let denote the set of selected commutators and denote the selected commutators which are of linear type. Our weak basis for will be
this is seen to be a basis for the Lie algebra of . That it spans is trivial, and if there were a relation note that there could be no elements of the form in the relation since projecting onto the first coordinate we recover multiplication in . Given that there are no elements of the form , within this relation multiplication then acts exactly as in and the result claimed independence follows.
We give a multidegree filtration by taking the multidegree filtration of and intersecting with the subgroup of elements of the form . We see that all the subgroups of the filtration are in fact spanned subsets by subsets of . This is simply by taking the generators in of the appropriate degree-rank; for instance
and we take the subsets of and where has degree at least . This is similarly true for which will ultimately form the underlying degree filtration for . Furthermore ordering the basis according to whether they lie in the degree ordering associated to proves that the basis has the degree nesting property. Thus it suffices to check the complexity of various commutators.
Note the identity
which holds for any Lie group and the associated Lie bracket. It is therefore immediate that
and we have
This immediately implies that the structure constants associated to the weak basis are of height .
When including the semi-direct action, we will use the weak basis given by taking elements where denotes the elementary basis vector in the corresponding direction in , placed at the start of . This is easily seen to preserve the nesting property.
To compute the associated structure constants, first note that
and thus the all Lie bracket structure constants of the corresponding form vanish. Furthermore note that
We have that if the type of does not contain then and otherwise (recall the definition of exponentiation by elements of given in Section 11.1). In either case the structure constant is appropriately rational. Therefore we may construct a Mal’cev basis adapted to with the appropriate complexity by applying [42, Lemma B.11] to to construct a Mal’cev basis for and adding the semi-direct Mal’cev basis elements described above to the front of the list. We define this basis to be and define initial segment corresponding to the semi-direct Mal’cev basis elements to be and the remaining elements to be .
We finally check the that is an appropriately Lipschitz function. Let be defined as in Section 11.1. Fix a pair . Note that if
we have that
which is sufficiently bounded. Therefore to check the Lipschitz constant it suffices to consider such that (where the implicit constants are chosen sufficiently large for the remainder of the argument). By multiplying by elements in the lattice, we may assume that , that , and
Note that to assume that we may need to swap and (if both are zero there is nothing to check with respect to the Lipschitz constant).
Since we in fact have that the first coordinates of are in . This implies, due to the distance bound between and and by [42, Lemma B.3], that the first coordinates of are in . Therefore if and then
Note that
where we have used that is -bounded. Next note that distance in controls the distance in for bounded elements by [42, Lemma B.1] and distance in controls distance in by [42, Lemma B.3]. The first term is therefore sufficiently bounded as is -Lipschitz.
Finally note that
where and are the coordinates of and in in the coordinates corresponding to . This is using that
Therefore we have that
and note that are appropriately bounded elements in since are low height combinations of elements in . Via telescoping, and using that the metric is right-invariant and essentially left-invariant under multiplication by bounded elements (e.g. [42, Lemma B.4]), we have that
This completes the proof upon noting that is appropriately Lipschitz on . ∎
Appendix C Nilcharacters
This section is essentially a straightforward quantification of various statements regarding nilcharacters proven in [34, Appendix E].
We first require that two nilcharacters being equivalent is a transitive relationship; this is a quantified version of [34, Lemma E.7]. Recall the notion of complexity that we carry over from Section 12.
Lemma C.1.
Consider three nilcharacters each of complexity and such that the pair and and the pair and are -equivalent for multidegree . Then and are -equivalent for multidegree .
Proof.
Notice that each coordinate of may be expressed as the sum of at most coordinates of the nilcharacter
this follows since the trace of is . The result then follows by rewriting
and applying the assumption. ∎
We will generally require the following specialization lemmas; these are rather straightforward consequences of the definitions modulo the need to handle slight filtration issues.
Lemma C.2.
We have the following:
-
•
Consider a nilsequence of multidegree and complexity . Given , the function , treating as fixed, is a multidegree nilsequence of complexity .
-
•
Consider homomorphisms . If is a nilsequence of degree of complexity then is a degree nilsequence in variables of complexity .
-
•
If is a nilsequence of multidegree of complexity then it is also a nilsequence of degree of complexity .
Remark.
This result allows us to interpret expressions such as as an appropriate degree nilcharacter in variables, if is a nilcharacter in variables with multidegree .
Proof.
We handle these items in reverse order (as this is also the difficulty of these claims). Let
with the underlying nilmanifold being and the specified Mal’cev basis being .
For the last claim, note that (by the definition of complexity for multidegree nilmanifolds) is adapted to the degree filtration . Furthermore by the inclusion given on [34, p. 1264] or direct inspection given the Taylor expansion in [34, Lemma B.9], we have that is a polynomial sequence with respect to the degree filtration . The desired result follows immediately.
For the second item, notice that if a polynomial has total degree , then for any linear maps we have that has total degree . This coupled with Taylor expansion [34, Lemma B.9] and the fact that the set of polynomial sequences with respect to a given -filtration is a group (by [34, Corollary B.4]) implies the result.
We now handle the first item; this is the only nontrivial part. Write with and . We replace the polynomial sequence by and by the function . We may thus assume, at the cost of replacing by , that .
We now apply [34, Lemma B.9] to see
where we order lexicographically with indices considered in reverse order in the product (in particular, the first few terms are , , , and so on) and . As , we have that
It then follows that is a polynomial with respect to
which we give a multidegree filtration for and . Note that all subgroups in this filtration are -rational with respect to and that is a degree filtration. Therefore applying [42, Lemma B.11] guarantees that we may find a Mal’cev basis for (which is -rational with respect to ). Descending to gives the desired result with the necessary Lipschitz bound following from [42, Lemma B.9]. ∎
We now state a quantified version of [34, Lemma E.8]. Recall the notion of equivalence (Definition 7.3).
Lemma C.3.
Consider a nilcharacter with complexity of multidegree with . We have that:
-
•
The nilcharacters
are -equivalent for multidegree .999This means we take the down-set generated by and then remove .
-
•
Fix . The nilcharacters
are -equivalent for multidegree .
-
•
Fix . Then
are -equivalent for multidegree .
-
•
Fix . There exists a nilcharacter of complexity such that
are -equivalent for multidegree .
Remark.
for is interpreted as .
Proof.
Throughout the proof, we let
where the underlying nilmanifold is and the underlying Mal’cev basis is . When going from item to item, we may reuse variables (e.g., will be defined in multiple different manners throughout the proof). Additionally, the following analysis implicitly uses that ; in the remaining case all nilsequences become fixed constants and the result is obvious.
For the first item, note that coordinates of are multidegree polynomial sequences with respect to group given the filtration
As all coordinates of have the same vertical frequency, we have that the coordinates of are invariant under . This immediately gives the desired result upon taking a quotient and using Lemma 3.10.
For the second item, note that is a shifted filtration. Note that this is an -filtration with respect to the multidegree ordering. We define the group
let , and define the following -filtration with respect to the multidegree ordering:
By using Lemma 2.2 we may see that this is a valid. We define the cocompact groups similarly. Now the proof of [34, Lemma E.8] shows that
is a polynomial sequence with respect to this filtration and that
is invariant under the action of .
We first construct a Mal’cev basis on . Define and note that has a degree filtration
and all these subgroups are -rational with respect to . Therefore has a Mal’cev basis which is adapted to this filtration and all elements are height at most combinations of elements in by [42, Lemma B.11]. Note that
is easily shown to be a weak basis of rationality for and has the degree nesting property. Letting we see that
form a sequence of subgroups such that for (with ). Thus by [42, Lemma B.11] we can find a Mal’cev basis adapted to this sequence such that each element is a height linear combination of
At present, however, we see that has not been given a multidegree filtration (only an -filtration with respect to the multidegree ordering; recall Definition 2.4). We replace by
and note that is appropriately rational with respect to and for . Note that is easily seen to have a multidegree filtration. Furthermore, removing the initial elements, we see that the truncation of is valid Mal’cev basis for of complexity and all subgroups in the multidegree filtration are -rational.
We now write where
and . We consider the modified polynomial sequence
evaluating at this is now seen to be a polynomial sequence in . Defining
we have that is invariant under and
We may pass to the quotient group and the desired result is essentially an immediate consequence of Lemma 3.10.
We now come to the third item; we only maintain the notation from the first sentence of the proof. Note that via writing with and , replacing by and by , up to replacing by we may assume that .
Define
here means is coordinate-wise at least as large as and not identical. Furthermore ; note that is isomorphic to however we have given the group an alternate filtration. This is verified to be an -filtration with respect to the multidegree ordering in [34, p. 1356]. Furthermore the proof of [34, Lemma E.8] shows that
is a polynomial sequence with respect to this filtration and that
is invariant under the action of . The primary technical issue, as before, is that while this is an –filtration with respect to the multidegree ordering this is not a multidegree filtration (Definition 2.4).
We first give a Mal’cev basis. Note that is adapted to the degree filtration on given by (Definition 3.8). It is immediate to see that
is a Mal’cev basis for the product filtration on . Then using [42, Lemma B.11] on
where , which is seen to satisfy for , we easily construct a Mal’cev basis for coming from combinations of . (We implicitly use that .) As is has complexity , it is trivial to see that all subgroups in the filtration of are -rational. The Mal’cev basis clearly has the nesting property of order since does.
We define as
and this group is seen to be appropriately rational with respect to and is given the multidegree filtration for . Noting that the constant term of the Taylor expansion of is , we have that this is in fact a polynomial sequence with respect to the multidegree filtration given to . (This is where we use that we reduced to .) Furthermore, letting , we see that a truncation of is an adapted Mal’cev basis to where each element is an -rational combination of . As is invariant under , by passing to the quotient and applying Lemma 3.10 we immediately finishe the proof.
We finally deduce the fourth item from the third item. Let ; note that may be extended to take on rational input via using Mal’cev coordinates and we may treat as a valid polynomial sequence. By applying the third item, we have that
are -equivalent for multidegree . Outputting then gives the desired result. ∎
The next lemma is a quantified version of [34, Lemma 13.2]. The proof is once again essentially identical modulo noting slight changes in the filtration notions.
Lemma C.4.
Consider which is a multidegree nilcharacter of complexity . Then
are -equivalent for degree .
Proof.
Let where the underlying nilmanifold is and the underlying Mal’cev basis is . Let with and . We have that
We let and . Thus may assume replace by and by (at the cost of replacing by ) and assume that .
Consider, for ,
and take . Via Baker–Campbell–Hausdorff this gives a valid degree filtration
We define . We now verify that
is a polynomial sequence with respect to this degree filtration. This is immediate nothing that by Taylor expansion [34, Lemma B.9] and the condition at , we have
with . The desired polynomiality of the tripled sequence then follows easily from Baker–Campbell–Hausdorff and the fact that the degree of the exponents in the Taylor expansion for the term is at most .
We now construct a Mal’cev basis for . Let and note that by definition is adapted to . We may prove that
is a weak basis for . Furthermore this basis is easily seen to have the nesting property of order and that all subgroups are -rational. Thus applying [42, Lemma B.11] we may find a Mal’cev basis for adapted to the given filtration of complexity and such that all basis elements are -rational combinations of .
The function we will consider is
This is easily seen to be Lipschitz on when given the Mal’cev basis . As has basis elements which are height rational combination of , we find that is -Lipschitz on .
Note that is invariant under the group and therefore taking the output quotient group with lattice and using Lemma 3.10 completes the proof. ∎
We now come to the most technical of the complexity justifications we will need to perform, multilinearization. We will give a rather barebones analysis (citing much from [34, Proposition E.9, E.10]); the reader may find the discussion in [34, pp. 1360-1363] where an extended example is discussed useful. (We prove a slightly weaker statement which is all that is used in the analysis to ease checking extra complexity details.)
Lemma C.5.
Consider nilcharacter of multidegree and complexity . There exists a multidegree nilcharacter
of complexity such that
are -equivalent for degree and furthermore, for each , is symmetric in the variables .
Remark.
We will only require the above lemma for multidegree nilsequences.
Proof.
By Lemma C.3, there exists such that
are -equivalent for degree . Therefore by Lemma 7.4, it suffices to produce such that
are -equivalent for degree .
Let
with the underlying nilmanifold being and the associated Mal’cev basis being . Via a standard manipulation which has been perform several times already, we may assume that (at the cost of an insignificant change in parameters). Furthermore assume that is the vertical character, so
Given , we denote
The group we will ultimately use to construct our nilsequence will be given by constructing the associated nilpotent Lie algebra. We take
and for each let denote the embedding into the direct sum. We endow with a Lie bracket such that if then
and if then
where the bracket between is taken in the ambient space and is seen to lie in by the commutator property of the original filtration on .
To verify that this gives a valid Lie algebra it suffices to verify this operation is antisymmetric and satisfies the Jacobi relations. Furthermore to verify it suffices to verify these relations on the generators. For antisymmetry for , if it is trivial and otherwise
as desired. For the Jacobi identity, when checked on generators , if the result is trivial. Otherwise we have
as desired.
The associated -filtration with respect to the multidegree ordering is given as follows. For any , let be the Lie subalgebra of generated by for which for each , and . It follows this is an -filtration with respect to the multidegree ordering because for vectors , if and we either have in which case the commutator is trivial or in which case the result also follows easily. Noting that by construction , the above immediately implies that we have a multidegree filtration on .
We now construct a weak basis for . Recall we have a Mal’cev basis for . Given , we define the filtration
Note that and that is a valid degree filtration when . Thus by [34, Lemma B.11], we may find a Mal’cev basis for each which is an -rational combination of .
Define
Furthermore define to be the group generated by where is a sufficiently large constant depending only on (and in particular not on or ). Direct computation with Baker–Campbell–Hausdorff implies that is contained in . Furthermore we see that is compact, is a weak basis of rationality for , and has the degree nesting property. As all groups within the multidegree filtration are -rational with respect to , by applying [42, Lemma B.11] we may construct a basis with respect to the canonical associated degree filtration of which certifies that with the given multidegree filtration has complexity bounded by . Furthermore the adapted Mal’cev basis is an -rational combination of (lifted to appropriately).
We define the -vertical frequency as
and it is trivial to use the construction of to certify that has height bounded by . We take to be a nilcharacter with frequency produced by Lemma B.4 (which is applied to the canonical degree filtration of ) and this construction gives output dimension and Lipschitz constant with respect to .
We now define . Note that
via [34, Lemma B.9] and the condition at to rule out need a coefficient where . (We are using monomials instead of binomials, which is a minor but easy alteration.) The product here is taken in increasing lexicographic order. We define
Let denote the subgroup of generated by
Note that the function
is invariant under the action of .
We will construct which is a subgroup of with a degree filtration such that the final group is and such that
is a polynomial sequence with respect to this filtration. Let (for ) be generated by elements of the form
(C.1) |
where , as well as
where in the first case, and in the second case. Furthermore set ; we trivially see that . That this is a filtration follows from liberal application of Baker–Campbell–Hausdorff; we use crucially that the number of ways to break a set of size into two labeled sets of size and which are disjoint is , which modifies the factorial prefactors in (C.1) appropriately.
Furthermore it is trivial to see that the are -rational with respect to the Mal’cev basis for given by
and therefore applying [42, Lemma B.11] we may construct a Mal’cev basis of complexity for . Furthermore is appropriately Lipschitz with respect to . Finally, since
is in by definition, we see that
is a polynomial sequence with respect to the filtration. Quotienting out by (using that is invariant under ) and using Lemma 3.10, we finally complete the proof. ∎
We now reach the final technical lemma of the paper which states that a nilsequence of multidegree can be approximated by a sum of products of nilsequences in and . This “splitting” lemma is a quantified version of [34, Lemma E.4]; the proof here is ever so slightly different as we are forced to not use the Stone–Weierstrass theorem.
Lemma C.6.
Let and be finite downsets in and fix . Suppose that is a nilsequence of multidegree with complexity . Then there exists such that
with the being nilsequences of multidegree , the being nilsequences of multidegree , and having complexity .
Proof.
We let
where the underlying nilmanifold is . As is standard, we may assume that up to the insignificant change of adjusting to . Furthermore let the adapted Mal’cev basis for be .
We have for each that the groups
form a degree filtration , where the length of the filtration is . As these subgroups are all -rational with respect to , there exists a Mal’cev basis adapted to this filtration of complexity where each element is an -rational combination of elements in by [42, Lemma B.11].
Using a variant of Lemma 10.2, adapted to multidegree filtrations, we may write
The product here is taken in is increasing and then lexicographic order and taken in increasing order of . The modified proof of such a representation involves iteratively handling terms in increasing order of (and handling these terms in an arbitrary order); we omit a careful proof.
The first key part of the proof is lifting to the universal nilmanifold. We define the universal nilmanifold to be generated by generators for , , and . The only relations these generators satisfy is that any -fold commutator for between vanishes if is not in . We give the structure of a multidegree nilmanifold by letting be generated by the set of -fold commutators (for any ) of where (here means that each coordinate is larger). This is easily proven to be an -filtration with respect to the multidegree ordering and note that since we have no generators with , this is in fact a multidegree filtration. Finally we let be the lattice generated by .
The analysis in Lemma 10.4 can easily be extended to prove that has a filtered Mal’cev basis of complexity where the basis elements are height linear combinations of -fold commutators of . Furthermore note that the dimension of is .
We now lift to . Define the homomorphism via
here we are writing . That this is a homormorphism follows from noting that all relations in are present in because has multidegree . We next lift the polynomial sequence to
and to via
Note that since , this is a well-defined function on . Furthermore, noting various properties of and that elements of are appropriately bounded and rational linear combinations of , we have that is -Lipschitz with respect to the Mal’cev basis specified by . Therefore for the remainder of the proof we operate with the nilsequence
For the remainder of the analysis we furthermore assume that there exists with such that if is identified with then lies in . We will ultimately take sufficiently small. If we prove the proposition with for functions with such restricted support then the result in generality follows by Lemma B.3.
The use of the universal nilmanifold comes precisely when defining the following two nilmanifolds for the split terms. Let be the group generated by with and be the group generated by with . It is trivial to see that are normal and -rational with respect to . Let and be bases for the Lie algebras of and which are -rational bounded combinations of .
We consider the nilmanifolds and . The first is clearly a multidegree nilmanifold while the second is a multidegree nilmanifold, each of complexity . Furthermore we can choose underlying Mal’cev bases which are -rational combinations of and , respectively. (See, e.g., the arguments regarding in Section 10.3.) Note here that and analogously for .
The key point is that by construction, . This implies that there exist linear maps and such that
(C.2) |
for all . Furthermore one can take and bounded in the sense that
for all and analogously for and .
We now identify via with the domain and we only have support of in . Given such that , we have that
Given that is sufficiently small, these are contained
respectively.
Identify with the torus (note that the boundaries are glued differently than in , but we are near the center so it is not an issue). We have that is an -Lipschitz function with respect to the standard torus metric (see e.g. [45, Lemma 2.3] and [42, Lemma B.3]). Thus for such that , via standard Fourier approximation (see e.g. [49, Lemma A.8]), for there exist with such that
where the sum is over . Using (C.2) we may write this equivalently as
where again the sum is over .
For such that , we let
with for , for , and is -Lipschitz and extends to via periodicity. is seen to be an -Lipschitz function on . This follows via the size of and that distance in controls distance in first-kind coordinates (see e.g. [42, Lemmas B.1, B.3]). Define in the same manner. We have that
As this holds for all such that and the approximating function is invariant under , this holds for all . This completes the proof, plugging in and noting that and are multidegree and polynomial sequences on and respectively. ∎
References
- [1] D. Altman, A non-flag arithmetic regularity lemma and counting lemma, arXiv:2209.14083.
- [2] D. Altman, On a conjecture of Gowers and Wolf, Discrete Anal. (2022), Paper No. 10, 13.
- [3] V. Bergelson, B. Host, and B. Kra, Multiple recurrence and nilsequences, Invent. Math. 160 (2005), 261–303, With an appendix by Imre Ruzsa.
- [4] V. Bergelson, T. Tao, and T. Ziegler, An inverse theorem for the uniformity seminorms associated with the action of , Geom. Funct. Anal. 19 (2010), 1539–1596.
- [5] T. F. Bloom and O. Sisask, An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, arXiv:2309.02353.
- [6] O. A. Camarena and B. Szegedy, Nilspaces, nilmanifolds and their morphisms, arXiv:1009.3825.
- [7] P. Candela, Notes on compact nilspaces, Discrete Anal. (2017), Paper No. 16, 57.
- [8] P. Candela, Notes on nilspaces: algebraic aspects, Discrete Anal. (2017), Paper No. 15, 59.
- [9] P. Candela, D. González-Sánchez, and B. Szegedy, On the inverse theorem for gowers norms in abelian groups of bounded torsion, arXiv:2311.13899.
- [10] P. Candela and B. Szegedy, Regularity and inverse theorems for uniformity norms on compact abelian groups and nilmanifolds, J. Reine Angew. Math. 789 (2022), 1–42.
- [11] J.-P. Conze and E. Lesigne, Théorèmes ergodiques pour des mesures diagonales, Bull. Soc. Math. France 112 (1984), 143–175.
- [12] L. J. Corwin and F. P. Greenleaf, Representations of nilpotent Lie groups and their applications. Part I, Cambridge Studies in Advanced Mathematics, vol. 18, Cambridge University Press, Cambridge, 1990, Basic theory and examples.
- [13] P. Erdős and P. Turán, On Some Sequences of Integers, J. London Math. Soc. 11 (1936), 261–264.
- [14] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256.
- [15] H. Furstenberg and B. Weiss, A mean ergodic theorem for , Convergence in ergodic theory and probability (Columbus, OH, 1993), Ohio State Univ. Math. Res. Inst. Publ., vol. 5, de Gruyter, Berlin, 1996, pp. 193–227.
- [16] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), 529–551.
- [17] W. T. Gowers, Arithmetic progressions in sparse sets, Current developments in mathematics, 2000, Int. Press, Somerville, MA, 2001, pp. 149–196.
- [18] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465–588.
- [19] W. T. Gowers and L. Milićević, An inverse theorem for Freiman multi-homomorphisms, arXiv:2002.11667.
- [20] W. T. Gowers and L. Milićević, A quantitative inverse theorem for the norm over finite fields, arXiv:1712.00241.
- [21] W. T. Gowers and J. Wolf, The true complexity of a system of linear equations, Proc. Lond. Math. Soc. (3) 100 (2010), 155–176.
- [22] B. Green, 100 open problems, manuscript, available on request.
- [23] B. Green and T. Tao, An inverse theorem for the Gowers norm, Proc. Edinb. Math. Soc. (2) 51 (2008), 73–153.
- [24] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), 481–547.
- [25] B. Green and T. Tao, New bounds for Szemerédi’s theorem. II. A new bound for , Analytic number theory, Cambridge Univ. Press, Cambridge, 2009, pp. 180–204.
- [26] B. Green and T. Tao, An arithmetic regularity lemma, an associated counting lemma, and applications, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 261–334.
- [27] B. Green and T. Tao, Linear equations in primes, Ann. of Math. (2) 171 (2010), 1753–1850.
- [28] B. Green and T. Tao, The Möbius function is strongly orthogonal to nilsequences, Ann. of Math. (2) 175 (2012), 541–566.
- [29] B. Green and T. Tao, The quantitative behaviour of polynomial orbits on nilmanifolds, Ann. of Math. (2) 175 (2012), 465–540.
- [30] B. Green and T. Tao, New bounds for Szemerédi’s theorem, III: a polylogarithmic bound for , Mathematika 63 (2017), 944–1040.
- [31] B. Green, T. Tao, and T. Ziegler, Erratum for “An inverse theorem for the Gowers -norm”, manuscript.
- [32] B. Green, T. Tao, and T. Ziegler, An inverse theorem for the Gowers -norm, Glasg. Math. J. 53 (2011), 1–50.
- [33] B. Green, T. Tao, and T. Ziegler, An inverse theorem for the Gowers -norm, Electron. Res. Announc. Math. Sci. 18 (2011), 69–90.
- [34] B. Green, T. Tao, and T. Ziegler, An inverse theorem for the Gowers -norm, Ann. of Math. (2) 176 (2012), 1231–1372.
- [35] Y. Gutman, F. W. R. M. Manners, and P. P. Varjú, The structure theory of nilspaces II: Representation as nilmanifolds, Trans. Amer. Math. Soc. 371 (2019), 4951–4992.
- [36] Y. Gutman, F. W. R. M. Manners, and P. P. Varjú, The structure theory of nilspaces I, J. Anal. Math. 140 (2020), 299–369.
- [37] Y. Gutman, F. W. R. M. Manners, and P. P. Varjú, The structure theory of nilspaces III: Inverse limit representations and topological dynamics, Adv. Math. 365 (2020), 107059, 53.
- [38] B. Host and B. Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), 397–488.
- [39] A. Jamneshan, O. Shalom, and T. Tao, The structure of arbitrary Conze–Lesigne systems, Comm. Amer. Math. Soc. 4 (2024), 182–229.
- [40] A. Jamneshan and T. Tao, The inverse theorem for the Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches, Discrete Anal. (2023), Paper No. 11, 48.
- [41] Z. Kelley and R. Meka, Strong bounds for 3-progressions, arXiv:2302.05537.
- [42] J. Leng, Efficient Equidistribution of Nilsequences, arXiv:2312.10772.
- [43] J. Leng, Efficient Equidistribution of Periodic Nilsequences and Applications, arXiv:2306.13820.
- [44] J. Leng, Improved Quadratic Gowers Uniformity for the Möbius Function, arXiv:2212.09635.
- [45] J. Leng, A. Sah, and M. Sawhney, Improved bounds for five-term arithmetic progressions, arXiv:2312.10776.
- [46] J. Leng, A. Sah, and M. Sawhney, Improved Bounds for Szemerédi’s Theorem, arXiv:2402.17995.
- [47] F. W. R. M. Manners, Quantitative bounds in the inverse theorem for the Gowers -norms over cyclic groups, arXiv:1811.00718.
- [48] L. Milićević, Bilinear Bogolyubov Argument in Abelian Groups, arXiv:2109.03093.
- [49] S. Peluse, A. Sah, and M. Sawhney, Effective bounds for Roth’s theorem with shifted square common difference, arXiv:2309.08359.
- [50] K. F. Roth, On certain sets of integers. II, J. London Math. Soc. 29 (1954), 20–26.
- [51] T. Sanders, On certain other sets of integers, J. Anal. Math. 116 (2012), 53–82.
- [52] T. Sanders, On the Bogolyubov-Ruzsa lemma, Anal. PDE 5 (2012), 627–655.
- [53] B. Szegedy, On higher order Fourier analysis, arXiv:1203.2260.
- [54] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Number Theory (Colloq., János Bolyai Math. Soc., Debrecen, 1968), Colloq. Math. Soc. János Bolyai, vol. 2, North-Holland, Amsterdam-London, 1970, pp. 197–204.
- [55] E. Szemerédi, On sets of integers containing no elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.
- [56] T. Tao, Goursat and Furstenberg–Weiss type lemmas, 2021, blog post. https://terrytao.wordpress.com/2021/05/07/goursat-and-furstenberg-weiss-type-lemmas/.
- [57] T. Tao and J. Teräväinen, Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions, J. Eur. Math. Soc. (2023), 1–64.
- [58] T. Tao and V. H. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2010, Paperback edition [of MR2289012].
- [59] T. Tao and T. Ziegler, The inverse conjecture for the Gowers norm over finite fields via the correspondence principle, Anal. PDE 3 (2010), 1–20.
- [60] T. Tao and T. Ziegler, The inverse conjecture for the Gowers norm over finite fields in low characteristic, Ann. Comb. 16 (2012), 121–188.
- [61] T. Tao and T. Ziegler, Polynomial patterns in the primes, Forum Math. Pi 6 (2018), e1, 60.
- [62] T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc. 20 (2007), 53–97.