AFTD Auto-Formalizing Theoretical Domains

op_98_small_packing_bound

theoremverified

Special 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 suffices.

Statement

theorem op_98_small_packing_bound {α : Type*} [DecidableEq α] {k : ℕ}
    (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α))
    (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (hOc : O.card ≤ 4) :
    packing_weight inst O ≤ 2 * packing_weight inst A
Source
step towards op_98_objective_switching_weighted_four_set_packing
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • op_98_sq_exchange_boundObjective switching, first half: square local optimality turns the squared potential inequality for exchanges of at most 4 sets into a…
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of 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 α)),…
  • squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…

The proof, explained

To bound the weight of any competing packing O with at most 4 sets by twice the weight of a square-locally optimal packing A, the proof first invokes the square-exchange bound (`op_98_sq_exchange_bound`) to bound the weight of O by twice the weight of its conflict neighborhood in A. Because the conflict neighborhood is a subcollection of A and all instance weights are positive, the weight of the conflict neighborhood is at most the weight of A. Linear arithmetic combines these two bounds to conclude that weight(O) ≤ 2 · weight(A).

  1. The weight of the competitor packing O is at most twice the weight of its conflict neighborhood in A.

    Applying `op_98_sq_exchange_bound` to A and O establishes that weight(O) ≤ 2 · weight(conflict_neighborhood A O), using the assumptions that A is square-locally optimal with parameter 4, O is a packing, and O contains at most 4 sets.

    lines 6–7

    uses op_98_sq_exchange_bound

      have h1 : packing_weight inst O ≤ 2 * packing_weight inst (conflict_neighborhood A O) :=
        op_98_sq_exchange_bound inst A O hA hO hOc
  2. The conflict neighborhood of O in A is a subset of A.

    By definition, the conflict neighborhood consists of those sets in A that intersect at least one set in O. Rewriting with `Finset.mem_filter`, any element in the conflict neighborhood is in particular an element of A.

    lines 8–11

    uses Finset.mem_filter

      have hsub : conflict_neighborhood A O ⊆ A := by
        intro x hx
        simp only [conflict_neighborhood, Finset.mem_filter] at hx
        exact hx.1
  3. The weight of the conflict neighborhood of O in A is at most the weight of A.

    Expanding the definition of packing weight into sums of weights, the conflict neighborhood is a subcollection of A. Since A is a packing, its sets belong to the instance family and have strictly positive weights; in particular, by `le_of_lt`, their weights are nonnegative. Therefore, `Finset.sum_le_sum_of_subset_of_nonneg` shows that the sum over the subcollection is at most the sum over all of A.

    lines 12–15

    uses Finset.sum_le_sum_of_subset_of_nonneg, le_of_lt

      have h2 : packing_weight inst (conflict_neighborhood A O) ≤ packing_weight inst A := by
        rw [packing_weight, packing_weight]
        exact Finset.sum_le_sum_of_subset_of_nonneg hsub
          (fun x hx _ => le_of_lt (inst.weight_pos x (hA.1.1 hx)))
  4. The weight of O is at most twice the weight of A. automation

    Combining the inequality weight(O) ≤ 2 · weight(conflict_neighborhood A O) with weight(conflict_neighborhood A O) ≤ weight(A), linear arithmetic directly concludes that weight(O) ≤ 2 · weight(A).

    line 16

      linarith
op_98_sq_exchange_bound
In a weighted set packing instance, if a packing A is square-locally optimal with parameter 4, and X is a packing with at most 4 sets, then the weight of X is at most twice the weight of its conflict neighborhood in A.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filter predicate.
Finset.sum_le_sum_of_subset_of_nonneg
If one finset is a subset of another and the summand is nonnegative on the difference, the sum over the subset is at most the sum over the superset.
le_of_lt
A strict inequality a < b implies the weak inequality a ≤ b.

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

/-- Small-instance case: ratio 2 with no repairs when the competitor has at most 4 sets. -/theorem op_98_small_packing_bound {α : Type*} [DecidableEq α] {k : ℕ}    (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α))    (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (hOc : O.card ≤ 4) :    packing_weight inst O ≤ 2 * packing_weight inst A := by  have h1 : packing_weight inst O ≤ 2 * packing_weight inst (conflict_neighborhood A O) :=    op_98_sq_exchange_bound inst A O hA hO hOc  have hsub : conflict_neighborhood A O ⊆ A := by    intro x hx    simp only [conflict_neighborhood, Finset.mem_filter] at hx    exact hx.1  have h2 : packing_weight inst (conflict_neighborhood A O) ≤ packing_weight inst A := by    rw [packing_weight, packing_weight]    exact Finset.sum_le_sum_of_subset_of_nonneg hsub      (fun x hx _ => le_of_lt (inst.weight_pos x (hA.1.1 hx)))  linarith
See it in the graphDiscuss this resultChallenge it