Category Archive

You are currently browsing the category archive for the ‘math.DS’ category.

Notes on the B+B+t theorem

24 April, 2024 in expository, math.CO, math.DS | Tags: Bryna Kra, Donald Robertson, Ethan Acklesberg, Florian Richter, infinitary mathematics, Joel Moreira, sumsets | by Terence Tao | 1 comment

A recent paper of Kra, Moreira, Richter, and Robertson established the following theorem, resolving a question of Erdös. Given a discrete amenable group ${G = (G,+)}$ , and a subset ${A}$ of ${G}$ , we define the Banach density of ${A}$ to be the quantity

$\displaystyle \sup_\Phi \limsup_{N \rightarrow \infty} |A \cap \Phi_N|/|\Phi_N|,$

where the supremum is over all Følner sequences ${\Phi = (\Phi_N)_{N=1}^\infty}$ of ${G}$ . Given a set ${B}$ in ${G}$ , we define the restricted sumset ${B \oplus B}$ to be the set of all pairs ${b_1+b_2}$ where ${b_1, b_2}$ are distinct elements of ${B}$ .

Theorem 1 Let ${G}$ be a countably infinite abelian group with the index ${[G:2G]}$ finite. Let ${A}$ be a positive Banach density subset of ${G}$ . Then there exists an infinite set ${B \subset A}$ and ${t \in G}$ such that ${B \oplus B + t \subset A}$ .

Strictly speaking, the main result of Kra et al. only claims this theorem for the case of the integers ${G={\bf Z}}$ , but as noted in the recent preprint of Charamaras and Mountakis, the argument in fact applies for all countable abelian ${G}$ in which the subgroup ${2G := \{ 2x: x \in G \}}$ has finite index. This condition is in fact necessary (as observed by forthcoming work of Ethan Acklesberg): if ${2G}$ has infinite index, then one can find a subgroup ${H_j}$ of ${G}$ of index ${2^j}$ for any ${j \geq 1}$ that contains ${2G}$ (or equivalently, ${G/H_j}$ is ${2}$ -torsion). If one lets ${y_1,y_2,\dots}$ be an enumeration of ${G}$ , and one can then check that the set

$\displaystyle A := G \backslash \bigcup_{j=1}^\infty (H_{j+1} + y_j) \backslash \{y_1,\dots,y_j\}$

has positive Banach density, but does not contain any set of the form ${B \oplus B + t}$ for any ${t}$ (indeed, from the pigeonhole principle and the ${2}$ -torsion nature of ${G/H_{j+1}}$ one can show that ${B \oplus B + y_j}$ must intersect ${H_{j+1} + y_j \backslash \{y_1,\dots,y_j\}}$ whenever ${B}$ has cardinality larger than ${j 2^{j+1}}$ ). It is also necessary to work with restricted sums ${B \oplus B}$ rather than full sums ${B+B}$ : a counterexample to the latter is provided for instance by the example with ${G = {\bf Z}}$ and ${A := \bigcup_{j=1}^\infty [10^j, 1.1 \times 10^j]}$ . Finally, the presence of the shift ${t}$ is also necessary, as can be seen by considering the example of ${A}$ being the odd numbers in ${G ={\bf Z}}$ , though in the case ${G=2G}$ one can of course delete the shift ${t}$ at the cost of giving up the containment ${B \subset A}$ .

Theorem 1 resembles other theorems in density Ramsey theory, such as Szemerédi’s theorem, but with the notable difference that the pattern located in the dense set ${A}$ is infinite rather than merely arbitrarily large but finite. As such, it does not seem that this theorem can be proven by purely finitary means. However, one can view this result as the conjunction of an infinite number of statements, each of which is a finitary density Ramsey theory statement. To see this, we need some more notation. Observe from Tychonoff’s theorem that the collection ${2^G := \{ B: B \subset G \}}$ is a compact topological space (with the topology of pointwise convergence) (it is also metrizable since ${G}$ is countable). Subsets ${{\mathcal F}}$ of ${2^G}$ can be thought of as properties of subsets of ${G}$ ; for instance, the property a subset ${B}$ of ${G}$ of being finite is of this form, as is the complementary property of being infinite. A property of subsets of ${G}$ can then be said to be closed or open if it corresponds to a closed or open subset of ${2^G}$ . Thus, a property is closed and only if if it is closed under pointwise limits, and a property is open if, whenever a set ${B}$ has this property, then any other set ${B'}$ that shares a sufficiently large (but finite) initial segment with ${B}$ will also have this property. Since ${2^G}$ is compact and Hausdorff, a property is closed if and only if it is compact.

The properties of being finite or infinite are neither closed nor open. Define a smallness property to be a closed (or compact) property of subsets of ${G}$ that is only satisfied by finite sets; the complement to this is a largeness property, which is an open property of subsets of ${G}$ that is satisfied by all infinite sets. (One could also choose to impose other axioms on these properties, for instance requiring a largeness property to be an upper set, but we will not do so here.) Examples of largeness properties for a subset ${B}$ of ${G}$ include:

${B}$ has at least ${10}$ elements.
${B}$ is non-empty and has at least ${b_1}$ elements, where ${b_1}$ is the smallest element of ${B}$ .
${B}$ is non-empty and has at least ${b_{b_1}}$ elements, where ${b_n}$ is the ${n^{\mathrm{th}}}$ element of ${B}$ .
${T}$ halts when given ${B}$ as input, where ${T}$ is a given Turing machine that halts whenever given an infinite set as input. (Note that this encompasses the preceding three examples as special cases, by selecting ${T}$ appropriately.)

We will call a set obeying a largeness property ${{\mathcal P}}$ an ${{\mathcal P}}$ -large set.

Theorem 1 is then equivalent to the following “almost finitary” version (cf. this previous discussion of almost finitary versions of the infinite pigeonhole principle):

Theorem 2 (Almost finitary form of main theorem) Let ${G}$ be a countably infinite abelian group with ${[G:2G]}$ finite. Let ${\Phi_n}$ be a Følner sequence in ${G}$ , let ${\delta>0}$ , and let ${{\mathcal P}_t}$ be a largeness property for each ${t \in G}$ . Then there exists ${N}$ such that if ${A \subset G}$ is such that ${|A \cap \Phi_n| / |\Phi_n| \geq \delta}$ for all ${n \leq N}$ , then there exists a shift ${t \in G}$ and ${A}$ contains a ${{\mathcal P}_t}$ -large set ${B}$ such that ${B \oplus B + t \subset A}$ .

Proof of Theorem 2 assuming Theorem 1. Let ${G, \Phi_n}$ , ${\delta}$ , ${{\mathcal P}_t}$ be as in Theorem 2. Suppose for contradiction that Theorem 2 failed, then for each ${N}$ we can find ${A_N}$ with ${|A_N \cap \Phi_n| / |\Phi_n| \geq \delta}$ for all ${n \leq N}$ , such that there is no ${t}$ and ${{\mathcal P}_t}$ -large ${B}$ such that ${B, B \oplus B + t \subset A_N}$ . By compactness, a subsequence of the ${A_N}$ converges pointwise to a set ${A}$ , which then has Banach density at least ${\delta}$ . By Theorem 1, there is an infinite set ${B}$ and a ${t}$ such that ${B, B \oplus B + t \subset A}$ . By openness, we conclude that there exists a finite ${{\mathcal P}_t}$ -large set ${B'}$ contained in ${B}$ , thus ${B', B' \oplus B' + t \subset A}$ . This implies that ${B', B' \oplus B' + t \subset A_N}$ for infinitely many ${N}$ , a contradiction.

Proof of Theorem 1 assuming Theorem 2. Let ${G, A}$ be as in Theorem 1. If the claim failed, then for each ${t}$ , the property ${{\mathcal P}_t}$ of being a set ${B}$ for which ${B, B \oplus B + t \subset A}$ would be a smallness property. By Theorem 2, we see that there is a ${t}$ and a ${B}$ obeying the complement of this property such that ${B, B \oplus B + t \subset A}$ , a contradiction.

Remark 3 Define a relation ${R}$ between ${2^G}$ and ${2^G \times G}$ by declaring ${A\ R\ (B,t)}$ if ${B \subset A}$ and ${B \oplus B + t \subset A}$ . The key observation that makes the above equivalences work is that this relation is continuous in the sense that if ${U}$ is an open subset of ${2^G \times G}$ , then the inverse image
$\displaystyle R^{-1} U := \{ A \in 2^G: A\ R\ (B,t) \hbox{ for some } (B,t) \in U \}$
is also open. Indeed, if ${A\ R\ (B,t)}$ for some ${(B,t) \in U}$ , then ${B}$ contains a finite set ${B'}$ such that ${(B',t) \in U}$ , and then any ${A'}$ that contains both ${B'}$ and ${B' \oplus B' + t}$ lies in ${R^{-1} U}$ .

For each specific largeness property, such as the examples listed previously, Theorem 2 can be viewed as a finitary assertion (at least if the property is “computable” in some sense), but if one quantifies over all largeness properties, then the theorem becomes infinitary. In the spirit of the Paris-Harrington theorem, I would in fact expect some cases of Theorem 2 to undecidable statements of Peano arithmetic, although I do not have a rigorous proof of this assertion.

Despite the complicated finitary interpretation of this theorem, I was still interested in trying to write the proof of Theorem 1 in some sort of “pseudo-finitary” manner, in which one can see analogies with finitary arguments in additive combinatorics. The proof of Theorem 1 that I give below the fold is my attempt to achieve this, although to avoid a complete explosion of “epsilon management” I will still use at one juncture an ergodic theory reduction from the original paper of Kra et al. that relies on such infinitary tools as the ergodic decomposition, the ergodic theory, and the spectral theorem. Also some of the steps will be a little sketchy, and assume some familiarity with additive combinatorics tools (such as the arithmetic regularity lemma).

Read the rest of this entry »

A Host–Kra F^omega_2-system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the U^6(F^n_2) norm; The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the U^k Gowers uniformity norms on finite abelian groups of bounded torsion

10 March, 2023 in math.CO, math.DS, paper | Tags: Asgar Jamneshan, Gowers uniformity norms, Gowers-Host-Kra seminorms, inverse conjecture for the Gowers norm, Or Shalom | by Terence Tao | 3 comments

Asgar Jamneshan, Or Shalom, and myself have just uploaded to the arXiv our preprints “A Host–Kra ${{\bf F}^\omega_2}$ -system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the ${U^6({\bf F}^n_2)}$ norm” and “The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the ${U^k}$ Gowers uniformity norms on finite abelian groups of bounded torsion“. These two papers are both concerned with advancing the inverse theory for the Gowers norms and Gowers-Host-Kra seminorms; the first paper provides a counterexample in this theory (in particular disproving a conjecture of Bergelson, Ziegler and myself), and the second paper gives new positive results in the case when the underlying group is bounded torsion, or the ergodic system is totally disconnected. I discuss the two papers more below the fold.

Read the rest of this entry »

Measurable tilings by abelian group actions

3 March, 2022 in math.DS, math.MG, paper | Tags: Jan Grebik, Rachel Greenfeld, tiling, Vaclav Rozhon | by Terence Tao | 9 comments

Jan Grebik, Rachel Greenfeld, Vaclav Rozhon and I have just uploaded to the arXiv our preprint “Measurable tilings by abelian group actions“. This paper is related to an earlier paper of Rachel Greenfeld and myself concerning tilings of lattices ${{\bf Z}^d}$ , but now we consider the more general situation of tiling a measure space ${X}$ by a tile ${A \subset X}$ shifted by a finite subset ${F}$ of shifts of an abelian group ${G = (G,+)}$ that acts in a measure-preserving (or at least quasi-measure-preserving) fashion on ${X}$ . For instance, ${X}$ could be a torus ${{\bf T}^d = {\bf R}^d/{\bf Z}^d}$ , ${A}$ could be a positive measure subset of that torus, and ${G}$ could be the group ${{\bf R}^d}$ , acting on ${X}$ by translation.

If ${F}$ is a finite subset of ${G}$ with the property that the translates ${f+A}$ , ${f \in F}$ of ${A \subset X}$ partition ${X}$ up to null sets, we write ${F \oplus A =_{a.e.} X}$ , and refer to this as a measurable tiling of ${X}$ by ${A}$ (with tiling set ${F}$ ). For instance, if ${X}$ is the torus ${{\bf T}^2}$ , we can create a measurable tiling with ${A = [0,1/2]^2 \hbox{ mod } {\bf Z}^2}$ and ${F = \{0,1/2\}^2}$ . Our main results are the following:

By modifying arguments from previous papers (including the one with Greenfeld mentioned above), we can establish the following “dilation lemma”: a measurable tiling ${F \oplus A =_{a.e.} X}$ automatically implies further measurable tilings ${rF \oplus A =_{a.e.} X}$ , whenever ${r}$ is an integer coprime to all primes up to the cardinality ${\# F}$ of ${F}$ .
By averaging the above dilation lemma, we can also establish a “structure theorem” that decomposes the indicator function ${1_A}$ of ${A}$ into components, each of which are invariant with respect to a certain shift in ${G}$ . We can establish this theorem in the case of measure-preserving actions on probability spaces via the ergodic theorem, but one can also generalize to other settings by using the device of “measurable medial means” (which relates to the concept of a universally measurable set).
By applying this structure theorem, we can show that all measurable tilings ${F \oplus A = {\bf T}^1}$ of the one-dimensional torus ${{\bf T}^1}$ are rational, in the sense that ${F}$ lies in a coset of the rationals ${{\bf Q} = {\bf Q}^1}$ . This answers a recent conjecture of Conley, Grebik, and Pikhurko; we also give an alternate proof of this conjecture using some previous results of Lagarias and Wang.
For tilings ${F \oplus A = {\bf T}^d}$ of higher-dimensional tori, the tiling need not be rational. However, we can show that we can “slide” the tiling to be rational by giving each translate ${f + A}$ of ${A}$ a “velocity” ${v_f \in {\bf R}^d}$ , and for every time ${t}$ , the translates ${f + tv_f + A}$ still form a partition of ${{\bf T}^d}$ modulo null sets, and at time ${t=1}$ the tiling becomes rational. In particular, if a set ${A}$ can tile a torus in an irrational fashion, then it must also be able to tile the torus in a rational fashion.
In the two-dimensional case ${d=2}$ one can arrange matters so that all the velocities ${v_f}$ are parallel. If we furthermore assume that the tile ${A}$ is connected, we can also show that the union of all the translates ${f+A}$ with a common velocity ${v_f = v}$ form a ${v}$ -invariant subset of the torus.
Finally, we show that tilings ${F \oplus A = {\bf Z}^d \times G}$ of a finitely generated discrete group ${{\bf Z}^d \times G}$ , with ${G}$ a finite group, cannot be constructed in a “local” fashion (we formalize this probabilistically using the notion of a “factor of iid process”) unless the tile ${F}$ is contained in a single coset of ${\{0\} \times G}$ . (Nonabelian local tilings, for instance of the sphere by rotations, are of interest due to connections with the Banach-Tarski paradox; see the aforementioned paper of Conley, Grebik, and Pikhurko. Unfortunately, our methods seem to break down completely in the nonabelian case.)

The structure of arbitrary Conze-Lesigne systems

6 December, 2021 in math.DS, paper | Tags: Asgar Jamneshan, characteristic factor, cocycles, Conze-Lesigne system, Or Shalom | by Terence Tao | 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.

The Gowers uniformity norm of order 1+

25 July, 2021 in expository, math.CA, math.CO, math.DS | Tags: arithmetic progressions, Gowers uniformity norms, polynomial recurrence, randomness | by Terence Tao | 25 comments

In the modern theory of higher order Fourier analysis, a key role are played by the Gowers uniformity norms ${\| \|_{U^k}}$ for ${k=1,2,\dots}$ . For finitely supported functions ${f: {\bf Z} \rightarrow {\bf C}}$ , one can define the (non-normalised) Gowers norm ${\|f\|_{\tilde U^k({\bf Z})}}$ by the formula

$\displaystyle \|f\|_{\tilde U^k({\bf Z})}^{2^k} := \sum_{n,h_1,\dots,h_k \in {\bf Z}} \prod_{\omega_1,\dots,\omega_k \in \{0,1\}} {\mathcal C}^{\omega_1+\dots+\omega_k} f(x+\omega_1 h_1 + \dots + \omega_k h_k)$

where ${{\mathcal C}}$ denotes complex conjugation, and then on any discrete interval ${[N] = \{1,\dots,N\}}$ and any function ${f: [N] \rightarrow {\bf C}}$ we can then define the (normalised) Gowers norm

$\displaystyle \|f\|_{U^k([N])} := \| f 1_{[N]} \|_{\tilde U^k({\bf Z})} / \|1_{[N]} \|_{\tilde U^k({\bf Z})}$

where ${f 1_{[N]}: {\bf Z} \rightarrow {\bf C}}$ is the extension of ${f}$ by zero to all of ${{\bf Z}}$ . Thus for instance

$\displaystyle \|f\|_{U^1([N])} = |\mathop{\bf E}_{n \in [N]} f(n)|$

(which technically makes ${\| \|_{U^1([N])}}$ a seminorm rather than a norm), and one can calculate

$\displaystyle \|f\|_{U^2([N])} \asymp (N \int_0^1 |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)|^4\ d\alpha)^{1/4} \ \ \ \ \ (1)$

where ${e(\theta) := e^{2\pi i \alpha}}$ , and we use the averaging notation ${\mathop{\bf E}_{n \in A} f(n) = \frac{1}{|A|} \sum_{n \in A} f(n)}$ .

The significance of the Gowers norms is that they control other multilinear forms that show up in additive combinatorics. Given any polynomials ${P_1,\dots,P_m: {\bf Z}^d \rightarrow {\bf Z}}$ and functions ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$ , we define the multilinear form

$\displaystyle \Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m) := \sum_{n \in {\bf Z}^d} \prod_{j=1}^m f_j 1_{[N]}(P_j(n)) / \sum_{n \in {\bf Z}^d} \prod_{j=1}^m 1_{[N]}(P_j(n))$

(assuming that the denominator is finite and non-zero). Thus for instance

$\displaystyle \Lambda^{\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N]} f(n)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}}(f,g) = (\mathop{\bf E}_{n \in [N]} f(n)) (\mathop{\bf E}_{n \in [N]} g(n))$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N,N]} f(n) g(n+r) h(n+2r)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N^{1/2},N^{1/2}]} f(n) g(n+r) h(n+r^2)$

where we view ${\mathrm{n}, \mathrm{r}}$ as formal (indeterminate) variables, and ${f,g,h: [N] \rightarrow {\bf C}}$ are understood to be extended by zero to all of ${{\bf Z}}$ . These forms are used to count patterns in various sets; for instance, the quantity ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(1_A,1_A,1_A)}$ is closely related to the number of length three arithmetic progressions contained in ${A}$ . Let us informally say that a form ${\Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m)}$ is controlled by the ${U^k[N]}$ norm if the form is small whenever ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$ are ${1}$ -bounded functions with at least one of the ${f_j}$ small in ${U^k[N]}$ norm. This definition was made more precise by Gowers and Wolf, who then defined the true complexity of a form ${\Lambda^{P_1,\dots,P_m}}$ to be the least ${s}$ such that ${\Lambda^{P_1,\dots,P_m}}$ is controlled by the ${U^{s+1}[N]}$ norm. For instance,

${\Lambda^{\mathrm{n}}}$ and ${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}}}$ have true complexity ${0}$ ;
${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}}}$ has true complexity ${1}$ ;
${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}, \mathrm{n} + \mathrm{3r}}}$ has true complexity ${2}$ ;
The form ${\Lambda^{\mathrm{n}, \mathrm{n}+2}}$ (which among other things could be used to count twin primes) has infinite true complexity (which is quite unfortunate for applications).

Roughly speaking, patterns of complexity ${1}$ or less are amenable to being studied by classical Fourier analytic tools (the Hardy-Littlewood circle method); patterns of higher complexity can be handled (in principle, at least) by the methods of higher order Fourier analysis; and patterns of infinite complexity are out of range of both methods and are generally quite difficult to study. See these recent slides of myself (or this video of the lecture) for some further discussion.

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

The ${U^1}$ (semi-)norm is so weak that it barely controls any averages at all. For instance the average

$\displaystyle \Lambda^{2\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N], \hbox{ even}} f(n)$

is not controlled by the ${U^1[N]}$ semi-norm: it is perfectly possible for a ${1}$ -bounded function ${f: [N] \rightarrow {\bf C}}$ to even have vanishing ${U^1([N])}$ norm but have large value of ${\Lambda^{2\mathrm{n}}(f)}$ (consider for instance the parity function ${f(n) := (-1)^n}$ ).

Because of this, I propose inserting an additional norm in the Gowers uniformity norm hierarchy between the ${U^1}$ and ${U^2}$ norms, which I will call the ${U^{1^+}}$ (or “profinite ${U^1}$ “) norm:

$\displaystyle \| f\|_{U^{1^+}[N]} := \frac{1}{N} \sup_P |\sum_{n \in P} f(n)| = \sup_P | \mathop{\bf E}_{n \in [N]} f 1_P(n)|$

where ${P}$ ranges over all arithmetic progressions in ${[N]}$ . This can easily be seen to be a norm on functions ${f: [N] \rightarrow {\bf C}}$ that controls the ${U^1[N]}$ norm. It is also basically controlled by the ${U^2[N]}$ norm for ${1}$ -bounded functions ${f}$ ; indeed, if ${P}$ is an arithmetic progression in ${[N]}$ of some spacing ${q \geq 1}$ , then we can write ${P}$ as the intersection of an interval ${I}$ with a residue class modulo ${q}$ , and from Fourier expansion we have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \sup_\alpha |\mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)|.$

If we let ${\psi}$ be a standard bump function supported on ${[-1,1]}$ with total mass and ${\delta>0}$ is a parameter then

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N})$

$\displaystyle 1_I(n+h+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle + \delta$

(extending ${f}$ by zero outside of ${[N]}$ ), as can be seen by using the triangle inequality and the estimate

$\displaystyle \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+h+k) - \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k)$

$\displaystyle \ll (1 + \mathrm{dist}(n+k, I) / \delta N)^{-2}.$

After some Fourier expansion of ${\delta \psi(\frac{h}{\delta N})}$ we now have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \sup_{\alpha,\beta} |\mathop{\bf E}_{n \in [N]; h, k \in [-N,N]} e(\beta h + \alpha (n+h+k))$

$\displaystyle 1_P(n+k) f(n+h+k)| + \delta.$

Writing ${\alpha h + \alpha(n+h+k)}$ as a linear combination of ${n, n+h, n+k}$ and using the Gowers–Cauchy–Schwarz inequality, we conclude

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \|f\|_{U^2([N])} + \delta$

hence on optimising in ${\delta}$ we have

$\displaystyle \| f\|_{U^{1^+}[N]} \ll \|f\|_{U^2[N]}^{1/2}.$

Forms which are controlled by the ${U^{1^+}}$ norm (but not ${U^1}$ ) would then have their true complexity adjusted to ${0^+}$ with this insertion.

The ${U^{1^+}}$ norm recently appeared implicitly in work of Peluse and Prendiville, who showed that the form ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h)}$ had true complexity ${0^+}$ in this notation (with polynomially strong bounds). [Actually, strictly speaking this control was only shown for the third function ${h}$ ; for the first two functions ${f,g}$ one needs to localize the ${U^{1^+}}$ norm to intervals of length ${\sim \sqrt{N}}$ . But I will ignore this technical point to keep the exposition simple.] The weaker claim that ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}^2}(f,g)}$ has true complexity ${0^+}$ is substantially easier to prove (one can apply the circle method together with Gauss sum estimates).

The well known inverse theorem for the ${U^2}$ norm tells us that if a ${1}$ -bounded function ${f}$ has ${U^2[N]}$ norm at least ${\eta}$ for some ${0 < \eta < 1}$ , then there is a Fourier phase ${n \mapsto e(\alpha n)}$ such that

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2;$

this follows easily from (1) and Plancherel’s theorem. Conversely, from the Gowers–Cauchy–Schwarz inequality one has

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \|f\|_{U^2[N]}.$

For ${U^1[N]}$ one has a trivial inverse theorem; by definition, the ${U^1[N]}$ norm of ${f}$ is at least ${\eta}$ if and only if

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n)| \geq \eta.$

Thus the frequency ${\alpha}$ appearing in the ${U^2}$ inverse theorem can be taken to be zero when working instead with the ${U^1}$ norm.

For ${U^{1^+}}$ one has the intermediate situation in which the frequency ${\alpha}$ is not taken to be zero, but is instead major arc. Indeed, suppose that ${f}$ is ${1}$ -bounded with ${\|f\|_{U^{1^+}[N]} \geq \eta}$ , thus

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_P(n) f(n)| \geq \eta$

for some progression ${P}$ . This forces the spacing ${q}$ of this progression to be ${\ll 1/\eta}$ . We write the above inequality as

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_{n=b\ (q)} 1_I(n) f(n)| \geq \eta$

for some residue class ${b\ (q)}$ and some interval ${I}$ . By Fourier expansion and the triangle inequality we then have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) 1_I(n) f(n)| \geq \eta$

for some integer ${a}$ . Convolving ${1_I}$ by ${\psi_\delta: n \mapsto \frac{1}{N\delta} \psi(\frac{n}{N\delta})}$ for ${\delta}$ a small multiple of ${\eta}$ and ${\psi}$ a Schwartz function of unit mass with Fourier transform supported on ${[-1,1]}$ , we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) (1_I * \psi_\delta)(n) f(n)| \gg \eta.$

The Fourier transform ${\xi \mapsto \sum_n 1_I * \psi_\delta(n) e(- \xi n)}$ of ${1_I * \psi_\delta}$ is bounded by ${O(N)}$ and supported on ${[-\frac{1}{\delta N},\frac{1}{\delta N}]}$ , thus by Fourier expansion and the triangle inequality we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) e(-\xi n) f(n)| \gg \eta^2$

for some ${\xi \in [-\frac{1}{\delta N},\frac{1}{\delta N}]}$ , so in particular ${\xi = O(\frac{1}{\eta N})}$ . Thus we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2 \ \ \ \ \ (2)$

for some ${\alpha}$ of the major arc form ${\alpha = \frac{a}{q} + O(1/\eta)}$ with ${1 \leq q \leq 1/\eta}$ . Conversely, for ${\alpha}$ of this form, some routine summation by parts gives the bound

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \frac{q}{\eta} \|f\|_{U^{1^+}[N]} \ll \frac{1}{\eta^2} \|f\|_{U^{1^+}[N]}$

so if (2) holds for a ${1}$ -bounded ${f}$ then one must have ${\|f\|_{U^{1^+}[N]} \gg \eta^4}$ .

Here is a diagram showing some of the control relationships between various Gowers norms, multilinear forms, and duals of classes ${{\mathcal F}}$ of functions (where each class of functions ${{\mathcal F}}$ induces a dual norm ${\| f \|_{{\mathcal F}^*} := \sup_{\phi \in {\mathcal F}} \mathop{\bf E}_{n \in[N]} f(n) \overline{\phi(n)}}$ :

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

The Gowers norms have counterparts for measure-preserving systems ${(X,T,\mu)}$ , known as Host-Kra seminorms. The ${U^1(X)}$ norm can be defined for ${f \in L^\infty(X)}$ as

$\displaystyle \|f\|_{U^1(X)} := \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^n f|\ d\mu$

and the ${U^2}$ norm can be defined as

$\displaystyle \|f\|_{U^2(X)}^4 := \lim_{N \rightarrow \infty} \mathop{\bf E}_{n \in [N]} \| T^n f \overline{f} \|_{U^1(X)}^2.$

The ${U^1(X)}$ seminorm is orthogonal to the invariant factor ${Z^0(X)}$ (generated by the (almost everywhere) invariant measurable subsets of ${X}$ ) in the sense that a function ${f \in L^\infty(X)}$ has vanishing ${U^1(X)}$ seminorm if and only if it is orthogonal to all ${Z^0(X)}$ -measurable (bounded) functions. Similarly, the ${U^2(X)}$ norm is orthogonal to the Kronecker factor ${Z^1(X)}$ , generated by the eigenfunctions of ${X}$ (that is to say, those ${f}$ obeying an identity ${Tf = \lambda f}$ for some ${T}$ -invariant ${\lambda}$ ); for ergodic systems, it is the largest factor isomorphic to rotation on a compact abelian group. In analogy to the Gowers ${U^{1^+}[N]}$ norm, one can then define the Host-Kra ${U^{1^+}(X)}$ seminorm by

$\displaystyle \|f\|_{U^{1^+}(X)} := \sup_{q \geq 1} \frac{1}{q} \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^{qn} f|\ d\mu;$

it is orthogonal to the profinite factor ${Z^{0^+}(X)}$ , generated by the periodic sets of ${X}$ (or equivalently, by those eigenfunctions whose eigenvalue is a root of unity); for ergodic systems, it is the largest factor isomorphic to rotation on a profinite abelian group.

An uncountable Mackey-Zimmer theorem

1 October, 2020 in math.DS, paper | Tags: abstract measure theory, Asgar Jamneshan, cocycles, group extensions, Mackey-Zimmer theorem, skew-products | by Terence Tao | 7 comments

Asgar Jamneshan and I have just uploaded to the arXiv our paper “An uncountable Mackey-Zimmer theorem“. This paper is part of our longer term project to develop “uncountable” versions of various theorems in ergodic theory; see this previous paper of Asgar and myself for the first paper in this series (and another paper will appear shortly).

In this case the theorem in question is the Mackey-Zimmer theorem, previously discussed in this blog post. This theorem gives an important classification of group and homogeneous extensions of measure-preserving systems. Let us first work in the (classical) setting of concrete measure-preserving systems. Let ${Y = (Y, \mu_Y, T_Y)}$ be a measure-preserving system for some group ${\Gamma}$ , thus ${(Y,\mu_Y)}$ is a (concrete) probability space and ${T_Y : \gamma \rightarrow T_Y^\gamma}$ is a group homomorphism from ${\Gamma}$ to the automorphism group ${\mathrm{Aut}(Y,\mu_Y)}$ of the probability space. (Here we are abusing notation by using ${Y}$ to refer both to the measure-preserving system and to the underlying set. In the notation of the paper we would instead distinguish these two objects as ${Y_{\mathbf{ConcPrb}_\Gamma}}$ and ${Y_{\mathbf{Set}}}$ respectively, reflecting two of the (many) categories one might wish to view ${Y}$ as a member of, but for sake of this informal overview we will not maintain such precise distinctions.) If ${K}$ is a compact group, we define a (concrete) cocycle to be a collection of measurable functions ${\rho_\gamma : Y \rightarrow K}$ for ${\gamma \in \Gamma}$ that obey the cocycle equation

$\displaystyle \rho_{\gamma \gamma'}(y) = \rho_\gamma(T_Y^{\gamma'} y) \rho_{\gamma'}(y) \ \ \ \ \ (1)$

for each ${\gamma,\gamma' \in \Gamma}$ and all ${y \in Y}$ . (One could weaken this requirement by only demanding the cocycle equation to hold for almost all ${y}$ , rather than all ${y}$ ; we will effectively do so later in the post, when we move to opposite probability algebra systems.) Any such cocycle generates a group skew-product ${X = Y \rtimes_\rho K}$ of ${Y}$ , which is another measure-preserving system ${(X, \mu_X, T_X)}$ where

${X = Y \times K}$ is the Cartesian product of ${Y}$ and ${K}$ ;
${\mu_X = \mu_Y \times \mathrm{Haar}_K}$ is the product measure of ${\mu_Y}$ and Haar probability measure on ${K}$ ; and
The action ${T_X: \gamma \rightarrow }$ is given by the formula
$\displaystyle T_X^\gamma(y,k) := (T_Y^\gamma y, \rho_\gamma(y) k). \ \ \ \ \ (2)$

The cocycle equation (1) guarantees that ${T_X}$ is a homomorphism, and the (left) invariance of Haar measure and Fubini’s theorem guarantees that the ${T_X^\gamma}$ remain measure preserving. There is also the more general notion of a homogeneous skew-product ${X \times Y \times_\rho K/L}$ in which the group ${K}$ is replaced by the homogeneous space ${K/L}$ for some closed subgroup of ${L}$ , noting that ${K/L}$ still comes with a left-action of ${K}$ and a Haar measure. Group skew-products are very “explicit” ways to extend a system ${Y}$ , as everything is described by the cocycle ${\rho}$ which is a relatively tractable object to manipulate. (This is not to say that the cohomology of measure-preserving systems is trivial, but at least there are many tools one can use to study them, such as the Moore-Schmidt theorem discussed in this previous post.)

This group skew-product ${X}$ comes with a factor map ${\pi: X \rightarrow Y}$ and a coordinate map ${\theta: X \rightarrow K}$ , which by (2) are related to the action via the identities

$\displaystyle \pi \circ T_X^\gamma = T_Y^\gamma \circ \pi \ \ \ \ \ (3)$

and

$\displaystyle \theta \circ T_X^\gamma = (\rho_\gamma \circ \pi) \theta \ \ \ \ \ (4)$

where in (4) we are implicitly working in the group of (concretely) measurable functions from ${Y}$ to ${K}$ . Furthermore, the combined map ${(\pi,\theta): X \rightarrow Y \times K}$ is measure-preserving (using the product measure on ${Y \times K}$ ), indeed the way we have constructed things this map is just the identity map.

We can now generalize the notion of group skew-product by just working with the maps ${\pi, \theta}$ , and weakening the requirement that ${(\pi,\theta)}$ be measure-preserving. Namely, define a group extension of ${Y}$ by ${K}$ to be a measure-preserving system ${(X,\mu_X, T_X)}$ equipped with a measure-preserving map ${\pi: X \rightarrow Y}$ obeying (3) and a measurable map ${\theta: X \rightarrow K}$ obeying (4) for some cocycle ${\rho}$ , such that the ${\sigma}$ -algebra of ${X}$ is generated by ${\pi,\theta}$ . There is also a more general notion of a homogeneous extension in which ${\theta}$ takes values in ${K/L}$ rather than ${K}$ . Then every group skew-product ${Y \rtimes_\rho K}$ is a group extension of ${Y}$ by ${K}$ , but not conversely. Here are some key counterexamples:

(i) If ${H}$ is a closed subgroup of ${K}$ , and ${\rho}$ is a cocycle taking values in ${H}$ , then ${Y \rtimes_\rho H}$ can be viewed as a group extension of ${Y}$ by ${K}$ , taking ${\theta: Y \rtimes_\rho H \rightarrow K}$ to be the vertical coordinate ${\theta(y,h) = h}$ (viewing ${h}$ now as an element of ${K}$ ). This will not be a skew-product by ${K}$ because ${(\theta,\pi)}$ pushes forward to the wrong measure on ${Y \times K}$ : it pushes forward to ${\mu_Y \times \mathrm{Haar}_H}$ rather than ${\mu_Y \times \mathrm{Haar}_K}$ .
(ii) If one takes the same example as (i), but twists the vertical coordinate ${\theta}$ to another vertical coordinate ${\tilde \theta(y,h) := \Phi(y) \theta(y,h)}$ for some measurable “gauge function” ${\Phi: Y \rightarrow K}$ , then ${Y \rtimes_\rho H}$ is still a group extension by ${K}$ , but now with the cocycle ${\rho}$ replaced by the cohomologous cocycle
$\displaystyle \tilde \rho_\gamma(y) := \Phi(T_Y^\gamma y) \rho_\gamma \Phi(y)^{-1}.$
Again, this will not be a skew product by ${K}$ , because ${(\theta,\pi)}$ pushes forward to a twisted version of ${\mu_Y \times \mathrm{Haar}_H}$ that is supported (at least in the case where ${Y}$ is compact and the cocycle ${\rho}$ is continuous) on the ${H}$ -bundle ${\bigcup_{y \in Y} \{y\} \times \Phi(y) H}$ .
(iii) With the situation as in (i), take ${X}$ to be the union ${X = Y \rtimes_\rho H \uplus Y \rtimes_\rho Hk \subset Y \times K}$ for some ${k \in K}$ outside of ${H}$ , where we continue to use the action (2) and the standard vertical coordinate ${\theta: (y,k) \mapsto k}$ but now use the measure ${\mu_Y \times (\frac{1}{2} \mathrm{Haar}_H + \frac{1}{2} \mathrm{Haar}_{Hk})}$ .

As it turns out, group extensions and homogeneous extensions arise naturally in the Furstenberg-Zimmer structural theory of measure-preserving systems; roughly speaking, every compact extension of ${Y}$ is an inverse limit of group extensions. It is then of interest to classify such extensions.

Examples such as (iii) are annoying, but they can be excluded by imposing the additional condition that the system ${(X,\mu_X,T_X)}$ is ergodic – all invariant (or essentially invariant) sets are of measure zero or measure one. (An essentially invariant set is a measurable subset ${E}$ of ${X}$ such that ${T^\gamma E}$ is equal modulo null sets to ${E}$ for all ${\gamma \in \Gamma}$ .) For instance, the system in (iii) is non-ergodic because the set ${Y \times H}$ (or ${Y \times Hk}$ ) is invariant but has measure ${1/2}$ . We then have the following fundamental result of Mackey and Zimmer:

Theorem 1 (Countable Mackey Zimmer theorem) Let ${\Gamma}$ be a group, ${Y}$ be a concrete measure-preserving system, and ${K}$ be a compact Hausdorff group. Assume that ${\Gamma}$ is at most countable, ${Y}$ is a standard Borel space, and ${K}$ is metrizable. Then every (concrete) ergodic group extension of ${Y}$ is abstractly isomorphic to a group skew-product (by some closed subgroup ${H}$ of ${K}$ ), and every (concrete) ergodic homogeneous extension of ${Y}$ is similarly abstractly isomorphic to a homogeneous skew-product.

We will not define precisely what “abstractly isomorphic” means here, but it roughly speaking means “isomorphic after quotienting out the null sets”. A proof of this theorem can be found for instance in .

The main result of this paper is to remove the “countability” hypotheses from the above theorem, at the cost of working with opposite probability algebra systems rather than concrete systems. (We will discuss opposite probability algebras in a subsequent blog post relating to another paper in this series.)

Theorem 2 (Uncountable Mackey Zimmer theorem) Let ${\Gamma}$ be a group, ${Y}$ be an opposite probability algebra measure-preserving system, and ${K}$ be a compact Hausdorff group. Then every (abstract) ergodic group extension of ${Y}$ is abstractly isomorphic to a group skew-product (by some closed subgroup ${H}$ of ${K}$ ), and every (abstract) ergodic homogeneous extension of ${Y}$ is similarly abstractly isomorphic to a homogeneous skew-product.

We plan to use this result in future work to obtain uncountable versions of the Furstenberg-Zimmer and Host-Kra structure theorems.

As one might expect, one locates a proof of Theorem 2 by finding a proof of Theorem 1 that does not rely too strongly on “countable” tools, such as disintegration or measurable selection, so that all of those tools can be replaced by “uncountable” counterparts. The proof we use is based on the one given in this previous post, and begins by comparing the system ${X}$ with the group extension ${Y \rtimes_\rho K}$ . As the examples (i), (ii) show, these two systems need not be isomorphic even in the ergodic case, due to the different probability measures employed. However one can relate the two after performing an additional averaging in ${K}$ . More precisely, there is a canonical factor map ${\Pi: X \rtimes_1 K \rightarrow Y \times_\rho K}$ given by the formula

$\displaystyle \Pi(x, k) := (\pi(x), \theta(x) k).$

This is a factor map not only of ${\Gamma}$ -systems, but actually of ${\Gamma \times K^{op}}$ -systems, where the opposite group ${K^{op}}$ to ${K}$ acts (on the left) by right-multiplication of the second coordinate (this reversal of order is why we need to use the opposite group here). The key point is that the ergodicity properties of the system ${Y \times_\rho K}$ are closely tied the group ${H}$ that is “secretly” controlling the group extension. Indeed, in example (i), the invariant functions on ${Y \times_\rho K}$ take the form ${(y,k) \mapsto f(Hk)}$ for some measurable ${f: H \backslash K \rightarrow {\bf C}}$ , while in example (ii), the invariant functions on ${Y \times_{\tilde \rho} K}$ take the form ${(y,k) \mapsto f(H \Phi(y)^{-1} k)}$ . In either case, the invariant factor is isomorphic to ${H \backslash K}$ , and can be viewed as a factor of the invariant factor of ${X \rtimes_1 K}$ , which is isomorphic to ${K}$ . Pursuing this reasoning (using an abstract ergodic theorem of Alaoglu and Birkhoff, as discussed in the previous post) one obtains the Mackey range ${H}$ , and also obtains the quotient ${\tilde \Phi: Y \rightarrow K/H}$ of ${\Phi: Y \rightarrow K}$ to ${K/H}$ in this process. The main remaining task is to lift the quotient ${\tilde \Phi}$ back up to a map ${\Phi: Y \rightarrow K}$ that stays measurable, in order to “untwist” a system that looks like (ii) to make it into one that looks like (i). In countable settings this is where a “measurable selection theorem” would ordinarily be invoked, but in the uncountable setting such theorems are not available for concrete maps. However it turns out that they still remain available for abstract maps: any abstractly measurable map ${\tilde \Phi}$ from ${Y}$ to ${K/H}$ has an abstractly measurable lift from ${Y}$ to ${K}$ . To prove this we first use a canonical model for opposite probability algebras (which we will discuss in a companion post to this one, to appear shortly) to work with continuous maps (on a Stone space) rather than abstractly measurable maps. The measurable map ${\tilde \Phi}$ then induces a probability measure on ${Y \times K/H}$ , formed by pushing forward ${\mu_Y}$ by the graphing map ${y \mapsto (y,\tilde \Phi(y))}$ . This measure in turn has several lifts up to a probability measure on ${Y \times K}$ ; for instance, one can construct such a measure ${\overline{\mu}}$ via the Riesz representation theorem by demanding

$\displaystyle \int_{Y \times K} f(y,k) \overline{\mu}(y,k) := \int_Y (\int_{\tilde \Phi(y) H} f(y,k)\ d\mathrm{Haar}_{\tilde \Phi(y) H})\ d\mu_Y(y)$

for all continuous functions ${f}$ . This measure does not come from a graph of any single lift ${\Phi: Y \rightarrow K}$ , but is in some sense an “average” of the entire ensemble of these lifts. But it turns out one can invoke the Krein-Milman theorem to pass to an extremal lifting measure which does come from an (abstract) lift ${\Phi}$ , and this can be used as a substitute for a measurable selection theorem. A variant of this Krein-Milman argument can also be used to express any homogeneous extension as a quotient of a group extension, giving the second part of the Mackey-Zimmer theorem.

Pointwise ergodic theorems for non-conventional bilinear polynomial averages

3 August, 2020 in math.CA, math.DS, paper | Tags: adeles, Ben Krause, Mariusz Mirek, nonconventional ergodic averages, pointwise ergodic theorem | by Terence Tao | 17 comments

Ben Krause, Mariusz Mirek, and I have uploaded to the arXiv our paper Pointwise ergodic theorems for non-conventional bilinear polynomial averages. This paper is a contribution to the decades-long program of extending the classical ergodic theorems to “non-conventional” ergodic averages. Here, the focus is on pointwise convergence theorems, and in particular looking for extensions of the pointwise ergodic theorem of Birkhoff:

Theorem 1 (Birkhoff ergodic theorem) Let ${(X,\mu,T)}$ be a measure-preserving system (by which we mean ${(X,\mu)}$ is a ${\sigma}$ -finite measure space, and ${T: X \rightarrow X}$ is invertible and measure-preserving), and let ${f \in L^p(X)}$ for any ${1 \leq p < \infty}$ . Then the averages ${\frac{1}{N} \sum_{n=1}^N f(T^n x)}$ converge pointwise for ${\mu}$ -almost every ${x \in X}$ .

Pointwise ergodic theorems have an inherently harmonic analysis content to them, as they are closely tied to maximal inequalities. For instance, the Birkhoff ergodic theorem is closely tied to the Hardy-Littlewood maximal inequality.

The above theorem was generalized by Bourgain (conceding the endpoint ${p=1}$ , where pointwise almost everywhere convergence is now known to fail) to polynomial averages:

Theorem 2 (Pointwise ergodic theorem for polynomial averages) Let ${(X,\mu,T)}$ be a measure-preserving system, and let ${f \in L^p(X)}$ for any ${1 < p < \infty}$ . Let ${P \in {\bf Z}[{\mathrm n}]}$ be a polynomial with integer coefficients. Then the averages ${\frac{1}{N} \sum_{n=1}^N f(T^{P(n)} x)}$ converge pointwise for ${\mu}$ -almost every ${x \in X}$ .

For bilinear averages, we have a separate 1990 result of Bourgain (for ${L^\infty}$ functions), extended to other ${L^p}$ spaces by Lacey, and with an alternate proof given, by Demeter:

Theorem 3 (Pointwise ergodic theorem for two linear polynomials) Let ${(X,\mu,T)}$ be a measure-preserving system with finite measure, and let ${f \in L^{p_1}(X)}$ , ${g \in L^{p_2}}$ for some ${1 < p_1,p_2 \leq \infty}$ with ${\frac{1}{p_1}+\frac{1}{p_2} < \frac{3}{2}}$ . Then for any integers ${a,b}$ , the averages ${\frac{1}{N} \sum_{n=1}^N f(T^{an} x) g(T^{bn} x)}$ converge pointwise almost everywhere.

It has been an open question for some time (see e.g., Problem 11 of this survey of Frantzikinakis) to extend this result to other bilinear ergodic averages. In our paper we are able to achieve this in the partially linear case:

Theorem 4 (Pointwise ergodic theorem for one linear and one nonlinear polynomial) Let ${(X,\mu,T)}$ be a measure-preserving system, and let ${f \in L^{p_1}(X)}$ , ${g \in L^{p_2}}$ for some ${1 < p_1,p_2 < \infty}$ with ${\frac{1}{p_1}+\frac{1}{p_2} \leq 1}$ . Then for any polynomial ${P \in {\bf Z}[{\mathrm n}]}$ of degree ${d \geq 2}$ , the averages ${\frac{1}{N} \sum_{n=1}^N f(T^{n} x) g(T^{P(n)} x)}$ converge pointwise almost everywhere.

We actually prove a bit more than this, namely a maximal function estimate and a variational estimate, together with some additional estimates that “break duality” by applying in certain ranges with ${\frac{1}{p_1}+\frac{1}{p_2}>1}$ , but we will not discuss these extensions here. A good model case to keep in mind is when ${p_1=p_2=2}$ and ${P(n) = n^2}$ (which is the case we started with). We note that norm convergence for these averages was established much earlier by Furstenberg and Weiss (in the ${d=2}$ case at least), and in fact norm convergence for arbitrary polynomial averages is now known thanks to the work of Host-Kra, Leibman, and Walsh.

Our proof of Theorem 4 is much closer in spirit to Theorem 2 than to Theorem 3. The property of the averages shared in common by Theorems 2, 4 is that they have “true complexity zero”, in the sense that they can only be only be large if the functions ${f,g}$ involved are “major arc” or “profinite”, in that they behave periodically over very long intervals (or like a linear combination of such periodic functions). In contrast, the average in Theorem 3 has “true complexity one”, in the sense that they can also be large if ${f,g}$ are “almost periodic” (a linear combination of eigenfunctions, or plane waves), and as such all proofs of the latter theorem have relied (either explicitly or implicitly) on some form of time-frequency analysis. In principle, the true complexity zero property reduces one to study the behaviour of averages on major arcs. However, until recently the available estimates to quantify this true complexity zero property were not strong enough to achieve a good reduction of this form, and even once one was in the major arc setting the bilinear averages in Theorem 4 were still quite complicated, exhibiting a mixture of both continuous and arithmetic aspects, both of which being genuinely bilinear in nature.

After applying standard reductions such as the Calderón transference principle, the key task is to establish a suitably “scale-invariant” maximal (or variational) inequality on the integer shift system (in which ${X = {\bf Z}}$ with counting measure, and ${T(n) = n-1}$ ). A model problem is to establish the maximal inequality

$\displaystyle \| \sup_N |A_N(f,g)| \|_{\ell^1({\bf Z})} \lesssim \|f\|_{\ell^2({\bf Z})}\|g\|_{\ell^2({\bf Z})} \ \ \ \ \ (1)$

where ${N}$ ranges over powers of two and ${A_N}$ is the bilinear operator

$\displaystyle A_N(f,g)(x) := \frac{1}{N} \sum_{n=1}^N f(x-n) g(x-n^2).$

The single scale estimate

$\displaystyle \| A_N(f,g) \|_{\ell^1({\bf Z})} \lesssim \|f\|_{\ell^2({\bf Z})}\|g\|_{\ell^2({\bf Z})}$

or equivalently (by duality)

$\displaystyle \frac{1}{N} \sum_{n=1}^N \sum_{x \in {\bf Z}} h(x) f(x-n) g(x-n^2) \lesssim \|f\|_{\ell^2({\bf Z})}\|g\|_{\ell^2({\bf Z})} \|h\|_{\ell^\infty({\bf Z})} \ \ \ \ \ (2)$

is immediate from Hölder’s inequality; the difficulty is how to take the supremum over scales ${N}$ .

The first step is to understand when the single-scale estimate (2) can come close to equality. A key example to keep in mind is when ${f(x) = e(ax/q) F(x)}$ , ${g(x) = e(bx/q) G(x)}$ , ${h(x) = e(cx/q) H(x)}$ where ${q=O(1)}$ is a small modulus, ${a,b,c}$ are such that ${a+b+c=0 \hbox{ mod } q}$ , ${G}$ is a smooth cutoff to an interval ${I}$ of length ${O(N^2)}$ , and ${F=H}$ is also supported on ${I}$ and behaves like a constant on intervals of length ${O(N)}$ . Then one can check that (barring some unusual cancellation) (2) is basically sharp for this example. A remarkable result of Peluse and Prendiville (generalised to arbitrary nonlinear polynomials ${P}$ by Peluse) asserts, roughly speaking, that this example basically the only way in which (2) can be saturated, at least when ${f,g,h}$ are supported on a common interval ${I}$ of length ${O(N^2)}$ and are normalised in ${\ell^\infty}$ rather than ${\ell^2}$ . (Strictly speaking, the above paper of Peluse and Prendiville only says something like this regarding the ${f,h}$ factors; the corresponding statement for ${g}$ was established in a subsequent paper of Peluse and Prendiville.) The argument requires tools from additive combinatorics such as the Gowers uniformity norms, and hinges in particular on the “degree lowering argument” of Peluse and Prendiville, which I discussed in this previous blog post. Crucially for our application, the estimates are very quantitative, with all bounds being polynomial in the ratio between the left and right hand sides of (2) (or more precisely, the ${\ell^\infty}$ -normalized version of (2)).

For our applications we had to extend the ${\ell^\infty}$ inverse theory of Peluse and Prendiville to an ${\ell^2}$ theory. This turned out to require a certain amount of “sleight of hand”. Firstly, one can dualise the theorem of Peluse and Prendiville to show that the “dual function”

$\displaystyle A^*_N(h,g)(x) = \frac{1}{N} \sum_{n=1}^N h(x+n) g(x+n-n^2)$

can be well approximated in ${\ell^1}$ by a function that has Fourier support on “major arcs” if ${g,h}$ enjoy ${\ell^\infty}$ control. To get the required extension to ${\ell^2}$ in the ${f}$ aspect one has to improve the control on the error from ${\ell^1}$ to ${\ell^2}$ ; this can be done by some interpolation theory combined with the useful Fourier multiplier theory of Ionescu and Wainger on major arcs. Then, by further interpolation using recent ${\ell^p({\bf Z})}$ improving estimates of Han, Kovac, Lacey, Madrid, and Yang for linear averages such as ${x \mapsto \frac{1}{N} \sum_{n=1}^N g(x+n-n^2)}$ , one can relax the ${\ell^\infty}$ hypothesis on ${g}$ to an ${\ell^2}$ hypothesis, and then by undoing the duality one obtains a good inverse theorem for (2) for the function ${f}$ ; a modification of the arguments also gives something similar for ${g}$ .

Using these inverse theorems (and the Ionescu-Wainger multiplier theory) one still has to understand the “major arc” portion of (1); a model case arises when ${f,g}$ are supported near rational numbers ${a/q}$ with ${q \sim 2^l}$ for some moderately large ${l}$ . The inverse theory gives good control (with an exponential decay in ${l}$ ) on individual scales ${N}$ , and one can leverage this with a Rademacher-Menshov type argument (see e.g., this blog post) and some closer analysis of the bilinear Fourier symbol of ${A_N}$ to eventually handle all “small” scales, with ${N}$ ranging up to say ${2^{2^u}}$ where ${u = C 2^{\rho l}}$ for some small constant ${\rho}$ and large constant ${C}$ . For the “large” scales, it becomes feasible to place all the major arcs simultaneously under a single common denominator ${Q}$ , and then a quantitative version of the Shannon sampling theorem allows one to transfer the problem from the integers ${{\bf Z}}$ to the locally compact abelian group ${{\bf R} \times {\bf Z}/Q{\bf Z}}$ . Actually it was conceptually clearer for us to work instead with the adelic integers ${{\mathbf A}_{\bf Z} ={\bf R} \times \hat {\bf Z}}$ , which is the inverse limit of the ${{\bf R} \times {\bf Z}/Q{\bf Z}}$ . Once one transfers to the adelic integers, the bilinear operators involved split up as tensor products of the “continuous” bilinear operator

$\displaystyle A_{N,{\bf R}}(f,g)(x) := \frac{1}{N} \int_0^N f(x-t) g(x-t^2)\ dt$

on ${{\bf R}}$ , and the “arithmetic” bilinear operator

$\displaystyle A_{\hat Z}(f,g)(x) := \int_{\hat {\bf Z}} f(x-y) g(x-y^2) d\mu_{\hat {\bf Z}}(y)$

on the profinite integers ${\hat {\bf Z}}$ , equipped with probability Haar measure ${\mu_{\hat {\bf Z}}}$ . After a number of standard manipulations (interpolation, Fubini’s theorem, Hölder’s inequality, variational inequalities, etc.) the task of estimating this tensor product boils down to establishing an ${L^q}$ improving estimate

$\displaystyle \| A_{\hat {\bf Z}}(f,g) \|_{L^q(\hat {\bf Z})} \lesssim \|f\|_{L^2(\hat {\bf Z})} \|g\|_{L^2(\hat {\bf Z})}$

for some ${q>2}$ . Splitting the profinite integers ${\hat {\bf Z}}$ into the product of the ${p}$ -adic integers ${{\bf Z}_p}$ , it suffices to establish this claim for each ${{\bf Z}_p}$ separately (so long as we keep the implied constant equal to ${1}$ for sufficiently large ${p}$ ). This turns out to be possible using an arithmetic version of the Peluse-Prendiville inverse theorem as well as an arithmetic ${L^q}$ improving estimate for linear averaging operators which ultimately arises from some estimates on the distribution of polynomials on the ${p}$ -adic field ${{\bf Q}_p}$ , which are a variant of some estimates of Kowalski and Wright.

Abel prize awarded to Furstenberg and Margulis

18 March, 2020 in math.DS, non-technical | Tags: Grigory Margulis, Hillel Furstenberg | by Terence Tao | 12 comments

Just a short post to note that this year’s Abel prize has been awarded jointly to Hillel Furstenberg and Grigory Margulis for “for pioneering the use of methods from probability and dynamics in group theory, number theory and combinatorics”. I was not involved in the decision making process of the Abel committee this year, but I certainly feel that the contributions of both mathematicians are worthy of the prize. Certainly both mathematicians have influenced my own work (for instance, Furstenberg’s proof of Szemeredi’s theorem ended up being a key influence in my result with Ben Green that the primes contain arbitrarily long arithmetic progressions); see for instance these blog posts mentioning Furstenberg, and these blog posts mentioning Margulis.

An uncountable Moore-Schmidt theorem

28 November, 2019 in math.DS, math.LO, math.PR, paper | Tags: abstract measure theory, Asgar Jamneshan, cocycles, compact abelian groups, ergodic theory, sigma algebras | by Terence Tao | 8 comments

Asgar Jamneshan and I have just uploaded to the arXiv our paper “An uncountable Moore-Schmidt theorem“. This paper revisits a classical theorem of Moore and Schmidt in measurable cohomology of measure-preserving systems. To state the theorem, let ${X = (X,{\mathcal X},\mu)}$ be a probability space, and ${\mathrm{Aut}(X, {\mathcal X}, \mu)}$ be the group of measure-preserving automorphisms of this space, that is to say the invertible bimeasurable maps ${T: X \rightarrow X}$ that preserve the measure ${\mu}$ : ${T_* \mu = \mu}$ . To avoid some ambiguity later in this post when we introduce abstract analogues of measure theory, we will refer to measurable maps as concrete measurable maps, and measurable spaces as concrete measurable spaces. (One could also call ${X = (X,{\mathcal X}, \mu)}$ a concrete probability space, but we will not need to do so here as we will not be working explicitly with abstract probability spaces.)

Let ${\Gamma = (\Gamma,\cdot)}$ be a discrete group. A (concrete) measure-preserving action of ${\Gamma}$ on ${X}$ is a group homomorphism ${\gamma \mapsto T^\gamma}$ from ${\Gamma}$ to ${\mathrm{Aut}(X, {\mathcal X}, \mu)}$ , thus ${T^1}$ is the identity map and ${T^{\gamma_1} \circ T^{\gamma_2} = T^{\gamma_1 \gamma_2}}$ for all ${\gamma_1,\gamma_2 \in \Gamma}$ . A large portion of ergodic theory is concerned with the study of such measure-preserving actions, especially in the classical case when ${\Gamma}$ is the integers (with the additive group law).

Let ${K = (K,+)}$ be a compact Hausdorff abelian group, which we can endow with the Borel ${\sigma}$ -algebra ${{\mathcal B}(K)}$ . A (concrete measurable) ${K}$ –cocycle is a collection ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ of concrete measurable maps ${\rho_\gamma: X \rightarrow K}$ obeying the cocycle equation

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

for ${\mu}$ -almost every ${x \in X}$ . (Here we are glossing over a measure-theoretic subtlety that we will return to later in this post – see if you can spot it before then!) Cocycles arise naturally in the theory of group extensions of dynamical systems; in particular (and ignoring the aforementioned subtlety), each cocycle induces a measure-preserving action ${\gamma \mapsto S^\gamma}$ on ${X \times K}$ (which we endow with the product of ${\mu}$ with Haar probability measure on ${K}$ ), defined by

$\displaystyle S^\gamma( x, k ) := (T^\gamma x, k + \rho_\gamma(x) ).$

This connection with group extensions was the original motivation for our study of measurable cohomology, but is not the focus of the current paper.

A special case of a ${K}$ -valued cocycle is a (concrete measurable) ${K}$ -valued coboundary, in which ${\rho_\gamma}$ for each ${\gamma \in \Gamma}$ takes the special form

$\displaystyle \rho_\gamma(x) = F \circ T^\gamma(x) - F(x)$

for ${\mu}$ -almost every ${x \in X}$ , where ${F: X \rightarrow K}$ is some measurable function; note that (ignoring the aforementioned subtlety), every function of this form is automatically a concrete measurable ${K}$ -valued cocycle. One of the first basic questions in measurable cohomology is to try to characterize which ${K}$ -valued cocycles are in fact ${K}$ -valued coboundaries. This is a difficult question in general. However, there is a general result of Moore and Schmidt that at least allows one to reduce to the model case when ${K}$ is the unit circle ${\mathbf{T} = {\bf R}/{\bf Z}}$ , by taking advantage of the Pontryagin dual group ${\hat K}$ of characters ${\hat k: K \rightarrow \mathbf{T}}$ , that is to say the collection of continuous homomorphisms ${\hat k: k \mapsto \langle \hat k, k \rangle}$ to the unit circle. More precisely, we have

Theorem 1 (Countable Moore-Schmidt theorem) Let ${\Gamma}$ be a discrete group acting in a concrete measure-preserving fashion on a probability space ${X}$ . Let ${K}$ be a compact Hausdorff abelian group. Assume the following additional hypotheses:

(i) ${\Gamma}$ is at most countable.

(ii) ${X}$ is a standard Borel space.

(iii) ${K}$ is metrisable.

Then a ${K}$ -valued concrete measurable cocycle ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ is a concrete coboundary if and only if for each character ${\hat k \in \hat K}$ , the ${\mathbf{T}}$ -valued cocycles ${\langle \hat k, \rho \rangle = ( \langle \hat k, \rho_\gamma \rangle )_{\gamma \in \Gamma}}$ are concrete coboundaries.

The hypotheses (i), (ii), (iii) are saying in some sense that the data ${\Gamma, X, K}$ are not too “large”; in all three cases they are saying in some sense that the data are only “countably complicated”. For instance, (iii) is equivalent to ${K}$ being second countable, and (ii) is equivalent to ${X}$ being modeled by a complete separable metric space. It is because of this restriction that we refer to this result as a “countable” Moore-Schmidt theorem. This theorem is a useful tool in several other applications, such as the Host-Kra structure theorem for ergodic systems; I hope to return to these subsequent applications in a future post.

Let us very briefly sketch the main ideas of the proof of Theorem 1. Ignore for now issues of measurability, and pretend that something that holds almost everywhere in fact holds everywhere. The hard direction is to show that if each ${\langle \hat k, \rho \rangle}$ is a coboundary, then so is ${\rho}$ . By hypothesis, we then have an equation of the form

$\displaystyle \langle \hat k, \rho_\gamma(x) \rangle = \alpha_{\hat k} \circ T^\gamma(x) - \alpha_{\hat k}(x) \ \ \ \ \ (2)$

for all ${\hat k, \gamma, x}$ and some functions ${\alpha_{\hat k}: X \rightarrow {\mathbf T}}$ , and our task is then to produce a function ${F: X \rightarrow K}$ for which

$\displaystyle \rho_\gamma(x) = F \circ T^\gamma(x) - F(x)$

for all ${\gamma,x}$ .

Comparing the two equations, the task would be easy if we could find an ${F: X \rightarrow K}$ for which

$\displaystyle \langle \hat k, F(x) \rangle = \alpha_{\hat k}(x) \ \ \ \ \ (3)$

for all ${\hat k, x}$ . However there is an obstruction to this: the left-hand side of (3) is additive in ${\hat k}$ , so the right-hand side would have to be also in order to obtain such a representation. In other words, for this strategy to work, one would have to first establish the identity

$\displaystyle \alpha_{\hat k_1 + \hat k_2}(x) - \alpha_{\hat k_1}(x) - \alpha_{\hat k_2}(x) = 0 \ \ \ \ \ (4)$

for all ${\hat k_1, \hat k_2, x}$ . On the other hand, the good news is that if we somehow manage to obtain the equation, then we can obtain a function ${F}$ obeying (3), thanks to Pontryagin duality, which gives a one-to-one correspondence between ${K}$ and the homomorphisms of the (discrete) group ${\hat K}$ to ${\mathbf{T}}$ .

Now, it turns out that one cannot derive the equation (4) directly from the given information (2). However, the left-hand side of (2) is additive in ${\hat k}$ , so the right-hand side must be also. Manipulating this fact, we eventually arrive at

$\displaystyle (\alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2}) \circ T^\gamma(x) = (\alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2})(x).$

In other words, we don’t get to show that the left-hand side of (4) vanishes, but we do at least get to show that it is ${\Gamma}$ -invariant. Now let us assume for sake of argument that the action of ${\Gamma}$ is ergodic, which (ignoring issues about sets of measure zero) basically asserts that the only ${\Gamma}$ -invariant functions are constant. So now we get a weaker version of (4), namely

$\displaystyle \alpha_{\hat k_1 + \hat k_2}(x) - \alpha_{\hat k_1}(x) - \alpha_{\hat k_2}(x) = c_{\hat k_1, \hat k_2} \ \ \ \ \ (5)$

for some constants ${c_{\hat k_1, \hat k_2} \in \mathbf{T}}$ .

Now we need to eliminate the constants. This can be done by the following group-theoretic projection. Let ${L^0({\bf X} \rightarrow {\bf T})}$ denote the space of concrete measurable maps ${\alpha}$ from ${{\bf X}}$ to ${{\bf T}}$ , up to almost everywhere equivalence; this is an abelian group where the various terms in (5) naturally live. Inside this group we have the subgroup ${{\bf T}}$ of constant functions (up to almost everywhere equivalence); this is where the right-hand side of (5) lives. Because ${{\bf T}}$ is a divisible group, there is an application of Zorn’s lemma (a good exercise for those who are not acquainted with these things) to show that there exists a retraction ${w: L^0({\bf X} \rightarrow {\bf T}) \rightarrow {\bf T}}$ , that is to say a group homomorphism that is the identity on the subgroup ${{\bf T}}$ . We can use this retraction, or more precisely the complement ${\alpha \mapsto \alpha - w(\alpha)}$ , to eliminate the constant in (5). Indeed, if we set

$\displaystyle \tilde \alpha_{\hat k}(x) := \alpha_{\hat k}(x) - w(\alpha_{\hat k})$

then from (5) we see that

$\displaystyle \tilde \alpha_{\hat k_1 + \hat k_2}(x) - \tilde \alpha_{\hat k_1}(x) - \tilde \alpha_{\hat k_2}(x) = 0$

while from (2) one has

$\displaystyle \langle \hat k, \rho_\gamma(x) \rangle = \tilde \alpha_{\hat k} \circ T^\gamma(x) - \tilde \alpha_{\hat k}(x)$

and now the previous strategy works with ${\alpha_{\hat k}}$ replaced by ${\tilde \alpha_{\hat k}}$ . This concludes the sketch of proof of Theorem 1.

In making the above argument rigorous, the hypotheses (i)-(iii) are used in several places. For instance, to reduce to the ergodic case one relies on the ergodic decomposition, which requires the hypothesis (ii). Also, most of the above equations only hold outside of a set of measure zero, and the hypothesis (i) and the hypothesis (iii) (which is equivalent to ${\hat K}$ being at most countable) to avoid the problem that an uncountable union of sets of measure zero could have positive measure (or fail to be measurable at all).

My co-author Asgar Jamneshan and I are working on a long-term project to extend many results in ergodic theory (such as the aforementioned Host-Kra structure theorem) to “uncountable” settings in which hypotheses analogous to (i)-(iii) are omitted; thus we wish to consider actions on uncountable groups, on spaces that are not standard Borel, and cocycles taking values in groups that are not metrisable. Such uncountable contexts naturally arise when trying to apply ergodic theory techniques to combinatorial problems (such as the inverse conjecture for the Gowers norms), as one often relies on the ultraproduct construction (or something similar) to generate an ergodic theory translation of these problems, and these constructions usually give “uncountable” objects rather than “countable” ones. (For instance, the ultraproduct of finite groups is a hyperfinite group, which is usually uncountable.). This paper marks the first step in this project by extending the Moore-Schmidt theorem to the uncountable setting.

If one simply drops the hypotheses (i)-(iii) and tries to prove the Moore-Schmidt theorem, several serious difficulties arise. We have already mentioned the loss of the ergodic decomposition and the possibility that one has to control an uncountable union of null sets. But there is in fact a more basic problem when one deletes (iii): the addition operation ${+: K \times K \rightarrow K}$ , while still continuous, can fail to be measurable as a map from ${(K \times K, {\mathcal B}(K) \otimes {\mathcal B}(K))}$ to ${(K, {\mathcal B}(K))}$ ! Thus for instance the sum of two measurable functions ${F: X \rightarrow K}$ need not remain measurable, which makes even the very definition of a measurable cocycle or measurable coboundary problematic (or at least unnatural). This phenomenon is known as the Nedoma pathology. A standard example arises when ${K}$ is the uncountable torus ${{\mathbf T}^{{\bf R}}}$ , endowed with the product topology. Crucially, the Borel ${\sigma}$ -algebra ${{\mathcal B}(K)}$ generated by this uncountable product is not the product ${{\mathcal B}(\mathbf{T})^{\otimes {\bf R}}}$ of the factor Borel ${\sigma}$ -algebras (the discrepancy ultimately arises from the fact that topologies permit uncountable unions, but ${\sigma}$ -algebras do not); relating to this, the product ${\sigma}$ -algebra ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$ is not the same as the Borel ${\sigma}$ -algebra ${{\mathcal B}(K \times K)}$ , but is instead a strict sub-algebra. If the group operations on ${K}$ were measurable, then the diagonal set

$\displaystyle K^\Delta := \{ (k,k') \in K \times K: k = k' \} = \{ (k,k') \in K \times K: k - k' = 0 \}$

would be measurable in ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$ . But it is an easy exercise in manipulation of ${\sigma}$ -algebras to show that if ${(X, {\mathcal X}), (Y, {\mathcal Y})}$ are any two measurable spaces and ${E \subset X \times Y}$ is measurable in ${{\mathcal X} \otimes {\mathcal Y}}$ , then the fibres ${E_x := \{ y \in Y: (x,y) \in E \}}$ of ${E}$ are contained in some countably generated subalgebra of ${{\mathcal Y}}$ . Thus if ${K^\Delta}$ were ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$ -measurable, then all the points of ${K}$ would lie in a single countably generated ${\sigma}$ -algebra. But the cardinality of such an algebra is at most ${2^{\alpha_0}}$ while the cardinality of ${K}$ is ${2^{2^{\alpha_0}}}$ , and Cantor’s theorem then gives a contradiction.

To resolve this problem, we give ${K}$ a coarser ${\sigma}$ -algebra than the Borel ${\sigma}$ -algebra, namely the Baire ${\sigma}$ -algebra ${{\mathcal B}^\otimes(K)}$ , thus coarsening the measurable space structure on ${K = (K,{\mathcal B}(K))}$ to a new measurable space ${K_\otimes := (K, {\mathcal B}^\otimes(K))}$ . In the case of compact Hausdorff abelian groups, ${{\mathcal B}^{\otimes}(K)}$ can be defined as the ${\sigma}$ -algebra generated by the characters ${\hat k: K \rightarrow {\mathbf T}}$ ; for more general compact abelian groups, one can define ${{\mathcal B}^{\otimes}(K)}$ as the ${\sigma}$ -algebra generated by all continuous maps into metric spaces. This ${\sigma}$ -algebra is equal to ${{\mathcal B}(K)}$ when ${K}$ is metrisable but can be smaller for other ${K}$ . With this measurable structure, ${K_\otimes}$ becomes a measurable group; it seems that once one leaves the metrisable world that ${K_\otimes}$ is a superior (or at least equally good) space to work with than ${K}$ for analysis, as it avoids the Nedoma pathology. (For instance, from Plancherel’s theorem, we see that if ${m_K}$ is the Haar probability measure on ${K}$ , then ${L^2(K,m_K) = L^2(K_\otimes,m_K)}$ (thus, every ${K}$ -measurable set is equivalent modulo ${m_K}$ -null sets to a ${K_\otimes}$ -measurable set), so there is no damage to Plancherel caused by passing to the Baire ${\sigma}$ -algebra.

Passing to the Baire ${\sigma}$ -algebra ${K_\otimes}$ fixes the most severe problems with an uncountable Moore-Schmidt theorem, but one is still faced with an issue of having to potentially take an uncountable union of null sets. To avoid this sort of problem, we pass to the framework of abstract measure theory, in which we remove explicit mention of “points” and can easily delete all null sets at a very early stage of the formalism. In this setup, the category of concrete measurable spaces is replaced with the larger category of abstract measurable spaces, which we formally define as the opposite category of the category of ${\sigma}$ -algebras (with Boolean algebra homomorphisms). Thus, we define an abstract measurable space to be an object of the form ${{\mathcal X}^{\mathrm{op}}}$ , where ${{\mathcal X}}$ is an (abstract) ${\sigma}$ -algebra and ${\mathrm{op}}$ is a formal placeholder symbol that signifies use of the opposite category, and an abstract measurable map ${T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Y}^{\mathrm{op}}}$ is an object of the form ${(T^*)^{\mathrm{op}}}$ , where ${T^*: {\mathcal Y} \rightarrow {\mathcal X}}$ is a Boolean algebra homomorphism and ${\mathrm{op}}$ is again used as a formal placeholder; we call ${T^*}$ the pullback map associated to ${T}$ . [UPDATE: It turns out that this definition of a measurable map led to technical issues. In a forthcoming revision of the paper we also impose the requirement that the abstract measurable map be $\sigma$ -complete (i.e., it respects countable joins).] The composition ${S \circ T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Z}^{\mathrm{op}}}$ of two abstract measurable maps ${T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Y}^{\mathrm{op}}}$ , ${S: {\mathcal Y}^{\mathrm{op}} \rightarrow {\mathcal Z}^{\mathrm{op}}}$ is defined by the formula ${S \circ T := (T^* \circ S^*)^{\mathrm{op}}}$ , or equivalently ${(S \circ T)^* = T^* \circ S^*}$ .

Every concrete measurable space ${X = (X,{\mathcal X})}$ can be identified with an abstract counterpart ${{\mathcal X}^{op}}$ , and similarly every concrete measurable map ${T: X \rightarrow Y}$ can be identified with an abstract counterpart ${(T^*)^{op}}$ , where ${T^*: {\mathcal Y} \rightarrow {\mathcal X}}$ is the pullback map ${T^* E := T^{-1}(E)}$ . Thus the category of concrete measurable spaces can be viewed as a subcategory of the category of abstract measurable spaces. The advantage of working in the abstract setting is that it gives us access to more spaces that could not be directly defined in the concrete setting. Most importantly for us, we have a new abstract space, the opposite measure algebra ${X_\mu}$ of ${X}$ , defined as ${({\bf X}/{\bf N})^*}$ where ${{\bf N}}$ is the ideal of null sets in ${{\bf X}}$ . Informally, ${X_\mu}$ is the space ${X}$ with all the null sets removed; there is a canonical abstract embedding map ${\iota: X_\mu \rightarrow X}$ , which allows one to convert any concrete measurable map ${f: X \rightarrow Y}$ into an abstract one ${[f]: X_\mu \rightarrow Y}$ . One can then define the notion of an abstract action, abstract cocycle, and abstract coboundary by replacing every occurrence of the category of concrete measurable spaces with their abstract counterparts, and replacing ${X}$ with the opposite measure algebra ${X_\mu}$ ; see the paper for details. Our main theorem is then

Theorem 2 (Uncountable Moore-Schmidt theorem) Let ${\Gamma}$ be a discrete group acting abstractly on a ${\sigma}$ -finite measure space ${X}$ . Let ${K}$ be a compact Hausdorff abelian group. Then a ${K_\otimes}$ -valued abstract measurable cocycle ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ is an abstract coboundary if and only if for each character ${\hat k \in \hat K}$ , the ${\mathbf{T}}$ -valued cocycles ${\langle \hat k, \rho \rangle = ( \langle \hat k, \rho_\gamma \rangle )_{\gamma \in \Gamma}}$ are abstract coboundaries.

With the abstract formalism, the proof of the uncountable Moore-Schmidt theorem is almost identical to the countable one (in fact we were able to make some simplifications, such as avoiding the use of the ergodic decomposition). A key tool is what we call a “conditional Pontryagin duality” theorem, which asserts that if one has an abstract measurable map ${\alpha_{\hat k}: X_\mu \rightarrow {\bf T}}$ for each ${\hat k \in K}$ obeying the identity ${ \alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2} = 0}$ for all ${\hat k_1,\hat k_2 \in \hat K}$ , then there is an abstract measurable map ${F: X_\mu \rightarrow K_\otimes}$ such that ${\alpha_{\hat k} = \langle \hat k, F \rangle}$ for all ${\hat k \in \hat K}$ . This is derived from the usual Pontryagin duality and some other tools, most notably the completeness of the ${\sigma}$ -algebra of ${X_\mu}$ , and the Sikorski extension theorem.

We feel that it is natural to stay within the abstract measure theory formalism whenever dealing with uncountable situations. However, it is still an interesting question as to when one can guarantee that the abstract objects constructed in this formalism are representable by concrete analogues. The basic questions in this regard are:

(i) Suppose one has an abstract measurable map ${f: X_\mu \rightarrow Y}$ into a concrete measurable space. Does there exist a representation of ${f}$ by a concrete measurable map ${\tilde f: X \rightarrow Y}$ ? Is it unique up to almost everywhere equivalence?
(ii) Suppose one has a concrete cocycle that is an abstract coboundary. When can it be represented by a concrete coboundary?

For (i) the answer is somewhat interesting (as I learned after posing this MathOverflow question):

If ${Y}$ does not separate points, or is not compact metrisable or Polish, there can be counterexamples to uniqueness. If ${Y}$ is not compact or Polish, there can be counterexamples to existence.
If ${Y}$ is a compact metric space or a Polish space, then one always has existence and uniqueness.
If ${Y}$ is a compact Hausdorff abelian group, one always has existence.
If ${X}$ is a complete measure space, then one always has existence (from a theorem of Maharam).
If ${X}$ is the unit interval with the Borel ${\sigma}$ -algebra and Lebesgue measure, then one has existence for all compact Hausdorff ${Y}$ assuming the continuum hypothesis (from a theorem of von Neumann) but existence can fail under other extensions of ZFC (from a theorem of Shelah, using the method of forcing).
For more general ${X}$ , existence for all compact Hausdorff ${Y}$ is equivalent to the existence of a lifting from the ${\sigma}$ -algebra ${\mathcal{X}/\mathcal{N}}$ to ${\mathcal{X}}$ (or, in the language of abstract measurable spaces, the existence of an abstract retraction from ${X}$ to ${X_\mu}$ ).
It is a long-standing open question (posed for instance by Fremlin) whether it is relatively consistent with ZFC that existence holds whenever ${Y}$ is compact Hausdorff.

Our understanding of (ii) is much less complete:

If ${K}$ is metrisable, the answer is “always” (which among other things establishes the countable Moore-Schmidt theorem as a corollary of the uncountable one).
If ${\Gamma}$ is at most countable and ${X}$ is a complete measure space, then the answer is again “always”.

In view of the answers to (i), I would not be surprised if the full answer to (ii) was also sensitive to axioms of set theory. However, such set theoretic issues seem to be almost completely avoided if one sticks with the abstract formalism throughout; they only arise when trying to pass back and forth between the abstract and concrete categories.

Almost all Collatz orbits attain almost bounded values

10 September, 2019 in math.DS, math.NT, math.PR, paper | Tags: Collatz conjecture, renewal process | by Terence Tao | 493 comments

I’ve just uploaded to the arXiv my paper “Almost all Collatz orbits attain almost bounded values“, submitted to the proceedings of the Forum of Mathematics, Pi. In this paper I returned to the topic of the notorious Collatz conjecture (also known as the ${3x+1}$ conjecture), which I previously discussed in this blog post. This conjecture can be phrased as follows. Let ${{\bf N}+1 = \{1,2,\dots\}}$ denote the positive integers (with ${{\bf N} =\{0,1,2,\dots\}}$ the natural numbers), and let ${\mathrm{Col}: {\bf N}+1 \rightarrow {\bf N}+1}$ be the map defined by setting ${\mathrm{Col}(N)}$ equal to ${3N+1}$ when ${N}$ is odd and ${N/2}$ when ${N}$ is even. Let ${\mathrm{Col}_{\min}(N) := \inf_{n \in {\bf N}} \mathrm{Col}^n(N)}$ be the minimal element of the Collatz orbit ${N, \mathrm{Col}(N), \mathrm{Col}^2(N),\dots}$ . Then we have

Conjecture 1 (Collatz conjecture) One has ${\mathrm{Col}_{\min}(N)=1}$ for all ${N \in {\bf N}+1}$ .

Establishing the conjecture for all ${N}$ remains out of reach of current techniques (for instance, as discussed in the previous blog post, it is basically at least as difficult as Baker’s theorem, all known proofs of which are quite difficult). However, the situation is more promising if one is willing to settle for results which only hold for “most” ${N}$ in some sense. For instance, it is a result of Krasikov and Lagarias that

$\displaystyle \{ N \leq x: \mathrm{Col}_{\min}(N) = 1 \} \gg x^{0.84}$

for all sufficiently large ${x}$ . In another direction, it was shown by Terras that for almost all ${N}$ (in the sense of natural density), one has ${\mathrm{Col}_{\min}(N) < N}$ . This was then improved by Allouche to ${\mathrm{Col}_{\min}(N) < N^\theta}$ for almost all ${N}$ and any fixed ${\theta > 0.869}$ , and extended later by Korec to cover all ${\theta > \frac{\log 3}{\log 4} \approx 0.7924}$ . In this paper we obtain the following further improvement (at the cost of weakening natural density to logarithmic density):

Theorem 2 Let ${f: {\bf N}+1 \rightarrow {\bf R}}$ be any function with ${\lim_{N \rightarrow \infty} f(N) = +\infty}$ . Then we have ${\mathrm{Col}_{\min}(N) < f(N)}$ for almost all ${N}$ (in the sense of logarithmic density).

Thus for instance one has ${\mathrm{Col}_{\min}(N) < \log\log\log\log N}$ for almost all ${N}$ (in the sense of logarithmic density).
The difficulty here is one usually only expects to establish “local-in-time” results that control the evolution ${\mathrm{Col}^n(N)}$ for times ${n}$ that only get as large as a small multiple ${c \log N}$ of ${\log N}$ ; the aforementioned results of Terras, Allouche, and Korec, for instance, are of this type. However, to get ${\mathrm{Col}^n(N)}$ all the way down to ${f(N)}$ one needs something more like an “(almost) global-in-time” result, where the evolution remains under control for so long that the orbit has nearly reached the bounded state ${N=O(1)}$ .
However, as observed by Bourgain in the context of nonlinear Schrödinger equations, one can iterate “almost sure local wellposedness” type results (which give local control for almost all initial data from a given distribution) into “almost sure (almost) global wellposedness” type results if one is fortunate enough to draw one’s data from an invariant measure for the dynamics. To illustrate the idea, let us take Korec’s aforementioned result that if ${\theta > \frac{\log 3}{\log 4}}$ one picks at random an integer ${N}$ from a large interval ${[1,x]}$ , then in most cases, the orbit of ${N}$ will eventually move into the interval ${[1,x^{\theta}]}$ . Similarly, if one picks an integer ${M}$ at random from ${[1,x^\theta]}$ , then in most cases, the orbit of ${M}$ will eventually move into ${[1,x^{\theta^2}]}$ . It is then tempting to concatenate the two statements and conclude that for most ${N}$ in ${[1,x]}$ , the orbit will eventually move ${[1,x^{\theta^2}]}$ . Unfortunately, this argument does not quite work, because by the time the orbit from a randomly drawn ${N \in [1,x]}$ reaches ${[1,x^\theta]}$ , the distribution of the final value is unlikely to be close to being uniformly distributed on ${[1,x^\theta]}$ , and in particular could potentially concentrate almost entirely in the exceptional set of ${M \in [1,x^\theta]}$ that do not make it into ${[1,x^{\theta^2}]}$ . The point here is the uniform measure on ${[1,x]}$ is not transported by Collatz dynamics to anything resembling the uniform measure on ${[1,x^\theta]}$ .
So, one now needs to locate a measure which has better invariance properties under the Collatz dynamics. It turns out to be technically convenient to work with a standard acceleration of the Collatz map known as the Syracuse map ${\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1}$ , defined on the odd numbers ${2{\bf N}+1 = \{1,3,5,\dots\}}$ by setting ${\mathrm{Syr}(N) = (3N+1)/2^a}$ , where ${2^a}$ is the largest power of ${2}$ that divides ${3N+1}$ . (The advantage of using the Syracuse map over the Collatz map is that it performs precisely one multiplication of ${3}$ at each iteration step, which makes the map better behaved when performing “ ${3}$ -adic” analysis.)
When viewed ${3}$ -adically, we soon see that iterations of the Syracuse map become somewhat irregular. Most obviously, ${\mathrm{Syr}(N)}$ is never divisible by ${3}$ . A little less obviously, ${\mathrm{Syr}(N)}$ is twice as likely to equal ${2}$ mod ${3}$ as it is to equal ${1}$ mod ${3}$ . This is because for a randomly chosen odd ${\mathbf{N}}$ , the number of times ${\mathbf{a}}$ that ${2}$ divides ${3\mathbf{N}+1}$ can be seen to have a geometric distribution of mean ${2}$ – it equals any given value ${a \in{\bf N}+1}$ with probability ${2^{-a}}$ . Such a geometric random variable is twice as likely to be odd as to be even, which is what gives the above irregularity. There are similar irregularities modulo higher powers of ${3}$ . For instance, one can compute that for large random odd ${\mathbf{N}}$ , ${\mathrm{Syr}^2(\mathbf{N}) \hbox{ mod } 9}$ will take the residue classes ${0,1,2,3,4,5,6,7,8 \hbox{ mod } 9}$ with probabilities

$\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}$

respectively. More generally, for any ${n}$ , ${\mathrm{Syr}^n(N) \hbox{ mod } 3^n}$ will be distributed according to the law of a random variable ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ on ${{\bf Z}/3^n{\bf Z}}$ that we call a Syracuse random variable, and can be described explicitly as

$\displaystyle \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = 2^{-\mathbf{a}_1} + 3^1 2^{-\mathbf{a}_1-\mathbf{a}_2} + \dots + 3^{n-1} 2^{-\mathbf{a}_1-\dots-\mathbf{a}_n} \hbox{ mod } 3^n, \ \ \ \ \ (1)$

where ${\mathbf{a}_1,\dots,\mathbf{a}_n}$ are iid copies of a geometric random variable of mean ${2}$ .
In view of this, any proposed “invariant” (or approximately invariant) measure (or family of measures) for the Syracuse dynamics should take this ${3}$ -adic irregularity of distribution into account. It turns out that one can use the Syracuse random variables ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ to construct such a measure, but only if these random variables stabilise in the limit ${n \rightarrow \infty}$ in a certain total variation sense. More precisely, in the paper we establish the estimate

$\displaystyle \sum_{Y \in {\bf Z}/3^n{\bf Z}} | \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z})=Y) - 3^{m-n} \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^m{\bf Z})=Y \hbox{ mod } 3^m)| \ \ \ \ \ (2)$

$\displaystyle \ll_A m^{-A}$

for any ${1 \leq m \leq n}$ and any ${A > 0}$ . This type of stabilisation is plausible from entropy heuristics – the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ of geometric random variables that generates ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ has Shannon entropy ${n \log 4}$ , which is significantly larger than the total entropy ${n \log 3}$ of the uniform distribution on ${{\bf Z}/3^n{\bf Z}}$ , so we expect a lot of “mixing” and “collision” to occur when converting the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ to ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ ; these heuristics can be supported by numerics (which I was able to work out up to about ${n=10}$ before running into memory and CPU issues), but it turns out to be surprisingly delicate to make this precise.
A first hint of how to proceed comes from the elementary number theory observation (easily proven by induction) that the rational numbers

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{n-1} 2^{-a_1-\dots-a_n}$

are all distinct as ${(a_1,\dots,a_n)}$ vary over tuples in ${({\bf N}+1)^n}$ . Unfortunately, the process of reducing mod ${3^n}$ creates a lot of collisions (as must happen from the pigeonhole principle); however, by a simple “Lefschetz principle” type argument one can at least show that the reductions

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{m-1} 2^{-a_1-\dots-a_m} \hbox{ mod } 3^n \ \ \ \ \ (3)$

are mostly distinct for “typical” ${a_1,\dots,a_m}$ (as drawn using the geometric distribution) as long as ${m}$ is a bit smaller than ${\frac{\log 3}{\log 4} n}$ (basically because the rational number appearing in (3) then typically takes a form like ${M/2^{2m}}$ with ${M}$ an integer between ${0}$ and ${3^n}$ ). This analysis of the component (3) of (1) is already enough to get quite a bit of spreading on ${ \mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ (roughly speaking, when the argument is optimised, it shows that this random variable cannot concentrate in any subset of ${{\bf Z}/3^n{\bf Z}}$ of density less than ${n^{-C}}$ for some large absolute constant ${C>0}$ ). To get from this to a stabilisation property (2) we have to exploit the mixing effects of the remaining portion of (1) that does not come from (3). After some standard Fourier-analytic manipulations, matters then boil down to obtaining non-trivial decay of the characteristic function of ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ , and more precisely in showing that

$\displaystyle \mathbb{E} e^{-2\pi i \xi \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) / 3^n} \ll_A n^{-A} \ \ \ \ \ (4)$

for any ${A > 0}$ and any ${\xi \in {\bf Z}/3^n{\bf Z}}$ that is not divisible by ${3}$ .
If the random variable (1) was the sum of independent terms, one could express this characteristic function as something like a Riesz product, which would be straightforward to estimate well. Unfortunately, the terms in (1) are loosely coupled together, and so the characteristic factor does not immediately factor into a Riesz product. However, if one groups adjacent terms in (1) together, one can rewrite it (assuming ${n}$ is even for sake of discussion) as

$\displaystyle (2^{\mathbf{a}_2} + 3) 2^{-\mathbf{b}_1} + (2^{\mathbf{a}_4}+3) 3^2 2^{-\mathbf{b}_1-\mathbf{b}_2} + \dots$

$\displaystyle + (2^{\mathbf{a}_n}+3) 3^{n-2} 2^{-\mathbf{b}_1-\dots-\mathbf{b}_{n/2}} \hbox{ mod } 3^n$

where ${\mathbf{b}_j := \mathbf{a}_{2j-1} + \mathbf{a}_{2j}}$ . The point here is that after conditioning on the ${\mathbf{b}_1,\dots,\mathbf{b}_{n/2}}$ to be fixed, the random variables ${\mathbf{a}_2, \mathbf{a}_4,\dots,\mathbf{a}_n}$ remain independent (though the distribution of each ${\mathbf{a}_{2j}}$ depends on the value that we conditioned ${\mathbf{b}_j}$ to), and so the above expression is a conditional sum of independent random variables. This lets one express the characeteristic function of (1) as an averaged Riesz product. One can use this to establish the bound (4) as long as one can show that the expression

$\displaystyle \frac{\xi 3^{2j-2} (2^{-\mathbf{b}_1-\dots-\mathbf{b}_j+1} \mod 3^n)}{3^n}$

is not close to an integer for a moderately large number ( ${\gg A \log n}$ , to be precise) of indices ${j = 1,\dots,n/2}$ . (Actually, for technical reasons we have to also restrict to those ${j}$ for which ${\mathbf{b}_j=3}$ , but let us ignore this detail here.) To put it another way, if we let ${B}$ denote the set of pairs ${(j,l)}$ for which

$\displaystyle \frac{\xi 3^{2j-2} (2^{-l+1} \mod 3^n)}{3^n} \in [-\varepsilon,\varepsilon] + {\bf Z},$

we have to show that (with overwhelming probability) the random walk

$\displaystyle (1,\mathbf{b}_1), (2, \mathbf{b}_1 + \mathbf{b}_2), \dots, (n/2, \mathbf{b}_1+\dots+\mathbf{b}_{n/2})$

(which we view as a two-dimensional renewal process) contains at least a few points lying outside of ${B}$ .
A little bit of elementary number theory and combinatorics allows one to describe the set ${B}$ as the union of “triangles” with a certain non-zero separation between them. If the triangles were all fairly small, then one expects the renewal process to visit at least one point outside of ${B}$ after passing through any given such triangle, and it then becomes relatively easy to then show that the renewal process usually has the required number of points outside of ${B}$ . The most difficult case is when the renewal process passes through a particularly large triangle in ${B}$ . However, it turns out that large triangles enjoy particularly good separation properties, and in particular afer passing through a large triangle one is likely to only encounter nothing but small triangles for a while. After making these heuristics more precise, one is finally able to get enough points on the renewal process outside of ${B}$ that one can finish the proof of (4), and thus Theorem 2.

	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Dense sets of natural numbers…
	Anonymous on Dense sets of natural numbers…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Dense sets of natural numbers…
	Fabrice Imparato on Dense sets of natural numbers…
	Anonymous on A computation-outsourced discu…
	Anonymous on Dense sets of natural numbers…
	Anonymous on 245A, Notes 3: Integration on…
	Samuel German on Analysis I

Category Archive

Notes on the B+B+t theorem

Measurable tilings by abelian group actions

The structure of arbitrary Conze-Lesigne systems

The Gowers uniformity norm of order 1+

Pointwise ergodic theorems for non-conventional bilinear polynomial averages

Abel prize awarded to Furstenberg and Margulis

An uncountable Moore-Schmidt theorem

Almost all Collatz orbits attain almost bounded values

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters