AFTD Auto-Formalizing Theoretical Domains

nae_p_schedule_lower_bound_strong

theoremverifiedoriginal

For 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 nae_p_schedule is the least relation containing (0, π, 1) and closed under: composition to (d+1, arccos(1−(4/9)(1−cos θ)²), 2q); amplification to (d, arccos(cos(cθ)), cq) for positive natural c; and relaxation to (d, θ′, q) for real 0 ≤ θ′ ≤ θ. The quantity q is the budget prescribed by these operations, not a lower bound on arbitrary quantum circuits.

Statement

theorem nae_p_schedule_lower_bound_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q)
    (hθ : Real.pi / 2 ≤ θ) :
    (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d ≤ q
Related work
arXiv:1211.0721, Section 3.3, p-computation rule analysis
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For any natural number d and any real numbers θ and q, if nae_p_schedule d θ q holds and θ ≥ π / 2, then (1 / 2) * (12 / 5) ^ d ≤ q.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The schedule potential invariant provides an upper bound on θ in terms of the budget q, namely θ ≤ π * q * (5 / 12)^d. Combining this with the hypothesis θ ≥ π / 2 yields π / 2 ≤ π * q * (5 / 12)^d. Multiplying both sides by (12 / 5)^d cancels the factor (5 / 12)^d, resulting in (π / 2) * (12 / 5)^d ≤ π * q. Dividing through by π > 0 concludes that q ≥ (1 / 2) * (12 / 5)^d.

  1. (π / 2) * (12 / 5)^d ≤ (π * q * (5 / 12)^d) * (12 / 5)^d

    The schedule invariant (nae_p_schedule_potential_strong) bounds the angle by θ ≤ π * q * (5 / 12)^d. Combining this with the assumption π / 2 ≤ θ (hθ) by transitivity (le_trans) yields π / 2 ≤ π * q * (5 / 12)^d. Since (12 / 5)^d > 0 (by positivity), multiplying both sides by this positive factor preserves the inequality (mul_le_mul_of_nonneg_right).

    lines 4–6

    uses nae_p_schedule_potential_strong, le_trans, mul_le_mul_of_nonneg_right

      have hp := (nae_p_schedule_potential_strong h).2.2.2
      have hrpos : 0 < (12 / 5 : ℝ) ^ d := by positivity
      have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le
  2. (5 / 12)^d * (12 / 5)^d = 1

    Distributing the exponent across multiplication (mul_pow) rewrites the product as ((5 / 12) * (12 / 5))^d. The base simplifies to 1, and 1^d = 1.

    lines 7–9

    uses mul_pow

      have hcancel : (5 / 12 : ℝ) ^ d * (12 / 5 : ℝ) ^ d = 1 := by
        rw [← mul_pow]
        norm_num
  3. (π / 2) * (12 / 5)^d ≤ π * q

    Regrouping factors on the right-hand side using associativity (mul_assoc) yields π * q * ((5 / 12)^d * (12 / 5)^d), which simplifies to π * q * 1 and thus π * q (mul_one). Replacing the right-hand side in the earlier inequality gives (π / 2) * (12 / 5)^d ≤ π * q.

    lines 10–12

    uses mul_assoc, mul_one

      have hprod : (Real.pi * q * (5 / 12 : ℝ) ^ d) * (12 / 5 : ℝ) ^ d = Real.pi * q := by
        rw [mul_assoc, hcancel, mul_one]
      rw [hprod] at hmul
  4. (1 / 2) * (12 / 5)^d ≤ q

    Since π > 0 (Real.pi_pos), dividing both sides of (π / 2) * (12 / 5)^d ≤ π * q by π yields the desired lower bound (1 / 2) * (12 / 5)^d ≤ q.

    line 13

    uses Real.pi_pos

      nlinarith [Real.pi_pos]
nae_p_schedule_potential_strong
for any valid schedule (d, θ, q), the bound θ ≤ π * q * (5 / 12)^d holds along with 0 ≤ θ ≤ π and 0 ≤ q
mul_le_mul_of_nonneg_right
multiplying both sides of an inequality by a non-negative value preserves the inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * a
le_trans
the transitive relation for inequalities: if a ≤ b and b ≤ c, then a ≤ c
mul_pow
a power of a product is the product of the powers: (a * b)^n = a^n * b^n
mul_assoc
multiplication is associative: (a * b) * c = a * (b * c)
mul_one
multiplying any value by 1 leaves it unchanged: a * 1 = a
Real.pi_pos
the constant π is strictly positive: 0 < π

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_lower_bound_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q)    (hθ : Real.pi / 2 ≤ θ) :    (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d ≤ q := by  have hp := (nae_p_schedule_potential_strong h).2.2.2  have hrpos : 0 < (12 / 5 : ℝ) ^ d := by positivity  have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le  have hcancel : (5 / 12 : ℝ) ^ d * (12 / 5 : ℝ) ^ d = 1 := by    rw [← mul_pow]    norm_num  have hprod : (Real.pi * q * (5 / 12 : ℝ) ^ d) * (12 / 5 : ℝ) ^ d = Real.pi * q := by    rw [mul_assoc, hcancel, mul_one]  rw [hprod] at hmul  nlinarith [Real.pi_pos]
See it in the graphDiscuss this resultChallenge it