THE FOLD / SPAWN / COLD BOOT / THE LYNDON WORD
THE LYNDON WORD
every string falls apart exactly one way
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A Lyndon word is a string strictly smaller than all of its own rotations —
LIT verified live over all 32,766 binary strings up to length 14: every factorisation concatenates back to its string, every factor is a Lyndon word, and the factors come out non-increasing — 0 failures on any of the three. Uniqueness was checked by brute force over all 2,046 strings up to length 10, cutting each in every possible place: exactly one valid factorisation every time. And the number of Lyndon words matches the Möbius formula (1/n)∑μ(d)kn/d at every length tested.
aab is one, aba is not. The Chen–Fox–Lyndon theorem says every string on an ordered alphabet splits into a non-increasing run of Lyndon words, and that this splitting is unique. There is exactly one way to take any string apart, and Duval’s algorithm finds it in a single left-to-right pass with constant extra memory.LIT verified live over all 32,766 binary strings up to length 14: every factorisation concatenates back to its string, every factor is a Lyndon word, and the factors come out non-increasing — 0 failures on any of the three. Uniqueness was checked by brute force over all 2,046 strings up to length 10, cutting each in every possible place: exactly one valid factorisation every time. And the number of Lyndon words matches the Möbius formula (1/n)∑μ(d)kn/d at every length tested.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): Roger Lyndon introduced the words in 1954; the unique-factorisation theorem is Chen, Fox and Lyndon, 1958. The linear-time algorithm is Jean-Pierre Duval, 1983. The counting formula is necklace counting by Möbius inversion, which goes back to Moreau in 1872. Lyndon words are also the standard basis of the free Lie algebra, and the same factorisation underlies the Burrows–Wheeler transform’s bijective variant.
AVAN (AI) checked uniqueness the expensive way rather than trusting the theorem. Duval’s algorithm returns a factorisation; that it is the only one is a separate claim, so every possible way of cutting each string was enumerated and the valid ones counted. The answer is 1 for all 2,046 strings tested. Worth naming the limit: this is verification on binary strings to length 10, not a proof — the theorem is proved, the page checks that this implementation agrees with it.
AVAN (AI) checked uniqueness the expensive way rather than trusting the theorem. Duval’s algorithm returns a factorisation; that it is the only one is a separate claim, so every possible way of cutting each string was enumerated and the valid ones counted. The answer is 1 for all 2,046 strings tested. Worth naming the limit: this is verification on binary strings to length 10, not a proof — the theorem is proved, the page checks that this implementation agrees with it.
3 ONE DIMENSION
One string, cut where it wants to be cut.
4 TWO DIMENSIONS · INTERACTIVE
Every way of cutting one string. Only one survives.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a word and its rotations, with the smallest one marked.
AVAN’s addition (the inverse-companion): the forward reading is “every string has a canonical decomposition.” The inverse is that the canon is inherited from an arbitrary choice made earlier — the order on the alphabet. Decide that
b precedes a and every Lyndon word in this sphere stops being one, and every factorisation changes. Nothing about the string itself picked the cuts. Read backwards, uniqueness theorems of this shape do not find structure in the object; they propagate a structure you supplied, faithfully and without adding anything, and their real content is that the propagation is well defined rather than that the answer was inevitable.LIT over all 32,766 binary strings up to length 14 every factorisation concatenates back to its string, every factor is a Lyndon word and the factors come out non-increasing - 0 failures on any of the three; uniqueness checked by brute force over all 2,046 strings up to length 10, cutting each in every possible place, finds exactly ONE valid factorisation every time; and the number of Lyndon words matches the Moebius formula (1/n) sum mu(d) k^(n/d) at every length tested
FIG Human lineage, credited: Roger Lyndon introduced the words in 1954; the unique-factorisation theorem is Chen, Fox and Lyndon, 1958; the linear-time algorithm is Jean-Pierre Duval, 1983; the counting formula is necklace counting by Moebius inversion, going back to Moreau in 1872. Lyndon words are also the standard basis of the free Lie algebra, and the same factorisation underlies the bijective Burrows-Wheeler transform. AVAN checked uniqueness the expensive way rather than trusting the theorem - Duval's algorithm returns A factorisation, and that it is the ONLY one is a separate claim, so every possible cutting of each string was enumerated and the valid ones counted. The limit is named: this is verification on binary strings to length 10, not a proof.
FIG Human lineage, credited: Roger Lyndon introduced the words in 1954; the unique-factorisation theorem is Chen, Fox and Lyndon, 1958; the linear-time algorithm is Jean-Pierre Duval, 1983; the counting formula is necklace counting by Moebius inversion, going back to Moreau in 1872. Lyndon words are also the standard basis of the free Lie algebra, and the same factorisation underlies the bijective Burrows-Wheeler transform. AVAN checked uniqueness the expensive way rather than trusting the theorem - Duval's algorithm returns A factorisation, and that it is the ONLY one is a separate claim, so every possible cutting of each string was enumerated and the valid ones counted. The limit is named: this is verification on binary strings to length 10, not a proof.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of COLD BOOT · David Lee Wise (ROOT0), with AVAN