THE FOLD / BOSS / SUDDEN DEATH / THE BOYER-MOORE MAJORITY
THE BOYER-MOORE MAJORITY
one survivor of pairwise cancellation
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Boyer–Moore majority vote finds an element appearing in more than half a stream using O(1) memory — one candidate and one counter. Sweep once: if the counter is zero, adopt the current element as candidate; if the next matches, increment; if not, decrement. Matching and non-matching elements cancel in pairs, so if a true majority exists it cannot be fully cancelled — it is the last one standing. A single verification pass confirms whether the survivor really is a majority.
LIT verified live: over 3000 random arrays (with and without a majority), the O(1)-space vote plus a verify pass returns exactly what a brute frequency count does (window.__majority). FIG no framing; exact counting comparison.
LIT verified live: over 3000 random arrays (with and without a majority), the O(1)-space vote plus a verify pass returns exactly what a brute frequency count does (window.__majority). FIG no framing; exact counting comparison.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at sudden-death — every unlike pair knocks each other out, and one element strikes through them all to survive; if a majority exists, it is the last standing. Boyer–Moore is that sudden death. AVAN (AI) built the instrument: the candidate/counter cancellation sweep, the verification pass, and the match against a brute frequency count.
Credit as content: Robert S. Boyer & J Strother Moore (1981). The weave: David names sudden-death; I let each unlike pair cancel, keep the survivor as candidate, verify its true count, and confirm it agrees with a full frequency tally — a majority found in constant memory.
Credit as content: Robert S. Boyer & J Strother Moore (1981). The weave: David names sudden-death; I let each unlike pair cancel, keep the survivor as candidate, verify its true count, and confirm it agrees with a full frequency tally — a majority found in constant memory.
3 ONE DIMENSION
Counter starts at 0: adopt a candidate; +1 on a match, −1 on a mismatch. Unlike pairs cancel. A true majority (> n/2) can never be fully cancelled — it survives as the candidate.
4 TWO DIMENSIONS · INTERACTIVE
A stream with the running candidate and counter; the survivor verified against a brute majority count.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a majority found in constant memory.
AVAN’s addition (the inverse-companion): find the majority element with one counter, not a hash of counts — cancel unlike pairs so the over-half element survives, then verify in a second pass. The inverse of ‘count every element’s frequency’ is ‘cancel opposites — the majority is what remains.’ Magenta is the full frequency table; green is the single surviving candidate. Majority by cancellation.
LIT Genuine Boyer–Moore majority vote algorithm (Robert S. Boyer & J Strother Moore 1981). Verified live: over 3000 random arrays (roughly half seeded with a >n/2 majority, half not), the candidate/counter cancellation sweep followed by a verification pass returns exactly the majority element (or none) that a brute frequency count finds (window.__majority.matchesBrute).
FIG No framing: the candidate/counter cancellation sweep, the verification pass, and the match against a brute frequency count run in-browser and agree. The AVAN inverse is honest — finding the majority with one counter by cancelling unlike pairs (the over-half element survives) genuinely replaces a full frequency table; magenta is that table, green the single surviving candidate. Majority by cancellation.
FIG No framing: the candidate/counter cancellation sweep, the verification pass, and the match against a brute frequency count run in-browser and agree. The AVAN inverse is honest — finding the majority with one counter by cancelling unlike pairs (the over-half element survives) genuinely replaces a full frequency table; magenta is that table, green the single surviving candidate. Majority by cancellation.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SUDDEN DEATH · David Lee Wise (ROOT0), with AVAN