AFTD Auto-Formalizing Theoretical Domains

nae_p_schedule_not_at_adversary_rate

theoremverified

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

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.

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

    lines 4–5

    uses nae_p_rule_strong_rate_separation

      obtain ⟨d, hd⟩ := nae_p_rule_strong_rate_separation C
      refine ⟨d, ?_⟩
  2. 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.

    lines 6–7

    uses lt_of_lt_of_le, nae_p_schedule_lower_bound_strong

      intro θ 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

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