On prefixal factorizations of words

International audienceWe consider the class P 1 of all infinite words x ∈ A ω over a finite alphabet A admitting a prefixal factorization, i.e., a factorization x = U 0 U 1 U 2 · · · where each U i is a non-empty prefix of x. With each x ∈ P 1 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 1 such that δ n (x) ∈ P 1 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 and by the second author. 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 0 V 1 V 2 · · · with ϕ(V i) = c for each i ≥ 0. In a recent paper (A coloring problem for infinite words, J. Combin. Theory (Ser. A) 125 (2014) 306–332), we conjectured that a word x ∈ P if and only if x is purely periodic. In this paper we prove that P P ∞ , so in other words, potential candidates to a counterexample to our conjecture are amongst the non-periodic elements of P ∞. We establish several results on the class P ∞. In particular, we prove 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