Digital Library of Mathematical Functions
About the Project
NIST
27 Functions of Number TheoryMultiplicative Number Theory

§27.11 Asymptotic Formulas: Partial Sums

The behavior of a number-theoretic function f(n) for large n is often difficult to determine because the function values can fluctuate considerably as n increases. It is more fruitful to study partial sums and seek asymptotic formulas of the form

27.11.1 nxf(n)=F(x)+O(g(x)),

where F(x) is a known function of x, and O(g(x)) represents the error, a function of smaller order than F(x) for all x in some prescribed range. For example, Dirichlet (1849) proves that for all x1,

27.11.2 nxd(n)=xlogx+(2γ-1)x+O(x),

where γ is Euler’s constant (§5.2(ii)). Dirichlet’s divisor problem (unsolved in 2009) is to determine the least number θ0 such that the error term in (27.11.2) is O(xθ) for all θ>θ0. Kolesnik (1969) proves that θ01237.

Equations (27.11.3)–(27.11.11) list further asymptotic formulas related to some of the functions listed in §27.2. They are valid for all x2. The error terms given here are not necessarily the best known.

27.11.3 nxd(n)n=12(logx)2+2γlogx+O(1),

where γ again is Euler’s constant.

27.11.4 nxσ1(n) =π212x2+O(xlogx).
27.11.5 nxσα(n) =ζ(α+1)α+1xα+1+O(xβ),
α>0, α1, β=max(1,α).
27.11.6 nxϕ(n) =3π2x2+O(xlogx).
27.11.7 nxϕ(n)n =6π2x+O(logx).
27.11.8 px1p=loglogx+A+O(1logx),

where A is a constant.

27.11.9 pxph(modk)1p=1ϕ(k)loglogx+B+O(1logx),

where (h,k)=1, k>0, and B is a constant depending on h and k.

27.11.10 pxlogpp=logx+O(1).
27.11.11 pxph(modk)logpp=1ϕ(k)logx+O(1),

where (h,k)=1, k>0.

Letting x in (27.11.9) or in (27.11.11) we see that there are infinitely many primes ph(modk) if h,k are coprime; this is Dirichlet’s theorem on primes in arithmetic progressions.

27.11.12 nxμ(n)=O(x-Clogx),
x,

for some positive constant C,

27.11.13 limx1xnxμ(n)=0,
27.11.14 limxnxμ(n)n=0,
27.11.15 limxnxμ(n)lognn=-1.

Each of (27.11.13)–(27.11.15) is equivalent to the prime number theorem (27.2.3). The prime number theorem for arithmetic progressions—an extension of (27.2.3) and first proved in de la Vallée Poussin (1896a, b)—states that if (h,k)=1, then the number of primes px with ph(modk) is asymptotic to x/(ϕ(k)logx) as x.