Square-free word

A word $x$ over an alphabet $A$, that is, an element of the free monoid $A^*$, is square-free if $x=uwwv$ implies that $w$ is the empty string. A square-free word is thus one that avoids the pattern $XX$.

Examples

Over a two-letter alphabet $\{a,b\}$ the only square-free words are the empty word and $a$, $b$, $ab$, $ba$, $aba$ and $bab$. However, there exist infinite square-free words in any alphabet with three or more symbols, as proved by Axel Thue.

One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet $\{0,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence.

An example found by John Leech is defined recursively over the alphabet $\{a,b,c\}$. Let $w_1$ be any word starting with the letter $a$. Define the words $\{w_i \mid i \in \mathbb{N} \}$ recursively as follows: the word $w_{i+1}$ is obtained from $w_i$ by replacing each $a$ in $w_i$ with $abcbacbcabcba$, each $b$ with $bcacbacabcacb$, and each $c$ with $cabacbabcabac$. The sequence $(w_i)$ converges to the infinite square-free word $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb \ldots$$

Related concepts

A cube-free word is one with no occurrence of $www$ for a factor $w$. The Thue–Morse sequence is an example of a cube-free word over a binary alphabet. This sequence is not square-free but is "almost" so: the critical exponent is 2. The Thue–Morse sequence has no overlap or overlapping square, instances of $0X0X0$ or $1X1X1$: it is essentially the only infinite binary word with this property.

An abelian $p$-th power is a subsequence of the form $w_1 \cdots w_p$ where each $w_i$ is a permutation of $w_1$. There is no abelian-square-free infinite word over an alphabet of size three: indeed, every word of length eight over such an alphabet contains an abelian square. There is an infinite abelian-square-free word over an alphabet of size five.

References

• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words" CRM Monograph Series 27 American Mathematical Society (2009) ISBN 978-0-8218-4480-9 Zbl 1161.68043
• Blanchet-Sadri, Francine; Simmons, Sean, Avoiding Abelian Powers in Partial Words pp. 70-81 in Mauri, Giancarlo; Leporati , Alberto (edd.) "Developments in Language Theory. Proceedings, 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011" Lecture Notes in Computer Science 6795 (2011), , Springer-Verlag (2011) ISBN 978-3-642-22320-4 DOI 10.1007/978-3-642-22321-1_7
• Krieger, Dalia, On critical exponents in fixed points of non-erasing morphisms pp.280-291 in Oscar H. Ibarra; Zhe Dang (edd.) "Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006", Lecture Notes in Computer Science 4036 Springer (2006) ISBN 3-540-35428-X Zbl 1227.68074
• Leech, John; A problem on strings of beads, Math. Gazette 41 (1957) pp.277–278 Zbl 0079.01101
• Lothaire, M.; "Combinatorics on words", Cambridge University Press (1997), ISBN 0-521-59924-5
• Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications 90 Cambridge University Press (2011) ISBN 978-0-521-18071-9 Zbl 1221.68183
• Pytheas Fogg, N.; Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics 1794Springer-Verlag (2002) ISBN 3-540-44141-7 Zbl 1014.11015
• Thue, A. Über unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1–22
• Thue, A. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1–67