Divisor count function

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

1 Definition
- 1.1 Formula in terms of prime factorization
2 Behavior
- 2.1 Lower bound
- 2.2 Upper bound
3 Relation with other arithmetic functions
- 3.1 Family of divisor power sum functions
- 3.2 Relations expressed in terms of Dirichlet products
4 Relation with properties of numbers
5 Properties
6 Generalization to other rings
- 6.1 Unique factorization domains
7 Algebraic significance
8 External links

Definition

Let $\text{[math]}$ be a natural number. The divisor count function of $\text{[math]}$ , denoted $\text{[math]}$ $\text{[math]}$ , or $\text{[math]}$ , is defined as the number of positive divisors of $\text{[math]}$ . In other words:

$\text{[math]}$ .

Formula in terms of prime factorization

Suppose we have:

$\text{[math]}$ .

Then:

$\text{[math]}$ .

Behavior

Lower bound

The divisor count function of $\text{[math]}$ takes its lowest value (other than $\text{[math]}$ ) at primes.

$\text{[math]}$ .

In particular:

$\text{[math]}$ .

Upper bound

Fill this in later

Relation with other arithmetic functions

Family of divisor power sum functions

For any real number (typically, integer) $\text{[math]}$ , the divisor power sum function $\text{[math]}$ is the sum of $\text{[math]}$ powers of all the positive divisors of $\text{[math]}$ . The divisor count function is the special case $\text{[math]}$ . The case $\text{[math]}$ is the divisor sum function, often just denoted $\text{[math]}$ , while the case $\text{[math]}$ is the divisor square sum function.

Relations expressed in terms of Dirichlet products

$\text{[math]}$ : The divisor count function can be expressed as the Dirichlet product of the all ones function with itself.
$\text{[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.
$\text{[math]}$ : The Dirichlet product of the divisor count function and the Euler phi-function is the divisor sum function.

Relation with properties of numbers

Prime number is a natural number $\text{[math]}$ for which $\text{[math]}$ .
Perfect square is a natural number $\text{[math]}$ for which $\text{[math]}$ is odd.
Refactorable number is a natural number $\text{[math]}$ for which $\text{[math]}$ divides $\text{[math]}$ .

Properties

Multiplicativity

This arithmetic function is a multiplicative function: the product of this function for two natural numbers that are relatively prime is the value of the function at the product.
View a complete list of multiplicative functions

Complete multiplicativity

NO: This arithmetic function is not a completely multiplicative function: in other words, the product of the values of the function at two natural numbers need not equal the value at the product.

For natural numbers $\text{[math]}$ and $\text{[math]}$ , it is not necessary that $\text{[math]}$ . In fact, the equality holds if and only if $\text{[math]}$ and $\text{[math]}$ are relatively prime.

Preservation of divisibility

NO: This arithmetic function is not a divisibility-preserving function: it does not preserve divisibility.

If $\text{[math]}$ divides $\text{[math]}$ , it is not necessary that $\text{[math]}$ should divide $\text{[math]}$ .

Generalization to other rings

This generalizes the notion of divisor count function from the case of the ring of integers $\text{[math]}$ to more general classes of rings.

Unique factorization domains

Suppose $\text{[math]}$ is a unique factorization domain. The divisor count function is a function defined on the nonzero elements of $\text{[math]}$ , and is defined as the number of associate classes of divisors of that element. (Note that this does not count the actual number of divisors, but only the number of divisors up to multiplication by units -- this has the same effect as counting only the positive divisors does in the case of integers). Further, the same formula in terms of factorization holds. If we have:

$\text{[math]}$ .

Then:

$\text{[math]}$ .

Algebraic significance

Number of subgroups of the cyclic group: For any natural number $\text{[math]}$ , $\text{[math]}$ equals the number of subgroups of the cyclic group of order $\text{[math]}$ under the action of the automorphism group.
Number of automorphism classes of elements in the cyclic group: For any natural number $\text{[math]}$ , $\text{[math]}$ equals the number of equivalence classes of elements in the cyclic group of order $\text{[math]}$ under the action of the automorphism group. In fact, two elements are in the same automorphism class if and only if they generate the same subgroup. The sizes of these equivalence classes are $\text{[math]}$ for the divisors $\text{[math]}$ of $\text{[math]}$ , and this is a combinatorial proof of the fact that $\text{[math]}$ .
Number of associate classes of elements in the ring of integers modulo $\text{[math]}$ : For any natural number $\text{[math]}$ , $\text{[math]}$ equals the number of equivalence classes of elements in the ring of integers modulo $\text{[math]}$ under the relation of being associate elements. In fact, the equivalence classes of associate elements are precisely the same as the equivalence classes under the action of automorphisms of the additive group of the ring. Thus, their sizes are $\text{[math]}$ , for the divisors $\text{[math]}$ of $\text{[math]}$ .
Number of irreducible factors of the polynomial $\text{[math]}$ over $\text{[math]}$ : This polynomial is a product of irreducible factors called cyclotomic polynomials $\text{[math]}$ for the divisors $\text{[math]}$ of $\text{[math]}$ , where $\text{[math]}$ has as its roots the primitive $\text{[math]}$ roots of unity. The degree of $\text{[math]}$ is $\text{[math]}$ .