block_insertion_residual_cost_bound_of_gt
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 α disjoint from B with k < E.card 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 ((E.card : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b.
Statement
theorem block_insertion_residual_cost_bound_of_gt {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (hk : 1 ≤ k) (B E : Finset α) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (hrk : k < E.card) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ ((E.card : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b
- Source
- arXiv:2611.07468 Lemma B.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- chore_residual_costGiven a type α with decidable equality, a cost function c : α → NNReal taking values in the non-negative reals, a natural number k : ℕ,…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- block_insertion_residual_cost_boundGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤…
Read back from the Lean
Let α be a type with decidable equality, and let c : α → NNReal be a cost function. Let k : ℕ satisfy 1 ≤ k. Let B and E be disjoint finite subsets of α such that k ≤ B.card and k < E.card. Suppose that for every e ∈ E and every b ∈ B, c e ≤ c b. Then chore_residual_cost c k (B ∪ E) ≤ ((E.card : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b.
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 bounds the residual cost of B ∪ E after removing an arbitrary subset T of size k by comparing all chore costs to the maximum cost a = c e₀ in E. Because every element in B costs at least a while every element in E costs at most a, the residual sum on E is bounded by |E \ T| * a while k * a is bounded by the total cost on B. An auxiliary algebraic lemma then combines these bounds with the cardinality identity |E \ T| + k = |E| + |B ∩ T| to conclude that the residual cost is at most (|E| / k) * ∑_{b ∈ B} c b.
The residual sum S_B_rem + S_E_rem is bounded by (S_B_rem + S_B_in) + (|E| - k) * a.
From the cardinality relation |E \ T| + k = |E| + |B ∩ T| with k ≤ |E|, integer arithmetic shows |E \ T| = (|E| - k) + |B ∩ T|. Casting to NNReal and distributing over a gives S_E_rem ≤ (|E| - k) * a + |B ∩ T| * a. Since |B ∩ T| * a ≤ S_B_in, adding S_B_rem yields S_B_rem + S_E_rem ≤ (S_B_rem + S_B_in) + (|E| - k) * a.
uses
ne_of_gt,Nat.cast_add,add_mulhave hk_ne : (k : NNReal) ≠ 0 := ne_of_gt hk_pos have hE_sub : E_sdiff_T_card = (E_card - k) + B_inter_T_card := by omega have hE_cast : (E_sdiff_T_card : NNReal) = ((E_card - k : ℕ) : NNReal) + (B_inter_T_card : NNReal) := by rw [hE_sub, Nat.cast_add] have h1 : S_E_rem ≤ (((E_card - k : ℕ) : NNReal) + (B_inter_T_card : NNReal)) * a := by rwa [← hE_cast] rw [add_mul] at h1 have h2 : S_B_rem + S_E_rem ≤ (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a := by calc S_B_rem + S_E_rem ≤ S_B_rem + (((E_card - k : ℕ) : NNReal) * a + (B_inter_T_card : NNReal) * a) := by gcongr _ = (S_B_rem + (B_inter_T_card : NNReal) * a) + ((E_card - k : ℕ) : NNReal) * a := by ring _ ≤ (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a := by gcongr
The term (|E| - k) * a is bounded by ((|E| - k) / k) * (S_B_rem + S_B_in).
Since k * a ≤ S_B_rem + S_B_in and k > 0, dividing by k yields a ≤ (S_B_rem + S_B_in) / k. Scaling both sides by the non-negative natural cast |E| - k and rearranging the product gives (|E| - k) * a ≤ ((|E| - k) / k) * (S_B_rem + S_B_in).
uses
le_div_iff₀,mul_commhave ha_le : a ≤ (S_B_rem + S_B_in) / (k : NNReal) := by rw [le_div_iff₀ hk_pos, mul_comm] exact hka have h3 : ((E_card - k : ℕ) : NNReal) * a ≤ ((E_card - k : ℕ) : NNReal) * ((S_B_rem + S_B_in) / (k : NNReal)) := by gcongr have h4 : ((E_card - k : ℕ) : NNReal) * ((S_B_rem + S_B_in) / (k : NNReal)) = (((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by ring rw [h4] at h3
The auxiliary bound S_B_rem + S_E_rem ≤ (|E| / k) * (S_B_rem + S_B_in) holds.
Factoring out S_B_rem + S_B_in gives (S_B_rem + S_B_in) + (|E| - k) * a ≤ (1 + (|E| - k) / k) * (S_B_rem + S_B_in). Rewriting 1 as k / k and combining fractions over k simplifies 1 + (|E| - k) / k to |E| / k. Combining this with the bound from the first step completes the auxiliary lemma.
uses
div_self,add_div,Nat.cast_addhave h5 : (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a ≤ (1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by calc (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a ≤ (S_B_rem + S_B_in) + (((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by gcongr _ = (1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by ring have h6 : 1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal) = (E_card : NNReal) / (k : NNReal) := by have : 1 = (k : NNReal) / (k : NNReal) := (div_self hk_ne).symm nth_rw 1 [this] rw [← add_div] congr 1 rw [← Nat.cast_add] congr 1 omega rw [h6] at h5 exact h2.trans h5
The parameter k is strictly positive and there exists a maximal element e₀ ∈ E with cost a = c e₀ such that c e ≤ a for all e ∈ E.
Because 1 ≤ k, we have 0 < k. Since k < |E|, E cannot be empty (an empty set would imply k < 0). A nonempty finite set admits a cost-maximizing element e₀ ∈ E. Setting a = c e₀ ensures that every element in E has cost at most a.
uses
Nat.cast_pos.mpr,Finset.nonempty_iff_ne_empty,Finset.card_empty,Finset.exists_max_imagehave hk_pos : 0 < (k : NNReal) := by have : 0 < k := by omega exact Nat.cast_pos.mpr this have hE_nonempty : E.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h rw [h, Finset.card_empty] at hrk omega rcases Finset.exists_max_image E c hE_nonempty with ⟨e₀, he₀, he₀_max⟩ set a := c e₀
To bound the residual cost, it suffices to bound the cost outside an arbitrary subset T ⊆ B ∪ E of size k.
By definition, the residual cost is the supremum over all subsets T ⊆ B ∪ E of cardinality min k |B ∪ E|. Because k ≤ |B| ≤ |B ∪ E|, this size is exactly k. Applying the supremum upper bound lemma reduces the theorem to showing the inequality for any fixed subset T of size k.
uses
ciSup_le',Finset.card_le_card,Finset.subset_union_left,Nat.min_eq_leftunfold chore_residual_cost refine ciSup_le' ?_ rintro ⟨T, hTsub, hTcard⟩ have hkBE : k ≤ (B ∪ E).card := hkB.trans (Finset.card_le_card Finset.subset_union_left) have hTcard' : T.card = k := by rw [Nat.min_eq_left hkBE] at hTcard exact hTcard
The subset T decomposes as (B ∩ T) ∪ (E ∩ T), leading to the cardinality identity |E \ T| + k = |E| + |B ∩ T|.
Since T ⊆ B ∪ E, every element of T is in B or E, so T = (B ∩ T) ∪ (E ∩ T) as a disjoint union, which gives |T| = |B ∩ T| + |E ∩ T| = k. Combined with the partition |E| = |E \ T| + |E ∩ T|, adding k to |E \ T| gives |E| + |B ∩ T|.
uses
Finset.mem_union,Finset.mem_inter,Or.inl,Or.inr,Finset.inter_subset_left,Finset.card_union_of_disjoint,Finset.card_sdiff_add_card_interhave hT_decomp : T.card = (B ∩ T).card + (E ∩ T).card := by have hT : T = (B ∩ T) ∪ (E ∩ T) := by ext x simp only [Finset.mem_union, Finset.mem_inter] constructor · intro hx have := hTsub hx simp only [Finset.mem_union] at this rcases this with h | h · exact Or.inl ⟨h, hx⟩ · exact Or.inr ⟨h, hx⟩ · rintro (⟨-, hx⟩ | ⟨-, hx⟩) <;> exact hx have hd : Disjoint (B ∩ T) (E ∩ T) := hdisj.mono Finset.inter_subset_left Finset.inter_subset_left conv_lhs => rw [hT] rw [Finset.card_union_of_disjoint hd] have hE_decomp : (E \ T).card + (E ∩ T).card = E.card := Finset.card_sdiff_add_card_inter E T have hE_identity : (E \ T).card + k = E.card + (B ∩ T).card := by omega
The residual cost splits as ∑_{(B ∪ E) \ T} c = ∑_{B \ T} c + ∑_{E \ T} c, and the total cost of B splits as ∑_B c = ∑_{B \ T} c + ∑_{B ∩ T} c.
Because B and E are disjoint, (B ∪ E) \ T is the disjoint union of B \ T and E \ T, so the sum splits across them. Similarly, B is partitioned into the elements outside T and those in T, so the total sum over B decomposes into the sum over B \ T plus the sum over B ∩ T.
uses
Finset.union_sdiff_distrib,Finset.sum_union,Finset.sdiff_subset,Finset.sum_sdiff,Finset.inter_subset_left,Finset.sdiff_inter_self_lefthave hdec1 : ∑ x ∈ (B ∪ E) \ T, c x = (∑ x ∈ B \ T, c x) + ∑ x ∈ E \ T, c x := by rw [Finset.union_sdiff_distrib, Finset.sum_union] exact hdisj.mono Finset.sdiff_subset Finset.sdiff_subset have hdec2 : (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x = ∑ x ∈ B, c x := by have := Finset.sum_sdiff (f := c) (s₁ := B ∩ T) (s₂ := B) Finset.inter_subset_left rw [Finset.sdiff_inter_self_left] at this exact this
The component sums satisfy ∑_{E \ T} c ≤ |E \ T| * a, |B ∩ T| * a ≤ ∑_{B ∩ T} c, and k * a ≤ ∑_{B \ T} c + ∑_{B ∩ T} c.
Every element in E \ T costs at most a, bounding the sum over E \ T by |E \ T| * a. Every element in B costs at least a by the assumption relating E and B, so |B ∩ T| * a ≤ ∑_{B ∩ T} c. Finally, k ≤ |B| implies k * a ≤ |B| * a ≤ ∑_B c, which matches the sum over B \ T plus B ∩ T.
uses
Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mulhave hSE : ∑ x ∈ E \ T, c x ≤ ((E \ T).card : NNReal) * a := by calc ∑ x ∈ E \ T, c x ≤ ∑ x ∈ E \ T, a := Finset.sum_le_sum fun x hx => he₀_max x (Finset.mem_sdiff.mp hx).1 _ = ((E \ T).card : NNReal) * a := by rw [Finset.sum_const, nsmul_eq_mul] have hSBin : ((B ∩ T).card : NNReal) * a ≤ ∑ x ∈ B ∩ T, c x := by calc ((B ∩ T).card : NNReal) * a = ∑ x ∈ B ∩ T, a := by rw [Finset.sum_const, nsmul_eq_mul] _ ≤ ∑ x ∈ B ∩ T, c x := Finset.sum_le_sum fun x hx => h_cost e₀ he₀ x (Finset.mem_inter.mp hx).1 have hka : (k : NNReal) * a ≤ (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x := by rw [hdec2] calc (k : NNReal) * a ≤ (B.card : NNReal) * a := by gcongr _ = ∑ x ∈ B, a := by rw [Finset.sum_const, nsmul_eq_mul] _ ≤ ∑ x ∈ B, c x := Finset.sum_le_sum fun x hx => h_cost e₀ he₀ x hx
The k-chore residual cost of B ∪ E is at most (|E| / k) * ∑_{b ∈ B} c b.
Rewriting the residual cost and the total cost of B using the sum decompositions matches the exact hypotheses of the auxiliary lemma with S_B_rem = ∑_{B \ T} c, S_B_in = ∑_{B ∩ T} c, and S_E_rem = ∑_{E \ T} c. Applying block_insertion_residual_cost_bound_of_gt_aux completes the proof.
uses
block_insertion_residual_cost_bound_of_gt_auxrw [hdec1, ← hdec2] exact block_insertion_residual_cost_bound_of_gt_aux (∑ x ∈ B \ T, c x) (∑ x ∈ B ∩ T, c x) (∑ x ∈ E \ T, c x) a k E.card (B ∩ T).card (E \ T).card hE_identity (by omega) hSE hSBin hka hk_pos
ne_of_gt- If b < a, then a ≠ b.
Nat.cast_add- The cast of m + n to a semiring equals the sum of the casts of m and n.
add_mul- Right distributivity of multiplication over addition: (a + b) * c = a * c + b * c.
le_div_iff₀- For c > 0, a ≤ b / c holds if and only if a * c ≤ b.
mul_comm- Multiplication is commutative: a * b = b * a.
div_self- Any nonzero element divided by itself equals 1.
add_div- Division distributes over addition in the numerator: (a + b) / c = a / c + b / c.
Nat.cast_pos.mpr- If 0 < k for a natural number k, then 0 < ↑k in an ordered semiring.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not equal to the empty set.
Finset.card_empty- The cardinality of the empty set is 0.
Finset.exists_max_image- A nonempty finite set has an element that maximizes a given function.
ciSup_le'- The supremum of a family of elements is at most a given bound if every element is at most that bound.
Finset.card_le_card- If s ⊆ t, then the cardinality of s is at most that of t.
Finset.subset_union_left- Any set s₁ is a subset of s₁ ∪ s₂.
Nat.min_eq_left- If a ≤ b, then min a b = a.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_inter- An element belongs to s ∩ t if and only if it belongs to both s and t.
Or.inl- Constructs a proof of a ∨ b from a proof of a.
Or.inr- Constructs a proof of a ∨ b from a proof of b.
Finset.inter_subset_left- The intersection s₁ ∩ s₂ is a subset of s₁.
Finset.card_union_of_disjoint- If s and t are disjoint finite sets, then |s ∪ t| = |s| + |t|.
Finset.card_sdiff_add_card_inter- For any finite sets s and t, |s \ t| + |s ∩ t| = |s|.
Finset.union_sdiff_distrib- Set difference distributes over union: (s₁ ∪ s₂) \ t = (s₁ \ t) ∪ (s₂ \ t).
Finset.sum_union- The sum of a function over the union of disjoint sets is the sum of the sums over each set.
Finset.sdiff_subset- The set difference s \ t is a subset of s.
Finset.sum_sdiff- For s₁ ⊆ s₂, the sum over s₂ equals the sum over s₂ \ s₁ plus the sum over s₁.
Finset.sdiff_inter_self_left- Subtracting s ∩ t from s yields s \ t.
Finset.sum_le_sum- If f x ≤ g x for all x in a finite set, then the sum of f over the set is at most the sum of g.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set multiplied by that value.
nsmul_eq_mul- Natural number scalar multiplication n • a equals (↑n) * a.
block_insertion_residual_cost_bound_of_gt_aux- Auxiliary algebraic lemma bounding S_B_rem + S_E_rem by (|E| / k) * (S_B_rem + S_B_in) under cardinality balance and cost inequalities.
- The linear integer arithmetic steps connecting set cardinalities, such as showing |E \ T| + k = |E| + |B ∩ T| and 0 < k, are discharged by the automated tactic omega.
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.
lemma block_insertion_residual_cost_bound_of_gt_aux (S_B_rem S_B_in S_E_rem a : NNReal) (k E_card B_inter_T_card E_sdiff_T_card : ℕ) (hE : E_sdiff_T_card + k = E_card + B_inter_T_card) (hk_le_E : k ≤ E_card) (hSE : S_E_rem ≤ (E_sdiff_T_card : NNReal) * a) (hSBin : (B_inter_T_card : NNReal) * a ≤ S_B_in) (hka : (k : NNReal) * a ≤ S_B_rem + S_B_in) (hk_pos : 0 < (k : NNReal)) : S_B_rem + S_E_rem ≤ ((E_card : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by have hk_ne : (k : NNReal) ≠ 0 := ne_of_gt hk_pos have hE_sub : E_sdiff_T_card = (E_card - k) + B_inter_T_card := by omega have hE_cast : (E_sdiff_T_card : NNReal) = ((E_card - k : ℕ) : NNReal) + (B_inter_T_card : NNReal) := by rw [hE_sub, Nat.cast_add] have h1 : S_E_rem ≤ (((E_card - k : ℕ) : NNReal) + (B_inter_T_card : NNReal)) * a := by rwa [← hE_cast] rw [add_mul] at h1 have h2 : S_B_rem + S_E_rem ≤ (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a := by calc S_B_rem + S_E_rem ≤ S_B_rem + (((E_card - k : ℕ) : NNReal) * a + (B_inter_T_card : NNReal) * a) := by gcongr _ = (S_B_rem + (B_inter_T_card : NNReal) * a) + ((E_card - k : ℕ) : NNReal) * a := by ring _ ≤ (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a := by gcongr have ha_le : a ≤ (S_B_rem + S_B_in) / (k : NNReal) := by rw [le_div_iff₀ hk_pos, mul_comm] exact hka have h3 : ((E_card - k : ℕ) : NNReal) * a ≤ ((E_card - k : ℕ) : NNReal) * ((S_B_rem + S_B_in) / (k : NNReal)) := by gcongr have h4 : ((E_card - k : ℕ) : NNReal) * ((S_B_rem + S_B_in) / (k : NNReal)) = (((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by ring rw [h4] at h3 have h5 : (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a ≤ (1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by calc (S_B_rem + S_B_in) + ((E_card - k : ℕ) : NNReal) * a ≤ (S_B_rem + S_B_in) + (((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by gcongr _ = (1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal)) * (S_B_rem + S_B_in) := by ring have h6 : 1 + ((E_card - k : ℕ) : NNReal) / (k : NNReal) = (E_card : NNReal) / (k : NNReal) := by have : 1 = (k : NNReal) / (k : NNReal) := (div_self hk_ne).symm nth_rw 1 [this] rw [← add_div] congr 1 rw [← Nat.cast_add] congr 1 omega rw [h6] at h5 exact h2.trans h5/-- When |E| > k, the k-chore residual cost of B ∪ E is at most (|E| / k) * c(B). -/theorem block_insertion_residual_cost_bound_of_gt {α : Type*} [DecidableEq α] (c : α → NNReal) (k : ℕ) (hk : 1 ≤ k) (B E : Finset α) (hdisj : Disjoint B E) (hkB : k ≤ B.card) (hrk : k < E.card) (h_cost : ∀ e ∈ E, ∀ b ∈ B, c e ≤ c b) : chore_residual_cost c k (B ∪ E) ≤ ((E.card : NNReal) / (k : NNReal)) * ∑ b ∈ B, c b := by have hk_pos : 0 < (k : NNReal) := by have : 0 < k := by omega exact Nat.cast_pos.mpr this have hE_nonempty : E.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h rw [h, Finset.card_empty] at hrk omega rcases Finset.exists_max_image E c hE_nonempty with ⟨e₀, he₀, he₀_max⟩ set a := c e₀ unfold chore_residual_cost refine ciSup_le' ?_ rintro ⟨T, hTsub, hTcard⟩ have hkBE : k ≤ (B ∪ E).card := hkB.trans (Finset.card_le_card Finset.subset_union_left) have hTcard' : T.card = k := by rw [Nat.min_eq_left hkBE] at hTcard exact hTcard have hT_decomp : T.card = (B ∩ T).card + (E ∩ T).card := by have hT : T = (B ∩ T) ∪ (E ∩ T) := by ext x simp only [Finset.mem_union, Finset.mem_inter] constructor · intro hx have := hTsub hx simp only [Finset.mem_union] at this rcases this with h | h · exact Or.inl ⟨h, hx⟩ · exact Or.inr ⟨h, hx⟩ · rintro (⟨-, hx⟩ | ⟨-, hx⟩) <;> exact hx have hd : Disjoint (B ∩ T) (E ∩ T) := hdisj.mono Finset.inter_subset_left Finset.inter_subset_left conv_lhs => rw [hT] rw [Finset.card_union_of_disjoint hd] have hE_decomp : (E \ T).card + (E ∩ T).card = E.card := Finset.card_sdiff_add_card_inter E T have hE_identity : (E \ T).card + k = E.card + (B ∩ T).card := by omega have hdec1 : ∑ x ∈ (B ∪ E) \ T, c x = (∑ x ∈ B \ T, c x) + ∑ x ∈ E \ T, c x := by rw [Finset.union_sdiff_distrib, Finset.sum_union] exact hdisj.mono Finset.sdiff_subset Finset.sdiff_subset have hdec2 : (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x = ∑ x ∈ B, c x := by have := Finset.sum_sdiff (f := c) (s₁ := B ∩ T) (s₂ := B) Finset.inter_subset_left rw [Finset.sdiff_inter_self_left] at this exact this have hSE : ∑ x ∈ E \ T, c x ≤ ((E \ T).card : NNReal) * a := by calc ∑ x ∈ E \ T, c x ≤ ∑ x ∈ E \ T, a := Finset.sum_le_sum fun x hx => he₀_max x (Finset.mem_sdiff.mp hx).1 _ = ((E \ T).card : NNReal) * a := by rw [Finset.sum_const, nsmul_eq_mul] have hSBin : ((B ∩ T).card : NNReal) * a ≤ ∑ x ∈ B ∩ T, c x := by calc ((B ∩ T).card : NNReal) * a = ∑ x ∈ B ∩ T, a := by rw [Finset.sum_const, nsmul_eq_mul] _ ≤ ∑ x ∈ B ∩ T, c x := Finset.sum_le_sum fun x hx => h_cost e₀ he₀ x (Finset.mem_inter.mp hx).1 have hka : (k : NNReal) * a ≤ (∑ x ∈ B \ T, c x) + ∑ x ∈ B ∩ T, c x := by rw [hdec2] calc (k : NNReal) * a ≤ (B.card : NNReal) * a := by gcongr _ = ∑ x ∈ B, a := by rw [Finset.sum_const, nsmul_eq_mul] _ ≤ ∑ x ∈ B, c x := Finset.sum_le_sum fun x hx => h_cost e₀ he₀ x hx rw [hdec1, ← hdec2] exact block_insertion_residual_cost_bound_of_gt_aux (∑ x ∈ B \ T, c x) (∑ x ∈ B ∩ T, c x) (∑ x ∈ E \ T, c x) a k E.card (B ∩ T).card (E \ T).card hE_identity (by omega) hSE hSBin hka hk_pos