AFTD Auto-Formalizing Theoretical Domains

nae_p_schedule_potential

theoremverified

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.

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

    lines 4–6

    uses Real.pi_pos.le

      induction h with
      | initial =>
          simp [Real.pi_pos.le]
  2. 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.

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

    lines 10–17

    uses nae_angle_contraction, mul_le_mul_of_nonneg_left, pow_succ, le_trans

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

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

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

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

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