🔢 mathematics

Non-Simple T-Prescriptions Yield T-Complexity Gains Infinitely Often

This paper affirms that non-simple T-prescriptions can achieve strictly higher T-complexity than simple ones for infinitely many maximum codeword lengths by demonstrating that the distinct-word requirement of simple prescriptions forces periodic threshold jumps that non-simple prescriptions can exploit to gain a complexity advantage.

Original authors: Thomas Schürmann

Published 2026-06-15

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Schürmann

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 you are a master chef trying to create the most complex recipe possible using a limited set of ingredients. In the world of computer science, this "recipe" is called a T-prescription, and the "complexity" of the recipe is measured by something called T-complexity.

This paper answers a specific question: Can a chef who breaks the rules create a more complex recipe than a chef who strictly follows the rules, and can they do this over and over again as the recipes get longer?

Here is the breakdown of the paper's findings using simple analogies:

1. The Rules of the Game

Think of building a code (a recipe) like stacking blocks.

The Ingredients: You start with a basic alphabet (like letters A and B).
The Process: You pick a current block (a "copy pattern") and duplicate it.
- Simple Chefs (Simple Prescriptions): They follow a strict rule: "I can only copy a block once." If they pick a block, they add one copy and move on.
- Unrestricted Chefs (Non-Simple Prescriptions): They have a secret power: "I can copy a block twice (or more) if I want." This adds extra layers of complexity.

The "Complexity Score" is calculated based on how many times you copy. Copying once adds a small score. Copying twice adds a slightly bigger score (specifically, it adds $\log_2 3$ , which is about 1.58, whereas copying once adds 1).

2. The Big Problem: Running Out of Short Blocks

There is a catch. Once you use a specific block (a word) as a pattern to copy, you can never use it again. It's like a "one-time use" coupon.

If you are a Simple Chef making a very long recipe, you must keep finding new, unused blocks to copy.
At first, you use short blocks (like "A" or "B").
But eventually, you run out of short blocks. You are forced to start using longer, more complex blocks (like "ABBA" or "AAB") just to keep the recipe going.

3. The "Jump" in Difficulty

Because the Simple Chef is forced to switch to longer blocks, the total length of their recipe jumps up in big steps.

Imagine the Simple Chef is climbing a staircase. Most steps are small, but occasionally, because they ran out of short blocks, they have to take a giant leap to reach the next available block.
The paper proves that these "giant leaps" happen infinitely often. No matter how long the recipe gets, there will always be a moment where the Simple Chef is forced to jump to a much longer block.

4. The Trick: The Non-Simple Chef Wins

Here is where the Unrestricted Chef (the one who can copy twice) wins.

Just before the Simple Chef is forced to take that giant leap to a new, long block, the Unrestricted Chef looks at the current block they are holding.
Instead of moving on to a new block, the Unrestricted Chef says, "I'll just copy this current block twice instead of once."
The Result:
- The recipe gets slightly longer (because of the extra copy).
- The complexity score goes up (because copying twice is worth more than copying once).
- Crucially: The recipe is still shorter than the next giant leap the Simple Chef would have to take.

So, at these specific moments, the Unrestricted Chef has a recipe that is:

Longer than the previous Simple Chef's best.
Shorter than the Simple Chef's next possible best.
More Complex than anything the Simple Chef could have made at that exact length.

5. The Conclusion

The paper proves that this isn't just a fluke that happens once. It happens infinitely many times.

Every time the Simple Chef is forced to jump to a longer block, there is a "sweet spot" where the Unrestricted Chef can squeeze in a slightly more complex recipe by simply copying one item twice.
The authors show that for any alphabet with at least two symbols (like 0 and 1), you can find an infinite number of recipe lengths where the "rule-breaker" creates a strictly more complex result than the "rule-follower."

Summary

Think of it like a video game level. The "Simple Player" is forced to skip levels because they run out of short shortcuts. The "Unrestricted Player" realizes that at the exact moment the Simple Player has to skip a level, they can just "double-jump" on the current level to get a higher score, beating the Simple Player's record without having to skip to the next level yet. The paper proves this "double-jump" strategy works forever.

Technical Summary: Non-Simple T-Prescriptions Yield T-Complexity Gains Infinitely Often

Problem Statement
The paper addresses a specific question regarding T-complexity, a deterministic complexity measure for finite words based on the recursive construction of T-codes. T-complexity is defined via T-prescriptions, which are sequences of T-augmentation steps. Each step selects a "copy pattern" (a current codeword) and a "copy factor" $k \ge 1$ . The T-complexity of a prescription $P$ is the sum of $\log_2(k_i + 1)$ for all steps.

A prescription is simple if all copy factors are 1; otherwise, it is non-simple. Titchener et al. [5] previously demonstrated finite examples where non-simple prescriptions achieved higher T-complexity than any simple prescription for a given maximum codeword length. They explicitly asked whether this phenomenon occurs infinitely often for every fixed alphabet of size at least two. Specifically, the problem asks if there are infinitely many lengths $N$ where the unrestricted exact-length maximum T-complexity, $C_T(N)$ , strictly exceeds the simple exact-length maximum, $C_T^{(1)}(N)$ .

Methodology
The author employs an elementary proof strategy based on the structural properties of T-augmentation and the constraints imposed by the "no recycling" rule of copy patterns. The methodology proceeds as follows:

Definitions and Bounds: The paper defines $L_m$ as the minimal possible maximum codeword length achievable by any simple prescription with exactly $m$ steps (arity $m$ ). It defines the increment $d_m = L_m - L_{m-1}$ , representing the minimal length cost of adding the $m$ -th step to a simple prescription.
Analysis of Increments: Using the fact that a valid T-prescription cannot reuse a copy pattern (Lemma 3), the author establishes that a simple prescription of arity $m$ must utilize $m$ distinct nonempty words. By analyzing the density of words over a finite alphabet, the paper proves that the average length of these distinct words must grow unbounded as $m$ increases. Consequently, the sequence of increments $d_m$ is unbounded.
Existence of Jumps: The unboundedness of $d_m$ implies that there are infinitely many indices $m$ where the increment strictly increases, i.e., $d_{m+1} > d_m$ .
Construction of Counter-Examples: At any such index $m$ $m$ where $d_{m+1} > d_m$ $d_{m + 1} > d_{m}$ , the author constructs a specific non-simple prescription $\hat{P}_m$ $\hat{P}_{m}$ . This is done by taking a minimal simple prescription $P_m$ $P_{m}$ of arity $m$ $m$ and changing the copy factor of the final step from 1 to 2.
- The new maximum length $N_m$ of $\hat{P}_m$ is $L_m + |p_m|$ , where $|p_m|$ is the length of the last pattern.
- Because $|p_m| \le d_m$ and $d_{m+1} > d_m$ , the new length $N_m$ satisfies $N_m < L_{m+1}$ .
- This ensures that no simple prescription with arity $m+1$ or greater can achieve a maximum length of $N_m$ or less. Thus, the best simple prescription for length $N_m$ has at most $m$ steps, yielding a complexity of at most $m$ .
- The constructed non-simple prescription $\hat{P}_m$ has complexity $(m-1) + \log_2 3$ , which is strictly greater than $m$ .

Key Contributions and Results

Affirmative Answer: The paper proves that for every alphabet size $r \ge 2$ , there exist infinitely many maximum codeword lengths $N$ such that $C_T(N) > C_T^{(1)}(N)$ .
Stronger Upper-Envelope Statement: The result is proven against the simple upper envelope $C_T^{(1), \le}(N)$ (the maximum complexity of any simple prescription with length $\le N$ ), which implies the strict inequality for the exact-length case.
Mechanism Identification: The paper identifies the mechanism driving these gains: the "no recycling" constraint forces simple prescriptions to use increasingly long distinct words, creating strict upward jumps in the minimal length thresholds. Non-simple prescriptions exploit these gaps by increasing the copy factor of the final step, gaining a complexity boost of $\log_2 3 - 1$ without crossing the next simple threshold.
Elementary Nature: The proof is described as elementary, relying on counting arguments and the recursive definition of T-codes rather than complex asymptotic analysis.

Significance and Limitations
The paper claims significance by providing a definitive, elementary answer to a finite-length question left open by Titchener et al. [5]. It demonstrates that the advantage of non-simple prescriptions is not merely an isolated short-length phenomenon but occurs infinitely often.

The author explicitly notes the modesty of the result regarding computational efficiency and structure:

The proof relies on a brute-force exhaustive enumeration to identify the jump indices; no closed-form sequence of these lengths or an efficient algorithm to locate them is provided.
The constructed non-simple prescriptions are valid witnesses to the inequality but are not asserted to be the unrestricted maximizers for those lengths (though the strict inequality holds because the unrestricted maximum dominates all valid prescriptions).
The paper does not address the density of these exceptional lengths, the magnitude of the largest possible gain, or asymptotic distribution properties, focusing strictly on the existence of infinitely many such instances.