Multiplicative function
In
number theory, a
multiplicative function is an
arithmetic function f(
n) of the positive
integer n with the property that
f(1) = 1 and whenever
a and
b are
coprime, then
- f(ab) = f(a) f(b).
An arithmetic function
f(
n) is said to be
completely (totally) multiplicative if
f(1) = 1 and
f(
ab) =
f(
a)
f(
b) holds
for all positive integers
a and
b, even when they are not coprime. In this case the function is a homomorphism of monoids and, because of the
fundamental theorem of arithmetic, is completely determined by its restriction to the
prime numbers. Every completely multiplicative function is multiplicative.
Outside number theory, the term multiplicative is usually used for functions with the property f(ab) = f(a) f(b) for all arguments a and b. This article discusses number theoretic multiplicative functions.
Examples of multiplicative functions include many functions of importance in number theory, such as:
- φ(n): the Euler's φ function, counting the positive integers coprime to n
- μ(n): the Möbius function, related to the number of prime factors of square-free numbers
- d(n): the number of positive divisors of n,
- σ(n): the sum of all the positive divisors of n,
- σ^{*}(n): the unitary divisor function, the sum of all the positive unitary divisors of n,
- σ_{k}(n): the sum of the k-th powers of all the positive divisors of n (where k may be any complex number). In special cases we have
- σ_{0}(n) = d(n) and
- σ_{1}(n) = σ(n),
- 1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
- Id(n): identity function, defined by Id(n) = n (completely multiplicative)
- Id_{k}(n): the power functions, defined by Id_{k}(n) = n^{k} for any natural (or even complex) number k (completely multiplicative). As special cases we have
- Id_{0}(n) = 1(n) and
- Id_{1}(n) = Id(n),
- ε(n): the function defined by ε(n) = 1 if n = 1 and = 0 if n > 1, sometimes called multiplication unit for Dirichlet convolution (completely multiplicative).
- (n/p), the Legendre symbol, where p is a fixed prime number (completely multiplicative).
- λ(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
- γ(n), defined by γ(n)=(-1)^{ω(n)}, where the additive function ω(n) is the number of distinct primes dividing n.
- All Dirichlet characters are completely multiplicative functions.
An example of a non-multiplicative function is the arithmetic function
r_{2}(
n) - the number of representations of
n as a sum of squares of two integers,
positive,
negative, or
zero, where in counting the number of ways, reversal of order is allowed. For example:
- 1 = 1^{2} + 0^{2} = (-1)^{2} + 0^{2} = 0^{2} + 1^{2} = 0^{2} + (-1)^{2}
and therefore
r_{2}(1) = 4 ≠ 1. This shows that the function is not multiplicative. However,
r_{2}(
n)/4 is multiplicative.
See arithmetic function for some examples of non-multiplicative functions.
A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if n is a product of powers of distinct primes, say n = p^{a} q^{b} ..., then
f(n) = f(p^{a}) f(q^{b}) ...
This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 2^{4} · 3^{2}:
- d(144) = σ_{0}(144) = σ_{0}(2^{4})σ_{0}(3^{2}) = (1^{0} + 2^{0} + 4^{0} + 8^{0} + 16^{0})(1^{0} + 3^{0} + 9^{0}) = 5 · 3 = 15,
- σ(144) = σ_{1}(144) = σ_{1}(2^{4})σ_{1}(3^{2}) = (1^{1} + 2^{1} + 4^{1} + 8^{1} + 16^{1})(1^{1} + 3^{1} + 9^{1}) = 31 · 13 = 403,
- σ^{*}(144) = σ^{*}(2^{4})σ^{*}(3^{2}) = (1^{1} + 16^{1})(1^{1} + 9^{1}) = 17 · 10 = 170.
Similarly, we have:
- φ(144)=φ(2^{4})φ(3^{2}) = 8 · 6 = 48
In general, if
f(
n) is a multiplicative function and
a,
b are two positive integers, then
- f(a) · f(b) = f(gcd(a,b)) · f(lcm(a,b)).
Convolution
If f and g are two multiplicative functions, one defines a new multiplicative function f * g, the Dirichlet convolution of f and g, by
- (f * g)(n) = ∑_{d|n} f(d)g(n/d)
where the sum extends over all positive divisors
d of
n.
With this operation, the set of all multiplicative functions turns into an
abelian group; the
identity element is ε.
Relations among the multiplicative functions discussed above include:
- ε = μ * 1 (the Möbius inversion formula)
- φ = μ * Id
- d = 1 * 1
- σ = Id * 1 = φ * d
- σ_{k} = Id_{k} * 1
- Id = φ * 1 = σ * μ
- Id_{k} = σ_{k} * μ
The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the
Dirichlet ring.