A dynamic program for the zeta transform, presented as a recurrence plus memoization; the Möbius version is almost identical 28:29, 29:06.

The auxiliary function

  • Ground set is {1, …, n}. Define G(i, S) = Σ_{R ⊆ S, S_i = R_i} f(R) 29:56.
  • Notation: S_i := S ∩ {i+1, …, n} — the part of S above index i 30:30.
  • So G(i, S) sums f(R) over subsets R ⊆ S that agree with S on all coordinates above i, leaving coordinates 1..i free.
  • f̂(S) = G(n, S): at i = n the set {n+1,…,n} is empty, so the constraint ∅ = ∅ is always true and the sum runs over all R ⊆ S 31:10.

The recurrence

  • Base case i = 0: S_0 = S, so the constraint forces R = S, giving G(0, S) = f(S) 31:40, 32:24.
  • For i > 0: G(i, S) = G(i−1, S) + [i ∈ S] · G(i−1, S − i) 32:43.
flowchart TD
    S0["G(0, S) = f(S)"] --> Si["G(i, S)"]
    Si --> R1["G(i−1, S)<br/>(subsets R that contain i, when i ∈ S)"]
    Si --> R2["[i ∈ S] · G(i−1, S − i)<br/>(subsets R that omit i)"]
    Si --> Fin["f̂(S) = G(n, S)"]

Cost

  • States: 2^n choices of S × n choices of i 33:21.
  • Space: n · 2^n · (space for one ring element) — the sums are at most exponentially large so a ring element fits in about n bits, though it depends on the ring f maps into 33:21, 33:44.
  • Time: each state needs O(1) recursive calls and O(1) arithmetic operations, so time is proportional to space 34:03.
  • Conclusion: all f̂(S) in O*(2^n) time and space 34:23.

Correctness proof

Split the sum by whether i ∈ R 35:02, 36:00:

G(i,S) = Σ_{R ⊆ S, i ∈ R} [S_i = R_i] f(R) + Σ_{R ⊆ S, i ∉ R} [S_i = R_i] f(R)

  • Case 1 — i ∉ S 36:00:
    • R ⊆ S forces i ∉ R, so the first sum is empty and vanishes 36:35, 37:04.
    • Since neither S nor R contains i, S_{i−1} = S_i and R_{i−1} = R_i, so the second sum is exactly G(i−1, S) 36:35, 37:04.
    • The indicator [i ∈ S] correctly kills the extra term 37:04.
  • Case 2 — i ∈ S 37:36:
    • If i ∈ R too, then S_{i−1} = R_{i−1}, so the first sum is G(i−1, S) 37:36, 38:31, 39:04.
    • If i ∉ R, then agreeing with S from i+1 on is the same as agreeing with S − i from i on, giving exactly G(i−1, S − i) 39:04, 39:52, 40:20.

Bottom line

  • k-colorability is decidable in roughly 2^n time, up to poly(n) factors 40:20.