THE FOLD / RESPAWN / THE CONTINUE / THE TODD-COXETER
THE TODD-COXETER
enumerate the cosets and the index falls out
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Give it generators, relations and a subgroup, and it fills in a table until the table closes on itself. The number of surviving rows is the index of the subgroup — so for the trivial subgroup it is the order of the group. A structural fact about an abstract group, produced by bookkeeping.
LIT verified live. The symmetric group on three letters enumerates to 6, the Klein four-group to 4, and the two-element cyclic group to 2. Run over a subgroup of order 2 instead of the trivial one, S₃ enumerates to 3 — which is 6/2, Lagrange’s theorem arriving as a row count rather than a proof.
LIT verified live. The symmetric group on three letters enumerates to 6, the Klein four-group to 4, and the two-element cyclic group to 2. Run over a subgroup of order 2 instead of the trivial one, S₃ enumerates to 3 — which is 6/2, Lagrange’s theorem arriving as a row count rather than a proof.
2 HOW IT WAS WEAVED · AI + HUMAN
John Todd and H.S.M. Coxeter published coset enumeration in 1936, as a hand procedure. It is one of the oldest algorithms in computational algebra and still the standard method — a table you fill in, where the difficulty is entirely in handling coincidences: discovering that two rows you had been treating as different are the same coset.
AVAN (AI) got the coincidence handling wrong on the first attempt and the gates caught it. A flat rewrite of references gave S₃ as 8 and the Klein group as 6 — both too large, because merging two cosets can force further merges that a single pass never discovers. The fix is a union-find over cosets with a queue, so a coincidence can cascade. That is not an implementation detail; it is the whole algorithm, and the naive version fails quietly with plausible-looking numbers.
AVAN (AI) got the coincidence handling wrong on the first attempt and the gates caught it. A flat rewrite of references gave S₃ as 8 and the Klein group as 6 — both too large, because merging two cosets can force further merges that a single pass never discovers. The fix is a union-find over cosets with a queue, so a coincidence can cascade. That is not an implementation detail; it is the whole algorithm, and the naive version fails quietly with plausible-looking numbers.
3 ONE DIMENSION
Four enumerations, and what each row count means.
4 TWO DIMENSIONS · INTERACTIVE
Change the presentation and watch the table close.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a table closing into a finite ring.
AVAN’s addition (the inverse-companion): the forward reading is “the table closes and gives you the index.” The inverse is that nothing tells you it will. A finitely presented group can be infinite, and then the enumeration runs forever, defining cosets and never closing — and the word problem for groups is undecidable, so no test can sort the two cases in advance. Read backwards, this is a procedure that answers correctly whenever it answers at all, which is semi-decidable: a running enumeration and a hung one are indistinguishable from outside, and the only honest report while it runs is that it is still running.
LIT the symmetric group on three letters enumerates to 6, the Klein four-group to 4 and the two-element cyclic group to 2; run over a subgroup of order 2 instead of the trivial one, S3 enumerates to 3 - which is 6/2, Lagrange's theorem arriving as a row count rather than a proof
FIG John Todd and H.S.M. Coxeter published coset enumeration in 1936, as a hand procedure. It is one of the oldest algorithms in computational algebra and still the standard method, with the difficulty entirely in handling COINCIDENCES - discovering that two rows treated as different are the same coset. AVAN got the coincidence handling wrong on the first attempt and the gates caught it: a flat rewrite of references gave S3 as 8 and the Klein group as 6, both too large, because merging two cosets can force further merges a single pass never discovers. The fix is a union-find with a QUEUE so a coincidence can cascade - and the naive version fails quietly with plausible-looking numbers.
FIG John Todd and H.S.M. Coxeter published coset enumeration in 1936, as a hand procedure. It is one of the oldest algorithms in computational algebra and still the standard method, with the difficulty entirely in handling COINCIDENCES - discovering that two rows treated as different are the same coset. AVAN got the coincidence handling wrong on the first attempt and the gates caught it: a flat rewrite of references gave S3 as 8 and the Klein group as 6, both too large, because merging two cosets can force further merges a single pass never discovers. The fix is a union-find with a QUEUE so a coincidence can cascade - and the naive version fails quietly with plausible-looking numbers.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CONTINUE · David Lee Wise (ROOT0), with AVAN