Cubefree binary words avoiding long squares

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Entringer, Jackson, and Schatz conjectured in 1974 that every infinite cubefree binary word contains arbitrarily long squares. In this paper we show this conjecture is false: there exist infinite cubefree binary words avoiding all squares xx with |x| >= 4, and the number 4 is best possible. However, the Entringer-Jackson-Schatz conjecture is true if "cubefree" is replaced with "overlap-free".
PLEASE NOTE: After this paper was prepared, we learned that all our results appeared (albeit with different proofs) in a paper of F. M. Dekking, On repetitions of blocks in binary sequences, J. Combin. Theory Ser. A 20 (1976), 292--299

Keywords

Combinatorics, Discrete Mathematics, 68R15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/66619

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0302303
 http://arxiv.org/abs/math/0302303

Collections

arXiv