Divisor function: Difference between revisions

Revision as of 12:58, 21 January 2023

Latest revision as of 15:10, 30 April 2025

(14 intermediate revisions by 12 users not shown)

Line 2:

{{short description|Arithmetic function related to the divisors of an integer}}

[[Image:Divisor.svg|thumb|right|Divisor function ''σ''₀(''n'') up to ''n'' = 250]]

[[Image:Sigma function.svg|thumb|right|Sigma function ''σ''₁(''n'') up to ''n'' = 250]]

[[Image:Divisor square.svg|thumb|right|Sum of the squares of divisors, ''σ''₂(''n''), up to ''n'' = 250]]

[[Image:Divisor cube.svg|thumb|right|Sum of cubes of divisors, ''σ''₃(''n'') up to ''n'' = 250]]

In [[mathematics]], and specifically in [[number theory]], a '''divisor function''' is an [[arithmetic function]] related to the [[divisor]]s of an [[integer]]. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (including 1 and the number itself). It appears in a number of remarkable identities, including relationships on the [[Riemann zeta function]] and the [[Eisenstein series]] of [[modular form]]s. Divisor functions were studied by [[Ramanujan]], who gave a number of important [[Modular arithmetic|congruences]] and [[identity (mathematics)|identities]]; these are treated separately in the article [[Ramanujan's sum]].

Line 11:

==Definition==

The '''sum of positive divisors function''' ''σ''_''z''(''n''), for a real or complex number ''z'', is defined as the [[summation|sum]] of the ''z''th [[Exponentiation|powers]] of the positive [[divisor]]s of ''n''. It can be expressed in [[Summation#Capital-sigma notation|sigma notation]] as

:<math>\sigma_z(n)=\sum_{d\mid n} d^z\,\! ,</math>

where <math>{d\mid n}</math> is shorthand for "''d'' [[divides]] ''n''".

The notations ''d''(''n''), ''ν''(''n'') and ''τ''(''n'') (for the German ''Teiler'' = divisors) are also used to denote ''σ''₀(''n''), or the '''number-of-divisors function'''<ref name="Long 1972 46">{{harvtxt|Long|1972|p=46}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=63}}</ref> ({{OEIS2C|id=A000005}}). When ''z'' is 1, the function is called the '''sigma function''' or '''sum-of-divisors function''',<ref name="Long 1972 46"/><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=58}}</ref> and the subscript is often omitted, so ''σ''(''n'') is the same as ''σ''₁(''n'') ({{OEIS2C|id=A000203}}).

The '''[[aliquot sum]]''' ''s''(''n'') of ''n'' is the sum of the [[proper divisor]]s (that is, the divisors excluding ''n'' itself, {{OEIS2C|id=A001065}}), and equals ''σ''₁(''n'')&nbsp;&minus;&nbsp;''n''; the [[aliquot sequence]] of ''n'' is formed by repeatedly applying the aliquot sum function.

==Example==

For example, ''σ''₀(12) is the number of the divisors of 12:

: <math>

\begin{align}

\sigma_{0}sigma_0(12) & = 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 \\

& = 1 + 1 + 1 + 1 + 1 + 1 = 6,

\end{align}

</math>

while ''σ''₁(12) is the sum of all the divisors:

: <math>

\begin{align}

\sigma_{1}sigma_1(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 + 12^1 \\

& = 1 + 2 + 3 + 4 + 6 + 12 = 28,

\end{align}

Line 48:

</math>

''σ''_-1−1(''n'') is sometimes called the [[abundancy index]] of ''n'', and we have:

: <math>

\begin{align}

\sigma_{-1}(12) & = 1^{-1} + 2^{-1} + 3^{-1} + 4^{-1} + 6^{-1} + 12^{-1} \\[6pt]

& = \tfrac11 + \tfrac12 + \tfrac13 + \tfrac14 + \tfrac16 + \tfrac1{12} \\[6pt]

& = \tfrac{12}{12} + \tfrac6{12} + \tfrac4{12} + \tfrac3{12} + \tfrac2{12} + \tfrac1{12} \\[6pt]

& = \tfrac{12 + 6 + 4 + 3 + 2 + 1}{12} = \tfrac{28}{12} = \tfrac73 = \tfrac{\sigma_1(12)}{12}

\end{align}

Line 60:

==Table of values==

The cases ''x'' = 2 to 5 are listed in {{OEIS2C|A001157}} −through {{OEIS2C|A001160}}, ''x'' = 6 to 24 are listed in {{OEIS2C|A013954}} −through {{OEIS2C|A013972}}.

{| class="wikitable" style="text-align:right; float:left"

! ''n'' !! prime factorization !! {{sigma}}₀(''n'')!! {{sigma}}₁(''n'')!! {{sigma}}₂(''n'')!! {{sigma}}₃(''n'')!! {{sigma}}₄(''n'')

|-

| 1||style='text-align:center;'| 1|| 1|| 1|| 1|| 1|| 1

Line 191:

| title = Highly Composite Numbers

| volume = s2-14

| year = 1915| url = https://zenodo.org/record/1433496 }}; see section 47, pp. 405–406, reproduced in ''Collected Papers of Srinivasa Ramanujan'', Cambridge Univ. Press, 2015, [https://books.google.com/books?id=h1G2CgAAQBAJ&pg=PA124 pp. 124–125]</ref>

Clearly, <math>1 < \sigma_0(n) < n</math> for all <math>n > 2</math>, and <math>\sigma_x(n) > n </math> for all <math>n > 1</math>, <math>x > 0</math> .

Line 211:

:<math>\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}.</math>

When ''x''&nbsp;=&nbsp;0, ''d''<math>\sigma_0(''n'')</math> is: {{sfnp|Hardy|Wright|2008|pp=310 f|loc=§16.7}}

:<math>\sigma_0(n)=\prod_{i=1}^r (a_i+1).</math>

Line 217:

This result can be directly deduced from the fact that all divisors of <math>n</math> are uniquely determined by the distinct tuples <math>(x_1, x_2, ..., x_i, ..., x_r)</math> of integers with <math>0 \le x_i \le a_i</math> (i.e. <math>a_i+1</math> independent choices for each <math>x_i</math>).

For example, if ''n'' is 24, there are two prime factors (''p''₁'' is 2; ''p''₂'' is 3); noting that 24 is the product of 2³×3¹, ''a''₁ is 3 and ''a''₂ is 1. Thus we can calculate <math>\sigma_0(24)</math> as so:

: <math>\sigma_0(24) = \prod_{i=1}^{2} (a_i+1) = (3 + 1)(1 + 1) = 4 \cdot 2 = 8.</math>

Line 227:

:<math>\begin{align}

\sigmasigma_1(n) &= \sigmasigma_1(n-1)+\sigmasigma_1(n-2)-\sigmasigma_1(n-5)-\sigmasigma_1(n-7)+\sigmasigma_1(n-12)+\sigmasigma_1(n-15)+ \cdots \\[12mu]

&= \sum_{i\in\N} (-1)^{i+1}\left( \sigmasigma_1 \left( n-\frac{1}{2} \left( 3i^2-i \right) \right) + \sigmasigma_1 \left( n-\frac{1}{2} \left( 3i^2+i \right) \right) \right),

\end{align}</math>

where <math>\sigmasigma_1(0)=n</math> if it occurs and <math>\sigmasigma_1(x)=0</math> for <math>x < 0</math>, and <math>\tfrac{1}{2} \left( 3i^2 \mp i \right)</math> are consecutive pairs of generalized [[pentagonal numbers]] ({{OEIS2C|A001318}}, starting at offset 1). Indeed, Euler proved this by logarithmic differentiation of the identity in his [[Pentagonalpentagonal number theorem]].

For a non-square integer, ''n'', every divisor, ''d'', of ''n'' is paired with divisor ''n''/''d'' of ''n'' and <math>\sigma_{0}(n)</math> is even; for a square integer, one divisor (namely <math>\sqrt n</math>) is not paired with a distinct divisor and <math>\sigma_{0}(n)</math> is odd. Similarly, the number <math>\sigma_{1}(n)</math> is odd if and only if ''n'' is a square or twice a square.{{sfnp|Gioia|Vaidya|1967}}

Line 271:

is true for infinitely many values of {{mvar|n}}, see {{OEIS2C|A005237}}.

=== Dirichlet convolutions ===

{{Main article|Dirichlet convolution}}

By definition:<math display="block">\sigma = \operatorname{Id} * \mathbf 1</math>By [[Möbius inversion formula|Möbius inversion]]:<math display="block">\operatorname{Id} = \sigma * \mu </math>

==Series relations==

Line 289 ⟶ 293:

A [[Lambert series]] involving the divisor function is: {{sfnp|Hardy|Wright|2008|pp=338-341|loc=§17.10}}

:<math>\sum_{n=1}^\infty q^n \sigma_a(n) = \sum_{n=1}^\infty \sum_{j=1}^\infty n^a q^{j\,n} = \sum_{n=1}^\infty \frac{n^a q^n}{1-q^n} = \sum_{n=1}^\infty \operatorname{Li}_{-a}(q^n)</math>

for arbitrary [[complex number|complex]] |''q''|&nbsp;≤&nbsp;1 and&nbsp;''a'' (<math>\operatorname{Li}</math> is the [[polylogarithm]]). This summation also appears as the [[Eisenstein series#Fourier series|Fourier series of the Eisenstein series]] and the [[Weierstrass elliptic functions#Invariants|invariants of the Weierstrass elliptic functions]].

For <math>k>0</math>, there is an explicit series representation with [[Ramanujan sum]]s <math> c_m(n) </math> as :<ref>{{cite book |author=E. Krätzel |title=Zahlentheorie |publisher=VEB Deutscher Verlag der Wissenschaften |place =Berlin |year=1981 |pages=130}} (German)</ref>

Line 317 ⟶ 321:

</math>

where lim sup is the [[limit superior]]. This result is '''[[Thomas Hakon Grönwall|Grönwall]]'s theorem''', published in 1913 {{harv|Grönwall|1913}}. His proof uses [[Mertens' theorems|Mertens' 3rdthird theorem]], which says that:

:<math>\lim_{n\to\infty}\frac{1}{\log n}\prod_{p\le n}\frac{p}{p-1}=e^\gamma,</math>

Line 325 ⟶ 329:

In 1915, Ramanujan proved that under the assumption of the [[Riemann hypothesis]], Robin's inequality

:<math>\ \sigma(n) < e^\gamma n \log \log n </math> (where γ is the [[Euler–Mascheroni constant]])

holds for all sufficiently large ''n'' {{harv|Ramanujan|1997}}. The largest known value that violates the inequality is ''n''=[[5040 (number)|5040]]. In 1984, [[Guy Robin]] proved that the inequality is true for all ''n'' > 5040 [[if and only if]] the Riemann hypothesis is true {{harv|Robin|1984}}. This is '''Robin's theorem''' and the inequality became known after him. Robin furthermore showed that if the Riemann hypothesis is false then there are an infinite number of values of ''n'' that violate the inequality, and it is known that the smallest such ''n'' > 5040 must be [[superabundant number|superabundant]] {{harv|Akbary|Friggstad|2009}}. It has been shown that the inequality holds for large odd and square-free integers, and that the Riemann hypothesis is equivalent to the inequality just for ''n'' divisible by the fifth power of a prime {{Harv|Choie|Lichiardopol|Moree|Solé|2007}}.

Robin also proved, unconditionally, that the inequality:

Line 361 ⟶ 365:

| title = Amicable numbers with opposite parity

| volume = 74

| year = 1967}}| issue = 8

}}

* {{Citation | last1=Grönwall | first1=Thomas Hakon | author1-link=Thomas Hakon Grönwall | title=Some asymptotic expressions in the theory of numbers | year=1913 | journal=Transactions of the American Mathematical Society | volume=14 | issue=1 | pages=113–122 | doi=10.1090/S0002-9947-1913-1500940-6| doi-access=free }}

* {{Citation | last1=Hardy | first1=G. H. | author1-link=G. H. Hardy | last2=Wright | first2=E. M. | author2-link=E. M. Wright | edition=6th | others=Revised by [[Roger Heath-Brown|D. R. Heath-Brown]] and [[Joseph H. Silverman|J. H. Silverman]]. Foreword by [[Andrew Wiles]]. | title=An Introduction to the Theory of Numbers | publisher=[[Oxford University Press]] | ___location=Oxford | isbn=978-0-19-921986-5 | mr=2445243 | zbl=1159.11001 | year=2008 | orig-year=1938}}

* {{citation | last=Ivić | first=Aleksandar | title=The Riemann zeta-function. The theory of the Riemann zeta-function with applications | series=A Wiley-Interscience Publication | ___location=New York etc. | publisher=John Wiley & Sons | year=1985 | isbn=0-471-80634-X | zbl=0556.10026 | pages=385–440 }}