Unit 6: Möbius Inversion, Average Orders & Ramanujan Sums

1. The Möbius Function

August Ferdinand Möbius introduced this fundamental function in 1832.

Definition 6.1 (The Möbius Function): The Möbius function $\mu: \mathbb{N} \to \{-1, 0, 1\}$ is defined by:

Theorem 6.1 (Fundamental Divisor Sum Identity of $\mu$): For every positive integer $n \ge 1$:

In the language of Dirichlet convolution, $\mu$ is the Dirichlet inverse of the constant function $u(n) = 1$:

Proof: For $n = 1$: $\sum_{d \mid 1} \mu(d) = \mu(1) = 1$. For $n > 1$: let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ with $k \ge 1$. Any divisor $d \mid n$ with a square factor contributes $\mu(d) = 0$. Thus, only square-free divisors $d = p_{i_1} p_{i_2} \cdots p_{i_j}$ contribute non-zero values $\mu(d) = (-1)^j$. The number of such divisors having exactly $j$ prime factors is $\binom{k}{j}$. Therefore, summing over all possible counts of prime factors $j \in \{0, 1, \dots, k\}$:

By the Binomial Theorem:

This establishes the identity completely. $\blacksquare$

2. The Möbius Inversion Formula

Theorem 6.2 (The Möbius Inversion Formula): Let $f$ and $F$ be arithmetical functions. Then:

Proof (via Dirichlet Convolution): The relation $F(n) = \sum_{d \mid n} f(d)$ is expressed concisely as:

Convolving both sides with the Möbius function $\mu$:

By associativity and commutativity of Dirichlet convolution (Theorem 5.8):

Thus:

The reverse implication follows symmetrically by convolving with $u$. $\blacksquare$

1. Inversion of Euler's Totient Identity

Theorem 6.3 (Gauss's Totient Divisor Sum): For every positive integer $n \ge 1$:

Proof: Partition the set of integers $\{1, 2, \dots, n\}$ into classes based on their greatest common divisor with $n$:

Notice that $\gcd(k, n) = d \iff \gcd(k/d, n/d) = 1$. Letting $k' = k/d$, the number of such integers is the number of $1 \le k' \le n/d$ with $\gcd(k', n/d) = 1$, which is precisely $\phi(n/d)$. Summing the sizes of all disjoint subsets $S_d$:

Applying the Möbius Inversion Formula to $F(n) = n$ and $f(n) = \phi(n)$:

Theorem 6.4 (Möbius Inversion Formula for $\phi(n)$):

2. Multiplicative Form of Möbius Inversion

For multiplicative relationships involving products rather than sums:

Theorem 6.5 (Product Form of Möbius Inversion): Let $g$ and $G$ be functions from $\mathbb{N}$ to $\mathbb{C}^\times$. Then:

Proof: Take the complex logarithm on both sides: $\ln G(n) = \sum_{d \mid n} \ln g(d)$. Applying standard additive Möbius Inversion to $\ln G$ and $\ln g$:

Exponentiating both sides establishes the result. $\blacksquare$

1. Definition of Ramanujan's Sum

Srinivasa Ramanujan introduced these sums in his 1918 paper On Certain Trigonometrical Sums and their Applications in the Theory of Numbers.

Definition 6.2 (Ramanujan's Trigonometric Sum): For positive integers $q, n \in \mathbb{N}$, Ramanujan's sum $c_q(n)$ is defined as the sum of the $n$-th powers of the primitive $q$-th roots of unity:

(the imaginary sine components cancel out by symmetry).

2. The Fundamental Identity of Ramanujan's Sum

Theorem 6.6 (Ramanujan's Divisor Sum Identity): For all positive integers $q$ and $n$:

Proof: Recall the fundamental character orthogonality sum for roots of unity:

Every residue $a \in \{1, 2, \dots, q\}$ satisfies $\gcd(a, q) = d$ for some unique divisor $d \mid q$. Writing $a = d a'$ and $q = d q'$ with $\gcd(a', q') = 1$:

Applying Möbius Inversion (Theorem 6.2) with respect to the variable $q$:

Since $\eta_d(n) = d$ when $d \mid n$ and $0$ otherwise, the sum runs only over divisors $d$ that divide both $q$ and $n$, that is, $d \mid \gcd(q, n)$:

Corollary 6.1 (Special Values):

1. When $n = 1$: $c_q(1) = \mu(q)$.
2. When $q \mid n$: $c_q(n) = \phi(q)$.
3. For any prime $p$:

1. The von Mangoldt Function $\Lambda(n)$

Definition 6.3 (The von Mangoldt Function): The von Mangoldt function $\Lambda: \mathbb{N} \to \mathbb{R}$ is defined by:

Theorem 6.7 (Logarithmic Divisor Sum Identity): For every positive integer $n \ge 1$:

Proof: Let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ be the prime factorization. The only divisors $d \mid n$ for which $\Lambda(d) \ne 0$ are the prime powers $p_i^j$ ($1 \le j \le a_i$). Therefore:

By Möbius Inversion:

2. Chebyshev's Functions $\psi(x)$ and $\theta(x)$

Pafnuty Chebyshev introduced these functions to study the distribution of primes.

Definition 6.4 (Chebyshev Functions): For $x \ge 1$:

1. Chebyshev's theta function: $\theta(x) = \sum_{p \le x} \ln p$
2. Chebyshev's psi function: $\psi(x) = \sum_{n \le x} \Lambda(n) = \sum_{p^k \le x} \ln p$

Theorem 6.8 (Equivalence with Prime Number Theorem): The Prime Number Theorem $\pi(x) \sim \frac{x}{\ln x}$ is logically equivalent to:

1. The Concept of Average Order

Many arithmetical functions (like $\tau(n)$ or $\mu(n)$) fluctuate wildly from point to point. To understand their macroscopic behavior, number theorists study their average order:

We say $f(n)$ has average order $g(n)$ if $\sum_{n \le x} f(n) \sim \sum_{n \le x} g(n)$.

2. Dirichlet's Divisor Problem & The Hyperbola Method

Consider the summatory function of the divisor function:

This counts the total number of integer lattice points $(u, v) \in \mathbb{N}^2$ lying under the hyperbola:

Theorem 6.9 (Dirichlet's Divisor Asymptotic, 1849): As $x \to \infty$:

where $\gamma \approx 0.57721566...$ is the Euler-Mascheroni constant.

Proof (Dirichlet's Hyperbola Method): Consider the hyperbolic region $\mathcal{R} = \{(u, v) \in \mathbb{R}^2 : u \ge 1, v \ge 1, uv \le x\}$. By symmetry across the line $u = v$, split the region into three pieces:

1. Region I: $u \le \sqrt{x}$ and $v \le x/u$.
2. Region II: $v \le \sqrt{x}$ and $u \le x/v$.
3. Overlap (square): $u \le \sqrt{x}$ and $v \le \sqrt{x}$.

Counting lattice points by inclusion-exclusion:

Replace $\lfloor x/u \rfloor = x/u - \{x/u\}$:

Recall the asymptotic for harmonic numbers $H_N = \sum_{k=1}^N \frac{1}{k} = \ln N + \gamma + O(1/N)$. Setting $N = \lfloor \sqrt{x} \rfloor$:

Multiplying by $2x$:

Now subtract the overlap square $\lfloor \sqrt{x} \rfloor^2 = (\sqrt{x} + O(1))^2 = x + O(\sqrt{x})$: