Subset Zeta and Möbius Transform

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).

A naive computation would check every pair of subsets, taking O(4^N) or O(3^N) time. The fast transform stages the updates bit by bit, taking only O(N 2^N) time. This is analogous to the Fast Fourier Transform, but operating over the Boolean lattice.

Worked example: Positive array, Stage 3 Zeta

Suppose our universe has 3 elements (masks 0 to 7). Let the original function values be the "Positive" array: f = [1, 2, 0, 3, 1, 0, 2, 1]. We want to compute the full Zeta transform (stage 3). We process the 3 bits sequentially.

Stage 0: Initial values. f = [1, 2, 0, 3, 1, 0, 2, 1]
Stage 1 (bit 0): We add f[mask without bit 0] to f[mask with bit 0].
- f[1] += f[0] = 2 + 1 = 3
- f[3] += f[2] = 3 + 0 = 3
- f[5] += f[4] = 0 + 1 = 1
- f[7] += f[6] = 1 + 2 = 3
After Stage 1, f = [1, 3, 0, 3, 1, 1, 2, 3].
Stage 2 (bit 1): We add f[mask without bit 1] to f[mask with bit 1].
- f[2] += f[0] = 0 + 1 = 1
- f[3] += f[1] = 3 + 3 = 6
- f[6] += f[4] = 2 + 1 = 3
- f[7] += f[5] = 3 + 1 = 4
After Stage 2, f = [1, 3, 1, 6, 1, 1, 3, 4].
Stage 3 (bit 2): We add f[mask without bit 2] to f[mask with bit 2].
- f[4] += f[0] = 1 + 1 = 2
- f[5] += f[1] = 1 + 3 = 4
- f[6] += f[2] = 3 + 1 = 4
- f[7] += f[3] = 4 + 6 = 10
After Stage 3, f = [1, 3, 1, 6, 2, 4, 4, 10].

The final value at probe mask 7 (binary 111) is Z(7) = 10. This matches the sum of all elements in the original array, because 7 contains all subsets!

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.

Limitations and characteristics

The fast transform executes in O(N 2^N) additions or subtractions, which is optimal but still scales exponentially with N. In practice, this restricts N to around 20-25 bits for real-time interactivity. The memory footprint also scales as O(2^N).

Because the operations are purely additions and subtractions, exact integers do not suffer from precision loss. If floating point values were used, algebraic zeros might have a small residual error bounded around 1e-11 depending on the magnitude of the accumulations.

This transform operates strictly on the subset lattice, which is distinct from the Fast Walsh-Hadamard Transform (FWHT) that uses XOR Fourier signs.

References

The algorithm and bound are detailed in foundational computational theory papers.

Fast Zeta Transform. A detailed theoretical treatment of fast algorithms for Möbius inversion and Zeta transforms on various lattices, establishing the O(N 2^N) bound.

Subset Zeta and Möbius Transform