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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s