Divisor count function - Revision history

Vipul at 14:51, 5 May 2009

2009-05-05T14:51:56Z

@@ Line 32: / Line 32: @@
 {{fillin}}
 ==Relation with other arithmetic functions==
@@ Line 51: / Line 44: @@
 * <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]].

Vipul at 22:46, 2 May 2009

2009-05-02T22:46:36Z

← Older revision		Revision as of 22:46, 2 May 2009
Line 32:		Line 32:

	{{fillin}}		{{fillin}}

			==Algebraic significance==

			* Number of subgroups of the cyclic group: For any natural number <math>n</math>, <math>\sigma_0(n)</math> equals the number of subgroups of the cyclic group of order <math>n</math> under the action of the automorphism group.
			* Number of automorphism classes of elements in the cyclic group: For any natural number <math>n</math>, <math>\sigma_0(n)</math> equals the number of equivalence classes of elements in the cyclic group of order <math>n</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 <math>\varphi(d)</math> for the divisors <math>d</math> of <math>n</math>, and this is a combinatorial proof of the fact that <math>n = \sum_{d\|n}\varphi(d)</math>.
			* Number of associate classes of elements in the ring of integers modulo <math>n</math>: For any natural number <math>n</math>, <math>\sigma_0(n)</math> equals the number of equivalence classes of elements in the ring of integers modulo <math>n</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 <math>\varphi(d)</math>, for the divisors <math>d</math> of <math>n</math>.
			* Number of irreducible factors of the polynomial <math>x^n - 1</math> over <math>\mathbb{Q}</math>: This polynomial is a product of irreducible factors called [[cyclotomic polynomial]]s <math>\Phi_d</math> for the divisors <math>d</math> of <math>n</math>, where <math>\Phi_d</math> has as its roots the primitive <math>d^{th}</math> roots of unity. The degree of <math>\Phi_d</math> is <math>\varphi(d)</math>.

	==Relation with other arithmetic functions==		==Relation with other arithmetic functions==

Vipul at 02:55, 29 April 2009

2009-04-29T02:55:17Z

← Older revision		Revision as of 02:55, 29 April 2009
Line 3:		Line 3:
	==Definition==		==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===		===Formula in terms of prime factorization===
Line 15:		Line 15:
	Then:		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==		==Behavior==
Line 23:		Line 23:
	The divisor count function of <math>n</math> takes its lowest value (other than <math>1</math>) at primes.		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:		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===		===Upper bound===

	{{fillin}}		{{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]].

Vipul: Created page with '{{arithmetic function}} ==Definition== Let $n$ be a natural number. The '''divisor count function''' of $n$ , denoted $d(n)$ or $\tau(n...'$

2009-04-29T00:40:57Z

Created page with '{{arithmetic function}} ==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...'

New page

{{arithmetic function}}

==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:

<math>\tau(n) = \sum_{d|n} 1</math>.

===Formula in terms of prime factorization===

Suppose we have:

<math>n = p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}</math>.

Then:

<math>\tau(n) = \prod_{i=1}^r (k_i + 1)</math>.

==Behavior==

===Lower bound===

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

In particular:

<math>\lim \inf_{n \to \infty} \tau(n) = 2</math>.

===Upper bound===

{{fillin}}

Divisor count function - Revision history

Vipul at 14:51, 5 May 2009

Vipul at 22:46, 2 May 2009

Vipul at 02:55, 29 April 2009

Vipul: Created page with '{{arithmetic function}} ==Definition== Let n be a natural number. The '''divisor count function''' of n, denoted d(n) or \tau(n...'

Vipul: Created page with '{{arithmetic function}} ==Definition== Let $n$ be a natural number. The '''divisor count function''' of $n$ , denoted $d(n)$ or $\tau(n...'$