op_98_sum_conflict_neighborhood_weight
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.
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.
uses
Finset.sum_congr,Finset.sum_filterhave 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
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.
uses
Finset.sum_commrw [h1, Finset.sum_comm]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.
uses
Finset.sum_congr,Finset.sum_filter,Finset.sum_const,nsmul_eq_mul,mul_commapply 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
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.
/-- 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]