Divisor function: Difference between revisions

Revision as of 13:58, 20 August 2021

Latest revision as of 15:10, 30 April 2025

(36 intermediate revisions by 29 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''' ''σ''_''xz''(''n''), for a real or complex number ''xz'', is defined as the [[summation|sum]] of the ''xz''th [[Exponentiation|powers]] of the positive [[divisor]]s of ''n''. It can be expressed in [[Summation#Capital-sigma notation|sigma notation]] as

:<math>\sigma_xsigma_z(n)=\sum_{d\mid n} d^xz\,\! ,</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 ''xz'' 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 45:

s(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 \\

& = 1 + 2 + 3 + 4 + 6 = 16.

\end{align}

</math>

''σ''₋₁(''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}

</math>

==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:leftright; 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 172 ⟶ 183:

:<math> \sigma_0(p_n\#) = 2^n </math>

since ''n'' prime factors allow a sequence of binary selection (<math>p_{i}</math> or 1) from ''n'' terms for each proper divisor formed. However, these are not in general the smallest numbers whose number of divisors is a [[power of two]]; instead, the smallest such number may be obtained by multiplying together the first ''n'' [[Fermi–Dirac prime]]s, prime powers whose exponent is a power of two.<ref>{{citation

| last = Ramanujan | first = S. | author-link = Srinivasa Ramanujan

| doi = 10.1112/plms/s2_14.1.347

| issue = 1

| journal = Proceedings of the London Mathematical Society

| pages = 347–409

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

The divisor function is [[multiplicative function|multiplicative]],{{Why|date=May 2021|reason=the(since each divisor function''c'' of the product doesn't'mn'' seemwith obviously<math>\gcd(m, multiplicative.n) = What1</math> isdistinctively thecorrespond proofto sketch?}}a divisor ''a'' of ''m'' and a divisor ''b'' of ''n''), but not [[Completely multiplicative function|completely multiplicative]]:

:<math>\gcd(a, b)=1 \Longrightarrow \sigma_x(ab)=\sigma_x(a)\sigma_x(b).</math>

Line 192 ⟶ 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>

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:

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 203 ⟶ 224:

===Other properties and identities===

[[Euler]] proved the remarkable recurrence:<ref>{{Cite arXiv |eprint = math/0411587|last1 = Euler|first1 = Leonhard|title = An observation on the sums of divisors|last2 = Bell|first2 = Jordan|year = 2004}}</ref><ref>httphttps://eulerarchivescholarlycommons.maapacific.orgedu/euler-works/pages175/E175.html, ''DecouverteDécouverte d'une loi tout extraordinaire des nombres par rapport aà la somme de leurs diviseurs''</ref><ref>https://scholarlycommons.pacific.edu/euler-works/542/, ''De mirabilis proprietatibus numerorum pentagonalium''</ref>

:<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\ZN} (-1)^{i+1}\left( \sigmasigma_1 \left ( n-\frac12frac{1}{2} \left ( 3i^2-i \right ) \right ) + \sigmasigma_1 \left (n n-\frac12frac{1}{2} \left ( 3i^2+i \right ) \right ) \right),

\end{align}</math>

where we set <math>\sigmasigma_1(0)=n</math> if it occurs and <math>\sigmasigma_1(ix)=0</math> for <math>ix \leq< 0,</math>, and <math>\tfrac12tfrac{1}{2} \left ( 3i^2- \mp i \right )</math> are theconsecutive 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.{{Citation neededsfnp|date=May 2015Gioia|Vaidya|1967}}

We also note ''s''(''n'') = ''σ''(''n'')&nbsp;−&nbsp;''n''. Here ''s''(''n'') denotes the sum of the ''proper'' divisors of ''n'', that is, the divisors of ''n'' excluding ''n'' itself. This function is the one used to recognize [[perfect number]]s, which are the ''n'' forsuch whichthat ''s''(''n'') =&nbsp;''n''. If ''s''(''n'') > ''n'', then ''n'' is an [[abundant number]], and if ''s''(''n'') < ''n'', then ''n'' is a [[deficient number]].

If {{mvar|n}} is a power of 2, for example, <math>n = 2^k</math>, then <math>\sigma(n) = 2 \cdot 2^k - 1 = 2n - 1,</math> and ''<math>s(n) = n - 1''</math>, which makes ''n'' [[Almost perfect number|almost-perfect]].

As an example, for two distinct primes ''<math>p'' and '',q'' with '':p < q''</math>, let

:<math>n = pq. p\,q</math>.

Then

:<math>\sigma(n) = (p+1)(q+1) = n + 1 + (p+q), </math>

:<math>\varphi(n) = (p-1)(q-1) = n + 1 - (p+q), </math>

Line 234 ⟶ 255:

where <math>\varphi(n)</math> is [[Euler phi|Euler's totient function]].

Then, the roots of:

:<math>(x-p)(x-q) = x^2 - (p+q)x + n = x^2 - [(\sigma(n) - \varphi(n))/2]x + [(\sigma(n) + \varphi(n))/2 - 1] = 0 </math>

allow us to express ''p'' and ''q'' in terms of ''σ''(''n'') and ''φ''(''n'') only, withoutrequiring evenno knowingknowledge of ''n'' or ''<math>p+q''</math>, as:

:<math>p = (\sigma(n) - \varphi(n))/4 - \sqrt{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}, </math>

:<math>q = (\sigma(n) - \varphi(n))/4 + \sqrt{[(\sigma(n) - \varphi(n))/4]^2 - [(\sigma(n) + \varphi(n))/2 - 1]}. </math>

Also, knowing {{mvar|n}} and either <math>\sigma(n)</math> or <math>\varphi(n)</math>, (or, knowingalternatively, <math>p+q</math> and either <math>\sigma(n)</math> or <math>\varphi(n)</math>) allows usan toeasy easilyrecovery findof ''p'' and ''q''.

In 1984, [[Roger Heath-Brown]] proved that the equality

Line 249 ⟶ 270:

:<math>\sigma_0(n) = \sigma_0(n + 1)</math>

is true for aninfinitely infinity ofmany 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 256 ⟶ 281:

:<math>\sum_{n=1}^\infty \frac{\sigma_{a}(n)}{n^s} = \zeta(s) \zeta(s-a)\quad\text{for}\quad s>1,s>a+1,</math>

whichwhere <math>\zeta</math> is the [[Riemann zeta function]]. The series for ''d''(''n'')&nbsp;=&nbsp;''&sigma;''₀(''n'') gives: {{sfnp|Hardy|Wright|2008|pp=326-328|loc=§17.5}}

: <math>\sum_{n=1}^\infty \frac{d(n)}{n^s} = \zeta^2(s)\quad\text{for}\quad s>1,</math>

Line 268 ⟶ 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>, existsthere 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>

:<math>\sigma_k(n) = \zeta(k+1)n^k\sum_{m=1}^\infty \frac {c_m(n)}{m^{k+1}}.</math>

The computation of the first terms of <math>c_m(n)</math> shows its oscillations around the "average value" <math>\zeta(k+1)n^k</math>:

Line 296 ⟶ 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 302 ⟶ 327:

where ''p'' denotes a prime.

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

:<math>\ \sigma(n) < e^\gamma n \log \log n </math> (Robin'swhere inequalityγ 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 311 ⟶ 336:

A related bound was given by [[Jeffrey Lagarias]] in 2002, who proved that the Riemann hypothesis is equivalent to the statement that:

:<math> \sigma(n) < H_n + \log(H_n)e^{H_n}\log(H_n)</math>

for every [[natural number]] ''n'' &gt; 1, where <math>H_n</math> is the ''n''th [[harmonic number]], {{harv|Lagarias|2002}}.

Line 330 ⟶ 355:

* {{Citation | last1=Caveney | first1=Geoffrey | last2=Nicolas | first2=Jean-Louis|author2-link=Jean-Louis Nicolas | last3=Sondow | first3=Jonathan | title=Robin's theorem, primes, and a new elementary reformulation of the Riemann Hypothesis | url=http://www.integers-ejcnt.org/l33/l33.pdf | year=2011 | journal=INTEGERS: The Electronic Journal of Combinatorial Number Theory | volume=11 | pages=A33| bibcode=2011arXiv1110.5078C | arxiv=1110.5078 }}

*{{Citation | last1=Choie | first1=YoungJu | author1-link= YoungJu Choie | last2=Lichiardopol | first2=Nicolas | last3=Moree | first3=Pieter | author3-link=Pieter Moree | last4=Solé | first4=Patrick | title=On Robin's criterion for the Riemann hypothesis | mr=2394891 | zbl=1163.11059 | arxiv=math.NT/0604314 | year=2007 | journal=Journal de théorie des nombres de Bordeaux | issn=1246-7405 | volume=19 | issue=2 | pages=357–372 | doi=10.5802/jtnb.591| s2cid=3207238 }}

*{{citation

* {{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 | pages=113–122 | doi=10.1090/S0002-9947-1913-1500940-6| doi-access=free }}

| last1 = Gioia | first1 = A. A.

| last2 = Vaidya | first2 = A. M.

| doi = 10.2307/2315280

| journal = [[The American Mathematical Monthly]]

| jstor = 2315280

| mr = 220659

| pages = 969–973

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