Divisor sum function - Revision history

Vipul at 14:40, 5 May 2009

2009-05-05T14:40:22Z

← Older revision		Revision as of 14:40, 5 May 2009
Line 80:		Line 80:

	* [[Divisor power sum function]] <math>\sigma_k</math> is the sum of the <math>k^{th}</math> powers of all the positive divisors. The divisor sum function is the divisor power sum function <math>\sigma_1</math>. Also related is the [[divisor count function]] <math>\sigma_0</math>, which is also denoted <math>d</math> or <math>\tau</math>.		* [[Divisor power sum function]] <math>\sigma_k</math> is the sum of the <math>k^{th}</math> powers of all the positive divisors. The divisor sum function is the divisor power sum function <math>\sigma_1</math>. Also related is the [[divisor count function]] <math>\sigma_0</math>, which is also denoted <math>d</math> or <math>\tau</math>.

			===Other similarly defined functions===

			* [[Euler phi-function]] is defined as the number of integers less than or equal to <math>n</math> that are relatively prime to <math>n</math>.
			* [[Dedekind psi-function]] is also closely related.

	===Relations expressed in terms of Dirichlet products===		===Relations expressed in terms of Dirichlet products===
Line 86:		Line 91:
	* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.		* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.
	* <math>\sigma * \varphi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.		* <math>\sigma * \varphi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.

			===Inequalities===

			* <math>\sigma(n) \le n\sigma_0(n)</math>, with equality iff <math>n = 1</math>: The sum of all divisors is less than or equal to <math>n</math> times the number of divisors. This follows from the obvious observation that every divisor of <math>n</math> is less than or equal to <math>n</math>.
			* <math>\sigma(n)\varphi(n) \le n^2</math>, with equality iff <math>n = 1</math>: This can be proved, for instance, using the formula for both functions in terms of the prime factorization. There are also combinatorial proofs.

	==Relation with properties of numbers==		==Relation with properties of numbers==
Line 114:		Line 124:
	If <math>m</math> divides <math>n</math>, it is not necessary that <math>\sigma(m)</math> divides <math>\sigma(n)</matH>.		If <math>m</math> divides <math>n</math>, it is not necessary that <math>\sigma(m)</math> divides <math>\sigma(n)</matH>.

			==Algebraic significance==

			The divisor sum function <math>\sigma(n)</math> comes up in the following algebraic contexts:

			* It is the sum of the sizes of all subgroups of a cyclic group of order <math>n</math>: Thus, the ratio <math>\sigma_1(n)/\sigma_0(n)</math> is the ''average'' size of a subgroup.
	==External links==		==External links==

	* [[Mathworld:DivisorFunction\|Divisor function on Mathworld]]		* [[Mathworld:DivisorFunction\|Divisor function on Mathworld]]

Vipul: /* Properties */

2009-05-05T14:33:12Z

Properties

← Older revision		Revision as of 14:33, 5 May 2009
Line 99:		Line 99:

	{{multiplicative}}		{{multiplicative}}

			The divisor sum function is multiplicative: in other words, if <math>m</math> and <math>n</math> are relatively prime positive integers, then:

			<math>\sigma(mn) = \sigma(m)\sigma(n)</math>.

			This can be proved in a number of ways. Apart from a direct proof, it also follows from the fact that the divisor sum function is a [[Dirichlet product]] of two multiplicative functions. {{proofat\|[[Divisor sum function is multiplicative]]}}

	{{not completely multiplicative}}		{{not completely multiplicative}}

			The divisor sum function is ''not'' a completely multiplicative function. In other words, there exist natural numbers <math>m,n</math> such that <math>\sigma(mn) \ne \sigma(m)\sigma(n)</math>. In fact, if <math>m</math> and <math>n</math> are ''not'' relatively prime, <math>\sigma(mn)</math> is ''not'' the product of <math>\sigma(m)</math> and <math>\sigma(n)</math>.

			{{not divisibility-preserving}}

			If <math>m</math> divides <math>n</math>, it is not necessary that <math>\sigma(m)</math> divides <math>\sigma(n)</matH>.

	==External links==		==External links==

	* [[Mathworld:DivisorFunction\|Divisor function on Mathworld]]		* [[Mathworld:DivisorFunction\|Divisor function on Mathworld]]

Vipul at 14:28, 5 May 2009

2009-05-05T14:28:27Z

← Older revision		Revision as of 14:28, 5 May 2009
Line 101:		Line 101:

	{{not completely multiplicative}}		{{not completely multiplicative}}

			==External links==

			* [[Mathworld:DivisorFunction\|Divisor function on Mathworld]]

Vipul at 14:20, 5 May 2009

2009-05-05T14:20:59Z

← Older revision		Revision as of 14:20, 5 May 2009
Line 3:		Line 3:
	==Definition==		==Definition==

	Let <math>n</math> be a [[natural number]]. The '''divisor sum function''' of <math>n</math>, denoted <math>\sigma(n)</math>, is defined in the following equivalent ways:		Let <math>n</math> be a [[natural number]]. The '''divisor sum function''' of <math>n</math>, denoted <math>\sigma(n)</math> or <math>\sigma_1(n)</math>, is defined in the following equivalent ways:

	# <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] <math>E</math> on the natural numbers and the [[all-one function]] <math>U</math>: the function sending every natural number to <math>1</math>.		# <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] <math>E</math> on the natural numbers and the [[all-one function]] <math>U</math>: the function sending every natural number to <math>1</math>.
Line 44:		Line 44:

	A closely related result is [[Robin's theorem]], which states that the [[Riemann hypothesis]] is equivalent to the statement that for <math>n \ge 5041</math>, the ratio is always strictly ''less'' than <math>e^{\gamma}</math>.		A closely related result is [[Robin's theorem]], which states that the [[Riemann hypothesis]] is equivalent to the statement that for <math>n \ge 5041</math>, the ratio is always strictly ''less'' than <math>e^{\gamma}</math>.

			===Logarithmic ratio===

			We have:

			<math>\lim_{n \to \infty} \frac{\log (\sigma(n))}{\log n} = 1</math>.

			Moreover, this approach is from the positive side, since <math>\sigma(n) \ge n + 1</math> for all <math>n > 1</math>.

			==Summatory function and average value==

	===Summatory function===		===Summatory function===

	{{~~fillin~~}}		The summatory function of this function is termed the [[divisor sum summatory function]], and is defined as:

			<math>x \mapsto \sum_{n \le x} \sigma(n)</math>.

			It is equivalent to the following:

			<math>\sum_{d \le x} d\left[\frac{x}{d}\right]</math>.

			In other words, it is the sum, over all numbers less than or equal to <math>x</math>, of the largest multiple of that number less than or equal to <math>x</math>. Note that this summatory function is bounded from above by <math>x^2</math> and from below by <math>x^2/2</math>.

			===Average value===

			Given any positive real <math>x</math>, consider the ratio:

			<math>\frac{\sum_{n \le x} \sigma(n)}{\sum_{n \le x} n}</math>.

			This ratio is bounded from below by <math>1</math> and from above by <math>2</math>.

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

			===Generalizations===

			* [[Divisor power sum function]] <math>\sigma_k</math> is the sum of the <math>k^{th}</math> powers of all the positive divisors. The divisor sum function is the divisor power sum function <math>\sigma_1</math>. Also related is the [[divisor count function]] <math>\sigma_0</math>, which is also denoted <math>d</math> or <math>\tau</math>.

	===Relations expressed in terms of Dirichlet products===		===Relations expressed in terms of Dirichlet products===
Line 55:		Line 85:
	* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all ones function]].		* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all ones function]].
	* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.		* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.
	* <math>\sigma * \~~phi~~ = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.		* <math>\sigma * \varphi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.

	==Relation with properties of numbers==		==Relation with properties of numbers==

			* [[Prime number]]: A natural number <math>n</math> such that <math>\sigma(n) = n + 1</math>.
	* [[Perfect number]]: A natural number <math>n</math> such that <math>\sigma(n) = 2n</math>.		* [[Perfect number]]: A natural number <math>n</math> such that <math>\sigma(n) = 2n</math>.
			* [[Quasiperfect number]]: A natural number <math>n</math> such that <math>\sigma(n) = 2n + 1</math>.
	* [[Abundant number]]: A natural number <math>n</math> such that <math>\sigma(n) > 2n</math>.		* [[Abundant number]]: A natural number <math>n</math> such that <math>\sigma(n) > 2n</math>.
	* [[Deficient number]]: A natural number <math>n</math> such that <math>\sigma(n) < 2n</math>.		* [[Deficient number]]: A natural number <math>n</math> such that <math>\sigma(n) < 2n</math>.
Line 65:		Line 97:

	==Properties==		==Properties==
	~~<math>\sigma</math> is a [[~~multiplicative ~~function]] but~~ not ~~a [[~~completely multiplicative ~~function]].~~
			{{multiplicative}}

			{{not completely multiplicative}}

Vipul at 22:22, 2 May 2009

2009-05-02T22:22:48Z

← Older revision		Revision as of 22:22, 2 May 2009
Line 7:		Line 7:
	# <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] <math>E</math> on the natural numbers and the [[all-one function]] <math>U</math>: the function sending every natural number to <math>1</math>.		# <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] <math>E</math> on the natural numbers and the [[all-one function]] <math>U</math>: the function sending every natural number to <math>1</math>.
	# We have <math>\sigma(n) = \sum_{d\|n} d</math>.		# We have <math>\sigma(n) = \sum_{d\|n} d</math>.

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

Line 17:		Line 16:

	<math>\sigma(n) = \prod_{i=1}^r \left(\frac{p_i^{k_i + 1} - 1}{p_i - 1}\right)</math>.		<math>\sigma(n) = \prod_{i=1}^r \left(\frac{p_i^{k_i + 1} - 1}{p_i - 1}\right)</math>.

			Equivalently, the ratio is given by:

			<math>\frac{\sigma(n)}{n} = \prod_{i=1}^r \left(\frac{1 - (1/p_i^{k_i + 1})}{1 - 1/p_i}\right)</math>.

	==Behavior==		==Behavior==
Line 33:		Line 36:

	===Upper bound===		===Upper bound===

			[[Gronwall's theorem]] asserts that:

			<math>\lim\sup_{n \to \infty} \frac{\sigma(n)}{n \log \log n} = e^\gamma</math>

			where all the logarithms are [[natural logarithm]]s and <math>\gamma</math> is the [[Euler-Mascheroni constant]].

			A closely related result is [[Robin's theorem]], which states that the [[Riemann hypothesis]] is equivalent to the statement that for <math>n \ge 5041</math>, the ratio is always strictly ''less'' than <math>e^{\gamma}</math>.

			===Summatory function===

	{{fillin}}		{{fillin}}

Vipul: /* Relation with other arithmetic functions */

2009-05-02T22:09:52Z

Relation with other arithmetic functions

← Older revision		Revision as of 22:09, 2 May 2009
Line 40:		Line 40:
	===Relations expressed in terms of Dirichlet products===		===Relations expressed in terms of Dirichlet products===

	* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all~~-one~~ function]].		* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all ones function]].
	* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.		* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.
	* <math>\sigma * \phi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.		* <math>\sigma * \phi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.

Vipul at 02:59, 29 April 2009

2009-04-29T02:59:46Z

← Older revision		Revision as of 02:59, 29 April 2009
Line 22:		Line 22:
	===Lower bound===		===Lower bound===

	~~The divisor sum function takes its lowest values~~ (~~in relative terms~~) ~~at primes~~. <math>\sigma(p) = ~~p +~~ 1</math> ~~for any prime number~~ <math>p</math>.		For any <math>n > 1</math>, <math>\sigma(n) \ge n + 1</math>. Equality is achieved if and only if <math>n</math> is prime. Further, <math>\sigma(n)</math> is the lowest, in relative terms, for primes. In particular, excluding the case <math>n = 1</math>, the fraction <math>\sigma(n)/n</math> achieves a [[strict minimum-so-far]] at every prime, and nowhere else.

	Thus, we have:		Thus, we have:
Line 49:		Line 49:
	* [[Abundant number]]: A natural number <math>n</math> such that <math>\sigma(n) > 2n</math>.		* [[Abundant number]]: A natural number <math>n</math> such that <math>\sigma(n) > 2n</math>.
	* [[Deficient number]]: A natural number <math>n</math> such that <math>\sigma(n) < 2n</math>.		* [[Deficient number]]: A natural number <math>n</math> such that <math>\sigma(n) < 2n</math>.
			* [[Superabundant number]]: A natural number <math>n</math> that is a [[strict maximum-so-far]] for <math>\sigma(n)/n</math>.

	==Properties==		==Properties==
	<math>\sigma</math> is a [[multiplicative function]] but not a [[completely multiplicative function]].		<math>\sigma</math> is a [[multiplicative function]] but not a [[completely multiplicative function]].

Vipul at 00:13, 29 April 2009

2009-04-29T00:13:04Z

← Older revision		Revision as of 00:13, 29 April 2009
Line 17:		Line 17:

	<math>\sigma(n) = \prod_{i=1}^r \left(\frac{p_i^{k_i + 1} - 1}{p_i - 1}\right)</math>.		<math>\sigma(n) = \prod_{i=1}^r \left(\frac{p_i^{k_i + 1} - 1}{p_i - 1}\right)</math>.

			==Behavior==

			===Lower bound===

			The divisor sum function takes its lowest values (in relative terms) at primes. <math>\sigma(p) = p + 1</math> for any prime number <math>p</math>.

			Thus, we have:

			<math>\lim_{n \to \infty} \sigma(n) \to \infty</math>,

			and:

			<math>\lim\inf_{n \to \infty} \frac{\sigma(n)}{n} = 1</math>,

			===Upper bound===

			{{fillin}}

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

Vipul: /* Relation with other arithmetic functions */

2009-04-22T19:17:06Z

Relation with other arithmetic functions

← Older revision		Revision as of 19:17, 22 April 2009
Line 24:		Line 24:
	* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all-one function]].		* <math>\sigma = E * U</math>: <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] and the [[all-one function]].
	* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.		* <math>\sigma * \mu = E</math>: The Dirichlet product of <math>\sigma</math> and the [[Mobius function]] is the [[identity function]]. Note that this is the [[Mobius inversion formula applied to the previous statement; equivalently, it is obtained by multiplying both sides of the previous equation by <math>\mu</math>.
			* <math>\sigma * \phi = E * E</math>: The Dirichlet product of <math>\sigma</math> and the [[Euler phi-function]] equals the Dirichlet product of the [[identity function]] with itself, which in turn is the (pointwise) product of the identity function and the divisor count function.

	==Relation with properties of numbers==		==Relation with properties of numbers==

Vipul at 17:29, 22 April 2009

2009-04-22T17:29:07Z

@@ Line 5: / Line 5: @@
 Let <math>n</math> be a [[natural number]]. The '''divisor sum function''' of <math>n</math>, denoted <math>\sigma(n)</math>, is defined in the following equivalent ways:
-# <math>\sigma</math> is the Dirichlet product of the [[identity function]] on the natural numbers and the [[all-one function]]: the function sending every natural number to <math>1</math>.
+# <math>\sigma</math> is the [[Dirichlet product]] of the [[identity function]] <math>E</math> on the natural numbers and the [[all-one function]] <math>U</math>: the function sending every natural number to <math>1</math>.
 # We have <math>\sigma(n) = \sum_{d|n} d</math>.
 <math>\sigma</math> is a [[multiplicative function]] but not a [[completely multiplicative function]].