Multiplicative function: Difference between revisions

Revision as of 04:18, 26 October 2024

Latest revision as of 08:46, 29 July 2025

(17 intermediate revisions by 11 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

* Id<submath>''k''\operatorname{Id}_k(n)</submath>(''n''): the power functions, defined by Id<sub>''k''</submath>\operatorname{Id}_k(''n'') = ''n''<sup>''^k''</supmath> for any complex number ''<math>k'' (completely multiplicative)</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-1)<sup>Ω^{\Omega(''n'')}</supmath>, where Ω<math>\Omega(''n'')</math> is the total number of primes (counted with multiplicity) dividing ''<math>n''. (completely multiplicative).</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>, countingwhich 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 (−1<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''.

* ''σ''<submath>''k''\sigma_k(n)</submath>(''n''): 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]]). SpecialAs special cases we have

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

** ''σ''<sub>0</submath>\sigma_0(''n'') = ''d''(''n'')</math>, the number of positive [[divisor]]s of ''<math>n''</math>,

** ''σ''<sub>1</submath>\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'') = (&minus;-1)<sup>''ω''^{\omega(n)}</supmath>, 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., Forfor 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 134 ⟶ 146:

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,

Line 144 ⟶ 156:

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>. In fact, quadraticQuadratic 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 188 ⟶ 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)

Line 208 ⟶ 220:

(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

Line 236 ⟶ 248:

*{{cite journal

|author=P. Haukkanen

|title=Some characterizations of specially multiplicative functions

|journal=Int. J. Math. Math. Sci.

|volume=372003

|pages=2335-23442335–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

}}

Line 259 ⟶ 274:

|volume=8

|issue=3

|pages=316-317316–317

|year=1972 |doi=10.1007/BF01844515 }}

}}

*{{cite journal

Line 267 ⟶ 283:

|journal=Duke Math. J.

|volume=33

|pages=49-5349–53

|year=1966 }}

*{{cite journal

Line 275 ⟶ 291:

|journal=International Journal of Number Theory

|volume=9

|pages=1301-13111301–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-662579–662

|year=1931

|doi=10.1090/S0002-9947-1931-1501607-1

Line 295 ⟶ 315:

==External links==

* {{PlanetMath |urlname=multiplicativefunction |title=Multiplicative function}}

==References==

{{Reflist}}

[[Category:Multiplicative functions| ]]