Multiplicative function

Template:Short description {{#invoke:Hatnote|hatnote}}

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 (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

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

• <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 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 divisors 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 divisors 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 characters 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, negative, or zero, where in counting the number of ways, reversal of order is allowed. For example:

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>{{#invoke:citation/CS1|citation |CitationClass=web }}</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 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²: <math display="block">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</math> <math display="block">\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</math> <math display="block">\sigma^*(144) = \sigma^*(2^4) \, \sigma^*(3^2) = (1^1 + 16^1)(1^1 + 9^1) = 17 \cdot 10 = 170</math>

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 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 <math>f * g</math>, the Dirichlet convolution of f and g, by <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 ε. Convolution is commutative, associative, and distributive over addition.

Relations among the multiplicative functions discussed above include:

• <math>\mu * 1 = \varepsilon</math> (the Möbius inversion formula)
• <math>(\mu \operatorname{Id}_k) * \operatorname{Id}_k = \varepsilon</math> (generalized Möbius inversion)
• <math>\varphi * 1 = \operatorname{Id}</math>
• <math>d = 1 * 1</math>
• <math>\sigma = \operatorname{Id} * 1 = \varphi * d</math>
• <math>\sigma_k = \operatorname{Id}_k * 1</math>
• <math>\operatorname{Id} = \varphi * 1 = \sigma * \mu</math>
• <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₁,...,g_r, h₁,...,h_s 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 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 <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 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

<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 Template:Math, 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 divisors 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 functions can be constructed using multiplicative model estimators. Where a matrix function of Template:Math is defined as <math display="block">D_N = N^2 \times N(N + 1) / 2</math>

a sum can be 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 Template:Math, the following two nonparametric regressions 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
• Lambert series

References

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

• Template:Cite journal

• Template:Cite journal
• Template:Cite journal
• 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

• Template:PlanetMath