The complexity of smooth words over binary alphabets

arXiv:2603.10733 · cs.FL, math.CO, math.DS · Submitted 2026-03-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "The complexity of smooth words over binary alphabets".

Jane: Here's the gist of the paper. Smooth words are exactly the factors of smooth sequences over any binary alphabet, and this paper proves that their complexity is governed by a specific growth rate related to alphabet properties.

Title and authors: Tom: So, Jane, this paper is titled "The complexity of smooth words over binary alphabets," and it really zeroes in on how complex these special sequences are.

Jane: It’s about these sequences that are infinitely derivable, like the Oldenburger-Kolakoski sequence κ over the alphabet of one and two. The authors are showing that their factors, which we call smooth words, cover exactly all the smooth words for any binary alphabet.

Lu: What this means is they’re tackling a big problem about how complicated these sequences get as you change the alphabet you're using. They are proving a lower bound for this complexity over any alphabet and an upper bound specifically for even alphabets.

Meng: Okay, so they’ve done some bounds, but what does that actually tell us about the practical limits of describing these words? Is this complexity growing really fast?

Lalam: The main thing they prove is that the factor complexity of smooth words over any binary alphabet has a growth rate related to the properties of that alphabet itself. They’re looking at how fast it grows with respect to something called n and the size of your alphabet.

Tom: It sounds like they are establishing a specific growth rate for this complexity, not just an upper bound somewhere. What's the actual formula they derive?

Jane: They prove that the complexity grows like Theta n log(a plus b) over log((a plus b) over two), where a and b are the letters in your alphabet. That’s a precise way of saying how fast it scales with the alphabet size.

Lu: And they tie this growth rate to whether you are dealing with an even or an odd alphabet, which is a key distinction in their work. They use Theorem one point four zero to check if the language complexity L of these smooth words equals C infinity or not <ref:2603.10733#pg3>.

Meng: So, knowing if it's equal to C infinity helps determine something about the sequence's recurrence type, which sounds like they can actually predict some structural behavior based on the alphabet they start with.

Lalam: Exactly, and this dichotomy links the language of smooth sequences directly to their morphicity and factor complexity. It allows them to make predictions about whether a sequence is morphic just by looking at its language properties.

Tom: That’s interesting because it connects these abstract mathematical properties—language, complexity, and morphicity—to the alphabet structure in a tangible way for the listener.

Title and authors: Jane: And they also offer improvements on how we estimate this complexity when we use mixed alphabets or odd alphabets, by using lower bounds from Theorem one point three one and upper bounds from Theorems one point three two and one point three five depending on the alphabet type you’re dealing with <ref:2603.10733#pg3>.

Lu: They even get pretty precise about the bounding for smooth words over even alphabets by using Lemma four point four, which states that for an even alphabet where a plus b is even, "the length of each word in Ti is psi (a plus b)/two i - psi for all i greater than or equal to zero <ref:2603.10733#pg2>."

Meng: That sounds like a very specific structural constraint on the words themselves, giving us a concrete way to bound the complexity rather than just relying on general estimates. How does that translate when we try to deploy models?

Lalam: When you're running this at scale, knowing that the length of these words is constrained by that formula gives you a very tight upper bound on the factor complexity for even alphabets. It’s a much stronger guarantee than just saying it grows like n log n.

Tom: And they also look at letter frequencies within these smooth words to derive upper bounds using results from Theorem one point three five, especially when the condition "u b u greater than one over two minus phi" is met <ref:2603.10733#pg3>. That suggests frequency analysis plays a role in tightening those bounds when certain conditions on the letters are present.

Jane: So, while they give us these powerful tools for bounding complexity, they also point out two blind spots where they don't go deep enough: first, studying the language C infinity only helps describe the expected language over mixed alphabets.

Lu: And second is that even though it appears in Theorem one point three five, they don't really tackle the important question of factor frequencies in smooth sequences, which relates back to the famous conjecture about equal letter frequencies for sequences like κ <ref:2603.10733#pg3,tackle the important question of factor frequencies in smooth sequences, which>.

Meng: So, if we're building an AI model to generate these things, knowing the frequency constraints is crucial for training efficiency and avoiding weird artifacts at scale. What do you think that means for real-world deployment?

Lalam: It means that just because you have a general bound doesn't mean your specific sequence will adhere to those frequency constraints, so you need to check those things separately. The work points toward needing more specific tools when dealing with mixed alphabets or odd alphabets.

Title and authors: Tom: So, we've seen they prove the main complexity growth rate over any alphabet and give us bounds depending on whether the alphabet is even or odd, and they show how language properties determine morphicity.

Jane: It’s a lot of machinery to connect these ideas—from the Oldenburger-Kolakoski sequence to general binary alphabets—but it gives us a solid framework for analyzing these smooth sequences.

Lu: Overall, the paper establishes a dichotomy that links the language, morphicity, and factor complexity of smooth words over binary alphabets by leveraging Theorem one point four zero and Conjecture one point one six. This is a significant result in understanding the structure of these sequences.

Meng: If this framework proves useful for predicting complexity based on alphabet structure, it could help us design better generative models that respect inherent structural limits rather than just chasing raw statistical complexity over huge datasets.

Lalam: It certainly gives us a way to predict behavior based on language properties, which is powerful when you don't have enough data to run exhaustive experiments.

Tom: So, to wrap up, we’ve seen that the complexity of smooth words over binary alphabets is governed by a specific growth rate related to alphabet properties, and this paper provides tools to determine if a sequence is morphic based on its language.

Jane: It's a deep dive into the structure of these sequences and how their underlying alphabet dictates their complexity growth. We’ve seen how they build on previous results about factor complexity bounds for even and odd alphabets, and they point out the missing pieces regarding factor frequencies in mixed alphabets.

Lu: The implications are that we have a clearer picture of the structural limits of smooth sequences than before, especially concerning their language properties.

Meng: From an engineering standpoint, it means we can set tighter complexity expectations for sequence generation based on the input alphabet structure, which is something you need when you're deploying things in production.

Lalam: The paper "The complexity of smooth words over binary alphabets" gives us a framework to analyze these sequences by linking language properties to their morphicity and factor complexity. We’ve seen how this helps us understand the growth rate based on even or odd alphabets, and we also learned about the limitations regarding factor frequencies in mixed alphabets.

Tom: That's the gist of it—a lot of hard math leading to a more structured understanding of how these words behave over different alphabets. It’s a solid piece for anyone interested in sequence complexity.

The paper's summary: Tom: So we've looked at how the complexity of smooth words over any binary alphabet is governed by the properties of that alphabet itself, and now we’re going to break down what this summary actually means for us.

Jane: It boils down to this paper proving that smooth words, which are basically infinitely derivable sequences, have a factor complexity growth rate tied directly to whether the alphabet is even or odd.

Tom: Right. They're using something called Theorem one point four zero to check if the language complexity L of these smooth words equals C infinity or not, and that’s how they deduce properties about the sequence's recurrence type based on which way it goes—even or odd alphabet.

Lu: What this tells us is that we can use that theorem to determine if a sequence is morphic just by looking at its language properties, which links directly into Conjecture one point one six and Theorem one point four zero.

Meng: So, if we see a certain language pattern in the smooth words, we can predict if the sequence is morphic before we even start training an AI model on it?

Lalam: Exactly. It establishes a dichotomy that links the language of these smooth sequences directly to their morphicity and factor complexity, which is powerful when you don't have a massive amount of data to run exhaustive experiments on.

Jane: And they’re not just giving us one answer for every alphabet; they’re actually providing tools to estimate the factor complexity for smooth words over even alphabets by using a lower bound from Theorem one point three one and several upper bounds from Theorems one point three two and one point three five, depending on whether we are dealing with an even, odd, or mixed alphabet type.

Tom: That’s important because it gives us different ways to bound the complexity depending on the input structure—even versus odd versus mixed—which is crucial when you're deploying models where you don't know your exact alphabet constraints beforehand.

Lu: They get pretty precise about bounding the factor complexity specifically for smooth words over even alphabets by applying Lemma four point four, which states that for an even alphabet, if a plus b is even, the length of each word in Ti is psi (a plus b) over two i minus psi for all i greater than or equal to zero.

Meng: That formula sounds like it gives us a concrete structural constraint on the words themselves that we can use to get a tighter upper bound on complexity when we're running things at scale.

Jane: It’s really about connecting these abstract language properties and growth rates to tangible structural limits, which is what makes this work feel relevant for sequence analysis.

Tom: And they also look at letter frequencies within these smooth words to derive upper bounds on factor complexity by utilizing the results from Theorem one point three five, specifically when the condition u b u over one over two minus phi is met.

Lalam: That suggests that analyzing how often certain letters appear in the sequence helps us tighten those complexity bounds when specific conditions on those letter frequencies are satisfied.

Jane: So, this paper gives us a very structured framework to analyze these sequences by linking language properties to their morphicity and factor complexity, and it shows exactly how the alphabet structure dictates the growth rate.

Tom: We've established that smooth words over any binary alphabet have a specific growth rate tied to those alphabet properties, and we’ve got tools now to check if a sequence is morphic based on its language.

Lu: The implications are that we have a clearer picture of the structural limits of smooth sequences than before, especially concerning their language properties.

Jane: That means we can start predicting behavior based on language structure rather than just chasing raw statistical complexity over huge datasets.

Tom: This is a solid piece for anyone interested in the underlying structure of these sequences and how their alphabet dictates their complexity growth. What we need to look at next is how these bounds translate into practical limits for sequence generation in production environments.

The paper's improvements: Tom: So we've looked at the core complexity growth rate over any alphabet, and now we’re going to talk about how they've improved on that original idea to make it more useful for real AI models.

Jane: The authors suggest a few big improvements to this work, mostly focused on making it easier to check if a sequence is morphic by analyzing that growth rate differently depending on whether the alphabet has an even or odd number of letters.

Lu: They propose using Theorem one point four zero to specifically check if the language complexity L equals C infinity or not, and then that lets them deduce properties about the recurrence type based on whether it’s over an even or odd alphabet.

Meng: So, instead of just looking at one growth rate, they suggest a way to use that growth rate analysis to actually determine the sequence's recurrence type more reliably.

Tom: Right. That sounds like a better diagnostic tool for figuring out the underlying structure of these sequences before you commit computational resources to generating them.

Jane: Then there’s an enhancement for estimating factor complexity when we're dealing with smooth words over any binary alphabet, using the lower bound from Theorem one point three one and several upper bounds from Theorems one point three two and one point three five, depending on whether it’s an even, odd, or mixed alphabet.

Lu: That gives us a more detailed toolkit for getting those complexity estimates depending on the exact nature of the alphabet you start with.

Meng: I need to know if this is just theoretical estimation or if these bounds are tight enough for me to actually deploy anything? What breaks at scale?

Jane: They also establish a dichotomy for smooth sequences over mixed alphabets by linking L equals C infinity to the morphicity of the sequence through Conjecture one point one six and Theorem one point four zero, which allows us to make predictions about whether a sequence is morphic based purely on its language properties.

Tom: That’s smart because it lets us predict behavior before we even try to run a full generation experiment on a mixed alphabet setup.

Lalam: And they get pretty precise about bounding the factor complexity of smooth words over even alphabets by applying Lemma four point four, which states that for an even alphabet where a plus b is even, the length of each word in Ti is psi (a plus b) over two i minus psi for all i greater than or equal to zero.

Jane: That specific lemma gives us a very tight bound on the word length itself when you have that kind of even alphabet structure.

Meng: If we can get a concrete formula for word length, that's valuable because it directly limits the size of the state space we need to manage in our generative models.

Tom: And they also incorporate sophisticated analysis of letter frequencies within smooth words to derive upper bounds on factor complexity by utilizing results from Theorem one point three five, specifically when the condition u b u over one over two minus phi is met.

Lu: So, frequency analysis isn't just there for show; it directly impacts how tightly we can bound complexity when those specific letter frequency conditions are present in the smooth words.

Jane: Overall, these improvements are about giving us a more nuanced way to assess the structural properties of these sequences using their language and alphabet characteristics.

Tom: So, we've moved past just finding a growth rate to having specific checks for morphicity and tighter bounds based on even, odd, or mixed alphabet structures.

Lu: This work is really pushing us toward understanding the structural limits of smooth sequences rather than just measuring their raw statistical complexity across massive data.

Jane: It’s about connecting the abstract language patterns directly to concrete structural limits in a way that helps us build better generative tools.

Meng: If these improved bounds mean we can set tighter complexity expectations for sequence generation based on the input alphabet structure, that's something you need when you're deploying things in production.

Tom: This is definitely moving the discussion from just "how complex is this thing?" to "what structural rules govern its complexity?"

Conclusion: Tom: So to wrap up, this paper on "The complexity of smooth words over binary alphabets" shows us how the complexity growth rate is fundamentally tied to whether you're working with an even or odd alphabet structure.

Jane: It’s really about giving us tools to check if a sequence is morphic based on its language properties, which means we can predict structural behavior before we commit resources.

Lu: The core idea here is establishing that dichotomy between language and morphicity using Theorem one point four zero and conjecture one point one six.

Meng: It’s interesting because it moves the complexity analysis away from just measuring raw growth over time to understanding the alphabet's inherent properties, which is something you need when you're trying to design efficient generative models.

Lalam: I’m confident in this direction; it gives us a solid framework for analyzing these sequences by linking language properties to their morphicity and factor complexity.

Tom: And they also provided specific tools for estimating that complexity based on the alphabet type, whether it’s even, odd, or mixed.

Jane: That means we have different ways to bound the factor complexity depending on the exact nature of the alphabet you start with.

Lu: They showed how to get a tighter bound for even alphabets using Lemma four point four and how letter frequencies affect those bounds under certain conditions.

Meng: If we can get a concrete formula for word length, that's valuable because it directly limits the size of the state space we need to manage in our generative models.

Tom: And they incorporated frequency analysis to show how important letter distribution is for complexity when those specific conditions are met.

Jane: So, this paper gives us a very structured framework to analyze these sequences by linking language properties to their morphicity and factor complexity.

Lu: This work is really pushing us toward understanding the structural limits of smooth sequences rather than just measuring their raw statistical complexity across massive data.

Meng: If we can get tighter bounds, it means we can set more realistic complexity expectations for sequence generation based on the input alphabet structure.

Tom: It’s about connecting the abstract language patterns directly to concrete structural limits in a way that helps us build better generative tools.

Jane: So, "The complexity of smooth words over binary alphabets" gives us a framework to analyze these sequences by linking language properties to their morphicity and factor complexity.

Lu: We’ve seen how this helps us understand the growth rate based on even or odd alphabets, and we also learned about the limitations regarding factor frequencies in mixed alphabets.

Meng: That means we need to be careful; just because a general bound exists doesn't mean your specific sequence will adhere to those frequency constraints, so you need to check those things separately.

Tom: This is definitely moving the discussion from just "how complex is this thing?" to "what structural rules govern its complexity?"

Jane: The next step is figuring out how these tighter bounds translate into practical limits for sequence generation in production environments.

CNRS · Aix Marseille University

cs.FL, math.CO, math.DS

Submitted: 2026-03-11

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: Smooth words are exactly the factors of smooth sequences over any binary alphabet, and this paper proves that their complexity is governed by a specific growth rate related to alphabet properties.

Key concepts

Factor Complexity
This measures how many distinct factors (subsequences) a given word or sequence contains. For smooth words, the paper focuses on how this number grows as the length of the word increases. Understanding this growth rate is central to determining the complexity of these sequences.
Even/Odd Alphabet Growth Rate
The paper analyzes whether the factor complexity growth rate is related to an even or odd alphabet structure. This distinction allows researchers to use specific theorems, like Theorem 1.40, to deduce important properties about the sequence's recurrence type and its potential for being morphic.
Morphicity
A sequence is considered morphic if it can be generated by a finite automaton. The paper links the language properties of smooth words, specifically whether their factor complexity reaches a certain constant ($C_{inf}$), to the concept of morphicity through Conjecture 1.16 and Theorem 1.40.

Terminology

Summary

Smooth words are exactly the factors of smooth sequences over any binary alphabet, and this paper proves that their complexity is governed by a specific growth rate related to alphabet properties. p. 0

Where the paper says it

The main way to study their language is to consider a finite version of smooth sequences called smooth words. In this paper we prove that the smooth words are exactly the factors of smooth sequences and we make progress towards the conjecture that the complexity of smooth words over {a, b} grows like Θ n log(a+b)/ log((a+b)/2) : we prove the lower bound over any alphabet and the upper bound over even alphabets, and we improve the known upper bound over odd and mixed alphabets.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved ability to determine if a sequence is morphic by analyzing its factor complexity growth rate based on whether it is over an even or odd alphabet. The system can use Theorem 1.40 to check if L(kappa) = C inf or not, and then deduce properties of the sequence's recurrence type.

  2. Enhanced capacity to estimate the factor complexity of smooth words over any binary alphabet by using the lower bound from Theorem 1.31 and several upper bounds from Theorem 1.32 and Theorem 1.35, depending on the alphabet type (even, odd, or mixed).

  3. Capability to establish a dichotomy for smooth sequences over mixed alphabets by linking L(x) = C inf to the morphicity of x through Conjecture 1.16 and Theorem 1.40, allowing predictions about whether a sequence is morphic based on its language properties.

  4. Precision in bounding the factor complexity of smooth words over even alphabets by applying Lemma 4.4, which states that for an even alphabet A = a + b is even, "the length of each word in Ti is psi (a+b)/2 i - psi for all i >= 0".

  5. Sophisticated analysis of letter frequencies within smooth words to derive upper bounds on factor complexity by utilizing the results from Theorem 1.35, specifically when the condition "|u|b |u| > 1/2 - phi" is met.

Abstract

Smooth sequences over an alphabet of positive integers a,b are sequences that are infinitely derivable, the emblematic example being the Oldenburger-Kolakoski sequence κ over 1,2. The main way to study their language is to consider a finite version of smooth sequences called smooth words. In this paper we prove that the smooth words are exactly the factors of smooth sequences and we make progress towards the conjecture that the complexity of smooth words over a,b grows like Θ (n(a+b)/ ((a+b)/2)): we prove the lower bound over any alphabet and the upper bound over even alphabets, and we improve the known upper bound over odd and mixed alphabets. We also provide a dichotomy that links the language, the morphicity and the factor complexity of κ.

Sources

Related papers