Divisor count function: Difference between revisions

Revision as of 02:55, 29 April 2009

This article defines an arithmetic function or number-theoretic function: a function from the natural numbers to a ring (usually, the ring of integers, rational numbers, real numbers, or complex numbers).
View a complete list of arithmetic functions

Definition

Let $n$ be a natural number. The divisor count function of $n$ , denoted $d (n)$ $σ_{0} (n)$ , or $τ (n)$ , is defined as the number of positive divisors of $n$ . In other words:

$σ_{0} (n) = \sum_{d | n} 1$ .

Formula in terms of prime factorization

Suppose we have:

$n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ .

Then:

$σ_{0} (n) = \prod_{i = 1}^{r} (k_{i} + 1)$ .

Behavior

Lower bound

The divisor count function of $n$ takes its lowest value (other than $1$ ) at primes.

$σ_{0} (p) = 2 \forall p$ .

In particular:

$lim {inf}_{n \to \infty} σ_{0} (n) = 2$ .

Upper bound

Fill this in later

Relation with other arithmetic functions

Family of divisor power sum functions

For any real number (typically, integer) $k$ , the divisor power sum function $σ_{k}$ is the sum of $k^{t h}$ powers of all the positive divisors of $k$ . The divisor count function is the special case $k = 0$ . The case $k = 1$ is the divisor sum function, often just denoted $σ$ , while the case $k = 2$ is the divisor square sum function.

Relations expressed in terms of Dirichlet products

$σ_{0} = U * U$ : The divisor count function can be expressed as the Dirichlet product of the all ones function with itself.
$σ_{0} * μ = U$ : This is obtained simply by applying the Mobius inversion formula to the previous statement. In other words, the Dirichlet product of the divisor count function and the Mobius function is the all ones function.
$σ_{0} * φ = σ$ : The Dirichlet product of the divisor count function and the Euler phi-function is the divisor sum function.

@@ Line 3: / Line 3: @@
 ==Definition==
-Let <math>n</math> be a [[natural number]]. The '''divisor count function''' of <math>n</math>, denoted <math>d(n)</math> or <math>\tau(n)</math>, is defined as the number of positive divisors of <math>n</math>. In other words:
+Let <math>n</math> be a [[natural number]]. The '''divisor count function''' of <math>n</math>, denoted <math>d(n)</math> <math>\sigma_0(n)</math>,  or <math>\tau(n)</math>, is defined as the number of positive divisors of <math>n</math>. In other words:
-<math>\tau(n) = \sum_{d|n} 1</math>.
+<math>\sigma_0(n) = \sum_{d|n} 1</math>.
 ===Formula in terms of prime factorization===
@@ Line 15: / Line 15: @@
 Then:
-<math>\tau(n) = \prod_{i=1}^r (k_i + 1)</math>.
+<math>\sigma_0(n) = \prod_{i=1}^r (k_i + 1)</math>.
 ==Behavior==
@@ Line 23: / Line 23: @@
 The divisor count function of <math>n</math> takes its lowest value (other than <math>1</math>) at primes.
-<math>\tau(p) = 2 \ \forall \ p</math>.
+<math>\sigma_0(p) = 2 \ \forall \ p</math>.
 In particular:
-<math>\lim \inf_{n \to \infty} \tau(n) = 2</math>.
+<math>\lim \inf_{n \to \infty} \sigma_0(n) = 2</math>.
 ===Upper bound===
 {{fillin}}
+==Relation with other arithmetic functions==
+===Family of divisor power sum functions===
+For any real number (typically, integer) <math>k</math>, the [[divisor power sum function]] <math>\sigma_k</math> is the sum of <math>k^{th}</math> powers of all the positive divisors of <math>k</math>. The divisor count function is the special case <math>k = 0</math>. The case <math>k = 1</math> is the [[divisor sum function]], often just denoted <math>\sigma</math>, while the case <math>k = 2</math> is the [[divisor square sum function]].
+===Relations expressed in terms of Dirichlet products===
+* <math>\sigma_0 = U * U</math>: The divisor count function can be expressed as the [[Dirichlet product]] of the [[all ones function]] with itself.
+* <math>\sigma_0 * \mu = U</math>: This is obtained simply by applying the [[Mobius inversion formula]] to the previous statement. In other words, the [[Dirichlet product]] of the divisor count function and the [[Mobius function]] is the [[all ones function]].
+* <math>\sigma_0 * \varphi = \sigma</math>: The Dirichlet product of the divisor count function and the [[Euler phi-function]] is the [[divisor sum function]].