I am recording here some neat proofs of some theorems on combinatorics on words. No great originality is claimed.
denotes the free monoid on and denotes the space of right infinite words. If , then denotes the set of all infinite concatenations of elements of .
Lemma 1. If is periodic with periods , then is a period of
Proof. Let be the shift operator. Then acts as a cyclic permutation of the orbit of and The result follows from basic group theory.
Theorem 1. Suppose that are commuting words, i.e., Then 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 . Then is periodic and both are periods of . Therefore is a period of . Thus if is the prefix of of length , then are powers of .
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 We prove this via Jeffery Shallit’s version of the Fine and Wilf theorem.
Theorem 2 (Shallit’s Fine and Wilf). Let and suppose there exist infinite words and such that initial segments of of length coincide. Then:
- are powers of some word
Proof. The proof is by induction on . The base case is when one of the words is empty, which is trivial. Assume without loss of generality that . Then since have the same prefix of length , we deduce for some Note that because . Also note that . Let be the words obtained from respectively by removing the common initial segment . Then and are such that the initial segments of of length coincide. By induction, we obtain and hence , and also are powers of some word But then is also a power of 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 are infinite periodic words with periods and , respectively, and if the initial segments of of length coincide, then and is a period of .
Proof. Apply Theorem 2 with as the initial segments of of lengths respectively.
The original proof is an elegant application of generating functions.
Corollary 2. Let . Then the following are equivalent.
- are powers of some word .
- do not freely generate a free submonoid of .
Proof. Clearly 2 implies 1 implies 3. Suppose 3 occurs. Then we can find distinct words in such that . Since is cancellative, we may assume that begins with and begins with . Now apply Theorem 2 to the infinite words and and use that .