AFTD Auto-Formalizing Theoretical Domains

scalar_repair_certificate_activation_optimality

theoremverifiedformalization

For all real numbers f, f_star, s_star, and sigma_star satisfying s_star = 1 - f_star, sigma_star = 9 - 16 * f_star + 6 * f_star², 2 * f_star³ - 4 * f_star² + 1 = 0, f ≠ 0, and f + s_star ≠ 0, the scalar repair certificate satisfies sigma_star - scalar_repair_certificate f s_star = sigma_star * (f - f_star)² / (f * (f + s_star)).

Statement

theorem scalar_repair_certificate_activation_optimality (f f_star s_star sigma_star : ℝ)
    (hs : s_star = 1 - f_star)
    (hsigma : sigma_star = 9 - 16 * f_star + 6 * f_star^2)
    (hcubic : 2 * f_star^3 - 4 * f_star^2 + 1 = 0)
    (hf_pos : f ≠ 0)
    (hdenom : f + s_star ≠ 0) :
    sigma_star - scalar_repair_certificate f s_star =
    sigma_star * (f - f_star)^2 / (f * (f + s_star))
Formalizes
arXiv:2611.06076:2505
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • scalar_repair_certificateThe scalar repair progress certificate K_f(H) for activation budget f and memory weight H is (1 + H) * (f + (2f - 1)H) / (f(f + H)).

Read back from the Lean

For any real numbers $f$, $f^*$, $s^*$, and $\sigma^*$, if: 1. $s^* = 1 - f^*$, 2. $\sigma^* = 9 - 16 f^* + 6 (f^*)^2$, 3. $2 (f^*)^3 - 4 (f^*)^2 + 1 = 0$, 4. $f \neq 0$, and 5. $f + s^* \neq 0$, then: $$\sigma^* - \text{scalar\_repair\_certificate}(f, s^*) = \frac{\sigma^* (f - f^*)^2}{f(f + s^*)}$$

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 clears denominators to reduce the statement to a polynomial identity. After substituting the definitions of s_star and sigma_star in terms of f_star, the difference between the two sides factors as (3 * f - 3 * f_star + 2) * (2 * f_star³ - 4 * f_star² + 1), which vanishes since f_star is a root of the given cubic polynomial. Dividing this polynomial identity by the non-zero denominator f * (f + s_star) and rearranging terms establishes the desired equality.

  1. The denominator f * (f + s_star) is non-zero, and scalar_repair_certificate is expanded in the goal.

    From the hypotheses that f ≠ 0 (hf_pos) and f + s_star ≠ 0 (hdenom), their product f * (f + s_star) is non-zero by mul_ne_zero. Unfolding the definition of scalar_repair_certificate f s_star replaces it in the goal with (1 + s_star) * (f + (2 * f - 1) * s_star) / (f * (f + s_star)).

    lines 10–11

    uses mul_ne_zero

      have hd : f * (f + s_star) ≠ 0 := mul_ne_zero hf_pos hdenom
      unfold scalar_repair_certificate
  2. sigma_star * (f * (f + s_star)) - (1 + s_star) * (f + (2 * f - 1) * s_star) = sigma_star * (f - f_star)²

    Substituting s_star = 1 - f_star (hs) and sigma_star = 9 - 16 * f_star + 6 * f_star² (hsigma), the difference between the left-hand side and the right-hand side factors as (3 * f - 3 * f_star + 2) * (2 * f_star³ - 4 * f_star² + 1). This vanishes because f_star satisfies the cubic equation 2 * f_star³ - 4 * f_star² + 1 = 0 (hcubic).

    lines 12–15

      have hpoly : sigma_star * (f * (f + s_star)) - (1 + s_star) * (f + (2 * f - 1) * s_star) =
          sigma_star * (f - f_star)^2 := by
        subst hs hsigma
        linear_combination (3 * f - 3 * f_star + 2) * hcubic
  3. sigma_star - scalar_repair_certificate f s_star = sigma_star * (f - f_star)² / (f * (f + s_star))

    Rearranging the polynomial identity hpoly isolates sigma_star * (f * (f + s_star)) on the left. Dividing both sides by the non-zero product f * (f + s_star) via eq_div_iff and splitting the resulting numerator sum using add_div expresses sigma_star as sigma_star * (f - f_star)² / (f * (f + s_star)) + (1 + s_star) * (f + (2 * f - 1) * s_star) / (f * (f + s_star)). Subtracting the certificate term from both sides completes the proof by linear arithmetic (linarith).

    lines 16–21

    uses eq_div_iff, add_div

      have h1 : sigma_star * (f * (f + s_star)) =
          sigma_star * (f - f_star)^2 + (1 + s_star) * (f + (2 * f - 1) * s_star) := by
        linear_combination hpoly
      rw [← eq_div_iff hd] at h1
      rw [add_div] at h1
      linarith
mul_ne_zero
The product of two non-zero elements in a type without zero divisors is non-zero.
eq_div_iff
For a non-zero divisor b, c = a / b if and only if c * b = a.
add_div
Division distributes over addition from the right: (a + b) / c = a / c + b / c.

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

/-- Optimality of f_star across activation parameters at the worst-case memory s_star. -/theorem scalar_repair_certificate_activation_optimality (f f_star s_star sigma_star : ℝ)    (hs : s_star = 1 - f_star)    (hsigma : sigma_star = 9 - 16 * f_star + 6 * f_star^2)    (hcubic : 2 * f_star^3 - 4 * f_star^2 + 1 = 0)    (hf_pos : f ≠ 0)    (hdenom : f + s_star ≠ 0) :    sigma_star - scalar_repair_certificate f s_star =    sigma_star * (f - f_star)^2 / (f * (f + s_star)) := by  have hd : f * (f + s_star) ≠ 0 := mul_ne_zero hf_pos hdenom  unfold scalar_repair_certificate  have hpoly : sigma_star * (f * (f + s_star)) - (1 + s_star) * (f + (2 * f - 1) * s_star) =      sigma_star * (f - f_star)^2 := by    subst hs hsigma    linear_combination (3 * f - 3 * f_star + 2) * hcubic  have h1 : sigma_star * (f * (f + s_star)) =      sigma_star * (f - f_star)^2 + (1 + s_star) * (f + (2 * f - 1) * s_star) := by    linear_combination hpoly  rw [← eq_div_iff hd] at h1  rw [add_div] at h1  linarith
See it in the graphDiscuss this resultChallenge it