User:Virginia-American/Sandbox/Arithmetic function

In number theory, an arithmetic function or arithmetical function is a real or complex valued function f(n) defined on the set of natural numbers (i.e. positive integers) that "expresses some arithmetical property of n.".

An example of an arithmetic function is the non-principal character (mod 4) defined by

$\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.$

To emphasise that they are being thought of as functions rather than sequences, values of an arithmetic function are usually denoted by a(n) rather than a_n.

There is a larger class of number-theoretic functions that do not fit the above definition, e.g. the prime-counting functions. This article provides links to functions of both classes.

Notation

$\sum _{p}f(p)\;$   and   $\prod _{p}f(p)\;$   mean that the sum or product is over all prime numbers:

$\sum _{p}f(p)=f(2)+f(3)+f(5)+\dots$     $\prod _{p}f(p)=f(2)f(3)f(5)\cdots$

Similarly,   $\sum _{p^{k}}f(p)\;$   and   $\prod _{p^{k}}f(p)\;$   mean that the sum or product is over all prime powers (with positive exponent, so 1 is not counted):

$\sum _{p^{k}}f(p)=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+\dots$

$\sum _{d|n}f(d)\;$   and   $\prod _{d|n}f(p)\;$   mean that the sum or product is over all positive divisors of n, including 1 and n. E.g., if n = 12,

$\prod _{d|12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).\$

The notations can be combined:   $\sum _{p|n}f(p)\;$   and   $\prod _{p|n}f(p)\;$   mean that the sum or product is over all prime divisors of n. E.g., if n = 18,

$\sum _{p|18}f(p)=f(2)+f(3),\$

and similarly   $\sum _{p^{k}|n}f(p^{k})\;$   and   $\prod _{p^{k}|n}f(p^{k})\;$   mean that the sum or product is over all prime powers dividing n. E.g., if n = 24,

$\prod _{p^{k}|24}f(p^{k})=f(2)f(3)f(4)f(8).\$

Multiplicative and additive functions

An arithmetic function a is

• completely additive if a(mn) = a(m) + a(n) for all natural numbers m and n;

• completely multiplicative if a(mn) = a(m)a(n) for all natural numbers m and n;

Two whole numbers m and n are called coprime if their greatest common divisor is 1; i.e., if there is no prime number that divides both of them.

Then an arithmetic function a is

• additive if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;

• multiplicative if a(mn) = a(m)a(n) for all coprime natural numbers m and n.

Ω(n), ω(n), ν_p(n) - prime power decomposition

The fundamental theorem of arithmetic states that any positive integer n can be factorised uniquely as a product of powers of primes:   $n=p_{1}^{a_{1}}\ldots p_{k}^{a_{k}}$   where p₁ < p₂ < ... < p_k are primes and the a_j are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define ν_p(n) as the exponent of the highest power of the prime p that divides n. I.e. if p is one of the p_i then ν_p(n) = a_i, otherwise it is zero. Then

$n=\prod _{p}p^{\nu _{p}(n)}.$

In terms of the above the functions ω and Ω are defined by

ω(n) = k,

Ω(n) = a₁ + a₂ + ... + a_k.

To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding p_i, a_i, ω, and Ω.

Multiplicative functions

σ_k(n), τ(n), d(n) - divisor sums

σ_k(n) is the sum of the k^th powers of of the positive divisors of n, including 1 and n, where k is a complex mumber.

σ₁(n), the sum of the (positive) divisors of n, is usually denoted by σ(n). Since a positive number to the zero power is one,

σ₀(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = dvisors).

$\sigma _{k}(n)=\prod _{i=1}^{\omega (n)}{\frac {p_{i}^{(a_{i}+1)k}-1}{p_{i}^{k}-1}}=\prod _{i=1}^{\omega (n)}(1+p_{i}^{k}+p_{i}^{2k}+...+p_{i}^{a_{i}k}).$

Setting k = 0 gives

$\tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).$

φ(n) - Euler totient function

φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

$\phi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).$

μ(n) - Möbius function

μ(n), the Möbius function, is important because of the Möbius inversion formula.

$\mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\mbox{if }}\;\omega (n)=\Omega (n)\\0&{\mbox{if }}\;\omega (n)\neq \Omega (n)\end{cases}}.$

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

Completely multiplicative functions

λ(n) - Liouville function

λ(n), the Liouville function, is defined by

$\lambda (n)=(-1)^{\Omega (n)}.\;$

χ(n) - characters

All Dirichlet characters χ(n) are completely multiplicative; e.g. the non-trivial character (mod 4) defined in the introduction, or the principal character (mod n) defined by

$\chi (k)={\begin{cases}1&{\mbox{if }}\gcd(k,n)=1,\\0&{\mbox{if }}\gcd(k,n)\neq 1.\end{cases}}$

Additive functions

ω(n) - distinct prime divisors

ω(n), defined above as the number of distinct primes dividing n, is additive

Completely additive functions

Ω(n) - prime divisors

Ω(n), defined above as the number of prime factors of n counted with multiplicities, is completely additive.

Neither multiplicative nor additive

π(x), Π(x), θ(x), ψ(x) - prime count functions

Unlike the other functions listed in this article, these are defined for non-negative real (not just integer) arguments. They are used in the statement and proof of the prime number theorem.

π(n), the prime counting function, is the number of primes not exceeding x.

$\pi (x)=\sum _{p\leq x}1$

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ...

$\Pi (x)=\sum _{p^{k}\leq x}{\frac {1}{k}}$

θ(x) and ψ(x), the Chebyshev functions are defined as sums of the natural logarithms of the primes not exceeding x:

$\vartheta (x)=\sum _{p\leq x}\log p,$ and

$\psi (x)=\sum _{p^{k}\leq x}\log p.$

Λ(n) - von Mangoldt function

Λ(n), the von Mangoldt function, is 0 unless the argument is a prime power, in which case it is the natural log of the prime:

$\Lambda (n)={\begin{cases}\log p&{\mbox{if }}n=p^{k}{\mbox{ is a prime power}}\\0&{\mbox{if }}n{\mbox{ is not a prime power}}.\end{cases}}$

p(n) - partition function

p(n), the partition function, is the number of unordered representations of n as a sum of positive integers.

λ(n) - Carmichael function

λ(n), the Carmichael function, is the smallest positive number such that $a^{\lambda (n)}\equiv 1{\pmod {n}}$   for all a coprime to n.

For prime powers it is equal to the Euler totient function (for 2, 4, and odd prime powers)
or to one-half the totient (for powers of 2 greater than 4):

$\lambda (n)={\begin{cases}\;\;\phi (n)&{\mbox{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\mbox{if }}n=8,16,32,64,\dots \end{cases}}$

and for general n it is the least common multiple of λ of each of its prime power factors:

$\lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\;\dots \;,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].$

h(n) - Class number

h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

r_k(n) - Sum of k squares

r_k(n) is the number of ways n can be be represented as the sum of k squares.

Summation functions

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

$A(x):=\sum _{n\leq 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 u_P(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 u_P(n)) for large x.

Convolution

Given an arithmetic function a(n), let F_a(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}}}.$

F_a(s) is called a generating function of a(n). One key example is given by a(n) = 1 for all n. In this case F_a(s) = ς(s), the Riemann zeta function.

Consider two arithmetic functions a and b and their respective generating functions F_a(s) and F_b(s). The product F_a(s)F_b(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 F_a(s)F_b(s) = F_c(s) where c is some arithmetic function given by

$c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i|n}a(i)b\left({\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.

See also

Ramanujan sum

References

Tom M. Apostol (1976). Introduction to Analytic Number Theory. Springer Undergraduate Texts in Mathematics. ISBN 0387901639.

• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715

G. J. O. Jameson (2003). The Prime Number Theorem. Cambridge University Press. ISBN 0-521-89110-8.

William J. LeVeque (1996). Fundamentals of Number Theory. Courier Dover Publications. ISBN 0486689069.

Elliott Mendelson (1987). Introduction to Mathematical Logic. CRC Press. ISBN 0412808307.