Monthly Archive

You are currently browsing the monthly archive for December 2021.

The inverse theorem for the U^3 Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches

28 December, 2021 in math.CO, paper | Tags: , , , | by | 15 comments

Asgar Jamneshan and myself have just uploaded to the arXiv our preprint “The inverse theorem for the {U^3} Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches“. This paper, which is a companion to another recent paper of ourselves and Or Shalom, studies the inverse theory for the third Gowers uniformity norm

\displaystyle \| f \|_{U^3(G)}^8 = {\bf E}_{h_1,h_2,h_3,x \in G} \Delta_{h_1} \Delta_{h_2} \Delta_{h_3} f(x)

on an arbitrary finite abelian group {G}, where {\Delta_h f(x) := f(x+h) \overline{f(x)}} is the multiplicative derivative. Our main result is as follows:

Theorem 1 (Inverse theorem for {U^3(G)}) Let {G} be a finite abelian group, and let {f: G \rightarrow {\bf C}} be a {1}-bounded function with {\|f\|_{U^3(G)} \geq \eta} for some {0 < \eta \leq 1/2}. Then:
  • (i) (Correlation with locally quadratic phase) There exists a regular Bohr set {B(S,\rho) \subset G} with {|S| \ll \eta^{-O(1)}} and {\exp(-\eta^{-O(1)}) \ll \rho \leq 1/2}, a locally quadratic function {\phi: B(S,\rho) \rightarrow {\bf R}/{\bf Z}}, and a function {\xi: G \rightarrow \hat G} such that

    \displaystyle {\bf E}_{x \in G} |{\bf E}_{h \in B(S,\rho)} f(x+h) e(-\phi(h)-\xi(x) \cdot h)| \gg \eta^{O(1)}.

  • (ii) (Correlation with nilsequence) There exists an explicit degree two filtered nilmanifold {H/\Lambda} of dimension {O(\eta^{-O(1)})}, a polynomial map {g: G \rightarrow H/\Lambda}, and a Lipschitz function {F: H/\Lambda \rightarrow {\bf C}} of constant {O(\exp(\eta^{-O(1)}))} such that

    \displaystyle |{\bf E}_{x \in G} f(x) \overline{F}(g(x))| \gg \exp(-\eta^{-O(1)}).

Such a theorem was proven by Ben Green and myself in the case when {|G|} was odd, and by Samorodnitsky in the {2}-torsion case {G = {\bf F}_2^n}. In all cases one uses the “higher order Fourier analysis” techniques introduced by Gowers. After some now-standard manipulations (using for instance what is now known as the Balog-Szemerédi-Gowers lemma), one arrives (for arbitrary {G}) at an estimate that is roughly of the form

\displaystyle |{\bf E}_{x \in G} {\bf E}_{h,k \in B(S,\rho)} f(x+h+k) b(x,k) b(x,h) e(-B(h,k))| \gg \eta^{O(1)}

where {b} denotes various {1}-bounded functions whose exact values are not too important, and {B: B(S,\rho) \times B(S,\rho) \rightarrow {\bf R}/{\bf Z}} is a symmetric locally bilinear form. The idea is then to “integrate” this form by expressing it in the form

\displaystyle B(h,k) = \phi(h+k) - \phi(h) - \phi(k) \ \ \ \ \ (1)

 for some locally quadratic {\phi: B(S,\rho) \rightarrow {\bf C}}; this then allows us to write the above correlation as

\displaystyle |{\bf E}_{x \in G} {\bf E}_{h,k \in B(S,\rho)} f(x+h+k) e(-\phi(h+k)) b(x,k) b(x,h)| \gg \eta^{O(1)}

(after adjusting the {b} functions suitably), and one can now conclude part (i) of the above theorem using some linear Fourier analysis. Part (ii) follows by encoding locally quadratic phase functions as nilsequences; for this we adapt an algebraic construction of Manners.

So the key step is to obtain a representation of the form (1), possibly after shrinking the Bohr set {B(S,\rho)} a little if needed. This has been done in the literature in two ways:

  • When {|G|} is odd, one has the ability to divide by {2}, and on the set {2 \cdot B(S,\frac{\rho}{10}) = \{ 2x: x \in B(S,\frac{\rho}{10})\}} one can establish (1) with {\phi(h) := B(\frac{1}{2} h, h)}. (This is similar to how in single variable calculus the function {x \mapsto \frac{1}{2} x^2} is a function whose second derivative is equal to {1}.)
  • When {G = {\bf F}_2^n}, then after a change of basis one can take the Bohr set {B(S,\rho)} to be {{\bf F}_2^m} for some {m}, and the bilinear form can be written in coordinates as

    \displaystyle B(h,k) = \sum_{1 \leq i,j \leq m} a_{ij} h_i k_j / 2 \hbox{ mod } 1

    for some {a_{ij} \in {\bf F}_2} with {a_{ij}=a_{ji}}. The diagonal terms {a_{ii}} cause a problem, but by subtracting off the rank one form {(\sum_{i=1}^m a_{ii} h_i) ((\sum_{i=1}^m a_{ii} k_i) / 2} one can write

    \displaystyle B(h,k) = \sum_{1 \leq i,j \leq m} b_{ij} h_i k_j / 2 \hbox{ mod } 1

    on the orthogonal complement of {(a_{11},\dots,a_{mm})} for some coefficients {b_{ij}=b_{ji}} which now vanish on the diagonal: {b_{ii}=0}. One can now obtain (1) on this complement by taking

    \displaystyle \phi(h) := \sum_{1 \leq i < j \leq m} b_{ij} h_i h_k / 2 \hbox{ mod } 1.

In our paper we can now treat the case of arbitrary finite abelian groups {G}, by means of the following two new ingredients:

  • (i) Using some geometry of numbers, we can lift the group {G} to a larger (possibly infinite, but still finitely generated) abelian group {G_S} with a projection map {\pi: G_S \rightarrow G}, and find a globally bilinear map {\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}} on the latter group, such that one has a representation

    \displaystyle B(\pi(x), \pi(y)) = \tilde B(x,y) \ \ \ \ \ (2)

     of the locally bilinear form {B} by the globally bilinear form {\tilde B} when {x,y} are close enough to the origin.
  • (ii) Using an explicit construction, one can show that every globally bilinear map {\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}} has a representation of the form (1) for some globally quadratic function {\tilde \phi: G_S \rightarrow {\bf R}/{\bf Z}}.

To illustrate (i), consider the Bohr set {B(S,1/10) = \{ x \in {\bf Z}/N{\bf Z}: \|x/N\|_{{\bf R}/{\bf Z}} < 1/10\}} in {G = {\bf Z}/N{\bf Z}} (where {\|\|_{{\bf R}/{\bf Z}}} denotes the distance to the nearest integer), and consider a locally bilinear form {B: B(S,1/10) \times B(S,1/10) \rightarrow {\bf R}/{\bf Z}} of the form {B(x,y) = \alpha x y \hbox{ mod } 1} for some real number {\alpha} and all integers {x,y \in (-N/10,N/10)} (which we identify with elements of {G}. For generic {\alpha}, this form cannot be extended to a globally bilinear form on {G}; however if one lifts {G} to the finitely generated abelian group

\displaystyle G_S := \{ (x,\theta) \in {\bf Z}/N{\bf Z} \times {\bf R}: \theta = x/N \hbox{ mod } 1 \}

(with projection map {\pi: (x,\theta) \mapsto x}) and introduces the globally bilinear form {\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}} by the formula

\displaystyle \tilde B((x,\theta),(y,\sigma)) = N^2 \alpha \theta \sigma \hbox{ mod } 1

then one has (2) when {\theta,\sigma} lie in the interval {(-1/10,1/10)}. A similar construction works for higher rank Bohr sets.

To illustrate (ii), the key case turns out to be when {G_S} is a cyclic group {{\bf Z}/N{\bf Z}}, in which case {\tilde B} will take the form

\displaystyle \tilde B(x,y) = \frac{axy}{N} \hbox{ mod } 1

for some integer {a}. One can then check by direct construction that (1) will be obeyed with

\displaystyle \tilde \phi(x) = \frac{a \binom{x}{2}}{N} - \frac{a x \binom{N}{2}}{N^2} \hbox{ mod } 1

regardless of whether {N} is even or odd. A variant of this construction also works for {{\bf Z}}, and the general case follows from a short calculation verifying that the claim (ii) for any two groups {G_S, G'_S} implies the corresponding claim (ii) for the product {G_S \times G'_S}.

This concludes the Fourier-analytic proof of Theorem 1. In this paper we also give an ergodic theory proof of (a qualitative version of) Theorem 1(ii), using a correspondence principle argument adapted from this previous paper of Ziegler, and myself. Basically, the idea is to randomly generate a dynamical system on the group {G}, by selecting an infinite number of random shifts {g_1, g_2, \dots \in G}, which induces an action of the infinitely generated free abelian group {{\bf Z}^\omega = \bigcup_{n=1}^\infty {\bf Z}^n} on {G} by the formula

\displaystyle T^h x := x + \sum_{i=1}^\infty h_i g_i.

Much as the law of large numbers ensures the almost sure convergence of Monte Carlo integration, one can show that this action is almost surely ergodic (after passing to a suitable Furstenberg-type limit {X} where the size of {G} goes to infinity), and that the dynamical Host-Kra-Gowers seminorms of that system coincide with the combinatorial Gowers norms of the original functions. One is then well placed to apply an inverse theorem for the third Host-Kra-Gowers seminorm {U^3(X)} for {{\bf Z}^\omega}-actions, which was accomplished in the companion paper to this one. After doing so, one almost gets the desired conclusion of Theorem 1(ii), except that after undoing the application of the Furstenberg correspondence principle, the map {g: G \rightarrow H/\Lambda} is merely an almost polynomial rather than a polynomial, which roughly speaking means that instead of certain derivatives of {g} vanishing, they instead are merely very small outside of a small exceptional set. To conclude we need to invoke a “stability of polynomials” result, which at this level of generality was first established by Candela and Szegedy (though we also provide an independent proof here in an appendix), which roughly speaking asserts that every approximate polynomial is close in measure to an actual polynomial. (This general strategy is also employed in the Candela-Szegedy paper, though in the absence of the ergodic inverse theorem input that we rely upon here, the conclusion is weaker in that the filtered nilmanifold {H/\Lambda} is replaced with a general space known as a “CFR nilspace”.)

This transference principle approach seems to work well for the higher step cases (for instance, the stability of polynomials result is known in arbitrary degree); the main difficulty is to establish a suitable higher step inverse theorem in the ergodic theory setting, which we hope to do in future research.

The structure of arbitrary Conze-Lesigne systems

6 December, 2021 in math.DS, paper | Tags: , , , , | by | 9 comments

Asgar Jamneshan, Or Shalom, and myself have just uploaded to the arXiv our preprint “The structure of arbitrary Conze–Lesigne systems“. As the title suggests, this paper is devoted to the structural classification of Conze-Lesigne systems, which are a type of measure-preserving system that are “quadratic” or of “complexity two” in a certain technical sense, and are of importance in the theory of multiple recurrence. There are multiple ways to define such systems; here is one. Take a countable abelian group {\Gamma} acting in a measure-preserving fashion on a probability space {(X,\mu)}, thus each group element {\gamma \in \Gamma} gives rise to a measure-preserving map {T^\gamma: X \rightarrow X}. Define the third Gowers-Host-Kra seminorm {\|f\|_{U^3(X)}} of a function {f \in L^\infty(X)} via the formula

\displaystyle \|f\|_{U^3(X)}^8 := \lim_{n \rightarrow \infty} {\bf E}_{h_1,h_2,h_3 \in \Phi_n} \int_X \prod_{\omega_1,\omega_2,\omega_3 \in \{0,1\}}

\displaystyle {\mathcal C}^{\omega_1+\omega_2+\omega_3} f(T^{\omega_1 h_1 + \omega_2 h_2 + \omega_3 h_3} x)\ d\mu(x)

where {\Phi_n} is a Folner sequence for {\Gamma} and {{\mathcal C}: z \mapsto \overline{z}} is the complex conjugation map. One can show that this limit exists and is independent of the choice of Folner sequence, and that the {\| \|_{U^3(X)}} seminorm is indeed a seminorm. A Conze-Lesigne system is an ergodic measure-preserving system in which the {U^3(X)} seminorm is in fact a norm, thus {\|f\|_{U^3(X)}>0} whenever {f \in L^\infty(X)} is non-zero. Informally, this means that when one considers a generic parallelepiped in a Conze–Lesigne system {X}, the location of any vertex of that parallelepiped is more or less determined by the location of the other seven vertices. These are the important systems to understand in order to study “complexity two” patterns, such as arithmetic progressions of length four. While not all systems {X} are Conze-Lesigne systems, it turns out that they always have a maximal factor {Z^2(X)} that is a Conze-Lesigne system, known as the Conze-Lesigne factor or the second Host-Kra-Ziegler factor of the system, and this factor controls all the complexity two recurrence properties of the system.

The analogous theory in complexity one is well understood. Here, one replaces the {U^3(X)} norm by the {U^2(X)} norm

\displaystyle \|f\|_{U^2(X)}^4 := \lim_{n \rightarrow \infty} {\bf E}_{h_1,h_2 \in \Phi_n} \int_X \prod_{\omega_1,\omega_2 \in \{0,1\}} {\mathcal C}^{\omega_1+\omega_2} f(T^{\omega_1 h_1 + \omega_2 h_2} x)\ d\mu(x)

and the ergodic systems for which {U^2} is a norm are called Kronecker systems. These systems are completely classified: a system is Kronecker if and only if it arises from a compact abelian group {Z} equipped with Haar probability measure and a translation action {T^\gamma \colon z \mapsto z + \phi(\gamma)} for some homomorphism {\phi: \Gamma \rightarrow Z} with dense image. Such systems can then be analyzed quite efficiently using the Fourier transform, and this can then be used to satisfactory analyze “complexity one” patterns, such as length three progressions, in arbitrary systems (or, when translated back to combinatorial settings, in arbitrary dense sets of abelian groups).

We return now to the complexity two setting. The most famous examples of Conze-Lesigne systems are (order two) nilsystems, in which the space {X} is a quotient {G/\Lambda} of a two-step nilpotent Lie group {G} by a lattice {\Lambda} (equipped with Haar probability measure), and the action is given by a translation {T^\gamma x = \phi(\gamma) x} for some group homomorphism {\phi: \Gamma \rightarrow G}. For instance, the Heisenberg {{\bf Z}}-nilsystem

\displaystyle \begin{pmatrix} 1 & {\bf R} & {\bf R} \\ 0 & 1 & {\bf R} \\ 0 & 0 & 1 \end{pmatrix} / \begin{pmatrix} 1 & {\bf Z} & {\bf Z} \\ 0 & 1 & {\bf Z} \\ 0 & 0 & 1 \end{pmatrix}

with a shift of the form

\displaystyle Tx = \begin{pmatrix} 1 & \alpha & 0 \\ 0 & 1 & \beta \\ 0 & 0 & 1 \end{pmatrix} x

for {\alpha,\beta} two real numbers with {1,\alpha,\beta} linearly independent over {{\bf Q}}, is a Conze-Lesigne system. As the base case of a well known result of Host and Kra, it is shown in fact that all Conze-Lesigne {{\bf Z}}-systems are inverse limits of nilsystems (previous results in this direction were obtained by Conze-Lesigne, Furstenberg-Weiss, and others). Similar results are known for {\Gamma}-systems when {\Gamma} is finitely generated, thanks to the thesis work of Griesmer (with further proofs by Gutman-Lian and Candela-Szegedy). However, this is not the case once {\Gamma} is not finitely generated; as a recent example of Shalom shows, Conze-Lesigne systems need not be the inverse limit of nilsystems in this case.

Our main result is that even in the infinitely generated case, Conze-Lesigne systems are still inverse limits of a slight generalisation of the nilsystem concept, in which {G} is a locally compact Polish group rather than a Lie group:

Theorem 1 (Classification of Conze-Lesigne systems) Let {\Gamma} be a countable abelian group, and {X} an ergodic measure-preserving {\Gamma}-system. Then {X} is a Conze-Lesigne system if and only if it is the inverse limit of translational systems {G/\Lambda}, where {G} is a nilpotent locally compact Polish group of nilpotency class two, and {\Lambda} is a lattice in {G} (and also a lattice in the commutator group {[G,G]}), with {G/\Lambda} equipped with the Haar probability measure and a translation action {T^\gamma x = \phi(\gamma) x} for some homomorphism {\phi: \Gamma \rightarrow G}.

In a forthcoming companion paper to this one, Asgar Jamneshan and I will use this theorem to derive an inverse theorem for the Gowers norm {U^3(G)} for an arbitrary finite abelian group {G} (with no restrictions on the order of {G}, in particular our result handles the case of even and odd {|G|} in a unified fashion). In principle, having a higher order version of this theorem will similarly allow us to derive inverse theorems for {U^{s+1}(G)} norms for arbitrary {s} and finite abelian {G}; we hope to investigate this further in future work.

We sketch some of the main ideas used to prove the theorem. The existing machinery developed by Conze-Lesigne, Furstenberg-Weiss, Host-Kra, and others allows one to describe an arbitrary Conze-Lesigne system as a group extension {Z \rtimes_\rho K}, where {Z} is a Kronecker system (a rotational system on a compact abelian group {Z = (Z,+)} and translation action {\phi: \Gamma \rightarrow Z}), {K = (K,+)} is another compact abelian group, and the cocycle {\rho = (\rho_\gamma)_{\gamma \in \Gamma}} is a collection of measurable maps {\rho_\gamma: Z \rightarrow K} obeying the cocycle equation

\displaystyle \rho_{\gamma_1+\gamma_2}(x) = \rho_{\gamma_1}(T^{\gamma_2} x) + \rho_{\gamma_2}(x) \ \ \ \ \ (1)

for almost all {x \in Z}. Furthermore, {\rho} is of “type two”, which means in this concrete setting that it obeys an additional equation

\displaystyle \rho_\gamma(x + z_1 + z_2) - \rho_\gamma(x+z_1) - \rho_\gamma(x+z_2) + \rho_\gamma(x) \ \ \ \ \ (2)

\displaystyle = F(x + \phi(\gamma), z_1, z_2) - F(x,z_1,z_2)

for all {\gamma \in \Gamma} and almost all {x,z_1,z_2 \in Z}, and some measurable function {F: Z^3 \rightarrow K}; roughly speaking this asserts that {\phi_\gamma} is “linear up to coboundaries”. For technical reasons it is also convenient to reduce to the case where {Z} is separable. The problem is that the equation (2) is unwieldy to work with. In the model case when the target group {K} is a circle {{\bf T} = {\bf R}/{\bf Z}}, one can use some Fourier analysis to convert (2) into the more tractable Conze-Lesigne equation

\displaystyle \rho_\gamma(x+z) - \rho_\gamma(x) = F_z(x+\phi(\gamma)) - F_z(x) + c_z(\gamma) \ \ \ \ \ (3)

 for all {\gamma \in \Gamma}, all {z \in Z}, and almost all {x \in Z}, where for each {z}, {F_z: Z \rightarrow K} is a measurable function, and {c_z: \Gamma \rightarrow K} is a homomorphism. (For technical reasons it is often also convenient to enforce that {F_z, c_z} depend in a measurable fashion on {z}; this can always be achieved, at least when the Conze-Lesigne system is separable, but actually verifying that this is possible actually requires a certain amount of effort, which we devote an appendix to in our paper.) It is not difficult to see that (3) implies (2) for any group {K} (as long as one has the measurability in {z} mentioned previously), but the converse turns out to fail for some groups {K}, such as solenoid groups (e.g., inverse limits of {{\bf R}/2^n{\bf Z}} as {n \rightarrow \infty}), as was essentially shown by Rudolph. However, in our paper we were able to find a separate argument that also derived the Conze-Lesigne equation in the case of a cyclic group {K = \frac{1}{N}{\bf Z}/{\bf Z}}. Putting together the {K={\bf T}} and {K = \frac{1}{N}{\bf Z}/{\bf Z}} cases, one can then derive the Conze-Lesigne equation for arbitrary compact abelian Lie groups {K} (as such groups are isomorphic to direct products of finitely many tori and cyclic groups). As has been known for some time (see e.g., this paper of Host and Kra), once one has a Conze-Lesigne equation, one can more or less describe the system {X} as a translational system {G/\Lambda}, where the Host-Kra group {G} is the set of all pairs {(z, F_z)} that solve an equation of the form (3) (with these pairs acting on {X \equiv Z \rtimes_\rho K} by the law {(z,F_z) \cdot (x,k) := (x+z, k+F_z(x))}), and {\Lambda} is the stabiliser of a point in this system. This then establishes the theorem in the case when {K} is a Lie group, and the general case basically comes from the fact (from Fourier analysis or the Peter-Weyl theorem) that an arbitrary compact abelian group is an inverse limit of Lie groups. (There is a technical issue here in that one has to check that the space of translational system factors of {X} form a directed set in order to have a genuine inverse limit, but this can be dealt with by modifications of the tools mentioned here.)

There is an additional technical issue worth pointing out here (which unfortunately was glossed over in some previous work in the area). Because the cocycle equation (1) and the Conze-Lesigne equation (3) are only valid almost everywhere instead of everywhere, the action of {G} on {X} is technically only a near-action rather than a genuine action, and as such one cannot directly define {\Lambda} to be the stabiliser of a point without running into multiple problems. To fix this, one has to pass to a topological model of {X} in which the action becomes continuous, and the stabilizer becomes well defined, although one then has to work a little more to check that the action is still transitive. This can be done via Gelfand duality; we proceed using a mixture of a construction from this book of Host and Kra, and the machinery in this recent paper of Asgar and myself.

Now we discuss how to establish the Conze-Lesigne equation (3) in the cyclic group case {K = \frac{1}{N}{\bf Z}/{\bf Z}}. As this group embeds into the torus {{\bf T}}, it is easy to use existing methods obtain (3) but with the homomorphism {c_z} and the function {F_z} taking values in {{\bf R}/{\bf Z}} rather than in {\frac{1}{N}{\bf Z}/{\bf Z}}. The main task is then to fix up the homomorphism {c_z} so that it takes values in {\frac{1}{N}{\bf Z}/{\bf Z}}, that is to say that {Nc_z} vanishes. This only needs to be done locally near the origin, because the claim is easy when {z} lies in the dense subgroup {\phi(\Gamma)} of {Z}, and also because the claim can be shown to be additive in {z}. Near the origin one can leverage the Steinhaus lemma to make {c_z} depend linearly (or more precisely, homomorphically) on {z}, and because the cocycle {\rho} already takes values in {\frac{1}{N}{\bf Z}/{\bf Z}}, {N\rho} vanishes and {Nc_z} must be an eigenvalue of the system {Z}. But as {Z} was assumed to be separable, there are only countably many eigenvalues, and by another application of Steinhaus and linearity one can then make {Nc_z} vanish on an open neighborhood of the identity, giving the claim.

Archives