Discover

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 ''coprime'' 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

Examples

Properties

Convolution

See also

References

Examples

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

★ $phi$(''n''): Euler's totient function $phi$, counting the positive integers coprime to (but not bigger than) ''n''

★ $mu$(''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'',

★ $sigma$(''n''): the sum of all the positive divisors of ''n'',

★ $sigma$_''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

★
★ $sigma$₀(''n'') = ''d''(''n'') and

★
★ $sigma$₁(''n'') = $sigma$(''n''),

★ 1(''n''): the constant function, defined by 1(''n'') = 1 (completely multiplicative)

★ $1\_C(n)$ the indicator function of the set $C$ of squares (or cubes, or fourth powers, etc.)

★ 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''),

★ $epsilon$(''n''): the function defined by $epsilon$(''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 $mu$(''n'') (completely multiplicative).

★ (''n''/''p''), the Legendre symbol, where ''p'' is a fixed prime number (completely multiplicative).

★ $lambda$(''n''): the Liouville function, related to the number of prime factors dividing ''n'' (completely multiplicative).

★ $gamma$(''n''), defined by $gamma$(''n'')=(-1)^$omega$(n), where the additive function $omega$(''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² + 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.
In the On-Line Encyclopedia of Integer Sequences, sequences of values of a multiplicative function have the keyword "mult".
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) = $sigma$₀(144) = $sigma$₀(2⁴)$sigma$₀(3²) = (1⁰ + 2⁰ + 4⁰ + 8⁰ + 16⁰)(1⁰ + 3⁰ + 9⁰) = 5 · 3 = 15,
: $sigma$(144) = $sigma$₁(144) = $sigma$₁(2⁴)$sigma$₁(3²) = (1¹ + 2¹ + 4¹ + 8¹ + 16¹)(1¹ + 3¹ + 9¹) = 31 · 13 = 403,
: $sigma$
^★ (144) = $sigma$
^★ (2⁴)$sigma$
^★ (3²) = (1¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170.
Similarly, we have:
:$phi$(144)=$phi$(2⁴)$phi$(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) = sum_{d|n} f(d) , g left( rac{n}{d}
ight)
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 $epsilon$.
Relations among the multiplicative functions discussed above include:

★ $mu$
★ 1 = $epsilon$ (the Möbius inversion formula)

★ ($mu$ Id_''k'')
★ Id_''k'' = $epsilon$ (generalized Möbius inversion)

★ $phi$
★ 1 = Id

★ ''d'' = 1
★ 1

★ $sigma$ = Id
★ 1 = $phi$
★ ''d''

★ $sigma$_''k'' = Id_''k''
★ 1

★ Id = $phi$
★ 1 = $sigma$
★ $mu$

★ Id_''k'' = $sigma$_''k''
★ $mu$
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.)''