AFTD Auto-Formalizing Theoretical Domains

block_insertion_residual_cost_bound

theoremverifiedformalization

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

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

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

    lines 9–16

    uses block_insertion_residual_cost_bound_of_le, le_max_left, one_mul

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

    lines 17–26

    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

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