Ten Squares Force an Overlap

Jeffrey Shallit · 2026

Read Ten Squares Force an Overlap by Jeffrey Shallit (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28570.txt.

Introduction

Jeffrey Shallit proves that every concatenation of ten or more binary squares contains an overlap. A square here is a word formed by repeating a block twice, and an overlap is a tight repetition pattern that such concatenations cannot avoid once they reach ten squares. The bound ten is best possible, meaning shorter concatenations can escape overlaps. Over a three-letter alphabet, by contrast, infinitely long overlap-free words built from squares exist, so the binary result does not extend to ternary alphabets.

Catalog record

CREATORJeffrey Shallit
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15011
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.28570

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ten Squares Force an Overlap Jeffrey Shallit Abstract We prove that every concatenation of 10 10 or more binary squares contains an overlap. The bound 10 10 is best possible. In contrast, over a ternary alphabet, there are infinitely long overlap-free words that consist of a concatenation of squares. 1 Introduction We say that a word w is a square if w=xx for some nonempty word x , and is an overlap if w=axaxa for some (possibly empty) word x and a single letter a . For example, murmur is a square, and alfalfa is an overlap. Suppose w=xyz for some words x,y,z . We call x a prefix of w , y a factor of w , and z a suffix of w . For example, for w={\tt concatenation} , the word con is a prefix, ten is a factor, and nation is a suffix. We call a word squarefree if it has no square factor, and overlap-free if it has no factor that is an overlap. In this paper we are mostly concerned with finite words over the alphabet \{0,1\} . We define \overline{0}=1 and \overline{1}=0 , and extend the notation for complement to words in the obvious way. The theory of overlap-free binary words was developed initially by Axel Thue [ 10 , 3 ] . Here an important role is played by the Thue-Morse morphism \mu , defined by \mu(0)=01 and \mu(1)=10 . We call 01 and 10 the \mu -blocks . We also write \mu^{i} for the i -fold iteration of \mu . In particular, a fundamental result in the area is the factorization theorem of Restivo and Salemi [ 7 , 8 ] , which states that every sufficiently long finite overlap-free binary word w can be written in the form x\mu(y)z , where y is overlap-free, and x,z are words of length at most two. In this paper we prove the following result. Theorem 1 . Every concatenation of 10 or more binary squares contains a factor that is an overlap, and the bound 10 is optimal. The rough idea of the proof is as follows: we assume, to get a contradiction, there is a shortest concatenation of 10 squares w that is overlap-free. If the squares in w are aligned with the \mu -blocks of the Restivo-Salemi factorization, then we can use that factorization to construct a shorter overlap-free concatenation of 10 squares. If the squares are not aligned with the \mu -blocks, their structure is constrained, and we can simply use breadth-first search to show that 9 squares is the maximum possible. All words in this paper are indexed starting at position 0 . 2 Useful lemmas In this section we state some of the basic results needed for the proof. Lemma 2 . Let x,y\in\{0,1\}^{*} and a\in\{0,1\} . (a) x is overlap-free if and only if \mu(x) is overlap-free. (b) If a\,x contains an overlap, so does \overline{a}\,\mu(x) . (c) If xa contains an overlap, so does \mu(x)a . (d) If x^{2}=\mu(y) then x=\mu(t) for some word t and y=tt . Proof. (a) See [ 10 , Satz 6] or [ 1 , Lemma 1.7.4] . (b) Suppose a\,x contains an overlap. Then either the overlap is entirely within x , or yaya is a prefix of x for some y . In the former case, \mu(x) contains an overlap by (a), and hence so does \overline{a}\mu(x) . In the latter case, \overline{a}\,\mu(x)=\overline{a}\mu(yaya)=\overline{a}\mu(y)a\overline{a}\mu(y)a\overline{a} , which clearly contains the overlap \overline{a}z\overline{a}z\overline{a} with z=\mu(y)a . (c) Analogous to (b). (d) See, for example, [ 1 , Lemma 1.7.3] ∎ Lemma 3 (Restivo-Salemi factorization) . Let w\in\{0,1\}^{*} be an overlap-free finite word. Then there exist u,v\in\{\epsilon,0,1,00,11\} and an overlap-free word y such that w=u\mu(y)v . If |w|\geq 7 the factorization is unique. Proof. The theorem is essentially in [ 7 , 8 ] . The version we use here can essentially be found in [ 6 ] or [ 1 , Prop. 1.7.5] . ∎ Lemma 4 . Let {\cal A}=\{0^{2},1^{2},(010)^{2},(101)^{2}\} . Then a word w\in\{0,1\}^{*} is an overlap-free square if and only if w is a conjugate of \mu^{i}(x) for x\in\cal A and i\geq 0 . In particular, an overlap-free square has length either 2^{i} or 3\cdot 2^{i} for i\geq 1 . Proof. See Thue [ 10 ] or Shelton and Soni [ 9 ] . ∎ Lemma 5 . Suppose x,y\in\{0,1\}^{+} and y is overlap-free. If ax^{2}b=\mu(y) , then x\in\{0,1,010,101\} . Proof. If x is of even length, say |x|=2m>0 , then |\mu(y)|=4m+2 and so |y|=2m+1 . Write y=c_{0}\cdots c_{2m} ; then \mu(y)=c_{0}\overline{c_{0}}\cdots c_{2m}\overline{c_{2m}} . Thus x=\overline{c_{0}}c_{1}\cdots c_{m-1}\overline{c_{m-1}}c_{m}=\overline{c_{m}}c_{m+1}\cdots\overline{c_{2m-1}}c_{2m}. It follows that \overline{c_{i}}=\overline{c_{m+i}} for 0\leq i\leq m-1 and c_{i}=c_{m+i} for 1\leq i\leq m ; hence c_{i}=c_{m+i} for 0\leq i\leq m . Thus y=c_{0}\cdots c_{m-1}c_{0}\cdots c_{m-1}c_{0} , an overlap, which is a contradiction. Hence x is of odd length. Since y is overlap-free, by Lemma 2 (a), so is \mu(y)=ax^{2}b , and hence so is x^{2} . By Lemma 4 , the only possibilities for x are x\in\{0,1,001,010,011,100,101,110\} . Of these the only ones for which \mu(y)=ax^{2}b has a solution are \{0,1,010,101\} . ∎ We define two functions on binary words. We define L(w) to be 1 if there exists a\in\{0,1\} such that aw is overlap-free, and 0 otherwise. Similarly, we define R(w) to be 1 if there exists a\in\{0,1\} such that wa is overlap-free, and 0 otherwise. Thus L measures whether an overlap-free word can be extended one symbol to the left to get a longer overlap-free word, and R measures the same thing for extension to the right. Lemma 6 . Let w\in\{0,1\}^{*} be overlap-free with |w|\geq 16 . Let its Restivo-Salemi factorization be w=u\mu(y)v , with y overlap-free, and u,v\in\{\epsilon,0,1,00,11\} . (i) If u=aa for some a\in\{0,1\} , then L(w)=0 . (ii) If v=aa for some a\in\{0,1\} , then R(w)=0 . Proof. We prove only (i), as (ii) follows with a symmetric argument. Since |w|\geq 16 and |v|\leq 2 , it follows that |y|\geq 6 . Checking all eight 3 -symbol prefixes of y , we easily confirm that aa\mu(y) being overlap-free implies that y begins with \overline{a}a\overline{a} . Thus w begins with aa\mu(\overline{a}a\overline{a}) . If we prepend a , then the resulting word begins with the overlap aaa . If we prepend \overline{a} then the resulting word begins \overline{a}aa\overline{a}aa\overline{a} , which is an overlap. Hence no left extension is overlap-free, and L(w)=0 . ∎ Lemma 7 . Define A=0^{2},\quad B=1^{2},\quad C=(010)^{2},\quad D=(101)^{2}. Every concatenation of nine or more words chosen from {\cal A}=\{A,B,C,D\} contains an overlap. Furthermore, no product of 8 words is extendable to the left or to the right and still be overlap-free. Proof. We use breadth-first search in the tree of all finite words that are products of A,B,C,D , and discarding those that have an overlap. The results are depicted in Table 1 . n=1 \{A,B,C,D\} n=2 \{AB,AD,BA,BC,CB,DA\} n=3 \{ABA,ABC,ADA,BAB,BAD,BCB,CBA,CBC,DAB,DAD\} n=4 \{ABAB,ABAD,ABCB,ADAB,ADAD,BABA,BABC, BADA,BCBA,BCBC,CBAB,CBCB,DABA,DADA\} n=5 \{ABADA,ABCBA,ADABA,BABCB,BADAB,BCBAB,CBABC,DABAD\} n=6 \{ABADAB,ABCBAB,ADABAD,BABCBA,BADABA, BCBABC,CBABCB,DABADA\} n=7 \{ABADABA,ABCBABC,ADABADA,BABCBAB,BADABAD, BCBABCB,CBABCBA,DABADAB\} n=8 \{ABADABAD,ABCBABCB,ADABADAB,BABCBABC,BADABADA, BCBABCBA,CBABCBAB,DABADABA\} n=9 \emptyset Table 1: Overlap-free words that are formed from blocks A,B,C,D for lengths 1 through 9 . At length n=9 no words survive, which proves the first claim. For the second claim, we simply check the 8 possible words of

Read the complete text