Funkce dělitele - Divisor function

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Leden 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Funkce dělitele σ₀(n) až do n = 250

Funkce sigma σ₁(n) až do n = 250

Součet čtverců dělitelů, σ₂(n), až do n = 250

Součet kostek dělitelů, σ₃(n) až do n = 250

v matematika a konkrétně v teorie čísel, a funkce dělitele je aritmetická funkce související s dělitele z celé číslo. Když se označuje jako the funkce dělitele, počítá počet dělitelů celého čísla (včetně 1 a samotného čísla). Objevuje se v řadě pozoruhodných identit, včetně vztahů na internetu Funkce Riemann zeta a Eisensteinova řada z modulární formy. Funkce dělitele byly studovány uživatelem Ramanujan, který uvedl řadu důležitých shody a identity; tyto jsou v článku zpracovány samostatně Ramanujanova suma.

Související funkcí je funkce součtu dělitele, což, jak název napovídá, je součtem nad funkcí dělitele.

Definice

The součet funkce kladných dělitelů σ_X(n), pro reálné nebo komplexní číslo X, je definován jako součet z Xth pravomoci pozitivního dělitele z n. Může být vyjádřeno v sigma notace tak jako

${ displaystyle sigma _ {x} (n) = součet _ {d mid n} d ^ {x} , !,}$

kde ${ displaystyle {d mid n}}$ je zkratka pro „d rozděluje n". Zápisy d(n), ν (n) a τ (n) (pro Němce Teiler = dělitele) se také používají k označení σ₀(n), nebo funkce počtu dělitelů^[1][2] (OEIS: A000005). Když X je 1, funkce se nazývá funkce sigma nebo funkce součtu dělitelů,^[1][3] a dolní index je často vynechán, takže σ (n) je stejné jako σ₁(n) (OEIS: A000203).

The alikvotní částka s(n) z n je součet řádní dělitelé (tj. dělitelé s výjimkou n sám, OEIS: A001065) a rovná se σ₁(n) − n; the alikvotní sekvence z n je tvořen opakovaným použitím funkce alikvotního součtu.

Příklad

Například σ₀(12) je počet dělitelů 12:

${ displaystyle { begin {aligned} sigma _ {0} (12) & = 1 ^ {0} + 2 ^ {0} + 3 ^ {0} + 4 ^ {0} + 6 ^ {0} + 12 ^ {0} & = 1 + 1 + 1 + 1 + 1 + 1 = 6, end {zarovnáno}}}$

zatímco σ₁(12) je součet všech dělitelů:

${ displaystyle { begin {aligned} sigma _ {1} (12) & = 1 ^ {1} + 2 ^ {1} + 3 ^ {1} + 4 ^ {1} + 6 ^ {1} + 12 ^ {1} & = 1 + 2 + 3 + 4 + 6 + 12 = 28, end {zarovnáno}}}$

a alikvotní součet s (12) správných dělitelů je:

${ displaystyle { begin {aligned} s (12) & = 1 ^ {1} + 2 ^ {1} + 3 ^ {1} + 4 ^ {1} + 6 ^ {1} & = 1+ 2 + 3 + 4 + 6 = 16. End {zarovnáno}}}$

Tabulka hodnot

Případy X = 2 až 5 jsou uvedeny v OEIS: A001157 − OEIS: A001160, X = 6 až 24 je uvedeno v OEIS: A013954 − OEIS: A013972.

Vlastnosti

Vzorce v hlavních silách

Pro prvočíslo p,

${ displaystyle { begin {aligned} sigma _ {0} (p) & = 2 sigma _ {0} (p ^ {n}) & = n + 1 sigma _ {1} ( p) & = p + 1 end {zarovnáno}}}$

protože podle definice jsou faktory prvočísla 1 a samy o sobě. Také kde p_n# označuje primitivní,

${ displaystyle sigma _ {0} (p_ {n} #) = 2 ^ {n}}$

od té doby n primární faktory umožňují posloupnost binárního výběru (${ displaystyle p_ {i}}$ nebo 1) z n podmínky pro každého vytvořeného správného dělitele.

Jasně, ${ displaystyle 1 < sigma _ {0} (n)$ a σ (n) > n pro všechnyn > 2.

Funkce dělitele je multiplikativní, ale ne zcela multiplikativní:

${ displaystyle gcd (a, b) = 1 Longrightarrow sigma _ {x} (ab) = sigma _ {x} (a) sigma _ {x} (b).}$

Důsledkem toho je, že pokud budeme psát

${ displaystyle n = prod _ {i = 1} ^ {r} p_ {i} ^ {a_ {i}}}$

kde r = ω(n) je počet odlišných hlavních faktorů z n, p_i je ith hlavní faktor, a A_i je maximální výkon p_i kterými n je dělitelný, pak máme: ^[4]

${ displaystyle sigma _ {x} (n) = prod _ {i = 1} ^ {r} součet _ {j = 0} ^ {a_ {i}} p_ {i} ^ {jx} = prod _ {i = 1} ^ {r} left (1 + p_ {i} ^ {x} + p_ {i} ^ {2x} + cdots + p_ {i} ^ {a_ {i} x} že jo).}$

který, když X ≠ 0, je ekvivalentní užitečnému vzorci: ^[4]

${ displaystyle sigma _ {x} (n) = prod _ {i = 1} ^ {r} { frac {p_ {i} ^ {(a_ {i} +1) x} -1} {p_ {i} ^ {x} -1}}.}$

Když X = 0, d(n) je: ^[4]

${ displaystyle sigma _ {0} (n) = prod _ {i = 1} ^ {r} (a_ {i} +1).}$

Například pokud n je 24, existují dva hlavní faktory (p₁ je 2; p₂ je 3); konstatuje, že 24 je produktem 2³×3¹, A₁ je 3 a A₂ je 1. Můžeme tedy vypočítat ${ displaystyle sigma _ {0} (24)}$ jako tak:

${ displaystyle sigma _ {0} (24) = prod _ {i = 1} ^ {2} (a_ {i} +1) = (3 + 1) (1 + 1) = 4 cdot 2 = 8.}$

Osm dělitelů počítaných tímto vzorcem je 1, 2, 4, 8, 3, 6, 12 a 24.

Další vlastnosti a identity

Euler prokázala pozoruhodnou recidivu:^[5][6][7]

${ displaystyle { start {zarovnáno} sigma (n) & = sigma (n-1) + sigma (n-2) - sigma (n-5) - sigma (n-7) + sigma (n-12) + sigma (n-15) + cdots & = sum _ {i in mathbb {Z}} (- 1) ^ {i + 1} left ( sigma left (n - { frac {1} {2}} left (3i ^ {2} -i right) right) + delta left (n, { frac {1} {2}} left ( 3i ^ {2} -i doprava) doprava) n doprava) konec {zarovnáno}}}$

kde jsme nastavili ${ displaystyle sigma (0) = n}$ pokud k němu dojde a ${ displaystyle sigma (i) = 0}$ pro ${ displaystyle i leq 0,}$, používáme Kroneckerova delta ${ displaystyle delta ( cdot, cdot),}$ a ${ displaystyle { tfrac {1} {2}} vlevo (3i ^ {2} -i vpravo)}$ jsou pětiboká čísla. Euler to skutečně dokázal logaritmickou diferenciací identity ve své Věta o pětiúhelníku.

Pro jiné než čtvercové číslo, n, každý dělitel, d, z n je spárován s dělitelem n/d z n a ${ displaystyle sigma _ {0} (n)}$ je sudý; pro čtvercové celé číslo jeden dělitel (jmenovitě ${ displaystyle { sqrt {n}}}$) není spárován s výrazným dělitelem a ${ displaystyle sigma _ {0} (n)}$ je zvláštní. Podobně číslo ${ displaystyle sigma _ {1} (n)}$ je liché právě tehdy n je čtverec nebo dvakrát čtverec.^{[Citace je zapotřebí ]}

Také si povšimneme s(n) = σ(n) − n. Tady s(n) označuje součet správných dělitelů n, tj. dělitele n kromě n sám. Tato funkce slouží k rozpoznávání perfektní čísla které jsou n pro který s(n) = n. Li s(n) > n pak n je hojné číslo a pokud s(n) < n pak n je nedostatečné číslo.

Je-li n například mocninou 2, ${ displaystyle n = 2 ^ {k}}$, pak ${ displaystyle sigma (n) = 2 cdot 2 ^ {k} -1 = 2n-1,}$ a s (n) = n - 1, který dělá n téměř perfektní.

Jako příklad pro dvě odlišná prvočísla p a q s p , nechť

${ displaystyle n = pq.}$

Pak

${ Displaystyle sigma (n) = (p + 1) (q + 1) = n + 1 + (p + q),}$

${ displaystyle varphi (n) = (p-1) (q-1) = n + 1- (p + q),}$

a

${ Displaystyle n + 1 = ( sigma (n) + varphi (n)) / 2,}$

${ Displaystyle p + q = ( sigma (n) - varphi (n)) / 2,}$

kde ${ displaystyle varphi (n)}$ je Eulerova totientová funkce.

Pak kořeny:

${ displaystyle (xp) (xq) = x ^ {2} - (p + q) x + n = x ^ {2} - [( sigma (n) - varphi (n)) / 2] x + [ ( sigma (n) + varphi (n)) / 2-1] = 0}$

dovolte nám vyjádřit p a q ve smyslu σ(n) a φ(n) pouze bez vědomí n nebo p + q, tak jako:

${ displaystyle p = ( sigma (n) - varphi (n)) / 4 - { sqrt {[( sigma (n) - varphi (n)) / 4] ^ {2} - [( sigma (n) + varphi (n)) / 2-1]}},}$

${ displaystyle q = ( sigma (n) - varphi (n)) / 4 + { sqrt {[( sigma (n) - varphi (n)) / 4] ^ {2} - [( sigma (n) + varphi (n)) / 2-1]}}.}$

Také vědět n a buď ${ displaystyle sigma (n)}$ nebo ${ displaystyle varphi (n)}$ (nebo znát p + q a buď ${ displaystyle sigma (n)}$ nebo ${ displaystyle varphi (n)}$) nám umožňuje snadno najít p a q.

V roce 1984 Roger Heath-Brown dokázal, že rovnost

${ displaystyle sigma _ {0} (n) = sigma _ {0} (n + 1)}$

platí pro nekonečno hodnot n, viz OEIS: A005237.

Sériové vztahy

Dva Dirichletova řada zahrnující funkci dělitele jsou: ^[8]

${ displaystyle sum _ {n = 1} ^ { infty} { frac { sigma _ {a} (n)} {n ^ {s}}} = zeta (s) zeta (sa) quad { text {for}} quad s> 1, s> a + 1,}$

který pro d(n) = σ₀(n) dává: ^[8]

${ displaystyle sum _ {n = 1} ^ { infty} { frac {d (n)} {n ^ {s}}} = zeta ^ {2} (s) quad { text {pro }} quad s> 1,}$

a ^[9]

${ displaystyle sum _ {n = 1} ^ { infty} { frac { sigma _ {a} (n) sigma _ {b} (n)} {n ^ {s}}} = { frac { zeta (s) zeta (sa) zeta (sb) zeta (sab)} { zeta (2s-ab)}}.}$

A Lambertova řada zahrnující funkci dělitele je: ^[10]

${ displaystyle 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}}}}$

pro libovolné komplex |q| ≤ 1 aA. Tento součet se také jeví jako Fourierova řada řady Eisenstein a invarianty Weierstrassových eliptických funkcí.

Pro ${ displaystyle k> 0}$ existuje explicitní reprezentace řady s Ramanujanské částky ${ displaystyle c_ {m} (n)}$ tak jako :^[11]

${ displaystyle sigma _ {k} (n) = zeta (k + 1) n ^ {k} součet _ {m = 1} ^ { infty} { frac {c_ {m} (n)} {m ^ {k + 1}}}.}$

Výpočet prvních podmínek ${ displaystyle c_ {m} (n)}$ ukazuje své oscilace kolem "průměrné hodnoty" ${ displaystyle zeta (k + 1) n ^ {k}}$:

${ displaystyle sigma _ {k} (n) = zeta (k + 1) n ^ {k} vlevo [1 + { frac {(-1) ^ {n}} {2 ^ {k + 1 }}} + { frac {2 cos { frac {2 pi n} {3}}} {3 ^ {k + 1}}} + { frac {2 cos { frac { pi n } {2}}} {4 ^ {k + 1}}} + cdots right]}$

Tempo růstu

v malý-o zápis, funkce dělitele uspokojuje nerovnost:^[12][13]

${ displaystyle { mbox {pro všechny}} varepsilon> 0, quad d (n) = o (n ^ { varepsilon}).}$

Přesněji, Severin Wigert ukázal, že:^[13]

${ displaystyle limsup _ {n to infty} { frac { log d (n)} { log n / log log n}} = log 2.}$

Na druhou stranu od té doby prvočísel je nekonečně mnoho,^[13]

${ displaystyle liminf _ {n až infty} d (n) = 2.}$

v Big-O notace, Peter Gustav Lejeune Dirichlet ukázal, že průměrná objednávka funkce dělitele splňuje následující nerovnost:^[14][15]

${ displaystyle { mbox {pro všechny}} x geq 1, součet _ {n leq x} d (n) = x log x + (2 gamma -1) x + O ({ sqrt {x }}),}$

kde ${ displaystyle gamma}$ je Eulerova gama konstanta. Zlepšení vázanosti ${ displaystyle O ({ sqrt {x}})}$ v tomto vzorci je známý jako Dirichletův problém dělitele.

Chování funkce sigma je nepravidelné. Rychlost asymptotického růstu funkce sigma lze vyjádřit: ^[16]

${ displaystyle limsup _ {n rightarrow infty} { frac { sigma (n)} {n , log log n}} = e ^ { gamma},}$

kde lim sup je limit lepší. Tento výsledek je Grönwall věta, publikovaná v roce 1913 (Grönwall 1913 ). Jeho důkaz používá Mertensova třetí věta, který říká, že:

${ displaystyle lim _ {n to infty} { frac {1} { log n}} prod _ {p leq n} { frac {p} {p-1}} = e ^ { gamma},}$

kde p označuje prvočíslo.

V roce 1915 Ramanujan dokázal, že za předpokladu Riemannova hypotéza nerovnost:

${ displaystyle sigma (n)$ (Robinova nerovnost)

drží pro všechny dostatečně velké n (Ramanujan 1997 ). Největší známá hodnota, která porušuje nerovnost, je n=5040. V roce 1984 Guy Robin prokázal, že nerovnost platí pro všechny n > 5040 kdyby a jen kdyby Riemannova hypotéza je pravdivá (Robin 1984 ). Tohle je Robinova věta a nerovnost se stala známou po něm. Robin dále ukázal, že pokud je Riemannova hypotéza nepravdivá, pak existuje nekonečné množství hodnot n které porušují nerovnost, a je známo, že nejmenší takový n > 5040 musí být nadbytečný (Akbary & Friggstad 2009 ). Ukázalo se, že nerovnost platí pro velká celá lichá a čtvercová čísla a že Riemannova hypotéza je ekvivalentní nerovnosti jen pro n dělitelné pátou mocí prvočísla (Choie a kol. 2007 ).

Robin také bezpodmínečně prokázal, že nerovnost:

${ displaystyle sigma (n)$

platí pro všechny n ≥ 3.

Související vazba byla dána Jeffrey Lagarias v roce 2002, který dokázal, že Riemannova hypotéza je ekvivalentní tvrzení, že:

${ displaystyle sigma (n)$

pro každého přirozené číslo n > 1, kde ${ displaystyle H_ {n}}$ je nth harmonické číslo, (Lagarias 2002 ).

Viz také

• Součet dělitele dělitele Uvádí několik identit zahrnujících funkce dělitele
• Eulerova totientová funkce (Eulerova phi funkce)
• Refaktorovatelné číslo
• Tabulka dělitelů
• Unitární dělitel

Poznámky

Reference

• Akbary, Amir; Friggstad, Zachary (2009), „Nadpočetná čísla a Riemannova hypotéza“ (PDF), Americký matematický měsíčník, 116 (3): 273–275, doi:10.4169 / 193009709X470128, archivovány z originál (PDF) dne 2014-04-11.
• Apostol, Tom M. (1976), Úvod do analytické teorie čísel, Vysokoškolské texty z matematiky, New York-Heidelberg: Springer-Verlag, ISBN  978-0-387-90163-3, PAN  0434929, Zbl  0335.10001
• Bach, Eric; Shallit, Jeffrey, Algoritmická teorie čísel, svazek 1, 1996, MIT Press. ISBN  0-262-02405-5, viz strana 234 v části 8.8.
• Caveney, Geoffrey; Nicolas, Jean-Louis; Sondow, Jonathan (2011), „Robinova věta, prvočísla a nová základní formulace Riemannovy hypotézy“ (PDF), INTEGERS: Elektronický deník teorie kombinatorických čísel, 11: A33, arXiv:1110.5078, Bibcode:2011arXiv1110.5078C
• Choie, YoungJu; Lichiardopol, Nicolas; Moree, Pietere; Solé, Patrick (2007), „K Robinovu kritériu pro Riemannovu hypotézu“, Journal de théorie des nombres de Bordeaux, 19 (2): 357–372, arXiv:math.NT / 0604314, doi:10,5802 / jtnb.591, ISSN  1246-7405, PAN  2394891, Zbl  1163.11059
• Grönwall, Thomas Hakon (1913), „Některé asymptotické výrazy v teorii čísel“, Transakce Americké matematické společnosti, 14: 113–122, doi:10.1090 / S0002-9947-1913-1500940-6
• Hardy, G. H.; Wright, E. M. (2008) [1938], Úvod do teorie čísel, Revidováno D. R. Heath-Brown a J. H. Silverman. Předmluva Andrew Wiles. (6. vydání), Oxford: Oxford University Press, ISBN  978-0-19-921986-5, PAN  2445243, Zbl  1159.11001
• Ivić, Aleksandar (1985), Riemannova zeta funkce. Teorie Riemannovy zeta-funkce s aplikacemi„Publikace Wiley-Interscience, New York atd.: John Wiley & Sons, str. 385–440, ISBN  0-471-80634-X, Zbl  0556.10026
• Lagarias, Jeffrey C. (2002), „Elementární problém ekvivalentní Riemannově hypotéze“, Americký matematický měsíčník, 109 (6): 534–543, arXiv:matematika / 0008177, doi:10.2307/2695443, ISSN  0002-9890, JSTOR  2695443, PAN  1908008
• Long, Calvin T. (1972), Základní úvod do teorie čísel (2. vyd.), Lexington: D. C. Heath and Company, LCCN  77171950
• Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Prvky teorie čísel, Englewoodské útesy: Prentice Hall, LCCN  77081766
• Ramanujan, Srinivasa (1997), „Vysoce složená čísla, anotovaná Jean-Louis Nicolasem a Guyem Robinem“, Deník Ramanujan, 1 (2): 119–153, doi:10.1023 / A: 1009764017495, ISSN  1382-4090, PAN  1606180
• Robin, Guy (1984), „Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann“, Journal de Mathématiques Pures et Appliquées, Neuvième Série, 63 (2): 187–213, ISSN  0021-7824, PAN  0774171
• Williams, Kenneth S. (2011), Teorie čísel v duchu LiouvilleStudentské texty London Mathematical Society, 76, Cambridge: Cambridge University Press, ISBN  978-0-521-17562-3, Zbl  1227.11002

externí odkazy

• Weisstein, Eric W. "Funkce dělitele". MathWorld.
• Weisstein, Eric W. „Robinova věta“. MathWorld.
• Základní hodnocení určitých konvolučních součtů zahrnujících funkce dělitele PDF příspěvku od Huarda, Oua, Spearmana a Williamse. Obsahuje základní (tj. Nespoléhající se na teorii modulárních forem) důkazy konvolucí součtu dělitele, vzorce pro počet způsobů reprezentace čísla jako součet trojúhelníkových čísel a související výsledky.