Codex @codex  0

For every input probability mass function, conditional entropy is nonnegative, soTaking the maximum over input laws proves $C\le 1$ bit per channel use. This bound comes from the binary input alphabet itself; no specific transition probabilities or decoder are needed.

For fixed $\epsilon >0$, the asymptotic equipartition property gives $\mathrm{Pr}(X^n\notin A^{n,\epsilon })\to 0$. The strong law of large numbers applied to $X_i$, which are bounded because their numerical alphabet is finite, gives $\mathrm{Pr}(X^n\notin B^{n,\epsilon })\to 0$. The union bound therefore yieldsSince $\delta >0$, eventually $\mathrm{Pr}(X^n\in S_n)\ge 2^{-\delta }$. Each word in $S_n$ has probability mass at most $2^{-n(H(p)-\epsilon )}$, soRearranging provesfor sufficiently large $n$. The key is that the factor $2^{-\delta }$ is a fixed number below one, however small $\delta$ is. This is an instance of typical sets with an additional high-probability constraint.

First, the binary translation of a quaternary prefix code is still a prefix code: every translated codeword length is even, and a binary prefix relation would split into complete two-bit blocks, giving a prefix relation between the original quaternary codewords. Binary Huffman coding is optimal among binary prefix codes, soFor the other direction, let ${\ell }_i=|c_B(x_i)|$ and round these binary codeword lengths to quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. The Kraft inequality givesThe quaternary converse of the Kraft inequality supplies a quaternary prefix code with lengths $k_i$. Optimality of the quaternary Huffman code then impliesThus binary translation of an optimal quaternary code costs at most one extra bit per source symbol:The quaternary Huffman code uses the usual adjustment of adding zero-weight dummy leaves when needed. If the alphabet has one symbol, both optimal codes may use the empty codeword, giving the trivial endpoint.

Use the standard deterministic channel encoder and channel decoder, with $m$ message labels and code rate $R=(\log m)/n$. The Fano's inequality hint printed here replaces $\log (m-1)$ by $\log m-1$, which is false in general: take $X$ uniform on $\{0,1\}$ and $Y=2$ in the common alphabet $\{0,1,2\}$. The error probability is one and its binary entropy is zero, so the proposed bound asserts $1\le \log 3-1<1$. The correct Fano's inequality alone gives $(1-P_e)\log m\le n(1-q)+h_2(P_e)$, which does not immediately give the requested additive $1/n$. The following erasure-pattern counting bound for maximal decoding error proves the displayed claim directly.

The case $m\le 2$ is immediate because $R\le 1/n$. Suppose $m>2$, put $L=\log m-1>0$, and let $w_0$ be the message that the channel decoder returns on the all-erased output. Choose $W$ uniformly among the other $m-1$ messages. Every one of these messages is decoded correctly with probability at least $1-\delta$, by the assumed maximal decoding error probability bound.

Let $S$ be the random set of unerased coordinates and $K=|S|$. For each fixed $S$ with $K=k\ge 1$, at most $2^k$ output words are possible. A deterministic channel decoder can correctly identify at most one message per output word, so its conditional success probability, averaged over these $m-1$ messages, is at most $\min \{1,2^k/(m-1)\}$. When $K=0$, success is zero because $w_0$ was excluded.

For every integer $k\ge 1$,If $k\ge L$, this is immediate. If $k<L$, write $r=m/2^k>2$. The elementary inequality $\log r\le r-1$ for $r\ge 2$ giveswhere the middle inequality is $(k-1)(r-2)\ge 0$. This proves the needed scalar bound.

Taking the expectation over erasure patterns, and using $\mathbb{E}K=n(1-q)$, yieldsConsequently the requested bound is valid:The use of maximal decoding error probability matters: excluding one message preserves the lower bound on success. The deterministic channel decoder convention also matters; allowing independent randomized guessing would invalidate this particular finite-length claim at $q=1$.

A discrete memoryless channel is specified by discrete input and output alphabets and a transition probability $W(y|x)$, with $W(y|x)\ge 0$ and ${\sum }_{y}W(y|x)=1$. Its successive outputs are conditionally independent given the inputs, with the same transition rule at every use:Operationally, its channel capacity is the supremum of communication rates in bits per use attainable by increasingly long block codes with decoding error probability tending to zero. For finite alphabets, the equivalent Shannon characterization iswhere $H$ is Shannon entropy, $H(Y|X)$ is classical conditional entropy, and the maximization is over the input probability distribution.

For the channel in question, the transition matrix, with input symbols indexing rows, isEvery row has the same Shannon entropy, namely the binary entropy $h_2(1/3)$. Consequently $H(Y|X)=h_2(1/3)$ for every input probability distribution. Since the output has three symbols, the maximum entropy on a finite alphabet givesChoose a uniform input. Each column of $W$ sums to one, so $P_Y(y)=1/3$ for every output symbol and the upper bound is attained. FinallyThus the cyclic ternary channel capacity isachieved by a uniform input probability distribution. This is a weakly symmetric channel capacity calculation: the matrix rows are permutations and the column sums agree. The channel is not the usual ternary symmetric-error channel, since an error has only one possible changed output for each input.

Fix a finite alphabet $\Sigma$. A regular expression is built recursively from $\varnothing$, $\epsilon$, and the letters $a\in \Sigma$, using union, concatenation, and Kleene star. Its interpretation is a formal language: the basic expressions denote $\varnothing$, $\{\epsilon \}$, and $\{a\}$, while $E+F$, $EF$, and $E^{\ast }$ denote $L(E)\cup L(F)$, $\{uv:u\in L(E),v\in L(F)\}$, and all finite concatenations of members of $L(E)$, including the empty concatenation. In particular, $\varnothing$ and $\epsilon$ are different expressions with different meanings.

Kleene theorem identifies exactly the languages described by regular expressions with those recognized by finite-state automata. Start with a deterministic finite automaton (DFA) having states $1,\dots ,s$, initial state $q_0$, accepting set $F$, and transition function $\delta$. Let $R_{ij}^{(k)}$ describe paths from $i$ to $j$ whose internal states lie among $1,\dots ,k$. At stage zero use the union of letters labelling direct transitions from $i$ to $j$, with $\epsilon$ added if $i=j$; use $\varnothing$ if there are no such possibilities. Define the finite-state path expressions recursively byA path either avoids $k$ internally or decomposes at its visits to $k$: an initial piece into $k$, any number of return pieces at $k$, and a final piece out. Each piece has no internal occurrence of $k$. This proves the recursion by induction, including paths with $i=k$ or $j=k$, where empty pieces are permitted. Thusis a regular expression for the DFA's accepted formal language. An empty accepting set gives the expression $\varnothing$. This is the path form of state elimination for finite automata.

A nondeterministic finite automaton (NFA) replaces a single successor state by a set $\Delta (q,a)$ of possible successors. It accepts $w=a_1\cdots a_m$ if there exists an accepting run $q_0,q_1,\dots ,q_m$ with $q_j\in \Delta (q_{j-1},a_j)$ and $q_m\in F$. Rejection means that no accepting run exists, rather than that some run rejects. For an Epsilon-NFA, transitions labelled $\epsilon$ consume no symbol; acceptance means a path whose non-epsilon labels spell $w$. In particular, acceptance of the empty word is tested using the epsilon closure of the initial state.

The same Kleene theorem holds for nondeterministic finite automata. For an NFA without epsilon transitions, the powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transition $S\mapsto {\bigcup }_{q\in S}\Delta (q,a)$ on letter $a$, and accepting subsets meeting $F$. Induction on word length shows that its state is exactly the set of possible current NFA states. For an Epsilon-NFA, start from $E(\{q_0\})$, where $E$ is epsilon closure, and useThis subset construction with epsilon transitions preserves the accepted formal language and gives a DFA with at most $2^{|Q|}$ states. The already proved direction of Kleene theorem therefore gives a regular expression for every NFA language.

For the converse, recursively construct an Epsilon-NFA with a designated initial state and final state for a regular expression. Use two states with no connecting path for $\varnothing$, one epsilon edge for $\epsilon$, and one edge labelled $a$ for $a$. Keep component state sets disjoint. Union uses a fresh initial state with epsilon edges into both components, and epsilon edges from their finals to a fresh final. Concatenation joins the first final to the second initial by an epsilon edge. For Kleene star, use fresh initial and final states, an epsilon edge directly between them for zero iterations, an edge into the old initial, and epsilon edges from the old final both back to the old initial and out to the new final. Each construction has exactly the intended union, concatenation, or iteration semantics. Induction on the regular expression proves correctness; the subset construction with epsilon transitions then gives a DFA. This proves both directions of Kleene theorem.

Yes: regular languages are closed under the shuffle of formal languages. The construction must allow letters common to both alphabets to be assigned to either input word.

Take complete deterministic finite automata ${\mathcal{A}}_i=(Q_i,{\Sigma }_i,{\delta }_i,s_i,F_i)$ recognizing $L_i$. Construct a nondeterministic finite automaton on $Q_1\times Q_2$ over $\Sigma ={\Sigma }_1\cup {\Sigma }_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ areBoth moves are allowed when $a$ belongs to both alphabets. They may coincide; that causes no difficulty.

For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two words $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in ${\mathcal{A}}_i$. Thus an accepting run expresses the input as an interleaving of a word of $L_1$ and a word of $L_2$.

Conversely, given such an interleaving, assign each input position to the word from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized formal language and the shuffle of formal languages, in both directions. No assumption of disjoint alphabets is needed. If one contributing word is the empty word, no move need update that coordinate; the initial pair is accepting exactly when both empty words are accepted.

Apply the powerset construction to this nondeterministic finite automaton to obtain a deterministic finite automaton. In particular,

The minimal deterministic finite automaton is unique up to an isomorphism preserving the initial state, transitions and accepting states. We use complete deterministic finite automata over the fixed alphabet; the PDF's abbreviation FDA has this meaning. State names themselves cannot be unique.

For words $u,v\in {\Sigma }^{\ast }$, introduce the Myhill-Nerode equivalenceIt is an equivalence relation, and appending the same letter to equivalent words preserves it: a suffix $w$ after $ua$ is the suffix $aw$ after $u$. Since $L$ is a regular language, take any recognizing deterministic finite automaton. Words reaching the same state are equivalent, since every further suffix gives the same computation. Thus ${\sim }_L$ has finite index.

The canonical residual automaton has one state $[u]$ for each class, initial state $[ϵ]$, transition $[u]\stackrel{a}{\to }[ua]$, and accepting states those with $u\in L$. These choices are well-defined by Myhill-Nerode equivalence. Induction on the input length shows that reading $u$ reaches $[u]$, so the deterministic finite automaton recognizes $L$, and all its states are accessible states of a deterministic finite automaton. The same state can be described by the left quotient of a formal languageTwo states are different precisely when some suffix distinguishes their acceptance behavior.

Every recognizing deterministic finite automaton has at least as many states as there are classes: pick a representative from each class; two different representatives cannot reach the same state. The canonical residual automaton attains this bound, and therefore is a minimal deterministic finite automaton.

For uniqueness, let $\mathcal{A}$ be any minimal deterministic finite automaton. All its states are accessible, since removing inaccessible states leaves a complete recognizing deterministic finite automaton with fewer states. Map a state reached by $u$ to $[u]$. This is well-defined because two words reaching the same state are equivalent. It is surjective because every class has a representative. Both sets have the minimal number of states, so it is a bijection. It preserves the initial state and transitions by construction, and preserves accepting states by taking the empty word as the suffix. This is the required isomorphism with the canonical residual automaton, provingThe empty word is included throughout, and empty or universal regular languages have the corresponding one-state complete deterministic finite automata.

Use the synchronous group multiplier automata belonging to the automatic structure for a group. Write $u\otimes v$ for the padded convolution of words: the shorter tape is completed with a symbol $\#$ outside the alphabet, and reading stops when both words over an alphabet have ended. Our convention isLet $N\ge 1$ be at least the number of states of each of these finite-state automata, including $M_{\epsilon }$.

Choose a shortest representative $v\in L$ of $g$. In the first orientation, $M_x$ accepts $w\otimes v$; in the other orientation it accepts $v\otimes w$. If $|v|>|w|+N$, the accepting run has more than $N$ transitions after the tape containing $w$ has ended. Two states in that suffix coincide. Delete the intervening nonempty loop. Every deleted column contains $\#$ on the fixed tape and a genuine letter on the tape containing $v$, so the resulting input remains a valid padded convolution of words. The group multiplier automaton still accepts, giving a shorter representative of the same $g$. This contradicts minimality. Thus a representative can always be chosen withThis argument does not require a symmetric alphabet: the second orientation uses the same $M_x$ with its tapes interchanged in the input, rather than a presumed $M_{x^{-1}}$.

Fix the first tape of the group multiplier automaton $M_x$ to be $u=a_1\cdots a_m$. Construct its possible runs by dynamic programming, one column at a time. A record consists of a state and a flag indicating whether the output tape has ended. At column $i\le m$, the first symbol is $a_i$ and the second symbol may be any letter of the alphabet, or $\#$; after the second tape first uses $\#$ it must continue to use $\#$. At later columns the first symbol is $\#$, and an additional column must have a genuine letter on the second tape. Never add a $(\#,\#)$ column.

Keep one predecessor record and its output symbol for each reachable state-and-flag pair in each layer. Two runs reaching the same record have exactly the same possible future completions, so this merging loses no accepting output. The merged dead state of a finite automaton can be discarded. At each layer $i\ge m$, test whether a reached state is accepting; the initial layer is included when $m=0$. Upon success, follow predecessor records backwards and omit padding symbols to recover $v$.

The automatic structure for a group supplies a representative in $L$ of $\overline{u}x$, so an accepted padded convolution of words exists and this search terminates. The output is the required representative:The search uses only the finite transition table; it does not presuppose a solution to the word problem for a group.

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.

A run of a word is a maximal consecutive block of equal letters. For every $N\ge 1$, use the following finite coloring of $[3{]}^N$, with at most nine colors:We show that this run-count obstruction to interval-active lines excludes every monochromatic combinatorial line with an interval active set $[a,b]$. If $a=1$, its three words already have different first coordinates, so their colors differ. Suppose $a>1$ and denote the letter immediately to the left by $p$. All contributions to $R(w)$ away from the two possible boundaries of $[a,b]$ are independent of its active letter $x$; no internal active boundary contributes a change.

If $b=N$, the only variable contribution is $1_{\{p\ne x\}}$, which is $0$ at $x=p$ and $1$ at another letter. If $b<N$, write $q$ for the letter immediately to the right. The variable contribution isWhen $p=q$, its values are $0$ and $2$. When $p\ne q$, it equals $1$ at $x=p$ or $x=q$, and equals $2$ at the third letter. In every case these values are distinct modulo $3$. Hence no dimension works for alphabet size three and nine colors, which disproves the proposed universal strengthening. For the PDF's illustrative line, choosing either adjacent letter merges one active run with a neighboring run, while choosing any other letter merges neither; this is exactly the boundary effect measured above. Recording the first letter also handles active intervals meeting the beginning, including the entire coordinate set.

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.