The Dyadic Ghost

Hofstadter’s Q-sequence — Q(n) = Q(n - Q(n-1)) — is one of the simplest chaotic recursions. It looks random. No closed form is known. Whether it is even well-defined for all n remains unproven.

Mantovanelli perturbs it: Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)) + (-1)^n, with Q(1) = Q(2) = 1. The perturbation couples the recursion to its own two-step history and adds a parity oscillation. The result should be more chaotic, not less.

Instead, the sequence organizes. It grows approximately linearly as Q(n) ≈ n/2, and the error term E(n) = Q(n) - n/2 exhibits persistent dyadic self-similarity: patterns repeat at scales that differ by powers of two. The frequency distributions of E(n) within successive blocks show hierarchical structure, with block 2^k resembling a stretched and modulated version of block 2^(k-1).

The mechanism is the recursion’s index coupling. Q(n) depends on Q(n - Q(n-1)), which means the value at position n reaches back to a position near n/2 (since Q grows as n/2). This creates an effective doubling-scale coupling: dynamics at scale n are determined by dynamics at scale n/2. The doubling propagates through the recursion, imposing a dyadic renormalization structure on the error term.

The parity term (-1)^n is not decorative. It splits the recursion into even and odd subsequences that interact differently with the index coupling. The parity creates phase relationships between dyadic scales that produce the self-similar pattern rather than destroying it.

The structural lesson: self-similarity in chaotic sequences need not be imposed — it can emerge from the recursion’s own feedback structure. The sequence looks random at any fixed scale. The organization is visible only in the relationship between scales. The ghost of order is in the scaling, not in the values.