nae_p_schedule_no_uniform_adversary_rate
For 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 bounds q(d) by C(3/√2)^d for every natural d.
Statement
theorem nae_p_schedule_no_uniform_adversary_rate
(θ q : ℕ → ℝ)
(h : ∀ d, nae_p_schedule d (θ d) (q d) ∧ Real.pi / 2 ≤ θ d) :
¬ ∃ C : ℝ, ∀ d, q d ≤ C * (3 / Real.sqrt 2) ^ 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 2
- 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_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 proof is by contradiction: assuming there exists a constant C bounding the sequence by C(3/√2)^d for all d, we invoke nae_p_schedule_not_at_adversary_rate to obtain a depth d where any schedule state with angle at least π/2 must strictly exceed C(3/√2)^d. Specialising to θ(d) and q(d) yields q(d) > C(3/√2)^d, which directly contradicts the assumed upper bound q(d) ≤ C(3/√2)^d.
Assume for contradiction that there exists a real constant C such that q(d) ≤ C(3/√2)^d for all d ∈ ℕ.
We proceed by contradiction, introducing the hypothetical bounding constant C along with the hypothesis that the upper bound holds for all natural numbers d.
rintro ⟨C, hC⟩
There is a depth d at which any valid schedule triple with angle at least π/2 must satisfy q > C(3/√2)^d.
Applying nae_p_schedule_not_at_adversary_rate to C produces a natural number d such that any triple (d, θ, q) in the schedule with θ ≥ π/2 has q strictly greater than C(3/√2)^d.
uses
nae_p_schedule_not_at_adversary_rateobtain ⟨d, hd⟩ := nae_p_schedule_not_at_adversary_rate CThe adversary rate lower bound at depth d contradicts the assumed upper bound.
Specialising the property at depth d to θ(d) and q(d) gives C(3/√2)^d < q(d), since by assumption (d, θ(d), q(d)) is in the schedule and π/2 ≤ θ(d). This strictly contradicts the assumed upper bound q(d) ≤ C(3/√2)^d via not_lt_of_ge, completing the proof by contradiction.
uses
not_lt_of_geexact (not_lt_of_ge (hC d)) (hd (θ d) (q d) (h d).1 (h d).2)
nae_p_schedule_not_at_adversary_rate- For any real constant C, there exists a depth d such that every triple (d, θ, q) in nae_p_schedule with θ ≥ π/2 satisfies C(3/√2)^d < q.
not_lt_of_ge- In any preorder, if a ≤ b then b < a is impossible.
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_no_uniform_adversary_rate (θ q : ℕ → ℝ) (h : ∀ d, nae_p_schedule d (θ d) (q d) ∧ Real.pi / 2 ≤ θ d) : ¬ ∃ C : ℝ, ∀ d, q d ≤ C * (3 / Real.sqrt 2) ^ d := by rintro ⟨C, hC⟩ obtain ⟨d, hd⟩ := nae_p_schedule_not_at_adversary_rate C exact (not_lt_of_ge (hC d)) (hd (θ d) (q d) (h d).1 (h d).2)