AFTD Auto-Formalizing Theoretical Domains

nae_p_schedule_no_uniform_adversary_rate

theoremverified

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.

  1. 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.

    line 5

      rintro ⟨C, hC⟩
  2. 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.

    line 6

    uses nae_p_schedule_not_at_adversary_rate

      obtain ⟨d, hd⟩ := nae_p_schedule_not_at_adversary_rate C
  3. The 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.

    line 7

    uses not_lt_of_ge

      exact (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

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)
See it in the graphDiscuss this resultChallenge it