Multiplicative function

From Wikipedia, the free encyclopedia

Outside number theory, the term multiplicative function is usually used for completely multiplicative functions. This article discusses number theoretic multiplicative functions.

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 (or 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.

1 Examples
2 Properties
3 Convolution
- 3.1 The Dirichlet convolution of two multiplicative functions is multiplicative
4 Proving convolution identities
5 See also
6 References
7 External links

[edit] Examples

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

$φ$ (n): Euler's totient function $φ$ , counting the positive integers coprime to (but not bigger than) n
$μ$ (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,
$σ$ (n): the sum of all the positive divisors of n,
σ_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
- $σ$ ₀(n) = d(n) and
- $σ$ ₁(n) = $σ$ (n),
$a (n)$ : the number of non-isomorphic abelian groups of order 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),
$ε$ (n): the function defined by $ε$ (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 $μ$ (n) (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₂(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.

[edit] 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¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170.

Similarly, we have:

φ

(144)=

φ

(2⁴)

φ

(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.

[edit] 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( \frac{n}{d} \right)$

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_k) * Id_k = $ε$ (generalized Möbius inversion)
$φ$ * 1 = 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.

[edit] The Dirichlet convolution of two multiplicative functions is multiplicative

This follows by direct evaluation of

$(f * g)(m) \; (f*g)(n),$

making repeated use of the fact that $(m, n) = 1$ and $(d 1, d 2) = 1$ if $d 1 | m$ and $d 2 | n,$ as in

$\sum_{d_1|m} f(d_1) g(m/d_1) \sum_{d_2|n} f(d_2) g(n/d_2) = \sum_{d_1|m} \sum_{d_2|n} f(d_1) f(d_2) g(m/d_1) g(n/d_2).$

Now using the fact that $f$ and $g$ are multiplicative this becomes

$\sum_{d_1|m} \sum_{d_2|n} f(d_1 d_2) g(m/d_1 \; n/d_2) = \sum_{d|m n} f(d) g(m n/d) = (f * g)(mn).$

[edit] Proving convolution identities

There is a very useful theorem for proving convolution identities, which says that if f, g and h are multiplicative, and one wants to prove that

$f \, * \, g = h,$

then it suffices to prove it for powers of primes.

The corresponding Dirichlet series

$F(s) = \sum_{n\ge 1} \frac{f(n)}{n^s}, \quad G(s) = \sum_{n\ge 1} \frac{g(n)}{n^s}, \quad \mbox{and} \quad H(s) = \sum_{n\ge 1} \frac{h(n)}{n^s}$

obey the relation

$F(s) \; G(s) = H(s).$

This means that convolution identities may be used to find closed forms of Dirichlet series corresponding to multiplicative functions. These closed forms may in turn be used to study the average order of multiplicative functions through the use of Perron's formula.

The proof of this theorem is by mathematical induction on the number of distinct prime factors of n. The base case of the induction is that n has just one prime factor, in which case

$(f \, * \, g)(n) = h(n),$

because we assumed that it holds for powers of primes.

For the induction step, let

$n = p^v m \quad \mbox{where} \quad v \ge 1, \; m > 1 \quad \mbox{and} \quad (p, m) = 1.$

Start with

$(f \, * \, g)(n) = \sum_{d|n} f(d) \, g\left(\frac{n}{d}\right)$

and split the set of divisors of n into those that are coprime to p, and those that are not:

$\sum_{d|m} f(d) \, g\left( p^v \frac{m}{d}\right) \, + \, \sum_{d|m} \sum_{w=1}^v f(d p^w) \, g\left(p^{v-w} \frac{m}{d} \right).$

Using the fact that f and g are multiplicative, this becomes

$g(p^v) \sum_{d|m} f(d) \, g\left(\frac{m}{d}\right) \, + \, \sum_{d|m} f(d) \, g\left(\frac{m}{d}\right) \, \sum_{w=1}^v f(p^w) \, g(p^{v-w}).$

Now $m$ has one fewer prime factor than $n$ , so by the induction hypothesis, we have

$\sum_{d|m} f(d) \, g\left(\frac{m}{d}\right) = h(m)$ ,

which yields

$h(m) \, g(p^v) \, + \, h(m) \, \sum_{w=1}^v f(p^w) \, g(p^{v-w})$

$h(m) \, \sum_{w=0}^v f(p^w) \, g(p^{v-w}) = h(m) \, h(p^v) = h(n),$

because we assumed the convolution holds for powers of primes, and by multiplicativity of h. QED.

We may now prove some convolution identities of multiplicative functions by verifying that they hold for powers of primes.

[edit] First example: Moebius inversion

We have

$\mu \, * \, 1 = \epsilon.$

This certainly holds for powers $n=p^v\,$ of primes, where the left evaluates to

$\sum_{w=0}^v \mu(p^w) = 1-1 = 0 = \epsilon(n).$

This proves the Moebius inversion formula, through

$(f \, * \, 1) \, * \, \mu = f \, * \, (1 \, * \, \mu) = f \, * \, \epsilon = f.$

In terms of Dirichlet series,

$\sum_{n\ge 1} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}.$

The Riemann Zeta function $ζ(s)$ will appear in all convolutions presented here.

[edit] Second example: the classic totient identity

We show that

$\varphi \, * \, 1 = n.$

The left is

$\sum_{w=0}^v \varphi(p^w) = 1 + \sum_{w=1}^v \left( p^w - p^{w-1} \right) = 1 + p^v - 1 = n, \quad \mbox{QED.}$

In terms of Dirichlet series,

$\sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.$

[edit] Third example: the square of the divisor function

We show that

$d^2 \, * \, 1_C = d \, * \, d,$

where $1 C$ is the indicator function of the set of naturals that are squares.

The right is

$\sum_{w=0}^v d(p^w) d(p^{v-w}) = \sum_{w=0}^v (w+1)(v-w+1) = \frac{1}{6} (v+1) (v+2) (v+3).$

The left is

$\sum_{w=0}^v d(p^w)^2 \; 1_C(p^{v-w}) = \sum_{w=0}^v (w+1)^2 \; 1_C(p^{v-w}).$

Now there are two cases, depending on whether v is even or odd. Let $v = 2 q$ where $q\ge 1$ . This gives

$\sum_{u=0}^q (2u+1)^2 = \frac{1}{6} (2q+1) (2q+2) (2q+3).$

Next let $v = 2 q + 1$ where $q\ge 0$ . This in turn gives

$\sum_{u=0}^q ((2u+1)+1)^2 = \frac{1}{6} (2q+2) (2q+3) (2q+4), \quad \mbox{QED.}$

In terms of Dirichlet series,

$\sum_{n\ge 1} \frac{d(n)^2}{n^s} = \frac{\zeta(s)^4}{\zeta(2s)}.$

[edit] Fourth example: an exotic identity

Here we show that

$2^\omega \, * \, 1_C = d.$

The left is

$\sum_{w=0}^v 2^{\omega(p^w)} \; 1_C(p^{v-w}) = 1_C(p^v) + 2 \sum_{w=1}^v 1_C(p^{v-w}).$

Once more there are two cases. Let $v = 2 q$ where $q\ge 1$ . We obtain

$1 + 2q = v+1 = d(n).\,$

Furthermore, when $v = 2 q + 1$ where $q\ge 0$ we find

$0 + 2(q+1) = v+1 = d(n), \quad \mbox{QED.}$

In terms of Dirichlet series,

$\sum_{n\ge 1} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta(s)^2}{\zeta(2s)}.$

[edit] See also

[edit] References

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

[edit] External links

Planet Math

Categories: Multiplicative functions

Multiplicative function

From Wikipedia, the free encyclopedia

Contents

[edit] Examples

[edit] Properties

[edit] Convolution

[edit] The Dirichlet convolution of two multiplicative functions is multiplicative

[edit] Proving convolution identities

[edit] First example: Moebius inversion

[edit] Second example: the classic totient identity

[edit] Third example: the square of the divisor function

[edit] Fourth example: an exotic identity

[edit] See also

[edit] References

[edit] External links

Views

Navigation

Interaction

Search

Languages