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.
The sum of the k-th powers of the unitary divisors is denoted by σ*_k(n):

\sigma _{k}^{*}(n)=\sum _{d\,\mid \,n \atop \gcd(d,\,n/d)=1}\!\!d^{k}.

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:

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 _{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: $\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

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({\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=\varepsilon$ (the Möbius inversion formula)
$(\mu \operatorname {Id} _{k})*\operatorname {Id} _{k}=\varepsilon$ (generalized Möbius inversion)
$\varphi *1=\operatorname {Id}$
$d=1*1$
$\sigma =\operatorname {Id} *1=\varphi *d$
$\sigma _{k}=\operatorname {Id} _{k}*1$
$\operatorname {Id} =\varphi *1=\sigma *\mu$
$\operatorname {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 {Z} ^{+}$ : ${\begin{aligned}(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{aligned}}$

Dirichlet series for some multiplicative functions

$\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}$
$\sum _{n\geq 1}{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}$
$\sum _{n\geq 1}{\frac {d(n)^{2}}{n^{s}}}={\frac {\zeta (s)^{4}}{\zeta (2s)}}$
$\sum _{n\geq 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 $\varphi (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 $\varepsilon$ 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 ${\displaystyle f_{p}(x)=\sum _{n=0}^{\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}$ . In fact, 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 $F q [X]$

Let $A = F q [X]$ , 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 $F q [X]$

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^{\deg(g)}$ if $g\neq 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}\left(\sum _{n\mathop {=} 0}^{\infty }h(P^{n})|P|^{-sn}\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 _{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 _{\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{aligned}(f*g)(m)&=\sum _{d\mid m}f(d)g\left({\frac {m}{d}}\right)\\&=\sum _{ab=m}f(a)g(b),\end{aligned}}

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 $A$ 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}\epsilon _{t}$

For the efficient estimation of $Σ(.)$ , 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)(\epsilon _{t}^{2}-1),$

and $y_{t}^{2}=\sigma ^{2}(t/T)+\sigma ^{2}(t/T)(g_{t}\epsilon _{t}^{2}-1).$

Thus it gives an estimate value of $L_{t}(\tau ;u)=\sum _{t=1}^{T}K_{h}(u-t/T){\begin{bmatrix}ln\tau +{\frac {y_{t}^{2}}{g_{t}\tau }}\end{bmatrix}}$

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 $c\,f(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)=cf_{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$ .

References

See chapter 2 of Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001
P. J. McCarthy, Introduction to Arithmetical Functions, Universitext. New York: Springer-Verlag, 1986.
Hafner, Christian M.; Linton, Oliver (2010). "Efficient estimation of a multivariate multiplicative volatility model" (PDF). Journal of Econometrics. 159 (1): 55–73. doi:10.1016/j.jeconom.2010.04.007. S2CID 54812323.
P. Haukkanen (2003). "Some characterizations of specially multiplicative functions". Int. J. Math. Math. Sci. 37: 2335–2344.
P. Haukkanen (2012). "Extensions of the class of multiplicative functions". East–West Journal of Mathematics. 14 (2): 101–113.
DB Lahiri (1972). "Hypo-multiplicative number-theoretic functions". Aequationes Mathematicae. 8 (3): 316–317.

D. Rearick (1966). "Semi-multiplicative functions". Duke Math. J. 33: 49–53.

L. Tóth (2013). "Two generalizations of the Busche-Ramanujan identities". International Journal of Number Theory. 9: 1301–1311.
R. Vaidyanathaswamy (1931). "The theory of multiplicative arithmetic functions". Transactions of the American Mathematical Society. 33 (2): 579–662. doi:10.1090/S0002-9947-1931-1501607-1.
S. Ramanujan, Some formulae in the analytic theory of numbers. Messenger 45 (1915), 81--84.

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.