The Structural Regularity of Sequence Complexity Functions

38 concepts12 papers1 proposal

When we look at an infinite sequence generated by a simple, deterministic rule—such as a finite state machine or a repeating substitution—we intuitively expect it to be highly ordered. But how do we quantify this order?

In combinatorics on words, researchers measure this by defining a complexity function. Instead of looking at the sequence as a whole, a complexity function counts the variety of local patterns (or "subwords") of a given length $n$. For instance, subword complexity counts the number of distinct blocks of length $n$, while abelian complexity counts blocks based only on their letter frequencies, completely ignoring the order of the characters.

A remarkable and recurring insight across recent literature is that the complexity function of a structured sequence is rarely chaotic; instead, it mirrors the structural logic of the sequence itself. If a sequence is generated by a clean, recursive rule, its complexity profile often turns out to be ultimately periodic, linear, or a "regular" sequence that can itself be computed by a finite automaton.

The Automaticity-Regularity Correspondence

To understand why this happens, consider an automatic sequence like the Cantor sequence or the Thue-Morse sequence. These infinite strings are constructed fractally via substitution rules (for example, replacing $0$ with $01$ and $1$ with $10$). Because the sequence is built by scaling up smaller blocks, its internal patterns repeat across different dimensions.

This self-similar architecture forces the sequence's complexity function to obey strict recursive constraints. A function is called $\ell$-regular if its values at an index $n$ can be expressed as a linear combination of its values at scaled indices like $\ell n$ or $\ell n + r$. In essence, the complexity function can be computed by a finite-state linear system.

This deep link between generation rules and complexity profiles is illustrated by several key results:

  • The Cantor Sequence: In their work on $k$-abelian complexity (which counts distinct subwords up to the permutation of blocks of length $k$), Lü et al. proved that the $k$-abelian complexity of the Cantor sequence is always a 3-regular sequence for any $k \ge 1$. This provides strong evidence for a broader combinatorial hypothesis: the $k$-abelian complexity of any $\ell$-automatic sequence is itself $\ell$-regular.
  • The Sierpinski Word: Similarly, Bulgakova et al. analyzed the prefix palindromic length of the Sierpinski word—a measure of how many palindromes are needed to decompose its prefixes. They proved this complexity metric is a 3-regular function, meaning its behavior can be fully captured by a simple 3-state automaton.
  • Logarithmic Growth: Symmetries can also constrain growth rates tightly. Wen et al. investigated the additive complexity (the number of distinct digit sums in a window) of a Thue-Morse-like sequence. They proved that its complexity grows predictably and logarithmically according to the formula $2\lfloor\log_2 n\rfloor + 3$, and that the resulting complexity sequence is 2-regular.

In all these cases, the "logic" embedded in the sequence's generator is perfectly preserved within the function that counts its disorder.

Symmetries and Ultimate Periodicity

When constraints on a sequence are exceptionally rigid, the complexity function does not grow indefinitely; instead, it hits a ceiling and becomes ultimately periodic. This means that after a certain window length $n$, the number of distinct pattern variations repeats with a fixed period.

This phenomenon is highly visible when evaluating abelian and binomial complexities, where the exact ordering of characters is relaxed. For example, Wen investigated the abelian complexity of generalized Thue-Morse sequences. By mapping the relationship between character counts and the underlying substitution rules, Wen derived an exact piecewise formula showing that the complexity is ultimately periodic, with a period exactly equal to the base $k$ of the sequence.

When extending this analysis to more complex character-matching relations, the periodicity persists but scales with the alphabet size. Lü et al. characterized the 2-binomial complexity of generalized Thue-Morse words. They demonstrated that for an alphabet of size $m \ge 3$, the number of distinct equivalence classes of factors eventually repeats with a fixed period of $m^2$. Because the substitution rules tightly govern how frequently characters can appear relative to one another, no new variations in letter distributions can emerge once the window size exceeds a specific threshold.

Why the Underlying Base Matters

The regularity of a complexity function is also deeply tied to the number-theoretic properties of the system used to generate it. A prime example of this is found in the study of leading digit sequences (the first digits of $a^n$ when expressed in a base $b$).

Intuitively, the sequence of leading digits feels like it should fluctuate unpredictably. However, He et al. demonstrated that if the base $b$ is squarefree (meaning it has no repeated prime factors, like 5 or 6), the subword complexity is surprisingly simple: it is a perfectly linear function of the block length ($c_{a,b}n + d_{a,b}$).

Squarefree Base (e.g., b=6)    -->  Logarithmic distribution spreads evenly  --> Linear Complexity
Non-Squarefree Base (e.g., b=4)-->  Prime factors cluster and overlap       --> Intricate, Non-Linear Complexity

Why does the squarefree property matter? When a base contains a square factor (like $b=4$), the logarithmic distribution of the powers of $a$ begins to overlap and cluster in ways that break the clean geometric distribution of the digits. As He et al. showed, losing the squarefree property causes the complexity to deviate from a simple linear form, revealing a far more intricate and less predictable structural growth pattern.

Alternative Lenses on Complexity

The principle that structural constraints dictate complexity profiles extends well beyond pure combinatorics on words into dynamical systems, information theory, and biology:

  • Constrained Shifts: In symbolic dynamics, Periodic-Finite-Type (PFT) shifts represent systems where certain data patterns are forbidden in a repeating, periodic manner. Manada et al. showed that by using sliding-block maps, one can construct families of shifts where the internal sequence periods grow exponentially relative to the rules defining them, proving that simple periodic constraints can unlock massive structural complexity.
  • Information Theory and Stream Ciphers: To evaluate the randomness of keystreams, Zhou et al. introduced Cube Theory. By decomposing binary sequences into independent structural building blocks ("cubes"), they derived precise combinatorial formulas for sequences that experience sudden drops in linear complexity at specific error thresholds, creating a more intuitive tool to measure keystream stability.
  • Statistical Sources: When sequences are generated by probabilistic rather than deterministic rules, complexity manifests as an average rate. Jacquet et al. analyzed joint string complexity—the number of subwords shared between two distinct text sources—under Markov processes. They discovered that when the underlying sources share structural properties, their joint complexity exhibits unexpected periodic oscillations, providing a sensitive metric for distinguishing authors or languages even with minimal data.
  • Biological Sequences: This mathematical framework can even categorize natural data. Jin et al. developed a Generalized Topological Entropy based on the density of unique subword patterns to analyze human DNA. By measuring pattern repetition versus randomness, they revealed a strict biological hierarchy of structural regularity: promoter regions are the most highly structured, followed by exons, while non-coding introns exhibit the highest complexity.

Whether an infinite string is generated by a biological evolutionary constraint, a cryptographic requirement, or a pure mathematical substitution, its local variations remain bound to its global architecture. By studying the regularity of complexity functions, researchers can look past the surface-level chaos of a sequence and directly read the rules of the engine that built it.

Key Foundational Work

A Generalized Topological Entropy for Analyzing the Complexity of DNA Sequences (2014) — contributed 1 concept elements to this direction.
On the Period of a Periodic-Finite-Type Shift (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_squarefree_base_requirement_ab74aefb,
  title = {squarefree base requirement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/squarefree-base-requirement/rdr_ab74aefbee8d43c887e26a996fd95d19},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_squarefree_base_requirement_ab74aefb_v1,
  title = {squarefree base requirement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/squarefree-base-requirement/rdr_ab74aefbee8d43c887e26a996fd95d19/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake