Multiplicative function
In number theory, a multiplicative function is an arithmetic function {\displaystyle f} of a positive integer {\displaystyle n} with the property that {\displaystyle f(1)=1} and {\displaystyle f(ab)=f(a)f(b)} whenever {\displaystyle a} and {\displaystyle b} are coprime.
An arithmetic function is said to be completely multiplicative (or totally multiplicative) if {\displaystyle f(1)=1} and {\displaystyle f(ab)=f(a)f(b)} holds for all positive integers {\displaystyle a} and {\displaystyle b}, even when they are not coprime.
Examples
[edit ]Some multiplicative functions are defined to make formulas easier to write:
- {\displaystyle 1(n)}: the constant function defined by {\displaystyle 1(n)=1}
- {\displaystyle \operatorname {Id} (n)}: the identity function, defined by {\displaystyle \operatorname {Id} (n)=n}
- {\displaystyle \operatorname {Id} _{k}(n)}: the power functions, defined by {\displaystyle \operatorname {Id} _{k}(n)=n^{k}} for any complex number {\displaystyle k}. As special cases we have
- {\displaystyle \operatorname {Id} _{0}(n)=1(n)}, and
- {\displaystyle \operatorname {Id} _{1}(n)=\operatorname {Id} (n)}.
- {\displaystyle \varepsilon (n)}: the function defined by {\displaystyle \varepsilon (n)=1} if {\displaystyle n=1} and {\displaystyle 0} otherwise; this is the unit function, so called because it is the multiplicative identity for Dirichlet convolution. Sometimes written as {\displaystyle u(n)}; not to be confused with {\displaystyle \mu (n)}.
- {\displaystyle \lambda (n)}: the Liouville function, {\displaystyle \lambda (n)=(-1)^{\Omega (n)}}, where {\displaystyle \Omega (n)} is the total number of primes (counted with multiplicity) dividing {\displaystyle n}
The above functions are all completely multiplicative.
- {\displaystyle 1_{C}(n)}: the indicator function of the set {\displaystyle C\subseteq \mathbb {Z} }. This function is multiplicative precisely when {\displaystyle 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:
- {\displaystyle \gcd(n,k)}: the greatest common divisor of {\displaystyle n} and {\displaystyle k}, as a function of {\displaystyle n}, where {\displaystyle k} is a fixed integer
- {\displaystyle \varphi (n)}: Euler's totient function, which counts the positive integers coprime to (but not bigger than) {\displaystyle n}
- {\displaystyle \mu (n)}: the Möbius function, the parity ({\displaystyle -1} for odd, {\displaystyle +1} for even) of the number of prime factors of square-free numbers; {\displaystyle 0} if {\displaystyle n} is not square-free
- {\displaystyle \sigma _{k}(n)}: the divisor function, which is the sum of the {\displaystyle k}-th powers of all the positive divisors of {\displaystyle n} (where {\displaystyle k} may be any complex number). As special cases we have
- {\displaystyle \sigma _{0}(n)=d(n)}, the number of positive divisors of {\displaystyle n},
- {\displaystyle \sigma _{1}(n)=\sigma (n)}, the sum of all the positive divisors of {\displaystyle n}.
- {\displaystyle \sigma _{k}^{*}(n)}: the sum of the {\displaystyle k}-th powers of all unitary divisors of {\displaystyle n}
- {\displaystyle \sigma _{k}^{*}(n),円=\!\!\sum _{d,円\mid ,円n \atop \gcd(d,,円n/d)=1}\!\!\!d^{k}}
- {\displaystyle \operatorname {rad} (n)}: the radical of {\displaystyle n}, which is the product of the distinct prime factors of {\displaystyle n}.
- {\displaystyle a(n)}: the number of non-isomorphic abelian groups of order {\displaystyle n}
- {\displaystyle \gamma (n)}, defined by {\displaystyle \gamma (n)=(-1)^{\omega (n)}}, where the additive function {\displaystyle \omega (n)} is the number of distinct primes dividing {\displaystyle n}
- {\displaystyle \tau (n)}: the Ramanujan tau function
- All Dirichlet characters are completely multiplicative functions, for example
- {\displaystyle (n/p)}, the Legendre symbol, considered as a function of {\displaystyle n} where {\displaystyle p} is a fixed prime number
An example of a non-multiplicative function is the arithmetic function {\displaystyle r_{2}(n)}, the number of representations of {\displaystyle 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 {\displaystyle r_{2}(1)=4\neq 1}. This shows that the function is not multiplicative. However, {\displaystyle 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".[1]
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: {\displaystyle 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} {\displaystyle \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} {\displaystyle \sigma ^{*}(144)=\sigma ^{*}(2^{4}),円\sigma ^{*}(3^{2})=(1^{1}+16^{1})(1^{1}+9^{1})=17\cdot 10=170}
Similarly, we have: {\displaystyle \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
[edit ]If f and g are two multiplicative functions, one defines a new multiplicative function {\displaystyle f*g}, the Dirichlet convolution of f and g, by {\displaystyle (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:
- {\displaystyle \mu *1=\varepsilon } (the Möbius inversion formula)
- {\displaystyle (\mu \operatorname {Id} _{k})*\operatorname {Id} _{k}=\varepsilon } (generalized Möbius inversion)
- {\displaystyle \varphi *1=\operatorname {Id} }
- {\displaystyle d=1*1}
- {\displaystyle \sigma =\operatorname {Id} *1=\varphi *d}
- {\displaystyle \sigma _{k}=\operatorname {Id} _{k}*1}
- {\displaystyle \operatorname {Id} =\varphi *1=\sigma *\mu }
- {\displaystyle \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 {\displaystyle a,b\in \mathbb {Z} ^{+}}: {\displaystyle {\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
[edit ]- {\displaystyle \sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}}
- {\displaystyle \sum _{n\geq 1}{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}
- {\displaystyle \sum _{n\geq 1}{\frac {d(n)^{2}}{n^{s}}}={\frac {\zeta (s)^{4}}{\zeta (2s)}}}
- {\displaystyle \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
[edit ]An arithmetical function f is said to be a rational arithmetical function of order {\displaystyle (r,s)} if there exists completely multiplicative functions g1,...,gr, h1,...,hs such that {\displaystyle 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 {\displaystyle (1,1)} are known as totient functions, and rational arithmetical functions of order {\displaystyle (2,0)} are known as quadratic functions or specially multiplicative functions. Euler's function {\displaystyle \varphi (n)} is a totient function, and the divisor function {\displaystyle \sigma _{k}(n)} is a quadratic function. Completely multiplicative functions are rational arithmetical functions of order {\displaystyle (1,0)}. Liouville's function {\displaystyle \lambda (n)} is completely multiplicative. The Möbius function {\displaystyle \mu (n)} is a rational arithmetical function of order {\displaystyle (0,1)}. By convention, the identity element {\displaystyle \varepsilon } under the Dirichlet convolution is a rational arithmetical function of order {\displaystyle (0,0)}.
All rational arithmetical functions are multiplicative. A multiplicative function f is a rational arithmetical function of order {\displaystyle (r,s)} if and only if its Bell series is of the form {\displaystyle {\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 {\displaystyle p}.
The concept of a rational arithmetical function originates from R. Vaidyanathaswamy (1931).
Busche-Ramanujan identities
[edit ]A multiplicative function {\displaystyle f} is said to be specially multiplicative if there is a completely multiplicative function {\displaystyle f_{A}} such that
- {\displaystyle f(m)f(n)=\sum _{d\mid (m,n)}f(mn/d^{2})f_{A}(d)}
for all positive integers {\displaystyle m} and {\displaystyle n}, or equivalently
- {\displaystyle f(mn)=\sum _{d\mid (m,n)}f(m/d)f(n/d)\mu (d)f_{A}(d)}
for all positive integers {\displaystyle m} and {\displaystyle n}, where {\displaystyle \mu } is the Möbius function. These are known as Busche-Ramanujan identities. In 1906, E. Busche stated the identity
- {\displaystyle \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
- {\displaystyle \sigma _{k}(mn)=\sum _{d\mid (m,n)}\sigma _{k}(m/d)\sigma _{k}(n/d)\mu (d)d^{k}}
for {\displaystyle k=0}. S. Chowla gave the inverse form for general {\displaystyle 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 {\displaystyle f=g_{1}\ast g_{2}} satisfy the Busche-Ramanujan identities with {\displaystyle 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 Fq[X]
[edit ]Let A = Fq[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 {\displaystyle \lambda } on A is called multiplicative if {\displaystyle \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 is defined to be
- {\displaystyle D_{h}(s)=\sum _{f{\text{ monic}}}h(f)|f|^{-s},}
where for {\displaystyle g\in A,} set {\displaystyle |g|=q^{\deg(g)}} if {\displaystyle g\neq 0,} and {\displaystyle |g|=0} otherwise.
The polynomial zeta function is then
- {\displaystyle \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):
- {\displaystyle 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:
- {\displaystyle \zeta _{A}(s)=\prod _{P}(1-|P|^{-s})^{-1}.}
Unlike the classical zeta function, {\displaystyle \zeta _{A}(s)} is a simple rational function:
- {\displaystyle \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
- {\displaystyle {\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 {\displaystyle D_{h}D_{g}=D_{h*g}} still holds.
Multivariate
[edit ]Multivariate functions can be constructed using multiplicative model estimators. Where a matrix function of A is defined as {\displaystyle D_{N}=N^{2}\times N(N+1)/2}
a sum can be distributed across the product{\displaystyle 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: {\displaystyle {\tilde {y}}_{t}^{2}={\frac {y_{t}^{2}}{g_{t}}}=\sigma ^{2}(t/T)+\sigma ^{2}(t/T)(\epsilon _{t}^{2}-1),}
and {\displaystyle y_{t}^{2}=\sigma ^{2}(t/T)+\sigma ^{2}(t/T)(g_{t}\epsilon _{t}^{2}-1).}
Thus it gives an estimate value of {\displaystyle 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 {\displaystyle y_{t}^{2}} with known {\displaystyle g_{t}} and unknown {\displaystyle \sigma ^{2}(t/T)}.
Generalizations
[edit ]An arithmetical function {\displaystyle f} is quasimultiplicative if there exists a nonzero constant {\displaystyle c} such that {\displaystyle c,円f(mn)=f(m)f(n)} for all positive integers {\displaystyle m,n} with {\displaystyle (m,n)=1}. This concept originates by Lahiri (1972).
An arithmetical function {\displaystyle f} is semimultiplicative if there exists a nonzero constant {\displaystyle c}, a positive integer {\displaystyle a} and a multiplicative function {\displaystyle f_{m}} such that {\displaystyle f(n)=cf_{m}(n/a)} for all positive integers {\displaystyle n} (under the convention that {\displaystyle f_{m}(x)=0} if {\displaystyle x} is not a positive integer.) This concept is due to David Rearick (1966).
An arithmetical function {\displaystyle f} is Selberg multiplicative if for each prime {\displaystyle p} there exists a function {\displaystyle f_{p}} on nonnegative integers with {\displaystyle f_{p}(0)=1} for all but finitely many primes {\displaystyle p} such that {\displaystyle f(n)=\prod _{p}f_{p}(\nu _{p}(n))} for all positive integers {\displaystyle n}, where {\displaystyle \nu _{p}(n)} is the exponent of {\displaystyle p} in the canonical factorization of {\displaystyle n}. See Selberg (1977).
It is known that the classes of semimultiplicative and Selberg multiplicative functions coincide. They both satisfy the arithmetical identity {\displaystyle f(m)f(n)=f((m,n))f([m,n])} for all positive integers {\displaystyle m,n}. See Haukkanen (2012).
It is well known and easy to see that multiplicative functions are quasimultiplicative functions with {\displaystyle c=1} and quasimultiplicative functions are semimultiplicative functions with {\displaystyle a=1}.
See also
[edit ]References
[edit ]- 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.201004007. S2CID 54812323.
- P. Haukkanen (2003). "Some characterizations of specially multiplicative functions". Int. J. Math. Math. Sci. 2003 (37): 2335–2344. doi:10.1155/S0161171203301139 .
- 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. doi:10.1007/BF01844515.
- D. Rearick (1966). "Semi-multiplicative functions". Duke Math. J. 33: 49–53. doi:10.1215/S0012-7094-66-03308-4.
- L. Tóth (2013). "Two generalizations of the Busche-Ramanujan identities". International Journal of Number Theory. 9 (5): 1301–1311. arXiv:1301.3331 . doi:10.1142/S1793042113500280.
- 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 .
- Ramanujan, S. (1916). "Some formulae in the analytic theory of numbers" (PDF). Messenger. 45: 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.
- Mathar, Richard J. (2012). "Survey of Dirichlet series of multiplicative arithmetic functions". arXiv:1106.4038 [math.NT].