Some properties of \(C^ \infty\)-words with applications (Q1357249)

The Kolakoski sequence is the sequence of 1's and 2's beginning with 1, such that the sequence of lengths of consecutive blocks of 1's and 2's is the initial sequence itself. This sequence begins with 122112122\dots [see \textit{W. Kolakoski}, Self generating runs, Problem 5304, Am. Math. Mon. 73, 681-682 (1966)]. Not much is known concerning this sequence [see \textit{F. M. Dekking}, Sémin. Théorie Nombres Bordeaux 1979-1980, Exposé, No. 9 (1980; Zbl 0438.10040), and Exposé 31 (1981; Zbl 0472.10054)]. Note two misprints in these references in the paper under review. Dekking proposed the notion of (finite) \(C^\infty\)-word: this is a word that can be differentiated an infinite number of times. The derivative of a word on \(\{1,2\}\) without any occurrence of 111 or 222 is the word whose \(j\)th symbol is the length of the \(j\)th run of 1's or 2's in this word (discarding the first and last run if their length is 1). For example \((122112)'=22\). Dekking noted that every finite subword of the Kolakoski sequence is \(C^\infty\). The authors study the minimal and maximal number of 2's in a \(C^\infty\) word of length \(n\) and obtain interesting estimations for these quantities. In particular, they give a partial answer to a question of J. Shallit.