AFTD Auto-Formalizing Theoretical Domains

op_153_positive_quadratic_eventually_quadratic_lower_bound

theoremverified

A degree-2 integer polynomial strictly positive on positive integers satisfies $n^2 \le 2 g(n)$ for all sufficiently large positive integers $n$.

Statement

theorem op_153_positive_quadratic_eventually_quadratic_lower_bound (g : Polynomial ℤ)
    (hdeg : g.degree = 2) (hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) :
    ∃ M : ℕ, ∀ n : ℕ, M ≤ n → (n : ℤ) ^ 2 ≤ 2 * g.eval (n : ℤ)
Source
step towards op_153_eventually_subexp_bound_positive_quadratic
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

The proof expands the quadratic polynomial g(x) = c₂ x² + c₁ x + c₀ and first shows that its leading coefficient c₂ must be positive: if c₂ ≤ -1, evaluating g at n = |c₁| + |c₀| + 2 would make g(n) negative, contradicting the hypothesis that g is strictly positive on positive integers. With c₂ ≥ 1, the quadratic term 2 c₂ n² - n² ≥ n² grows faster than the linear and constant terms. By choosing the threshold M = 2|c₁| + 2|c₀| + 1, any n ≥ M ensures that n² ≥ (2|c₁| + 1)n ≥ -2 c₁ n - 2 c₀, which guarantees n² ≤ 2 g(n).

  1. The polynomial g has natural degree 2 and evaluates at any integer x as g(x) = c₂ x² + c₁ x + c₀, where cᵢ is the i-th coefficient of g.

    Since the degree of g is 2, Polynomial.natDegree_eq_of_degree_eq_some ensures that its natural degree is 2. The evaluation g(x) is expanded as the sum ∑_{i=0}^2 cᵢ xⁱ using Polynomial.eval_eq_sum_range, unrolled via Finset.sum_range_succ, and rearranged algebraically with ring.

    lines 5–10

    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
      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₂ = g.coeff 2 is non-zero.

    If g were the zero polynomial, its degree would be ⊥ by Polynomial.degree_zero, contradicting that its degree is 2. Thus g ≠ 0, so its leading coefficient is non-zero by Polynomial.leadingCoeff_ne_zero.mpr. Because the natural degree of g is 2, Polynomial.coeff_natDegree equates this leading coefficient with g.coeff 2.

    lines 11–17

    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₂ = g.coeff 2 is strictly positive.

    By lt_or_gt_of_ne, either c₂ < 0 or c₂ > 0. If c₂ < 0, then c₂ ≤ -1 because it is an integer. Setting n = |c₁| + |c₀| + 2 gives a positive integer n ≥ 2, so g(n) > 0 by hypothesis. However, c₂ n² ≤ -n², and n² ≥ n(|c₁| + |c₀| + 2) > |c₁| n + |c₀| ≥ c₁ n + c₀, which forces g(n) = c₂ n² + c₁ n + c₀ ≤ 0, a contradiction. Therefore, c₂ > 0.

    lines 18–44

    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. With M = 2|c₁| + 2|c₀| + 1, any integer n ≥ M satisfies c₂ ≥ 1, n ≥ 2|c₁| + 2|c₀| + 1, n ≥ 0, and n² ≥ 0.

    We choose the threshold M = 2|c₁| + 2|c₀| + 1 and fix n ≥ M. Since c₂ is a strictly positive integer, c₂ ≥ 1. Casting the condition M ≤ n to the integers via Nat.cast_le.mpr gives n ≥ 2|c₁| + 2|c₀| + 1. Since absolute values and squares are non-negative (abs_nonneg, sq_nonneg), it follows that n ≥ 0 and n² ≥ 0.

    lines 45–55

    uses Nat.cast_le.mpr, abs_nonneg, sq_nonneg

      refine ⟨2 * (g.coeff 1).natAbs + 2 * (g.coeff 0).natAbs + 1, ?_⟩
      intro n hn
      rw [hexp]
      have hc1 : (1:ℤ) ≤ g.coeff 2 := by omega
      have hbound : (2 * |g.coeff 1| + 2 * |g.coeff 0| + 1 : ℤ) ≤ (n:ℤ) := by
        have : ((2 * (g.coeff 1).natAbs + 2 * (g.coeff 0).natAbs + 1 : ℕ) : ℤ) ≤ (n : ℤ) := by
          exact Nat.cast_le.mpr hn
        push_cast at this
        exact this
      have hnpos : (0:ℤ) ≤ (n:ℤ) := by linarith [abs_nonneg (g.coeff 1), abs_nonneg (g.coeff 0), hbound]
      have hnsq : (0:ℤ) ≤ (n:ℤ)^2 := sq_nonneg _
  5. The quadratic term satisfies (2c₂ - 1)n² ≥ n² and n² ≥ (2|c₁| + 1)n.

    Because c₂ ≥ 1, we have 2c₂ - 1 ≥ 1, hence (2c₂ - 1)n² ≥ n². Furthermore, n ≥ 2|c₁| + 2|c₀| + 1 together with |c₀| ≥ 0 implies n ≥ 2|c₁| + 1. Multiplying both sides by n ≥ 0 preserves the inequality by mul_le_mul_of_nonneg_right, giving (2|c₁| + 1)n ≤ n².

    lines 56–64

    uses abs_nonneg, mul_le_mul_of_nonneg_right

      have hlead : (n:ℤ)^2 ≤ (2 * g.coeff 2 - 1) * (n:ℤ)^2 := by
        nlinarith [show (0:ℤ) ≤ 2 * g.coeff 2 - 2 by linarith]
      have hsq_ge : (2 * |g.coeff 1| + 1) * (n:ℤ) ≤ (n:ℤ)^2 := by
        have h : (2 * |g.coeff 1| + 1 : ℤ) ≤ (n:ℤ) := by
          linarith [abs_nonneg (g.coeff 0), hbound]
        calc
          (2 * |g.coeff 1| + 1) * (n:ℤ) ≤ (n:ℤ) * (n:ℤ) := by
            apply mul_le_mul_of_nonneg_right h hnpos
          _ = (n:ℤ)^2 := by ring
  6. For every n ≥ M, the inequality n² ≤ 2 g(n) holds.

    By neg_abs_le, we have -2|c₁| n ≤ 2 c₁ n and -2|c₀| ≤ 2 c₀. The bound n ≥ M implies n ≥ 2|c₀|, so n² ≥ 2|c₁| n + n ≥ 2|c₁| n + 2|c₀| ≥ -2 c₁ n - 2 c₀. Combining this with (2c₂ - 1)n² ≥ n², linear arithmetic establishes that n² ≤ 2(c₂ n² + c₁ n + c₀) = 2 g(n).

    lines 65–73

    uses neg_abs_le, abs_nonneg

      have hlin : -2 * |g.coeff 1| * (n:ℤ) ≤ 2 * g.coeff 1 * (n:ℤ) := by
        have := neg_abs_le (g.coeff 1)
        nlinarith
      have hconst : -2 * |g.coeff 0| ≤ 2 * g.coeff 0 := by
        have := neg_abs_le (g.coeff 0)
        linarith
      have htail : 2 * |g.coeff 0| ≤ (n:ℤ) := by
        linarith [abs_nonneg (g.coeff 1), hbound]
      linarith
Polynomial.natDegree_eq_of_degree_eq_some
If a polynomial has degree n as an extended natural number (WithBot ℕ), its natural degree equals n.
Polynomial.eval_eq_sum_range
Evaluating a polynomial at x equals the sum of its terms coeff(i) * x^i for i from 0 up to its natural degree.
Finset.sum_range_succ
A sum over the range 0 to n + 1 equals the sum over 0 to n plus the term at index n.
Polynomial.degree_zero
The degree of the zero polynomial is ⊥ (negative infinity).
Polynomial.coeff_natDegree
The coefficient of a polynomial at index equal to its natural degree is its leading coefficient.
Polynomial.leadingCoeff_ne_zero.mpr
If a polynomial is non-zero, its leading coefficient is non-zero.
lt_or_gt_of_ne
Two distinct elements in a linear order satisfy either a < b or b < a.
abs_nonneg
The absolute value of any element in an ordered group is non-negative.
sq_nonneg
The square of any element in an ordered semiring is non-negative.
le_refl
The order relation is reflexive: every element is less than or equal to itself.
mul_nonneg
The product of two non-negative elements is non-negative.
mul_le_mul_of_nonneg_right
Multiplying an inequality by a non-negative element on the right preserves the inequality.
le_abs_self
Any element is less than or equal to its absolute value.
Nat.cast_le.mpr
An inequality between natural numbers is preserved when casting both sides to integers.
neg_abs_le
The negation of the absolute value of an element is less than or equal to the element itself.

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 integer polynomial taking positive values on all positive integers eventually satisfies n^2 <= 2 g(n). -/theorem op_153_positive_quadratic_eventually_quadratic_lower_bound (g : Polynomial ℤ)    (hdeg : g.degree = 2) (hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) :    ∃ M : ℕ, ∀ n : ℕ, M ≤ n → (n : ℤ) ^ 2 ≤ 2 * g.eval (n : ℤ) := by  have hnd : g.natDegree = 2 := Polynomial.natDegree_eq_of_degree_eq_some hdeg  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  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  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  refine ⟨2 * (g.coeff 1).natAbs + 2 * (g.coeff 0).natAbs + 1, ?_⟩  intro n hn  rw [hexp]  have hc1 : (1:ℤ) ≤ g.coeff 2 := by omega  have hbound : (2 * |g.coeff 1| + 2 * |g.coeff 0| + 1 : ℤ) ≤ (n:ℤ) := by    have : ((2 * (g.coeff 1).natAbs + 2 * (g.coeff 0).natAbs + 1 : ℕ) : ℤ) ≤ (n : ℤ) := by      exact Nat.cast_le.mpr hn    push_cast at this    exact this  have hnpos : (0:ℤ) ≤ (n:ℤ) := by linarith [abs_nonneg (g.coeff 1), abs_nonneg (g.coeff 0), hbound]  have hnsq : (0:ℤ) ≤ (n:ℤ)^2 := sq_nonneg _  have hlead : (n:ℤ)^2 ≤ (2 * g.coeff 2 - 1) * (n:ℤ)^2 := by    nlinarith [show (0:ℤ) ≤ 2 * g.coeff 2 - 2 by linarith]  have hsq_ge : (2 * |g.coeff 1| + 1) * (n:ℤ) ≤ (n:ℤ)^2 := by    have h : (2 * |g.coeff 1| + 1 : ℤ) ≤ (n:ℤ) := by      linarith [abs_nonneg (g.coeff 0), hbound]    calc      (2 * |g.coeff 1| + 1) * (n:ℤ) ≤ (n:ℤ) * (n:ℤ) := by        apply mul_le_mul_of_nonneg_right h hnpos      _ = (n:ℤ)^2 := by ring  have hlin : -2 * |g.coeff 1| * (n:ℤ) ≤ 2 * g.coeff 1 * (n:ℤ) := by    have := neg_abs_le (g.coeff 1)    nlinarith  have hconst : -2 * |g.coeff 0| ≤ 2 * g.coeff 0 := by    have := neg_abs_le (g.coeff 0)    linarith  have htail : 2 * |g.coeff 0| ≤ (n:ℤ) := by    linarith [abs_nonneg (g.coeff 1), hbound]  linarith
See it in the graphDiscuss this resultChallenge it