THE FOLD / GRIND / THE MAINFRAME / THE ZETA TRANSFORM
THE ZETA TRANSFORM
all subset-sums at once, invertible by Mobius
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The zeta transform (sum-over-subsets) computes, for every set S at once, the sum of a function f over all subsets of S — F[S] = ΣT⊆S f[T]. Done naively that is 3n work; the SOS dynamic program does it in n·2n by sweeping one bit at a time. Its exact inverse is the Möbius transform (subtract instead of add), which recovers f — the two are add/subtract mirrors, inclusion–exclusion made fast and invertible.
LIT verified live: over 300 random functions the SOS transform equals the brute subset-sum for every S, and the Möbius transform inverts it exactly (window.__zeta). FIG no framing; exact.
LIT verified live: over 300 random functions the SOS transform equals the brute subset-sum for every S, and the Möbius transform inverts it exactly (window.__zeta). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the heavy combinatorial DP a mainframe sweeps in one pass over all 2n subsets. The zeta transform is that sweep. AVAN (AI) built the instrument: the bitwise SOS accumulation, the Möbius inverse, the brute subset-sum cross-check.
Credit as content: the Möbius function over the subset lattice (Rota’s theory of Möbius inversion). The weave: David names the mainframe; I add each bit’s contribution in place to build all subset-sums at once, and subtract to invert exactly.
Credit as content: the Möbius function over the subset lattice (Rota’s theory of Möbius inversion). The weave: David names the mainframe; I add each bit’s contribution in place to build all subset-sums at once, and subtract to invert exactly.
3 ONE DIMENSION
Bit by bit: for bit i, add F[mask without i] into F[mask with i]. After n passes every F[S] holds the sum over all subsets of S — and subtracting instead of adding undoes it.
4 TWO DIMENSIONS · INTERACTIVE
A function over subsets of a small set; its zeta transform is shown against the brute subset-sum, and the Möbius transform recovers the original.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: all 2n subset-sums, built by a bitwise sweep.
AVAN’s addition (the inverse-companion): accumulate one bit at a time — for each of the n bits, add the value without that bit into the value with it, in place; n·2n work computes all subset-sums at once, and the Möbius transform (subtract instead of add) is its exact inverse. The inverse of ‘sum over each subset separately’ is ‘sweep bit by bit; the transform and its Möbius inverse are add/subtract mirrors.’ Magenta is the 3n naive subset-sums; green is the n·2n bitwise sweep. Inclusion–exclusion as a fast, invertible transform.
LIT Genuine sum-over-subsets / zeta-Mobius transform (Mobius inversion over the subset lattice). Verified live: the bitwise SOS accumulation equals a brute subset-sum for every subset, and the Mobius transform recovers the original function exactly, over 300 random functions on up to 5 elements (window.__zeta.subsetSum && .mobiusInverse).
FIG No framing: the bitwise SOS accumulation, the Mobius inverse, and the brute subset-sum cross-check run in-browser and agree exactly. The AVAN inverse is honest — adding each bit's contribution in place builds all 2^n subset-sums in n*2^n, and subtracting inverts exactly (add/subtract mirrors); magenta is the 3^n naive subset-sums, green the bitwise sweep. Inclusion-exclusion as a fast, invertible transform.
FIG No framing: the bitwise SOS accumulation, the Mobius inverse, and the brute subset-sum cross-check run in-browser and agree exactly. The AVAN inverse is honest — adding each bit's contribution in place builds all 2^n subset-sums in n*2^n, and subtracting inverts exactly (add/subtract mirrors); magenta is the 3^n naive subset-sums, green the bitwise sweep. Inclusion-exclusion as a fast, invertible transform.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MAINFRAME · David Lee Wise (ROOT0), with AVAN