## Combinatorics on Words

I am recording here some neat proofs of some theorems on combinatorics on words. No great originality is claimed. $A^{\ast}$ denotes the free monoid on $A$ and $A^{\omega}$ denotes the space of right infinite words. If $L\subseteq A^*$, then $L^{\omega}$ denotes the set of all infinite concatenations of elements of $L$.

Lemma 1. If $u\in A^{\omega}$ is periodic with periods $p,q$, then $\gcd(p,q)$ is a period of $u.$

Proof. Let $T\colon A^{\omega}\to A^{\omega}$ be the shift operator. Then $T$ acts as a cyclic permutation of the orbit of $u$ and $T^p(u)=u=T^q(u).$ The result follows from basic group theory.

Theorem 1. Suppose that $u,v\in A^*$ are commuting words, i.e., $uv=vu.$ Then $u,v$ are powers of a common word.

Proof. This is a variation of a proof in Mark Sapir’s book, which he attributes to Victor Guba. Consider the infinite word $w=uvuv\cdots = vuvu\cdots$. Then $w$ is periodic and both $|u|,|v|$ are periods of $w$. Therefore $d=\gcd( |u|,|v|)$ is a period of $w$. Thus if $t$ is the prefix of $w$ of length $d$, then $u,v$ are powers of $t$.

Theorem 1 is a consequence of the more general fact that two words which are not powers of a common word freely generated a free submonoid of $A^*.$ We prove this via Jeffery Shallit’s version of the Fine and Wilf theorem.

Theorem 2 (Shallit’s Fine and Wilf). Let $u,v\in A^*$ and suppose there exist infinite words $x\in u\{u,v\}^{\omega}$ and $y\in v\{u,v\}^{\omega}$ such that initial segments of $x,y$ of length $|u|+|v|-\gcd(|u|,|v|)$ coincide. Then:

1. $x=y.$
2. $u,v$ are powers of some word $t.$

Proof. The proof is by induction on $|u|+|v|$. The base case is when one of the words is empty, which is trivial. Assume without loss of generality that $|u|\leq |v|$. Then since $x,y$ have the same prefix of length $|v|$, we deduce $v=uv'$ for some $v'\in A^*.$ Note that $\gcd(|u|,|v|) = \gcd(|u|,|v'|)$ because $|v|=|u|+|v'|$. Also note that $\{u,v\}^\omega\subseteq \{u,v'\}^{\omega}$. Let $x',y'$ be the words obtained from $x,y$ respectively by removing the common initial segment $u$. Then $x'\in u\{u,v'\}^{\omega}$ and $y'\in v'\{u,v'\}^{\omega}$ are such that the initial segments of $x',y'$ of length $|u|+|v'|-\gcd(|u|,|v'|)$ coincide. By induction, we obtain $x'=y'$ and hence $x=y$, and also $u,v'$ are powers of some word $t.$ But then $v=uv'$ is also a power of $t.$ This completes the proof.

I would love to see a proof of this theorem along the lines of the proof of Theorem 1 that avoids induction.

Corollary 1 (Fine and Wilf ). If $x,y\in A^{\omega}$ are infinite periodic words with periods $p$ and $q$, respectively, and if the initial segments of $x,y$ of length $p+q-\gcd(p,q)$ coincide, then $x=y$ and $\gcd(p,q)$ is a period of $x=y$.

Proof. Apply Theorem 2 with $u,v$ as the initial segments of $x,y$ of lengths $p,q$ respectively.

The original proof is an elegant application of generating functions.

Corollary 2. Let $u,v\in A^*$. Then the following are equivalent.

1. $u,v$ commute.
2. $u,v$ are powers of some word $t$.
3. $u,v$ do not freely generate a free submonoid of $A^*$.

Proof. Clearly 2 implies 1 implies 3. Suppose 3 occurs. Then we can find distinct words $w_1(a,b),w_2(a,b)$ in $\{a,b\}^*$ such that $w_1(u,v)=w_2(u,v)$. Since $A^*$ is cancellative, we may assume that $w_1$ begins with $a$ and $w_2$ begins with $b$. Now apply Theorem 2 to the infinite words $x=w_1(u,v)^{\omega}\in u\{u,v\}^{\omega}$ and $y=w_2(u,v)^{\omega}\in v\{u,v\}^{\omega}$ and use that $x=y$. ## About Benjamin Steinberg

Mathematician interested in semigroups, groups and automata.
This entry was posted in Math, Uncategorized and tagged . Bookmark the permalink.