Divisor function
|
|
In mathematics the divisor function σa(n) is defined as the sum of the ath powers of the divisors of n, or
- <math>\sigma_{a}(n)=\sum_{d|n} d^a\,\! .<math>
The notations d(n) and <math>\tau(n)<math> (the tau function) are also used to denote σ0(n), or the number of divisors of n. The sigma function σ(n) is
- <math>\sigma_{1}(n)=\sum d<math>.
For example iff p is a prime number,
- <math>\sigma (p)=p+1\,\! <math>
because, by definition, the factors of a prime number are 1 and itself. Clearly 1 < d(n) < n for all n > 1 and σ(n) > n for all n > 1.
Generally, the divisor function is multiplicative, but not completely multiplicative.
The consequence of this is that, if we write
- <math>n = \prod_{i=1}^{r}p_{i}^{\alpha_{i}}<math>
then we have
- <math>\sigma(n) = \prod_{i=1}^{r} \frac{p_{i}^{\alpha_{i}+1}-1}{p_{i}-1}<math>
which is equivalent to the useful formula:
- <math>
\sigma(n) = \prod_{i=1}^{r} \sum_{j=0}^{\alpha_{i}} p_{i}^{j} = \prod_{i=1}^{r} (1 + p_{i} + p_{i}^2 + ... + p_{i}^{a_r}) <math>
We also note <math>s(n) = \sigma(n) - n<math>. This function is the one used to recognize perfect numbers which are the n for which <math>s(n) = n<math>.
As an example, for two distinct primes p and q, let
- <math>n = pq.<math>
Then
- <math>\phi(n) = (p-1)(q-1) = n + 1 - (p+q),<math>
- <math>\sigma(n) = (p+1)(q+1) = n + 1 + (p+q).<math>
| Contents |
Equations involving the divisor function
Two Dirichlet series involving the divisor function are:
- <math>\sum_{n=1}^{\infty} \frac{\sigma_{a}(n)}{n^s}=\zeta(s) \zeta(s-a)<math>
and
- <math>\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)}<math>
A Lambert series involving the divisor function is:
- <math>\sum_{n=1}^{\infty} q^n \sigma_a(n) = \sum_{n=1}^{\infty} \frac{n^a q^n}{1-q^n}<math>
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.
Inequalities with the divisor function
A pair of inequalities combining the divisor function and the φ function are:
- <math>
\frac {6 n^2} {\pi^2} < \varphi(n) \sigma(n) < n^2 <math>, for n > 1.
For the number of divisors function,
- <math>
d(n) < n^{\frac {2} {3}} <math> for n > 12.
Another bound on the number of divisors is
- <math>
\log d(n) < 1.066 \frac {\log n} {\log \log n} <math> for n > 2.
For the sum of divisors function,
- <math>
\sigma(n) < \frac {6n^\frac {3} {2}} {\pi^2} <math> for n > 12.
Approximate growth rate
The growth rate of the sigma function is approximated by
- <math>
\sigma(n) \sim e^\gamma \ n\ \log \log n <math>
where γ is Euler's constant.
See also
References
- Tom M. Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. ISBN 0-387-90163-9
- Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.de:Teilersummenfunktion