Fractal Staircases in a Self-Referential Equation

Can you still find new mathematics by looking? The Mandelbrot set is the famous example: a one-line rule, iterated, hiding a structure nobody had put there. I wanted to try the same thing deliberately. Not by extending a famous object, but by searching blindly through simple rules and keeping only what is both new and lawful.

This post reports what came out. It is a small result, not a Mandelbrot set. But it is exact, it has a short proof, and as far as I can tell it has not been written down before.

The equation

The equation is

It has an obvious solution. Try $f(x) = c\,x$: substituting gives $c = 1 - c + c^3$, whose roots are the degenerate $c = 1$ and $c = 1/\varphi$, where $\varphi = (1+\sqrt5)/2$ is the golden ratio. So the straight line $f(x) = x/\varphi$ solves it.

The surprise is that it has many other solutions, and they are not smooth. They are staircases: continuous functions whose slope is only ever 0 or 1, which repeat exactly when you zoom out by a fixed factor $L$.

The blue staircase repeats when you double $x$. The red one repeats when you multiply $x$ by the plastic number $\rho \approx 1.3247$, the real root of $\rho^3 = \rho + 1$. Neither number appears anywhere in the equation.

The theorem

These two are the first members of an infinite family.

Theorem. Let $p \ge 1$ be an integer and let $L = L_p > 1$ be the root of

Put $b = L^{1-p} + L^{1-2p}$, so that $1 < b < L$. For every integer $k$, define

Then $f$ is continuous, satisfies $f(Lx) = L\,f(x)$, and solves $f(x) = x - f(x - f(f(x)))$ for every $x > 0$.

The ladder scales are discrete:

Why it works

The proof is short enough to give in full. The single fact it uses is the defining relation $L^{-p} + L^{1-2p} = 1$. Write $R_k$ for the rising step $[L^k, L^k b)$ and $F_k$ for the flat step $[L^k b, L^{k+1})$.

First, $f$ maps each rising step $R_k$ onto the whole period $[L^{k-p}, L^{k+1-p})$. Its left end goes to $L^k - L^{k+1-2p} = L^{k-p}$ by the defining relation, and its right end to $L^{k+1-p}$. That also shows $f$ is continuous. There are three cases.

$x$ on a flat step $F_k$. Then $f(x) = L^{k+1-p}$ and $f(f(x)) = L^{k+1-2p}$. Put $u = x - L^{k+1-2p}$. As $x$ runs over $F_k$, $u$ runs exactly over the rising step $R_{k+1-p}$. The left end checks out directly, and the right end uses $1 - L^{-2p} = (1 - L^{-p})(1 + L^{-p})$. On that step $f(u) = u - L^{k+2-3p}$, so

$x$ on a rising step, and $f(x)$ on a rising step. Then $u = x - f(f(x))$ lands exactly on $L^{k-p} b$, the corner where a flat step begins, so $f(u) = L^{k+1-2p}$ and $x - f(u) = f(x)$.

$x$ on a rising step, and $f(x)$ on a flat step. Then $f(f(x)) = L^{k+1-2p}$, so $u = f(x)$ itself, and again $x - f(u) = f(x)$.

That covers every $x > 0$. The indices $k+1-p$ and $k-p$ only land on whole steps when $p$ is an integer, so this mechanism produces a discrete ladder. It is not the only mechanism, as the next section shows.

A continuum above 2

Take the step height $f(L^k) = L^k/2$ and any scale $L \ge 2$:

This also solves the equation exactly. Here the composition never needs to line up across distant periods. On a flat step, $f(x) = L^{k+1}/2$ stays in the same period precisely because $L \ge 2$. Then $f(f(x)) = L^k(L-1)/2$, and $u = x - f(f(x))$ runs over the rising step of the same period, which gives $x - f(u) = L^{k+1}/2 = f(x)$. On a rising step there are three subcases, and each closes in one line, as in the proof above.

At $L = 2$ this branch meets the $p = 1$ staircase, so the ladder hangs off the end of a continuum. A scan over all two-step staircases with scales up to 4 found nothing else: one continuous branch above 2, and the isolated ladder below it.

The integer sequences do not use the continuum evenly. The scale near 2.618 that I first could not explain is $\varphi^2$, on this branch. Sequences that show it match the $L = \varphi^2$ staircase to within $10^{-4}$, about 13 times better than the nearby scale $2.6$. Why the integers pick out $\varphi^2$ from a continuum of allowed scales is open.

The golden limit

As $p$ grows, $L_p$ slides down to 1 and the steps get finer. From $1 - L^{-p} = L \cdot L^{-2p}$ one gets $L^{-p} \to 1/\varphi$. Every staircase stays between $L^{-p}$ and a slightly larger bound, and that band closes onto the straight golden solution.

So the integer 2, the plastic number and the golden ratio sit in one family. The straight solution is the $p = \infty$ end of the ladder.

Where it came from

I did not start from this equation. I enumerated every rule of the form $a(n) = E$, where $E$ is built from $n$, the constants 1 and 2, the previous terms $a(n-1)$ and $a(n-2)$, addition, subtraction, and self-reference $a(\cdot)$. That gives about 11.3 million rules, of which about 2,000 produce distinct non-trivial integer sequences. I then kept only sequences that were absent from the OEIS and that showed exact structure their definition does not mention.

The filter's own controls came back correct. It rediscovered Hofstadter's G, Q and Conway sequences, and matched each to its OEIS entry.

One rule kept turning up:

Its large-scale shape is the equation above. Depending on the starting values, $a(n)/n$ settles onto different staircases. Fitting only the phase, the closed form matches sequences up to $n = 2^{24}$ to within $10^{-4}$, while the next-best member of the family misses by at least $1.5 \times 10^{-2}$.

Across 300,000 random seeds, a strict test of the step geometry found $p = 1$ about 52,000 times, $p = 2$ about 33,000 times, $p = 3$ about 5,000 times, and $p = 4$ only 26 times. Larger $p$ did not appear.

One case is proved for every $n$, not just observed. With seed $a(1) = 2$, $a(2) = 1$, the sequence is computed by a 13-state automaton reading $n$ in binary. An exact decision procedure checks the recurrence for all $n$, and perturbed versions of the rule fail it, as they should.

Several tempting claims did not survive the checks. One was a "continuous family" of solutions that turned out to be the trivial symmetry $f(x) \to c\,f(x/c)$, which every solution has. The theorem was also checked at 80 digits up to $p = 60$, separately from the proof above.

What is not settled

• Novelty. I searched for this equation and these scales and did not find them. The nearest work I found, Klaus Pinn's continuous models of meta-Fibonacci sequences, studies different equations. Nested recurrences are a well-studied area, though, and a specialist may recognise this. If you do, please tell me.
• Convergence. The integer sequences converge to the $p \ge 2$ staircases numerically. That is not proved.
• Selection. Why a given seed picks a given $p$ and phase is unexplained.
• Completeness. These are not all the solutions. Discontinuous variants also work, and staircases with more than two steps were not classified. Some seeds show a scale near 1.75 that I cannot yet explain.
• Selection. Integer sequences pick particular scales, such as 2 and $\varphi^2$, out of the continuum. Why is unexplained.

Why bother

The equation is about as simple as a self-referential rule can be, and nothing in it points to the plastic number, an infinite ladder of scales, or a continuum that begins exactly at 2. They are there anyway, and a proof short enough to read in five minutes holds them in place. That is the kind of hidden structure I set out to look for, and it suggests that blind search, with strict filters for novelty and exactness, can still turn up new mathematics.

The code, data and proof notes are available on request.