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[edit]

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[edit]

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[edit]

* 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