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