View source for 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 [[Avoidable pattern|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 <math>w_1</math> be any word starting with the letter $a$.  Define the words <math> \{w_i \mid i \in \mathbb{N} \}</math> recursively as follows: the word <math>w_{i+1}</math> is obtained from <math>w_i</math> by replacing each $a$ in <math>w_i</math> 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 of a word|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 <math>w_1 \cdots w_p</math> where each <math>w_i</math> is a permutation of <math>w_1</math>.  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 '''1794'''Springer-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

{{TEX|done}}