ERT6: Topological Dynamics and van der Waerden Theorem

Posted by: yglima | February 5, 2010

ERT6: Topological Dynamics and van der Waerden Theorem

The previous post showed how to connect sets ${E\subset{\mathbb Z}}$ with ergodic theory, namely a measure-preserving system ${(X,\mathcal B,\mu,T)}$ , where ${X}$ is the symbolic space ${\{0,1\}^{{\mathbb Z}}}$ and ${T:X\rightarrow X}$ is the shift map. As the reader can check in ERT5, the measure ${\mu}$ is an accumulation point of Dirac probability measures along increasing intervals of orbits of the point ${\underline x\in X}$ associated to ${E}$ . For this reason, ${\mu}$ is supported in the orbit of ${\underline x}$ . Then we could take ${X}$ as the orbit closure

$\displaystyle \mathcal O(\underline x)=\overline{\{T^n\underline x\,;\,n\in{\mathbb Z}\}}$

instead of the whole space ${\{0,1\}^{{\mathbb Z}}}$ . The set ${\mathcal O(\underline x)}$ , in addition of composing the mps ${(\mathcal O(\underline x),\mathcal B\cap\mathcal O(\underline x),\mu,T|_{\mathcal O(\underline x)})}$ , has the natural metric induced by ${X}$ . More precisely, endow ${\{0,1\}}$ with the discrete metric ${d_0(x,y)=\delta_x(y)}$ and ${X}$ with the product topology. By Tychonoff Theorem, ${X}$ is a compact topological space, and the distance ${d:X\times X\rightarrow{\mathbb R}}$ defined as

$\displaystyle d(\underline x,\underline y)=\sum_{n\in{\mathbb Z}}\dfrac{d_0(x_n,y_n)}{2^{|n|}}\ ,\ \ \underline x,\underline y\in X,$

generates the topology of ${X}$ (to see this, just note that the cylinders – sets of elements with fixed entries in a finite number of positions – form a basis of topology of ${X}$ and each of them is a ball with respect to the metric ${d}$ ). Also, ${T}$ is homeomorphism. In fact, we leave as exercise to the reader to prove that

$\displaystyle d(T\underline x,T\underline y)\le 2\cdot d(\underline x,\underline y)\,,\ \forall\,\underline x,\underline y\in X.$

It is natural to wonder how general results of topological dynamics can be obtained and applied to this setting. This is what we are going to do in this post. The first section consists of the relations between arithmetic properties of ${E}$ and topological properties of ${\mathcal O(\underline x)}$ . The second section is deeper and we prove van der Waerden theorem assuming a topological multiple recurrence theorem, which will be proved in ERT7. The main result of this post is, then,

Theorem 1 (van der Waerden) If ${{\mathbb Z}=E_1\cup\cdots\cup E_r}$ , then some ${E_i}$ contains arbitrarily long arithmetic progressions.

1. Combinatorics of ${E}$ vs Topology of ${\mathcal O(\underline x)}$

The set ${\mathcal O(\underline x)}$ is always a compact, totally disconnected set (because ${X}$ is) and transitive with respect to ${T}$ (the orbit of ${\underline x}$ is dense in ${\mathcal O(\underline x)}$ ).

Proposition 2 Let ${E\subset{\mathbb N}}$ and ${\mathcal O(\underline x)\subset X}$ its associated set.

(i) ${\mathcal O(\underline x)}$ is finite if and only if there exist a finite set ${E_0\subset{\mathbb Z}}$ and an integer ${p>0}$ such that ${E}$ is the disjoint union $\displaystyle \bigcup_{n\in{\mathbb Z}}(E_0+np).$

(ii) ${{\mathbb Z}\backslash E}$ is thick if and only if ${(\ldots,0;0,\ldots)\in\mathcal O(\underline x)}$ .

(iii) ${{\rm d}^*(E)=1}$ if and only if ${(\ldots,1;1,\ldots)\in\mathcal O(\underline x)}$ .

Proof: (i) ${\mathcal O(\underline x)}$ is finite if and only if ${\underline x}$ is periodic for ${T}$ , that is, if and only if there exists ${p>0}$ such that ${T^p\underline x=\underline x}$ . Considering ${E_0=E\cap\{0,1,\ldots,p-1\}}$ , we obtain the desired conclusion.

(ii) If ${{\mathbb Z}\backslash E}$ is thick, there are intervals ${I_k=[n_k-k,n_k+k)}$ , ${k\ge 1}$ , such that ${E\cap I_k=\emptyset}$ . Then

$\displaystyle T^{n_k}\underline x=(\ldots,\underbrace{0,\ldots,0;0,\ldots,0}_{2k},\ldots),$

which converges to ${(\ldots,0;0,\ldots)}$ if ${k\rightarrow+\infty}$ . For the opposite implication, the same argument works: if ${(\ldots,0;0,\ldots)\in\mathcal O(\underline x)}$ then, for every ${k\ge 1}$ , there exists ${n\in{\mathbb Z}}$ such that

$\displaystyle T^{n}\underline x=(\ldots,\underbrace{0,\ldots,0;0,\ldots,0}_{2k},\ldots),$

that is, ${E\cap [n-k,n+k)=\emptyset}$ . As ${k}$ is arbitrary, ${{\mathbb Z}\backslash E}$ is thick.

(iii) If ${{\rm d}^*(E)=1}$ , there exist intervals ${(I_k)_{k\ge1}}$ , ${|I_k|\rightarrow+\infty}$ , such that

$\displaystyle \lim_{k\rightarrow+\infty}\dfrac{|E\cap I_k|}{|I_k|}=1.$

Fix an integer ${L>0}$ and decompose ${I_k}$ as the union of intervals of length ${L}$ (except, at most, the last one). That is, write ${|I_k|=qL+r}$ , $0\le r<L$ , and $\displaystyle I_k=I_k^1\cup\cdots\cup I_k^q\cup I_k^{q+1}$ into ${q}$ intervals of lenght ${L}$ and one of lenght ${r}$ ( ${I_k^{q+1}}$ is possibly empty). If ${k}$ is large, ${|I_k|\gg L}$ and then some ${I_k^j=[n,n+L)}$ is contained in ${E}$ , so that

$\displaystyle T^{n+\lfloor L/2\rfloor}\underline x=(\ldots,\underbrace{1,\ldots,1;1,\ldots,1}_L,\ldots).$

Again, as ${L}$ is arbitrary, ${(\ldots,1;1,\ldots)\in\mathcal O(\underline x)}$ . Reciprocally, if ${(\ldots,1;1,\ldots)\in\mathcal O(\underline x)}$ , there exists, for each ${L>0}$ , an integer ${n}$ such that

$\displaystyle T^{n+\lfloor L/2\rfloor}\underline x=(\ldots,\underbrace{1,\ldots,1;1,\ldots,1}_L,\ldots),$

that is, ${[n+1,n+L)\subset E}$ . This proves that ${{\rm d}^*(E)=1}$ . $\Box$

The situation (i) happens if ${E=a{\mathbb Z}+b}$ , where ${a,b\in{\mathbb Z}}$ . These sets have low complexity and are highly structured sets formed by infinite arithmetic progressions.

Proposition 3 If ${\mathcal O(\underline x)}$ is minimal, then ${E}$ is syndetic.

Proof: Take any ${n\in E}$ and consider the clopen cylinder

$\displaystyle V=\{\underline y\in \mathcal O(\underline x)\,;\,y_n=1\}.$

By minimality, the set ${B=\{m\in{\mathbb Z}\,;\,T^m\underline x\in V\}}$ of return times of ${\underline x}$ to ${V}$ is syndetic. But

$\displaystyle m\in B\ \iff\ T^m\underline x\in V\ \iff\ x_{m+n}=1\ \iff\ m+n\in E$

and so ${B+n\subset E}$ , implying that ${E}$ is syndetic. $\Box$

The converse is false. For example,

$\displaystyle E={\mathbb Z}\backslash\{n(n+1)/2\,;\,n\in{\mathbb Z}\}$

is syndetic, but ${\mathcal O(\underline x)}$ contains the fixed point ${(\ldots,1;1,\ldots)}$ (this follows from Proposition 2, because ${{\rm d}^*(E)=1}$ ). This means we have to look for more conditions about ${E}$ to characterize minimality of ${\mathcal O(\underline x)}$ .

Question. What are these conditions?

Given ${\underline x\in X}$ , consider the ${\omega}$ -limit of ${\underline x}$ , defined as

$\displaystyle \omega(\underline x)=\{\underline y\in X\,;\,T^{n_k}\underline x\rightarrow \underline y\text{ for some }n_k\rightarrow+\infty\}.$

We say that ${\underline x}$ is recurrent if ${\underline x\in\omega(\underline x)}$ .

Definition 4 A set ${E\subset{\mathbb Z}}$ is called IP-set if it there exists an increasing sequence ${(n_k)_{k\ge 1}}$ such that ${E}$ contains the set $\displaystyle {\rm FS}(n_1,n_2,\ldots)=\left\{\sum\limits_{k\in F} n_k\,;\, F\subset{\mathbb N} \textrm{ is finite}\right\}.$

Theorem 5 If ${\underline x}$ is recurrent, then ${E}$ contains the translate of an IP-set.

Proof: Construct inductively an increasing sequence ${(n_k)_{k\ge 0}}$ as follows: ${n_0}$ is any element of ${E}$ and, for every ${k\ge0}$ , ${n_{k+1}}$ is a positive integer greater than ${n_0+\cdots+n_k}$ such that the first ${n_0+\cdots+n_k}$ entries of ${T^{n_k}\underline x}$ and ${\underline x}$ are equal, that is

$\displaystyle x_i=x_{i+n_{k+1}}\,,\ i=0,1,\ldots,n_0+\cdots+n_k.$

This last condition means that

$\displaystyle (E-n_{k+1})\cap\{0,1,\ldots,n_0+\cdots+n_k\}=E\cap\{0,1,\ldots,n_0+\cdots+n_k\}.$

We’ll prove that ${n_0+{\rm FS}(n_1,n_2,\ldots)\subset E}$ . This is equivalent to ${n_0+{\rm FS}(n_1,\ldots,n_k)\subset E}$ , for every ${k\ge 1}$ . The case ${k=1}$ is obvious:

$\displaystyle n_0\in E\cap\{0,1,\ldots,n_0\}=(E-n_1)\cap\{0,1,\ldots,n_0\}\ \ \Longrightarrow\ \ n_0+n_1\in E.$

Suppose ${n_0+{\rm FS}(n_1,\ldots,n_k)\subset E}$ for some ${k\ge 1}$ . Then

$\displaystyle \begin{array}{rcl} n_0+{\rm FS}(n_1,\ldots,n_k)&\subset &E\cap\{0,1,\ldots,n_0+\cdots+n_k\}\\ &=&(E-n_{k+1})\cap\{0,1,\ldots,n_0+\cdots+n_k\}\\ n_0+{\rm FS}(n_1,\ldots,n_k)+n_{k+1}&\subset &E\\ n_0+{\rm FS}(n_1,\ldots,n_{k+1})&\subset &E\,, \end{array}$

which concludes the proof. $\Box$

Corollary 6 Choose ${E\subset{\mathbb Z}}$ ramdomly, that is, each ${n\in{\mathbb Z}}$ is in ${E}$ with probability ${1/2}$ . Then almost surely ${E}$ contains the translate of an IP-set.

Proof: Consider the probability in ${X}$ induced by the vector ${(1/2,1/2)}$ . By Poincaré Recurrence Theorem (see ERT1), almost-every ${\underline x\in X}$ is recurrent. $\Box$

2. Proof of van der Waerden theorem

We know how to translate the notion of subsets of ${{\mathbb Z}}$ to symbolic spaces. How to encode a partition

$\displaystyle {\mathbb Z}=E_1\cup E_2\cup\cdots\cup E_r \ \ \ \ \ (1)$

to topology? Well, instead if considering ${\{0,1\}^{{\mathbb Z}}}$ , we take $\displaystyle X=\{1,2,\ldots,r\}^{{\mathbb Z}}$ and, for the partition given in (1), associate the element ${\underline x=(x_n)_{n\in{\mathbb Z}}}$ defined as

$\displaystyle x_n=i\iff n\in E_i\,,\ \forall\,n\in{\mathbb Z}\,.$

Such association follows the same philosophy of the previous section: to ${E\subset{\mathbb Z}}$ , there is a natural partition ${{\mathbb Z}=E\cup({\mathbb Z}\backslash E)}$ . By the same reasons described in Section 1, ${X}$ is a compact metric space and the same happens to the orbit closure ${\mathcal O(\underline x)}$ of ${\underline x}$ with respect to the shift ${T:X\rightarrow X}$ . In this encoding, by definition of the distance ${d}$ ,

$\displaystyle d\left(T^m\underline y,T^l\underline z\right)<1\ \iff\ y_m=z_l.$

Therefore, the existence of a monochromatic arithmetic progression ${m,m+n,\dots, m+(k-1)n}$ is equivalent to ${x_m=x_{m+n}=\cdots=x_{m+(k-1)n}}$ , that is, $\displaystyle d\left(T^m\underline x,T^{in}T^m\underline x\right)<1\, ,\ i=1,2,\ldots,k. \ \ \ \ \ (2)$

This condition is guaranteed by the

Theorem 7 (Furstenberg-Weiss topological multiple recurrence) Let ${T:X\rightarrow X}$ be a continuous map of the compact metric space ${(X,d)}$ . Then, for any ${k\in\mathbb{N}}$ and ${\varepsilon>0}$ , there exist ${n\in\mathbb{N}}$ and ${x\in X}$ such that

$\displaystyle d\left(T^{in}x,x\right)<\varepsilon\, ,\ i=1,2,\ldots,k.$

Moreover, given any dense subset ${Y\subset X}$ , we can take ${x\in Y}$ .

Consider the transformation ${T:\mathcal O(\underline x)\rightarrow\mathcal O(\underline x)}$ . By Theorem 7, we can fix ${m\in\mathbb{N}}$ such that, for some ${n\in\mathbb{N}}$ , the element ${\underline y=T^m\underline x}$ satisfies

$\displaystyle d\left(\underline y,T^{in}\underline y\right)<1\,,\ i=1,2,\ldots,k,$

which is exactly (2). This concludes the proof of Theorem 1.

Previous posts: ERT0, ERT1, ERT2, ERT3, ERT4, ERT5.

Like this:

Be the first to like this post.

Posted in expository, guest blog, math.DS, Mathematics | Tags: IP-set, topological multiple recurrence, van der Waerden

M	T	W	T	F	S	S
« Jan				Mar »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28

	matheuscmss on Diffusion in Ehrenfest wind-tr…
	yglima on Diffusion in Ehrenfest wind-tr…
	yglima on CF1: uniform distribution and …
	vdelecroix on CF1: uniform distribution and …
	matheuscmss on CF1: uniform distribution and …

Disquisitiones Mathematicae

ERT6: Topological Dynamics and van der Waerden Theorem

Like this:

Leave a Reply Cancel reply

Categories

Archives

Mathematics

politics

Recent Posts

Tags

Top Posts

Recent Comments

Follow “Disquisitiones Mathematicae”