block_insertion_residual_cost_bound
Given a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤ B.card, and a bundle E : Finset α of r chores disjoint from B with E.card = r such that c e ≤ c b for all e ∈ E and b ∈ B, the k-chore residual cost chore_residual_cost c k (B ∪ E) is at most max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b.
Statement
theorem block_insertion_residual_cost_bound {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (hk : 1 ≤ k) (B E : Finset α) (r : ℕ) (hr : E.card = r) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b
- Formalizes
- arXiv:2611.07468 Lemma B.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- chore_residual_costGiven a type α with decidable equality, a cost function c : α → NNReal taking values in the non-negative reals, a natural number k : ℕ,…
- block_insertion_residual_cost_bound_of_leGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ, a bundle B : Finset α with k ≤ B.card, and…
- block_insertion_residual_cost_bound_of_gtGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
Let α be a type with decidable equality, and let c : α → NNReal be a cost function assigning a non-negative real number to each element of α. Let k be a positive natural number (1 ≤ k). Let B and E be finite subsets of α, and let r be a natural number such that the cardinality of E equals r. Assume that B and E are disjoint, that k ≤ B.card, and that every element in E has cost at most that of any element in B (i.e., ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b).
Then the chore_residual_cost of B ∪ E with parameters c and k is at most max 1 (r / k) * ∑ b ∈ B, c b (where r and k are coerced to NNReal).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by case analysis on whether r ≤ k. If r ≤ k, a helper lemma bounds the residual cost of B ∪ E by ∑ b ∈ B, c b, which is at most max 1 (r / k) * ∑ b ∈ B, c b because 1 ≤ max 1 (r / k). If r > k, a companion lemma bounds the residual cost by (r / k) * ∑ b ∈ B, c b, which is bounded by the same expression since r / k ≤ max 1 (r / k).
The desired residual cost bound holds when r ≤ k.
We divide into cases depending on whether r ≤ k. In this first case, since |E| = r, we have |E| ≤ k. By block_insertion_residual_cost_bound_of_le, the k-chore residual cost of B ∪ E is bounded above by ∑ b ∈ B, c b. Using le_max_left, we have 1 ≤ max 1 (r / k). Rewriting ∑ b ∈ B, c b as 1 * ∑ b ∈ B, c b via one_mul and applying monotonicity of multiplication yields ∑ b ∈ B, c b ≤ max 1 (r / k) * ∑ b ∈ B, c b. By transitivity, the bound holds for this case.
uses
block_insertion_residual_cost_bound_of_le,le_max_left,one_mulby_cases hrk : r ≤ k · have hrk' : E.card ≤ k := hr.symm ▸ hrk have hle := block_insertion_residual_cost_bound_of_le c k B E hdisj hkB hrk' h_cost have hmax : (1 : NNReal) ≤ max 1 ((r : NNReal) / (k : NNReal)) := le_max_left 1 _ have h1 : ∑ b ∈ B, c b ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by conv_lhs => rw [← one_mul (∑ b ∈ B, c b)] gcongr exact hle.trans h1
The desired residual cost bound holds when r > k, completing the proof.
In the remaining case ¬(r ≤ k), integer arithmetic gives k < r = |E|. By block_insertion_residual_cost_bound_of_gt, the residual cost of B ∪ E is at most (|E| / k) * ∑ b ∈ B, c b, which simplifies to (r / k) * ∑ b ∈ B, c b by substituting |E| = r. Since r / k ≤ max 1 (r / k) by le_max_right, multiplying by the sum gives (r / k) * ∑ b ∈ B, c b ≤ max 1 (r / k) * ∑ b ∈ B, c b. Transitivity with the previous inequality completes the proof.
uses
block_insertion_residual_cost_bound_of_gt,le_max_right· have hrk' : k < E.card := by rw [hr] omega have hgt := block_insertion_residual_cost_bound_of_gt c k hk B E hdisj hkB hrk' h_cost have hmax : ((r : NNReal) / (k : NNReal)) ≤ max 1 ((r : NNReal) / (k : NNReal)) := le_max_right _ _ rw [hr] at hgt have h2 : ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by gcongr exact hgt.trans h2
block_insertion_residual_cost_bound_of_le- If a bundle E with |E| ≤ k is disjoint from B, |B| ≥ k, and every chore in E costs at most every chore in B, then the k-chore residual cost of B ∪ E is at most ∑ b ∈ B, c b.
le_max_left- In any linear order, a ≤ max a b.
one_mul- Multiplying any element on the left by 1 leaves it unchanged: 1 * a = a.
block_insertion_residual_cost_bound_of_gt- If 1 ≤ k < |E|, B and E are disjoint with |B| ≥ k, and every chore in E costs at most every chore in B, then the k-chore residual cost of B ∪ E is at most (|E| / k) * ∑ b ∈ B, c b.
le_max_right- In any linear order, b ≤ max 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
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.
/-- Block insertion cost bound for EFkX residuals (Lemma B.1). -/theorem block_insertion_residual_cost_bound {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (hk : 1 ≤ k) (B E : Finset α) (r : ℕ) (hr : E.card = r) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by by_cases hrk : r ≤ k · have hrk' : E.card ≤ k := hr.symm ▸ hrk have hle := block_insertion_residual_cost_bound_of_le c k B E hdisj hkB hrk' h_cost have hmax : (1 : NNReal) ≤ max 1 ((r : NNReal) / (k : NNReal)) := le_max_left 1 _ have h1 : ∑ b ∈ B, c b ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by conv_lhs => rw [← one_mul (∑ b ∈ B, c b)] gcongr exact hle.trans h1 · have hrk' : k < E.card := by rw [hr] omega have hgt := block_insertion_residual_cost_bound_of_gt c k hk B E hdisj hkB hrk' h_cost have hmax : ((r : NNReal) / (k : NNReal)) ≤ max 1 ((r : NNReal) / (k : NNReal)) := le_max_right _ _ rw [hr] at hgt have h2 : ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b ≤ max 1 ((r : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by gcongr exact hgt.trans h2