Analytic number theory almost never produces an exact formula. Ask "how many primes are below x?", "what is the average number of divisors of n?", "how big is the n-th harmonic number?" — and the honest answer in every case is a main term you understand completely, plus an error term you can only bound. The entire subject is organised around that split. A theorem in this field is, almost by definition, a sentence of the form

To even write such sentences down you need a compact, precise vocabulary for "an error you control" — for saying how fast something grows or shrinks without committing to its exact value. That vocabulary is asymptotic notation: big-O, little-o, \sim, \Omega, \Theta, and — the working number-theorist's favourite — Vinogradov's \ll and \gg. This page teaches the language, its habits, and its traps, because every later result in the course will be phrased in it.

A quick orientation before the definitions: O and \ll are upper bounds ("no bigger than, up to a constant"), \Omega and \gg are lower bounds, \Theta pins something between two constant multiples, little- o says one thing is negligible beside another, and \sim says two things agree in the limit. Everything below is elaboration of that one sentence.

Big-O: the master tool

Two features of the definition do all the work. First, it is about eventual behaviour — what happens for large x — so any finite initial stretch is irrelevant. Second, it only asks for some constant C to exist; it never tells you which one. That deliberate vagueness is the point: big-O lets you throw away constants and lower-order clutter and talk only about the shape of growth.

Worked example. Take f(x) = 3x^2 + 100x + 7. For x \ge 1 we have 100x \le 100x^2 and 7 \le 7x^2, so

which is exactly the statement 3x^2 + 100x + 7 = O(x^2) with implied constant C = 110 (and x_0 = 1). Notice we cheerfully bounded 100x by 100x^2 — a wildly lossy step — because for big-O only the winning term x^2 matters. The leading coefficient 3 is gone too: O(x^2) and O(3x^2) are the same class.

The same idea runs the other direction, toward a limit point instead of infinity. Near x = 0, \sin x = x + O(x^3) and e^x = 1 + x + O(x^2) — the O-term collects the tail of the Taylor series into a single controlled bundle. Whenever you see O(\cdot) you should silently ask "in which limit?"; in this course it is almost always x \to \infty.

Vinogradov's \ll and \gg

Big-O is a mouthful to chain together — O(g) inside O(h) inside a sum quickly becomes unreadable. So analytic number theorists overwhelmingly prefer a lighter, relational notation, due to I. M. Vinogradov.

The great virtue is that \ll reads like an inequality and composes like one. You can write a whole chain, \sum_{n\le x} d(n) \ll x\log x \ll x^{1+\varepsilon}, and it scans left to right as "is of order at most". Because it points the same way as \le, f \ll g is far harder to abuse than the notorious f = O(g) (more on that abuse below).

Implied constants and subscripts. The constant hidden in \ll may depend on fixed parameters of the problem, and we record that dependence as a subscript. Writing f \ll_{\varepsilon} g (or f = O_{\varepsilon}(g)) says "the implied constant is allowed to depend on \varepsilon". This matters enormously: the bound d(n) \ll_{\varepsilon} n^{\varepsilon} is true for every fixed \varepsilon > 0, but the constant blows up as \varepsilon \to 0, so you may not silently send \varepsilon to zero inside the bound. A subscript is a promise about exactly what the constant is and isn't allowed to know.

The whole family, side by side

Five relations, one table. Read f as "the quantity we're studying" and g as "the yardstick".

Three things worth internalising from the table. First, o is strictly stronger than O: f = o(g) forces the ratio all the way to 0, whereas f = O(g) merely keeps it bounded. So o(g) \Rightarrow O(g) but not conversely. Second, f \sim g is equivalent to f = g + o(g) — the error is negligible relative to the main term, which is a much weaker claim than the error being small in absolute terms. Third, watch the warning below about \Omega: in this field it is a lower bound, not (as in computer science) a two-sided one.

Seeing the hierarchy of scales

Asymptotic notation is a tool for sorting functions into orders of growth. It helps to have the standard yardsticks physically in front of you. Below are four of them — \log x, \sqrt{x}, x, and x\log x — on a common axis. Each sits strictly below the next in the little-o sense: \log x = o(\sqrt x), \sqrt x = o(x), and x = o(x\log x).

The ordering looks obvious on the page, but the little-o statements it encodes are what let us say, cleanly, that a main term of size x utterly dominates an error of size \sqrt x, or that a \log x factor is a "small" blemish on a power of x. The whole grammar of "main term + error" is just a claim about which curve on a chart like this lies above which — eventually.

The algebra of O-terms

The reason O and \ll are so usable is that they obey a simple, forgiving algebra. Treat an O(\cdot) as a "black box of that size" and the following rules let you compute with them almost like numbers.

Worked example — an O-term inside a sum. Suppose we know a_n = \tfrac1n + O(n^{-2}) and we want \sum_{n=1}^{N} a_n. Split the sum along the split in a_n:

The last step used two facts: the harmonic sum's own expansion (next section), and that \sum_{n=1}^{\infty} n^{-2} converges, so the accumulated error is merely O(1) — a bounded constant — rather than growing. Being allowed to sum an O-term termwise like this, and recognise when the total stays finite, is one of the most-used moves in the whole subject.

Worked example — a product. If f(x) = x + O(\sqrt x), what is f(x)^2? Multiply out, treating O(\sqrt x) as a genuine quantity of that size:

The cross term 2x\cdot O(\sqrt x) = O(x^{3/2}) dominates the leftover O(x), so by the "larger wins" rule the error collapses to O(x^{3/2}). The main term squares cleanly; the error term is what needs care.

Worked example 1: the harmonic number

The prototype "main term + error" result, and one you will reuse constantly, is the asymptotics of the harmonic number H_n = 1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1n.

Read the three pieces in the language of this page. The main term \log n captures the growth — the harmonic series diverges, but only logarithmically slowly. The constant term \gamma is the stubborn offset that survives forever: H_n - \log n does not tend to 0, it tends to \gamma. And the error O(1/n) is the shrinking remainder that vanishes as n \to \infty. The result also gives us the cleaner but weaker statement H_n \sim \log n, since \gamma + O(1/n) = o(\log n) — but that phrasing throws away the valuable constant \gamma, which is exactly the kind of information the O-form preserves and the \sim-form discards.

Where the error comes from. Compare the sum to the integral \int_1^n dt/t = \log n. On each interval [k, k+1] the difference between the rectangle 1/k and the area under 1/t is a sliver of size O(1/k^2). Those slivers converge when summed — their total is what defines \gamma — and the tail left after n terms is \sum_{k>n} O(1/k^2) = O(1/n). That last estimate, \sum_{k>n} 1/k^2 \ll 1/n, is itself a clean little \ll-exercise: bound the sum by \int_n^\infty dt/t^2 = 1/n.

Worked example 2: the average number of divisors

Let d(n) be the number of divisors of n. It is a wildly erratic function — d(p) = 2 for a prime, but d(n) can be huge for highly composite n. Yet its average is beautifully smooth, and the proof is a perfect showcase of the O-algebra.

The idea (Dirichlet's "hyperbola method" in miniature) is to count lattice points under a hyperbola. Since d(n) = \sum_{d \mid n} 1, summing over n \le x counts pairs (d, q) with dq \le x:

Now feed in the harmonic asymptotics from the last section, \sum_{d\le x} 1/d = \log x + \gamma + O(1/x):

This already proves the average order is \log x — the crude error O(x) is smaller than the main term x\log x by a factor of \log x. Dirichlet's cleverer symmetric count (summing d \le \sqrt x and q \le \sqrt x and subtracting the doubly-counted square) sharpens the error all the way down to O(\sqrt x) and reveals the secondary main term (2\gamma - 1)x. How far that error can really be pushed — the Dirichlet divisor problem — is still open: the truth is believed to be O(x^{1/4 + \varepsilon}), and no one has proved it.

Worked example 3: the Prime Number Theorem, restated

Everything on this page was really rehearsal for reading the central theorem of the course in its proper, quantitative form. The bare Prime Number Theorem is usually stated as \pi(x) \sim x/\log x. But \sim is the weakest useful statement — it only says the ratio tends to 1 and hides how fast. The whole modern theory lives in the error term.

A first upgrade replaces \sim with an explicit split. Integrating \operatorname{Li}(x) = \int_2^x dt/\log t by parts gives

which is genuinely more informative: it names the size of the gap between \pi(x) and its crude estimate. But x/\log x is a poor main term, so the standard modern statement uses \operatorname{Li}(x) as the main term and buries everything hard in the error:

for some constant c > 0 (the classical Hadamard–de la Vallée Poussin error term). The size of that error term is a direct translation of a fact about the zeta function: how far to the left of the line \Re(s) = 1 we can prove \zeta(s) \ne 0. Push the zero-free region right up to the critical line and the error shrinks to O(x^{1/2}\log x) — that statement is equivalent to the Riemann Hypothesis. The entire difficulty of the subject has been quietly repackaged into the O(\cdot). That is the power, and the honesty, of asymptotic notation: it gives you an exact place to put what you do not yet know.