Premium
MONOCHROMATIC FACTORIZATIONS OF WORDS AND PERIODICITY
Author(s) -
Wojcik Caïus,
Zamboni Luca Q.
Publication year - 2018
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579317000377
Subject(s) - mathematics , monochromatic color , pure mathematics , arithmetic , optics , physics
In 2006 Brown asked the following question in the spirit of Ramsey theory: given a non‐periodic infinite word x = x 1 x 2 x 3 … with values in a set A , does there exist a finite colouring φ : A + → C relative to which x does not admit a φ ‐monochromatic factorization, i.e. a factorization of the form x = u 1 u 2 u 3 … with φ ( u i ) = φ ( uj )for all i , j ⩾ 1 ? Various partial results in support of an affirmative answer to this question have appeared in the literature in recent years. In particular it is known that the question admits an affirmative answer for all non‐uniformly recurrent words and for various classes of uniformly recurrent words including Sturmian words and fixed points of strongly recognizable primitive substitutions. In this paper we give a complete and optimal affirmative answer to this question by showing that if x = x 1 x 2 x 3 … is an infinite non‐periodic word with values in a set A , then there exists a 2‐colouring φ : A + → { 0 , 1 }such that for any factorization x = u 1 u 2 u 3 … we have φ ( u i ) ≠ φ ( uj )for some i ≠ j .