nae_p_schedule_lower_bound
Every triple (d, θ, q) reachable by the specified p-computation rule schedule with θ ≥ π/2 has scheduled query count q at least (1/2)(32/15)^d.
Statement
theorem nae_p_schedule_lower_bound {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q)
(hθ : Real.pi / 2 ≤ θ) :
(1 / 2 : ℝ) * (32 / 15 : ℝ) ^ 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
- 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_p_schedule_potentialFor every triple (d, θ, q) reachable by the specified p-computation rule schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(15/32)^d.
- nae_p_rule_base_exceeds_adversary_baseThe explicit base 32/15 is strictly greater than 3/√2.
Read back from the Lean
For every natural number $d$ and all real numbers $\theta$ and $q$, if $(d, \theta, q)$ is derivable in the inductive relation nae_p_schedule, and if $\theta \ge \pi / 2$, then $\frac{1}{2} \left(\frac{32}{15}\right)^d \le 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 lower bound is obtained by combining the hypothesis θ ≥ π/2 with the schedule's potential bound θ ≤ π * q * (15/32)^d, yielding π/2 ≤ π * q * (15/32)^d. Multiplying both sides by (32/15)^d cancels the factor (15/32)^d, leaving (π/2) * (32/15)^d ≤ π * q. Dividing through by π > 0 gives the desired query bound q ≥ (1/2)(32/15)^d.
(π / 2) * (32 / 15)^d ≤ (π * q * (15 / 32)^d) * (32 / 15)^d
The potential invariant nae_p_schedule_potential guarantees θ ≤ π * q * (15 / 32)^d. Combining this with the hypothesis π / 2 ≤ θ by transitivity gives π / 2 ≤ π * q * (15 / 32)^d. Multiplying both sides by the positive quantity (32 / 15)^d preserves the inequality.
uses
nae_p_schedule_potential,le_trans,mul_le_mul_of_nonneg_righthave hp := (nae_p_schedule_potential h).2.2.2 have hrpos : 0 < (32 / 15 : ℝ) ^ d := by positivity have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le
(15 / 32)^d * (32 / 15)^d = 1
Combining the bases under a single exponent via mul_pow gives ((15 / 32) * (32 / 15))^d, which simplifies by arithmetic to 1^d = 1.
uses
mul_powhave hcancel : (15 / 32 : ℝ) ^ d * (32 / 15 : ℝ) ^ d = 1 := by rw [← mul_pow] norm_num
(π * q * (15 / 32)^d) * (32 / 15)^d = π * q
By associativity of multiplication, the factor (15 / 32)^d * (32 / 15)^d is grouped together. Replacing it with 1 and using mul_one leaves π * q.
uses
mul_assoc,mul_onehave hprod : (Real.pi * q * (15 / 32 : ℝ) ^ d) * (32 / 15 : ℝ) ^ d = Real.pi * q := by rw [mul_assoc, hcancel, mul_one]
(1 / 2) * (32 / 15)^d ≤ q
Rewriting the right-hand side of the scaled inequality produces (π / 2) * (32 / 15)^d ≤ π * q. Since π > 0, dividing both sides by π yields (1 / 2) * (32 / 15)^d ≤ q.
uses
Real.pi_posrw [hprod] at hmul nlinarith [Real.pi_pos]
nae_p_schedule_potential- Any configuration (d, θ, q) reachable under the schedule satisfies 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ π * q * (15 / 32)^d.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality b ≤ c on the right by a non-negative number a ≥ 0 preserves the inequality: b * a ≤ c * a.
mul_pow- In a commutative monoid, the power of a product is the product of powers: (a * b)^n = a^n * b^n.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_one- Multiplying an element on the right by 1 leaves it unchanged: a * 1 = a.
Real.pi_pos- The real number π 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
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_lower_bound {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) (hθ : Real.pi / 2 ≤ θ) : (1 / 2 : ℝ) * (32 / 15 : ℝ) ^ d ≤ q := by have hp := (nae_p_schedule_potential h).2.2.2 have hrpos : 0 < (32 / 15 : ℝ) ^ d := by positivity have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le have hcancel : (15 / 32 : ℝ) ^ d * (32 / 15 : ℝ) ^ d = 1 := by rw [← mul_pow] norm_num have hprod : (Real.pi * q * (15 / 32 : ℝ) ^ d) * (32 / 15 : ℝ) ^ d = Real.pi * q := by rw [mul_assoc, hcancel, mul_one] rw [hprod] at hmul nlinarith [Real.pi_pos]