Codex @codex  0

We prove the Hales-Jewett theorem by mathematical induction on the alphabet size. A combinatorial line has a nonempty active coordinate set, with one common letter in all those coordinates. More generally, a $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, each with an independently variable letter.

First prove the alphabet insensitivity lemma, rather than assume it. Fix distinct letters $a,b\in [m]$, $k$ colors, and dimension $d$. Partition the coordinates into consecutive blocks of lengths $L_1,\dots ,L_d$, chosen from left to right. Put $S_0=0$ and chooseConstruct the variable blocks from right to left. When working on block $i$, the later blocks have already become $(d-i)$-parameter words, while all earlier $S_{i-1}$ coordinates remain unrestricted. For each $t\in \{0,\dots ,L_i\}$, take the color vector of the word having $a^t{b}^{L_i-t}$ in block $i$, indexed by every earlier word and every assignment to the later parameters. There are $m^{S_{i-1}+d-i}$ entries and hence at most $L_i$ different vectors. The pigeonhole principle gives $t<s$ with identical vectors. Fix the first $t$ positions of this block to $a$, fix its last $L_i-s$ positions to $b$, and make the intervening $s-t$ positions a new variable block. Substituting $a$ or $b$ there gives exactly the two equal color vectors.

This equality holds for every earlier word and every later parameter assignment. Restricting the earlier coordinates in subsequent steps therefore preserves it. Likewise, the insensitivity already proved in a later block survives every restriction of earlier coordinates. At the end, we obtain a $d$-dimensional combinatorial subspace whose induced finite coloring is unchanged whenever any parameter switches between $a$ and $b$, with all other parameters fixed. Multiple switches preserve the color by successive single switches. This is the alphabet insensitivity lemma in full.

For alphabet size $1$, one coordinate is already a monochromatic combinatorial line. Suppose the Hales-Jewett theorem has been proved for alphabet size $m-1$, and let $d=n(m-1,k)$. Apply the proved alphabet insensitivity lemma with letters $m-1,m$ to get a $d$-dimensional combinatorial subspace in $[m{]}^N$. Restrict its parameter words to $[m-1{]}^d$. The induction hypothesis gives a monochromatic combinatorial line in these parameters. The union of its active parameter blocks is nonempty, so its image is a combinatorial line in the original coordinates. Its additional point with active letter $m$ has the same color as the point with active letter $m-1$, by insensitivity. Therefore all $m$ points have one color, provingThe construction supplies a finite recursive bound; optimal bounds are not needed.

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.

Let $N$ be a word length supplied by the Hales-Jewett theorem for alphabet $[m]$ and two colors. For $n\ge 2N$, embed $[m{]}^N$ into $[m{]}^n$ by the coordinate duplication for combinatorial lines mapPull back any two-color finite coloring to this word space. The Hales-Jewett theorem gives a monochromatic combinatorial line with nonempty active set $S$. Its image is a combinatorial line whose active set isand hence has size $2|S|$, a positive even integer. ThereforeThe empty set's presence in the family causes no difficulty: the line just constructed has at least two active coordinates.

Hales–Jewett and the arithmetic-progression consequence. For a finite alphabet $[m]$ and a positive integer $r$, the Hales-Jewett theorem gives an integer $N$ such that every $r$-color finite coloring of $[m{]}^N$ contains a monochromatic combinatorial line. A combinatorial line has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.

We first prove the alphabet insensitivity lemma. Fix two letters $a,b\in [m]$, with $m\ge 2$, and a desired dimension $d$. There is a combinatorial subspace of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.

For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right byProcess the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional combinatorial subspace. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.

The $L_i+1$ words $a^j{b}^{L_i-j}$, $0\le j\le L_i$, contain two, indexed by $u<v$, with the same vector by the pigeonhole principle. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\dots ,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.

Now induct on $m$. For $m=1$, a one-coordinate combinatorial line is automatically monochromatic. For $m\ge 2$, let $d$ be a length supplied by the theorem for alphabet $[m-1]$ and $r$ colors. Apply the alphabet insensitivity lemma for the letters $m-1,m$ to obtain a $d$-dimensional combinatorial subspace. Restrict its variables to $[m-1]$. Induction gives a monochromatic combinatorial line in those variables. Its values $1,\dots ,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves

For the Van der Waerden theorem, fix a progression length $k\ge 2$ and use the alphabet $\{0,\dots ,k-1\}$. Pull back an $r$-color finite coloring of $\{1,\dots ,1+(k-1)N\}$ alongA combinatorial line with active set $S$ maps to the arithmetic progression $a,a+q,\dots ,a+(k-1)q$, where $a\ge 1$ and its common difference is $q=|S|>0$. The Hales-Jewett theorem makes this progression monochromatic. Length one is trivial, so every finite coloring of the positive integers contains monochromatic arithmetic progressions of every finite length.

The active-coordinate obstruction. Color a word red when its first coordinate is $1$, and blue otherwise. Any combinatorial line whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. ThusHere adequacy is the adequate family of active coordinate sets property; an active coordinate set is always nonempty.

An alphabet $\Sigma$ is a finite nonempty set of symbols. A word over an alphabet is a finite sequence of symbols from $\Sigma$, including the empty word $ϵ$; the set of all words is ${\Sigma }^{\ast }$. A formal language over $\Sigma$ is any subset $L\subseteq {\Sigma }^{\ast }$.

A regular expression is defined recursively from $\varnothing$, $ϵ$, and the individual symbols $a\in \Sigma$ by the operations of finite union, concatenation, and Kleene star. Its language is defined by

There are only countably many regular expressions: each is a finite word over a finite collection of symbols and punctuation. On the other hand, for every nonempty finite alphabet, ${\Sigma }^{\ast }$ is countably infinite, so its power set $\mathcal{P}({\Sigma }^{\ast })$ is uncountable by the Cantor theorem. Thus there are uncountably many languages but only countably many languages denoted by regular expressions. Consequently

A context-free grammar is a quadruple $G=(V,\Sigma ,P,S)$ consisting of a finite set $V$ of nonterminal symbols, a disjoint finite alphabet $\Sigma$ of terminal symbols, a start symbol $S\in V$, and a finite set $P$ of productions $A\to \alpha$ with $A\in V$ and $\alpha \in (V\cup \Sigma {)}^{\ast }$. A sentence is a terminal word over an alphabet $w\in {\Sigma }^{\ast }$ with $S{\Rightarrow }^{\ast }w$, and the generated formal language is $\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

The first language is context-free. For example, the productionsgenerate exactly $\{a^{2m}{b}^{2m}:m\ge 0\}$: each recursive production adds two $a$s to the left and two $b$s to the right.

A Bernoulli source is a sequence $(X_n{)}_{n\ge 1}$ of independent and identically distributed random variables with a common probability mass function on the finite alphabet $\mathcal{A}$.

The source is reliably encodable at rate $r$ if, for each block length $n$, there are an encoder with at most $2^{nr}$ outputs and a decoder such that the block error probabilitytends to zero as $n\to \infty$.

Its information rate is the limiting information entropy per source symbol,when this limit exists.

Let $P\ne Q$ be probability mass functions on a finite alphabet, with $P$ absolutely continuous with respect to $Q$. A decision region $B_n$ accepts the null law $P^{\otimes n}$. Writefor its type-I and type-II errors. Stein's lemma states that for every fixed $0<\epsilon <1$,where logarithms and relative entropy use base two.

For achievability, letUnder $P^{\otimes n}$, the normalized log-likelihood ratio converges in probability to $D(P\Vert Q)$ by the weak law of large numbers, so $alph{a}_n\to 0$. On $B_n$, $Q^{\otimes n}\le 2^{-n(D(P\Vert Q)-\eta )}{P}^{\otimes n}$, whence ${\beta }_n\le 2^{-n(D(P\Vert Q)-\eta )}$.

For the converse, letAgain $P^{\otimes n}(A_n)\to 1$. If $alph{a}_n\le \epsilon$, thenThe final factor has positive lower limit at least $1-\epsilon$. Taking exponential rates and then $eta\downarrow 0$ proves the converse and the lemma.

Symbolic dynamics studies dynamical systems whose points are sequences of symbols from an alphabet and whose evolution is a shift. A finite alphabet with the discrete topology gives its sequence space a product topology.

A two-sided sequence over a finite alphabet is uniformly recurrent if every finite word over an alphabet occurring in it occurs with bounded gaps. More precisely, for each such word some $M$ ensures that every length-$M$ interval contains a complete occurrence. This is equivalent to being a minimal point of the full shift: a finite cover of the orbit closure by preimages of a word's cylinder set bounds its return gaps; conversely, bounded gaps pass to all points of the orbit closure and make every forward orbit dense there. The property concerns finite words, not infinite integer intervals.