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 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 all functions with the property f(ab) = f(a) f(b) for all arguments a and b. This article discusses number theoretic multiplicative functions.

Examples

Examples of multiplicative functions include many functions of importance in number theory, such as:

• φ(n): 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,
• σ_k(n): the sum of the k-th powers of all the positive divisors of n (where k may be any complex number),
• Id(n): identity function, defined by Id(n) = n
• Id^k(n): the power functions, defined by Id^k(n) = n^k for any natural (or even complex) number k,
• 1(n): the constant function, defined by 1(n) = 1
• ε(n): the function defined by ε(n) = 1 if n = 1 and = 0 if n > 1.

An example of a non-multiplicative function is the arithmetic function r₂(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²+0² = (-1)²+0² = 0²+1² = 0²+(-1)²

and therefore r₂(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r₂(n)/4 is multiplicative.

See arithmetic function for some examples of non-multiplicative functions.

Properties

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⁴ · 3²:

d(144) = σ₀(144) = σ₀(2⁴)σ₀(3²) = (1⁰+2⁰+4⁰+8⁰+16⁰)(1⁰+3⁰+9⁰) = 5 · 3 = 15,

σ(144) = σ₁(144) = σ₁(2⁴)σ₁(3²) = (1¹+2¹+4¹+8¹+16¹)(1¹+3¹+9¹) = 31 · 13 = 403,

σ₂(144) = σ₂(2⁴)σ₂(3²) = (1²+2²+4²+8²+16²)(1²+3²+9²) = 341 · 91 = 31031,

σ₃(144) = σ₃(2⁴)σ₃(3²) = (1³+2³+4³+8³+16³)(1³+3³+9³) = 4681 &middot 757 = 3543517.

Similarly, we have:

φ(144)=φ(2⁴)φ(3²) = 8 &middot 6 = 48

Convolution

If f and g are two arithmetic functions, one defines a new arithmetic function f*g, the 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.

Some general properties of this operation include (here the argument n is omitted in all functions):

• If both f and g are multiplicative, then so is f*g.
• f*g = g*f
• (f*g)*h = f*(g*h)
• f*ε = ε*f = f

This shows that the multiplicative functions with convolution form a commutative monoid with identity element ε.

Relations among the multiplicative functions discussed above include:

• μ*1 = ε (the Moebius inversion formula)
• 1*1 = d
• Id*1 = σ
• Id^k*1 = σ_k
• φ*1 = Id