AFTD Auto-Formalizing Theoretical Domains

op_98_sum_conflict_neighborhood_weight

theoremverified

The sum of conflict neighborhood weights over a packing O equals the weighted sum of conflict degrees in O over A: ∑_{o ∈ O} weight(N(A, {o})) = ∑_{a ∈ A} weight(a) * |{o ∈ O : ¬ Disjoint a o}|.

Statement

theorem op_98_sum_conflict_neighborhood_weight {α : Type*} [DecidableEq α] {k : ℕ}
    (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α)) :
    ∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o}) =
    ∑ a ∈ A, inst.weight a * (O.filter (fun o => ¬ Disjoint a o)).card
Source
step towards op_98_objective_switching_weighted_four_set_packing
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
  • conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…
  • packing_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear weight packing_weight inst A of a…
Used by 1
  • op_98_four_approximationEvery packing O satisfies packing_weight inst O ≤ 4 * packing_weight inst A under square local optimality with respect to 4-exchanges.

The proof, explained

The proof is a double counting argument that exchanges the order of summation. First, the sum of conflict neighborhood weights over o ∈ O is rewritten as a double sum over o ∈ O and a ∈ A of the weight of a conditioned on a and o conflicting (not being disjoint). Interchanging the order of summation groups the terms by each a ∈ A, where the inner sum over o ∈ O simply counts the number of elements in O conflicting with a, multiplied by the weight of a.

  1. The sum of conflict neighborhood weights over O is expressed as the double sum ∑ o ∈ O, ∑ a ∈ A, if ¬ Disjoint a o then inst.weight a else 0.

    We establish this auxiliary identity (h1) by showing equality of the summands for each o ∈ O via Finset.sum_congr. By definition, the packing weight of the conflict neighborhood of {o} sums inst.weight over all a ∈ A that are not disjoint from some element of {o}. Rewriting this filtered sum as an indicator sum over all a ∈ A using Finset.sum_filter, the condition (∃ x ∈ {o}, ¬ Disjoint a x) simplifies to ¬ Disjoint a o because {o} is a singleton.

    lines 6–14

    uses Finset.sum_congr, Finset.sum_filter

      have h1 : (∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o})) =
          ∑ o ∈ O, ∑ a ∈ A, if ¬ Disjoint a o then inst.weight a else 0 := by
        apply Finset.sum_congr rfl
        intro o ho
        simp only [packing_weight, conflict_neighborhood]
        rw [Finset.sum_filter]
        apply Finset.sum_congr rfl
        intro a ha
        simp
  2. The order of summation is interchanged, yielding ∑ a ∈ A, ∑ o ∈ O, if ¬ Disjoint a o then inst.weight a else 0.

    Rewriting the left-hand side with h1 replaces it with the double sum over o ∈ O and a ∈ A. Applying Finset.sum_comm swaps the outer and inner sums so that the outer sum runs over a ∈ A and the inner sum runs over o ∈ O.

    line 15

    uses Finset.sum_comm

      rw [h1, Finset.sum_comm]
  3. For each a ∈ A, the inner sum over o ∈ O evaluates to inst.weight a * |{o ∈ O : ¬ Disjoint a o}|, completing the proof.

    By Finset.sum_congr, it suffices to prove equality of the terms for each fixed a ∈ A. Applying Finset.sum_filter in reverse gathers the indicator terms into a sum of the constant inst.weight a over the filtered set {o ∈ O | ¬ Disjoint a o}. By Finset.sum_const, this sum equals the cardinality of that filtered set times the constant. Finally, nsmul_eq_mul converts natural scalar multiplication to semiring multiplication, and mul_comm commutes the factors to match the target expression.

    lines 16–19

    uses Finset.sum_congr, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, mul_comm

      apply Finset.sum_congr rfl
      intro a ha
      rw [← Finset.sum_filter, Finset.sum_const]
      simp [nsmul_eq_mul, mul_comm]
Finset.sum_congr
If two finite sets are equal and their summands agree on every element, their sums are equal.
Finset.sum_filter
Summing over a filtered subset equals summing over the whole set with an indicator function that takes the summand when the condition holds and zero otherwise.
Finset.sum_comm
The order of summation in a double sum over two finite sets can be swapped.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
nsmul_eq_mul
Scalar multiplication by a natural number n equals multiplication by n coerced into the semiring.
mul_comm
Multiplication in a commutative magma or ring is commutative (a * b = b * a).

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

/-- Double counting identity for conflict neighborhoods: the sum over O of neighborhood weights equals the sum over A of weights times conflict degrees in O. -/theorem op_98_sum_conflict_neighborhood_weight {α : Type*} [DecidableEq α] {k : ℕ}    (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α)) :    ∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o}) =    ∑ a ∈ A, inst.weight a * (O.filter (fun o => ¬ Disjoint a o)).card := by  have h1 : (∑ o ∈ O, packing_weight inst (conflict_neighborhood A {o})) =      ∑ o ∈ O, ∑ a ∈ A, if ¬ Disjoint a o then inst.weight a else 0 := by    apply Finset.sum_congr rfl    intro o ho    simp only [packing_weight, conflict_neighborhood]    rw [Finset.sum_filter]    apply Finset.sum_congr rfl    intro a ha    simp  rw [h1, Finset.sum_comm]  apply Finset.sum_congr rfl  intro a ha  rw [← Finset.sum_filter, Finset.sum_const]  simp [nsmul_eq_mul, mul_comm]
See it in the graphDiscuss this resultChallenge it