AFTD Auto-Formalizing Theoretical Domains

op_153_positive_quadratic_eventually_strict_mono

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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

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

    lines 5–11

    uses Polynomial.natDegree_eq_of_degree_eq_some, Polynomial.eval_eq_sum_range, Finset.sum_range_succ

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

    lines 13–19

    uses Polynomial.degree_zero, Polynomial.coeff_natDegree, Polynomial.leadingCoeff_ne_zero.mpr

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

    lines 22–49

    uses lt_or_gt_of_ne, abs_nonneg, sq_nonneg, le_refl, mul_nonneg, mul_le_mul_of_nonneg_right, le_abs_self

      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
  4. 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)$.

    lines 51–68

    uses Int.natCast_natAbs, mul_le_mul_of_nonneg_right, neg_abs_le

      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]
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$).

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

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