Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Divisor bound d(n)≪εnεd(n)\ll_\varepsilon n^\varepsilond(n)≪ε​nε

Proved
CircleMethod.divisor_bound

by tabbott · Sep 1, 2026 · Mathlib c5ea003 (Lean v4.30.0)

analytic-number-theorycircle-methodexponential-sumsnumber-theory

The classical divisor bound: for every ε>0\varepsilon>0ε>0 there is a constant C=C(ε)C=C(\varepsilon)C=C(ε) with

d(n)  ≤  C nεfor all n≥1,d(n)\;\le\;C\,n^{\varepsilon}\qquad\text{for all }n\ge 1,d(n)≤Cnεfor all n≥1,

where d(n)d(n)d(n) is the number of positive divisors of nnn. Equivalently d(n)=Oε(nε)d(n)=O_\varepsilon(n^\varepsilon)d(n)=Oε​(nε): the divisor function grows more slowly than any positive power of nnn, even though it is unbounded and reaches nc/log⁡log⁡nn^{c/\log\log n}nc/loglogn infinitely often.

This is needed in the proof of Weyl's inequality. After the differencing steps one must count the pairs (h1,…,hk−1)(h_1,\dots,h_{k-1})(h1​,…,hk−1​) for which the resulting linear coefficient lies close to an integer; the count is governed by the number of divisors of an integer of size O(Nk)O(N^{k})O(Nk), and the crude bound above is exactly strong enough to absorb it into the NεN^{\varepsilon}Nε factor. It is also used throughout analytic number theory whenever a divisor-type sum must be dominated.

Formalization Note. d(n)d(n)d(n) is n.divisors.card, Mathlib's count of the divisors of n; the hypothesis 0<n0<n0<n excludes the convention Nat.divisors 0 = ∅. The exponent nεn^\varepsilonnε is a real power (Real.rpow). The constant CCC is quantified after ε\varepsilonε and before nnn, so a single CCC must serve every nnn; solvers should preserve that order, since permitting CCC to depend on nnn trivialises the claim.

Preamble
import Definitions.Def_CircleMethod_genfun
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Integrals.Basic
import Mathlib.NumberTheory.Divisors
import Mathlib.Data.Fintype.Pi
open Finset
Formal statement
namespace CircleMethod

theorem divisor_bound {ε : ℝ} (hε : 0 < ε) :
    ∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 0 < n → ((n.divisors.card : ℝ)) ≤ C * (n : ℝ) ^ ε := by sorry

end CircleMethod
Source
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, Theorem 315 (d(n) = O(n^delta) for every delta > 0); used in R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., 1997, proof of Lemma 2.4.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back: CircleMethod.divisor_bound

The declaration asserts the following statement.

Let ε\varepsilonε be a real number (supplied implicitly, i.e. it is to be inferred from context rather than written out at each use), and assume the single hypothesis

0<ε.0 < \varepsilon .0<ε.

Under this hypothesis, the claim is that there exists a real number CCC such that both of the following hold:

  • 0<C0 < C0<C; and
  • for every natural number nnn, if 0<n0 < n0<n, then
#(divisors(n))  ≤  C⋅nε.\#\bigl(\mathrm{divisors}(n)\bigr) \;\le\; C \cdot n^{\varepsilon}.#(divisors(n))≤C⋅nε.

Here the quantities are to be read as follows.

The left-hand side. divisors(n)\mathrm{divisors}(n)divisors(n) denotes the standard finite set of divisors of a natural number nnn as defined in the ambient library: the finite set of those natural numbers ddd with 1≤d≤n1 \le d \le n1≤d≤n and d∣nd \mid nd∣n. Its cardinality is a natural number — the classical divisor-counting function τ(n)=d(n)\tau(n) = d(n)τ(n)=d(n) — and this natural number is then coerced (cast) into the real numbers so that it can be compared with the right-hand side. For n=0n = 0n=0 this set is empty by convention, but the hypothesis 0<n0 < n0<n excludes that case, so the inequality is asserted only for n≥1n \ge 1n≥1.

The right-hand side. nnn is coerced from a natural number to a real number, and nεn^{\varepsilon}nε is the real power (real exponentiation with a real exponent), not an iterated product: for n≥1n \ge 1n≥1 the base is positive and nε=exp⁡(εlog⁡n)n^{\varepsilon} = \exp(\varepsilon \log n)nε=exp(εlogn). In particular 1ε=11^{\varepsilon} = 11ε=1. The product C⋅nεC \cdot n^{\varepsilon}C⋅nε is a product of real numbers, and the comparison ≤\le≤ is the (non-strict) order on R\mathbb{R}R.

Order of the quantifiers. The existential quantifier over CCC stands outside the universal quantifier over nnn. Consequently CCC is a single constant that must work simultaneously for all n≥1n \ge 1n≥1; it is chosen after ε\varepsilonε is given, so CCC is permitted to depend on ε\varepsilonε, but not on nnn. Conversely, the statement makes no claim about how CCC depends on ε\varepsilonε: no formula, no bound, no uniformity in ε\varepsilonε, and no explicit witness is asserted — only that some positive CCC exists.

Strength and edge cases.

  • The hypothesis 0<ε0 < \varepsilon0<ε is strict; nothing is asserted for ε=0\varepsilon = 0ε=0 or ε<0\varepsilon < 0ε<0. The hypothesis is satisfiable (e.g. ε=1\varepsilon = 1ε=1), so the statement is not vacuous.
  • The requirement 0<C0 < C0<C is strict, and it is an additional conjunct of the existential claim, not merely a side remark: any witness must be strictly positive. (Since the inequality at n=1n = 1n=1 reads 1≤C⋅11 \le C \cdot 11≤C⋅1, the positivity requirement is not the binding constraint there.)
  • The inequality is ≤\le≤, not <<<.
  • The quantification over nnn ranges over all natural numbers, with the case n=0n = 0n=0 removed by the hypothesis 0<n0 < n0<n; the case n=1n = 1n=1 is included.
  • ε\varepsilonε is fixed once and for all before CCC and nnn are chosen; the statement is a single assertion about that one ε\varepsilonε, universally quantified over ε\varepsilonε only in the sense that the declaration may be instantiated at any positive ε\varepsilonε.

Definitions in scope that do not appear. The bundle supplies three auxiliary definitions which the statement does not mention or use in any way: the additive character e(θ)=exp⁡(2πiθ)e(\theta) = \exp(2\pi i \theta)e(θ)=exp(2πiθ) taking a real number to a complex number; the exponential generating function fA(θ)=∑a∈Ae(aθ)f_A(\theta) = \sum_{a \in A} e(a\theta)fA​(θ)=∑a∈A​e(aθ) of a finite set A⊆ZA \subseteq \mathbb{Z}A⊆Z, valued in C\mathbb{C}C; and the distance-to-the-nearest-integer function ∥θ∥=∣θ−round(θ)∣\lVert \theta \rVert = |\theta - \mathrm{round}(\theta)|∥θ∥=∣θ−round(θ)∣. None of eee, fff, or ∥⋅∥\lVert \cdot \rVert∥⋅∥ occurs in the asserted inequality; the statement is purely about the divisor-counting function and a real power of nnn.

Proof status. The declaration is stated with its proof omitted (a placeholder stands in place of a proof), so the file records the assertion above without establishing it.

Human review
  • Endorsed by tianyipeng · Sep 2, 2026

  • Endorsed by tabbott · Sep 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me