Average Orders and Summatory Functions

While individual values of arithmetic functions can be irregular, their average behavior often exhibits surprising regularity. Summatory functions capture this asymptotic information.

DefinitionSummatory Function

For an arithmetic function $f$ , its summatory function is:

F(x) = \sum_{n \leq x} f(n)

We say $f$ has average order $g(n)$ if:

\sum_{n \leq x} f(n) \sim \sum_{n \leq x} g(n) \quad \text{as } x \to \infty

meaning the ratio approaches $1$ .

ExampleClassical Summatory Functions

Divisor sum: $\sum_{n \leq x} \tau(n) = x \log x + (2\gamma - 1)x + O(\sqrt{x})$
Euler totient: $\sum_{n \leq x} \varphi(n) = \frac{3}{\pi^2} x^2 + O(x \log x)$
Möbius function: $\sum_{n \leq x} \mu(n) = o(x)$ (equivalent to the Prime Number Theorem)

The Dirichlet hyperbola method is a powerful technique for evaluating summatory functions involving convolutions.

DefinitionDirichlet Hyperbola Method

For arithmetic functions $f, g$ with summatory functions $F, G$ , and $h = f * g$ :

\sum_{n \leq x} h(n) = \sum_{d \leq \sqrt{x}} f(d) G(x/d) + \sum_{m \leq \sqrt{x}} g(m) F(x/m) - F(\sqrt{x}) G(\sqrt{x})

This reduces the problem of summing $h$ to understanding $F$ and $G$ separately.

ExampleCounting Lattice Points

The hyperbola method can count lattice points under the hyperbola $xy \leq N$ :

\sum_{n \leq N} \tau(n) = \sum_{d \leq \sqrt{N}} \lfloor N/d \rfloor \cdot 2 - \lfloor \sqrt{N} \rfloor^2

which yields the asymptotic $N \log N + (2\gamma - 1)N + O(\sqrt{N})$ .

Remark

The error term in summatory functions often reveals deep arithmetic information. For instance, the error in $\sum_{n \leq x} \tau(n)$ is related to the Dirichlet divisor problem, whose optimal bound remains open.

Average order estimates transform chaotic individual behavior into smooth asymptotic formulas. This philosophy—that arithmetic functions become "nicer" when averaged—pervades analytic number theory and connects to profound conjectures like the Riemann Hypothesis through error term analysis.