Content deleted Content added
m Link directly to square-free integer, instead of square-free disambig page |
Aliu Salau (talk | contribs) Link suggestions feature: 3 links added. Tags: Visual edit Mobile edit Mobile web edit Newcomer task Suggested: add links |
||
| (168 intermediate revisions by 88 users not shown) | |||
Line 1:
{{short description|Function equal to the product of its values on coprime factors}}
{{hatnote|Outside number theory, the term '''multiplicative function''' is usually used for [[completely multiplicative function]]s. This article discusses number theoretic multiplicative functions.}}
In [[number theory]], a '''multiplicative function''' is an [[arithmetic function]] <math>f</math> of a positive [[integer]] <math>n</math> with the property that <math>f(1)=1</math> and
<math display="block">f(ab) = f(a)f(b)</math> whenever <math>a</math> and <math>b</math> are [[coprime]].
An arithmetic function is said to be '''[[completely multiplicative function|completely multiplicative]]''' (or '''totally multiplicative''') if <math>f(1)=1</math> and <math>f(ab) = f(a)f(b)</math> holds ''for all'' positive integers <math>a</math> and <math>b</math>, even when they are not coprime.
== Examples ==
* <math>1(n)</math>: the constant function defined by <math>1(n)=1</math>
* <math>\operatorname{Id}(n)</math>: the [[identity function]], defined by <math>\operatorname{Id}(n)=n</math>
* <math>\operatorname{Id}_k(n)</math>: the power functions, defined by <math>\operatorname{Id}_k(n)=n^k</math> for any complex number <math>k</math>. As special cases we have
** <math>\operatorname{Id}_0(n)=1(n)</math>, and
** <math>\operatorname{Id}_1(n)=\operatorname{Id}(n)</math>.
* <math>\varepsilon(n)</math>: the function defined by <math>\varepsilon(n)=1</math> if <math>n=1</math> and <math>0</math> otherwise; this is the [[unit function]], so called because it is the multiplicative identity for [[Dirichlet convolution]]. Sometimes written as <math>u(n)</math>; not to be confused with <math>\mu(n)</math>.
* <math>\lambda(n)</math>: the [[Liouville function]], <math>\lambda(n)=(-1)^{\Omega(n)}</math>, where <math>\Omega(n)</math> is the total number of primes (counted with multiplicity) dividing <math>n</math>
The above functions are all completely multiplicative.
* <math>1_C(n)</math>: the [[indicator function]] of the set <math>C\subseteq \Z</math>. This function is multiplicative precisely when <math>C</math> 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:
* <math>\gcd(n,k)</math>: the [[greatest common divisor]] of <math>n</math> and <math>k</math>, as a function of <math>n</math>, where <math>k</math> is a fixed integer
* <math>\varphi(n)</math>: [[Euler's totient function]], which counts the positive integers [[coprime]] to (but not bigger than) <math>n</math>
* <math>\mu(n)</math>: the [[Möbius function]], the parity (<math>-1</math> for odd, <math>+1</math> for even) of the number of prime factors of [[square-free integer|square-free]] numbers; <math>0</math> if <math>n</math> is not square-free
* <math>\sigma_k(n)</math>: the [[divisor function]], which is the sum of the <math>k</math>-th powers of all the positive divisors of <math>n</math> (where <math>k</math> may be any [[complex number]]). As special cases we have
** <math>\sigma_0(n)=d(n)</math>, the number of positive [[divisor]]s of <math>n</math>,
** <math>\sigma_1(n)=\sigma(n)</math>, the sum of all the positive divisors of <math>n</math>.
*<math>\sigma^*_k(n)</math>: the sum of the <math>k</math>-th powers of all [[unitary divisor]]s of <math>n</math>
::<math>\sigma_k^*(n) \,=\!\!\sum_{d \,\mid\, n \atop \gcd(d,\,n/d)=1} \!\!\! d^k</math>
* <math>a(n)</math>: the number of non-isomorphic [[abelian groups]] of order <math>n</math>
* <math>\gamma(n)</math>, defined by <math>\gamma(n) = (-1)^{\omega(n)}</math>, where the [[additive function]] <math>\omega(n)</math> is the number of distinct primes dividing <math>n</math>
* <math>\tau(n)</math>: the [[Ramanujan tau function]]
* All [[Dirichlet character]]s are completely multiplicative functions, for example
** <math>(n/p)</math>, the [[Legendre symbol]], considered as a function of <math>n</math> where <math>p</math> is a fixed [[prime number]]
An example of a non-multiplicative function is the arithmetic function <math>r_2(n)</math>, the number of representations of <math>n</math> as a sum of squares of two integers, [[positive number|positive]], [[negative number|negative]], or [[0 (number)|zero]], where in counting the number of ways, reversal of order is allowed. For example:
{{block indent|em=1.2|text=1 = 1<sup>2</sup> + 0<sup>2</sup> = (−1)<sup>2</sup> + 0<sup>2</sup> = 0<sup>2</sup> + 1<sup>2</sup> = 0<sup>2</sup> + (−1)<sup>2</sup>}}
and therefore <math>r_2(1)=4\neq 1</math>. This shows that the function is not multiplicative. However, <math>r_2(n)/4</math> is multiplicative.
In the [[On-Line Encyclopedia of Integer Sequences]], sequences of values of a multiplicative function have the keyword "mult".<ref>{{cite web | url=http://oeis.org/search?q=keyword:mult | title=Keyword:mult - OEIS }}</ref>
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 number]]s, a consequence of the [[fundamental theorem of arithmetic]]. Thus, if ''n'' is a product of powers of distinct primes, say ''n'' = ''p''<sup>''a''</sup> ''q''<sup>''b''</sup> ..., then
''f''(''n'') = ''f''(''p''<sup>''a''</sup>) ''f''(''q''<sup>''b''</sup>) ...
This property of multiplicative functions significantly reduces the need for computation, as in the following examples for ''n'' = 144 = 2<sup>4</sup> · 3<sup>2</sup>:
Similarly, we have:
<math display="block">\varphi(144) = \varphi(2^4) \, \varphi(3^2) = 8 \cdot 6 = 48</math>
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 [[monoid]]s and is completely determined by its restriction to the prime numbers.
Line 60 ⟶ 78:
== Convolution ==
If ''f'' and ''g'' are two multiplicative functions, one defines a new multiplicative function
<math display="block"> (f \, * \, g)(n) = \sum_{d|n} f(d) \, g \left( \frac{n}{d} \right)</math>
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
Relations among the multiplicative functions discussed above include:
* <math>\
* <math>(\mu \operatorname{Id}_k) * \operatorname{Id}_k = \varepsilon</math> (generalized Möbius inversion)
* <math>\varphi * 1 = \operatorname{Id}</math>
* <math>
* <math>\sigma
*
*
* <math>\operatorname{Id}_k = \sigma_k * \mu</math>
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 <math>a,b \in \mathbb{Z}^{+}</math>:
<math display="block">\begin{align}
(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_1d_2) g\left(\frac{ab}{d_1d_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{align} </math>
=== Dirichlet series for some multiplicative functions ===
* <math>\sum_{n\ge 1} \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}</math>
* <math>\sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}</math>
* <math>\sum_{n\ge 1} \frac{d(n)^2}{n^s} = \frac{\zeta(s)^4}{\zeta(2s)}</math>
* <math>\sum_{n\ge 1} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta(s)^2}{\zeta(2s)}</math>
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 <math>(r, s)</math> if there exists completely multiplicative functions ''g''<sub>''1''</sub>,...,''g''<sub>''r''</sub>,
''h''<sub>''1''</sub>,...,''h''<sub>''s''</sub> such that
<math display="block">
f=g_1\ast\cdots\ast g_r\ast h_1^{-1}\ast\cdots\ast h_s^{-1},
</math>
where the inverses are with respect to the Dirichlet convolution. Rational arithmetical functions of order <math>(1, 1)</math> are known as totient functions, and rational arithmetical functions of order <math>(2,0)</math> are known as quadratic functions or specially multiplicative functions. Euler's function <math>\varphi(n)</math> is a totient function, and the divisor function <math>\sigma_k(n)</math> is a quadratic function.
Completely multiplicative functions are rational arithmetical functions of order <math>(1,0)</math>. Liouville's function <math>\lambda(n)</math> is completely multiplicative. The Möbius function <math>\mu(n)</math> is a rational arithmetical function of order <math>(0, 1)</math>.
By convention, the identity element <math>\varepsilon</math> under the Dirichlet convolution is a rational arithmetical function of order <math>(0, 0)</math>.
All rational arithmetical functions are multiplicative. A multiplicative function ''f'' is a rational arithmetical function of order <math>(r, s)</math> [[if and only if]] its Bell series is of the form
<math display="block">
{\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)}}
</math>
for all prime numbers <math>p</math>.
The concept of a rational arithmetical function originates from R. Vaidyanathaswamy (1931).
== Busche-Ramanujan identities ==
A multiplicative function <math>f</math> is said to be specially multiplicative
if there is a completely multiplicative function <math>f_A</math> such that
:<math>
f(m) f(n) = \sum_{d\mid (m,n)} f(mn/d^2) f_A(d)
</math>
for all positive integers <math>m</math> and <math>n</math>, or equivalently
:<math>
f(mn) = \sum_{d\mid (m,n)} f(m/d) f(n/d) \mu(d) f_A(d)
</math>
for all positive integers <math>m</math> and <math>n</math>, where <math>\mu</math> is the Möbius function.
These are known as Busche-Ramanujan identities.
In 1906, E. Busche stated the identity
:<math>
\sigma_k(m) \sigma_k(n) = \sum_{d\mid (m,n)} \sigma_k(mn/d^2) d^k,
</math>
and, in 1915, S. Ramanujan gave the inverse form
:<math>
\sigma_k(mn) = \sum_{d\mid (m,n)} \sigma_k(m/d) \sigma_k(n/d) \mu(d) d^k
</math>
for <math>k=0</math>. S. Chowla gave the inverse form for general <math>k</math> 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 <math>f=g_1\ast g_2</math> satisfy the Busche-Ramanujan identities with <math>f_A=g_1g_2</math>. Quadratic functions are exactly the same as specially multiplicative functions. Totients satisfy a restricted Busche-Ramanujan identity. For further details, see [[Ramaswamy S. Vaidyanathaswamy|R. Vaidyanathaswamy]] (1931).
==Multiplicative function over {{math|''F''<sub>''q''</sub>[''X'']}}==
Let {{math|1=''A'' = ''F''<sub>''q''</sub>[''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 <math>\lambda</math> on ''A'' is called '''multiplicative''' if <math>\lambda(fg)=\lambda(f)\lambda(g)</math> whenever ''f'' and ''g'' are [[relatively prime]].
===Zeta function and Dirichlet series in {{math|''F''<sub>''q''</sub>[''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
: <math display="block">D_h(s)=\sum_{f\text{ monic}}h(f)|f|^{-s},</math>
where for <math>g\in A,</math> set <math>|g|=q^{\deg(g)}</math> if <math>g\ne 0,</math> and <math>|g|=0</math> otherwise.
The polynomial zeta function is then
: <math display="block">\zeta_A(s)=\sum_{f\text{ monic}}|f|^{-s}.</math>
Similar to the situation in {{math|'''N'''}}, every Dirichlet series of a multiplicative function ''h'' has a product representation ([[Euler product]]):
: <math display="block">D_{h}(s)=\prod_P \left(\sum_{n\mathop =0}^{\infty}h(P^{n})|P|^{-sn}\right),</math>
where the product runs over all monic irreducible polynomials ''P''. For example, the product representation of the zeta function is as for the integers:
: <math display="block">\zeta_A(s)=\prod_{P}(1-|P|^{-s})^{-1}.</math>
Unlike the classical [[zeta function]], <math>\zeta_A(s)</math> is a simple rational function:
: <math display="block">\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}.</math>
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
: <math display="block">
\begin{align}
(f*g)(m)
&= \sum_{d \mid m} f(d)g\left(\frac{m}{d}\right) \\
&= \sum_{ab = m}f(a)g(b),
\end{align}
</math>
where the sum is over all monic [[divisor]]s ''d'' of ''m'', or equivalently over all pairs (''a'', ''b'') of monic polynomials whose product is ''m''. The identity <math>D_h D_g = D_{h*g}</math> still holds.
== Multivariate ==
[[Multivariate function]]s can be constructed using multiplicative model estimators. Where a matrix function of {{math|1=''A''}} is defined as <math display="block">D_N = N^2 \times N(N + 1) / 2</math>
a sum can be [[logarithmic distribution|distributed]] across the product<math display="block">y_t = \sum(t/T)^{1/2}u_t = \sum(t/T)^{1/2}G_t^{1/2}\epsilon_t</math>
For the efficient [[estimation]] of {{math|1=Σ(.)}}, the following two [[nonparametric regression]]s can be considered: <math display="block">\tilde{y}^2_t = \frac{y^2_t}{g_t} = \sigma^2(t/T) + \sigma^2(t/T)(\epsilon^2_t - 1),</math>
and <math display="block">y^2_t = \sigma^2(t/T) + \sigma^2(t/T)(g_t\epsilon^2_t - 1).</math>
Thus it gives an estimate value of <math display="block">L_t(\tau;u) = \sum_{t=1}^T K_h(u - t/T)\begin{bmatrix} ln\tau + \frac{y^2_t}{g_t\tau} \end{bmatrix}</math>
with a local [[likelihood function]] for <math>y^2_t</math> with known <math>g_t</math> and unknown <math>\sigma^2(t/T)</math>.
== Generalizations ==
An arithmetical function <math>f</math> is
quasimultiplicative if there exists a nonzero constant <math>c</math> such that
<math>
c\,f(mn)=f(m)f(n)
</math>
for all positive integers <math>m, n</math> with <math>(m, n)=1</math>. This concept originates by Lahiri (1972).
An arithmetical function <math>f</math> is semimultiplicative
if there exists a nonzero constant <math>c</math>, a positive integer <math>a</math> and
a multiplicative function <math>f_m</math> such that
<math>
f(n)=c f_m(n/a)
</math>
for all positive integers <math>n</math>
(under the convention that <math>f_m(x)=0</math> if <math>x</math> is not a positive integer.) This concept is due to David Rearick (1966).
An arithmetical function <math>f</math> is Selberg multiplicative if
for each prime <math>p</math> there exists a function <math>f_p</math> on nonnegative integers with <math>f_p(0)=1</math> for
all but finitely many primes <math>p</math> such that
<math>
f(n)=\prod_{p} f_p(\nu_p(n))
</math>
for all positive integers <math>n</math>, where <math>\nu_p(n)</math> is the exponent of <math>p</math> in the canonical factorization of <math>n</math>.
See Selberg (1977).
It is known that the classes of semimultiplicative and Selberg multiplicative functions coincide. They both satisfy the arithmetical identity
<math>
f(m)f(n)=f((m, n))f([m, n])
</math>
for all positive integers <math>m, n</math>. See Haukkanen (2012).
It is well known and easy to see that multiplicative functions are quasimultiplicative functions with <math>c=1</math> and quasimultiplicative functions are semimultiplicative functions with <math>a=1</math>.
==See also==
* [[Euler product]]
* [[Bell series]]
Line 83 ⟶ 243:
==References==
* See chapter 2 of {{Apostol IANT}}
* P. J. McCarthy, Introduction to Arithmetical Functions, Universitext. New York: Springer-Verlag, 1986.
* {{cite journal |title=Efficient estimation of a multivariate multiplicative volatility model |journal=Journal of Econometrics |date=2010 |volume=159 |issue=1 |pages=55–73 |doi=10.1016/j.jeconom.2010.04.007 |s2cid=54812323 |url=http://sticerd.lse.ac.uk/dps/em/em541.pdf |last1=Hafner |first1=Christian M. |last2=Linton |first2=Oliver }}
*{{cite journal
|author=P. Haukkanen
|title=Some characterizations of specially multiplicative functions
|journal=Int. J. Math. Math. Sci.
|volume=2003
|pages=2335–2344
|year=2003
|issue=37
|doi=10.1155/S0161171203301139
|doi-access=free
|url=https://www.emis.de/journals/HOA/IJMMS/Volume2003_37/515979.abs.html
}}
*{{cite journal
|author=P. Haukkanen
|title=Extensions of the class of multiplicative functions
|journal=East–West Journal of Mathematics
|volume=14
|issue=2
|pages=101–113
|year=2012
|url=http://eastwestmath.org/index.php/ewm/article/view/100/98
}}
*{{cite journal
|author=DB Lahiri
|title=Hypo-multiplicative number-theoretic functions
|journal=Aequationes Mathematicae
|volume=8
|issue=3
|pages=316–317
|year=1972 |doi=10.1007/BF01844515
}}
*{{cite journal
|author=D. Rearick
|title=Semi-multiplicative functions
|journal=Duke Math. J.
|volume=33
|pages=49–53
|year=1966}}
*{{cite journal
|author=L. Tóth
|title=Two generalizations of the Busche-Ramanujan identities
|journal=International Journal of Number Theory
|volume=9
|pages=1301–1311
|year=2013 |issue=5
|doi=10.1142/S1793042113500280
|arxiv=1301.3331
}}
*{{cite journal
|author=R. Vaidyanathaswamy
|author-link=Ramaswamy S. Vaidyanathaswamy
|title=The theory of multiplicative arithmetic functions
|journal=Transactions of the American Mathematical Society
|volume=33
|issue=2
|pages=579–662
|year=1931
|doi=10.1090/S0002-9947-1931-1501607-1
|doi-access=free }}
*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==
* {{PlanetMath |urlname=multiplicativefunction |title=Multiplicative function}}
==References==
{{Reflist}}
[[Category:Multiplicative functions| ]]
[[Category:Number theory]]
| |||