Multiplicative function: Difference between revisions

Revision as of 12:46, 29 February 2024

Latest revision as of 08:46, 29 July 2025

(31 intermediate revisions by 15 users not shown)

Line 2:

{{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''(''n'')</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 ''f''(''n'') 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 ==

Line 11:

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

* <math>1(''n'')</math>: the constant function, defined by <math>1(''n'') = 1 (completely multiplicative)</math>

* Id(''n''): [[identity function]], defined by Id(''n'') = ''n'' (completely multiplicative)

* <math>\operatorname{Id}(n)</math>: the [[identity function]], defined by <math>\operatorname{Id}(n)=n</math>

* 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

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

** Id₁(''n'') = Id(''n'').

** <math>\operatorname{Id}_0(n)=1(n)</math>, and

* ''ε''(''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'') .

** <math>\operatorname{Id}_1(n)=\operatorname{Id}(n)</math>.

* 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.

* <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]] <math>\varphi</math>, counting the positive integers [[coprime]] to (but not bigger than) ''n''

* <math>\varphi(n)</math>: [[Euler's totient function]], which counts the positive integers [[coprime]] to (but not bigger than) <math>n</math>

* ''μ''(''n''): the [[Möbius function]], the parity (−1 for odd, +1 for even) of the number of prime factors of [[square-free integer|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

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

** ''σ''₀(''n'') = ''d''(''n'') the number of positive [[divisor]]s of ''n'',

** ''σ''₁(''n'') = ''σ''(''n''), the sum of all the positive divisors of ''n''.

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

*The sum of the ''k''-th [[exponentiation|powers]] of the [[Unitary divisor]]s is denoted by σ*_''k''(''n''):

** <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>\sigma_k^*(n) = \sum_{d \,\mid\, n \atop \gcd(d,\,n/d)=1} \!\! d^k.</math>

* <math>\tau(n)</math>: the [[Ramanujan tau function]]

* ''a''(''n''): the number of non-isomorphic abelian groups of order ''n''.

* All [[Dirichlet character]]s are completely multiplicative functions, for example

* ''λ''(''n''): the [[Liouville function]], ''λ''(''n'') = (−1)^Ω(''n'') where Ω(''n'') is the total number of primes (counted with multiplicity) dividing ''n''. (completely multiplicative).

** <math>(n/p)</math>, the [[Legendre symbol]], considered as a function of <math>n</math> where <math>p</math> is a fixed [[prime number]]

* ''γ''(''n''), defined by ''γ''(''n'') = (&minus;1)^''ω''(n), where the [[additive function]] ''ω''(''n'') is the number of distinct primes dividing ''n''.

* ''τ''(''n''): the [[Ramanujan tau function]].

* All [[Dirichlet character]]s 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''<sub>2</submath>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² + 0² = (−1)² + 0² = 0² + 1² = 0² + (−1)²}}

and therefore ''r''<sub>2</submath>r_2(1) = 4 ≠\neq 1</math>. This shows that the function is not multiplicative. However, ''r''<sub>2</submath>r_2(''n'')/4</math> is multiplicative.

In the [[On-Line Encyclopedia of Integer Sequences]], [http://oeis.org/search?q=keyword:mult 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.

Line 52 ⟶ 64:

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:

Line 107 ⟶ 119:

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}=

Line 120 ⟶ 132:

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''_''q''[''X'']}}==

Let {{math|1=''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 <math>\lambda</math> on ''A'' is called '''multiplicative''' if <math>\lambda(fg)=\lambda(f)\lambda(g)</math> whenever ''f'' and ''g'' are [[relatively prime]].

Line 163 ⟶ 200:

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

Line 172 ⟶ 244:

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

*{{cite journal |author=R. 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 }}

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