Monochromatic factorizations of words and periodicity

DOI10.1112/S0025579317000377zbMATH Open1386.68123arXiv1608.03519OpenAlexW2963816020WikidataQ114077767 ScholiaQ114077767MaRDI QIDQ4604492FDOQ4604492

Authors: Caïus Wojcik, Luca Q. Zamboni 

Publication date: 26 February 2018

Published in: Mathematika (Search for Journal in Brave)

Abstract: In 2006 T. Brown asked the following question: Given a non-periodic infinite word $x=x_1{x}_2{x}_{3}cdots$ with values in a non-empty set $mathbbA,$ does there exist a finite coloring $varphi:mathbb{A}^{+}ightarrowC$ relative to which $x$ does not admit a $varphi$-monochromatic factorisation, i.e., a factorisation of the form $x=u_1{u}_2{u}_{3}cdots$ with $varphi(u_i)=varphi(u_j)$ for all $i,jgeq1$? 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 various classes of uniformly recurrent words including Sturmian words. In this note we answer this question in general by showing that if $x=x_1{x}_2{x}_{3}cdots$ is an infinite word with values in a non-empty set $mathbbA,$ then $x$ is periodic if and only if for every $2$-coloring $varphi:mathbb{A}^{+}ightarrow0,1$ there exists a $varphi$-monochromatic factorisation of $x.$ This characterization of periodicity of infinite words may be reformulated in the language of ultrafilters. Let $$ denote the Stone-Cech compactification of the discrete semigroup $mathbb{A}^{+}$ which we regard as the set of all ultrafilters on $mathbb{A}^{+}.$ Then $x$ is periodic if and only if there exists $$ such that for each $Ainp$ there exists a factorisation $x=u_1{u}_2{u}_{3}cdots$ with each $u_{i}inA.$

Full work available at URL: https://arxiv.org/abs/1608.03519

Recommendations

• Coloring problems for infinite words
• A coloring problem for infinite words
• A coloring problem for Sturmian and episturmian words
• A Ramsey characterisation of eventually periodic words
• On prefixal factorizations of words

Mathematics Subject Classification ID

Combinatorics on words (68R15) Ramsey theory (05D10)

Cites Work

• Algebra in the Stone-Čech compactification: theory and applications
• Substitutional dynamical systems, Bratteli diagrams and dimension groups
• Category theory of symbolic dynamics
• On prefixal factorizations of words
• A coloring problem for infinite words
• Coloring factors of substitutive infinite words
• On some variations of coloring problems of infinite words
• Partitions and sums of integers with repetition
• Pairwise sums in colourings of the reals

Cited In (10)

• A coloring problem for Sturmian and episturmian words
• Words, univalent factors, and boxes
• A Ramsey characterisation of eventually periodic words
• On some variations of coloring problems of infinite words
• Special factors, periodicity, and an application to Sturmian words
• On prefixal factorizations of words
• Coloring problems for infinite words
• A coloring problem for infinite words
• Positions of the ranks of factors in certain finite long length words
• Monochromatic arithmetic progressions in binary Thue-Morse-like words

This page was built for publication: Monochromatic factorizations of words and periodicity

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