4 - Repetitions in words

Summary

Introduction

The topic of this chapter is the study of avoidable repetitions in words (finite or infinite sequences). The study of regularities in mathematical structures is a basic one in mathematics. The area of Ramsey theory is devoted to the study of unavoidable regularities in mathematical structures. Here we are principally concerned with the study of certain kinds of avoidable regularities in words. In particular, we are interested in the question, ‘What kinds of repetitions can be avoided by infinite words?’ The first work relating to this question dates back at least to the beginning of the twentieth century and the work of Thue (1906a, 1912) on repetitions in words. Thue's results were independently rediscovered from time to time in the first half of the twentieth century; however, a systematic study of what is now known as combinatorics on words was not initiated until perhaps the late 1970s or early 1980s.

The study of repetitions in words has as its principal motivation nothing other than its inherent mathematical appeal (indeed, this was Thue's reason for studying it). Nevertheless, the study of repetitions in words has several applications, the most famous of which is perhaps the work of Novikov and Adian (1968) in solving the Burnside problem for groups. Other applications have been found in cryptography and bioinformatics, such as discussed in Section 5.6 and also in Section 6.2.4. Recently, combinatorial results regarding repetitions in words have been used to prove deep results in transcendental number theory. A survey of these recent developments has been given by Adamczewski and Bugeaud (2010). Note that repetitions are also the main object of study of the next chapter (Chapter 5) where detection algorithms are also provided.

Avoidability

The notions of alphabet, letter, finite or infinite word, factor, prefix, suffix and morphism have been defined in Section 1.2.We recall in particular that the Thue–Morse morphism μ : {0,1}^∗→{0,1}^∗ is defined by

Frequently we shall deduce the existence of an infinite word with a certain property from the existence of arbitrarily large finite words with the desired property. To pass from the finite to the infinite, we shall often rely (implicitly) on the following form of König's infinity lemma.