op1525_complement_sum_parity
Let f assign integers to subsets of a finite set, with f supported on subsets of size k. If every sum of f over the supersets of each subset of size less than k vanishes, then for every S the sum of f over subsets of the complement of S equals (-1)^k times the sum over subsets of S.
Statement
theorem op1525_complement_sum_parity {V : Type} [DecidableEq V] [Fintype V] (f : Finset V → ℤ) (k : ℕ) (hsupport : ∀ T, f T ≠ 0 → T.card = k) (hlower : ∀ R : Finset V, R.card < k → (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = 0) (S : Finset V) : (∑ T ∈ (Finset.univ \ S).powerset, f T) = (-1 : ℤ)^k * (∑ T ∈ S.powerset, f T)
- Source
- Inclusion-exclusion helper for the subset-deletion route to OP-1525, arXiv:2611.13901, Remark 4.11.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof expresses the sum of f(T) over subsets of the complement V \ S by writing the indicator that S and T are disjoint as an alternating sum over subsets R ⊆ S contained in T. Exchanging the order of summation converts the expression into ∑_{R ⊆ S} (-1)^|R| ∑_{T ⊇ R} f(T). For each R ⊆ S, the inner superset sum vanishes when |R| < k (by hypothesis) and when |R| > k (by support of f), while for |R| = k it isolates the single value f(R). Factoring out the resulting common factor of (-1)^k from the sum over subsets of S completes the identity.
For every subset T of V, the alternating sum ∑_{R ⊆ S, R ⊆ T} (-1)^|R| equals 1 if S and T are disjoint, and 0 otherwise.
Subsets R ⊆ S satisfying R ⊆ T are precisely the subsets of S ∩ T. By Finset.sum_powerset_neg_one_pow_card, the alternating sum of (-1)^|R| over all subsets of S ∩ T is 1 if S ∩ T = ∅ (that is, S and T are disjoint) and 0 otherwise.
uses
Finset.sum_filter,Finset.mem_filter,Finset.mem_powerset,Finset.subset_inter_iff,Finset.sum_powerset_neg_one_pow_card,Finset.disjoint_iff_inter_eq_emptyclassical have hcancel (T : Finset V) : (∑ R ∈ S.powerset, if R ⊆ T then (-1 : ℤ)^R.card else 0) = if Disjoint S T then 1 else 0 := by rw [← Finset.sum_filter] have heq : S.powerset.filter (fun R => R ⊆ T) = (S ∩ T).powerset := by ext R simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_inter_iff] rw [heq, Finset.sum_powerset_neg_one_pow_card] simp [Finset.disjoint_iff_inter_eq_empty]
For any subset R of V with |R| = k, the sum of f(T) over all supersets T ⊇ R equals f(R).
Using Finset.sum_eq_single, we isolate the summand at T = R. For any other superset T ⊇ R with T ≠ R, if f(T) were nonzero, the support hypothesis would require |T| = k = |R|, forcing R = T by Finset.eq_of_subset_of_card_le and contradicting T ≠ R. Thus all terms for T ≠ R vanish, leaving f(R).
uses
Finset.sum_eq_single,Finset.eq_of_subset_of_card_lehave htop (R : Finset V) (hR : R.card = k) : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = f R := by have hsum := Finset.sum_eq_single R (s := (Finset.univ : Finset V).powerset) (f := fun T => if R ⊆ T then f T else 0) have hresult : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = (if R ⊆ R then f R else 0) := by apply hsum · intro T _ hne by_cases hRT : R ⊆ T · have hft : f T = 0 := by by_contra hn have hc := hsupport T hn have he : R = T := Finset.eq_of_subset_of_card_le hRT (by omega) exact hne he.symm simp [hft] · simp [hRT] · simp simpa using hresult
For any subset R of V with |R| > k, the sum of f(T) over all supersets T ⊇ R equals 0.
By Finset.sum_eq_zero, it suffices to show each term vanishes. For any superset T ⊇ R, cardinality monotonicity (Finset.card_le_card) gives |T| ≥ |R| > k. Since f is supported on subsets of size k, f(T) must be 0 for every superset T.
uses
Finset.sum_eq_zero,Finset.card_le_cardhave hlarge (R : Finset V) (hR : k < R.card) : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = 0 := by apply Finset.sum_eq_zero intro T _ by_cases hRT : R ⊆ T · have hf : f T = 0 := by by_contra hn have hc := hsupport T hn have hle := Finset.card_le_card hRT omega simp [hf] · simp [hRT]
The sum of f(T) over subsets T of the complement V \ S equals ∑_{T ⊆ V} f(T) ∑_{R ⊆ S, R ⊆ T} (-1)^|R|.
Substituting the disjointness identity for the inner sum restricts the sum over all T ⊆ V to those disjoint from S. Disjointness from S is equivalent to being contained in the complement V \ S, so the index sets coincide.
uses
Finset.sum_filter,mul_ite,mul_one,mul_zero,Finset.sum_congr,Finset.mem_filter,Finset.mem_powerset,Finset.subset_univ,true_and,Finset.subset_sdiff,Finset.disjoint_leftcalc (∑ T ∈ (Finset.univ \ S).powerset, f T) = ∑ T ∈ (Finset.univ : Finset V).powerset, f T * (∑ R ∈ S.powerset, if R ⊆ T then (-1 : ℤ)^R.card else 0) := by simp_rw [hcancel] simp only [mul_ite, mul_one, mul_zero, ← Finset.sum_filter] apply Finset.sum_congr ?_ (fun _ _ => rfl) ext T simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and] simp [Finset.subset_sdiff, Finset.disjoint_left] aesop
Interchanging the order of summation expresses the total sum as ∑_{R ⊆ S} (-1)^|R| ∑_{T ⊇ R} f(T).
We distribute f(T) into the inner sum over R using Finset.mul_sum, swap the double summation order with Finset.sum_comm, and commute the multiplication f(T) * (-1)^|R| to (-1)^|R| * f(T).
uses
Finset.mul_sum,Finset.sum_comm,Finset.sum_congr,mul_comm_ = ∑ R ∈ S.powerset, (-1 : ℤ)^R.card * (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) := by simp_rw [Finset.mul_sum] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro R _ apply Finset.sum_congr rfl intro T _ split_ifs <;> simp [mul_comm]The sum simplifies to ∑_{R ⊆ S} (-1)^k f(R).
For each R ⊆ S, we split into three cases using lt_trichotomy on |R| and k. When |R| < k, the inner superset sum vanishes by the lower-size hypothesis hlower and f(R) = 0 by the support hypothesis. When |R| = k, the superset sum is f(R) and (-1)^|R| = (-1)^k. When |R| > k, the superset sum vanishes by the large-size lemma and f(R) = 0. In all cases, the summand is (-1)^k f(R).
uses
Finset.sum_congr,lt_trichotomy_ = ∑ R ∈ S.powerset, (-1 : ℤ)^k * f R := by apply Finset.sum_congr rfl intro R _ rcases lt_trichotomy R.card k with h | h | h · have hf : f R = 0 := by by_contra hn have hc := hsupport R hn omega rw [hlower R h, hf] simp · rw [htop R h, h] · have hf : f R = 0 := by by_contra hn have hc := hsupport R hn omega rw [hlarge R h, hf] simp
∑_{R ⊆ S} (-1)^k f(R) = (-1)^k ∑_{T ⊆ S} f(T).
Factoring out the constant factor (-1)^k from the finite sum over subsets of S via Finset.mul_sum concludes the proof.
uses
Finset.mul_sum_ = (-1 : ℤ)^k * (∑ T ∈ S.powerset, f T) := by rw [Finset.mul_sum]
Finset.sum_filter- A sum over elements satisfying a predicate equals the sum over all elements with an if-then-else condition.
Finset.mem_filter- An element belongs to the filtered sub-finset if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_powerset- A finset belongs to the powerset of another finset if and only if it is a subset of it.
Finset.subset_inter_iff- A finset is a subset of the intersection of two finsets if and only if it is a subset of each.
Finset.sum_powerset_neg_one_pow_card- The alternating sum of (-1)^|m| over all subsets m of a finite set x is 1 if x is empty and 0 otherwise.
Finset.disjoint_iff_inter_eq_empty- Two finite sets are disjoint if and only if their intersection is empty.
Finset.sum_eq_single- If all terms in a finite sum vanish except possibly at a single index a, the sum equals the term at a.
Finset.eq_of_subset_of_card_le- If s is a subset of t and the cardinality of t is at most the cardinality of s, then s = t.
Finset.sum_eq_zero- If every term in a finite sum is zero, the sum is zero.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
mul_ite- Multiplication distributes over an if-then-else condition on the right.
mul_one- Multiplying any element by 1 yields the element itself.
mul_zero- Multiplying any element by 0 yields 0.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on all elements.
Finset.subset_univ- Every subset of a finite type is a subset of the universal finset.
true_and- Conjunction of True with any proposition p simplifies to p.
Finset.subset_sdiff- A finset s is a subset of t \ u if and only if s is a subset of t and disjoint from u.
Finset.disjoint_left- Two finsets s and t are disjoint if and only if no element of s belongs to t.
Finset.mul_sum- A scalar factor distributes over a finite sum.
Finset.sum_comm- The order of summation in a finite double sum can be swapped.
mul_comm- Multiplication is commutative.
lt_trichotomy- For any two elements a, b in a linearly ordered type, exactly one of a < b, a = b, or b < a holds.
- At line 59, the equivalence between (∀ a ∈ T, a ∉ S) and (∀ a ∈ S, a ∉ T) (symmetry of disjointness) is discharged automatically by `aesop`.
- Linear arithmetic over ℕ (`omega`) is used in lines 31, 46, 76, and 83 to automatically compare set cardinalities against k.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op1525_complement_sum_parity {V : Type} [DecidableEq V] [Fintype V] (f : Finset V → ℤ) (k : ℕ) (hsupport : ∀ T, f T ≠ 0 → T.card = k) (hlower : ∀ R : Finset V, R.card < k → (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = 0) (S : Finset V) : (∑ T ∈ (Finset.univ \ S).powerset, f T) = (-1 : ℤ)^k * (∑ T ∈ S.powerset, f T) := by classical have hcancel (T : Finset V) : (∑ R ∈ S.powerset, if R ⊆ T then (-1 : ℤ)^R.card else 0) = if Disjoint S T then 1 else 0 := by rw [← Finset.sum_filter] have heq : S.powerset.filter (fun R => R ⊆ T) = (S ∩ T).powerset := by ext R simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_inter_iff] rw [heq, Finset.sum_powerset_neg_one_pow_card] simp [Finset.disjoint_iff_inter_eq_empty] have htop (R : Finset V) (hR : R.card = k) : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = f R := by have hsum := Finset.sum_eq_single R (s := (Finset.univ : Finset V).powerset) (f := fun T => if R ⊆ T then f T else 0) have hresult : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = (if R ⊆ R then f R else 0) := by apply hsum · intro T _ hne by_cases hRT : R ⊆ T · have hft : f T = 0 := by by_contra hn have hc := hsupport T hn have he : R = T := Finset.eq_of_subset_of_card_le hRT (by omega) exact hne he.symm simp [hft] · simp [hRT] · simp simpa using hresult have hlarge (R : Finset V) (hR : k < R.card) : (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) = 0 := by apply Finset.sum_eq_zero intro T _ by_cases hRT : R ⊆ T · have hf : f T = 0 := by by_contra hn have hc := hsupport T hn have hle := Finset.card_le_card hRT omega simp [hf] · simp [hRT] calc (∑ T ∈ (Finset.univ \ S).powerset, f T) = ∑ T ∈ (Finset.univ : Finset V).powerset, f T * (∑ R ∈ S.powerset, if R ⊆ T then (-1 : ℤ)^R.card else 0) := by simp_rw [hcancel] simp only [mul_ite, mul_one, mul_zero, ← Finset.sum_filter] apply Finset.sum_congr ?_ (fun _ _ => rfl) ext T simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and] simp [Finset.subset_sdiff, Finset.disjoint_left] aesop _ = ∑ R ∈ S.powerset, (-1 : ℤ)^R.card * (∑ T ∈ (Finset.univ : Finset V).powerset, if R ⊆ T then f T else 0) := by simp_rw [Finset.mul_sum] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro R _ apply Finset.sum_congr rfl intro T _ split_ifs <;> simp [mul_comm] _ = ∑ R ∈ S.powerset, (-1 : ℤ)^k * f R := by apply Finset.sum_congr rfl intro R _ rcases lt_trichotomy R.card k with h | h | h · have hf : f R = 0 := by by_contra hn have hc := hsupport R hn omega rw [hlower R h, hf] simp · rw [htop R h, h] · have hf : f R = 0 := by by_contra hn have hc := hsupport R hn omega rw [hlarge R h, hf] simp _ = (-1 : ℤ)^k * (∑ T ∈ S.powerset, f T) := by rw [Finset.mul_sum]