Arithmetic Functions and Multiplicative Number Theory

Understanding the behavior of integers often requires looking beyond individual numbers to patterns across the whole set of natural numbers. Arithmetic functions are the essential tools for this task, mapping integers to complex numbers and revealing deep structural properties. Their study, particularly through the lens of multiplicative number theory, provides a powerful algebraic framework for solving counting problems, analyzing asymptotic distributions, and uncovering relationships that form the bedrock of analytic number theory. Mastering these functions and their interactions is key to progressing from elementary number theory to more advanced analytical techniques.

Fundamental Arithmetic Functions and Multiplicativity

An arithmetic function is any function $f:\mathbb{N}\to \mathbb{C}$. While this definition is broad, the most impactful functions are those defined by intrinsic number-theoretic properties. Three cornerstone examples are:

1. The divisor function $\tau (n)$: This function counts the number of positive divisors of $n$. For example, $\tau (12)=6$ because the divisors of 12 are 1, 2, 3, 4, 6, and 12.
2. The sum-of-divisors function $\sigma (n)$: This sums all positive divisors of $n$. For instance, $\sigma (12)=1+2+3+4+6+12=28$.
3. Euler's totient function $\phi (n)$: This counts the number of integers between 1 and $n$ that are coprime to $n$ (i.e., share no common factors other than 1). We have $\phi (12)=4$, as the numbers 1, 5, 7, and 11 are coprime to 12.

These functions exhibit a crucial simplifying property known as multiplicativity. An arithmetic function $f$ is called multiplicative if $f(mn)=f(m)f(n)$ for all pairs of coprime integers $m$ and $n$ (i.e., $\gcd (m,n)=1$). This property is immensely powerful. It means that to evaluate a multiplicative function for any integer $n$, you only need to know its values on prime powers. If $n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$ is the prime factorization, then for a multiplicative $f$, $$f(n)=f(p_1^{a_1})f(p_2^{a_2})\cdots f(p_k^{a_k}).$$ Both $\sigma (n)$ and $\phi (n)$ are multiplicative. For a prime power $p^a$, $\phi (p^a)=p^a-p^{a-1}=p^a(1-\frac{1}{p})$. Therefore, for a general $n$, we have the elegant product formula: $$\phi (n)=n\prod _{p\mid n}\left(1-\frac{1}{p}\right).$$ This formula, a direct consequence of multiplicativity, is far more efficient for computation than counting coprime numbers directly.

The Möbius Function and Dirichlet Convolution

To unlock deeper relationships between arithmetic functions, we need an algebraic operation. This is provided by Dirichlet convolution. Given two arithmetic functions $f$ and $g$, their Dirichlet convolution $f\ast g$ is defined as: $$(f\ast g)(n)=\sum _{d\mid n}f(d)g\left(\frac{n}{d}\right),$$ where the sum is over all positive divisors $d$ of $n$. For example, the divisor sum function can be expressed as $\sigma =u\ast N$, where $u(n)=1$ is the constant-1 function and $N(n)=n$ is the identity function.

The set of arithmetic functions, under pointwise addition and Dirichlet convolution, forms a commutative ring. The multiplicative identity in this ring is the function $\epsilon (n)$, defined as $\epsilon (1)=1$ and $\epsilon (n)=0$ for $n>1$. Crucially, a multiplicative function has a Dirichlet inverse (another multiplicative function) if and only if $f(1)\ne 0$.

A central character in this ring is the Möbius function $\mu (n)$. It is defined multiplicatively based on the prime factorization of $n$: $$\mu (n)=\{\begin{array}{ll}1& \text{if }n=1,\\ (-1{)}^k& \text{if }n=p_1{p}_2\cdots p_k\text{ (squarefree with }k\text{ primes)},\\ 0& \text{if }n\text{ has a squared prime factor }(p^2\mid n).\end{array}$$ The Möbius function is the Dirichlet inverse of the constant-1 function $u(n)$. That is, $(\mu \ast u)=\epsilon$. This simple algebraic fact leads to one of the most useful tools in number theory.

The Möbius Inversion Formula and Its Applications

The relationship $\mu \ast u=\epsilon$ gives rise to the powerful Möbius inversion formula. It states: If $g(n)={\sum }_{d\mid n}f(d)$, then $f(n)={\sum }_{d\mid n}\mu (d)g\left(\frac{n}{d}\right)$. In the language of Dirichlet convolution, if $g=f\ast u$, then $f=g\ast \mu$.

This formula allows us to invert sums over divisors. Consider Euler's totient function. A classic identity states $n={\sum }_{d\mid n}\phi (d)$. For instance, for $n=12$, the sum is $\phi (1)+\phi (2)+\phi (3)+\phi (4)+\phi (6)+\phi (12)=1+1+2+2+2+4=12$. Applying Möbius inversion to $N=\phi \ast u$ immediately yields a formula for $\phi$: $$\phi (n)=\sum _{d\mid n}\mu (d)\frac{n}{d}=n\sum _{d\mid n}\frac{\mu (d)}{d}.$$ This connects $\phi$ directly to $\mu$ and leads back to the product formula. Möbius inversion is a workhorse for solving problems in combinatorics and number theory where objects are counted with over-inclusion, such as counting irreducible polynomials over finite fields or numbers with specific greatest common divisor properties.

Average Order and Asymptotic Estimates

While values of arithmetic functions fluctuate wildly ($\sigma (n)$ can be large for abundant numbers, $\phi (n)$ is typically smaller), multiplicative number theory often seeks to understand their average behavior. The average order of an arithmetic function $f(n)$ is a simpler function $g(n)$ such that the summatory function ${\sum }_{n\le x}f(n)$ is asymptotically close to ${\sum }_{n\le x}g(n)$.

Finding average orders involves summation techniques and often exploits the multiplicative structure via Dirichlet convolution. A landmark result is the average order of the divisor function: $$\sum _{n\le x}\tau (n)=x\log x+(2\gamma -1)x+O(\sqrt{x}),$$ where $\gamma$ is the Euler-Mascheroni constant. This tells us that, on average, an integer near $x$ has about $\log x$ divisors.

For Euler's totient, a beautiful result emerges from the identity $n={\sum }_{d\mid n}\phi (d)$. Summing both sides over $n\le x$ and rearranging leads to: $$\sum _{n\le x}\phi (n)=\frac{3}{{\pi }^2}{x}^2+O(x\log x).$$ Thus, the average value of $\phi (n)/n$ for $n\le x$ is asymptotically $6/{\pi }^2$, which is also the probability that two randomly chosen integers are coprime. These asymptotic estimates are fundamental results that connect discrete arithmetic properties to continuous analysis and constants like $\pi$.

Common Pitfalls

1. Assuming full multiplicativity: A function is completely multiplicative if $f(mn)=f(m)f(n)$ holds for all integers $m,n$, not just coprime ones. This is a much stronger condition. Euler's $\phi (n)$ is multiplicative but not completely multiplicative, as $\phi (4)=2$ but $\phi (2)\phi (2)=1$. Always check the coprime condition.
2. Misapplying the Möbius inversion formula: The formula requires the sum to be over all positive divisors. You cannot apply it directly to sums like ${\sum }_{d=1}^{n}f(d)$. Carefully verify that the lower limit of summation is $d\mid n$.
3. Confusing the Möbius function definition: The value $\mu (n)=0$ is assigned not just to even numbers, but to any integer divisible by a square greater than 1 (e.g., 4, 8, 9, 12, 18). This is easy to overlook when performing manual calculations.
4. Over-interpreting average orders: An average order describes the aggregate behavior of the summatory function, not a pointwise bound. Saying "the average order of $\tau (n)$ is $\log n$" does not mean $\tau (n)\approx \log n$ for most $n$; individual values can deviate significantly (primes have $\tau (n)=2$). It describes the growth of the cumulative sum.

Summary

• Arithmetic functions like $\tau (n)$, $\sigma (n)$, and Euler's totient function $\phi (n)$ encode fundamental number-theoretic data. Their multiplicative property allows evaluation via prime factorizations, leading to formulas like $\phi (n)=n{\prod }_{p|n}(1-1/p)$.
• Dirichlet convolution $(f\ast g)(n)={\sum }_{d|n}f(d)g(n/d)$ provides an algebraic ring structure for manipulating arithmetic functions, where the Möbius function $\mu (n)$ serves as the inverse of the constant-1 function.
• The Möbius inversion formula is a direct consequence of this algebra: if $g(n)={\sum }_{d|n}f(d)$, then $f(n)={\sum }_{d|n}\mu (d)g(n/d)$. It is an indispensable tool for inverting divisor sums and proving identities.
• Studying the average order of these functions reveals their asymptotic behavior. Key results include ${\sum }_{n\le x}\tau (n)\sim x\log x$ and ${\sum }_{n\le x}\phi (n)\sim 3x^2/{\pi }^2$, connecting discrete arithmetic to analytical limits.