The complexity of finite smooth words over binary alphabets

Julien Cassaigne Raphaël Henry · 2026

Read The complexity of finite smooth words over binary alphabets by Julien Cassaigne Raphaël Henry (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10733.txt.

Introduction

Julien Cassaigne and Raphaël Henry study smooth words over binary alphabets, the finite pieces of smooth sequences such as the Oldenburger-Kolakoski sequence. Their first result identifies the smooth words completely: they are exactly the factors of smooth sequences. Toward a conjectured growth rate for their complexity, they prove a lower bound valid over any alphabet and an upper bound over even alphabets. They also improve the known upper bound for odd and mixed alphabets, and link language, morphicity, and factor complexity in a dichotomy.

Catalog record

CREATORJulien Cassaigne Raphaël Henry
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72095
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10733

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The complexity of finite smooth words over binary alphabets Julien Cassaigne Raphaël Henry Abstract Smooth words over an alphabet of non-negative integers { a , b } \{a,b\} are infinite words that are infinitely derivable, the most famous example being the Oldenburger-Kolakoski word over { 1 , 2 } \{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 } \{a,b\} grows like Θ ⁡ ( n log ⁡ ( a + b ) / log ⁡ ( ( a + b ) / 2 ) ) \Theta\left(n^{\log(a+b)/\log((a+b)/2)}\right) : 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. Introduction The Oldenburger-Kolakoski word is very famous in combinatorics on words, it is a fixed point of the run-length encoding over the alphabet \{1,2\} : \begin{gathered}\hbox to336.5pt{\vbox to20.18pt{\pgfpicture\makeatletter\hbox{\hskip-0.2pt\lower 0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{}}{} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.533pt}{10.04411pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{62}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{}}{} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{303.70969pt}{5.16049pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{62}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\end{gathered} Initially studied by Oldenburger [ 18 ] , it was later popularized by Kolakoski [ 16 ] and is now registered as A000002 in the OEIS. Early on, the community of combinatorics on words asked the following questions: Does \kappa belong to a known class of words? Is it eventually periodic? (uniformly) recurrent? Does it have factor frequencies? What is its factor complexity? Kolakoski’s original question had already been answered in [ 18 ] : \kappa is not eventually periodic. However, since the foundational work of Dekking in [ 6 ] and [ 7 ] , the other questions remain unsolved. One of the main challenges is to describe the factors of \kappa . To do so, Dekking introduced in [ 6 ] finite smooth words , or f-smooth words in short, that is, a set of finite words over \{1,2\} closed under an operation called derivation that simulates locally the run-length encoding. We write \mathcal{C}_{f}^{\infty} the set of f-smooth words, they were originally called C^{\infty} -words but we change the name to align with the rest of the vocabulary of this paper. It easily follows that all factors of \kappa are f-smooth words, and Dekking conjectured the converse. With this in mind, the properties of f-smooth words have been thoroughly investigated. Notably, Carpi showed in [ 4 ] that f-smooth words are cube-free. Also, Dekking conjectured in [ 6 ] that the complexity of f-smooth words grows like \Theta\left(n^{\log(3)/\log(3/2)}\right) and was able to show that it is bounded by two polynomials. Weakley was the first to study the bispecial f-smooth words, in [ 22 ] he described how they can be used to prove the conjecture on the complexity and in [ 10 ] he and Huang obtained other polynomial bounds of the complexity by using letter frequencies. Facing the difficulties raised by \kappa , researchers started to investigate its variations in the hope of finding better answers. The first idea is to change the alphabet: if a and b are two different integers, let \kappa_{a,b} denote the fixed point of the run-length encoding starting with a over the binary alphabet \{a,b\} . The Oldenburger-Kolakoski word is then denoted by \kappa_{2,1} and we easily observe that \kappa_{1,2}=1\kappa_{2,1} , so the next word to bring attention is \begin{gathered}\hbox to356.34pt{\vbox to21.6pt{\pgfpicture\makeatletter\hbox{\hskip-0.2pt\lower-1.22272pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{}}{} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{3.533pt}{10.04411pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{62}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{}}{} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{312.81435pt}{4.97137pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{62}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\end{gathered} Dekking had already noticed in [ 6 ] that \kappa_{3,1} is morphic, and in [ 1 ] the authors extensively studied its properties. In particular it is linearly recurrent, it has linear complexity and it has algebraic letter frequencies that are different from 1/2 (the frequency of the letter 3 is approximately 0.6028). Interestingly, \kappa_{3,1} is not the only word with these properties: in the overview [ 21 ] , Sing showed that all words \kappa_{a,b} are generated by a primitive substitution when a+b is even. In our paper we shall consider a family of infinite words originally introduced over \{1,2\} by Dekking in Section 4 of [ 8 ] , which contains the words \kappa_{a,b} and continues to borrow its vocabulary from derivable functions. Over any binary alphabet \mathpzc{A} , if the run-length encoding is derivation , then a word in \mathpzc{A}^{\mathbb{N}} is smooth if all its derivatives are in \mathpzc{A}^{\mathbb{N}} . We write \mathcal{C}^{\infty} the set of infinite smooth words, and we define f-smooth words and their set \mathcal{C}_{f}^{\infty} over any binary alphabet as we did over \{1,2\} . We then observe a dichotomy between smooth words: • Over alphabets \mathpzc{A}=\{a,b\} where a+b is odd, it seems that every smooth word contains all f-smooth words. In particular, they all have the same factor complexity as \mathcal{C}_{f}^{\infty} . • Over alphabets \mathpzc{A}=\{a,b\} where a+b is even, it seems that every smooth word has linear factor complexity and does not contain all f-smooth words. However, f-smooth words are still very relevant in the second case of the dichotomy because the factors of smooth words are always f-smooth. Therefore the attempt to describe smooth words by studying f-smooth words naturally developed, and researchers started to generalize the properties of f-smooth words from \{1,2\} to every binary alphabet. For instance Huang extensively studied repetitions in \mathcal{C}_{f}^{\infty} , but for the purpose of this paper let us simply cite his unpublished work [ 12 ] where he generalized [ 4 ] by showing that f-smooth words are (b+1) -th-power-free over any alphabet \{a,b\} where a<b , except over \{1,3\} where they are 5 -th-power-free. Regarding their complexity, Sing generalized in [ 21 ] the conjecture of Dekking by stating that {p_{\mathcal{C}_{f}^{\infty}}(n)=\Theta\left(n^{\log(a+b)/\log((a+b)/2)}\right)} over any alphabet \{a,b\} . In this direction, Sing generalized Dekking’s result in [ 20 ] by giving polynomial bounds of the complexity over any alphabet. Also, Huang claimed in [ 11 ] to generalize the results of [ 10 ] to any alphabet, but we found a mistake in these results that we explain in the preliminaries of this paper. In this paper we contribute to the study of f-smooth. • In Theorem 1.5 we show that, over any binary alphabet, the f-smooth words are exactly the factors of smooth words. This yields the equality of complexities {p_{\mathcal{C}^{\infty}}(n)=p_{\mathcal{C}_{f}^{\infty}}(n)} and further motivates the study of \mathcal{C}_{f}^{\infty} . • In Theorem 1.6 we prove the conjectured lower bound of p_{\mathcal{C}_{f}^{\infty}}(n) over any alphabet and the conjectured upper bound over even alphabets (i.e., a and b are even). • In Theorem 1.7 we give a new upper bound of p_{\mathcal{C}_{f}^{\infty}}(n) over odd alphabets (i.e., a and b are odd). Lastly, let us discuss two blind spots this paper has on the topic of smooth words. The first one is that, with the previous dichotomy, the approach we take does not say anything about the factor complexity of individual smooth words over alphabets where a+b

Read the complete text