HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
, a multiplicative function is an arithmetic function ''f''(''n'') of a positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
''n'' with the property that ''f''(1) = 1 and f(ab) = f(a)f(b) whenever ''a'' and ''b'' are
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
. An arithmetic function ''f''(''n'') is said to be completely multiplicative (or totally multiplicative) if ''f''(1) = 1 and ''f''(''ab'') = ''f''(''a'')''f''(''b'') holds ''for all'' positive integers ''a'' and ''b'', even when they are not coprime.


Examples

Some multiplicative functions are defined to make formulas easier to write: * 1(''n''): the constant function, defined by 1(''n'') = 1 (completely multiplicative) * Id(''n''):
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
, defined by Id(''n'') = ''n'' (completely multiplicative) * 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 ** Id0(''n'') = 1(''n'') and ** Id1(''n'') = Id(''n''). * ''ε''(''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 In number theory, the unit function is a completely multiplicative function on the positive integers defined as: :\varepsilon(n) = \begin 1, & \mboxn=1 \\ 0, & \mboxn \neq 1 \end It is called the unit function because it is the identity element f ...
'' (completely multiplicative). Sometimes written as ''u''(''n''), but not to be confused with ''μ''(''n'') . * 1''C''(''n''), the
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
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. Other examples of multiplicative functions include many functions of importance in number theory, such as: * gcd(''n'',''k''): the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of ''n'' and ''k'', as a function of ''n'', where ''k'' is a fixed integer. * \varphi(n):
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ...
\varphi, counting the positive integers
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to (but not bigger than) ''n'' * ''μ''(''n''): the
Möbius function The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
, the parity (−1 for odd, +1 for even) of the number of prime factors of square-free numbers; 0 if ''n'' is not square-free * ''σ''''k''(''n''): the
divisor function In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (includin ...
, which is the sum of the ''k''-th powers of all the positive divisors of ''n'' (where ''k'' may be any
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
). Special cases we have ** ''σ''0(''n'') = ''d''(''n'') the number of positive
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of ''n'', ** ''σ''1(''n'') = ''σ''(''n''), the sum of all the positive divisors of ''n''. * ''a''(''n''): the number of non-isomorphic abelian groups of order ''n''. * ''λ''(''n''): the Liouville function, ''λ''(''n'') = (−1)Ω(''n'') where Ω(''n'') is the total number of primes (counted with multiplicity) dividing ''n''. (completely multiplicative). * ''γ''(''n''), defined by ''γ''(''n'') = (−1)''ω''(n), where the additive function ''ω''(''n'') is the number of distinct primes dividing ''n''. * ''τ''(''n''): the Ramanujan tau function. * All
Dirichlet character In analytic number theory and related branches of mathematics, a complex-valued arithmetic function \chi:\mathbb\rightarrow\mathbb is a Dirichlet character of modulus m (where m is a positive integer) if for all integers a and b: :1)   \ch ...
s are completely multiplicative functions. For example ** (''n''/''p''), the
Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...
, considered as a function of ''n'' where ''p'' is a fixed
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
. An example of a non-multiplicative function is the arithmetic function ''r''2(''n'') - the number of representations of ''n'' as a sum of squares of two integers, positive, negative, or
zero 0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by Multiplication, multiplying digits to the left of 0 by th ...
, where in counting the number of ways, reversal of order is allowed. For example: and therefore ''r''2(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, ''r''2(''n'')/4 is multiplicative. In the
On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...

sequences of values of a multiplicative function
have the keyword "mult". 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 A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, a consequence of the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
. 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 = 24 · 32: Similarly, we have: \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 In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
of
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
s 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 f * g, the '' Dirichlet convolution'' of ''f'' and ''g'', by (f \, * \, g)(n) = \sum_ f(d) \, g \left( \frac \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 In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
; the
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
is ''ε''. Convolution is commutative, associative, and distributive over addition. Relations among the multiplicative functions discussed above include: * \mu * 1 = \varepsilon (the Möbius inversion formula) * (\mu \operatorname_k) * \operatorname_k = \varepsilon (generalized Möbius inversion) * \varphi * 1 = \operatorname * d = 1 * 1 * \sigma = \operatorname * 1 = \varphi * d * \sigma_k = \operatorname_k * 1 * \operatorname = \varphi * 1 = \sigma * \mu * \operatorname_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 a,b \in \mathbb^: \begin (f \ast g)(ab) & = \sum_ f(d) g\left(\frac\right) \\ &= \sum_ \sum_ f(d_1d_2) g\left(\frac\right) \\ &= \sum_ f(d_1) g\left(\frac\right) \times \sum_ f(d_2) g\left(\frac\right) \\ &= (f \ast g)(a) \cdot (f \ast g)(b). \end


Dirichlet series for some multiplicative functions

* \sum_ \frac = \frac * \sum_ \frac = \frac * \sum_ \frac = \frac * \sum_ \frac = \frac More examples are shown in the article on
Dirichlet series In mathematics, a Dirichlet series is any series of the form \sum_^\infty \frac, where ''s'' is complex, and a_n is a complex sequence. It is a special case of general Dirichlet series. Dirichlet series play a variety of important roles in analy ...
.


Multiplicative function over

Let , the polynomial ring over the
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with ''q'' elements. ''A'' is a
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principa ...
and therefore ''A'' is a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
. A complex-valued function \lambda on ''A'' is called multiplicative if \lambda(fg)=\lambda(f)\lambda(g) whenever ''f'' and ''g'' are relatively prime.


Zeta function and Dirichlet series in

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 : D_h(s)=\sum_h(f), f, ^, where for g\in A, set , g, =q^ if g\ne 0, and , g, =0 otherwise. The polynomial zeta function is then : \zeta_A(s)=\sum_, f, ^. Similar to the situation in , every Dirichlet series of a multiplicative function ''h'' has a product representation (
Euler product In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for the sum of all positive integers raised to a certain power as proven by Leonhard Eu ...
): : D_(s)=\prod_P \left(\sum_^h(P^), P, ^\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: : \zeta_A(s)=\prod_(1-, P, ^)^. Unlike the classical
zeta function In mathematics, a zeta function is (usually) a function analogous to the original example, the Riemann zeta function : \zeta(s) = \sum_^\infty \frac 1 . Zeta functions include: * Airy zeta function, related to the zeros of the Airy function * ...
, \zeta_A(s) is a simple rational function: : \zeta_A(s)=\sum_f , f, ^ = \sum_n\sum_q^=\sum_n(q^)=(1-q^)^. 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 : \begin (f*g)(m) &= \sum_ f(d)g\left(\frac\right) \\ &= \sum_f(a)g(b), \end where the sum is over all monic
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s ''d'' of ''m'', or equivalently over all pairs (''a'', ''b'') of monic polynomials whose product is ''m''. The identity D_h D_g = D_ still holds.


See also

*
Euler product In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for the sum of all positive integers raised to a certain power as proven by Leonhard Eu ...
* Bell series * Lambert series


References

* See chapter 2 of


External links

* {{PlanetMath , urlname=multiplicativefunction , title=Multiplicative function