THE FOLD / BOSS / THE RAID / THE ERDŐS–GINZBURG–ZIV
THE ERDŐS–GINZBURG–ZIV
any 2n−1 integers hide n that sum to zero mod n
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Erdős–Ginzburg–Ziv theorem is a zero-sum guarantee: among any 2n − 1 integers (repeats allowed), some n of them have a sum divisible by n. No matter how adversarially the numbers are chosen, a size-n subset summing to 0 mod n is always hiding inside. And the count is sharp: with only 2n − 2 integers it can fail — take n − 1 zeros and n − 1 ones, and any n of them sum to between 1 and n − 1, never 0. It is a founding result of zero-sum combinatorics.
LIT verified live: for thousands of random collections of 2n − 1 integers, a size-n zero-sum subset (mod n) is always found by a subset-sum dynamic program, and the (n−1)-zeros-plus-(n−1)-ones set of size 2n − 2 has none (window.__egz). FIG no framing; an exhaustive subset-sum search and the sharp counterexample.
LIT verified live: for thousands of random collections of 2n − 1 integers, a size-n zero-sum subset (mod n) is always found by a subset-sum dynamic program, and the (n−1)-zeros-plus-(n−1)-ones set of size 2n − 2 has none (window.__egz). FIG no framing; an exhaustive subset-sum search and the sharp counterexample.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-raid — however the enemy stacks 2n − 1 numbers, the raid always uncovers a party of exactly n whose sum vanishes mod n. That guaranteed find is the mechanic. AVAN (AI) built the instrument: the count-and-residue subset-sum dynamic program, the search for a size-n zero-sum subset, and the sharp 2n − 2 counterexample.
Credit as content: Paul Erdős, Abraham Ginzburg & Abraham Ziv (1961). The weave: David names the-raid; I track which residues mod n are reachable using exactly n of the given integers, confirm 0 is always reachable from 2n − 1 numbers, and show one number fewer can fail — the bound is exact.
Credit as content: Paul Erdős, Abraham Ginzburg & Abraham Ziv (1961). The weave: David names the-raid; I track which residues mod n are reachable using exactly n of the given integers, confirm 0 is always reachable from 2n − 1 numbers, and show one number fewer can fail — the bound is exact.
3 ONE DIMENSION
n = 3: any 5 integers contain 3 summing to a multiple of 3. E.g. 1, 4, 2, 6, 5 → 1 + 2 + 6 = 9. But 0, 0, 1, 1 (only 2n − 2 = 4) has no 3 summing to 0 mod 3.
4 TWO DIMENSIONS · INTERACTIVE
A pile of 2n − 1 integers and the size-n zero-sum subset found inside; the guarantee checked, the sharp case shown.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a zero-sum party always hiding in the pile.
AVAN’s addition (the inverse-companion): don’t choose numbers to make a zero-sum subset — note that with 2n − 1 of them you cannot avoid one. The inverse of ‘construct a subset summing to 0 mod n’ is ‘any 2n − 1 integers already contain one.’ Magenta is a hand-built zero-sum subset; green is the one forced to exist. Zero-sum, unavoidable.
LIT Genuine Erdős–Ginzburg–Ziv theorem (Paul Erdős, Abraham Ginzburg & Abraham Ziv, 1961). Verified live: for 4000 random collections of 2n−1 integers, a size-n subset summing to 0 mod n is always found by a count-and-residue subset-sum dynamic program (window.__egz.exists), and the sharp set of 2n−2 integers (n−1 zeros plus n−1 ones) has no such subset (window.__egz.sharp).
FIG No framing: the count-and-residue subset-sum DP, the size-n zero-sum search, and the sharp 2n−2 counterexample all run in-browser with exact arithmetic. The AVAN inverse is honest — noting that 2n−1 integers cannot avoid a zero-sum n-subset (rather than constructing one) is the real content, and 2n−2 shows the bound is exact; magenta is a hand-built zero-sum subset, green the one forced to exist. Zero-sum, unavoidable.
FIG No framing: the count-and-residue subset-sum DP, the size-n zero-sum search, and the sharp 2n−2 counterexample all run in-browser with exact arithmetic. The AVAN inverse is honest — noting that 2n−1 integers cannot avoid a zero-sum n-subset (rather than constructing one) is the real content, and 2n−2 shows the bound is exact; magenta is a hand-built zero-sum subset, green the one forced to exist. Zero-sum, unavoidable.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN