ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5, 40 Cassaigne, Julien, Institut de Mathématiques de Luminy, Marseille, France On the conjectured subword complexity of the Kolakoski sequence 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. Dekking conjectured in 1981 that its subword complexity function p_{K}(n) was equivalent to Cn^{ρ} with ρ = log 3/ log(3/2). We prove, under the hypothesis that the set of subwords of K is invariant under the exchange of 1 and 2, that p(n) ≥ Cn^{ρ}, and, under the additional hypothesis that 1 and 2 occur with the same frequency (which is a famous open problem), that p(n) = O(n^{ρ+ϵ}) for any positive ϵ.