AFTD Auto-Formalizing Theoretical Domains

nae_p_schedule_potential_strong

theoremverified

For every triple (d, θ, q) in nae_p_schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(5/12)^d.

Statement

theorem nae_p_schedule_potential_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) :
    0 ≤ θ ∧ θ ≤ Real.pi ∧ 0 ≤ q ∧
      θ ≤ Real.pi * q * (5 / 12 : ℝ) ^ d
Source
arXiv:1211.0721, Section 3.3, p-computation rule analysis
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_angle_contraction_strongFor real θ with 0 ≤ θ ≤ π, arccos(1−(4/9)(1−cos θ)²) ≤ 5θ/6.
  • nae_arccos_cos_leFor every nonnegative x, arccos(cos x) ≤ x.
Used by 1
  • 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…

The proof, explained

The theorem is proved by induction on the derivation of the schedule nae_p_schedule d θ q. The base case (0, π, 1) holds directly since (5/12)⁰ = 1. In all inductive cases, the range constraints 0 ≤ θ ≤ π and q ≥ 0 are preserved by standard properties of the arccosine function. The potential bound θ ≤ π q (5/12)^d is maintained in the compose step through the strong contraction factor 5/6 combined with the identity 2 · (5/12) = 5/6, in the amplify step by scaling by c, and in the relax step by transitivity.

  1. The theorem holds for the initial schedule (0, π, 1).

    We proceed by induction on the derivation of nae_p_schedule d θ q. In the base case initial, the parameters are d = 0, θ = π, and q = 1. The goal reduces to 0 ≤ π ≤ π, 0 ≤ 1, and π ≤ π * 1 * (5/12)⁰ = π, which holds immediately since π is positive (Real.pi_pos.le).

    lines 4–6

    uses Real.pi_pos.le

      induction h with
      | initial =>
          simp [Real.pi_pos.le]
  2. In the compose step, the updated angle lies in [0, π] and the updated weight 2q is non-negative.

    We unpack the induction hypothesis for (d, θ, q) into the four bounds 0 ≤ θ, θ ≤ π, 0 ≤ q, and θ ≤ π q (5/12)^d. For the new triple with angle arccos(1 - (4/9)(1 - cos θ)²) and weight 2q, the angle lies in [0, π] by standard bounds on the arccosine function (Real.arccos_nonneg and Real.arccos_le_pi), and 2q ≥ 0 follows from q ≥ 0.

    lines 7–9

    uses Real.arccos_nonneg, Real.arccos_le_pi

      | @compose d θ q h ih =>
          rcases ih with ⟨ht0, htpi, hq0, hpot⟩
          refine ⟨Real.arccos_nonneg _, Real.arccos_le_pi _, by positivity, ?_⟩
  3. The updated angle in the compose step satisfies the potential bound for depth d + 1: arccos(1 - (4/9)(1 - cos θ)²) ≤ π (2q) (5/12)^(d + 1).

    By nae_angle_contraction_strong, the new angle is at most (5/6)θ. Multiplying the induction hypothesis θ ≤ π q (5/12)^d by 5/6 ≥ 0 via mul_le_mul_of_nonneg_left yields (5/6)θ ≤ (5/6)(π q (5/12)^d). Expanding (5/12)^(d+1) as (5/12)^d * (5/12) via pow_succ and using 2 * (5/12) = 5/6 shows that π (2q) (5/12)^(d + 1) = (5/6)(π q (5/12)^d). Transitivity of inequality (le_trans) combines these bounds to close the compose case.

    lines 10–17

    uses nae_angle_contraction_strong, mul_le_mul_of_nonneg_left, pow_succ, le_trans

          have hc := nae_angle_contraction_strong θ ht0 htpi
          have hm := mul_le_mul_of_nonneg_left hpot (show (0 : ℝ) ≤ 5 / 6 by norm_num)
          have hid : Real.pi * (2 * q) * (5 / 12 : ℝ) ^ (d + 1) =
              (5 / 6 : ℝ) * (Real.pi * q * (5 / 12 : ℝ) ^ d) := by
            rw [pow_succ]
            ring
          rw [hid]
          exact le_trans hc hm
  4. In the amplify step, the amplified angle lies in [0, π] and the amplified weight cq is non-negative.

    We unpack the induction hypothesis for (d, θ, q). Since c is a positive integer, c ≥ 0. The angle arccos(cos(cθ)) is in [0, π] by Real.arccos_nonneg and Real.arccos_le_pi, and cq is non-negative because both c and q are non-negative.

    lines 18–21

    uses Real.arccos_nonneg, Real.arccos_le_pi

      | @amplify d θ q c hc h ih =>
          rcases ih with ⟨ht0, htpi, hq0, hpot⟩
          have hc0 : (0 : ℝ) ≤ c := by positivity
          refine ⟨Real.arccos_nonneg _, Real.arccos_le_pi _, by positivity, ?_⟩
  5. The amplified angle satisfies the potential bound arccos(cos(cθ)) ≤ π (cq) (5/12)^d.

    Since c ≥ 0 and θ ≥ 0, their product cθ is non-negative by mul_nonneg, so nae_arccos_cos_le gives arccos(cos(cθ)) ≤ cθ. Multiplying the induction hypothesis θ ≤ π q (5/12)^d by c ≥ 0 via mul_le_mul_of_nonneg_left gives cθ ≤ c(π q (5/12)^d). Combining these two inequalities establishes the potential bound for the amplified triple.

    lines 22–24

    uses nae_arccos_cos_le, mul_nonneg, mul_le_mul_of_nonneg_left

          have ha := nae_arccos_cos_le ((c : ℝ) * θ) (mul_nonneg hc0 ht0)
          have hm := mul_le_mul_of_nonneg_left hpot hc0
          nlinarith
  6. In the relax step, the relaxed angle θ' satisfies all four bounds.

    Unpacking the induction hypothesis for θ, we have 0 ≤ θ' by assumption, θ' ≤ π by transitivity (le_trans) from θ' ≤ θ and θ ≤ π, 0 ≤ q unchanged, and θ' ≤ π q (5/12)^d by transitivity (le_trans) from θ' ≤ θ and the inductive potential bound.

    lines 25–27

    uses le_trans

      | @relax d θ q θ' hθ'0 hθ'le h ih =>
          rcases ih with ⟨ht0, htpi, hq0, hpot⟩
          exact ⟨hθ'0, le_trans hθ'le htpi, hq0, le_trans hθ'le hpot⟩
Real.pi_pos.le
π is non-negative (0 ≤ π), derived from π > 0
Real.arccos_nonneg
The arccosine function takes non-negative values: 0 ≤ arccos x for all x
Real.arccos_le_pi
The arccosine function is bounded above by π: arccos x ≤ π for all x
nae_angle_contraction_strong
For any angle θ with 0 ≤ θ ≤ π, the contraction map satisfies arccos(1 - (4/9)(1 - cos θ)²) ≤ (5/6)θ
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c on the left by a non-negative element a yields a * b ≤ a * c
pow_succ
In any monoid, a^(n + 1) = a^n * a
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c
nae_arccos_cos_le
For any non-negative real x, arccos(cos x) ≤ x
mul_nonneg
The product of two non-negative numbers is non-negative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * 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

theorem nae_p_schedule_potential_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) :    0 ≤ θ ∧ θ ≤ Real.pi ∧ 0 ≤ q ∧      θ ≤ Real.pi * q * (5 / 12 : ℝ) ^ d := by  induction h with  | initial =>      simp [Real.pi_pos.le]  | @compose d θ q h ih =>      rcases ih with ⟨ht0, htpi, hq0, hpot⟩      refine ⟨Real.arccos_nonneg _, Real.arccos_le_pi _, by positivity, ?_⟩      have hc := nae_angle_contraction_strong θ ht0 htpi      have hm := mul_le_mul_of_nonneg_left hpot (show (0 : ℝ) ≤ 5 / 6 by norm_num)      have hid : Real.pi * (2 * q) * (5 / 12 : ℝ) ^ (d + 1) =          (5 / 6 : ℝ) * (Real.pi * q * (5 / 12 : ℝ) ^ d) := by        rw [pow_succ]        ring      rw [hid]      exact le_trans hc hm  | @amplify d θ q c hc h ih =>      rcases ih with ⟨ht0, htpi, hq0, hpot⟩      have hc0 : (0 : ℝ) ≤ c := by positivity      refine ⟨Real.arccos_nonneg _, Real.arccos_le_pi _, by positivity, ?_⟩      have ha := nae_arccos_cos_le ((c : ℝ) * θ) (mul_nonneg hc0 ht0)      have hm := mul_le_mul_of_nonneg_left hpot hc0      nlinarith  | @relax d θ q θ' hθ'0 hθ'le h ih =>      rcases ih with ⟨ht0, htpi, hq0, hpot⟩      exact ⟨hθ'0, le_trans hθ'le htpi, hq0, le_trans hθ'le hpot⟩
See it in the graphDiscuss this resultChallenge it