scalar_sampler_ratio_bound
For integers q ≥ 3, r ≥ 1 and 0 ≤ j < q, the parameters m_j = 1 + (q-1)!(12r(q-1) + j), D = ∏_{i=0}^{q-1} m_i, M = 12r(D/m_0)^2, and S = (12r-1) m_0 (D/m_0)^2 satisfy m_j / S ≤ 2 / M.
Statement
theorem scalar_sampler_ratio_bound (q r : ℕ) (hq : 3 ≤ q) (hr : 1 ≤ r) (j : ℕ) (hj : j < q) : let m : ℕ → ℤ := fun i => 1 + (q - 1).factorial * (12 * r * (q - 1) + i) let D : ℤ := ∏ i ∈ Finset.range q, m i let M : ℤ := 12 * r * (D / m 0) ^ 2 let S : ℤ := (12 * r - 1) * m 0 * (D / m 0) ^ 2 (m j : ℝ) / (S : ℝ) ≤ 2 / (M : ℝ)
- Source
- arXiv:2611.13281, Lemma 2.1, equation (7)
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any natural numbers $q$ and $r$ with $3 \le q$ and $1 \le r$, and for any natural number $j$ with $j < q$: let $m : \mathbb{N} \to \mathbb{Z}$ be defined by $m(i) = 1 + (q - 1)! \cdot (12 \cdot r \cdot (q - 1) + i)$ (where natural subtraction is used for $q - 1$), let $D \in \mathbb{Z}$ be the product $\prod_{i = 0}^{q - 1} m(i)$ (i.e., over $i \in \text{range}(q)$), let $M \in \mathbb{Z}$ be $12 \cdot r \cdot (D / m(0))^2$ (using integer division), and let $S \in \mathbb{Z}$ be $(12 \cdot r - 1) \cdot m(0) \cdot (D / m(0))^2$. Then, when cast to the real numbers, $$\frac{m(j)}{S} \le \frac{2}{M}.$$
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 proof establishes m_j / S ≤ 2 / M by factoring out the shared quantity K = (D / m_0)² from both M = 12 r K and S = (12 r - 1) m_0 K. When K = 0, both sides vanish under Lean's convention for division by zero and the inequality holds trivially. When K > 0, clearing denominators reduces the claim to 12 r m_j ≤ 2(12 r - 1) m_0, which is proved by expanding the difference into a sum of manifestly non-negative terms using r ≥ 1, q ≥ 3, and j < q.
The parameters M and S are expressed in terms of the common factor K = (D / m 0)², giving M = 12 r K and S = (12 r - 1) m₀ K.
We introduce the definitions and set K = (D / m 0)² as a real number. Expanding M and S and pushing the integer casts into ℝ, ring simplification shows M = 12 r K and S = (12 r - 1) m₀ K.
intro m D M S set K := ((D / m 0 : ℤ) : ℝ) ^ 2 have hM_eq : (M : ℝ) = 12 * (r : ℝ) * K := by dsimp [M, K] push_cast ring have hS_eq : (S : ℝ) = (12 * (r : ℝ) - 1) * (m 0 : ℝ) * K := by dsimp [S, K] push_cast ring
The ratio bound holds in the degenerate case where D / m 0 = 0.
We split into cases using eq_or_ne according to whether D / m 0 = 0. If D / m 0 = 0, then K = 0² = 0. Substituting K = 0 into hM_eq and hS_eq via mul_zero gives M = 0 and S = 0. By Lean's division-by-zero rule (div_zero), both sides of m_j / S ≤ 2 / M evaluate to 0, which satisfies 0 ≤ 0.
uses
eq_or_ne,mul_zero,div_zerorcases eq_or_ne ((D / m 0 : ℤ) : ℝ) 0 with h | h · have hK0 : K = 0 := by dsimp [K] rw [h] ring have hS0 : (S : ℝ) = 0 := by rw [hS_eq, hK0, mul_zero] have hM0 : (M : ℝ) = 0 := by rw [hM_eq, hK0, mul_zero] rw [hS0, hM0, div_zero, div_zero]
In the non-zero case, K > 0, and real variables R = r, Q = q - 1, J = j, and F = (q - 1)! are introduced.
When D / m 0 ≠ 0, sq_pos_of_ne_zero guarantees that K = (D / m 0)² > 0. We then introduce real-valued names R, Q, J, and F for convenience in the upcoming inequalities.
uses
sq_pos_of_ne_zero· have hK : 0 < K := sq_pos_of_ne_zero h set R := (r : ℝ) set Q := (q : ℝ) - 1 set J := (j : ℝ) set F := ((q - 1).factorial : ℝ)
The parameters satisfy the real inequalities R ≥ 1, Q ≥ 2, F ≥ 1, and J ≤ Q.
The hypothesis r ≥ 1 casts directly to R ≥ 1. From q ≥ 3, we have Q = q - 1 ≥ 2. Because factorials are strictly positive (Nat.factorial_pos), F = (q - 1)! ≥ 1. Finally, j < q means j + 1 ≤ q, which rearranges to J ≤ Q.
uses
Nat.factorial_poshave hR : 1 ≤ R := by dsimp [R] exact_mod_cast hr have hQ : 2 ≤ Q := by have : (3 : ℝ) ≤ (q : ℝ) := by exact_mod_cast hq dsimp [Q] linarith have hF : 1 ≤ F := by have : 1 ≤ (q - 1).factorial := Nat.factorial_pos (q - 1) dsimp [F] exact_mod_cast this have hJ : J ≤ Q := by have : j + 1 ≤ q := hj have : (j : ℝ) + 1 ≤ (q : ℝ) := by exact_mod_cast this dsimp [J, Q] linarith
The sequence values m 0 and m j equal 1 + 12 R Q F and 1 + F (12 R Q + J), respectively.
Evaluating the definition of m at 0 and j, pushing integer casts to the reals, and simplifying with polynomial ring normalization establishes the explicit real formulas for m 0 and m j.
have hm0 : (m 0 : ℝ) = 1 + F * (12 * R * Q) := by dsimp [m, F, R, Q] push_cast ring have hmj : (m j : ℝ) = 1 + F * (12 * R * Q + J) := by dsimp [m, F, R, Q, J] push_cast ring
The real numbers m 0, M, and S are all strictly positive.
Since R, Q, and F are all at least 1, m 0 = 1 + 12 R Q F is positive. Since K > 0 and R > 0, M = 12 R K > 0. Finally, 12 R - 1 ≥ 11 > 0, so S = (12 R - 1) m 0 K is positive as a product of positive numbers.
have hm0_pos : 0 < (m 0 : ℝ) := by rw [hm0] have : 0 < F := by linarith have : 0 < R := by linarith have : 0 < Q := by linarith positivity have hM_pos : 0 < (M : ℝ) := by rw [hM_eq] have : 0 < R := by linarith positivity have hS_pos : 0 < (S : ℝ) := by rw [hS_eq] have : 0 < 12 * R - 1 := by linarith positivity
The goal m j / S ≤ 2 / M is transformed by clearing denominators into m j (12 r K) ≤ 2 ((12 r - 1) m 0 K).
Because S > 0 and M > 0, div_le_div_iff₀ clears fractions to (m j) M ≤ 2 S. Rewriting with the identities M = 12 r K and S = (12 r - 1) m 0 K yields the product inequality.
uses
div_le_div_iff₀rw [div_le_div_iff₀ hS_pos hM_pos] rw [hM_eq, hS_eq]
The core inequality (m j)(12 R) ≤ 2(12 R - 1)(m 0) holds.
Expanding the difference 2(12 R - 1)(m 0) - (m j)(12 R) using the formulas for m 0 and m j yields the identity (12 R - 2) + (12 R - 3)(12 R Q F) + 12 R F (Q - J). Since R ≥ 1, we have 12 R - 2 ≥ 10 and 12 R - 3 ≥ 9; since Q ≥ J, we have Q - J ≥ 0. Every summand is therefore non-negative, proving that the difference is non-negative.
have h_diff : (m j : ℝ) * (12 * R) ≤ 2 * (12 * R - 1) * (m 0 : ℝ) := by have hid : 2 * (12 * R - 1) * (m 0 : ℝ) - (m j : ℝ) * (12 * R) = (12 * R - 2) + (12 * R - 3) * (12 * R * Q * F) + 12 * R * F * (Q - J) := by rw [hm0, hmj] ring have h1 : 0 ≤ 12 * R - 2 := by linarith have h2 : 0 ≤ 12 * R - 3 := by linarith have h3 : 0 ≤ 12 * R * Q * F := by positivity have h4 : 0 ≤ 12 * R * F := by positivity have h5 : 0 ≤ Q - J := by linarith have h_nonneg : 0 ≤ (12 * R - 2) + (12 * R - 3) * (12 * R * Q * F) + 12 * R * F * (Q - J) := by positivity linarith
Multiplying by K completes the inequality m j (12 r K) ≤ 2 ((12 r - 1) m 0 K).
A calculational chain factors out K, applies the core inequality (m j)(12 R) ≤ 2(12 R - 1)(m 0) scaled by K ≥ 0 via non-linear arithmetic, and regroups terms into 2 ((12 r - 1) m 0 K).
calc (m j : ℝ) * (12 * (r : ℝ) * K) _ = ((m j : ℝ) * (12 * R)) * K := by ring _ ≤ (2 * (12 * R - 1) * (m 0 : ℝ)) * K := by nlinarith _ = 2 * ((12 * (r : ℝ) - 1) * (m 0 : ℝ) * K) := by ring
eq_or_ne- For any two elements x and y of a type, either x = y or x ≠ y.
mul_zero- Multiplying any ring element by zero yields zero: a * 0 = 0.
div_zero- In a group with zero, dividing any element by zero yields zero: a / 0 = 0.
sq_pos_of_ne_zero- In a strictly ordered semiring, the square of any non-zero element is strictly positive: a ≠ 0 implies a² > 0.
Nat.factorial_pos- The factorial of any natural number is strictly positive: n! > 0.
div_le_div_iff₀- For strictly positive denominators b and d, a / b ≤ c / d is equivalent to a * d ≤ c * b.
- In Lean, division by zero is defined to equal zero (x / 0 = 0). As a result, the degenerate branch where D / m 0 = 0 evaluates trivially to 0 ≤ 0 rather than being undefined.
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.
/-- Ratio bound m_j / S ≤ 2 / M for the scalar quadratic sampler parameters. -/theorem scalar_sampler_ratio_bound (q r : ℕ) (hq : 3 ≤ q) (hr : 1 ≤ r) (j : ℕ) (hj : j < q) : let m : ℕ → ℤ := fun i => 1 + (q - 1).factorial * (12 * r * (q - 1) + i) let D : ℤ := ∏ i ∈ Finset.range q, m i let M : ℤ := 12 * r * (D / m 0) ^ 2 let S : ℤ := (12 * r - 1) * m 0 * (D / m 0) ^ 2 (m j : ℝ) / (S : ℝ) ≤ 2 / (M : ℝ) := by intro m D M S set K := ((D / m 0 : ℤ) : ℝ) ^ 2 have hM_eq : (M : ℝ) = 12 * (r : ℝ) * K := by dsimp [M, K] push_cast ring have hS_eq : (S : ℝ) = (12 * (r : ℝ) - 1) * (m 0 : ℝ) * K := by dsimp [S, K] push_cast ring rcases eq_or_ne ((D / m 0 : ℤ) : ℝ) 0 with h | h · have hK0 : K = 0 := by dsimp [K] rw [h] ring have hS0 : (S : ℝ) = 0 := by rw [hS_eq, hK0, mul_zero] have hM0 : (M : ℝ) = 0 := by rw [hM_eq, hK0, mul_zero] rw [hS0, hM0, div_zero, div_zero] · have hK : 0 < K := sq_pos_of_ne_zero h set R := (r : ℝ) set Q := (q : ℝ) - 1 set J := (j : ℝ) set F := ((q - 1).factorial : ℝ) have hR : 1 ≤ R := by dsimp [R] exact_mod_cast hr have hQ : 2 ≤ Q := by have : (3 : ℝ) ≤ (q : ℝ) := by exact_mod_cast hq dsimp [Q] linarith have hF : 1 ≤ F := by have : 1 ≤ (q - 1).factorial := Nat.factorial_pos (q - 1) dsimp [F] exact_mod_cast this have hJ : J ≤ Q := by have : j + 1 ≤ q := hj have : (j : ℝ) + 1 ≤ (q : ℝ) := by exact_mod_cast this dsimp [J, Q] linarith have hm0 : (m 0 : ℝ) = 1 + F * (12 * R * Q) := by dsimp [m, F, R, Q] push_cast ring have hmj : (m j : ℝ) = 1 + F * (12 * R * Q + J) := by dsimp [m, F, R, Q, J] push_cast ring have hm0_pos : 0 < (m 0 : ℝ) := by rw [hm0] have : 0 < F := by linarith have : 0 < R := by linarith have : 0 < Q := by linarith positivity have hM_pos : 0 < (M : ℝ) := by rw [hM_eq] have : 0 < R := by linarith positivity have hS_pos : 0 < (S : ℝ) := by rw [hS_eq] have : 0 < 12 * R - 1 := by linarith positivity rw [div_le_div_iff₀ hS_pos hM_pos] rw [hM_eq, hS_eq] have h_diff : (m j : ℝ) * (12 * R) ≤ 2 * (12 * R - 1) * (m 0 : ℝ) := by have hid : 2 * (12 * R - 1) * (m 0 : ℝ) - (m j : ℝ) * (12 * R) = (12 * R - 2) + (12 * R - 3) * (12 * R * Q * F) + 12 * R * F * (Q - J) := by rw [hm0, hmj] ring have h1 : 0 ≤ 12 * R - 2 := by linarith have h2 : 0 ≤ 12 * R - 3 := by linarith have h3 : 0 ≤ 12 * R * Q * F := by positivity have h4 : 0 ≤ 12 * R * F := by positivity have h5 : 0 ≤ Q - J := by linarith have h_nonneg : 0 ≤ (12 * R - 2) + (12 * R - 3) * (12 * R * Q * F) + 12 * R * F * (Q - J) := by positivity linarith calc (m j : ℝ) * (12 * (r : ℝ) * K) _ = ((m j : ℝ) * (12 * R)) * K := by ring _ ≤ (2 * (12 * R - 1) * (m 0 : ℝ)) * K := by nlinarith _ = 2 * ((12 * (r : ℝ) - 1) * (m 0 : ℝ) * K) := by ring