nae_p_schedule_potential
For every triple (d, θ, q) reachable by the specified p-computation rule schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(15/32)^d.
Statement
theorem nae_p_schedule_potential {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) :
0 ≤ θ ∧ θ ≤ Real.pi ∧ 0 ≤ q ∧
θ ≤ Real.pi * q * (15 / 32 : ℝ) ^ 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_contractionFor 0 ≤ θ ≤ π, arccos(1−(4/9)(1−cos θ)²) ≤ 15θ/16.
- nae_arccos_cos_leFor every nonnegative x, arccos(cos x) ≤ x.
- Used by 1
- nae_p_schedule_lower_boundEvery triple (d, θ, q) reachable by the specified p-computation rule schedule with θ ≥ π/2 has scheduled query count q at least…
The proof, explained
The theorem is proved by structural induction on the derivation of `nae_p_schedule d θ q`. In the base case, the initial state (d=0, θ=π, q=1) trivially satisfies all conditions. For composition, the angle contraction lemma `nae_angle_contraction` provides a factor of 15/16, which matches the factor of 2 * (15/32) produced by doubling the charge and advancing depth d to d + 1. Amplification and relaxation rules preserve the potential bound through trigonometric bound `nae_arccos_cos_le` and transitivity of inequality respectively.
The four invariants hold for the initial schedule: 0 ≤ π ≤ π, 0 ≤ 1, and π ≤ π * 1 * (15 / 32)⁰.
We proceed by induction on the derivation of the schedule `nae_p_schedule d θ q`. In the base case `initial`, the parameters are d = 0, θ = π, and q = 1. The goal simplifies directly using `Real.pi_pos.le` (0 ≤ π) and basic arithmetic, since (15/32)⁰ = 1 and π ≤ π holds reflexively.
uses
Real.pi_pos.leinduction h with | initial => simp [Real.pi_pos.le]
For the composition rule, the new angle satisfies 0 ≤ θ' ≤ π, the doubled charge satisfies 2q ≥ 0, and it suffices to show the potential bound for the updated state.
We unpack the induction hypothesis into 0 ≤ θ, θ ≤ π, 0 ≤ q, and θ ≤ πq(15/32)^d. For the composition rule, the new depth is d + 1, the new angle is θ' = arccos(1 - (4/9)(1 - cos θ)²), and the new charge is 2q. The bounds 0 ≤ θ' ≤ π hold generally for the arccosine function via `Real.arccos_nonneg` and `Real.arccos_le_pi`. Positivity arithmetic verifies 0 ≤ 2q from q ≥ 0, leaving only the potential upper bound on θ' to establish.
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 potential bound holds after composition: arccos(1 - (4/9)(1 - cos θ)²) ≤ π(2q)(15 / 32)^(d + 1).
By `nae_angle_contraction`, the new angle contracts to at most (15/16)θ. Multiplying the induction hypothesis θ ≤ πq(15/32)^d by 15/16 ≥ 0 via `mul_le_mul_of_nonneg_left` gives (15/16)θ ≤ (15/16)(πq(15/32)^d). Using `pow_succ` to expand (15/32)^(d+1) = (15/32)^d * (15/32), ring arithmetic shows that π(2q)(15/32)^(d+1) is identical to (15/16)(πq(15/32)^d). Applying transitivity `le_trans` completes the bound.
uses
nae_angle_contraction,mul_le_mul_of_nonneg_left,pow_succ,le_transhave hc := nae_angle_contraction θ ht0 htpi have hm := mul_le_mul_of_nonneg_left hpot (show (0 : ℝ) ≤ 15 / 16 by norm_num) have hid : Real.pi * (2 * q) * (15 / 32 : ℝ) ^ (d + 1) = (15 / 16 : ℝ) * (Real.pi * q * (15 / 32 : ℝ) ^ d) := by rw [pow_succ] ring rw [hid] exact le_trans hc hm
For the amplification rule, the new angle satisfies 0 ≤ arccos(cos(cθ)) ≤ π, the amplified charge satisfies cq ≥ 0, and it suffices to establish the potential inequality.
Unpacking the induction hypothesis, we note that c ≥ 0 since c > 0 is a positive natural number. The arccosine properties `Real.arccos_nonneg` and `Real.arccos_le_pi` ensure 0 ≤ arccos(cos(cθ)) ≤ π, and positivity arithmetic ensures cq ≥ 0 from c ≥ 0 and q ≥ 0.
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 potential bound holds after amplification: arccos(cos(cθ)) ≤ π(cq)(15 / 32)^d.
Since cθ ≥ 0 from c ≥ 0 and θ ≥ 0 via `mul_nonneg`, `nae_arccos_cos_le` bounds arccos(cos(cθ)) ≤ cθ. Multiplying the induction hypothesis θ ≤ πq(15/32)^d by c ≥ 0 via `mul_le_mul_of_nonneg_left` gives cθ ≤ c(πq(15/32)^d). Finally, `nlinarith` combines these inequalities with the algebraic identity c(πq(15/32)^d) = π(cq)(15/32)^d to conclude.
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
The induction step holds for the relaxation rule: reducing the angle to θ' with 0 ≤ θ' ≤ θ preserves all four invariants.
Unpacking the induction hypothesis gives 0 ≤ θ ≤ π, 0 ≤ q, and θ ≤ πq(15/32)^d. For the new angle θ', 0 ≤ θ' is assumed directly, θ' ≤ π follows by transitivity (`le_trans`) from θ' ≤ θ and θ ≤ π, the charge q ≥ 0 is unchanged, and the potential bound θ' ≤ πq(15/32)^d follows by transitivity (`le_trans`) from θ' ≤ θ and the induction hypothesis.
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- The constant π is non-negative, derived from the fact that π > 0.
Real.arccos_nonneg- The arccosine of any real number is non-negative: 0 ≤ arccos x for all x.
Real.arccos_le_pi- The arccosine of any real number is at most π: arccos x ≤ π for all x.
nae_angle_contraction- For any angle θ ∈ [0, π], the contraction inequality arccos(1 - (4/9)(1 - cos θ)²) ≤ (15/16)θ holds.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative value a ≥ 0 preserves the inequality: a * b ≤ a * c.
pow_succ- The (n + 1)-th power of an element equals its n-th power multiplied by the element: 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 ≥ 0, 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 {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) : 0 ≤ θ ∧ θ ≤ Real.pi ∧ 0 ≤ q ∧ θ ≤ Real.pi * q * (15 / 32 : ℝ) ^ 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 θ ht0 htpi have hm := mul_le_mul_of_nonneg_left hpot (show (0 : ℝ) ≤ 15 / 16 by norm_num) have hid : Real.pi * (2 * q) * (15 / 32 : ℝ) ^ (d + 1) = (15 / 16 : ℝ) * (Real.pi * q * (15 / 32 : ℝ) ^ 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⟩