op_98_no_singleton_repair
Under square local optimality a single-set exchange never has positive linear gain: for X = {s}, w(s)² ≤ squared_weight(N(A,{s})) ≤ weight(N(A,{s}))², hence linear_gain inst A {s} ≤ 0.
Statement
theorem op_98_no_singleton_repair {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hX : is_packing inst X) (hXc : X.card = 1) : linear_gain inst A X ≤ 0
- Source
- step towards op_98_objective_switching_weighted_four_set_packing
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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 α)),…
- is_packingGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection A : Finset (Finset α) is a packing…
- squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…
- is_square_locally_optimalGiven an instance inst of weighted k-set packing on a type α with decidable equality, a packing A is square locally optimal with respect…
- linear_gainGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear gain linear_gain inst A X of an exchange…
- 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
Because X is a singleton {s}, its cardinality is 1 ≤ 4, so square local optimality of order 4 ensures that w(s)² is bounded by the sum of squared weights in the conflict neighborhood N(A, {s}). Since all weights in the packing are nonnegative, the sum of squared weights is bounded by the square of their sum, yielding w(s)² ≤ (∑_{x ∈ N(A, {s})} w(x))². Taking the square root gives w(s) ≤ ∑_{x ∈ N(A, {s})} w(x), which immediately implies that the linear gain w(s) - weight(N(A, {s})) is at most zero.
X is a singleton {s}, and 4-square local optimality bounds w(s)² by the sum of squared weights in its conflict neighborhood.
Since X has cardinality 1 (hXc), it can be written as {s} for some set s. Because |{s}| = 1 ≤ 4 and {s} is a packing (hX), the square local optimality of A applies, giving that the squared weight of {s} is at most the squared weight of its conflict neighborhood N(A, {s}). Evaluating the squared weight sum on the singleton {s} reduces this to w(s)² ≤ ∑_{x ∈ N(A, {s})} w(x)².
uses
Finset.card_eq_one.mp,Finset.sum_singletonobtain ⟨s, rfl⟩ := Finset.card_eq_one.mp hXc have hcard : ({s} : Finset (Finset α)).card ≤ 4 := by simp have hsq_opt := hA.2 {s} hX hcard dsimp [squared_weight] at hsq_opt rw [Finset.sum_singleton] at hsq_opt
Every set in the conflict neighborhood N(A, {s}) has nonnegative weight.
Every x in N(A, {s}) belongs to A by the definition of the conflict neighborhood as a filtered subset of A. Because A is a packing, all of its elements belong to the instance family, where every set has strictly positive weight, hence nonnegative weight.
uses
Finset.mem_filter.mp,le_of_lthave h_nonneg : ∀ x ∈ conflict_neighborhood A {s}, 0 ≤ inst.weight x := by intro x hx have hxA : x ∈ A := (Finset.mem_filter.mp hx).1 exact le_of_lt (inst.weight_pos x (hA.1.1 hxA))
w(s)² ≤ (∑_{x ∈ N(A, {s})} w(x))²
For any finite collection of nonnegative numbers, the sum of squares is bounded by the square of the sum. Combining this inequality with the bound from square local optimality shows that w(s)² ≤ (∑_{x ∈ N(A, {s})} w(x))².
uses
Finset.sum_sq_le_sq_sum_of_nonneghave hsq_sum := Finset.sum_sq_le_sq_sum_of_nonneg h_nonneg have hle_sq : inst.weight s ^ 2 ≤ (∑ x ∈ conflict_neighborhood A {s}, inst.weight x) ^ 2 := hsq_opt.trans hsq_sum
w(s) ≤ ∑_{x ∈ N(A, {s})} w(x)
The total weight of the conflict neighborhood is nonnegative because each element's weight is nonnegative. From w(s)² ≤ (∑_{x ∈ N(A, {s})} w(x))² and the nonnegativity of the sum, nonlinear arithmetic deduces w(s) ≤ ∑_{x ∈ N(A, {s})} w(x).
uses
Finset.sum_nonneghave hsum_nonneg : 0 ≤ ∑ x ∈ conflict_neighborhood A {s}, inst.weight x := Finset.sum_nonneg h_nonneg have hlin : inst.weight s ≤ ∑ x ∈ conflict_neighborhood A {s}, inst.weight x := by nlinarith
The linear gain linear_gain inst A X is at most 0.
Unfolding the definition, the linear gain is the weight of {s}, which simplifies to w(s), minus the total weight of the conflict neighborhood N(A, {s}). Since w(s) ≤ ∑_{x ∈ N(A, {s})} w(x), their difference is at most 0.
uses
Finset.sum_singletondsimp [linear_gain, packing_weight] rw [Finset.sum_singleton] linarith
Finset.card_eq_one.mp- A finite set has cardinality 1 only if it is a singleton {a} for some element a.
Finset.sum_singleton- The sum of a function over a singleton {a} equals the function's value at a.
Finset.mem_filter.mp- If an element belongs to a filtered set, then it belongs to the base set and satisfies the filtering condition.
le_of_lt- Strict inequality a < b implies weak inequality a ≤ b.
Finset.sum_sq_le_sq_sum_of_nonneg- For any finite set of nonnegative terms, the sum of squares is at most the square of the sum: ∑ x_i² ≤ (∑ x_i)².
Finset.sum_nonneg- The sum of nonnegative elements over a finite set is nonnegative.
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.
/-- No single-set exchange has positive linear gain under square local optimality, so every repair has at least 2 sets. -/theorem op_98_no_singleton_repair {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A X : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hX : is_packing inst X) (hXc : X.card = 1) : linear_gain inst A X ≤ 0 := by obtain ⟨s, rfl⟩ := Finset.card_eq_one.mp hXc have hcard : ({s} : Finset (Finset α)).card ≤ 4 := by simp have hsq_opt := hA.2 {s} hX hcard dsimp [squared_weight] at hsq_opt rw [Finset.sum_singleton] at hsq_opt have h_nonneg : ∀ x ∈ conflict_neighborhood A {s}, 0 ≤ inst.weight x := by intro x hx have hxA : x ∈ A := (Finset.mem_filter.mp hx).1 exact le_of_lt (inst.weight_pos x (hA.1.1 hxA)) have hsq_sum := Finset.sum_sq_le_sq_sum_of_nonneg h_nonneg have hle_sq : inst.weight s ^ 2 ≤ (∑ x ∈ conflict_neighborhood A {s}, inst.weight x) ^ 2 := hsq_opt.trans hsq_sum have hsum_nonneg : 0 ≤ ∑ x ∈ conflict_neighborhood A {s}, inst.weight x := Finset.sum_nonneg h_nonneg have hlin : inst.weight s ≤ ∑ x ∈ conflict_neighborhood A {s}, inst.weight x := by nlinarith dsimp [linear_gain, packing_weight] rw [Finset.sum_singleton] linarith