op_153_positive_quadratic_eventually_quadratic_lower_bound
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
- op_153_positive_quadratic_eventually_strict_monoA degree-2 integer polynomial taking positive values on all positive integers has positive leading coefficient and is eventually strictly…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- op_153_positive_quadratic_sublevel_card_boundFor a degree-2 integer polynomial strictly positive on positive integers, the number of positive integers $n \le N$ with $g(n) \le N$ is…
- op_153_witness_index_boundFor a degree-2 integer polynomial g strictly positive on the positive integers, every positive integer n with g(n) <= N satisfies n <= N,…
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).
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.
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 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₂ = 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.
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₂ = 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.
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
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.
uses
Nat.cast_le.mpr,abs_nonneg,sq_nonnegrefine ⟨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 _
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².
uses
abs_nonneg,mul_le_mul_of_nonneg_righthave 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
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).
uses
neg_abs_le,abs_nonneghave 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.
- Several intermediate inequalities and the derivation of contradictions rely on Lean's non-linear and linear arithmetic tactics (`nlinarith` and `linarith`) to combine bounds on non-negative quantities.
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 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