AFTD Auto-Formalizing Theoretical Domains

subadditive_tangent_bound_step

theoremverified

If K_1 ≤ η_g, ℓ_g = η_g + K'_1, and K_x ≤ K_1 + K'_1 (x - 1), then η_g x + K_x ≤ 2 η_g + (x - 1) ℓ_g.

Statement

theorem subadditive_tangent_bound_step (η_g ℓ_g K1 K'1 x Kx : ℝ)
    (hℓ : ℓ_g = η_g + K'1)
    (hK1 : K1 ≤ η_g)
    (htan : Kx ≤ K1 + K'1 * (x - 1)) :
    η_g * x + Kx ≤ 2 * η_g + (x - 1) * ℓ_g
Source
arXiv:2610.21231, Appendix C
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For all real numbers $\eta_g$, $\ell_g$, $K_1$, $K'_1$, $x$, and $K_x$, if $\ell_g = \eta_g + K'_1$, $K_1 \le \eta_g$, and $K_x \le K_1 + K'_1(x - 1)$, then $\eta_g x + K_x \le 2\eta_g + (x - 1)\ell_g$.

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 establishes the inequality by a chain of bounds in a `calc` block. It first replaces K_x with its affine upper bound K_1 + K'_1 (x - 1) given by the tangent condition. It then algebraically rearranges this expression into K_1 + η_g + (x - 1) ℓ_g using the relation ℓ_g = η_g + K'_1. Finally, it bounds K_1 by η_g to arrive at 2 η_g + (x - 1) ℓ_g.

  1. η_g * x + Kx ≤ η_g * x + (K1 + K'1 * (x - 1))

    Using the tangent bound Kx ≤ K1 + K'1 * (x - 1) (the hypothesis `htan`), adding η_g * x to both sides yields the upper bound by linear arithmetic.

    lines 7–8

      calc
        η_g * x + Kx ≤ η_g * x + (K1 + K'1 * (x - 1)) := by linarith
  2. η_g * x + (K1 + K'1 * (x - 1)) = K1 + η_g + (x - 1) * ℓ_g

    The expression is algebraically rearranged into K1 + η_g + (x - 1) * (η_g + K'1) using ring arithmetic, and the factor η_g + K'1 is then replaced by ℓ_g via the hypothesis ℓ_g = η_g + K'1 (`hℓ`).

    lines 9–10

        _ = K1 + η_g + (x - 1) * (η_g + K'1) := by ring
        _ = K1 + η_g + (x - 1) * ℓ_g := by rw [← hℓ]
  3. K1 + η_g + (x - 1) * ℓ_g ≤ 2 * η_g + (x - 1) * ℓ_g, completing the proof

    Since K1 ≤ η_g by hypothesis `hK1`, we have K1 + η_g ≤ 2 * η_g. Adding (x - 1) * ℓ_g to both sides closes the final inequality via linear arithmetic.

    line 11

        _ ≤ 2 * η_g + (x - 1) * ℓ_g := by linarith

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

/-- Tangent bound bounding η_g x + K_s(x) by 2 η_g + (x - 1) ℓ_g. -/theorem subadditive_tangent_bound_step (η_g ℓ_g K1 K'1 x Kx : ℝ)    (hℓ : ℓ_g = η_g + K'1)    (hK1 : K1 ≤ η_g)    (htan : Kx ≤ K1 + K'1 * (x - 1)) :    η_g * x + Kx ≤ 2 * η_g + (x - 1) * ℓ_g := by  calc    η_g * x + Kx ≤ η_g * x + (K1 + K'1 * (x - 1)) := by linarith    _ = K1 + η_g + (x - 1) * (η_g + K'1) := by ring    _ = K1 + η_g + (x - 1) * ℓ_g := by rw [← hℓ]    _ ≤ 2 * η_g + (x - 1) * ℓ_g := by linarith
See it in the graphDiscuss this resultChallenge it