🔢 mathematics

Dyadic Self-Similarity in a Perturbed Hofstadter $Q$ -Recursion

This paper presents numerical evidence and heuristic analysis suggesting that a perturbed variant of Hofstadter's $Q$ -recursion exhibits well-defined, approximately linear growth with a fluctuation term displaying persistent dyadic self-similarity driven by a parity-dependent renormalization mechanism.

Original authors: Marco Mantovanelli

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marco Mantovanelli

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 building a tower of blocks, but there's a catch: to decide how tall the next block should be, you have to look back at the tower you've already built. Specifically, you look at the height of the block you placed just before the last one, and the one before that, to decide where to place your next measurement.

This is the essence of a meta-Fibonacci sequence. It's a mathematical recipe that refers to itself. The most famous version of this is Hofstadter's Q-sequence, which is known for being chaotic and unpredictable—like a tower that suddenly collapses or grows in a wild, jagged way.

In this paper, the author, Marco Mantovanelli, introduces a slightly tweaked version of this recipe. He adds a tiny "nudge" to the formula: every time he calculates a new number, he adds or subtracts 1 depending on whether the step number is even or odd (like a heartbeat: thump-thump, thump-thump).

Here is what he discovered, explained through simple analogies:

1. The Tower Grows Straight (Mostly)

If you plot the height of this tower over time, it doesn't look like a wild rollercoaster. Instead, it grows in a very straight line.

The Analogy: Imagine a tree growing. It might wiggle a bit left and right as it grows, but its overall height increases steadily.
The Finding: The author found that for every step $n$ , the height of the tower is roughly half that number ( $n/2$ ). So, at step 100, the tower is about 50 units high. This is surprisingly stable for a self-referencing recipe.

2. The "Echo" Effect (Dyadic Self-Similarity)

This is the most magical part of the discovery. If you zoom in on the "wiggles" (the small deviations from the straight line), you see a pattern that repeats itself at different scales.

The Analogy: Think of a fractal (like a fern leaf or a coastline). If you look at the whole mountain, you see a shape. If you zoom in on a small rock on the mountain, you see a similar shape. If you zoom in even further on a grain of sand, the shape is still there.
The Finding: The author calls this "dyadic self-similarity." It means the pattern of wiggles at step 1,000 looks remarkably similar to the pattern at step 2,000, 4,000, and 8,000. The "noise" of the sequence isn't random; it's a structured echo that repeats every time you double the size of the problem.

3. The Two-Headed Clock

Why does this happen? The author suggests the recipe has a hidden "clock" mechanism.

The Analogy: Imagine a relay race where the runner at the finish line looks back to see who is running at the halfway point. Because the runner at the finish line is always looking back at the halfway point, the race dynamics at the end are a direct copy of the dynamics in the middle.
The Finding: The math shows that to calculate the current number, the recipe almost always looks back at numbers that are roughly half the current size. This creates a feedback loop that copies the behavior from "halfway" to "full," creating that repeating fractal pattern.
The Twist: There are actually two clocks running slightly differently (one for even steps, one for odd steps). They work together like a pair of dancers who are slightly out of sync, creating a complex but rhythmic dance.

4. The "Frequency" of Numbers

The author also asked: "How often does each number appear in the sequence?"

The Analogy: Imagine a playlist of songs. Some songs are hits (played 100 times), some are B-sides (played 10 times), and some are never played.
The Finding: The numbers in this sequence follow a strict rule. If you group the numbers into "blocks" (like 1-2, 4-8, 8-16), the number of times a specific value appears follows a perfect geometric pattern. It's like a playlist where the hits are distributed in a mathematically precise way, not by chance.

5. The Fragile Start

Finally, the author tested what happens if you change the very first few numbers (the "seeds") of the sequence.

The Analogy: Think of starting a game of Jenga. If you start with the blocks perfectly balanced, the tower grows tall. If you start with them slightly off, the tower might collapse after just a few moves.
The Finding: Most starting combinations cause the sequence to "crash" (the math breaks because it tries to look back at a block that doesn't exist yet). However, a few specific starting combinations allow the tower to grow forever. Interestingly, even though these "surviving" towers look different up close (different wiggles), they all grow at the exact same steady speed ( $n/2$ ).

The Big Picture

The paper concludes that this specific mathematical recipe is governed by a hidden order. Even though it looks like a chaotic mess of numbers, it is actually a highly structured system that repeats its own patterns over and over as it grows.

The author calls this a "parity-split dyadic renormalization mechanism." In plain English: The sequence has a two-sided rhythm that copies its own behavior from smaller sizes to larger sizes, creating a beautiful, repeating fractal structure that we can see if we look at the right way.

While we can see this pattern clearly with computers, the author admits that writing down the exact mathematical proof for why it happens is still a mystery waiting to be solved.

1. Problem Statement

The paper investigates a perturbed variant of the famous Hofstadter Q-sequence, a meta-Fibonacci recursion known for its complex and often chaotic behavior. The standard Hofstadter Q-sequence is defined by $Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))$ .

The author studies the perturbed recursion:
$Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)) + (-1)^n$
with initial conditions $Q(1) = Q(2) = 1$ .

The primary objective is to understand the long-term asymptotic behavior, the structure of fluctuations around the mean growth, the distribution of values taken by the sequence, and the sensitivity of the system to initial conditions. Unlike the original Hofstadter sequence, which is notorious for undefined terms (dying) for certain initial conditions, this perturbed version appears to remain well-defined for extremely large $n$ (up to $3 \times 10^{10}$ in numerical experiments).

2. Methodology

The study employs a combination of large-scale numerical computation, heuristic asymptotic analysis, and structural decomposition:

Numerical Simulation: The sequence was computed sequentially using a dedicated C program up to $n = 3 \times 10^{10}$ . This allowed for the observation of global trends and the collection of statistical data on value frequencies.
Fluctuation Analysis: The sequence was decomposed into a linear trend and a fluctuation term: $Q(n) = n/2 + E(n)$ . The behavior of $E(n)$ was analyzed to detect self-similarity.
Dyadic Scaling: The authors examined the sequence on dyadic scales (powers of 2) by plotting rescaled profiles $R_k(m) = Q(2^k m) - 2^{k-1}m$ to test for renormalization properties.
Index Dynamics (Clock Sequences): Following Pelesko's approach, the recursive indices $t_1(n) = n - Q(n-1)$ and $t_2(n) = n - Q(n-2)$ were analyzed as "clock sequences" governing the internal dynamics.
Parity-Split Diagnostics: The quantity $R(n) = Q(2n) - 2Q(n)$ was introduced to test for linear scaling and parity dependence.
Frequency Analysis: The multiplicity of values $F(m)$ (how often the $m$ -th odd integer appears) was computed and grouped into dyadic blocks $B_k = \{2^k, \dots, 2^{k+1}-1\}$ .
Initial Condition Sensitivity: A systematic classification was performed for all triples $(Q(1), Q(2), Q(3)) \in \{1, 2, 3\}^3$ to determine which seeds lead to long-lived sequences versus rapid termination.

3. Key Contributions and Results

A. Linear Growth and Fluctuations

Linear Growth: Numerical evidence strongly suggests that the sequence grows linearly with a slope of $1/2$ :
$Q(n) \sim \frac{n}{2}$
Dyadic Self-Similarity: The fluctuation term $E(n) = Q(n) - n/2$ exhibits a pronounced dyadic self-similarity. When plotted on logarithmic scales, the fluctuation patterns repeat across intervals related by powers of two.
Heuristic Explanation: The recursion naturally couples values at scale $n$ with values near scale $n/2$ because the indices $n - Q(n-1)$ and $n - Q(n-2)$ are approximately $n/2$ . This creates a renormalization mechanism where information propagates from $n/2$ to $n$ , leading to log-periodic oscillations.
Parity-Split Mechanism: The renormalization is not a simple scalar law but is parity-split. The diagnostic $R(n) = Q(2n) - 2Q(n)$ shows distinct behaviors for odd and even $n$ , suggesting the dynamics are governed by two interlaced subsequences (odd and even indices) that evolve differently.

B. Frequency Structure

The distribution of values in the sequence follows a highly regular dyadic law:

Odd Values Only: All terms $Q(n)$ are odd.
Geometric Multiplicities: Within dyadic blocks $B_k$ , the multiplicities of frequency values follow a geometric pattern. Specifically, the number of times a frequency $r$ occurs decreases by a factor of 2 as $r$ increases.
Peak Scaling: The location of the maximum frequency peak $m_k$ within block $B_k$ satisfies the empirical scaling relation:
$m_k \approx \frac{4}{3} 2^k$
This suggests a deep connection between the growth rate ( $n/2$ ) and the self-referential structure.

C. Dependence on Initial Conditions

Fragility: The recursion is highly sensitive to initial conditions. Among the $27$ triples tested in $\{1, 2, 3\}^3$ , the majority lead to rapid termination (usually at $n=5$ ) because the recursive indices become non-positive.
Surviving Classes: Only a small subset of seeds generates long-lived sequences. These surviving cases fall into three categories:
1. Trajectories that merge into the original sequence (e.g., $(2,1,1)$ ).
2. An explicit exceptional orbit (e.g., $(1,1,2)$ where $Q(2m)=2m$ ).
3. Genuinely new long-lived trajectories with irregular local fluctuations.
Robustness of Global Growth: Despite significant differences in local fluctuation structures among different surviving seeds, all long-lived cases obey the same global growth law $Q(n) \approx n/2$ .

4. Significance and Open Problems

Theoretical Insight: The paper provides strong evidence that a simple perturbation ( $(-1)^n$ ) to the chaotic Hofstadter Q-recursion stabilizes the system into a regime of structured self-similarity. This challenges the notion that such recursions are inherently chaotic or undefined.
Renormalization in Discrete Systems: The work identifies a "parity-split dyadic renormalization" mechanism, offering a new perspective on how self-referential integer sequences can exhibit scale-invariant properties similar to those found in physics and analytic combinatorics.
Open Problems: The author formulates several conjectures and open problems, including:
- Proving the linear growth limit $\lim_{n \to \infty} Q(n)/n = 1/2$ .
- Rigorously establishing the existence of a bounded, log-periodic function $\Phi$ such that $Q(n) = n/2 + \Phi(\log_2 n) + o(1)$ .
- Classifying all initial conditions that yield infinite sequences.
- Understanding the statistical distribution of the difference sequence $D(n) = Q(n+1) - Q(n)$ .

In conclusion, Mantovanelli demonstrates that this perturbed Hofstadter recursion is governed by a robust, parity-dependent dyadic renormalization mechanism, resulting in a sequence that is globally linear but locally self-similar, with a highly regular frequency distribution.