The complexity of smooth words over binary alphabets

2026/03/11 by Julien Cassaigne, Raphaël Henry · 1 voice · 1 citation
Computer Science · Mathematics · #cs.FL #math.CO #math.DS

paper · pdf

arxiv published 2026/03/11 · arxiv updated 2026/06/16

Abstract

Smooth words over an alphabet of non-negative integers \a,b\ are infinite words that are infinitely derivable, the emblematic example being the Oldenburger-Kolakoski word over \1,2\. The main way to study their language is to consider a finite version of smooth words that we call f-smooth words. In this paper we prove that the f-smooth words are exactly the factors of smooth words, and we make progress towards the conjecture of Sing that the complexity of f-smooth words over \a,b\ grows like Θ(n^{log(a+b)/log((a+b)/2)}): we prove it over even alphabets, we prove the lower bound over any binary alphabet and we improve the known upper bound over odd alphabets.

Citations

• Frequencies of Patterns in Smooth Sequences Over the Alphabet \1,3\
• More Kolakoski Sequences
• The powers of smooth words over arbitrary 2-letter alphabets
• Kolakoski-(3,1) is a (deformed) model set

Cited by

• Frequencies of Patterns in Smooth Sequences Over the Alphabet \1,3\

Discussions

• Julien Cassaigne, Rapha\"el Henry: The complexity of finite smooth words over binary alphabets https://arxiv.org/abs/2603.10733 https://arxiv.org/pdf/2603.10733 https://arxiv.org/html/2603.10733 [bsky, 0 points, 0 comments]

Related

• Smooth words and Chebyshev polynomials
• On additive complexity of infinite words
• Smooth infinite words over n-letter alphabets having same remainder when divided by n
• Factor versus palindromic complexity of uniformly recurrent infinite words
• Frequencies of subwords in words of linear subword complexity