nae_p_rule_strong_rate_separation
For every real C there is a natural d such that C(3/√2)^d is strictly less than (1/2)(12/5)^d.
Statement
theorem nae_p_rule_strong_rate_separation (C : ℝ) :
∃ d : ℕ, C * (3 / Real.sqrt 2) ^ d < (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d- Source
- Consequence of nae_p_schedule_lower_bound_strong; related rules: arXiv:1211.0721, Section 3.3.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nae_p_rule_strong_base_exceeds_adversary_baseThe explicit base 12/5 is strictly greater than 3/√2.
- Used by 1
- nae_p_schedule_not_at_adversary_rateFor every real C there is a natural d such that every real θ and q satisfying nae_p_schedule d θ q and θ ≥ π/2 has q > C(3/√2)^d.
The proof, explained
The theorem compares the exponential growth of (3/√2)^d and (12/5)^d. Because 3/√2 < 12/5, the ratio r = (12/5) / (3/√2) is strictly greater than 1. Since powers of r grow without bound, there is an exponent d such that r^d > 2C, which upon clearing the denominator and dividing by 2 yields the desired inequality.
The ratio between the bases 12/5 and a = 3/√2 is strictly greater than 1.
Let a = 3/√2. Since a > 0 and a < 12/5 by nae_p_rule_strong_base_exceeds_adversary_base, dividing by a via one_lt_div shows that 1 < (12/5) / a.
uses
nae_p_rule_strong_base_exceeds_adversary_base,one_lt_divlet a : ℝ := 3 / Real.sqrt 2 have ha : 0 < a := by dsimp [a]; positivity have hab : a < (12 / 5 : ℝ) := nae_p_rule_strong_base_exceeds_adversary_base have hr : 1 < (12 / 5 : ℝ) / a := (one_lt_div ha).2 hab
There is an exponent d such that 2C < (12/5)^d / a^d.
Because the ratio (12/5) / a is strictly greater than 1, its powers eventually exceed any given real number by pow_unbounded_of_one_lt, yielding a natural number d such that 2C < ((12/5) / a)^d. Distributing the exponent over division via div_pow gives 2C < (12/5)^d / a^d.
uses
pow_unbounded_of_one_lt,div_powobtain ⟨d, hd⟩ := pow_unbounded_of_one_lt (2 * C) hr have hd' : 2 * C < (12 / 5 : ℝ) ^ d / a ^ d := by simpa [div_pow] using hd
Clearing the denominator gives 2C * a^d < (12/5)^d.
Since a > 0, its power a^d is also positive by pow_pos. Multiplying both sides by a^d using lt_div_iff₀ transforms the inequality into 2C * a^d < (12/5)^d.
uses
pow_pos,lt_div_iff₀have ha' : 0 < a ^ d := pow_pos ha d have hmul := (lt_div_iff₀ ha').mp hd'
The natural number d satisfies C * (3/√2)^d < (1/2) * (12/5)^d.
We provide d as the required witness. Expanding a back to 3/√2 in 2C * a^d < (12/5)^d and dividing through by 2 completes the proof via arithmetic.
refine ⟨d, ?_⟩ dsimp [a] at hmul nlinarith
nae_p_rule_strong_base_exceeds_adversary_base- The constant 3 / √2 is strictly less than 12/5.
one_lt_div- For b > 0, 1 < a / b if and only if b < a.
pow_unbounded_of_one_lt- In an Archimedean ordered semiring, if y > 1, then for any x there is a natural exponent n such that x < y^n.
div_pow- (a / b)^n = a^n / b^n for all elements in a division group and natural exponents n.
pow_pos- If a > 0, then a^n > 0 for every natural number n.
lt_div_iff₀- For c > 0, a < b / c if and only if a * c < b.
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_rate_separation (C : ℝ) : ∃ d : ℕ, C * (3 / Real.sqrt 2) ^ d < (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d := by let a : ℝ := 3 / Real.sqrt 2 have ha : 0 < a := by dsimp [a]; positivity have hab : a < (12 / 5 : ℝ) := nae_p_rule_strong_base_exceeds_adversary_base have hr : 1 < (12 / 5 : ℝ) / a := (one_lt_div ha).2 hab obtain ⟨d, hd⟩ := pow_unbounded_of_one_lt (2 * C) hr have hd' : 2 * C < (12 / 5 : ℝ) ^ d / a ^ d := by simpa [div_pow] using hd have ha' : 0 < a ^ d := pow_pos ha d have hmul := (lt_div_iff₀ ha').mp hd' refine ⟨d, ?_⟩ dsimp [a] at hmul nlinarith