Lemma 3.3 — Möbius inversion on the subset lattice
ProvedMinBisectFPT.lemma_3_3graph-algorithmsminimum-bisectionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexitytree-decompositions
Let be a finite set, an abelian group, and . Then holds for every if and only if
holds for every .
Differences from the source:
- generalization: a truncated polynomial ring → any abelian group; reason: a truncated polynomial ring is an abelian group under addition
Preamble
import Mathlib open scoped Classical
Formal statement
namespace MinBisectFPT
/-- **Lemma 3.3 (Möbius inversion).** Anand, Kipouridis, Węgrzycki, STOC 2027 submission (manuscript sha256 8db80a52…), Lemma 3.3, p.10.
**Formalization Note** `R` is any abelian group, of which a truncated polynomial ring is an instance. -/
theorem lemma_3_3 {β R : Type} [Fintype β] [DecidableEq β] [AddCommGroup R]
(g h : Finset β → R) :
(∀ W, g W = ∑ U ∈ W.powerset, h U) ↔
∀ U, h U = ∑ W ∈ U.powerset, ((-1 : ℤ) ^ (U \ W).card) • g W := by sorry
end MinBisectFPT
Source
Anand, Kipouridis, Węgrzycki, Counting over Unbreakable Decompositions, STOC 2027 submission (manuscript sha256 8db80a52…), Lemma 3.3, p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.