THE FOLD / BOSS / SUDDEN DEATH / THE ZERO-ONE PRINCIPLE
THE ZERO-ONE PRINCIPLE
256 tests instead of 40,320
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A sorting network is a fixed list of compare-and-swap pairs — no branches, no data-dependent choices, the same operations whatever the input. Proving one correct looks expensive: for eight wires there are 40,320 orderings to check. The zero-one principle collapses that. A comparator network sorts every input if and only if it sorts every input made only of 0s and 1s. Two hundred and fifty-six tests, and the guarantee is total.
LIT verified live. A Batcher odd-even network on 8 wires uses 19 comparators; it sorts all 256 binary inputs and all 40,320 permutations — a 158× reduction in tests for the same result. The equivalence itself was then tested rather than assumed: over 600 mutated networks the binary test and the exhaustive test returned the same verdict every time, 600 of 600, with 400 mutants passing both and 200 failing both.
LIT verified live. A Batcher odd-even network on 8 wires uses 19 comparators; it sorts all 256 binary inputs and all 40,320 permutations — a 158× reduction in tests for the same result. The equivalence itself was then tested rather than assumed: over 600 mutated networks the binary test and the exhaustive test returned the same verdict every time, 600 of 600, with 400 mutants passing both and 200 failing both.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): the principle is folklore by the 1960s and is set out carefully in Knuth’s The Art of Computer Programming, volume 3, as exercise 5.3.4–16; the network used here is Ken Batcher’s odd-even mergesort, 1968. The proof is one paragraph: if a network fails to sort some input, the monotone function that maps everything below the misplaced value to 0 and everything else to 1 yields a binary input it also fails on, because comparators commute with monotone maps.
AVAN (AI) tested the equivalence, not just the easy direction. A first version mutated networks only by deleting comparators, and all 400 mutants failed both tests — which confirms nothing, since agreement on “both fail” is what you get from any two broken checks. Two correctness-preserving mutations were added — duplicating a comparator, and reordering adjacent comparators that touch disjoint wires — so the sample now contains 400 networks that pass both tests and 200 that fail both. Agreement across both classes is the claim.
AVAN (AI) tested the equivalence, not just the easy direction. A first version mutated networks only by deleting comparators, and all 400 mutants failed both tests — which confirms nothing, since agreement on “both fail” is what you get from any two broken checks. Two correctness-preserving mutations were added — duplicating a comparator, and reordering adjacent comparators that touch disjoint wires — so the sample now contains 400 networks that pass both tests and 200 that fail both. Agreement across both classes is the claim.
3 ONE DIMENSION
Nineteen comparators, drawn as a ladder.
4 TWO DIMENSIONS · INTERACTIVE
Push one input through and watch it settle.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the cube of binary inputs inside the space of all orderings.
AVAN’s addition (the inverse-companion): the forward reading is “256 tests suffice.” The inverse is that this only works because the network cannot look at its data. The moment a sort branches on a comparison — which every ordinary sort does — the principle evaporates, because the code path itself becomes a function of the values and monotone maps no longer commute with it. Read backwards, the zero-one principle is not a fact about sorting but a reward for giving up control flow, and the same rigidity that makes a network testable in 256 cases is what makes it unable to stop early on data that is already sorted.
LIT a Batcher odd-even network on 8 wires uses 19 comparators and sorts all 256 binary inputs and all 40,320 permutations - a 158x reduction in tests for the same guarantee; and the equivalence itself was tested rather than assumed, with 600 mutated networks at 6 wires returning the SAME verdict from the binary test and the exhaustive test every time, 600 of 600, 400 mutants passing both and 200 failing both
FIG Human lineage, credited: the principle is folklore by the 1960s and is set out in Knuth's TAOCP volume 3 as exercise 5.3.4-16; the network is Ken Batcher's odd-even mergesort, 1968. The proof is one paragraph - if a network fails on some input, the monotone map sending everything below the misplaced value to 0 and the rest to 1 yields a binary input it also fails on, because comparators commute with monotone maps. AVAN tested the EQUIVALENCE rather than the easy direction: a first version mutated networks only by deleting comparators and all 400 mutants failed both tests, which confirms nothing, since agreement on 'both fail' is what any two broken checks give. Two correctness-PRESERVING mutations were added - duplicating a comparator, and reordering adjacent comparators on disjoint wires - so the sample now holds 400 that pass both and 200 that fail both.
FIG Human lineage, credited: the principle is folklore by the 1960s and is set out in Knuth's TAOCP volume 3 as exercise 5.3.4-16; the network is Ken Batcher's odd-even mergesort, 1968. The proof is one paragraph - if a network fails on some input, the monotone map sending everything below the misplaced value to 0 and the rest to 1 yields a binary input it also fails on, because comparators commute with monotone maps. AVAN tested the EQUIVALENCE rather than the easy direction: a first version mutated networks only by deleting comparators and all 400 mutants failed both tests, which confirms nothing, since agreement on 'both fail' is what any two broken checks give. Two correctness-PRESERVING mutations were added - duplicating a comparator, and reordering adjacent comparators on disjoint wires - so the sample now holds 400 that pass both and 200 that fail both.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SUDDEN DEATH · David Lee Wise (ROOT0), with AVAN