op_153_positive_quadratic_sublevel_card_bound
For a degree-2 integer polynomial strictly positive on positive integers, the number of positive integers $n \le N$ with $g(n) \le N$ is $O(\sqrt{N})$.
Statement
theorem op_153_positive_quadratic_sublevel_card_bound (g : Polynomial ℤ) (hdeg : g.degree = 2) (hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) : ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → (((Finset.Icc 1 N).filter (fun (n : ℕ) => g.eval (n : ℤ) ≤ (N : ℤ))).card : ℝ) ≤ C * Real.sqrt (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_quadratic_lower_boundA degree-2 integer polynomial strictly positive on positive integers satisfies $n^2 \le 2 g(n)$ for all sufficiently large positive…
- 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 1
- op_153_forbidden_diff_set_card_boundFor a degree-2 integer polynomial g strictly positive on the positive integers, any finite set of integers in {1, ..., N} each of which is…
The proof, explained
The proof partitions the sublevel set {n ∈ [1, N] | g(n) ≤ N} into small values n < M and large values n ≥ M, where M is a threshold beyond which g(n) ≥ n² / 2. For n ≥ M, the condition g(n) ≤ N forces n² ≤ 2N, bounding n by ⌊√(2N)⌋. Therefore, the sublevel set has cardinality at most M + ⌊√(2N)⌋ + 1 ≤ M + 2√N + 1. Since √N ≥ 1 for N ≥ 1, this is bounded by (M + 3)√N, establishing the O(√N) bound with C = M + 3 and N₀ = 1.
There is a threshold M beyond which n² ≤ 2g(n), and we choose C = M + 3 > 0 and N₀ = 1.
By the helper lemma op_153_positive_quadratic_eventually_quadratic_lower_bound, there exists M such that n² ≤ 2g(n) for all n ≥ M. We provide C = M + 3 (which is strictly positive) and N₀ = 1 as the constants for the bound.
uses
op_153_positive_quadratic_eventually_quadratic_lower_boundobtain ⟨M, hM⟩ := op_153_positive_quadratic_eventually_quadratic_lower_bound g hdeg hpos refine ⟨(M : ℝ) + 3, by positivity, 1, ?_⟩
Let N ≥ 1 and define the sublevel set s = {n ∈ [1, N] | g(n) ≤ N}.
We introduce an arbitrary integer N ≥ 1 and let s denote the finite set of integers n ∈ [1, N] with g(n) ≤ N.
intro N hN let s := (Finset.Icc 1 N).filter (fun (n : ℕ) => g.eval (n : ℤ) ≤ (N : ℤ))
The sublevel set s is contained in {0, ..., M - 1} ∪ {0, ..., ⌊√(2N)⌋}.
For any n ∈ s, we split into cases: if n < M, then n is in the range of M. If n ≥ M, the quadratic lower bound gives n² ≤ 2g(n) ≤ 2N. Hence n * n ≤ 2N, which implies n ≤ ⌊√(2N)⌋ by Nat.le_sqrt.mpr, so n < ⌊√(2N)⌋ + 1.
uses
Finset.mem_union,Finset.mem_range,Finset.mem_filter,Finset.mem_Icc,Nat.le_sqrt.mprhave hsub : s ⊆ Finset.range M ∪ Finset.range (Nat.sqrt (2 * N) + 1) := by intro n hn simp only [Finset.mem_union, Finset.mem_range] simp only [s, Finset.mem_filter, Finset.mem_Icc] at hn rcases hn with ⟨⟨h1, h2⟩, hg⟩ by_cases hlt : n < M · left; exact hlt · right have hge : M ≤ n := by omega have hle := hM n hge have hsq : (n : ℤ) ^ 2 ≤ 2 * (N : ℤ) := by linarith have hsq_nat : n ^ 2 ≤ 2 * N := by exact_mod_cast hsq have hsq_mul : n * n ≤ 2 * N := by linarith [show n ^ 2 = n * n by ring] have : n ≤ Nat.sqrt (2 * N) := Nat.le_sqrt.mpr hsq_mul omega
The cardinality of s is at most M + ⌊√(2N)⌋ + 1.
Since s is a subset of Finset.range M ∪ Finset.range (⌊√(2N)⌋ + 1), its cardinality is at most the cardinality of the union, which is bounded by the sum of the sizes M and ⌊√(2N)⌋ + 1.
uses
Finset.card_le_card,Finset.card_union_le,Finset.card_rangehave hcard_le : s.card ≤ M + Nat.sqrt (2 * N) + 1 := by have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (Finset.range M) (Finset.range (Nat.sqrt (2 * N) + 1)) simp only [Finset.card_range] at h2 omega
In the real numbers, ⌊√(2N)⌋ ≤ 2√N.
The integer square root satisfies ⌊√(2N)⌋ ≤ √(2N). By monotonicity of real square roots, √(2N) ≤ √(4N) since 2N ≤ 4N for N ≥ 0. Finally, √(4N) = √4 * √N = 2√N.
uses
Real.nat_sqrt_le_real_sqrt,Real.sqrt_le_sqrt,Nat.cast_nonneg,Real.sqrt_mulhave hsqrt : (Nat.sqrt (2 * N) : ℝ) ≤ 2 * Real.sqrt (N : ℝ) := by have h1 : ((2 * N).sqrt : ℝ) ≤ Real.sqrt ((2 * N : ℕ) : ℝ) := Real.nat_sqrt_le_real_sqrt have hcast : ((2 * N : ℕ) : ℝ) = 2 * (N : ℝ) := by push_cast; ring rw [hcast] at h1 have h2 : Real.sqrt (2 * (N : ℝ)) ≤ Real.sqrt (4 * (N : ℝ)) := by apply Real.sqrt_le_sqrt have : 0 ≤ (N : ℝ) := Nat.cast_nonneg N linarith have h3 : Real.sqrt (4 * (N : ℝ)) = 2 * Real.sqrt (N : ℝ) := by rw [Real.sqrt_mul (by norm_num)] norm_num linarith
In the real numbers, √N ≥ 1, M ≥ 0, and |s| ≤ M + ⌊√(2N)⌋ + 1.
Because N ≥ 1, √1 ≤ √N, so 1 ≤ √N. The natural threshold M is non-negative, and the integer cardinality bound on |s| is cast directly to the reals.
uses
Real.sqrt_le_sqrt,Nat.cast_nonneghave hsqrt_ge1 : 1 ≤ Real.sqrt (N : ℝ) := by have : (1 : ℝ) = Real.sqrt 1 := by norm_num rw [this] apply Real.sqrt_le_sqrt exact_mod_cast hN have hM_nonneg : 0 ≤ (M : ℝ) := Nat.cast_nonneg M have hcard_cast : (s.card : ℝ) ≤ (M : ℝ) + (Nat.sqrt (2 * N) : ℝ) + 1 := by exact_mod_cast hcard_le
The cardinality of s is at most (M + 3)√N.
Combining |s| ≤ M + 2√N + 1 with 1 ≤ √N and M ≥ 0 gives M ≤ M√N and 1 ≤ √N, whence |s| ≤ M√N + 2√N + √N = (M + 3)√N.
nlinarith
op_153_positive_quadratic_eventually_quadratic_lower_bound- For any degree-2 integer polynomial g strictly positive on positive integers, there exists a natural number M such that n² ≤ 2g(n) for all n ≥ M.
Finset.mem_union- An element belongs to the union of two finite sets s ∪ t if and only if it belongs to s or to t.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
Finset.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Nat.le_sqrt.mpr- If m * m ≤ k for natural numbers, then m ≤ ⌊√k⌋.
Finset.card_le_card- If s ⊆ t for finite sets, then the cardinality of s is at most that of t.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their individual cardinalities.
Finset.card_range- The cardinality of Finset.range n is n.
Real.nat_sqrt_le_real_sqrt- The integer square root of a natural number a, cast to the reals, is at most the real square root √a.
Real.sqrt_le_sqrt- If x ≤ y for real numbers, then √x ≤ √y.
Nat.cast_nonneg- The canonical image of any natural number in an ordered semiring is non-negative.
Real.sqrt_mul- For a non-negative real x and any real y, √(x * y) = √x * √y.
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.
/-- The sublevel set of positive integers n <= N with g(n) <= N has cardinality bounded by C sqrt(N). -/theorem op_153_positive_quadratic_sublevel_card_bound (g : Polynomial ℤ) (hdeg : g.degree = 2) (hpos : ∀ n : ℕ, 0 < n → 0 < g.eval (n : ℤ)) : ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → (((Finset.Icc 1 N).filter (fun (n : ℕ) => g.eval (n : ℤ) ≤ (N : ℤ))).card : ℝ) ≤ C * Real.sqrt (N : ℝ) := by obtain ⟨M, hM⟩ := op_153_positive_quadratic_eventually_quadratic_lower_bound g hdeg hpos refine ⟨(M : ℝ) + 3, by positivity, 1, ?_⟩ intro N hN let s := (Finset.Icc 1 N).filter (fun (n : ℕ) => g.eval (n : ℤ) ≤ (N : ℤ)) have hsub : s ⊆ Finset.range M ∪ Finset.range (Nat.sqrt (2 * N) + 1) := by intro n hn simp only [Finset.mem_union, Finset.mem_range] simp only [s, Finset.mem_filter, Finset.mem_Icc] at hn rcases hn with ⟨⟨h1, h2⟩, hg⟩ by_cases hlt : n < M · left; exact hlt · right have hge : M ≤ n := by omega have hle := hM n hge have hsq : (n : ℤ) ^ 2 ≤ 2 * (N : ℤ) := by linarith have hsq_nat : n ^ 2 ≤ 2 * N := by exact_mod_cast hsq have hsq_mul : n * n ≤ 2 * N := by linarith [show n ^ 2 = n * n by ring] have : n ≤ Nat.sqrt (2 * N) := Nat.le_sqrt.mpr hsq_mul omega have hcard_le : s.card ≤ M + Nat.sqrt (2 * N) + 1 := by have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (Finset.range M) (Finset.range (Nat.sqrt (2 * N) + 1)) simp only [Finset.card_range] at h2 omega have hsqrt : (Nat.sqrt (2 * N) : ℝ) ≤ 2 * Real.sqrt (N : ℝ) := by have h1 : ((2 * N).sqrt : ℝ) ≤ Real.sqrt ((2 * N : ℕ) : ℝ) := Real.nat_sqrt_le_real_sqrt have hcast : ((2 * N : ℕ) : ℝ) = 2 * (N : ℝ) := by push_cast; ring rw [hcast] at h1 have h2 : Real.sqrt (2 * (N : ℝ)) ≤ Real.sqrt (4 * (N : ℝ)) := by apply Real.sqrt_le_sqrt have : 0 ≤ (N : ℝ) := Nat.cast_nonneg N linarith have h3 : Real.sqrt (4 * (N : ℝ)) = 2 * Real.sqrt (N : ℝ) := by rw [Real.sqrt_mul (by norm_num)] norm_num linarith have hsqrt_ge1 : 1 ≤ Real.sqrt (N : ℝ) := by have : (1 : ℝ) = Real.sqrt 1 := by norm_num rw [this] apply Real.sqrt_le_sqrt exact_mod_cast hN have hM_nonneg : 0 ≤ (M : ℝ) := Nat.cast_nonneg M have hcard_cast : (s.card : ℝ) ≤ (M : ℝ) + (Nat.sqrt (2 * N) : ℝ) + 1 := by exact_mod_cast hcard_le nlinarith