nae_p_rule_strong_base_exceeds_adversary_base
The explicit base 12/5 is strictly greater than 3/√2.
Statement
theorem nae_p_rule_strong_base_exceeds_adversary_base :
3 / Real.sqrt 2 < (12 / 5 : ℝ)- Source
- arXiv:1211.0721, Section 3.3, p-computation rule analysis
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- nae_p_rule_strong_rate_separationFor every real C there is a natural d such that C(3/√2)^d is strictly less than (1/2)(12/5)^d.
- nae_p_schedule_lower_bound_strongFor every natural number d and real numbers θ and q, if nae_p_schedule d θ q holds and θ ≥ π/2, then q ≥ (1/2)(12/5)^d. Here…
The proof, explained
To prove that 3 / √2 < 12 / 5, we clear the denominator using the positivity of √2, which reduces the inequality to 3 < (12 / 5) * √2, or equivalently 15 < 12√2. Squaring both sides shows that this is equivalent to 225 < 288, which is true. In Lean, this comparison is finalized by `nlinarith` using (√2)² = 2 and the non-negativity of (12√2 - 15)².
√2 is strictly positive, and its square is 2.
Since 0 < 2, the square root of 2 is strictly positive by `Real.sqrt_pos.2`. Similarly, because 0 ≤ 2, `Real.sq_sqrt` shows that (√2)² = 2.
uses
Real.sqrt_pos.2,Real.sq_sqrthave 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)
It suffices to show that 3 < (12 / 5) * √2.
Because √2 > 0, multiplying both sides by √2 preserves the strict inequality by `div_lt_iff₀`, reducing 3 / √2 < 12 / 5 to 3 < (12 / 5) * √2.
uses
div_lt_iff₀apply (div_lt_iff₀ hspos).23 < (12 / 5) * √2, which completes the proof. automation
Multiplying through by 5, this is equivalent to 15 < 12√2, which holds because 15² = 225 < 288 = (12√2)². The nonlinear arithmetic tactic `nlinarith` verifies this using (√2)² = 2 and the non-negativity of the square (12√2 - 15)² ≥ 0 from `sq_nonneg`.
uses
sq_nonnegnlinarith [sq_nonneg (12 * Real.sqrt 2 - 15)]
Real.sqrt_pos.2- If a real number is strictly positive, its square root is strictly positive.
Real.sq_sqrt- For any non-negative real number x ≥ 0, the square of its square root equals x.
div_lt_iff₀- Given a strictly positive denominator c > 0 in a linearly ordered group with zero, b / c < a holds if and only if b < a * c.
sq_nonneg- The square of any element in an ordered semiring is non-negative: a² ≥ 0.
- The nonlinear arithmetic tactic `nlinarith` automatically closes the final inequality by combining the hypotheses with the non-negativity of the provided squared term without displaying intermediate algebraic steps.
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_strong_base_exceeds_adversary_base : 3 / Real.sqrt 2 < (12 / 5 : ℝ) := 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 (12 * Real.sqrt 2 - 15)]