Avoiding large squares in infinite binary words

Abstract: We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with |y| >= 4; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except 00, 11, and 0101; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.

Review text

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.

Recommendations

Cites work

Cited in

(31)

This page was built for publication: Avoiding large squares in infinite binary words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557912)