The horocycle flow is mixing of all orders

— 1. Introduction —

The main purpose of this post is to present a proof, due to Brian Marcus, that the horocycle flow is mixing of all orders. The precise definition of mixing of all orders for {{\mathbb R}}-actions is given below in Definition 2; we begin by describing the horocycle flow. Let {SL(2,{\mathbb R})} denote the set of all {2\times2} matrices with real entries and determinant {1}, endowed with the usual topology and the (left and right invariant) Haar measure {\lambda}. Given a discrete subgroup {\Gamma\subset SL(2,{\mathbb R})}, the quotient {X:=SL(2,{\mathbb R})/\Gamma} is given the quotient topology and `quotient Haar measure’ {\mu}. The latter can be described by

\displaystyle \int_X\sum_{\gamma\in\Gamma}f(x\gamma)~\mathtt{d}\mu(x)=\int_{SL(2,{\mathbb R})}f(g)~\mathtt{d}\lambda(g)

for any {f\in C_c(SL(2,{\mathbb R}))}. If the total measure {\mu(X)} of {X} is finite (in which case we normalize it so that {\mu(X)=1}), we say that {\Gamma} is a lattice. The classical example is when {\Gamma=SL(2,{\mathbb Z})}.

The horocycle flow is the (continuous) {{\mathbb R}}-action on {X} defined by {s\cdot(g\Gamma)=(h_sg)\Gamma}, where {h_s=\left[\begin{array}{cc} 1 & s \\ 0 & 1 \end{array}\right]} for {s\in{\mathbb R}} and {g\in SL(2,{\mathbb R})}. We will also need the geodesic flow, corresponding in this case to {g_t=\left[\begin{array}{cc} e^{t/2} & 0 \\ 0 &e^{-t/2} \end{array}\right]}.

The theorem we will prove actually deals with a more general situation:

Theorem 1 Let {X} be a (finite dimensional) manifold, let {\mu} a Borel probability measure on {X} and let {(h_s)_{s\in{\mathbb R}}} and {(g_t)_{t\in{\mathbb R}}} be continuous {\mu}-preserving {{\mathbb R}}-actions. If {(h_s)_{s\in{\mathbb R}}} is ergodic and there exists {\lambda>1} such that

\displaystyle  g_th_sg_t^{-1}=h_{s\lambda^t}, \ \ \ \ \ (1)

then {(h_s)_{s\in{\mathbb R}}} is mixing of all orders.

The first step of the proof of Theorem 1 is to show that {(h_s)_{s\in{\mathbb R}}} satisfies a weaker property, called property {P(N)} (see Definition 3) which resembles a property equivalent to weakly mixing of order {N} (at least in the case of {{\mathbb Z}}-actions). For this step, all we need is that {(h_s)_{s\in{\mathbb R}}} is a continuous probability preserving mixing {{\mathbb R}}-action .

Continue reading

Advertisements
Posted in Analysis, Classic results, Ergodic Theory | Tagged , , , , | Leave a comment

Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points

— 1. Introduction —

Recently, Florian Richter and I uploaded to the arXiv our paper titled `Large subsets of discrete hypersurfaces in {{\mathbb Z}^d} contain arbitrarily many collinear points’.

This was the outcome of a fun project which started when we learned about Pomerance’s theorem:

Theorem 1 (Pomerance’s theorem) For every {B,k\in{\mathbb N}} there exists {n\in{\mathbb N}} such that for any {u_0,\dots,u_n\in{\mathbb Z}^2} with average gap bounded by {B}, i.e.

\displaystyle \frac1n\sum_{i=1}^n\|u_i-u_{i-1}\|\leq B,

there exist {k} points among {u_1,\dots,u_n} which are collinear.

I have presented the proof of Pomerance’s theorem in this post. A weakening of Pomerance’s theorem was proved earlier by L. T. Ramsey (it is Lemma 1 in that paper) as a combinatorial intermediate step in a problem in Fourier analysis.

Lemma 2 (Ramsey’s lemma) For every {B,k\in{\mathbb N}} there exists {n\in{\mathbb N}} such that for any {u_0,\dots,u_n\in{\mathbb Z}^2} with gaps bounded by {B}, i.e.

\displaystyle \forall i\in\{1,\dots,n\}\qquad\qquad\|u_i-u_{i-1}\|\leq B

there exist {k} points among {u_1,\dots,u_n} which are collinear.

Even when {B=1} Lemma 2 is nontrivial (and in fact it is easy to derive Lemma 2 from the case when {B=1}).

The question we asked (and eventually answered) was whether these results could be extended to higher dimensions. The first problem here is how to even formulate such a generalization!
Continue reading

Posted in Analysis, Combinatorics, paper | Tagged , , , , , | 2 Comments

New polynomial and multidimensional extensions of classical partition results

Vitaly Bergelson, John Johnson and I recently uploaded to the arXiv a paper entitled “New polynomial and multidimensional extensions of classical partition results“. In this post I will give some motivating examples for the results in the paper.

To keep things as concrete as possible, I will establish parallels to our results in the paper using known generalizations of the classical van der Waerden’s theorem on arithmetic progressions:

Theorem 1 (van der Waerden) For any finite partition of the natural numbers {{\mathbb N}=C_1\cup\cdots\cup C_r}, there exists some {i\in[r]=\{1,\dots,r\}} for which {C_i} contains arbitrarily long arithmetic progressions, i.e., for every {k\in{\mathbb N}}, there are {a,b\in{\mathbb N}} such that

\displaystyle ja+b\in C_i\qquad\forall j\in[k]\ \ \ \ \ (1)

Continue reading

Posted in Combinatorics, paper, Ramsey Theory | Tagged , , , , , | 1 Comment

Weighted densities with multiplicative structure

The upper density of a set {A\subset{\mathbb N}}, defined by

\displaystyle \bar d(A)=\limsup_{N\rightarrow\infty}\frac{\big|A\cap\{1,\dots,N\}\big|}N \ \ \ \ \ (1)

provides a useful way to measure subsets of {{\mathbb N}}. For instance, whenever {\bar d(A)>0}, {A} contains arbitrarily long arithmetic progressions, this is Szemerédi’s theorem. A fundamental property of the upper density {\bar d} is that it is invariant under (additive) shifts. More precisely, if we denote by {A-n} the set {\{x\in{\mathbb N}:x+n\in A\}} then {\bar d(A-1)=\bar d(A)} for any {A\subset{\mathbb N}} and {n\in{\mathbb N}}.
However the upper density is not invariant under multiplicative `shifts’. More precisely, if we let {A/n:=\{x\in{\mathbb N}:x\cdot n\in A\}}, then {\bar d(A/n)} is not, in general, the same as {\bar d(A)}. For instance, taking {A} to be the set of odd numbers and {n=2} we have {\bar d(A)=1/2} but {A/n} is the empty set, and as such {\bar d(A/n)=0}. In fact, as I explored in a previous post, there is very little multiplicative information contained in the upper density {\bar d} of a set. In particular, for any {\epsilon>0}, there are sets with upper density {\bar d(A)>1/2-\epsilon} but without any two numbers {x,y\in A} which divide each other; the first examples of such sets were constructed by Besicovitch in 1934. Continue reading

Posted in Combinatorics, Number Theory, Tool | Tagged , , , | Leave a comment

A proof of Deuber’s theorem using Hales-Jewett’s theorem

In my previous post I explained how Rado’s theorem follows from Deuber’s theorem (which in turn gives a little more than Rado’s theorem, in one direction). The main purpose of this post is to give a full proof of Deuber’s theorem, which will then complete the proof of Rado’s theorem.

I will follow the proof presented in this survey by Gunderson (available here). According to the survey, this proof was first suggested by Leeb and later worked out by Prömel. The main tool for the proof is the Hales-Jewett theorem. I wrote about this theorem twice before in this blog, including a complete proof. In particular I showed how van der Waerden’s theorem on arithmetic progressions, which is an important corollary of Deuber’s theorem, follows from Hales-Jewett’s theorem.

However, Deuber’s theorem (which I will formulate precisely below) implies also Schur’s theorem, and it is not at all clear how to derive Schur’s theorem from Hales-Jewett theorem directly. Thus it is somewhat surprising that one can leverage the Hales-Jewett theorem to deduce Deuber’s theorem. Continue reading

Posted in Combinatorics, Ramsey Theory | Tagged , , | 1 Comment

Rado’s theorem and Deuber’s theorem

In this post I talk about (and prove) a fundamental theorem of Rado in Ramsey’s theory. I will prove “half” of the theorem and will postpone the second part of the proof to a future post.

To better appreciate Rado’s theorem, I will start by listing some of it’s consequences: {Schur’s theorem}}} For any {r\in{\mathbb N}} and any function {\chi:{\mathbb N}\rightarrow[r]} (as usual we will take {[r]=\{1,\dots,r\}}) there exist {x,y\in{\mathbb N}} such that {\chi(x)=\chi(y)=\chi(x+y)}.

Equivalently, for any finite coloring of {{\mathbb N}} there exists a monochromatic solution to the equation {x+y=z}.

\href{van der Waerden’s theorem}} For any {r,k\in{\mathbb N}} and any function {\chi:{\mathbb N}\rightarrow[r]} there exist {x,y\in{\mathbb N}} such that {\chi(x)=\chi(x+y)=\cdots=\chi(x+ky)}.

Equivalently, for any finite coloring of {{\mathbb N}} there exists a monochromatic solution to the system {x_{i+1}-x_i=x_i-x_{i-1}} for {i=1,\dots,k-1}.

A common generalization of the two above theorems is Brauer’s theorem:

Theorem 1 (Brauer’s theorem) For any {r,k\in{\mathbb N}} and any function {\chi:{\mathbb N}\rightarrow[r]} there exist {x,y\in{\mathbb N}} such that {\chi(x)=\chi(y)=\chi(x+y)=\cdots=\chi(x+ky)}.

Equivalently, for any finite coloring of {{\mathbb N}} there exists a monochromatic solution to the system {x_{i+1}-x_i=x_0} for {i=1,\dots,k-1}.

Another consequence of Rado’s theorem is the following result, sometimes called Folkman’s theorem, which contains Schur’s theorem as a special case when {k=2}: \href{Folkman’s theorem}} For any {r,k\in{\mathbb N}} and any function {\chi:{\mathbb N}\rightarrow[r]} there exist {x_1,\dots,x_k\in{\mathbb N}} and a color {i\in[r]} such that

\displaystyle \chi\left(\sum_{j\in\alpha}x_j\right)=i\qquad\forall\emptyset\neq\alpha\subset[k]

While it’s not as immediate as the previous theorems, one can also formulate Folkman’s theorem in the form “For any finite coloring of {{\mathbb N}} there exists a monochromatic solution to the system {A\vec x=\vec 0}“. To see that, let {m=2^k-k-1} be the number of subsets of {[k]} with at least two elements. Take {A_1} to be the {m\times k} matrix which contains in each line the indicator function of a subset {\alpha\subset[k]} with {|\alpha|\geq2}. Then let {A_2=-I_m} where {I_m} is the {m\times m} identity matrix. Finally let {A} be the {m\times(k+m)} concatenation of {A_1} with {A_2}. For instance, when {k=3} we get

\displaystyle A=\left[\begin{array}{cccccccc}1&1&0&|&-1&0&0&0\\ 1&0&1&|&0&-1&0&0\\ 0&1&1&|&0&0&-1&0\\ 1&1&1&|&0&0&0&-1\end{array}\right]

More generally, given an homogeneous system of linear equations {A\vec x=\vec 0}, where {\vec x\in{\mathbb N}^d}, {\vec 0\in{\mathbb Z}^k} and {A} is a {k\times d} matrix with integer coefficients, one can ask whether for any finite coloring of {{\mathbb N}} there exists a vector {\vec x\in{\mathbb N}^d} with all coordinates in one color and such that {A\vec x=\vec 0}. The answer is provided by Rado’s theorem. Continue reading

Posted in Ramsey Theory | Tagged , , , | 2 Comments

Hales-Jewett and a generalized van der Warden Theorems

The Hales-Jewett theorem is one of the most fundamental results in Ramsey theory, implying the celebrated van der Waerden theorem on arithmetic progressions, as well an its multidimensional and IP versions. One interesting property of the Hales-Jewett’s theorem is that it is a set theoretical statement, having no structure, and hence making it versatile for applications. Recently I realized that there exists an equivalent formulation of this theorem using some algebraic structure, and indeed it can be seen as an analogue of van der Waerden’s theorem. The main purpose of this post is to establish that equivalence. In an initial section I present the deduction of the multidimensional van der Waerden from the Hales-Jewett theorem, both to set the mood and to set the stage to later establish the analogy between van der Waerden’s theorem and the equivalent formulation of the Hales-Jewett theorem. Continue reading

Posted in Combinatorics, Ramsey Theory | Tagged , , , , , , , | 3 Comments