The Kolakoski sequence and its conjectured subword complexity

The  Kolakoski sequence is the sequence K with values in  {1,2} such that K(n) is equal to the length of the nth run of equal symbols in K.  This is an intriguing sequence, for which apparently simple questions turn out to be very difficult problems. Dekking conjectured in 1981 that its subword complexity function p_K(n) was equivalent to Cn^p with p=log3/log(3/2). We prove, under the hypothesis that the set of subwords of K is invariant under the exchange of 1 and 2, the inequality p_K(n) >= Cn^p, and, under the additional hypothesis that 1 and 2 occur with the same frequency (which is a famous open problem), that p_K(n) =O(n ^p+e)  for any positive e.

Information:

Special factors of sequences with linear subword complexity

Sequences with low complexity, which means that p(n) does not grow too fast (e.g., it is bounded by a linear function), are certainly the sequences with the most interesting features, as this constraint on complexity induces certain regularities in the sequence, without however making it periodic.  Their properties have been extensively studied; among them is the famous class of Sturmian sequences for which the complexity is as low as possible for non-periodic sequences:
p(n)=n+1.

No characterization of the set of integer-valued functions that can arise as subword complexities of sequences is known; nevertheless it is clear that not all functions are obtainable this way.  For instance, complexity functions are necessarily monotonically increasing, and they can neither grow faster than kⁿ nor more slowly than n, except when they are stationary.  In this talk we establish a subtler restriction, which was conjectured by S. Ferenczi: if p(n) has linear growth (i.e., p(n) is bounded by some linear function), then its differences p(n+1)-p(n) are bounded.
The proof of this result uses a combination of two combinatorial representations of the set of factors of a sequence:  Rauzy graphs and special factor trees.  A crucial notion for this proof (and for many related problems) is that of right (and left)  special factors, i.e., factors that can be extended in more than one way to longer factors by adding one letter to the right (or left).
When the alphabet has only two letters, the number of right special factors is exactly the quantity p(n+1)-p(n) we are interested in.

Information: