scalar_repair_certificate_activation_optimality
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.
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)).
uses
mul_ne_zerohave hd : f * (f + s_star) ≠ 0 := mul_ne_zero hf_pos hdenom unfold scalar_repair_certificate
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).
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
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).
uses
eq_div_iff,add_divhave 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
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.
/-- 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