integer_quadratic_seventeen_span_lower_bound
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$.
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$.
have h0 := h ⟨0, by decide⟩ have h8 := h ⟨8, by decide⟩ have h16 := h ⟨16, by decide⟩ norm_num at h0 h8 h16
$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.
omega
- The inequality $64q \le U - L$ relies on the second finite difference identity $P(16) - 2P(8) + P(0) = 128q \le 2(U - L)$, which the `omega` tactic verifies automatically without requiring the linear combination to be explicitly written out in the proof.
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 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