Subset Zeta and Möbius Transform
Accumulate subset sums and reverse them with inclusion–exclusion signs.
Free theory articleAccumulate subset sums and reverse them with inclusion–exclusion signs.
Concept & interpretation
The subset Zeta transform evaluates sums over all subsets of a finite set efficiently. If we have a function defined on the subsets, it computes Z(S) = sum_{T subset S} f(T). The inverse, the Möbius transform, recovers the original values via inclusion-exclusion: M(S) = sum (-1)^(|S|-|T|) f(T).
Experiment: Applying the transforms
Open the Subset Zeta and Möbius Transform module.
- Select Array as "Positive", Transform as "Zeta", Stage as 3, and Probe mask as 7. Observe the Stage vector is exactly 1,3,1,6,2,4,4,10 and Probe value is 10. Full round trip error is 0.
- Change Transform to "Mobius" and select Array to "Signed". The Mobius transform uses subtraction instead of addition. Observe the Stage vector at Stage 3 becomes -1,3,-2,4,-1,0,4,-4, and Probe value is -4.
- Set Transform back to "Zeta" and change Stage step-by-step from 0 to 1, 2, and 3. The visualization highlights the edges (additions) along the boolean lattice being processed in each stage.
- Note the Full round trip error. It remains 0 across all transforms because the Zeta and Mobius transforms are exact inverses of each other mathematically.