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.

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 requires either f(1) = 1, or f(a) = 0 for all a except a = 1. This article discusses number theoretic multiplicative functions.

Contents

1 Examples 2 Properties 3 Convolution 4 See also 5 References

Examples

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

• <math>\phi<math>(n): Euler's Totient function <math>\phi<math>, counting the positive integers coprime to (but not bigger than) n
• <math>\mu<math>(n): the Möbius function, related to the number of prime factors of square-free numbers
• gcd(n,k): the greatest common divisor of n and k, where k is a fixed integer.
• d(n): the number of positive divisors of n,
• <math>\sigma<math>(n): the sum of all the positive divisors of n,
• <math>\sigma<math>_k(n): the divisor function, which is 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
  • <math>\sigma<math>₀(n) = d(n) and
  • <math>\sigma<math>₁(n) = <math>\sigma<math>(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₀(n) = 1(n) and
  • Id₁(n) = Id(n),
• <math>\epsilon<math>(n): the function defined by <math>\epsilon<math>(n) = 1 if n = 1 and = 0 if n > 1, sometimes called multiplication unit for Dirichlet convolution or simply the unit function; sometimes written as u(n), not to be confused with <math>\mu<math>(n) (completely multiplicative).
• (n/p), the Legendre symbol, where p is a fixed prime number (completely multiplicative).
• <math>\lambda<math>(n): the Liouville function, related to the number of prime factors dividing n (completely multiplicative).
• <math>\gamma<math>(n), defined by <math>\gamma<math>(n)=(-1)^{<math>\omega<math>(n)}, where the additive function <math>\omega<math>(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₂(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 other 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) = <math>\sigma<math>₀(144) = <math>\sigma<math>₀(2⁴)<math>\sigma<math>₀(3²) = (1⁰ + 2⁰ + 4⁰ + 8⁰ + 16⁰)(1⁰ + 3⁰ + 9⁰) = 5 · 3 = 15,

<math>\sigma<math>(144) = <math>\sigma<math>₁(144) = <math>\sigma<math>₁(2⁴)<math>\sigma<math>₁(3²) = (1¹ + 2¹ + 4¹ + 8¹ + 16¹)(1¹ + 3¹ + 9¹) = 31 · 13 = 403,

<math>\sigma<math>^*(144) = <math>\sigma<math>^*(2⁴)<math>\sigma<math>^*(3²) = (1¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170.

Similarly, we have:

<math>\phi<math>(144)=<math>\phi<math>(2⁴)<math>\phi<math>(3²) = 8 · 6 = 48

In general, if f(n) is a multiplicative function and a, b are any two positive integers, then

f(a) · f(b) = f(gcd(a,b)) · f(lcm(a,b)).

Every completely multiplicative function is a homomorphism of monoids and is completely determined by its restriction to the prime numbers.

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 <math>\epsilon<math>.

Relations among the multiplicative functions discussed above include:

• <math>\epsilon<math> = <math>\mu<math> * 1 (the Möbius inversion formula)
• <math>\phi<math> = <math>\mu<math> * Id
• d = 1 * 1
• <math>\sigma<math> = Id * 1 = <math>\phi<math> * d
• <math>\sigma<math>_k = Id_k * 1
• Id = <math>\phi<math> * 1 = <math>\sigma<math> * <math>\mu<math>
• Id_k = <math>\sigma<math>_k * <math>\mu<math>

The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the Dirichlet ring.

See also

• Euler product
• Bell series
• Lambert series

References

• Tom M.Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. ISBN 0-387-90163-9 (See Chapter 2.)de:Multiplikativität

es:Función multiplicativa fr:Fonction multiplicative it:Funzione moltiplicativa ko:곱셈적 함수 sv:Multiplikativ funktion zh:積性函數