THE FOLD / CO-OP / THE HANDOFF / THE LYNDON FACTORIZATION
THE LYNDON FACTORIZATION
factor a string into non-increasing necklaces
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Lyndon factorization (Chen–Fox–Lyndon) splits any string uniquely into a sequence of Lyndon words in non-increasing order. A Lyndon word is one that is strictly smaller than all its rotations — an “aperiodic necklace” with a canonical starting point. Duval’s algorithm computes the factorization in linear time and constant extra space, in one left-to-right scan. Every string has exactly one such factorization; “banana” becomes b · an · an · a.
LIT verified live: over 3000 random strings, Duval’s factors concatenate back to the input, each factor is a Lyndon word, and the factors are non-increasing (window.__lyndon). FIG no framing; exact string comparisons.
LIT verified live: over 3000 random strings, Duval’s factors concatenate back to the input, each factor is a Lyndon word, and the factors are non-increasing (window.__lyndon). FIG no framing; exact string comparisons.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-handoff — the string is passed hand to hand into a chain of canonical necklaces, each no larger than the last. Duval’s scan is that handoff. AVAN (AI) built the instrument: Duval’s one-pass factorizer, the is-Lyndon rotation test, and the concatenation + non-increasing checks.
Credit as content: K. T. Chen, R. H. Fox & R. C. Lyndon (existence/uniqueness, 1958); Jean-Pierre Duval (linear algorithm, 1983). The weave: David names the-handoff; I run Duval’s scan to cut the string into Lyndon words, verify each is strictly smaller than its rotations, and confirm the pieces are non-increasing and rebuild the input.
Credit as content: K. T. Chen, R. H. Fox & R. C. Lyndon (existence/uniqueness, 1958); Jean-Pierre Duval (linear algorithm, 1983). The weave: David names the-handoff; I run Duval’s scan to cut the string into Lyndon words, verify each is strictly smaller than its rotations, and confirm the pieces are non-increasing and rebuild the input.
3 ONE DIMENSION
A Lyndon word is strictly smaller than every rotation of itself. Duval scans once, cutting the string into non-increasing Lyndon pieces: banana → b | an | an | a.
4 TWO DIMENSIONS · INTERACTIVE
A string factored by Duval; each Lyndon piece shown, with the concatenation and non-increasing order checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a string as unique non-increasing necklaces.
AVAN’s addition (the inverse-companion): decompose a string into a canonical, unique sequence of aperiodic necklaces (Lyndon words) in one linear scan — each strictly smaller than its rotations, the pieces non-increasing. The inverse of ‘treat the string as one opaque block’ is ‘cut it into its unique Lyndon factorization — a normal form.’ Magenta is the undivided string; green is the necklace factorization. A canonical cut, always the same.
LIT Genuine Lyndon factorization (Chen, Fox & Lyndon 1958 for existence/uniqueness; Jean-Pierre Duval 1983 for the linear algorithm). Verified live: over 3000 random strings, Duval's one-pass factors concatenate to the input (window.__lyndon.concat), each factor is a Lyndon word — strictly smaller than all its rotations (allLyndon) — and the factors are non-increasing (nonIncreasing) — exact string comparisons.
FIG No framing: Duval's one-pass factorizer, the is-Lyndon rotation test, and the concatenation + non-increasing checks run in-browser and agree. The AVAN inverse is honest — cutting a string into its unique non-increasing Lyndon factorization (a normal form) in one linear scan genuinely differs from treating it as an opaque block; magenta is the undivided string, green the necklace factorization. A canonical cut, always the same.
FIG No framing: Duval's one-pass factorizer, the is-Lyndon rotation test, and the concatenation + non-increasing checks run in-browser and agree. The AVAN inverse is honest — cutting a string into its unique non-increasing Lyndon factorization (a normal form) in one linear scan genuinely differs from treating it as an opaque block; magenta is the undivided string, green the necklace factorization. A canonical cut, always the same.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HANDOFF · David Lee Wise (ROOT0), with AVAN