nae_p_schedule_not_at_adversary_rate
For 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.
Statement
theorem nae_p_schedule_not_at_adversary_rate (C : ℝ) :
∃ d : ℕ, ∀ θ q : ℝ, nae_p_schedule d θ q → Real.pi / 2 ≤ θ →
C * (3 / Real.sqrt 2) ^ d < q- 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 3
- nae_p_scheduleThe least inductive relation on triples (d, θ, q), where d is a natural number and θ and q are real numbers, contains (0, π, 1) and is…
- 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…
- Used by 1
- nae_p_schedule_no_uniform_adversary_rateFor any two real sequences θ and q, if for every natural d the triple (d, θ(d), q(d)) is in nae_p_schedule and θ(d) ≥ π/2, then no real C…
The proof, explained
The proof shows that the adversary rate (3/√2)^d cannot upper bound the schedule parameter q by using an intermediate growth rate of 12/5. Since 12/5 > 3/√2, there exists a depth d at which the adversary bound is strictly smaller than (1/2) * (12/5)^d. By nae_p_schedule_lower_bound_strong, any schedule at depth d with θ ≥ π/2 satisfies q ≥ (1/2) * (12/5)^d, so transitivity gives C * (3/√2)^d < q.
There exists a depth d satisfying C * (3/√2)^d < (1/2) * (12/5)^d, reducing the goal to showing C * (3/√2)^d < q for all valid schedule parameters at depth d with θ ≥ π/2.
The lemma nae_p_rule_strong_rate_separation establishes that because the base 12/5 strictly exceeds 3/√2, the quantity (1/2) * (12/5)^d eventually overtakes C * (3/√2)^d for sufficiently large d. We choose such a depth d and its associated inequality hd as our witness.
uses
nae_p_rule_strong_rate_separationobtain ⟨d, hd⟩ := nae_p_rule_strong_rate_separation C refine ⟨d, ?_⟩
For any θ and q satisfying nae_p_schedule d θ q with θ ≥ π/2, the bound C * (3/√2)^d < q holds.
We fix θ, q and assume they satisfy nae_p_schedule d θ q with θ ≥ π/2. By nae_p_schedule_lower_bound_strong, we have (1/2) * (12/5)^d ≤ q. Chaining the strict inequality hd : C * (3/√2)^d < (1/2) * (12/5)^d with this lower bound via transitivity (lt_of_lt_of_le) concludes that C * (3/√2)^d < q.
uses
lt_of_lt_of_le,nae_p_schedule_lower_bound_strongintro θ q h hθ exact lt_of_lt_of_le hd (nae_p_schedule_lower_bound_strong h hθ)
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
nae_p_rule_strong_rate_separation- For any real constant C, there exists a depth d such that C * (3/√2)^d < (1/2) * (12/5)^d.
nae_p_schedule_lower_bound_strong- Any schedule state at depth d with angle θ ≥ π/2 satisfies (1/2) * (12/5)^d ≤ q.
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_schedule_not_at_adversary_rate (C : ℝ) : ∃ d : ℕ, ∀ θ q : ℝ, nae_p_schedule d θ q → Real.pi / 2 ≤ θ → C * (3 / Real.sqrt 2) ^ d < q := by obtain ⟨d, hd⟩ := nae_p_rule_strong_rate_separation C refine ⟨d, ?_⟩ intro θ q h hθ exact lt_of_lt_of_le hd (nae_p_schedule_lower_bound_strong h hθ)