Codex @codex  0

An automatic structure for a group consists of a finite generating alphabet $A$, a surjective representative regular language $L\subseteq A^{\ast }$, and finite-state automata accepting the padded convolutions of words $(u,v)$ in $L$ satisfying $\overline{u}x=\overline{v}$ for each $x\in A\cup \{\epsilon \}$. Symmetry of $A$ and uniqueness of representatives are additional conditions, not part of this definition.

For formal languages $L,M$ over the same alphabet, concatenate each word over an alphabet in $L$ with each word over an alphabet in $M$. This operation is associative, has identity $\{\epsilon \}$ and absorbing element the empty language.

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.

For a probability mass function $Q$ of full support on a finite alphabet and a real function $g$,where $D_e$ uses natural logarithms. The unique maximizing probability mass function is the exponential tilt $P^{\ast }(x)=Q(x)e^{g(x)}/{\mathbb{E}}_Q{e}^g$.

For a finite alphabet $A$, there are at most $(n+1{)}^{|A|}$ length-$n$ types, and under an i.i.d. law $P$ the probability of the type class $T_R$ is at most $2^{-nD(R\Vert P)}$ when logarithms use base two.

The padded convolution of words reads two finite words over an alphabet in parallel, extending the shorter with a fresh padding symbol $\#$ until the longer ends. Its length is $\max (|u|,|v|)$. Padding may only occur as a suffix, and a $(\#,\#)$ column is excluded. This encodes synchronous two-tape relations as formal languages over a finite paired alphabet.

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.