op_153_positive_quadratic_eventually_strict_mono
A degree-2 integer polynomial taking positive values on all positive integers has positive leading coefficient and is eventually strictly increasing on the positive integers: there is M such that for all M ≤ n < m one has g(n) < g(m). Consequently, past M the values g(n) are pairwise distinct, the forbidden-difference set h(ℕ⁺) meets {1, ..., N} in at most as many elements as the index range {n : 1 ≤ n, g(n) ≤ N}, and the map n ↦ g(n) can be inverted.
Statement
theorem op_153_positive_quadratic_eventually_strict_mono (g : Polynomial ℤ) (hdeg : g.degree = 2)
(hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) :
∃ M : ℕ, ∀ n m : ℕ, M ≤ n → n < m → g.eval (n : ℤ) < g.eval (m : ℤ)- Source
- step towards op_153_subexp_bound_intersective_quadratic
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- op_153_positive_quadratic_eventually_quadratic_lower_boundA degree-2 integer polynomial strictly positive on positive integers satisfies $n^2 \le 2 g(n)$ for all sufficiently large positive…
The proof, explained
An integer quadratic polynomial $g(x) = c_2 x^2 + c_1 x + c_0$ taking positive values on all positive integers must have a positive leading coefficient $c_2 > 0$, since a negative leading coefficient would make $g(n) \le 0$ for large arguments (specifically at $n = |c_1| + |c_0| + 2$). With $c_2 \ge 1$, the difference between two values factors as $g(m) - g(n) = (m - n)(c_2(m + n) + c_1)$. Choosing the threshold $M = |c_1| + 1$ ensures that whenever $m > n \ge M$, both factors $m - n$ and $c_2(m + n) + c_1$ are strictly positive, proving that $g$ is strictly increasing past $M$.
The polynomial $g$ has natural degree 2 and expands at any integer $x$ as $g(x) = c_2 x^2 + c_1 x + c_0$.
Since $g$ has degree 2, its natural degree is 2 by `Polynomial.natDegree_eq_of_degree_eq_some`. Writing the evaluation of $g$ as a sum over the range $0, \ldots, 2$ using `Polynomial.eval_eq_sum_range` and expanding the sum using `Finset.sum_range_succ` gives $g(x) = c_2 x^2 + c_1 x + c_0$ after ring simplification.
uses
Polynomial.natDegree_eq_of_degree_eq_some,Polynomial.eval_eq_sum_range,Finset.sum_range_succhave hnd : g.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hdeg -- Expansion of `g` at an integer point. have hexp : ∀ x : ℤ, g.eval x = g.coeff 2 * x^2 + g.coeff 1 * x + g.coeff 0 := by intro x rw [Polynomial.eval_eq_sum_range, hnd] simp [Finset.sum_range_succ] ring
The leading coefficient $c_2$ of $g$ is nonzero.
If $g$ were the zero polynomial, its degree would be $\bot$ by `Polynomial.degree_zero`, contradicting the assumption that its degree is 2. Thus $g \ne 0$. A nonzero polynomial has a nonzero leading coefficient by `Polynomial.leadingCoeff_ne_zero.mpr`, and since the natural degree of $g$ is 2, `Polynomial.coeff_natDegree` identifies the coefficient $c_2$ with this leading coefficient.
uses
Polynomial.degree_zero,Polynomial.coeff_natDegree,Polynomial.leadingCoeff_ne_zero.mprhave ha_ne : g.coeff 2 ≠ 0 := by have hg0 : g ≠ 0 := by intro h rw [h, Polynomial.degree_zero] at hdeg exact absurd hdeg (by simp) rw [← hnd, Polynomial.coeff_natDegree] exact Polynomial.leadingCoeff_ne_zero.mpr hg0
The leading coefficient $c_2$ is strictly positive ($c_2 > 0$).
By trichotomy (`lt_or_gt_of_ne`), $c_2 < 0$ or $c_2 > 0$. Suppose for contradiction that $c_2 < 0$, which over the integers implies $c_2 \le -1$. Evaluating $g$ at the large positive integer $n = |c_1| + |c_0| + 2 \ge 2$, the quadratic term dominates: $c_2 n^2 \le -n^2$, while $c_1 n \le |c_1| n$ and $c_0 \le |c_0|$. Summing these bounds shows $g(n) \le -n^2 + |c_1|n + |c_0| \le 0$, contradicting the hypothesis that $g(n) > 0$ for all positive integers $n$. Hence, $c_2 > 0$.
uses
lt_or_gt_of_ne,abs_nonneg,sq_nonneg,le_refl,mul_nonneg,mul_le_mul_of_nonneg_right,le_abs_selfhave ha_pos : 0 < g.coeff 2 := by rcases lt_or_gt_of_ne ha_ne with hneg | hgt · exfalso obtain ⟨n, hn⟩ : ∃ n : ℕ, n = (g.coeff 1).natAbs + (g.coeff 0).natAbs + 2 := ⟨_, rfl⟩ have hnpos : 0 < n := by omega have hlt := hpos n hnpos rw [hexp] at hlt have hcast : (n : ℤ) = |g.coeff 1| + |g.coeff 0| + 2 := by simp [hn] have hc : g.coeff 2 ≤ -1 := by omega have hN2 : (2:ℤ) ≤ (n:ℤ) := by rw [hcast] have := abs_nonneg (g.coeff 1); have := abs_nonneg (g.coeff 0); linarith have hNpos : (0:ℤ) ≤ (n:ℤ) := by linarith have hnsq : (0:ℤ) ≤ (n:ℤ)^2 := sq_nonneg _ have hsq2 : (n:ℤ) * (|g.coeff 1| + |g.coeff 0| + 2) ≤ (n:ℤ)^2 := by have h : (0:ℤ) ≤ (n:ℤ) - (|g.coeff 1| + |g.coeff 0| + 2) := by rw [hcast]; ring_nf; exact le_refl 0 nlinarith [mul_nonneg h hNpos] have e1 : g.coeff 2 * (n:ℤ)^2 ≤ -(n:ℤ)^2 := by nlinarith [mul_nonneg (show (0:ℤ) ≤ -1 - g.coeff 2 by linarith) hnsq] have e2 : g.coeff 1 * (n:ℤ) ≤ |g.coeff 1| * (n:ℤ) := by nlinarith [mul_le_mul_of_nonneg_right (le_abs_self (g.coeff 1)) hNpos] have e3 : g.coeff 0 ≤ |g.coeff 0| := le_abs_self _ have hpc : (0:ℤ) ≤ |g.coeff 0| * ((n:ℤ) - 1) := by apply mul_nonneg (abs_nonneg _); linarith nlinarith [hlt, e1, e2, e3, hsq2, hpc, hN2] · exact hgt
For the threshold $M = |c_1| + 1$, the polynomial $g$ is strictly increasing on integers at least $M$: for all $M \le n < m$, $g(n) < g(m)$.
We choose $M = |c_1| + 1$. For $M \le n < m$, the difference of values factors algebraically as $g(m) - g(n) = (m - n)(c_2(m + n) + c_1)$. The first factor $m - n$ is strictly positive because $n < m$. For the second factor, since $c_2 \ge 1$ and $m + n > 2M > |c_1|$, we have $c_2(m + n) \ge m + n > |c_1| \ge -c_1$ using `neg_abs_le`, so $c_2(m + n) + c_1 > 0$. Being the product of two strictly positive integers, $g(m) - g(n)$ is strictly positive, establishing that $g(n) < g(m)$.
uses
Int.natCast_natAbs,mul_le_mul_of_nonneg_right,neg_abs_lerefine ⟨(g.coeff 1).natAbs + 1, ?_⟩ intro n m hMn hnm have hc1 : (1:ℤ) ≤ g.coeff 2 := by omega have hn : ((g.coeff 1).natAbs : ℤ) + 1 ≤ (n:ℤ) := by omega have hm : ((g.coeff 1).natAbs : ℤ) + 1 ≤ (m:ℤ) := by omega have hnmZ : (n:ℤ) < (m:ℤ) := by omega have habs : ((g.coeff 1).natAbs : ℤ) = |g.coeff 1| := Int.natCast_natAbs _ have hkey : g.eval (m:ℤ) - g.eval (n:ℤ) = ((m:ℤ) - (n:ℤ)) * (g.coeff 2 * ((m:ℤ) + (n:ℤ)) + g.coeff 1) := by rw [hexp, hexp]; ring have hdiff : (0:ℤ) < (m:ℤ) - (n:ℤ) := by linarith have hsum : (0:ℤ) ≤ (m:ℤ) + (n:ℤ) := by linarith have hstep : (1:ℤ) * ((m:ℤ) + (n:ℤ)) ≤ g.coeff 2 * ((m:ℤ) + (n:ℤ)) := mul_le_mul_of_nonneg_right hc1 hsum have hc1low : -|g.coeff 1| ≤ g.coeff 1 := neg_abs_le _ have hsecond : (0:ℤ) < g.coeff 2 * ((m:ℤ) + (n:ℤ)) + g.coeff 1 := by nlinarith [hstep, hc1low, hn, hm, habs] nlinarith [hkey, hdiff, hsecond]
Polynomial.natDegree_eq_of_degree_eq_some- A polynomial of degree $n$ (as an element of `WithBot ℕ`) has natural degree $n$.
Polynomial.eval_eq_sum_range- The evaluation of a polynomial $p$ at a point $x$ equals the sum of $c_i x^i$ for $i$ from $0$ to the natural degree of $p$.
Finset.sum_range_succ- A sum over $0 \le i < n + 1$ equals the sum over $0 \le i < n$ plus the $(n+1)$-th term.
Polynomial.degree_zero- The zero polynomial has degree $\bot$ ($-\infty$).
Polynomial.coeff_natDegree- The coefficient of a polynomial at its natural degree is its leading coefficient.
Polynomial.leadingCoeff_ne_zero.mpr- If a polynomial is nonzero, its leading coefficient is nonzero.
lt_or_gt_of_ne- In a linear order, two unequal elements satisfy $a < b$ or $b < a$.
abs_nonneg- The absolute value of any number is non-negative.
sq_nonneg- The square of any element in an ordered ring is non-negative.
le_refl- Every element is less than or equal to itself ($a \le a$).
mul_nonneg- The product of two non-negative numbers is non-negative.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality $b \le c$ by a non-negative element preserves the inequality.
le_abs_self- Every element is bounded above by its absolute value ($a \le |a|$).
Int.natCast_natAbs- The natural absolute value of an integer cast back to $\mathbb{Z}$ equals its integer absolute value ($|n|$).
neg_abs_le- Every element is bounded below by the negative of its absolute value ($-|a| \le a$).
- The proof relies on non-linear arithmetic automation (`nlinarith`) to close the inequality goals by combining explicit lower bounds and algebraic identities.
- The natural number arguments $n$ and $m$ are explicitly cast to integers $\mathbb{Z}$ to evaluate the integer polynomial $g$.
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.
/-- A degree-2 polynomial that is positive on the positive integers is eventually strictly increasing there (so its value set is thin and its values past a threshold are distinct). -/theorem op_153_positive_quadratic_eventually_strict_mono (g : Polynomial ℤ) (hdeg : g.degree = 2) (hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) : ∃ M : ℕ, ∀ n m : ℕ, M ≤ n → n < m → g.eval (n : ℤ) < g.eval (m : ℤ) := by have hnd : g.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hdeg -- Expansion of `g` at an integer point. have hexp : ∀ x : ℤ, g.eval x = g.coeff 2 * x^2 + g.coeff 1 * x + g.coeff 0 := by intro x rw [Polynomial.eval_eq_sum_range, hnd] simp [Finset.sum_range_succ] ring -- The leading coefficient (which is `g.coeff 2`) is nonzero. have ha_ne : g.coeff 2 ≠ 0 := by have hg0 : g ≠ 0 := by intro h rw [h, Polynomial.degree_zero] at hdeg exact absurd hdeg (by simp) rw [← hnd, Polynomial.coeff_natDegree] exact Polynomial.leadingCoeff_ne_zero.mpr hg0 -- Positivity on the positive integers forces a positive leading coefficient: an explicit -- large argument makes the polynomial negative otherwise. have ha_pos : 0 < g.coeff 2 := by rcases lt_or_gt_of_ne ha_ne with hneg | hgt · exfalso obtain ⟨n, hn⟩ : ∃ n : ℕ, n = (g.coeff 1).natAbs + (g.coeff 0).natAbs + 2 := ⟨_, rfl⟩ have hnpos : 0 < n := by omega have hlt := hpos n hnpos rw [hexp] at hlt have hcast : (n : ℤ) = |g.coeff 1| + |g.coeff 0| + 2 := by simp [hn] have hc : g.coeff 2 ≤ -1 := by omega have hN2 : (2:ℤ) ≤ (n:ℤ) := by rw [hcast] have := abs_nonneg (g.coeff 1); have := abs_nonneg (g.coeff 0); linarith have hNpos : (0:ℤ) ≤ (n:ℤ) := by linarith have hnsq : (0:ℤ) ≤ (n:ℤ)^2 := sq_nonneg _ have hsq2 : (n:ℤ) * (|g.coeff 1| + |g.coeff 0| + 2) ≤ (n:ℤ)^2 := by have h : (0:ℤ) ≤ (n:ℤ) - (|g.coeff 1| + |g.coeff 0| + 2) := by rw [hcast]; ring_nf; exact le_refl 0 nlinarith [mul_nonneg h hNpos] have e1 : g.coeff 2 * (n:ℤ)^2 ≤ -(n:ℤ)^2 := by nlinarith [mul_nonneg (show (0:ℤ) ≤ -1 - g.coeff 2 by linarith) hnsq] have e2 : g.coeff 1 * (n:ℤ) ≤ |g.coeff 1| * (n:ℤ) := by nlinarith [mul_le_mul_of_nonneg_right (le_abs_self (g.coeff 1)) hNpos] have e3 : g.coeff 0 ≤ |g.coeff 0| := le_abs_self _ have hpc : (0:ℤ) ≤ |g.coeff 0| * ((n:ℤ) - 1) := by apply mul_nonneg (abs_nonneg _); linarith nlinarith [hlt, e1, e2, e3, hsq2, hpc, hN2] · exact hgt -- The threshold is the size of the linear coefficient plus one. refine ⟨(g.coeff 1).natAbs + 1, ?_⟩ intro n m hMn hnm have hc1 : (1:ℤ) ≤ g.coeff 2 := by omega have hn : ((g.coeff 1).natAbs : ℤ) + 1 ≤ (n:ℤ) := by omega have hm : ((g.coeff 1).natAbs : ℤ) + 1 ≤ (m:ℤ) := by omega have hnmZ : (n:ℤ) < (m:ℤ) := by omega have habs : ((g.coeff 1).natAbs : ℤ) = |g.coeff 1| := Int.natCast_natAbs _ have hkey : g.eval (m:ℤ) - g.eval (n:ℤ) = ((m:ℤ) - (n:ℤ)) * (g.coeff 2 * ((m:ℤ) + (n:ℤ)) + g.coeff 1) := by rw [hexp, hexp]; ring have hdiff : (0:ℤ) < (m:ℤ) - (n:ℤ) := by linarith have hsum : (0:ℤ) ≤ (m:ℤ) + (n:ℤ) := by linarith have hstep : (1:ℤ) * ((m:ℤ) + (n:ℤ)) ≤ g.coeff 2 * ((m:ℤ) + (n:ℤ)) := mul_le_mul_of_nonneg_right hc1 hsum have hc1low : -|g.coeff 1| ≤ g.coeff 1 := neg_abs_le _ have hsecond : (0:ℤ) < g.coeff 2 * ((m:ℤ) + (n:ℤ)) + g.coeff 1 := by nlinarith [hstep, hc1low, hn, hm, habs] nlinarith [hkey, hdiff, hsecond]