In number theory, an arithmetic, arithmetical, or number-theoretic function[1][2] is generally any functionf(n) whose domain is the positive integers and whose range is a subset of the complex numbers.[3][4][5] Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".[6] There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.
An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.
Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of Ramanujan's sum.
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.
Notation
edit
In this article, and mean that the sum or product is over all prime numbers:
and
Similarly, and mean that the sum or product is over all prime powers with strictly positive exponent (so k = 0 is not included):
The notations and mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if n = 12, then
The notations can be combined: and mean that the sum or product is over all prime divisors of n. For example, if n = 18, then
and similarly and mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then
Ω(n), ω(n), νp(n) – prime power decomposition
edit
The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: where p1 < p2 < ... < pk are primes and the aj 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 the p-adic valuationνp(n) to be the exponent of the highest power of the prime p that divides n. That is, if p is one of the pi then νp(n) = ai, otherwise it is zero. Then
To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω.
Multiplicative functions
edit
σk(n), τ(n), d(n) – divisor sums
edit
σk(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.
σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).
Since a positive number to the zero power is one, σ0(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).
Setting k = 0 in the second product gives
φ(n) – Euler totient function
edit
φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.
Jk(n) – Jordan totient function
edit
Jk(n), the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J1(n).
Although it is hard to say exactly what "arithmetical property of n" it "expresses",[7] (τ(n) is (2π)−12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function)[8] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σk(n) and rk(n) functions (because these are also coefficients in the expansion of modular forms).
cq(n) – Ramanujan's sum
edit
cq(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity:
Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:
For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.
Logarithmic derivative
edit
, where is the arithmetic derivative.
Neither multiplicative nor additive
edit
π(x), Π(x), θ(x), ψ(x) – prime-counting functions
edit
These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.
π(x), the prime-counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers.
A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ... It is the summation function of the arithmetic function which takes the value 1/k on integers which are the k-th power of some prime number, and the value 0 on other integers.
θ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x.
The Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.
Λ(n) – von Mangoldt function
edit
Λ(n), the von Mangoldt function, is 0 unless the argument n is a prime power pk, in which case it is the natural log of the prime p:
p(n) – partition function
edit
p(n), the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:
For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n:
and for general n it is the least common multiple of λ of each of the prime power factors of n:
h(n) – Class number
edit
h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminantn. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.
rk(n) – Sum of k squares
edit
rk(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.
Given an arithmetic function a(n), its summation functionA(x) is defined by
A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervalsm < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.
Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:
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.
A classical example of this phenomenon[9] is given by the divisor summatory function, the summation function of d(n), the number of divisors of n:
An average order of an arithmetic function is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if
as x tends to infinity. The example above shows that d(n) has the average order log(n).[10]
Dirichlet convolution
edit
Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):[11]Fa(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the Riemann zeta function.
The generating function of the Möbius function is the inverse of the 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:
It is a straightforward exercise to show that if c(n) is defined by
then
A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function:
Multiplying by the inverse of the zeta function gives the Möbius inversion formula:
If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.
Relations among the functions
edit
There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page divisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.
That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, that is, σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.
Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:
The sequence is called the convolution or the Cauchy product of the sequences an and bn.
These formulas may be proved analytically (see Eisenstein series) or by elementary methods.[28]
Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences[35] for the functions. See Ramanujan tau function for some examples.
Extend the domain of the partition function by setting p(0) = 1.
An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).[38]
Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol:
Then if D < −4 is a fundamental discriminant[39][40]
There is also a formula relating r3 and h. Again, let D be a fundamental discriminant, D < −4. Then[41]
^Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7.
^Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.
^Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.
^Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134
Hardy, G. H. (1999), Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work, Providence RI: AMS / Chelsea, hdl:10115/1436, ISBN 978-0-8218-2023-0
Hardy, G. H.; Wright, E. M. (1979) [1938]. An Introduction to the Theory of Numbers (5th ed.). Oxford: Clarendon Press. ISBN 0-19-853171-0. MR 0568909. Zbl 0423.10001.
Jameson, G. J. O. (2003), The Prime Number Theorem, Cambridge University Press, ISBN 0-521-89110-8
Koblitz, Neal (1984), Introduction to Elliptic Curves and Modular Forms, New York: Springer, ISBN 0-387-97966-2
Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea
William J. LeVeque (1996), Fundamentals of Number Theory, Courier Dover Publications, ISBN 0-486-68906-9
Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
Elliott Mendelson (1987), Introduction to Mathematical Logic, CRC Press, ISBN 0-412-80830-7
Nagell, Trygve (1964), Introduction to number theory (2nd Edition), Chelsea, ISBN 978-0-8218-2833-5
Williams, Kenneth S. (2011), Number theory in the spirit of Liouville, London Mathematical Society Student Texts, vol. 76, Cambridge: Cambridge University Press, ISBN 978-0-521-17562-3, Zbl 1227.11002
Further reading
edit
Schwarz, Wolfgang; Spilker, Jürgen (1994), Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties, London Mathematical Society Lecture Note Series, vol. 184, Cambridge University Press, ISBN 0-521-42725-8, Zbl 0807.11001