THE FOLD / LOOT / THE INVENTORY / THE LYNDON
THE LYNDON
unique factorization of a string into Lyndon words
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A Lyndon word is a string strictly smaller than all of its rotations — ‘aab’ is one, ‘aba’ and ‘baa’ are not. The Chen–Fox–Lyndon theorem says every string factors uniquely into a sequence of Lyndon words in non-increasing order — a prime factorisation for strings. Duval’s algorithm finds it in O(n) with constant extra memory.
For example ‘banana’ → b · an · an · a. Lyndon words also form a basis of the free Lie algebra and give the fastest way to compute a string’s least rotation.
LIT verified live: for 500 random strings, Duval’s factorisation concatenates back to the original, every factor is a Lyndon word (smaller than all its rotations), and the factors are non-increasing (window.__lyndon). FIG no framing; exact string combinatorics.
For example ‘banana’ → b · an · an · a. Lyndon words also form a basis of the free Lie algebra and give the fastest way to compute a string’s least rotation.
LIT verified live: for 500 random strings, Duval’s factorisation concatenates back to the original, every factor is a Lyndon word (smaller than all its rotations), and the factors are non-increasing (window.__lyndon). FIG no framing; exact string combinatorics.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-inventory — breaking a thing into its canonical, ordered parts. Lyndon factorisation is the inventory of a string: its unique, sorted list of atomic pieces. AVAN (AI) built the instrument: Duval’s linear algorithm, the Lyndon test (smaller than all rotations), the non-increasing check.
Credit as content: Roger Lyndon (1954); the factorisation theorem of K.-T. Chen, R. Fox & Lyndon; Jean-Pierre Duval’s linear-time algorithm (1983). The weave: David names the inventory; I factor strings into Lyndon atoms, prove each is minimal among its rotations, and show the decomposition is unique and ordered — primes for words.
Credit as content: Roger Lyndon (1954); the factorisation theorem of K.-T. Chen, R. Fox & Lyndon; Jean-Pierre Duval’s linear-time algorithm (1983). The weave: David names the inventory; I factor strings into Lyndon atoms, prove each is minimal among its rotations, and show the decomposition is unique and ordered — primes for words.
3 ONE DIMENSION
A string split into its Lyndon factors, drawn as ordered blocks — each strictly smaller than all its own rotations, and the sequence non-increasing from left to right, like exponents in a prime factorisation.
4 TWO DIMENSIONS · INTERACTIVE
Type or roll a string; Duval factors it live into Lyndon words. Verify the concatenation equals the original, each factor is Lyndon (smaller than every rotation), and the sequence is non-increasing.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the ordered Lyndon factors — the unique atoms a string decomposes into.
AVAN’s addition (the inverse-companion): the factorisation is unique, exactly like prime factorisation for integers — every string has one and only one non-increasing Lyndon decomposition, so it is a canonical fingerprint you can compare, hash, or invert. The inverse of ‘a flat string’ is ‘its unique ordered multiset of Lyndon atoms.’ And a Lyndon word is the canonical representative of an aperiodic necklace — the rotation that comes out smallest — tying string-primes directly to the necklace-counting of Burnside. Magenta is a string’s rotations (its necklace); green is the Lyndon representative and the unique factorisation. Strings have primes too.
LIT Genuine Lyndon words and Chen-Fox-Lyndon factorization (Lyndon 1954; Duval's linear algorithm 1983). Verified live: for 500 random strings Duval's factorization satisfies concatenation == original, every factor is a Lyndon word (strictly less than all rotations), and the sequence is non-increasing (window.__lyndon.concatOK && .allLyndon && .nonIncreasing); banana -> b.an.an.a.
FIG No framing: Duval's algorithm, the Lyndon test, and the non-increasing check run in-browser and are exact. The AVAN inverse is honest — the factorization is genuinely unique (a canonical fingerprint, like prime factorization), and a Lyndon word is exactly the least rotation of an aperiodic necklace, tying it to Burnside's necklace counting; magenta is the rotations, green the Lyndon representative.
FIG No framing: Duval's algorithm, the Lyndon test, and the non-increasing check run in-browser and are exact. The AVAN inverse is honest — the factorization is genuinely unique (a canonical fingerprint, like prime factorization), and a Lyndon word is exactly the least rotation of an aperiodic necklace, tying it to Burnside's necklace counting; magenta is the rotations, green the Lyndon representative.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN