Divisor function

The sum of positive divisors function σz(n), for a real or complex number z, is defined as the sum of the zth powers of the positive divisors of n. It can be expressed in sigma notation as :\sigma_z(n)=\sum_{d\mid n} d^z\,\! , where {d\mid n} is shorthand for "d divides 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 divisors (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{align} \sigma_0(12) & = 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 \\ & = 1 + 1 + 1 + 1 + 1 + 1 = 6, \end{align} while σ1(12) is the sum of all the divisors: : \begin{align} \sigma_1(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 + 12^1 \\ & = 1 + 2 + 3 + 4 + 6 + 12 = 28, \end{align} and the aliquot sum s(12) of proper divisors is: : \begin{align} s(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 \\ & = 1 + 2 + 3 + 4 + 6 = 16. \end{align} σ−1(n) is sometimes called the abundancy index of n, and we have: : \begin{align} \sigma_{-1}(12) & = 1^{-1} + 2^{-1} + 3^{-1} + 4^{-1} + 6^{-1} + 12^{-1} \\[6pt] & = \tfrac11 + \tfrac12 + \tfrac13 + \tfrac14 + \tfrac16 + \tfrac1{12} \\[6pt] & = \tfrac{12}{12} + \tfrac6{12} + \tfrac4{12} + \tfrac3{12} + \tfrac2{12} + \tfrac1{12} \\[6pt] & = \tfrac{12 + 6 + 4 + 3 + 2 + 1}{12} = \tfrac{28}{12} = \tfrac73 = \tfrac{\sigma_1(12)}{12} \end{align} ==Table of values==

The cases x = 2 to 5 are listed in through , x = 6 to 24 are listed in through . ==Properties==

Formulas at prime powers For a prime number p, :\begin{align} \sigma_0(p) & = 2 \\ \sigma_0(p^n) & = n+1 \\ \sigma_1(p) & = p+1 \end{align} because by definition, the factors of a prime number are 1 and itself. Also, where pn# denotes the primorial, : \sigma_0(p_n\#) = 2^n since n prime factors allow a sequence of binary selection (p_{i} 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; 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 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_{i=1}^r p_i^{a_i} where r = ω(n) is the number of distinct prime factors of n, pi is the ith prime factor, and ai is the maximum power of pi by which n is divisible, then we have: :\sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = \prod_{i=1}^r \left (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x} \right ). which, when x ≠ 0, is equivalent to the useful formula: :\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}. When x = 0, \sigma_0(n) is: :\sigma_0(n)=\prod_{i=1}^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, a1 is 3 and a2 is 1. Thus we can calculate \sigma_0(24) as so: : \sigma_0(24) = \prod_{i=1}^{2} (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 proved the remarkable recurrence: :\begin{align} \sigma_1(n) &= \sigma_1(n-1)+\sigma_1(n-2)-\sigma_1(n-5)-\sigma_1(n-7)+\sigma_1(n-12)+\sigma_1(n-15)+ \cdots \\[12mu] &= \sum_{i\in\N} (-1)^{i+1}\left( \sigma_1 \left( n-\frac{1}{2} \left( 3i^2-i \right) \right) + \sigma_1 \left( n-\frac{1}{2} \left( 3i^2+i \right) \right) \right), \end{align} where \sigma_1(0)=n if it occurs and \sigma_1(x)=0 for x , and \tfrac{1}{2} \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_{0}(n) is even; for a square integer, one divisor (namely \sqrt n) is not paired with a distinct divisor and \sigma_{0}(n) is odd. Similarly, the number \sigma_{1}(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 numbers, which are the n such that s(n) = n. If s(n) > n, then n is an abundant number, and if s(n) 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. Then, the roots of :(x-p)(x-q) = x^2 - (p+q)x + n = x^2 - [(\sigma(n) - \varphi(n))/2]x + [(\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{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}, :q = (\sigma(n) - \varphi(n))/4 + \sqrt{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}. 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 proved that the equality :\sigma_0(n) = \sigma_0(n + 1) is true for infinitely many values of , see . Dirichlet convolutions By definition:\sigma = \operatorname{Id} * \mathbf 1By Möbius inversion:\operatorname{Id} = \sigma * \mu ==Series relations==

Two Dirichlet series involving the divisor function are: :\sum_{n=1}^\infty \frac{\sigma_{a}(n)}{n^s} = \zeta(s) \zeta(s-a)\quad\text{for}\quad \real(s)>1+\max\{\real(a),0\}, where \zeta is the Riemann zeta function. The series for d(n) = σ0(n) gives: : \sum_{n=1}^\infty \frac{d(n)}{n^s} = \zeta^2(s)\quad\text{for}\quad \real(s)>1, and a Ramanujan identity :\sum_{n=1}^\infty \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s) \zeta(s-a) \zeta(s-b) \zeta(s-a-b)}{\zeta(2s-a-b)}, which is a special case of the Rankin–Selberg convolution. A Lambert series involving the divisor function is: :\sum_{n=1}^\infty q^n \sigma_a(n) = \sum_{n=1}^\infty \sum_{j=1}^\infty n^a q^{j\,n} = \sum_{n=1}^\infty \frac{n^a q^n}{1-q^n} = \sum_{n=1}^\infty \operatorname{Li}_{-a}(q^n) for arbitrary complex |q| ≤ 1 and a (\operatorname{Li} is the polylogarithm). 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 : :\sigma_k(n) = \zeta(k+1)n^k\sum_{m=1}^\infty \frac {c_m(n)}{m^{k+1}}. 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{(-1)^n}{2^{k+1}} + \frac{2\cos\frac {2\pi n}{3}}{3^{k+1}} + \frac{2\cos\frac {\pi n}{2}}{4^{k+1}} + \cdots\right] ==Growth rate==

In little-o notation, the divisor function satisfies the inequality: :\mbox{for all }\varepsilon>0,\quad d(n)=o(n^\varepsilon). More precisely, Severin Wigert showed that: :\limsup_{n\to\infty}\frac{\log d(n)}{\log n/\log\log n}=\log2, approached by n taking the primorials since :p_k\# = e^{(1 + o(1)) k \log k}. On the other hand, since there are infinitely many prime numbers, :\liminf_{n\to\infty} d(n)=2. In Big-O notation, Peter Gustav Lejeune Dirichlet showed that the average order of the divisor function satisfies the following inequality: :\mbox{for all } x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}), where \gamma is Euler's gamma constant. Improving the bound O(\sqrt{x}) 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_{n\rightarrow\infty}\frac{\sigma(n)}{n\,\log \log n}=e^\gamma, where lim sup is the limit superior. This result is '''Grönwall's theorem''', published in 1913 . His proof uses Mertens' third theorem, which says that: :\lim_{n\to\infty}\frac{1}{\log n}\prod_{p\le n}\frac{p}{p-1}=e^\gamma, where p denotes a prime. Grönwall also showed that : \limsup_{n\rightarrow\infty}\frac{\sigma_a(n)}{n^a}=\zeta(a),\quad a>1, where \zeta is the Riemann zeta function. In 1915, Ramanujan proved that under the assumption of the Riemann hypothesis, Robin's inequality :\ \sigma(n) (where γ is the Euler–Mascheroni constant) 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 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) holds for all n ≥ 3. A related bound was given by Jeffrey Lagarias in 2002, who proved that the Riemann hypothesis is equivalent to the statement that: : \sigma(n) for every natural number n > 1, where H_n is the nth harmonic number, . == See also ==