Average Orders of Arithmetic Functions

Irregular Arithmetic Functions

Arithmetic functions often fluctuate strongly from one integer to the next.

For example,

\tau(p)=2

for every prime $p$ , while

\tau(360)=24.

Similarly,

\varphi(p)=p-1

for primes, but

\varphi(2^k)=2^{k-1}.

Because of this irregular behavior, exact formulas for individual integers are often difficult to analyze globally.

Instead of studying precise values, number theory frequently studies average behavior.

Average Order

Let $f(n)$ be an arithmetic function. An average order of $f$ is a simpler function $g(n)$ such that the sums

\sum_{n\le x} f(n)

behave approximately like

\sum_{n\le x} g(n)

for large $x$ .

Informally, $g(n)$ describes the typical size of $f(n)$ .

This viewpoint shifts attention from local fluctuations to large-scale statistical behavior.

Average Order of the Divisor Function

The divisor-counting function satisfies

\tau(n)=\sum_{d\mid n}1.

One can show that

\sum_{n\le x}\tau(n) = x\log x+(2\gamma-1)x+O(\sqrt{x}),

where $\gamma$ is Euler’s constant.

Thus the average size of $\tau(n)$ is roughly

\log n.

Although $\tau(n)$ varies considerably, a typical integer near $n$ has about $\log n$ divisors on average.

Hyperbola Method

A classical way to estimate divisor sums is the Dirichlet hyperbola method.

Since

\tau(n)=\sum_{d\mid n}1,

we have

\sum_{n\le x}\tau(n) = \sum_{n\le x}\sum_{d\mid n}1.

Reversing the order of summation,

= \sum_{d\le x}\left\lfloor\frac{x}{d}\right\rfloor.

Geometrically, this counts lattice points under the hyperbola

mn\le x.

Approximating

\left\lfloor\frac{x}{d}\right\rfloor \approx \frac{x}{d},

one obtains

\sum_{n\le x}\tau(n) \approx x\sum_{d\le x}\frac1d.

Since the harmonic sum behaves like

\log x,

the main term becomes

x\log x.

This explains heuristically why the average order of $\tau(n)$ is logarithmic.

Average Order of the Totient Function

Euler’s totient function also has a predictable average size.

One can prove

\sum_{n\le x}\varphi(n) \sim \frac{3}{\pi^2}x^2.

Dividing by $x$ , the average size of $\varphi(n)$ near $n$ is approximately

\frac{6}{\pi^2}n.

The constant

\frac{6}{\pi^2}

appears because it equals the probability that two randomly chosen integers are coprime.

Thus a typical integer $n$ has about

\frac{6}{\pi^2}n

invertible residue classes modulo $n$ .

Average Order of $\sigma(n)$

The divisor-sum function satisfies

\sigma(n)=\sum_{d\mid n} d.

Its average order is quadratic in size:

\sum_{n\le x}\sigma(n) \sim \frac{\pi^2}{12}x^2.

Hence the average size of $\sigma(n)$ near $n$ is approximately

\frac{\pi^2}{6}n.

This reflects the fact that the average sum of divisors grows proportionally to the integer itself.

Mean Values

The mean value of an arithmetic function $f$ is often defined as

\frac1x\sum_{n\le x}f(n).

If this quantity approaches a limit as

x\to\infty,

that limit describes the long-term average behavior of $f$ .

For example, one can show that

\frac1x\sum_{n\le x}\frac{\varphi(n)}{n} \to \frac6{\pi^2}.

Thus the average proportion of integers coprime to $n$ is

6/\pi^2.

Normal Order

An average order describes the average size of a function across many integers. A normal order describes the size for most integers individually.

For example, the divisor function has average order

\log n,

but its normal order is smaller:

(\log n)^{\log 2}.

Similarly, the normal order of the number of distinct prime factors of $n$ is

\log\log n.

These results show that average behavior and typical behavior need not coincide exactly.

Probabilistic Heuristics

Average orders often arise from probabilistic reasoning.

For example, the probability that a random integer is divisible by a prime $p$ is approximately

\frac1p.

Thus the probability that it is not divisible by $p$ is

1-\frac1p.

Such heuristics lead naturally to estimates involving Euler products and logarithms.

Although the integers are deterministic objects, many arithmetic phenomena behave statistically.

Dirichlet Series and Average Orders

Dirichlet series encode average behavior analytically.

For example,

\sum_{n=1}^{\infty}\frac{\tau(n)}{n^s} = \zeta(s)^2.

The pole of $\zeta(s)^2$ at

s=1

controls the growth of

\sum_{n\le x}\tau(n).

Similarly,

\sum_{n=1}^{\infty}\frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.

The analytic properties of these Dirichlet series determine asymptotic behavior of the underlying arithmetic functions.

This principle is central in analytic number theory.

Role in Number Theory

Average orders reveal large-scale arithmetic structure hidden behind irregular local behavior.

They connect arithmetic functions with harmonic sums, Euler products, Dirichlet series, and probabilistic heuristics. Instead of studying isolated integers, one studies statistical laws across all integers.

This shift from exact formulas to asymptotic behavior is one of the defining transitions from elementary number theory to analytic number theory.