Divisor function

In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. 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 and the Eisenstein series of modular forms. 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.

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 σ₀(n), or the number-of-divisors function (OEIS: A000005). 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 σ₁(n) (OEIS: A000203).

The aliquot sum s(n) of n is the sum of the proper divisors (that is, the divisors excluding n itself, OEIS: A001065), and equals σ₁(n) − n; the aliquot sequence of n is formed by repeatedly applying the aliquot sum function.

For example, σ₀(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 σ₁(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}\)

σ₋₁(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}\)

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. Clearly, \(1 < \sigma_0(n) < n\) for all \(n > 2\), and \(\sigma_x(n) > n\) for all \(n > 1\), \(x > 0\).

In general, since the divisors of a prime power \(p^a\), with \(a\) a natural number, are \(1=p^0,p=p^1,p^2,\ldots,p^a\), then

\(\sigma_x(p^a)=1^x+p^x+p^{2x}+\ldots+p^{ax}\)

If \(n = \prod_{i=1}^r p_i^{a_i}\), where r = ω(n) is the number of distinct prime factors of n, p_i is the ith prime factor, and a_i is the maximum power of p_i 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:

\(\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).\)

Proof: The proof is combinatorial in nature. Distributing (expanding) the product

\(\prod_{i=1}^r \left (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x} \right )\)

gives a sum in which each summand is a product. In the products there is one factor per parentheses, and each is one of the summands in the parentheses. Each such selection gives a different summand. Each such selection is equivalent to select, for each \(i=1,2,\ldots,r\), a value \(0\leq x_i\leq a_i\) which will represent selecting the summand \(p_i^{x_ix}\) from the \(i\)-th parentheses. On the other hand, this is the same collection of choices needed to select a divisor of \(n\), and write it as its prime factorization. This is because each divisor of \(n\) can be written uniquely in the form \(\prod_{i=1}^r p_i^{x_i}\), for \(0\leq x_i\leq a_i\).

For example, the divisors of \(24=2^3\cdot 3^1\) are \(2^0\cdot 3^0, 2^0\cdot 3^1, 2^1\cdot 3^0, 2^1\cdot 3^1, 2^2\cdot 3^0, 2^2\cdot 3^1, 2^3\cdot 3^0, 2^3\cdot 3^1\). These are the same summands obtained when expanding

\((2^0+2^1+2^2+2^3)(3^0+3^1)\)

A direct consequence of the formula is that the function \(n\mapsto\sigma_x(n)\) is multiplicative. In fact, if \(a,b\) are relatively prime, then they have prime factorizations \(\prod_{i=1}^r p_i^{a_i}\) and \(\prod_{i=r+1}^s p_i^{a_i}\) in which the set of primes \(\{p_i\}_{i=1}^{r}\) and \(\{p_i\}_{i=r+1}^s\) are disjoint. Then

\(\sigma_x(ab)=\prod_{i=1}^s \sum_{j=0}^{a_ix}p_i^{jx}=\prod_{i=1}^r \sum_{j=0}^{a_ix} p_i^{jx}\cdot\prod_{i=r+1}^s \sum_{j=0}^{a_ix} p_i^{jx}=\sigma_x(a)\sigma_x(b)\)

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 < 0\), and \(\tfrac{1}{2} \left( 3i^2 \mp i \right)\) are consecutive pairs of generalized pentagonal numbers (OEIS: A001318, 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, then n is a deficient number.

If n 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

\(n = p\,q\).

Then

\(\sigma(n) = (p+1)(q+1) = n + 1 + (p+q),\)

\(\varphi(n) = (p-1)(q-1) = n + 1 - (p+q),\)

\(n + 1 = (\sigma(n) + \varphi(n))/2,\)

\(p + q = (\sigma(n) - \varphi(n))/2,\)

\((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\)

\(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]}.\)

\(\sigma_0(n) = \sigma_0(n + 1)\)

Condensed: the full section is in Wikipedia.

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) = σ₀(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}}.\)

\(\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]\)

Condensed: the full section is in Wikipedia.

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.

\(\limsup_{n\rightarrow\infty}\frac{\sigma(n)}{n\,\log \log n}=e^\gamma,\)

\(\lim_{n\to\infty}\frac{1}{\log n}\prod_{p\le n}\frac{p}{p-1}=e^\gamma,\)

\(\limsup_{n\rightarrow\infty}\frac{\sigma_a(n)}{n^a}=\zeta(a),\quad a>1,\)

\(\ \sigma(n) < e^\gamma n \log \log n\) (where γ is the Euler-Mascheroni constant)

\(\ \sigma(n) < e^\gamma n \log \log n + \frac{0.6483\ n}{\log \log n}\)

\(\sigma(n) < H_n + e^{H_n}\log(H_n)\)

Condensed: the full section is in Wikipedia.