nae_p_rule_base_exceeds_adversary_base
The explicit base 32/15 is strictly greater than 3/√2.
Statement
theorem nae_p_rule_base_exceeds_adversary_base :
3 / Real.sqrt 2 < (32 / 15 : ℝ)- Source
- arXiv:1211.0721, Section 3.3, p-computation rule analysis
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- nae_p_schedule_lower_boundEvery triple (d, θ, q) reachable by the specified p-computation rule schedule with θ ≥ π/2 has scheduled query count q at least…
The proof, explained
The inequality $3 / \sqrt{2} < 32 / 15$ is equivalent to $45 < 32\sqrt{2}$, which holds because $45^2 = 2025 < 2048 = 32^2 \cdot 2$. The proof establishes that $\sqrt{2} > 0$ and $(\sqrt{2})^2 = 2$, clears the denominator to reduce the goal to $3 < \frac{32}{15}\sqrt{2}$, and finishes using nonlinear arithmetic with the nonnegativity of $(32\sqrt{2} - 45)^2$.
$\sqrt{2} > 0$
Since $2 > 0$ (verified by numerical computation), `Real.sqrt_pos.2` establishes that $\sqrt{2}$ is strictly positive.
uses
Real.sqrt_pos.2have hspos : 0 < Real.sqrt 2 := Real.sqrt_pos.2 (by norm_num)
$(\sqrt{2})^2 = 2$
Since $2 \ge 0$ (verified by numerical computation), `Real.sq_sqrt` shows that squaring $\sqrt{2}$ gives $2$.
uses
Real.sq_sqrthave hs2 : (Real.sqrt 2) ^ 2 = 2 := Real.sq_sqrt (by norm_num)
It suffices to show that $3 < \frac{32}{15}\sqrt{2}$
Because $\sqrt{2} > 0$, multiplying both sides of $3 / \sqrt{2} < 32 / 15$ by $\sqrt{2}$ yields an equivalent inequality via `div_lt_iff₀`.
uses
div_lt_iff₀apply (div_lt_iff₀ hspos).2$3 < \frac{32}{15}\sqrt{2}$, completing the proof automation
The goal $3 < \frac{32}{15}\sqrt{2}$ is closed by nonlinear arithmetic (`nlinarith`), combining the relation $(\sqrt{2})^2 = 2$, the positivity of $\sqrt{2}$, and the nonnegativity of $(32\sqrt{2} - 45)^2$ from `sq_nonneg`.
uses
sq_nonnegnlinarith [sq_nonneg (32 * Real.sqrt 2 - 45)]
Real.sqrt_pos.2- The square root of a strictly positive real number is strictly positive.
Real.sq_sqrt- For any nonnegative real number $x$, $(\sqrt{x})^2 = x$.
div_lt_iff₀- For $c > 0$, $b / c < a$ if and only if $b < a \cdot c$.
sq_nonneg- The square of any element in an ordered semiring is nonnegative.
- The final inequality is verified by `nlinarith` using the fact that $(\sqrt{2})^2 = 2$ and the hint $(32\sqrt{2} - 45)^2 \ge 0$, which algebraic manipulation equates to $45^2 = 2025 < 2048 = 32^2 \cdot 2$.
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.
theorem nae_p_rule_base_exceeds_adversary_base : 3 / Real.sqrt 2 < (32 / 15 : ℝ) := by have hspos : 0 < Real.sqrt 2 := Real.sqrt_pos.2 (by norm_num) have hs2 : (Real.sqrt 2) ^ 2 = 2 := Real.sq_sqrt (by norm_num) apply (div_lt_iff₀ hspos).2 nlinarith [sq_nonneg (32 * Real.sqrt 2 - 45)]