Multiplicative function

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

Id₀(n) = 1(n) and

Id₁(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 (completely multiplicative). Sometimes written as u(n), but not to be confused with μ(n) .

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.

Other examples of multiplicative functions include many functions of importance in number theory, such as:

gcd(n,k): the greatest common divisor of n and k, as a function of n, where k is a fixed integer.

φ (n): Euler's totient function φ , counting the positive integers coprime to (but not bigger than) n

μ(n): the Möbius function, 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, 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

σ₀(n) = d(n) the number of positive divisors of n,

σ₁(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 characters 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₂(n) - the number of representations of n 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:

1 = 1² + 0² = (−1)² + 0² = 0² + 1² = 0² + (−1)²

and therefore r₂(1) = 4 ≠ 1. This shows that the function is not multiplicative. However, r₂(n)/4 is multiplicative.

In the On-Line Encyclopedia of Integer Sequences, 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 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²:

d(144) = σ₀(144) = σ₀(2⁴)σ₀(3²) = (1⁰ + 2⁰ + 4⁰ + 8⁰ + 16⁰)(1⁰ + 3⁰ + 9⁰) = 5 · 3 = 15, σ(144) = σ₁(144) = σ₁(2⁴)σ₁(3²) = (1¹ + 2¹ + 4¹ + 8¹ + 16¹)(1¹ + 3¹ + 9¹) = 31 · 13 = 403, σ^*(144) = σ^*(2⁴)σ^*(3²) = (1¹ + 16¹)(1¹ + 9¹) = 17 · 10 = 170.

Similarly, we have:

φ (144)= φ (2⁴) φ (3²) = 8 · 6 = 48

In general, if f(n) is a multiplicative function and a, b are any two positive integers, then

f(a) · f(b) = f(gcd(a,b)) · f(lcm(a,b)).

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 f * g, the Dirichlet convolution of f and g, by

( f ∗ g ) ( n ) = ∑ d | n f ( d ) g ( n d )

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:

μ * 1 = ε (the Möbius inversion formula)

(μ Id_k) * Id_k = ε (generalized Möbius inversion)

φ * 1 = Id

d = 1 * 1

σ = Id * 1 = φ * d

σ_k = Id_k * 1

Id = φ * 1 = σ * μ

Id_k = σ_k * μ

The Dirichlet convolution can be defined for general arithmetic functions, and yields a ring structure, the Dirichlet ring.

Dirichlet series for some multiplicative functions

∑ n ≥ 1 μ ( n ) n s = 1 ζ ( s )

∑ n ≥ 1 φ ( n ) n s = ζ ( s − 1 ) ζ ( s )

∑ n ≥ 1 d ( n ) 2 n s = ζ ( s ) 4 ζ ( 2 s )

∑ n ≥ 1 2 ω ( n ) n s = ζ ( s ) 2 ζ ( 2 s )

More examples are shown in the article on Dirichlet series.

Multiplicative function over Fq[X]

Let A=F_q[X], the polynomial ring over the finite field with q elements. A is principal ideal domain and therefore A is unique factorization domain.

a complex-valued function λ on A is called multiplicative if λ ( f g ) = λ ( f ) λ ( g ) , whenever f and g are relatively prime.

Zeta function and Dirichlet series in Fq[X]

Let h be a polynomial arithmetic function (i.e. a function on set of monic polynomials over A). Its corresponding Dirichlet series define to be

D h ( s ) = ∑ f  monic h ( f ) | f | − s ,

where for g ∈ A , set | g | = q deg ⁡ ( g ) if g ≠ 0 , and | g | = 0 otherwise.

The polynomial zeta function is then

ζ A ( s ) = ∑ f  monic | f | − s .

Similar to the situation in N, every Dirichlet series of a multiplicative function h has a product representation (Euler product):

D h ( s ) = ∏ P ( ∑ n = 0 ∞ h ( P n ) | P | − s n ) ,

Where the product runs over all monic irreducible polynomials P.

For example, the product representation of the zeta function is as for the integers: ζ A ( s ) = ∏ P ( 1 − | P | − s ) − 1 .

Unlike the classical zeta function, ζ A ( s ) is a simple rational function:

ζ A ( s ) = ∑ f ( | f | − s ) = ∑ n ∑ deg(f)=n q − s n = ∑ n ( q n − s n ) = ( 1 − q 1 − s ) − 1 .

In a similar way, If ƒ and g are two polynomial arithmetic functions, one defines ƒ * g, the Dirichlet convolution of ƒ and g, by

( f ∗ g ) ( m ) = ∑ d ∣ m f ( d ) g ( m d ) = ∑ a b = m f ( a ) g ( b )

where the sum extends over all monic divisors d of m, or equivalently over all pairs (a, b) of monic polynomials whose product is m. The identity D h D g = D h ∗ g still holds.