Combinatorics on words

A main contributor to the development of combinatorics on words was Axel Thue (1863–1922); he researched repetition. Thue's main contribution was the proof of the existence of infinite square-free words. Square-free words do not have adjacent repeated factors.[1] To clarify, "dining" is not square-free since "in" is repeated consecutively, while "baggage" is square-free, its two "ag" factors not being adjacent. Thue proves his conjecture on the existence of infinite square-free words by using substitutions. A substitution is a way to take a symbol and replace it with a word. He uses this technique to describe his other contribution, the Thue–Morse sequence, or Thue–Morse word.[1]

Thue wrote two papers on square-free words, the second of which was on the Thue–Morse word. Marston Morse is included in the name because he discovered the same result as Thue did, yet they worked independently. Thue also proved the existence of an overlap-free word. An overlap-free word is when, for two symbols x and y, the pattern xyxyx does not exist within the word. He continues in his second paper to prove a relationship between infinite overlap-free words and square-free words. He takes overlap-free words that are created using two different letters, and demonstrates how they can be transformed into square-free words of three letters using substitution.[1]

As was previously described, words are studied by examining the sequences made by the symbols. Patterns are found, and they are able to be described mathematically. Patterns can be either avoidable patterns, or unavoidable. A significant contributor to the work of unavoidable patterns, or regularities, was Frank Ramsey in 1930. His important theorem states that for integers k, m≥2, there exists a least positive integer R(k,m) such that despite how a complete graph is colored with two colors, there will always exist a solid color subgraph of each color.[1]

Other contributors to the study of unavoidable patterns include van der Waerden. His theorem states that if the positive integers are partitioned into k classes, then there exists a class c such that c contains an arithmetic progression of some unknown length. An arithmetic progression is a sequence of numbers in which the difference between adjacent numbers remains constant.[1]

When examining unavoidable patterns sesquipowers are also studied. For some patterns x,y,z, a sesquipower is of the form x, xyx, xyxzxyx, .... This is another pattern such as square-free, or unavoidable patterns. Coudrain and Schützenberger mainly studied these sesquipowers for group theory applications. In addition, Zimin proved that sesquipowers are all unavoidable. Whether the entire pattern shows up, or only some piece of the sesquipower shows up repetitively, it is not possible to avoid it.[1]

Necklaces are constructed from words of circular sequences. They are most frequently used in music and astronomy. Flye Sainte-Marie in 1894 proved there are 2²ⁿ⁻¹⁻ⁿ binary de Bruijn necklaces of length 2ⁿ. A de Bruijn necklace contains factors made of words of length n over a certain number of letters. The words appear only once in the necklace.[1]

In 1874, Baudot developed the code that would eventually take the place of Morse code by applying the theory of binary de Bruijn necklaces. The problem continued from Sainte-Marie to Martin in 1934, who began looking at algorithms to make words of the de Bruijn structure. It was then worked on by Posthumus in 1943.[1]

Sturmian words, created by François Sturm, have roots in combinatorics on words. There exist several equivalent definitions of Sturmian words. For example, an infinite word is Sturmian if and only if it has n+1 distinct factors of length n, for every non-negative integer n.[1]

A Lyndon word is a word over a given alphabet that is written in its simplest and most ordered form out of its respective conjugacy class. Lyndon words are important because for any given Lyndon word x, there exists Lyndon words y and z, with y<z, x=yz. Further, there exists a theorem by Chen, Fox, and Lyndon, that states any word has a unique factorization of Lyndon words, where the factorization words are non-increasing. Due to this property, Lyndon words are used to study algebra, specifically group theory. They form the basis for the idea of commutators.[1]

One problem considered in the study of combinatorics on words in group theory is the following: for two elements x,y of a semigroup, does x=y modulo the defining relations of x and y. Post and Markov studied this problem and determined it undecidable. Undecidable means the theory cannot be proved.[1]

The Burnside question was proved using the existence of an infinite cube-free word. This question asks if a group is finite if the group has a definite number of generators and meets the criteria xⁿ=1, for x in the group.[1]

Many word problems are undecidable based on the Post correspondence problem. Any two homomorphisms ${\displaystyle g,h}$ with a common domain and a common codomain form an instance of the Post correspondence problem, which asks whether there exists a word ${\displaystyle w}$ in the domain such that ${\displaystyle g(w)=h(w)}$. Post proved that this problem is undecidable; consequently, any word problem that can be reduced to this basic problem is likewise undecidable.[1]