Multiplicative function

In number theory, a multiplicative function is an arithmetic function $f$ 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 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$

• $\mathrm{Id}(n)$: the identity function, defined by $\mathrm{Id}(n)=n$

• ${\mathrm{Id}}_k(n)$: the power functions, defined by ${\mathrm{Id}}_k(n)=n^k$ for any complex number $k$. As special cases we have
  • ${\mathrm{Id}}_0(n)=1(n)$, and
  • ${\mathrm{Id}}_1(n)=\mathrm{Id}(n)$.

• $\epsilon (n)$: the function defined by $\epsilon (n)=1$ if $n=1$ and $0$ otherwise; this is the unit function, so called because it is the multiplicative identity for Dirichlet convolution. Sometimes written as $u(n)$; not to be confused with $\mu (n)$.

• $\lambda (n)$: the Liouville function, $\lambda (n)=(-1{)}^{\mathrm{\Omega }(n)}$, where $\mathrm{\Omega }(n)$ is the total number of primes (counted with multiplicity) dividing $n$

The above functions are all completely multiplicative.

• $1_C(n)$: the indicator function of the set $C\subseteq \mathbb{\mathbb{Z}}$. This function is multiplicative precisely when $C$ is closed under multiplication of coprime elements. There are also other sets (not closed under multiplication) that give rise to such functions, such as 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

• $\phi (n)$: Euler's totient function, which counts the positive integers coprime to (but not bigger than) $n$

• $\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

• ${\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). As special cases we have
  • ${\sigma }_0(n)=d(n)$, the number of positive divisors of $n$,
  • ${\sigma }_1(n)=\sigma (n)$, the sum of all the positive divisors of $n$.

• ${\sigma }_k^{*}(n)$: the sum of the $k$-th powers of all unitary divisors of $n$

${\sigma }_k^{*}(n)=\sum _{\genfrac{}{}{0ex}{}{d\mid n}{\gcd (d,n/d)=1}}{d}^k$

• $\mathrm{rad}(n)$: the radical of $n$, which is the product of the distinct prime factors of $n$.

• $a(n)$: the number of non-isomorphic abelian groups of order $n$

• $\gamma (n)$, defined by $\gamma (n)=(-1{)}^{\omega (n)}$, where the additive function $\omega (n)$ is the number of distinct primes dividing $n$
• $\tau (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_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:

and therefore $r_2(1)=4\ne 1$. This shows that the function is not multiplicative. However, $r_2(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 }_0(144)={\sigma }_0(2^4){\sigma }_0(3^2)=(1^0+2^0+4^0+8^0+16^0)(1^0+3^0+9^0)=5\cdot 3=15$$ $$\sigma (144)={\sigma }_1(144)={\sigma }_1(2^4){\sigma }_1(3^2)=(1^1+2^1+4^1+8^1+16^1)(1^1+3^1+9^1)=31\cdot 13=403$$ $${\sigma }^{*}(144)={\sigma }^{*}(2^4){\sigma }^{*}(3^2)=(1^1+16^1)(1^1+9^1)=17\cdot 10=170$$

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

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

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(\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 ε. 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 {\mathrm{Id}}_k)*{\mathrm{Id}}_k=\epsilon$ (generalized Möbius inversion)
• $\phi *1=\mathrm{Id}$
• $d=1*1$
• $\sigma =\mathrm{Id}*1=\phi *d$
• ${\sigma }_k={\mathrm{Id}}_k*1$
• $\mathrm{Id}=\phi *1=\sigma *\mu$
• ${\mathrm{Id}}_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{\mathbb{Z}}}^{+}$: $$\begin{array}{rl}(f\ast g)(ab)& =\sum _{d|ab}f(d)g\left(\frac{ab}{d}\right)\\ & =\sum _{d_1|a}\sum _{d_2|b}f(d_1{d}_2)g\left(\frac{ab}{d_1{d}_2}\right)\\ & =\sum _{d_1|a}f(d_1)g\left(\frac{a}{d_1}\right)\times \sum _{d_2|b}f(d_2)g\left(\frac{b}{d_2}\right)\\ & =(f\ast g)(a)\cdot (f\ast g)(b).\end{array}$$

Dirichlet series for some multiplicative functions

• $\sum _{n\ge 1}\frac{\mu (n)}{n^s}=\frac{1}{\zeta (s)}$
• $\sum _{n\ge 1}\frac{\phi (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.

Rational arithmetical functions

An arithmetical function f is said to be a rational arithmetical function of order $(r,s)$ if there exists completely multiplicative functions g₁,...,g_r, h₁,...,h_s such that $$f=g_1\ast \cdots \ast g_r\ast h_1^{-1}\ast \cdots \ast h_s^{-1},$$ where the inverses are with respect to the Dirichlet convolution. Rational arithmetical functions of order $(1,1)$ are known as totient functions, and rational arithmetical functions of order $(2,0)$ are known as quadratic functions or specially multiplicative functions. Euler's function $\phi (n)$ is a totient function, and the divisor function ${\sigma }_k(n)$ is a quadratic function. Completely multiplicative functions are rational arithmetical functions of order $(1,0)$. Liouville's function $\lambda (n)$ is completely multiplicative. The Möbius function $\mu (n)$ is a rational arithmetical function of order $(0,1)$. By convention, the identity element $\epsilon$ under the Dirichlet convolution is a rational arithmetical function of order $(0,0)$.

All rational arithmetical functions are multiplicative. A multiplicative function f is a rational arithmetical function of order $(r,s)$ if and only if its Bell series is of the form $$f_p(x)=\sum _{n=0}^{\mathrm{\infty }}f(p^n)x^n=\frac{(1-h_1(p)x)(1-h_2(p)x)\cdots (1-h_s(p)x)}{(1-g_1(p)x)(1-g_2(p)x)\cdots (1-g_r(p)x)}$$ for all prime numbers $p$.

The concept of a rational arithmetical function originates from R. Vaidyanathaswamy (1931).

Busche-Ramanujan identities

A multiplicative function $f$ is said to be specially multiplicative if there is a completely multiplicative function $f_A$ such that

$f(m)f(n)=\sum _{d\mid (m,n)}f(mn/d^2)f_A(d)$

for all positive integers $m$ and $n$, or equivalently

$f(mn)=\sum _{d\mid (m,n)}f(m/d)f(n/d)\mu (d)f_A(d)$

for all positive integers $m$ and $n$, where $\mu$ is the Möbius function. These are known as Busche-Ramanujan identities. In 1906, E. Busche stated the identity

${\sigma }_k(m){\sigma }_k(n)=\sum _{d\mid (m,n)}{\sigma }_k(mn/d^2)d^k,$

and, in 1915, S. Ramanujan gave the inverse form

${\sigma }_k(mn)=\sum _{d\mid (m,n)}{\sigma }_k(m/d){\sigma }_k(n/d)\mu (d)d^k$

for $k=0$. S. Chowla gave the inverse form for general $k$ in 1929, see P. J. McCarthy (1986). The study of Busche-Ramanujan identities begun from an attempt to better understand the special cases given by Busche and Ramanujan.

It is known that quadratic functions $f=g_1\ast g_2$ satisfy the Busche-Ramanujan identities with $f_A=g_1{g}_2$. Quadratic functions are exactly the same as specially multiplicative functions. Totients satisfy a restricted Busche-Ramanujan identity. For further details, see R. Vaidyanathaswamy (1931).

Multiplicative function over Template:Math

Let Template:Math, 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 Template:Math

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 _{f\text{ monic}}h(f)|f{|}^{-s},$$

where for $g\in A,$ set $|g|=q^{\mathrm{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 Template:Math, every Dirichlet series of a multiplicative function h has a product representation (Euler product):

$$D_h(s)=\prod _P(\sum _{n=0}^{\mathrm{\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 _{\mathrm{deg}(f)=n}{q}^{-sn}=\sum _n(q^{n-sn})=(1-q^{1-s}{)}^{-1}.$$

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{array}{rl}(f*g)(m)& =\sum _{d\mid m}f(d)g\left(\frac{m}{d}\right)\\ & =\sum _{ab=m}f(a)g(b),\end{array}$$

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_{h*g}$ still holds.

Multivariate

Multivariate functions can be constructed using multiplicative model estimators. Where a matrix function of Template:Math is defined as $$D_N=N^2\times N(N+1)/2$$

a sum can be distributed across the product$$y_t=\sum (t/T{)}^{1/2}{u}_t=\sum (t/T{)}^{1/2}{G}_t^{1/2}{ϵ}_t$$

For the efficient estimation of Template:Math, the following two nonparametric regressions can be considered: $${\tilde{y}}_t^2=\frac{y_t^2}{g_t}={\sigma }^2(t/T)+{\sigma }^2(t/T)({ϵ}_t^2-1),$$

and $$y_t^2={\sigma }^2(t/T)+{\sigma }^2(t/T)(g_t{ϵ}_t^2-1).$$

Thus it gives an estimate value of $$L_t(\tau ;u)=\sum _{t=1}^T{K}_h(u-t/T)\left[\begin{array}{c}ln\tau +\frac{y_t^2}{g_t\tau }\end{array}\right]$$

with a local likelihood function for $y_t^2$ with known $g_t$ and unknown ${\sigma }^2(t/T)$.

Generalizations

An arithmetical function $f$ is quasimultiplicative if there exists a nonzero constant $c$ such that $cf(mn)=f(m)f(n)$ for all positive integers $m,n$ with $(m,n)=1$. This concept originates by Lahiri (1972).

An arithmetical function $f$ is semimultiplicative if there exists a nonzero constant $c$, a positive integer $a$ and a multiplicative function $f_m$ such that $f(n)=c{f}_m(n/a)$ for all positive integers $n$ (under the convention that $f_m(x)=0$ if $x$ is not a positive integer.) This concept is due to David Rearick (1966).

An arithmetical function $f$ is Selberg multiplicative if for each prime $p$ there exists a function $f_p$ on nonnegative integers with $f_p(0)=1$ for all but finitely many primes $p$ such that $f(n)=\prod _p{f}_p({\nu }_p(n))$ for all positive integers $n$, where ${\nu }_p(n)$ is the exponent of $p$ in the canonical factorization of $n$. See Selberg (1977).

It is known that the classes of semimultiplicative and Selberg multiplicative functions coincide. They both satisfy the arithmetical identity $f(m)f(n)=f((m,n))f([m,n])$ for all positive integers $m,n$. See Haukkanen (2012).

It is well known and easy to see that multiplicative functions are quasimultiplicative functions with $c=1$ and quasimultiplicative functions are semimultiplicative functions with $a=1$.

See also

• Euler product
• Bell series
• Lambert series

References

• See chapter 2 of Template:Apostol IANT
• P. J. McCarthy, Introduction to Arithmetical Functions, Universitext. New York: Springer-Verlag, 1986.

• E. Busche, Lösung einer Aufgabe über Teileranzahlen. Mitt. Math. Ges. Hamb. 4, 229--237 (1906)

• A. Selberg: Remarks on multiplicative functions. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976), pp. 232–241, Springer, 1977.

External links

• Multiplicative function at PlanetMath.