1.3. Simple estimation techniques 7

1.3. Simple estimation techniques

In analytic number theory arithmetical questions are characteristically an-

swered by finding estimates that imply the desired conclusions. The proof

of Bertrand’s Postulate is typical; we wanted to know that every interval

(x/2,x] for x ≥ 2 contains at least one prime, but to obtain this result we

detoured through a lower bound for ϑ(x) − ϑ(x/2). Carrying out an esti-

mate often requires long calculations with inequalities, for which the usual

notation proves cumbersome. The big-O notation of P. G. H. Bachmann is

well adapted for eﬃcient calculations with long chains of inequalities. The

statement f(x) = O(g(x)) means that there exist some unspecified con-

stants C 0 and x0 such that |f(x)| ≤ Cg(x) on the interval x ≥ x0. The

bound ψ(x) ≤ 2 log(2)x +

log2(x)/

log(2) for x ≥ 1 would be expressed as

ψ(x) = O(x) in the big-O notation. The latter statement is less precise,

but the kind of information suppressed in the big-O notation is often unim-

portant anyway. The following result is the key to labor-saving calculations

using the big-O notation.

Proposition 1.3. If f1(x) = O(g(x)) and f2(x) = O(g(x)) then f1(x) +

f2(x) = O(g(x)). If also f3(x) = O(h(x)) then f1(x)f3(x) = O(g(x)h(x)).

Proof. There are C1,C2,C3 0 and x1,x2,x3 such that |f1(x)| ≤ C1g(x)

for x ≥ x1, |f2(x)| ≤ C2g(x) for x ≥ x2 and |f3(x)| ≤ C3h(x) for x ≥ x3.

Then

|f1(x) + f2(x)| ≤ |f1(x)| + |f2(x)| ≤ C1g(x) + C2g(x) = (C1 + C2)g(x)

for x ≥ max(x1,x2) and

|f1(x)f3(x)| = |f1(x)||f2(x)| ≤ C1g(x)C3h(x) = (C1C3)g(x)h(x)

for x ≥ max(x1,x3).

Note in particular that the largest of the O-terms in a sum absorbs

everything smaller. The notation f(x) g(x) due to I. M. Vinogradov

is synonymous with f(x) = O(g(x)). The notation f(x) g(x) of G.

H. Hardy means that f(x) g(x) and g(x) f(x). There is also a

small-o notation due to Landau. The statement f(x) = o(g(x)) means that

limx→+∞ f(x)/g(x) = 0, or equivalently, for any ε 0 there exists some

x0(ε) so that |f(x)| ≤ εg(x) for x ≥ x0(ε).

If the function f in an estimate f = O(g) depends on one or more

parameters, say fa(x) = Oa(g(x)), the question of uniformity of the estimate

is often of considerable importance. If it is possible to choose both C and

x0 in the statement that

|fa(x)| ≤ Cg(x) for x ≥ x0