TUCS On the Density of Critical Factorizations

We investigate the density of critical positions, that is, the ratio between the number of critical positions and the number of all positions of a word, in infinite sequences of words of index one, that is, the period of which is longer than half of the length of the word. On one hand, we considered words with the lowest possible number of critical points, namely one, and show, as an example, that every Fibonacci word longer than five has exactly one critical factorization which provides a new way to prove two known facts about the periodicity of Fibonacci words. On the other hand, sequences of words with a high density of critical points are considered. We show how to construct an infinite sequence of words in four letters where every point in every word is critical. We construct an infinite sequence of words in three letters with densities of critical points approaching one, using square-free words, and an infinite sequence of words in two letters with densities of critical points approaching two, using Thue– Morse words. It is shown that these bounds are optimal. Furthermore, we give a short proof of the Critical Factorization Theorem and a theorem about the maximal distance between two critical points in a word. We state that only words in a binary alphabet can have just one critical factorization