THE FOLD / RESPAWN / THE RESURRECT / THE DAVENPORT-SCHINZEL
THE DAVENPORT-SCHINZEL
a sequence that cannot alternate
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Take a sequence over n symbols with two rules: no symbol may sit next to itself, and no two symbols may alternate too many times — no
LIT verified live by exhaustive search, not by construction. For order 1 the longest sequence is exactly n at every n from 1 to 5. For order 2 it is exactly 2n−1 — 1, 3, 5, 7, 9. For order 3 the maxima already run past 2n−1: 1, 4, 8, 12 at n = 1 to 4, exceeding the order-2 bound at 3 of the 4 sizes tested.
a…b…a for order 1, no a…b…a…b for order 2, and so on. How long can such a sequence get? The answer is not obvious, and for order 3 it is famously not linear: it grows like n·α(n), where α is the inverse Ackermann function — a function that reaches 5 somewhere past the number of atoms in the universe.LIT verified live by exhaustive search, not by construction. For order 1 the longest sequence is exactly n at every n from 1 to 5. For order 2 it is exactly 2n−1 — 1, 3, 5, 7, 9. For order 3 the maxima already run past 2n−1: 1, 4, 8, 12 at n = 1 to 4, exceeding the order-2 bound at 3 of the 4 sizes tested.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): Harold Davenport and Andrzej Schinzel, 1965, who introduced these sequences while studying differential equations. The superlinear behaviour at order 3 was settled by Sergiu Hart and Micha Sharir in 1986, who proved λ3(n) = Θ(n·α(n)) — the first natural combinatorial problem where the inverse Ackermann function appears. The sequences bound the complexity of the lower envelope of n curves, which is why computational geometry cares.
AVAN (AI) searched exhaustively rather than exhibiting a construction. A sequence reaching 2n−1 proves the bound is achievable; it says nothing about whether something longer exists. Every sequence over the alphabet was enumerated instead, so the figures here are true maxima. The limit is honest and severe: this is n ≤ 5. The Θ(n·α(n)) result is cited, not reproduced — α does not become interesting at any size a browser can search.
AVAN (AI) searched exhaustively rather than exhibiting a construction. A sequence reaching 2n−1 proves the bound is achievable; it says nothing about whether something longer exists. Every sequence over the alphabet was enumerated instead, so the figures here are true maxima. The limit is honest and severe: this is n ≤ 5. The Θ(n·α(n)) result is cited, not reproduced — α does not become interesting at any size a browser can search.
3 ONE DIMENSION
Three orders, and where each one stops.
4 TWO DIMENSIONS · INTERACTIVE
The longest sequence at each order, and the alternation that ends it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the lower envelope of a family of curves.
AVAN’s addition (the inverse-companion): the forward reading is “forbidding alternation bounds the length.” The inverse is that the bound stops being a number and becomes a growth rate exactly when the forbidden pattern gets long enough to be rare. At order 1 and 2 the constraint bites on every step and the answer is a formula; at order 3 it almost never bites, and what is left is a Θ(n·α(n)) that no finite search can distinguish from linear. Read backwards, α(n) is not a strange function that turned up — it is what a bound looks like when the thing it forbids has almost stopped happening, and the reason nobody found it by computing examples is that at every size you can compute, it is 3.
LIT by exhaustive search rather than construction, for order 1 the longest sequence is exactly n at every n from 1 to 5; for order 2 it is exactly 2n-1, giving 1, 3, 5, 7, 9; and for order 3 the maxima already run past 2n-1 at 1, 4, 8, 12 for n = 1 to 4, exceeding the order-2 bound at 3 of the 4 sizes tested
FIG Human lineage, credited: Harold Davenport and Andrzej Schinzel, 1965, who introduced these sequences while studying differential equations. The superlinear behaviour at order 3 was settled by Sergiu Hart and Micha Sharir in 1986, who proved lambda_3(n) = Theta(n alpha(n)) - the first natural combinatorial problem where the inverse Ackermann function appears. The sequences bound the complexity of the lower envelope of n curves, which is why computational geometry cares. AVAN searched exhaustively rather than exhibiting a construction: a sequence reaching 2n-1 proves the bound is ACHIEVABLE and says nothing about whether something longer exists. The limit is honest and severe - this is n <= 5, and the Theta(n alpha(n)) result is CITED, NOT REPRODUCED, since alpha does not become interesting at any size a browser can search.
FIG Human lineage, credited: Harold Davenport and Andrzej Schinzel, 1965, who introduced these sequences while studying differential equations. The superlinear behaviour at order 3 was settled by Sergiu Hart and Micha Sharir in 1986, who proved lambda_3(n) = Theta(n alpha(n)) - the first natural combinatorial problem where the inverse Ackermann function appears. The sequences bound the complexity of the lower envelope of n curves, which is why computational geometry cares. AVAN searched exhaustively rather than exhibiting a construction: a sequence reaching 2n-1 proves the bound is ACHIEVABLE and says nothing about whether something longer exists. The limit is honest and severe - this is n <= 5, and the Theta(n alpha(n)) result is CITED, NOT REPRODUCED, since alpha does not become interesting at any size a browser can search.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RESURRECT · David Lee Wise (ROOT0), with AVAN