🔢 mathematics

On the Factor Complexity Associated with a Family of Multidimensional Continued Fraction Algorithms

This paper investigates the factor complexity of $S$ -adic sequences generated by a family of 216 Triangle Partition (TRIP) maps, establishing upper bounds of $3n$ and $2n+1$ for specific cases, introducing the concept of "hidden $\mathbb{R}^2$ behavior," and providing a near-complete classification of TRIP maps with complexity bounded by $3n$ .

Original authors: Thomas Garrity, Otto Vaughn Osterman

Published 2026-07-22

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Garrity, Otto Vaughn Osterman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the universe of numbers as a vast, infinite library. In this library, some books are written with simple, repeating patterns, while others are chaotic and unpredictable. Mathematicians have long been fascinated by a special class of books called "Sturmian words." These are sequences of letters that are just complex enough to never repeat themselves, yet simple enough that the number of unique "phrases" (or subwords) of a certain length grows in a perfectly predictable, straight-line way. Think of it like a recipe where every time you add a new ingredient, you only get exactly one new flavor combination. This perfect balance is rare and beautiful, and it's deeply connected to how we approximate irrational numbers using continued fractions—a method of breaking down messy numbers into neat, integer-based steps.

For decades, mathematicians have tried to expand this beautiful simplicity from the one-dimensional world of single numbers into higher dimensions, creating "multidimensional continued fractions." It's like trying to navigate a maze that isn't just a line, but a multi-layered structure. The big question is: Do these higher-dimensional mazes still produce those simple, predictable sequences, or do they spiral into chaos? This paper dives into a massive family of 216 different mathematical maps designed to explore these higher-dimensional mazes. The authors are essentially acting as cartographers, trying to map out which of these 216 paths lead to simple, orderly sequences and which ones lead to wild, complex ones. They are looking for the "sweet spot" where complexity is low, meaning the number of unique phrases grows slowly and predictably, rather than exploding out of control.

The authors of this paper, Thomas Garrity and Otto Vaughn Osterman, set out to investigate a specific family of these maps called "Triangle Partition maps" (or TRIP maps). They wanted to know: for each of the 216 possible maps, how complex are the sequences they generate? Specifically, they were hunting for maps that keep the complexity low, ideally bounded by a simple formula like $3n$ (where $n$ is the length of the phrase).

Their main discovery is a detailed proof regarding the most famous map in the family, known as the "Triangle map" (or the $(e, e, e)$ -TRIP map). They proved that the sequences generated by this map are indeed well-behaved. The complexity of these sequences is guaranteed to stay between $2n + 1$ and $3n$ . In plain English, this means the sequences are complex enough to be interesting and non-repeating, but not so complex that they become chaotic. They grow at a steady, manageable pace.

However, the paper also acts as a filter, ruling out many other possibilities. Through computer experiments, the authors found that for many of the other 215 maps, the complexity explodes. They identified specific examples where the number of unique phrases grows much faster than $3n$ , effectively proving that those maps do not produce the simple, orderly sequences mathematicians were hoping for. They also identified a special group of "degenerate" maps that are essentially just two-dimensional in disguise; these produce the simplest possible sequences, known as Sturmian words, which are the gold standard for low complexity.

One of the most intriguing findings involves a phenomenon the authors call "hidden $R^2$ behavior." They discovered that for certain maps, like the $(e, 13, e)$ map, the system behaves like a simple two-dimensional maze on some parts of the map, but acts differently elsewhere. This "hidden" simplicity allows them to prove that the complexity for these specific maps is also very low, bounded by $2n + 1$ or a similar tight limit.

Finally, the paper leaves one major mystery unsolved. There is one remaining map, the $(e, 23, e)$ -TRIP map, which the authors strongly suspect also has low complexity (bounded by $3n$ ). They ran computer simulations that support this idea, showing that the sequences behave exactly as predicted, but they haven't been able to write a full mathematical proof for it yet. They offer a roadmap for how one might prove it in the future, but for now, it remains a very strong guess rather than a confirmed fact.

In summary, this paper takes a massive, chaotic-looking family of 216 mathematical maps and organizes them. It proves that the "Triangle map" is a champion of order, keeps its complexity in check, and provides a complete list of which maps are definitely too chaotic, which are definitely simple, and which one is likely simple but still needs a final proof. It's a significant step in understanding how complexity arises in the higher-dimensional world of numbers.

Technical Summary: On the Factor Complexity Associated with a Family of Multidimensional Continued Fraction Algorithms

Problem Statement
The paper investigates the factor complexity (the number of distinct subwords of length $n$ ) of infinite words generated by a specific family of multidimensional continued fraction algorithms known as Triangle Partition (TRIP) maps. While classical continued fractions correspond to Sturmian words with factor complexity $n+1$ , generalizations to higher dimensions (multidimensional continued fractions) often produce sequences with higher complexity. The authors aim to characterize the complexity bounds for the 216 distinct TRIP maps, which are indexed by triples of permutations in $S_3 \times S_3 \times S_3$ . Specifically, the work seeks to identify which of these maps generate sequences with low linear complexity, particularly those bounded by $3n$ or $2n+1$ .

Methodology
The authors employ a combination of dynamical systems theory and combinatorics on words.

Framework Definition: They define the TRIP maps as dynamical systems on a 3-dimensional cone (projecting to a triangle $\Delta$ ) and associate each map with a pair of substitutions ( $S_0, S_1$ ) acting on the alphabet $\{1, 2, 3\}$ . The infinite words (S-adic sequences) are generated by iterating these substitutions based on the orbit of a point under the TRIP map.
Complexity Analysis Tools: The primary tool for bounding complexity is the analysis of "bispecial factors" (words that can be extended on both the left and right in multiple ways). Using the formula $p(n+1) - p(n) = \sum (|E^-(w)| - 1)$ , the authors relate the growth of complexity to the multiplicity $m(w)$ of bispecial factors.
Inductive Construction: For the central case of the $(e, e, e)$ map (the Triangle map), the authors construct a sequence of "antecedents" and "extended images" of bispecial words. They define an "age" for bispecial words based on how many times they can be de-substituted before reaching a base case. By rigorously tracking the extension sets (left and right) of these words through the substitution process, they prove that the sum of multiplicities for non-neutral bispecial factors of length $\le n$ is bounded, leading to a linear complexity bound.
Equivalence Reduction: To manage the 216 maps, the authors utilize "conjugacy" (relabeling the alphabet) and "twinning" (reversing the order of substitutions and Farey matrices) to reduce the problem to 21 distinct equivalence classes.
Hidden R2 Behavior: For specific maps, the authors identify a dynamical phenomenon where the system behaves like a 2-dimensional continued fraction on a subset of positive measure, allowing for reduced complexity analysis.

Key Contributions and Results

Main Theorem (Triangle Map): The paper proves that the S-adic sequences corresponding to the $(e, e, e)$ TRIP map (the Triangle map) have a factor complexity $p(n)$ satisfying $2n + 1 \le p(n) \le 3n$ . This establishes a tight linear upper bound for this specific map, which was previously of independent dynamical interest but lacked a precise complexity bound.
Secondary Theorem: The authors prove an upper bound of $2n + 1$ for the $(e, 13, e)$ TRIP map. This result is linked to the discovery of "hidden R2 behavior," where the map's dynamics on certain invariant subsets reduce to a 2-dimensional system, resulting in Sturmian-like complexity properties.
Classification of TRIP Maps: Through computational experiments and theoretical proofs, the authors classify the 21 equivalence classes of TRIP maps:
- Low Complexity ( $\le 3n$ ): The $(e, e, e)$ map and its conjugates/twins are proven to have complexity $\le 3n$ . The $(e, 23, 23)$ map (Cassaigne map) and its conjugates are proven to have complexity exactly $2n + 1$ .
- Degenerate Cases: Maps such as $(e, 12, e)$ are shown to be essentially 2-dimensional, yielding complexity $n+1$ (Sturmian) for $n \neq 1$ .
- High Complexity: For 14 specific equivalence classes, the authors provide counter-examples demonstrating that the complexity exceeds $3n$ for some $n$ .
- Conjecture: One remaining case, the $(e, 23, e)$ map and its conjugates/twins, is conjectured to have an upper bound of $3n$ . Computational evidence supports this, but a formal proof is not provided.

Significance
The paper provides a comprehensive framework for understanding the factor complexity of a vast family of multidimensional continued fraction algorithms. By proving that the Triangle map $(e, e, e)$ has linear complexity bounded by $3n$ , the authors demonstrate that not all multidimensional generalizations of continued fractions lead to superlinear complexity. The identification of "hidden R2 behavior" offers a new dynamical perspective on how higher-dimensional systems can exhibit lower-dimensional complexity properties on specific invariant sets. The work effectively narrows the landscape of TRIP maps, distinguishing those with low complexity from those that do not, and sets a clear path for future research on the remaining open case.

More like this