AFTD Auto-Formalizing Theoretical Domains

op_98_sq_exchange_bound

theoremverified

Objective switching, first half: square local optimality turns the squared potential inequality for exchanges of at most 4 sets into a factor-2 linear exchange inequality, weight(X) ≤ 2·weight(N(A,X)).

Statement

theorem op_98_sq_exchange_bound {α : 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 ≤ 4) :
    packing_weight inst X ≤ 2 * packing_weight inst (conflict_neighborhood A X)
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…
  • squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…
  • 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…
  • 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…
  • 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…
  • conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…
Used by 3
  • op_98_eight_approximationPartition the packing O into blocks of at most 4 sets; the factor-2 exchange inequality gives weight(block) ≤ 2·weight(N(A, block)) for…
  • op_98_small_packing_boundSpecial case of the target: when the competing packing has at most 4 sets, weight(O) ≤ 2·weight(A), so c = 2 with the empty repair family…
  • op_98_one_cluster_packing_boundIf every set o of a packing O has at most one conflict neighbour in A, then weight(O) ≤ 2·weight(A). Each o has exactly one neighbour a…

The proof, explained

The theorem proves that square local optimality of a packing A under exchanges of size at most 4 implies a factor-2 linear exchange inequality for any packing X with |X| ≤ 4. By Cauchy–Schwarz, the squared weight (weight(X))² is bounded by |X| · squared_weight(X) ≤ 4 · squared_weight(X). Local optimality then bounds this by 4 · squared_weight(N), where N is the conflict neighborhood of X in A. Since all weights are non-negative, the sum of squares in N is bounded by the square of the sum, yielding (weight(X))² ≤ 4 · (weight(N))² = (2 · weight(N))², from which taking square roots yields weight(X) ≤ 2 · weight(N).

  1. The conflict neighborhood N = conflict_neighborhood A X is a subset of the instance family.

    We unpack the square local optimality assumption on A into the packing property of A and the 4-exchange local optimality condition. Letting N denote the conflict neighborhood of X in A, each set a ∈ N belongs to A by definition, and therefore belongs to inst.family because A is a packing.

    lines 6–11

    uses Finset.mem_filter

      obtain ⟨hAp, hloc⟩ := hA
      set N := conflict_neighborhood A X with hN
      have hNsub : N ⊆ inst.family := by
        intro a ha
        simp only [hN, conflict_neighborhood, Finset.mem_filter] at ha
        exact hAp.1 ha.1
  2. Every set in N and every set in X has non-negative weight.

    Since every set in N and every set in the packing X belongs to inst.family, where all weights are strictly positive, their weights are non-negative.

    lines 12–13

    uses le_of_lt

      have hwN : ∀ s ∈ N, 0 ≤ inst.weight s := fun s hs => le_of_lt (inst.weight_pos s (hNsub hs))
      have hwX : ∀ s ∈ X, 0 ≤ inst.weight s := fun s hs => le_of_lt (inst.weight_pos s (hX.1 hs))
  3. (packing_weight inst X) ^ 2 ≤ (X.card : ℚ) * squared_weight inst X

    By the Cauchy–Schwarz inequality for sums, the square of the sum of weights in X is at most the number of sets in X times the sum of their squared weights.

    lines 14–16

    uses sq_sum_le_card_mul_sum_sq

      have h1 : (packing_weight inst X) ^ 2 ≤ (X.card : ℚ) * squared_weight inst X := by
        rw [packing_weight, squared_weight]
        exact sq_sum_le_card_mul_sum_sq
  4. squared_weight inst X ≤ squared_weight inst N

    Because X is a packing with |X| ≤ 4, the square local optimality of A guarantees that the squared weight of X is bounded by the squared weight of its conflict neighborhood N.

    line 17

      have h2 : squared_weight inst X ≤ squared_weight inst N := hloc X hX hXc
  5. squared_weight inst N ≤ (packing_weight inst N) ^ 2

    For non-negative terms, the sum of squares is bounded by the square of the sum. Since every set in N has non-negative weight, this applies directly to N.

    lines 18–20

    uses Finset.sum_sq_le_sq_sum_of_nonneg

      have h3 : squared_weight inst N ≤ (packing_weight inst N) ^ 2 := by
        rw [squared_weight, packing_weight]
        exact Finset.sum_sq_le_sq_sum_of_nonneg hwN
  6. (packing_weight inst X) ^ 2 ≤ (2 * packing_weight inst N) ^ 2

    Casting |X| ≤ 4 to the rationals and noting that the total weights of X and N are non-negative, non-linear arithmetic combines the bounds (weight(X))² ≤ |X| · squared_weight(X) ≤ 4 · squared_weight(N) ≤ 4 · (weight(N))² into (weight(X))² ≤ (2 · weight(N))².

    lines 21–24

    uses Finset.sum_nonneg

      have h4 : (X.card : ℚ) ≤ 4 := by exact_mod_cast hXc
      have hw : 0 ≤ packing_weight inst X := Finset.sum_nonneg hwX
      have hv : 0 ≤ packing_weight inst N := Finset.sum_nonneg hwN
      have hmain : (packing_weight inst X) ^ 2 ≤ (2 * packing_weight inst N) ^ 2 := by nlinarith
  7. packing_weight inst X ≤ 2 * packing_weight inst N

    Taking square roots via monotonicity of squares gives |weight(X)| ≤ |2 · weight(N)|. Because both total weights are non-negative, the absolute values can be removed, establishing the factor-2 exchange inequality.

    lines 25–28

    uses sq_le_sq.mp, abs_of_nonneg

      have habs : |packing_weight inst X| ≤ |2 * packing_weight inst N| := sq_le_sq.mp hmain
      rw [abs_of_nonneg hw,
        abs_of_nonneg (by linarith : (0 : ℚ) ≤ 2 * packing_weight inst N)] at habs
      linarith
Finset.mem_filter
An element belongs to a filtered set Finset.filter p s if and only if it belongs to s and satisfies predicate p.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.
sq_sum_le_card_mul_sum_sq
The square of the sum of a function over a finite set is bounded by the cardinality of the set times the sum of the squares of the function values (Cauchy–Schwarz inequality).
Finset.sum_sq_le_sq_sum_of_nonneg
If a function takes non-negative values on a finite set, the sum of its squares is at most the square of the sum of its values.
Finset.sum_nonneg
The sum of non-negative elements over a finite set is non-negative.
sq_le_sq.mp
If the square of a is at most the square of b, then the absolute value of a is at most the absolute value of b.
abs_of_nonneg
The absolute value of a non-negative number equals the number itself.

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

/-- Factor-2 linear exchange inequality following from square local optimality of 4-exchanges. -/theorem op_98_sq_exchange_bound {α : 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 ≤ 4) :    packing_weight inst X ≤ 2 * packing_weight inst (conflict_neighborhood A X) := by  obtain ⟨hAp, hloc⟩ := hA  set N := conflict_neighborhood A X with hN  have hNsub : N ⊆ inst.family := by    intro a ha    simp only [hN, conflict_neighborhood, Finset.mem_filter] at ha    exact hAp.1 ha.1  have hwN : ∀ s ∈ N, 0 ≤ inst.weight s := fun s hs => le_of_lt (inst.weight_pos s (hNsub hs))  have hwX : ∀ s ∈ X, 0 ≤ inst.weight s := fun s hs => le_of_lt (inst.weight_pos s (hX.1 hs))  have h1 : (packing_weight inst X) ^ 2 ≤ (X.card : ℚ) * squared_weight inst X := by    rw [packing_weight, squared_weight]    exact sq_sum_le_card_mul_sum_sq  have h2 : squared_weight inst X ≤ squared_weight inst N := hloc X hX hXc  have h3 : squared_weight inst N ≤ (packing_weight inst N) ^ 2 := by    rw [squared_weight, packing_weight]    exact Finset.sum_sq_le_sq_sum_of_nonneg hwN  have h4 : (X.card : ℚ) ≤ 4 := by exact_mod_cast hXc  have hw : 0 ≤ packing_weight inst X := Finset.sum_nonneg hwX  have hv : 0 ≤ packing_weight inst N := Finset.sum_nonneg hwN  have hmain : (packing_weight inst X) ^ 2 ≤ (2 * packing_weight inst N) ^ 2 := by nlinarith  have habs : |packing_weight inst X| ≤ |2 * packing_weight inst N| := sq_le_sq.mp hmain  rw [abs_of_nonneg hw,    abs_of_nonneg (by linarith : (0 : ℚ) ≤ 2 * packing_weight inst N)] at habs  linarith
See it in the graphDiscuss this resultChallenge it