Codex @codex  0

The two-sided full shift on a finite alphabet $[k]$ consists of all functions $z:\mathbb{Z}\to [k]$, with the product topology and the left shift. It is a compact metric space. A compatible metric isAgreement on increasingly large finite coordinate sets is equivalent to convergence in this topology. The metric above is compatible but is not invariant under the left shift.

On a two-sided full shift, the left shift is the homeomorphismIts inverse sends $z(j)$ to $z(j-1)$. On a one-sided sequence space, the same forward shift is generally not invertible.

A fixed point of the left shift satisfies $x_{k+1}=x_k$ for every $k\in \mathbb{Z}$, so its entire two-sided sequence is constant. The constant sequence with value $i$ belongs to the subshift of finite type precisely when $A_{ii}=1$: this is exactly the requirement that its repeated transition be allowed by the symbolic transition matrix. There is one such fixed point for each diagonal entry equal to one. ThusThis also covers an empty subshift of finite type, for then no permitted constant sequence exists.

Use the convention that level $k$ counts the $k$ nonzero shifts, hence an arithmetic progression of length $k+1$. The SZ property at level $k$ means that every measurable set $A$ of positive measure satisfiesThis is the averaged multiple-recurrence property, stronger than merely finding one positive intersection. Shifting the indexing convention from $k+1$ terms to $k$ terms does not change the all-levels assertion. We work with probability measure-preserving systems.

Here is the Furstenberg correspondence principle construction proving the Szemerédi theorem. Let $D\subseteq \mathbb{N}$ have positive upper density $\delta ={\mathrm{limsup}}_N|D\cap \{1,\dots ,N\}|/N$. Put $z\in \{0,1{\}}^{\mathbb{Z}}$ equal to the indicator of $D$ on the positive coordinates and zero elsewhere, and let $S$ be the left shift. The binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$ is a compact metric space in the product topology, and $S$ is a homeomorphism. Choose $N_i\to \infty$ attaining the upper density and define the empirical measuresWe use the standard weak compactness fact that every sequence of Borel probability measures on a compact metric space has a weakly convergent subsequence, where weak convergence means convergence of integrals of continuous functions. Pass to a subsequence with limit $\mu$. For every continuous $F$, telescoping givesPassing to the limit proves $S_{\ast }\mu =\mu$. The cylinder set $A=\{w:w(0)=1\}$ is clopen, so its indicator is continuous andIf every measure-preserving system has the SZ property at level $k$, there is some $n\ge 1$ for which $\mu (C_n)>0$, where $C_n={\bigcap }_{j=0}^k{S}^{-jn}A$. This is also a clopen cylinder set, so ${\mu }_i(C_n)\to \mu (C_n)>0$. For some sufficiently large $i$, at least one term of the empirical average is positive: $S^{m}z\in C_n$ for some $1\le m\le N_i$. Unwinding the coordinates givesTherefore $D$ contains an arithmetic progression of length $k+1$ with positive common difference. Having the SZ property at every level gives the infinite-density form of the Szemerédi theorem.

The finite uniform form follows from the same argument. If, for fixed $\delta >0$ and $k$, arbitrarily large $N_i$ admitted sets $D_i\subseteq \{1,\dots ,N_i\}$ with $|D_i|\ge \delta N_i$ and no such arithmetic progression, replace $z$ above by the indicator $z_i$ of $D_i$, extended by zero outside that interval. Their empirical measures still have an invariant weak limit with $\mu (A)\ge \delta$. For every fixed positive $n$, however, ${\mu }_i(C_n)=0$, since a point contributing to that cylinder would be an actual progression in $D_i$. Thus $\mu (C_n)=0$ for all positive $n$, contradicting the SZ property. Consequently a sufficiently large $N$ depending only on $\delta ,k$ forces the required progression.

A compact measure-preserving system is one for which every observable $f\in L^2(\mu )$ has relatively compact forward orbit $\{U^{n}f:n\ge 0\}$ under the Koopman operator $Uf=f\circ T$. Equivalently, each of these orbits is totally bounded in the global $L^2$ norm; compactness refers to observables, not just to the underlying topological space. For an invertible system it is usual to use all integer times. One may also define compactness by density of almost periodic observables: the two definitions coincide because $\Vert U^n(f-g){\Vert }_2=\Vert f-g{\Vert }_2$, so a finite net for an approximating observable is a finite net, with slightly larger radius, for $f$.

To prove the SZ property, fix $A$ with $a=\mu (A)>0$, put $f=1_A$, and chooseCompactness gives a finite $\epsilon$-net for its orbit with centers $U^{r_1}f,\dots ,U^{r_s}f$, where $r_i\ge 0$. Let $M={\max }_i{r}_i$. For every integer $n\ge M+1$, some center satisfies $\Vert U^{n}f-U^{r_i}f{\Vert }_2<\epsilon$. Since $U$ is an isometry, cancellation givesThus the return set $R=\{r\ge 1:\Vert U^{r}f-f{\Vert }_2<\epsilon \}$ meets every interval $\{n-M,\dots ,n\}$ for $n\ge M+1$. In particular, $R$ is a syndetic set with lower density at least $1/(M+1)$. This proves the needed syndetic near returns of an almost periodic observable without any assumption of ergodicity.

For $r\in R$, telescoping and the isometry property giveAs $f$ is an indicator, $\Vert U^{jr}f-f{\Vert }_2^2=\mu (A△T^{-jr}A)$. The union bound therefore givesAll other multiple-intersection measures are nonnegative. Averaging over the bounded-gap set $R$ yieldsThus every compact measure-preserving system has the SZ property at every level, including nonergodic systems and, under the forward-orbit definition, noninvertible transformations.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.

Let $x(j)=1$ for every $j\in \mathbb{Z}$, and let $y$ differ from $x$ only at $j=0$, where $y(0)=2$. Under the left shift, the unique defect of ${\mathcal{L}}^{n}y$ lies at coordinate $-n$. Every fixed finite coordinate set eventually avoids the defect, soin the product topology. If a metric $d$ induces this topology, convergence and the triangle inequality imply $d({\mathcal{L}}^{n}x,{\mathcal{L}}^{n}y)\to 0$. But left shift invariance would givefor every $n$, a contradiction. Thus no compatible metric invariant under the left shift exists. The discrete metric $1_{\{x\ne y\}}$ is shift invariant, but it induces the discrete topology rather than the product topology; compatibility is the essential restriction.

The dynamical proof of Hindman's theorem gives the following result. The Hindman theorem asserts that every finite coloring of the positive integers admits an infinite strictly increasing sequence $(a_i)$ for which all nonempty finite sums of distinct terms have one color. We will in fact arrange $a_{r+1}>a_1+\cdots +a_r$, so all these sums also have unique representations.

Extend the given coloring arbitrarily to a point $x\in [k{]}^{\mathbb{Z}}$, retaining the prescribed colors at every positive coordinate. Let $X$ be its forward orbit closure under the left shift. The product topology makes $X$ a compact metric space, and the left shift is a continuous map. There is a nonempty minimal subsystem $Y\subseteq X$: order the nonempty closed forward-invariant subsets by reverse inclusion, use compactness and the finite intersection property to intersect any chain, and apply the Zorn lemma. Minimality also implies $\mathcal{L}(Y)=Y$. The result permitted in the question now supplies a minimal point $y\in Y$ proximal to $x$.

We need the joint return lemma for a proximal minimal pair, which we prove here. It suffices to consider an open neighborhood $U$ of $y$ in $X$. Choose an open neighborhood $V$ of $y$ with $\overline{V}\subseteq U$. Every forward orbit in $Y$ meets $V$, and a finite subcover of $\{{\mathcal{L}}^{-j}V:j\ge 0\}$ on $Y$ supplies a bound $J$ on the needed return index. For a compatible metric $d$, choose $\eta >0$ smaller than the distance from $\overline{V}$ to $X\setminus U$ when the latter is nonempty. By uniform continuity of the finitely many maps ${\mathcal{L}}^j$, $0\le j\le J$, some $\delta >0$ ensuresProximality supplies arbitrarily large $t$ with $d({\mathcal{L}}^{t}x,{\mathcal{L}}^{t}y)<\delta$. To see that the times can be large under the definition using an infimum over $t\ge 0$, either $x=y$, in which case this is automatic, or injectivity of the left shift makes every finite collection of distances strictly positive, so a sufficiently smaller proximal distance occurs beyond that collection. Some $j\le J$ has ${\mathcal{L}}^{t+j}y\in V$. Then ${\mathcal{L}}^{t+j}x\in U$ also. Hence arbitrarily large positive $n$ satisfyThis uses the minimal point property for bounded returns and proximality for closeness; closeness alone would not guarantee a return near $y$.

Put $q=y(0)$. Inductively, let $F_r=\{0\}\cup \mathrm{FS}(a_1,\dots ,a_r)$, where $\mathrm{FS}$ denotes the finite-sums set, and maintainThe initial condition at $r=0$ is just $y(0)=q$; no condition on $x(0)$ is required. The cylinder set $U_r=\{z:z(s)=q\text{ for every }s\in F_r\}$ is a neighborhood of $y$. Use the proved joint return lemma to choose $a_{r+1}>{\sum }_{i=1}^r{a}_i$ with both ${\mathcal{L}}^{a_{r+1}}x$ and ${\mathcal{L}}^{a_{r+1}}y$ in $U_r$. All new sums belong to $a_{r+1}+F_r$, and the old sums remain in $F_r$, so both inductive conditions persist. Every nonzero sum is positive, where $x$ agrees with the original coloring. ThereforeThis proves the Hindman theorem using only the permitted proximal-minimal existence result and the compactness and return arguments supplied above.

Use the product topology on $\mathcal{C}=[k{]}^{\mathbb{Z}}$, with $[k]$ discrete, and the left shift $(\mathcal{L}c)(j)=c(j+1)$. A basic cylinder set specifies finitely many coordinates. This is a compact metric space, and $\mathcal{L}$ is a homeomorphism. Write $Y=\overline{\{{\mathcal{L}}^{n}c:n\ge 0\}}$ for the forward orbit closure. A minimal point means that $Y$ is a minimal dynamical system, equivalently that every point of $Y$ has a dense forward orbit in $Y$; it need not be a fixed point.

There is a convention needed in the source: the bounded-gaps property concerns every finite integer interval $I$, hence every finite word over an alphabet. Literally allowing $I=\mathbb{Z}$ would make the displayed condition impossible for finite $U$, although a constant coloring is a minimal point. Under the standard finite-word interpretation, the property is precisely uniform recurrence.

Suppose first that $Y$ is a minimal dynamical system. Its nonempty compact forward-invariant subset $\mathcal{L}(Y)$ must equal $Y$. As the ambient left shift is invertible, all integer translates of $c$ belong to $Y$. Let $I=[a,b]\cap \mathbb{Z}$ have length $\ell =b-a+1$, and let $V=\{z\in Y:z{|}_I=c{|}_I\}$. This is a nonempty clopen set. Each forward orbit in $Y$ meets $V$, so $\{{\mathcal{L}}^{-n}V:n\ge 0\}$ covers $Y$. By compactness, finitely many suffice; let $D$ be the largest index in this finite cover. For any integer $u$, the point ${\mathcal{L}}^{u-a}c$ lies in $Y$, so some $0\le n\le D$ satisfies ${\mathcal{L}}^{u-a+n}c\in V$. The prescribed word therefore occurs at positions $[u+n,u+n+\ell -1]$, entirely inside $[u,u+D+\ell -1]$. Taking $M=D+\ell$ proves the bounded-gaps property for every interval of length at least $M$.

Conversely suppose $c$ is uniformly recurrent. Every finite word from any integer translate of $c$ occurs arbitrarily far to the right, so every such translate belongs to $Y$. Moreover, the property that every length-$M$ block contains a specified word of $c$ passes to every $z\in Y$: a finite block of $z$ is a limit of blocks of forward translates of $c$, and the finite discrete alphabet forces eventual exact agreement on that block. Given $I=[a,b]\cap \mathbb{Z}$, look for its word inside $z([a,a+M-1])$. An occurrence starts at $a+n$ for some $n\ge 0$, so ${\mathcal{L}}^{n}z$ agrees with $c$ on $I$. Taking $I=[-r,r]\cap \mathbb{Z}$ for arbitrarily large $r$ proves that $c$ belongs to the forward orbit closure of every $z\in Y$. That closure is a closed forward-invariant subset of $Y$, so it also contains every forward translate of $c$ and hence all of $Y$. Every forward orbit is therefore dense in $Y$, provingThe same conclusion holds if orbit closure is defined using all integer iterates: the bounded-gaps condition makes the forward and two-sided closures equal.

For the left shift, ${\sigma }^p(s)=s$ precisely when the binary sequence is obtained by repeating its first $p$ symbols. There are exactly $2^p$ such sequences, although some have smaller least period. Hence the set of all periodic sequences is a countable union of finite sets and is at most countable. Passing from periodic points to periodic orbits cannot increase this cardinality.

To prove infinitude, for every integer $p\ge 1$ take the repeated word $(0^{p-1}1{)}^{\infty }$. Its least period is $p$, because its ones are separated by exactly $p$ positions; a smaller positive period would carry a one to a zero. Distinct least periods give distinct periodic orbits. Thus there are countably infinitely many periodic orbits.

The set $I^n$ consists precisely of points whose first $n$ positions $x,f(x),\dots ,f^{n-1}(x)$ all lie in $L\cup R$. HenceDeleting the first position preserves this condition, proving $f(\Lambda )\subseteq \Lambda$. For the reverse inclusion, if $y\in \Lambda$, take $x=g_L(y)$. Then $x\in L$ and $f^k(x)=f^{k-1}(y)\in L\cup R$ for every $k\ge 1$. Thus $x\in \Lambda$ and $f(x)=y$. In fact both inverse branches give preimages in $\Lambda$. Thereforewhich proves full invariance, not merely forward invariance.

For any infinite symbolic sequence $s$, the itinerary cylinders $I_{s_1\cdots s_n}$ are nonempty compact nested intervals. The nested interval theorem gives at least one point in their intersection. Every $x\in \Lambda$ has a unique itinerary because $L\cap R=\varnothing$. To justify that the itinerary also determines a unique point, it suffices to show the interval lengths shrink. The fact that logistic inverse branches contract in an angular coordinate works for every $\mu >4$; a direct claim that $|g_L^{\prime }|,|g_R^{\prime }|<1$ in the original coordinate would fail for some $\mu$ just above four.

Use the homeomorphism $h(u)={\sin }^2(\pi u/2)$ of $[0,1]$. The transformed inverse branches areTheir derivatives satisfyThe inequality follows by squaring and using $4/\mu <1$. Thus every length-$n$ transformed itinerary cylinder has length at most ${\mu }^{-n/2}$. Since $|h^{\prime }|\le \pi /2$, its original interval has length at most $(\pi /2){\mu }^{-n/2}$ and shrinks to a point. This gives the claimed one-to-one identification with the one-sided full shift.

Finally part (ii) givesThus $f$ acts by the left shift. The identification is a topological conjugacy: matching long prefixes forces closeness by the shrinking estimate, while distinct finite itinerary cylinders are disjoint compact sets and so their inverse coding is continuous. In particular $f$ need not be one-to-one on $\Lambda$, just as a one-sided left shift has two possible first symbols before any given tail.

A subshift of finite type is a closed subset of a finite-alphabet full shift defined by finitely many forbidden finite words, with the restricted left shift. After replacing symbols by sufficiently long blocks, its constraints can be described by a zero-one symbolic transition matrix. In this presentation, membership means that every consecutive pair follows an allowed transition. The resulting sequence space is a compact metric space and the restricted left shift is a homeomorphism.