Project-declaredLean 4.32.0 · mathlib@81a5d257c8e4

Is Big O nat Top of at Top

BrunTitchmarsh.IsBigO.nat_Top_of_atTop

analytic number theory prime numbers asymptotics brun titchmarsh

Plain-language statement

Suppose sequences $f,g:\mathbb N\to\mathbb R$ satisfy $f(n)=O(g(n))$ as $n\to\infty$ , and $f(n)=0$ whenever $g(n)=0$ . Then a single constant bounds $|f(n)|$ by that constant times $|g(n)|$ for every natural number $n$ , not only for all sufficiently large $n$ .

Exact Lean statement

theorem IsBigO.nat_Top_of_atTop (f g : ℕ → ℝ) (h : f =O[Filter.atTop] g)
    (h0 : ∀ n, g n = 0 → f n = 0) : f =O[⊤] g

Formal artifact

Lean source

Canonical source

Full Lean sourceLean 4

theorem IsBigO.nat_Top_of_atTop (f g : ℕ → ℝ) (h : f =O[Filter.atTop] g)    (h0 : ∀ n, g n = 0 → f n = 0) : f =O[⊤] g := by  simp only [Asymptotics.isBigO_top, Real.norm_eq_abs]  rw [Asymptotics.isBigO_atTop_iff_eventually_exists] at h  simp only [ge_iff_le, Real.norm_eq_abs, Filter.eventually_atTop] at h  obtain ⟨N, hN⟩ := h  specialize hN N le_rfl  obtain ⟨c, hc⟩ := hN  let C := Finset.max' (insert c ((Finset.range N).image (fun n ↦ |f n| * |g n|⁻¹))) (by simp)  refine ⟨C, fun n ↦ ?_⟩  by_cases hn : N ≤ n  · calc |f n| ≤ c * |g n| := hc n hn      _ ≤ C * |g n| := by        gcongr        apply Finset.le_max'        simp  · by_cases hg : g n = 0    · simp [hg, h0]    rw [← mul_inv_le_iff₀]    · apply Finset.le_max'      simp only [Finset.mem_insert, Finset.mem_image, Finset.mem_range]      exact .inr ⟨n, by omega, rfl⟩    · simp [hg]

Project: Prime Number Theorem and More
License: Apache-2.0
Commit: a93551347dce
Source: PrimeNumberTheoremAnd/BrunTitchmarsh.lean:400-422

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.32.0

Admissible bound mono

admissible_bound.mono

Plain-language statement

For positive parameters $A,B,C,R$ , the classical error-bound function $A\left(\frac{\log x}{R}\right)^B\exp\!\left(-C\sqrt{\frac{\log x}{R}}\right)$ is nonincreasing once $x\ge \exp\!\left(R(2B/C)^2\right)$ .

analytic number theoryprime numbersasymptotics

Source project: Prime Number Theorem and More

Person-level attribution pending.

View proof record

Project-declaredLean 4.32.0

Analytic On div Removable zero

AnalyticOn_divRemovable_zero

Plain-language statement

Let $f$ be analytic on an open set $s$ containing $0$ , and suppose $f(0)=0$ . Define $g(z)=f(z)/z$ for $z\ne0$ and $g(0)=f'(0)$ . Then the apparent singularity at $0$ is removable and $g$ is analytic throughout $s$ .

analytic number theoryprime numbersasymptotics

Source project: Prime Number Theorem and More

Person-level attribution pending.

View proof record

Project-declaredLean 4.32.0

Analytic On div Removable zero closed Ball

AnalyticOn_divRemovable_zero_closedBall

Plain-language statement

Suppose $R>0$ and $f$ is analytic on the closed disc $|z|\le R$ with $f(0)=0$ . Define $g(z)=f(z)/z$ for $z\ne0$ and $g(0)=f'(0)$ . Then $g$ is analytic on the entire closed disc, including at the removed singularity.

analytic number theoryprime numbersasymptotics

Source project: Prime Number Theorem and More

Person-level attribution pending.

View proof record