AFTD Auto-Formalizing Theoretical Domains

op_153_positive_quadratic_sublevel_card_bound

theoremverified

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
Used by 1

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.

  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.

    lines 7–8

    uses op_153_positive_quadratic_eventually_quadratic_lower_bound

      obtain ⟨M, hM⟩ := op_153_positive_quadratic_eventually_quadratic_lower_bound g hdeg hpos
      refine ⟨(M : ℝ) + 3, by positivity, 1, ?_⟩
  2. 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.

    lines 9–10

      intro N hN
      let s := (Finset.Icc 1 N).filter (fun (n : ℕ) => g.eval (n : ℤ) ≤ (N : ℤ))
  3. 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.

    lines 11–27

    uses Finset.mem_union, Finset.mem_range, Finset.mem_filter, Finset.mem_Icc, Nat.le_sqrt.mpr

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

    lines 28–32

    uses Finset.card_le_card, Finset.card_union_le, Finset.card_range

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

    lines 33–44

    uses Real.nat_sqrt_le_real_sqrt, Real.sqrt_le_sqrt, Nat.cast_nonneg, Real.sqrt_mul

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

    lines 45–52

    uses Real.sqrt_le_sqrt, Nat.cast_nonneg

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

    line 53

      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

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