Avoiding large squares in infinite binary words (Q557912)

A square is a nonempty word of the form \(xx\); a cube is of the form \(xxx\). Every binary sequence is known to contain a square, but there exist explicit examples of sequences with no \(xx\) such that the length of \(x\) satisfies \(| x| \geq 3\). There exist also examples with no cube \(xxx\) and no square \(yy\) such that \(| y| \geq 4\). Other sequences are proved to contain no square except \(0^2\), \(1^2\) and \((01)^2\). The authors give new proofs of these results by exhibiting constant length iterated morphisms. Using such morphisms allows them to prove that the number of finite binary words of length \(n\) with such avoidance properties is bounded by \(1,002^n\) and \(1,178^n\). Finally, the authors exhibit an example of two infinite words \((a_i)_i\), \((b_i)_i\) avoiding squares \(ww\) with \(| w| \geq 4\) and such that the sequence \(a_1b_1a_2b_2 \dots\) has unbounded large squares. The method consists in exhibiting a constant length substitution on four letters whose fixed point avoids a given set of finite words. Combinatorial properties based on the set of forbidden subwords imply that the morphism maps square free finite words to square free words. An explicit infinite binary sequence with the expected properties is obtained as a projection on a two-letters alphabet of the fixed point of the four-letters iterated morphism.