op_98_sq_exchange_bound
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).
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.
uses
Finset.mem_filterobtain ⟨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
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.
uses
le_of_lthave 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))
(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.
uses
sq_sum_le_card_mul_sum_sqhave 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
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.
have h2 : squared_weight inst X ≤ squared_weight inst N := hloc X hX hXcsquared_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.
uses
Finset.sum_sq_le_sq_sum_of_nonneghave 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
(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))².
uses
Finset.sum_nonneghave 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
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.
uses
sq_le_sq.mp,abs_of_nonneghave 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.
- The cast of the cardinality bound |X| ≤ 4 from ℕ to ℚ and explicit non-negativity checks for the sums are Lean bookkeeping steps to allow nlinarith and absolute value simplification.
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.
/-- 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