Definitions

Arithmetic_function

Arithmetic function

In number theory an arithmetic function or arithmetical function is a function defined on the set of natural numbers (i.e. positive integers) that takes real or complex values. A simple example of an arithmetic function is the characteristic function of even positive integers, which takes the value 0 at the odd integers 1,3,5,7... and the value 1 at the even integers 2,4,6,8...

To emphasise that they are functions, values of an arithmetic function are usually denoted by a(n) rather than an. A large part of number theory consists of the study of these functions.

Multiplicative and additive functions

Let (m,n) denote the greatest common divisor of m and n. An arithmetic function a is said to be

  • multiplicative if a(mn) = a(m)a(n) for all natual numbers m and n such that (m,n) = 1;
  • completely multiplicative if a(mn) = a(m)a(n) for all natural numbers m and n;
  • additive if a(mn) = a(m)+a(n) for all natual numbers m and n such that (m,n) = 1;
  • completely additive if a(mn) = a(m)+a(n) for all natural numbers m and n.

Examples

  • π(n), the prime counting function - the number of primes less than or equal to n. This arithmetic function is neither multiplicative nor additive, e.g. π(7) = 4 and π(11) = 5, but π(7×11) = π(77) = 21 ≠ 4×5.
  • τ(n), the number of positive divisors of n, including 1 and n. This arithmetic function is multiplicative.
  • ω(n), the number of distinct primes dividing the number n. This arithmetic function is additive.
  • Ω(n), the number of prime factors of n, counted with multiplicities. This arithmetic function is completely additive.
  • λ(n), the Liouville function - defined by λ(n) := (-1)Ω(n). This arithmetic function is completely multiplicative (by the last example).
  • Λ(n), the von Mangoldt function - defined to be ln(p) if n is an integer power of a prime p and 0 for all other n. This arithmetic function is neither multiplicative nor additive, e.g. Λ(2) = ln(2), Λ(3) = ln(3), but Λ(2×3) = 0 ≠ ln(2)×ln(3).
  • P(n), the partition function - the number of unordered representations of n as a sum of positive integers; neither multiplicative nor additive.
  • χ(n) - defined by the following

chi(n) := left{begin{array}{cl} 0 & mbox{if } n mbox{ is even}, 1 & mbox{if } n equiv 1 mod 4, -1 & mbox{if } n equiv 3 mod 4.
end{array}right.
This arithmetic function is completely multiplicative.

mu(n) := left{begin{array}{cl} (-1)^k & mbox{if } n mbox{ is a product of } k mbox{ distinct primes}
0 & mbox{if } p^2|n mbox{ for some prime } p end{array}right.
The definition of the Möbius function presents itself naturally when working with Euler products. This arithmetic function is multiplicative.

Prime power decomposition

Some of the arithmetic functions above can be computed easily using prime power decomposition. Any positive integer n can be factorised uniquely as a product of powers of primes, as follows:

n = p_1^{a_1}ldots p_k^{a_k}
where each pi is prime and each aj ≥ 1. For example 10 = 21.51, 25 = 52, 666 = 21.32.371, etc.

Arithmetic functions can then be defined as follows:

  • τ(n) = (1 + a1)...(1 + ak)
  • ω(n) = k
  • Ω(n) = a1 + ... + ak
  • Λ(n) = ln(p1) if k = 1; otherwise Λ(n) = 0.
  • μ(n) = 0 if ai > 1 for any i; otherwise μ(n) = (-1)k.

An exact expression for π(n) in terms of the k, the pi and the aj is so far not known. The prime number theorem gives an estimate for π(n) as n becomes very large. Certain remainer terms to improve the prime number theorem have been postulated, and these are linked to the Reimann hypothesis.

Summation functions

Given an arithmetic function a(n), its summation function A(x) is defined by

A(x) := sum_{n le x} a(n) .
A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.

Given any set E of the natural numbers (for example, the set of prime numbers), define

u_E(n) := left{ begin{array}{ll} 1 & mbox{if} n in E
0 & mbox{if} n notin E end{array}right. Let P be the set of positive prime numbers then π(x) is the summation function of uP(n).

Individual values of arithmetic functions may fluctuate wildly - as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find asymptotic behaviour for the summation function for large x. The prime number theorem gives asymptotic behaviour for π(x) (the summation function of uP(n)) for large x.

Convolution

Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):

F_a(s) := sum_{n=1}^{infty} frac{a(n)}{n^s} .
Fa(s) is called a generating function of a(n). One key example is given by a(n) = 1 for all n. In this case Fa(s) = ς(s), the Riemann zeta function.

Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows:

F_a(s)F_b(s) = left(sum_{m=1}^{infty}frac{a(m)}{m^s} right)left(sum_{n=1}^{infty}frac{b(n)}{n^s} right) .
After some simplification this gives Fa(s)Fb(s) = Fc(s) where c is some arithmetic function given by
c(n) := sum_{ij = n} a(i)b(j) = sum_{i|n}a(i)bleft(frac{n}{i}right) ,
where the notation i|n means that i divides n. The function c defined in this way is called the Dirichlet convolution of a and b, and is denoted by a*b. This binary operation on the space of arithmetic functions has some interesting properties. See the article on Dirichlet convolutions for more details.

References

Search another word or see Arithmetic_functionon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature