multiplicative function

In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and
$f(ab) = f(a)f(b)$ whenever ''a'' and ''b'' are coprime.

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.

Examples

Some multiplicative functions are defined to make formulas easier to write:

* 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 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 otherwise, sometimes called ''multiplication unit for Dirichlet convolution'' or simply the ''unit function'' (completely multiplicative). Sometimes written as ''u''(''n''), but not to be confused with ''μ''(''n'') .
* 1_''C''(''n''), the indicator function of the set ''C'' ⊂ Z, for certain sets ''C''. The indicator function 1_''C''(''n'') is multiplicative precisely when the set ''C'' has the following property for any coprime numbers ''a'' and ''b'': the product ''ab'' is in ''C'' if and only if the numbers ''a'' and ''b'' are both themselves in ''C''. This is the case if ''C'' is the set of squares, cubes, or ''k''-th powers, or if ''C'' is the set of square-free numbers.

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

* gcd(''n'',''k''): the greatest common divisor of ''n'' and ''k'', as a function of ''n'', where ''k'' is a fixed integer.
* $\varphi(n)$: Euler's totient function $\varphi$, counting the positive integers coprime to (but not bigger than) ''n''
* ''μ''(''n''): the Möbius function, the parity (−1 for odd, +1 for even) of the number of prime factors of square-free numbers; 0 if ''n'' is not square-free
* ''σ''_''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). Special cases we have
** ''σ''₀(''n'') = ''d''(''n'') the number of positive divisors of ''n'',
** ''σ''₁(''n'') = ''σ''(''n''), the sum of all the positive divisors of ''n''.
* ''a''(''n''): the number of non-isomorphic abelian groups of order ''n''.
* ''λ''(''n''): the Liouville function, ''λ''(''n'') = (−1)^Ω(''n'') where Ω(''n'') is the total number of primes (counted with multiplicity) dividing ''n''. (completely multiplicative).
* ''γ''(''n''), defined by ''γ''(''n'') = (−1)^''ω''(n), where the additive function ''ω''(''n'') is the number of distinct primes dividing ''n''.
* ''τ''(''n''): the Ramanujan tau function.
* All Dirichlet characters are completely multiplicative functions. For example
** (''n''/''p''), the Legendre symbol, considered as a function of ''n'' where ''p'' is a fixed prime number.

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:

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²:

Similarly, we have:
$\varphi(144) = \varphi(2^4) \, \varphi(3^2) = 8 \cdot 6 = 48$

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

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_ f(d) \, g \left( \frac \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 ''ε''. Convolution is commutative, associative, and distributive over addition.

Relations among the multiplicative functions discussed above include:

* $\mu * 1 = \varepsilon$ (the Möbius inversion formula)
* $(\mu \operatorname_k) * \operatorname_k = \varepsilon$ (generalized Möbius inversion)
* $\varphi * 1 = \operatorname$
* $d = 1 * 1$
* $\sigma = \operatorname * 1 = \varphi * d$
* $\sigma_k = \operatorname_k * 1$
* $\operatorname = \varphi * 1 = \sigma * \mu$
* $\operatorname_k = \sigma_k * \mu$

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

The Dirichlet convolution of two multiplicative functions is again multiplicative. A proof of this fact is given by the following expansion for relatively prime $a,b \in \mathbb^$:
$\begin (f \ast g)(ab) & = \sum_ f(d) g\left(\frac\right) \\ &= \sum_ \sum_ f(d_1d_2) g\left(\frac\right) \\ &= \sum_ f(d_1) g\left(\frac\right) \times \sum_ f(d_2) g\left(\frac\right) \\ &= (f \ast g)(a) \cdot (f \ast g)(b). \end$

Dirichlet series for some multiplicative functions

* $\sum_ \frac = \frac$
* $\sum_ \frac = \frac$
* $\sum_ \frac = \frac$
* $\sum_ \frac = \frac$
More examples are shown in the article on Dirichlet series.

Multiplicative function over

Let , the polynomial ring over the finite field with ''q'' elements. ''A'' is a principal ideal domain and therefore ''A'' is a unique factorization domain.

A complex-valued function $\lambda$ on ''A'' is called multiplicative if $\lambda(fg)=\lambda(f)\lambda(g)$ whenever ''f'' and ''g'' are relatively prime.

Zeta function and Dirichlet series in

Let ''h'' be a polynomial arithmetic function (i.e. a function on set of monic polynomials over ''A''). Its corresponding Dirichlet series is defined to be
: $D_h(s)=\sum_h(f), f, ^,$
where for $g\in A,$ set $, g, =q^$ if $g\ne 0,$ and $, g, =0$ otherwise.

The polynomial zeta function is then
: $\zeta_A(s)=\sum_, f, ^.$

Similar to the situation in , every Dirichlet series of a multiplicative function ''h'' has a product representation ( Euler product):
: $D_(s)=\prod_P \left(\sum_^h(P^), P, ^\right),$
where the product runs over all monic irreducible polynomials ''P''. For example, the product representation of the zeta function is as for the integers:
: $\zeta_A(s)=\prod_(1-, P, ^)^.$

Unlike the classical zeta function, $\zeta_A(s)$ is a simple rational function:
: $\zeta_A(s)=\sum_f , f, ^ = \sum_n\sum_q^=\sum_n(q^)=(1-q^)^.$

In a similar way, If ''f'' and ''g'' are two polynomial arithmetic functions, one defines ''f'' * ''g'', the ''Dirichlet convolution'' of ''f'' and ''g'', by
: $\begin (f*g)(m) &= \sum_ f(d)g\left(\frac\right) \\ &= \sum_f(a)g(b), \end$
where the sum is over all monic divisors ''d'' of ''m'', or equivalently over all pairs (''a'', ''b'') of monic polynomials whose product is ''m''. The identity $D_h D_g = D_$ still holds.

See also

* Euler product
* Bell series
* Lambert series

References

* See chapter 2 of

External links

* {{PlanetMath , urlname=multiplicativefunction , title=Multiplicative function