On prefixal factorizations of words

Original · EN

We consider the class P₁ of all infinite words x∈ Aω over a finite alphabet A admitting a prefixal factorization, i.e., a factorization x= U₀ U₁U₂ where each Uᵢ is a non-empty prefix of x. With each x∈ P₁ one naturally associates a "derived" infinite word δ(x) which may or may not admit a prefixal factorization. We are interested in the class P∞ of all words x of P₁ such that δⁿ(x) ∈ P₁ for all n≥ 1. Our primary motivation for studying the class P∞ stems from its connection to a coloring problem on infinite words independently posed by T. Brown in BTC and by the second author in LQZ. More precisely, let P be the class of all words x∈ Aω such that for every finite coloring φ: A+ → C there exist c∈ C and a factorization x= V₀V₁V₂ with φ(Vᵢ)=c for each i≥ 0. In DPZ we conjectured that a word x∈ P if and only if x is purely periodic. In this paper we show that P P∞, so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of P∞. We establish several results on the class P∞. In particular, we show that a Sturmian word x belongs to P∞ if and only if x is nonsingular, i.e., no proper suffix of x is a standard Sturmian word.