AFTD Auto-Formalizing Theoretical Domains

scalar_sampler_ratio_bound

theoremverified

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.

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

    lines 8–17

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

    lines 18–25

    uses eq_or_ne, mul_zero, div_zero

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

    lines 26–30

    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 : ℝ)
  4. 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.

    lines 31–46

    uses Nat.factorial_pos

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

    lines 47–54

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

    lines 55–68

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

    lines 69–70

    uses div_le_div_iff₀

        rw [div_le_div_iff₀ hS_pos hM_pos]
        rw [hM_eq, hS_eq]
  8. 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.

    lines 71–83

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

    lines 84–87

        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.

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

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