AFTD Auto-Formalizing Theoretical Domains

integer_quadratic_seventeen_span_lower_bound

theoremverified

If all first 17 values of an integer quadratic with nonnegative leading coefficient q lie between L and U, then U−L is at least 64q.

Statement

theorem integer_quadratic_seventeen_span_lower_bound (q a b L U : ℤ) (hq : 0 ≤ q) (h : ∀ k : Fin 17, L ≤ q * (k.val : ℤ)^2 + a * k.val + b ∧ q * (k.val : ℤ)^2 + a * k.val + b ≤ U) : 64 * q ≤ U - L
Source
Endpoint calculation for the integer quadratic route to OP-1482.
Verified
13 Nov 2026
Axioms
Quot.soundpropext

The proof, explained

The proof samples the quadratic polynomial at three equally spaced points: $k = 0$, $k = 8$, and $k = 16$. The second finite difference $(q \cdot 16^2 + 16a + b) - 2(q \cdot 8^2 + 8a + b) + b$ eliminates the linear and constant terms, leaving $128q$. Because each of the three values is trapped in $[L, U]$, this second difference cannot exceed $2(U - L)$, which yields the bound $64q \le U - L$.

  1. The quadratic polynomial values at $k = 0, 8, 16$ satisfy $L \le b \le U$, $L \le 64q + 8a + b \le U$, and $L \le 256q + 16a + b \le U$.

    We specialize the assumption that the quadratic stays between $L$ and $U$ to the three indices $k = 0$, $k = 8$, and $k = 16$, each of which is verified to be strictly less than 17 by `decide`. Then `norm_num` evaluates the powers and products, simplifying the polynomial expressions at these points to $b$, $64q + 8a + b$, and $256q + 16a + b$.

    lines 2–5

      have h0 := h ⟨0, by decide⟩
      have h8 := h ⟨8, by decide⟩
      have h16 := h ⟨16, by decide⟩
      norm_num at h0 h8 h16
  2. $64q \le U - L$ automation

    Taking the second difference $P(16) - 2P(8) + P(0)$ eliminates both $a$ and $b$, leaving $256q - 2(64q) = 128q$. Since $P(16) \le U$, $P(0) \le U$, and $P(8) \ge L$ (so $-2P(8) \le -2L$), this sum is at most $2(U - L)$, yielding $128q \le 2(U - L)$ and hence $64q \le U - L$. The `omega` tactic discharges this integer linear arithmetic consequence automatically.

    line 6

      omega

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 integer_quadratic_seventeen_span_lower_bound (q a b L U : ℤ) (hq : 0 ≤ q) (h : ∀ k : Fin 17, L ≤ q * (k.val : ℤ)^2 + a * k.val + b ∧ q * (k.val : ℤ)^2 + a * k.val + b ≤ U) : 64 * q ≤ U - L := by  have h0 := h ⟨0, by decide⟩  have h8 := h ⟨8, by decide⟩  have h16 := h ⟨16, by decide⟩  norm_num at h0 h8 h16  omega
See it in the graphDiscuss this resultChallenge it