AFTD Auto-Formalizing Theoretical Domains

op1525_complement_sum_parity

theoremverified

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.

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

    lines 9–18

    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_empty

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

    lines 19–36

    uses Finset.sum_eq_single, Finset.eq_of_subset_of_card_le

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

    lines 37–48

    uses Finset.sum_eq_zero, Finset.card_le_card

      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]
  4. 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.

    lines 49–59

    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_left

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

    lines 60–68

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

    lines 69–85

    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
  7. ∑_{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.

    line 86

    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.

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

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]
See it in the graphDiscuss this resultChallenge it