HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, and specifically 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 divisor function is an arithmetic function related to the
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 an
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 ...
. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (including 1 and the number itself). It appears in a number of remarkable identities, including relationships on the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
and the Eisenstein series of
modular form In mathematics, a modular form is a (complex) analytic function on the upper half-plane satisfying a certain kind of functional equation with respect to the group action of the modular group, and also satisfying a growth condition. The theory o ...
s. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum. A related function is the divisor summatory function, which, as the name implies, is a sum over the divisor function.


Definition

The sum of positive divisors function σ''z''(''n''), for a real or complex number ''z'', is defined as the sum of the ''z''th powers of the 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''. It can be expressed in sigma notation as :\sigma_z(n)=\sum_ d^z\,\! , where is shorthand for "''d''
divides 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 b ...
''n''". The notations ''d''(''n''), ν(''n'') and τ(''n'') (for the German ''Teiler'' = divisors) are also used to denote σ0(''n''), or the number-of-divisors function (). When ''z'' is 1, the function is called the sigma function or sum-of-divisors function, and the subscript is often omitted, so σ(''n'') is the same as σ1(''n'') (). The aliquot sum ''s''(''n'') of ''n'' is the sum of the
proper 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 (that is, the divisors excluding ''n'' itself, ), and equals σ1(''n'') − ''n''; the aliquot sequence of ''n'' is formed by repeatedly applying the aliquot sum function.


Example

For example, σ0(12) is the number of the divisors of 12: : \begin \sigma_(12) & = 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 \\ & = 1 + 1 + 1 + 1 + 1 + 1 = 6, \end while σ1(12) is the sum of all the divisors: : \begin \sigma_(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 + 12^1 \\ & = 1 + 2 + 3 + 4 + 6 + 12 = 28, \end and the aliquot sum s(12) of proper divisors is: : \begin s(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 \\ & = 1 + 2 + 3 + 4 + 6 = 16. \end σ-1(''n'') is sometimes called the
abundancy index In number theory, an abundant number or excessive number is a number for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. The ...
of ''n'', and we have: : \begin \sigma_(12) & = 1^ + 2^ + 3^ + 4^ + 6^ + 12^ \\ & = \tfrac11 + \tfrac12 + \tfrac13 + \tfrac14 + \tfrac16 + \tfrac1 \\ & = \tfrac + \tfrac6 + \tfrac4 + \tfrac3 + \tfrac2 + \tfrac1 \\ & = \tfrac = \tfrac = \tfrac73 = \tfrac \end


Table of values

The cases ''x'' = 2 to 5 are listed in − , ''x'' = 6 to 24 are listed in − .


Properties


Formulas at prime powers

For a
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 ...
''p'', :\begin \sigma_0(p) & = 2 \\ \sigma_0(p^n) & = n+1 \\ \sigma_1(p) & = p+1 \end because by definition, the factors of a prime number are 1 and itself. Also, where ''pn''# denotes the
primorial In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function ...
, : \sigma_0(p_n\#) = 2^n since ''n'' prime factors allow a sequence of binary selection (p_ or 1) from ''n'' terms for each proper divisor formed. However, these are not in general the smallest numbers whose number of divisors is a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negat ...
; instead, the smallest such number may be obtained by multiplying together the first ''n'' Fermi–Dirac primes, prime powers whose exponent is a power of two. Clearly, 1 < \sigma_0(n) < n for all n > 2, and \sigma_x(n) > n for all n > 1, x > 0 . The divisor function is multiplicative (since each divisor ''c'' of the product ''mn'' with \gcd(m, n) = 1 distinctively correspond to a divisor ''a'' of ''m'' and a divisor ''b'' of ''n''), but not completely multiplicative: :\gcd(a, b)=1 \Longrightarrow \sigma_x(ab)=\sigma_x(a)\sigma_x(b). The consequence of this is that, if we write :n = \prod_^r p_i^ where ''r'' = ''ω''(''n'') is the number of distinct prime factors of ''n'', ''pi'' is the ''i''th prime factor, and ''ai'' is the maximum power of ''pi'' by which ''n'' is divisible, then we have: :\sigma_x(n) = \prod_^r \sum_^ p_i^ = \prod_^r \left (1 + p_i^x + p_i^ + \cdots + p_i^ \right ). which, when ''x'' ≠ 0, is equivalent to the useful formula: :\sigma_x(n) = \prod_^ \frac. When ''x'' = 0, ''d''(''n'') is: :\sigma_0(n)=\prod_^r (a_i+1). This result can be directly deduced from the fact that all divisors of n are uniquely determined by the distinct tuples (x_1, x_2, ..., x_i, ..., x_r) of integers with 0 \le x_i \le a_i (i.e. a_i+1 independent choices for each x_i). For example, if ''n'' is 24, there are two prime factors (''p1'' is 2; ''p2'' is 3); noting that 24 is the product of 23×31, ''a''1 is 3 and ''a''2 is 1. Thus we can calculate \sigma_0(24) as so: : \sigma_0(24) = \prod_^ (a_i+1) = (3 + 1)(1 + 1) = 4 \cdot 2 = 8. The eight divisors counted by this formula are 1, 2, 4, 8, 3, 6, 12, and 24.


Other properties and identities

Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
proved the remarkable recurrence: :\begin \sigma(n) &= \sigma(n-1)+\sigma(n-2)-\sigma(n-5)-\sigma(n-7)+\sigma(n-12)+\sigma(n-15)+ \cdots \\ 2mu &= \sum_ (-1)^\left( \sigma \left( n-\frac \left( 3i^2-i \right) \right) + \sigma \left( n-\frac \left( 3i^2+i \right) \right) \right), \end where \sigma(0)=n if it occurs and \sigma(x)=0 for x < 0, and \tfrac \left( 3i^2 \mp i \right) are consecutive pairs of generalized pentagonal numbers (, starting at offset 1). Indeed, Euler proved this by logarithmic differentiation of the identity in his Pentagonal number theorem. For a non-square integer, ''n'', every divisor, ''d'', of ''n'' is paired with divisor ''n''/''d'' of ''n'' and \sigma_(n) is even; for a square integer, one divisor (namely \sqrt n) is not paired with a distinct divisor and \sigma_(n) is odd. Similarly, the number \sigma_(n) is odd if and only if ''n'' is a square or twice a square. We also note ''s''(''n'') = ''σ''(''n'') − ''n''. Here ''s''(''n'') denotes the sum of the ''proper'' divisors of ''n'', that is, the divisors of ''n'' excluding ''n'' itself. This function is used to recognize
perfect number In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. ...
s, which are the ''n'' such that ''s''(''n'') = ''n''. If ''s''(''n'') > ''n'', then ''n'' is an abundant number, and if ''s''(''n'') < ''n'', then ''n'' is a deficient number. If is a power of 2, n = 2^k, then \sigma(n) = 2 \cdot 2^k - 1 = 2n - 1 and s(n) = n - 1, which makes ''n'' almost-perfect. As an example, for two primes p,q:p, let :n = p\,q. Then :\sigma(n) = (p+1)(q+1) = n + 1 + (p+q), :\varphi(n) = (p-1)(q-1) = n + 1 - (p+q), and :n + 1 = (\sigma(n) + \varphi(n))/2, :p + q = (\sigma(n) - \varphi(n))/2, where \varphi(n) is
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 ...
. Then, the roots of :(x-p)(x-q) = x^2 - (p+q)x + n = x^2 - \sigma(n) - \varphi(n))/2 + \sigma(n) + \varphi(n))/2 - 1= 0 express ''p'' and ''q'' in terms of ''σ''(''n'') and ''φ''(''n'') only, requiring no knowledge of ''n'' or p+q, as :p = (\sigma(n) - \varphi(n))/4 - \sqrt, :q = (\sigma(n) - \varphi(n))/4 + \sqrt. Also, knowing and either \sigma(n) or \varphi(n), or, alternatively, p+q and either \sigma(n) or \varphi(n) allows an easy recovery of ''p'' and ''q''. In 1984,
Roger Heath-Brown David Rodney "Roger" Heath-Brown FRS (born 12 October 1952), is a British mathematician working in the field of analytic number theory. Education He was an undergraduate and graduate student of Trinity College, Cambridge; his research supervi ...
proved that the equality :\sigma_0(n) = \sigma_0(n + 1) is true for infinitely many values of , see .


Series relations

Two
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 ...
involving the divisor function are: :\sum_^\infty \frac = \zeta(s) \zeta(s-a)\quad\text\quad s>1,s>a+1, where \zeta is the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
. The series for ''d''(''n'') = ''σ''0(''n'') gives: : \sum_^\infty \frac = \zeta^2(s)\quad\text\quad s>1, and a Ramanujan identity :\sum_^\infty \frac = \frac, which is a special case of the Rankin–Selberg convolution. A Lambert series involving the divisor function is: :\sum_^\infty q^n \sigma_a(n) = \sum_^\infty \sum_^\infty n^a q^ = \sum_^\infty \frac for arbitrary complex , ''q'',  ≤ 1 and ''a''. This summation also appears as the Fourier series of the Eisenstein series and the invariants of the Weierstrass elliptic functions. For k>0, there is an explicit series representation with Ramanujan sums c_m(n) as : (German) :\sigma_k(n) = \zeta(k+1)n^k\sum_^\infty \frac . The computation of the first terms of c_m(n) shows its oscillations around the "average value" \zeta(k+1)n^k: :\sigma_k(n) = \zeta(k+1)n^k \left 1 + \frac + \frac + \frac + \cdots\right/math>


Growth rate

In
little-o notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
, the divisor function satisfies the inequality: :\mbox\varepsilon>0,\quad d(n)=o(n^\varepsilon). More precisely,
Severin Wigert Carl Severin Wigert (1871–1941) was a Swedish mathematician who created Stieltjes–Wigert polynomials and worked on the divisor function, including correctly describing its maximal order of growth. Wigert proved that :\limsup_\frac=\log2. ...
showed that: :\limsup_\frac=\log2. On the other hand, since there are infinitely many prime numbers, :\liminf_ d(n)=2. In
Big-O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
,
Peter Gustav Lejeune Dirichlet Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
showed that the average order of the divisor function satisfies the following inequality: :\mbox x\geq1, \sum_d(n)=x\log x+(2\gamma-1)x+O(\sqrt), where \gamma is Euler's gamma constant. Improving the bound O(\sqrt) in this formula is known as Dirichlet's divisor problem. The behaviour of the sigma function is irregular. The asymptotic growth rate of the sigma function can be expressed by: : \limsup_\frac=e^\gamma, where lim sup is the limit superior. This result is Grönwall's theorem, published in 1913 . His proof uses Mertens' 3rd theorem, which says that: :\lim_\frac\prod_\frac=e^\gamma, where ''p'' denotes a prime. In 1915, Ramanujan proved that under the assumption of the
Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in p ...
, the inequality: :\ \sigma(n) < e^\gamma n \log \log n (Robin's inequality) holds for all sufficiently large ''n'' . The largest known value that violates the inequality is ''n''= 5040. In 1984, Guy Robin proved that the inequality is true for all ''n'' > 5040
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
the Riemann hypothesis is true . This is Robin's theorem and the inequality became known after him. Robin furthermore showed that if the Riemann hypothesis is false then there are an infinite number of values of ''n'' that violate the inequality, and it is known that the smallest such ''n'' > 5040 must be superabundant . It has been shown that the inequality holds for large odd and square-free integers, and that the Riemann hypothesis is equivalent to the inequality just for ''n'' divisible by the fifth power of a prime . Robin also proved, unconditionally, that the inequality: :\ \sigma(n) < e^\gamma n \log \log n + \frac holds for all ''n'' ≥ 3. A related bound was given by
Jeffrey Lagarias Jeffrey Clark Lagarias (born November 16, 1949 in Pittsburgh, Pennsylvania, United States) is a mathematician and professor at the University of Michigan. Education While in high school in 1966, Lagarias studied astronomy at the Summer Science ...
in 2002, who proved that the Riemann hypothesis is equivalent to the statement that: : \sigma(n) < H_n + e^\log(H_n) for every
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
''n'' > 1, where H_n is the ''n''th
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \do ...
, .


See also

* Divisor sum convolutions, lists a few identities involving the divisor functions *
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 ...
, Euler's phi function *
Refactorable number A refactorable number or tau number is an integer ''n'' that is divisible by the count of its divisors, or to put it algebraically, ''n'' is such that \tau(n)\mid n. The first few refactorable numbers are listed in as : 1, 2, 8, 9, 12, 18, ...
* Table of divisors * Unitary divisor


Notes


References

*. * * Bach, Eric; Shallit, Jeffrey, ''Algorithmic Number Theory'', volume 1, 1996, MIT Press. , see page 234 in section 8.8. * * * * * * * * * * * *


External links

* *
Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions
PDF of a paper by Huard, Ou, Spearman, and Williams. Contains elementary (i.e. not relying on the theory of modular forms) proofs of divisor sum convolutions, formulas for the number of ways of representing a number as a sum of triangular numbers, and related results. {{DEFAULTSORT:Divisor function Analytic number theory Number theory Zeta and L-functions