AFTD Auto-Formalizing Theoretical Domains

is_square_locally_optimal

def

Given an instance inst of weighted k-set packing on a type α with decidable equality, a packing A is square locally optimal with respect to size m exchanges (is_square_locally_optimal inst m A) if A is a packing and for every packing X in inst of cardinality at most m, the squared-weight potential of X is at most the squared-weight potential of the conflict neighborhood of X in A.

Statement

def is_square_locally_optimal {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (m : ℕ) (A : Finset (Finset α)) : Prop
Defined in
arXiv:2610.10036 Sec. 3
Verified
19 Oct 2026
Axioms
none listed
Built on 4
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
  • 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…
  • 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 7
  • op_98_no_singleton_repairUnder square local optimality a single-set exchange never has positive linear gain: for X = {s}, w(s)² ≤ squared_weight(N(A,{s})) ≤…
  • 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…
  • 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…
  • op_98_conflict_deg_le_fourFor any weighted 4-set packing instance inst and packings A, O, if A is square locally optimal and o ∈ O, then (conflict_neighborhood A…
  • 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.

Read back from the Lean

Given a type α with decidable equality, a natural number k, an instance inst : WeightedSetPackingInstance α k, a natural number m, and a finite set of sets A : Finset (Finset α), is_square_locally_optimal inst m A asserts that: 1. A is a valid packing for inst (is_packing inst A); and 2. For every finite set of sets X : Finset (Finset α), if X is a valid packing for inst (is_packing inst X) and the cardinality of X is at most m (X.card ≤ m), then the sum of squared weights of the sets in X is less than or equal to the sum of squared weights of the sets in the conflict neighborhood of X within A (squared_weight inst X ≤ squared_weight inst (conflict_neighborhood A X)).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A packing is square-locally optimal if no exchange of size up to m increases squared weight. -/
def is_square_locally_optimal {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (m : ℕ) (A : Finset (Finset α)) : Prop := is_packing inst A ∧ ∀ X, is_packing inst X → X.card ≤ m → squared_weight inst X ≤ squared_weight inst (conflict_neighborhood A X)
See it in the graphDiscuss this resultChallenge it