Multiplicative function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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.

Examples[edit]

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

  • 1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
  • 1_C(n) the indicator function of the set C\subset \mathbb{Z}. This is multiplicative if the set C has the property that if a and b are in C, gcd(a, b)=1, then ab is also in C. This is the case if C is the set of squares, cubes, or higher powers, or if C is the set of square-free numbers.
  • Idk(n): the power functions, defined by Idk(n) = nk for any complex number k (completely multiplicative). As special cases we have
    • Id0(n) = 1(n) and
    • Id1(n) = Id(n).
  • \epsilon(n): the function defined by \epsilon(n) = 1 if n = 1 and 0 otherwise, sometimes called multiplication unit for Dirichlet convolution or simply the unit function; the Kronecker delta δin; sometimes written as u(n), not to be confused with \mu(n) (completely multiplicative).

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

  • \mu(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
  • \sigmak(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
    • \sigma0(n) = d(n) the number of positive divisors of n,
    • \sigma1(n) = \sigma(n), the sum of all the positive divisors of n.
  • a(n): the number of non-isomorphic abelian groups of order n.
  • \lambda(n): the Liouville function, λ(n) = (−1)Ω(n) where Ω(n) is the total number of primes (counted with multiplicity) 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.

An example of a non-multiplicative function is the arithmetic function r2(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 = 12 + 02 = (-1)2 + 02 = 02 + 12 = 02 + (-1)2

and therefore r2(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r2(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[edit]

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 = pa qb ..., then f(n) = f(pa) f(qb) ...

This property of multiplicative functions significantly reduces the need for computation, as in the following examples for n = 144 = 24 · 32:

d(144) = \sigma0(144) = \sigma0(24)\sigma0(32) = (10 + 20 + 40 + 80 + 160)(10 + 30 + 90) = 5 · 3 = 15,
\sigma(144) = \sigma1(144) = \sigma1(24)\sigma1(32) = (11 + 21 + 41 + 81 + 161)(11 + 31 + 91) = 31 · 13 = 403,
\sigma*(144) = \sigma*(24)\sigma*(32) = (11 + 161)(11 + 91) = 17 · 10 = 170.

Similarly, we have:

\varphi(144)=\varphi(24)\varphi(32) = 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[edit]

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 \epsilon. Convolution is commutative, associative, and distributive over addition.

Relations among the multiplicative functions discussed above include:

  • \mu * 1 = \epsilon (the Möbius inversion formula)
  • (\mu Idk) * Idk = \epsilon (generalized Möbius inversion)
  • \varphi * 1 = Id
  • d = 1 * 1
  • \sigma = Id * 1 = \varphi * d
  • \sigmak = Idk * 1
  • Id = \varphi * 1 = \sigma * \mu
  • Idk = \sigmak * \mu

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

Dirichlet series for some multiplicative functions[edit]

  • \sum_{n\ge 1} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}
  • \sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}
  • \sum_{n\ge 1} \frac{d(n)^2}{n^s} = \frac{\zeta(s)^4}{\zeta(2s)}
  • \sum_{n\ge 1} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta(s)^2}{\zeta(2s)}

More examples are shown in the article on Dirichlet series.

Multiplicative function over Fq[X][edit]

Let A=Fq[X], the polynomial ring over the finite field with q elements. A is principal ideal domain and therefore A is 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 Fq[X][edit]

Let h be a polynomial arithmetic function (i.e. a function on set of monic polynomials over A). Its corresponding Dirichlet series define to be

D_{h}(s)=\sum_{f\text{ monic}}h(f)|f|^{-s},

where for g\in A, set |g|=q^{deg(g)} if g\ne 0, and |g|=0 otherwise.

The polynomial zeta function is then

\zeta_{A}(s)=\sum_{f\text{ monic}}|f|^{-s}.

Similar to the situation in N, every Dirichlet series of a multiplicative function h has a product representation (Euler product):

D_{h}(s)=\prod_{P}(\sum_{n\mathop =0}^{\infty}h(P^{n})|P|^{-sn}),

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_{P}(1-|P|^{-s})^{-1}.

Unlike the classical zeta function, \zeta_{A}(s) is a simple rational function:

\zeta_{A}(s)=\sum_{f}(|f|^{-s})=\sum_{n}\sum_{\text{deg(f)=n}}q^{-sn}=\sum_{n}(q^{n-sn})=(1-q^{1-s})^{-1}.

In a similar way, If ƒ and g are two polynomial arithmetic functions, one defines ƒ * g, the Dirichlet convolution of ƒ and g, by


\begin{align}
(f*g)(m) 
&= \sum_{d\,\mid \,m} f(m)g\left(\frac{m}{d}\right) \\
&= \sum_{ab\,=\,f}f(a)g(b)
\end{align}

where the sum extends 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_{h*g} still holds.

See also[edit]

References[edit]

External links[edit]