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 arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, a divisor function is an
arithmetic function In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
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 language ...
. 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 Eisenstein series, named after German mathematician Gotthold Eisenstein, are particular modular forms with infinite series expansions that may be written down directly. Originally defined for the modular group, Eisenstein series can be generaliz ...
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 (mathematics), group action of the modular group, and also satisfying a grow ...
s. Divisor functions were studied by Ramanujan, who gave a number of important
congruences In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
and identities; these are treated separately in the article
Ramanujan's sum In number theory, Ramanujan's sum, usually denoted ''cq''(''n''), is a function of two positive integer variables ''q'' and ''n'' defined by the formula : c_q(n) = \sum_ e^, where (''a'', ''q'') = 1 means that ''a'' only takes on values coprime ...
. A related function is the
divisor summatory function 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 ...
, 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 In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, matr ...
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 by ...
''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 In number theory, the aliquot sum ''s''(''n'') of a positive integer ''n'' is the sum of all proper divisors of ''n'', that is, all divisors of ''n'' other than ''n'' itself. That is, :s(n)=\sum\nolimits_d. It can be used to characterize the prim ...
''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 In mathematics, an aliquot sequence is a sequence of positive integers in which each term is the sum of the proper divisors of the previous term. If the sequence reaches the number 1, it ends, since the sum of the proper divisors of 1 is 0. Defi ...
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 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 because the only ways ...
''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-negative ...
; instead, the smallest such number may be obtained by multiplying together the first ''n''
Fermi–Dirac prime In number theory, a Fermi–Dirac prime is a prime power whose exponent is a power of two. These numbers are named from an analogy to Fermi–Dirac statistics in physics based on the fact that each integer has a unique representation as a product ...
s, 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 In number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. A weaker condition is also important, respecting only products of coprime ...
: :\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 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 ...
, 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 ma ...
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 A pentagonal number is a figurate number that extends the concept of triangular and square numbers to the pentagon, but, unlike the first two, the patterns involved in the construction of pentagonal numbers are not rotationally symmetrical. The ...
(, starting at offset 1). Indeed, Euler proved this by logarithmic differentiation of the identity in his
Pentagonal number theorem In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. It states that :\prod_^\left(1-x^\right)=\sum_^\left(-1\right)^x^=1+\sum_^\infty(-1)^k\left(x^+x^\right ...
. 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. T ...
s, which are the ''n'' such that ''s''(''n'') = ''n''. If ''s''(''n'') > ''n'', then ''n'' is an
abundant number 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 ...
, and if ''s''(''n'') < ''n'', then ''n'' is a
deficient number In number theory, a deficient number or defective number is a number ''n'' for which the sum of divisors of ''n'' is less than 2''n''. Equivalently, it is a number for which the sum of proper divisors (or aliquot sum) is less than ''n''. For ex ...
. 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 ot ...
. 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 supervis ...
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 analyti ...
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 In mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form :S(q)=\sum_^\infty a_n \frac . It can be resumed formally by expanding the denominator: :S(q)=\sum_^\infty a_n \sum_^\infty q^ = \sum_^\infty b_m ...
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 Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
, ''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 sum In number theory, Ramanujan's sum, usually denoted ''cq''(''n''), is a function of two positive integer variables ''q'' and ''n'' defined by the formula : c_q(n) = \sum_ e^, where (''a'', ''q'') = 1 means that ''a'' only takes on values coprime ...
s 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 Land ...
, the divisor function satisfies the inequality: :\mbox\varepsilon>0,\quad d(n)=o(n^\varepsilon). More precisely, Severin Wigert 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 Land ...
,
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 In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...
. 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 ...
, 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 bicondi ...
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 P ...
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 ...
''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, \dot ...
, .


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 ot ...
, 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 In mathematics, a natural number ''a'' is a unitary divisor (or Hall divisor) of a number ''b'' if ''a'' is a divisor of ''b'' and if ''a'' and \frac are coprime, having no common factor other than 1. Thus, 5 is a unitary divisor of 60, because 5 an ...


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