Divisor function

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

Lua error in package.lua at line 80: module 'strict' not found.

<templatestyles src="Module:Hatnote/styles.css"></templatestyles>

Divisor function σ0(n) up to n = 250
Sigma function σ1(n) up to n = 250
Sum of the squares of divisors, σ2(n), up to n = 250
Sum of cubes of divisors, σ3(n) up to n = 250

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. 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.

Definition

The sum of positive divisors function σx(n), for a real or complex number x, is defined as the sum of the xth powers of the positive divisors of n. It can be expressed in sigma notation as

\sigma_{x}(n)=\sum_{d|n} d^x\,\! ,

where {d|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[1][2] (OEISA000005). When x is 1, the function is called the sigma function or sum-of-divisors function,[1][3] and the subscript is often omitted, so σ(n) is the same as σ1(n) (OEISA000203).

The aliquot sum s(n) of n is the sum of the proper divisors (that is, the divisors excluding n itself, OEISA001065), 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}

Table of values

n Divisors σ0(n) σ1(n) s(n) = σ1(n) − n Comment
1 1 1 1 0 square number: σ0(n) is odd; power of 2: s(n) = n − 1 (almost-perfect)
2 1, 2 2 3 1 Prime: σ1(n) = 1 + n so s(n) = 1; power of 2: s(n) = n − 1 (almost-perfect)
3 1, 3 2 4 1 Prime: σ1(n) = 1 + n so s(n) = 1
4 1, 2, 4 3 7 3 square number: σ0(n) is odd; power of 2: s(n) = n − 1 (almost-perfect)
5 1, 5 2 6 1 Prime: σ1(n) = 1 + n so s(n) = 1
6 1, 2, 3, 6 4 12 6 first perfect number: s(n) = n
7 1, 7 2 8 1 Prime: σ1(n) = 1 + n so s(n) = 1
8 1, 2, 4, 8 4 15 7 power of 2: s(n) = n − 1 (almost-perfect)
9 1, 3, 9 3 13 4 square number: σ0(n) is odd
10 1, 2, 5, 10 4 18 8
11 1, 11 2 12 1 Prime: σ1(n) = 1 + n so s(n) = 1
12 1, 2, 3, 4, 6, 12 6 28 16 first abundant number: s(n) > n
13 1, 13 2 14 1 Prime: σ1(n) = 1 + n so s(n) = 1
14 1, 2, 7, 14 4 24 10
15 1, 3, 5, 15 4 24 9
16 1, 2, 4, 8, 16 5 31 15 square number: σ0(n) is odd; power of 2: s(n) = n − 1 (almost-perfect)
σ0(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+ 1 2 2 3 2 4 2 4 3 4 2
12+ 6 2 4 4 5 2 6 2 6 4 4 2
24+ 8 3 4 4 6 2 8 2 6 4 4 4
36+ 9 2 4 4 8 2 8 2 6 6 4 2
48+ 10 3 6 4 6 2 8 4 8 4 4 2
60+ 12 2 4 6 7 4 8 2 6 4 8 2
72+ 12 2 4 6 6 4 8 2 10 5 4 2
84+ 12 4 4 4 8 2 12 4 6 4 4 4
96+ 12 2 6 6 9 2 8 2 8 8 4 2
108+ 12 2 8 4 10 2 8 4 6 6 4 4
120+ 16 3 4 4 6 4 12 2 8 4 8 2
132+ 12 4 4 8 8 2 8 2 12 4 4 4
σ1(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+ 1 3 4 7 6 12 8 15 13 18 12
12+ 28 14 24 24 31 18 39 20 42 32 36 24
24+ 60 31 42 40 56 30 72 32 63 48 54 48
36+ 91 38 60 56 90 42 96 44 84 78 72 48
48+ 124 57 93 72 98 54 120 72 120 80 90 60
60+ 168 62 96 104 127 84 144 68 126 96 144 72
72+ 195 74 114 124 140 96 168 80 186 121 126 84
84+ 224 108 132 120 180 90 234 112 168 128 144 120
96+ 252 98 171 156 217 102 216 104 210 192 162 108
108+ 280 110 216 152 248 114 240 144 210 182 180 144
120+ 360 133 186 168 224 156 312 128 255 176 252 132
132+ 336 160 204 240 270 138 288 140 336 192 216 168
σ2(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+ 1 5 10 21 26 50 50 85 91 130 122
12+ 210 170 250 260 341 290 455 362 546 500 610 530
24+ 850 651 850 820 1050 842 1300 962 1365 1220 1450 1300
36+ 1911 1370 1810 1700 2210 1682 2500 1850 2562 2366 2650 2210
48+ 3410 2451 3255 2900 3570 2810 4100 3172 4250 3620 4210 3482
60+ 5460 3722 4810 4550 5461 4420 6100 4490 6090 5300 6500 5042
72+ 7735 5330 6850 6510 7602 6100 8500 6242 8866 7381 8410 6890
84+ 10500 7540 9250 8420 10370 7922 11830 8500 11130 9620 11050 9412
96+ 13650 9410 12255 11102 13671 10202 14500 10610 14450 13000 14050 11450
108+ 17220 11882 15860 13700 17050 12770 18100 13780 17682 15470 17410 14500
120+ 22100 14763 18610 16820 20202 16276 22750 16130 21845 18500 22100 17162
132+ 25620 18100 22450 21320 24650 18770 26500 19322 27300 22100 25210 20740

The cases x = 2 to 5 are listed in OEISA001157OEISA001160, x = 6 to 24 are listed in OEISA013954OEISA013972.

Properties

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.[citation needed]

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.

Clearly, 1 < \sigma_0(n) < n and σ(n) > n for all n > 2.

The divisor function is multiplicative, but not completely multiplicative. 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} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}

which is equivalent to the useful formula:


\sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = 
\prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}).

It follows (by setting x = 0) that d(n) is:

\sigma_0(n)=\prod_{i=1}^r (a_i+1).

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:


\begin{align}
\sigma_0(24) & = \prod_{i=1}^{2} (a_i+1) \\
& = (3 + 1)(1 + 1) = 4 \times 2 = 8.
\end{align}

The eight divisors counted by this formula are 1, 2, 4, 8, 3, 6, 12, and 24.

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 the one used to recognize perfect numbers which are the n for which 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, for example, n = 2^k, then \sigma(n) = 2 \times 2^k - 1 = 2n - 1, and s(n) = n - 1, which makes n almost-perfect.

As an example, for two distinct primes p and q with p < q, let

n = pq. \,

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 φ(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 \,

allow us to express p and q in terms of σ(n) and φ(n) only, without even knowing 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 n and either σ(n) or φ(n) (or knowing p+q and either σ(n) or φ(n)) allows us to easily find p and q.

In 1984, Roger Heath-Brown proved that

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

will occur infinitely often.

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 s>1,s>a+1,

which for d(n) = σ0(n) gives

\sum_{n=1}^\infty \frac{d(n)}{n^s} = \zeta^2(s)\quad\text{for}\quad s>1,

and

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

A Lambert series involving the divisor function is:

\sum_{n=1}^\infty q^n \sigma_a(n) = \sum_{n=1}^\infty \frac{n^a q^n}{1-q^n}

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.

Growth rate

In little-o notation, the divisor function satisfies the inequality (see page 296 of Apostol’s book[4])

\mbox{for all }\epsilon>0,\quad d(n)=o(n^\epsilon).

More precisely, Severin Wigert showed that

\limsup_{n\to\infty}\frac{\log d(n)}{\log n/\log\log n}=\log2.

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 (see Theorem 3.3 of Apostol’s book[4])

\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 (Grönwall 1913). His proof uses Mertens' 3rd 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.

In 1915, Ramanujan proved that under the assumption of the Riemann hypothesis, the inequality:

\ \sigma(n) < e^\gamma n \log \log n (Robin's inequality)

holds for all sufficiently large n (Ramanujan 1997). 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 (Robin 1984). 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 (Akbary & Friggstad 2009). 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 (Choie et al. 2007).

Robin also proved, unconditionally, that the inequality

\ \sigma(n) < e^\gamma n \log \log n + \frac{0.6483\ n}{\log \log 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) < H_n + \ln(H_n)e^{H_n}

for every natural number n > 1, where H_n is the nth harmonic number, (Lagarias 2002).

See also

Notes

  1. 1.0 1.1 Long (1972, p. 46)
  2. Pettofrezzo & Byrkit (1970, p. 63)
  3. Pettofrezzo & Byrkit (1970, p. 58)
  4. 4.0 4.1 Lua error in package.lua at line 80: module 'strict' not found.

References

  • Lua error in package.lua at line 80: module 'strict' not found..
  • Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Weisstein, Eric W., "Divisor Function", MathWorld.
  • Weisstein, Eric W., "Robin's Theorem", MathWorld.
  • 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.

hu:Osztóösszeg-függvény

pl:Funkcja σ