nae_p_schedule_potential_strong
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.
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).
uses
Real.pi_pos.leinduction h with | initial => simp [Real.pi_pos.le]
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.
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, ?_⟩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.
uses
nae_angle_contraction_strong,mul_le_mul_of_nonneg_left,pow_succ,le_transhave 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
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.
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, ?_⟩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.
uses
nae_arccos_cos_le,mul_nonneg,mul_le_mul_of_nonneg_lefthave ha := nae_arccos_cos_le ((c : ℝ) * θ) (mul_nonneg hc0 ht0) have hm := mul_le_mul_of_nonneg_left hpot hc0 nlinarith
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.
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
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_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⟩