AFTD Auto-Formalizing Theoretical Domains

op_98_no_singleton_repair

theoremverified

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.

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

    lines 6–10

    uses Finset.card_eq_one.mp, Finset.sum_singleton

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

    lines 11–14

    uses Finset.mem_filter.mp, le_of_lt

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

    lines 15–17

    uses Finset.sum_sq_le_sq_sum_of_nonneg

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

    lines 18–21

    uses Finset.sum_nonneg

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

    lines 22–24

    uses Finset.sum_singleton

      dsimp [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

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