AFTD Auto-Formalizing Theoretical Domains

block_insertion_residual_cost_bound_of_gt

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  1. 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.

    lines 10–21

    uses ne_of_gt, Nat.cast_add, add_mul

      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
  2. 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).

    lines 22–30

    uses le_div_iff₀, mul_comm

      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
  3. 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.

    lines 31–45

    uses div_self, add_div, Nat.cast_add

      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
  4. 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.

    lines 54–63

    uses Nat.cast_pos.mpr, Finset.nonempty_iff_ne_empty, Finset.card_empty, Finset.exists_max_image

      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₀
  5. 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.

    lines 64–70

    uses ciSup_le', Finset.card_le_card, Finset.subset_union_left, Nat.min_eq_left

      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
  6. 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|.

    lines 71–90

    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_inter

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

    lines 91–97

    uses Finset.union_sdiff_distrib, Finset.sum_union, Finset.sdiff_subset, Finset.sum_sdiff, Finset.inter_subset_left, Finset.sdiff_inter_self_left

      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
  8. 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.

    lines 98–108

    uses Finset.sum_le_sum, Finset.sum_const, nsmul_eq_mul

      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
  9. 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.

    lines 109–113

    uses block_insertion_residual_cost_bound_of_gt_aux

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

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

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
See it in the graphDiscuss this resultChallenge it