Funkce rozdělení (teorie čísel) - Partition function (number theory)

Hodnoty ${ displaystyle p (1), tečky p (8)}$ funkce oddílu (1, 2, 3, 5, 7, 11, 15 a 22) lze určit počítáním Mladé diagramy pro oddíly čísel od 1 do 8.

v teorie čísel, funkce oddílu p(n) představuje číslo možné oddíly nezáporného celého čísla n. Například, p(4) = 5 protože celé číslo 4 má pět oddílů 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, a 4.

Ne uzavřený výraz pro funkci oddílu je známa, ale má obojí asymptotické expanze které to přesně přibližují a relace opakování podle kterého jej lze přesně vypočítat. Roste jako exponenciální funkce z odmocnina jeho argumentu. The multiplikativní inverzní jeho generující funkce je Eulerova funkce; od Eulera věta o pětiúhelníku tato funkce je střídavým součtem pětiúhelníkové číslo pravomoci jeho argumentu.

Srinivasa Ramanujan nejprve objevil, že funkce oddílu má netriviální vzory v modulární aritmetika, nyní známý jako Ramanujanovy shody. Například kdykoli desítkové vyjádření n končí číslicí 4 nebo 9, počtem oddílů n bude dělitelná 5.

Definice a příklady

Pro kladné celé číslo n, p(n) je počet odlišných způsobů reprezentace n jako součet kladných celých čísel. Pro účely této definice je pořadí výrazů v součtu irelevantní: dvě částky se stejnými výrazy v jiném pořadí nejsou považovány za odlišné.

Podle dohody p(0) = 1, protože existuje jeden způsob ( prázdná částka ) reprezentující nulu jako součet kladných celých čísel. Ze stejného důvodu, podle definice, p(n) = 0 když n je negativní.

Prvních několik hodnot funkce oddílu, počínaje p(0) = 1, jsou:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604,… (sekvence A000041 v OEIS ).

Nějaká přesná hodnota p(n) pro větší hodnoty n zahrnout:^[1]

${ displaystyle { begin {zarovnáno} p (100) & = 190 569 292 p (1000) & = 24 061 467 864 032 622 473 692 149 999 277 991 přibližně 2,40615 krát 10 ^ {31} p (10 000) & = 36 167 251 325, tečky, 906 916 435 144 přibližně 3,61673 krát 10 ^ {106} konec {zarovnáno}}}$

Od září 2017^{[Aktualizace]}, největší známý prvočíslo mezi hodnotami p(n) je p(221444161)s 16 569 desetinnými číslicemi.^[2]

Generující funkce

The generující funkce pro p(n) darováno^[3]

${ displaystyle { begin {aligned} sum _ {n = 0} ^ { infty} p (n) x ^ {n} & = prod _ {k = 1} ^ { infty} left ({ frac {1} {1-x ^ {k}}} vpravo) & = (1 + x + x ^ {2} + x ^ {3} + cdots) (1 + x ^ {2} + x ^ {4} + x ^ {6} + cdots) (1 + x ^ {3} + x ^ {6} + x ^ {9} + cdots) cdots & = { frac { 1} {1-xx ^ {2} + x ^ {5} + x ^ {7} -x ^ {12} -x ^ {15} + x ^ {22} + x ^ {26} - cdots} } & = 1 { Big /} sum _ {k = - infty} ^ { infty} (- 1) ^ {k} x ^ {k (3k-1) / 2}. konec {zarovnáno}}}$

Rovnost mezi produkty v prvním a druhém řádku tohoto vzorce se získá rozšířením každého faktoru ${ displaystyle 1 / (1-x ^ {k})}$ do geometrické řady ${ displaystyle (1 + x ^ {k} + x ^ {2k} + x ^ {3k} + cdots).}$Chcete-li vidět, že se rozšířený produkt rovná součtu v prvním řádku, použijte distribuční právo k produktu. Tím se produkt rozšíří na součet monomials formuláře ${ displaystyle x ^ {a_ {1}} x ^ {2a_ {2}} x ^ {3a_ {3}} cdots}$ pro nějakou posloupnost koeficientů${ displaystyle a_ {i}}$, pouze konečně mnoho z nich může být nenulových. Exponent exponentu je ${ displaystyle n = součet ia_ {i}}$a tuto částku lze interpretovat jako vyjádření ${ displaystyle n}$ jako oddíl do ${ displaystyle a_ {i}}$ kopie každého čísla ${ displaystyle i}$. Proto počet výrazů produktu, které mají exponent ${ displaystyle n}$ je přesně ${ displaystyle p (n)}$, stejný jako koeficient ${ displaystyle x ^ {n}}$ v součtu vlevo. Proto se součet rovná součinu.

Funkce, která se objeví ve jmenovateli ve třetím a čtvrtém řádku vzorce, je Eulerova funkce. Rovnost mezi produktem v prvním řádku a vzorci ve třetím a čtvrtém řádku je Eulerova věta o pětiúhelníku Exponenti ${ displaystyle x}$ v těchto řádcích jsou pětiboká čísla ${ displaystyle P_ {k} = k (3k-1) / 2}$ pro ${ displaystyle k in {0,1, -1,2, -2, tečky }}$ (zobecněno poněkud z obvyklých pětiúhelníkových čísel, která vycházejí ze stejného vzorce pro kladné hodnoty ${ displaystyle k}$). Vzor pozitivních a negativních znaků ve třetím řádku pochází z termínu ${ displaystyle (-1) ^ {k}}$ ve čtvrtém řádku: sudá volba ${ displaystyle k}$ vytvářejí kladné výrazy a liché volby vytvářejí negativní výrazy.

Obecněji řečeno, generující funkce pro oddíly ${ displaystyle n}$ do čísel vybraných ze sady ${ displaystyle A}$ kladných celých čísel lze najít tak, že v prvním produktu, pro který ${ displaystyle k v A}$. Tento výsledek je způsoben Leonhard Euler.^[4] Formulace Eulerovy generující funkce je zvláštním případem a ${ displaystyle q}$-Pochhammer symbol a je podobný složení mnoha produktů modulární formy a konkrétně Funkce Dedekind eta.

Vztahy opakování

Stejná posloupnost pětiúhelníkových čísel se objeví v a relace opakování pro funkci oddílu:^[5]

${ displaystyle { begin {zarovnáno} p (n) & = součet _ {k in mathbb {Z} setminus {0 }} (- 1) ^ {k + 1} p (nk (3k -1) / 2) & = p (n-1) + p (n-2) -p (n-5) -p (n-7) + p (n-12) + p (n-15 ) -p (n-22) - cdots end {zarovnáno}}}$

Jako základní případy ${ displaystyle p (0)}$ je považováno za rovnocenné ${ displaystyle 1}$, a ${ displaystyle p (k)}$ se považuje za nulu pro zápor${ displaystyle k}$. Ačkoli se součet na pravé straně jeví jako nekonečný, má pouze konečně mnoho nenulových výrazů pocházejících z nenulových hodnot ${ displaystyle k}$ v dosahu

${ displaystyle - { frac {{ sqrt {24n + 1}} - 1} {6}} leq k leq { frac {{ sqrt {24n + 1}} + 1} {6}}}$.

Další relace opakování pro ${ displaystyle p (n)}$ lze uvést ve smyslu součet funkce dělitelů σ:^[6]

${ displaystyle p (n) = { frac {1} {n}} součet _ {k = 0} ^ {n-1} sigma (n-k) p (k).}$

Li ${ displaystyle q (n)}$ označuje počet oddílů ${ displaystyle n}$ bez opakovaných částí pak následuje rozdělením každého oddílu na jeho sudé části a liché části a dělením sudých částí dvěma, že^[7]

${ Displaystyle p (n) = součet _ {k = 0} ^ { levý lfloor n / 2 pravý rfloor} q (n-2k) p (k).}$

Shody

Srinivasa Ramanujan je připočítán s objevem, že funkce oddílu má netriviální vzory modulární aritmetika Například počet oddílů je dělitelný pěti, kdykoli je desetinná reprezentace ${ displaystyle n}$ končí číslicí 4 nebo 9, jak je vyjádřeno shodou^[8]

${ displaystyle p (5k + 4) equiv 0 { pmod {5}}}$

Například počet oddílů pro celé číslo 4 je 5. Pro celé číslo 9 je počet oddílů 30; pro 14 existuje 135 oddílů. Tato shoda je implikována obecnější identitou

${ displaystyle sum _ {k = 0} ^ { infty} p (5k + 4) x ^ {k} = 5 ~ { frac {(x ^ {5}) _ { infty} ^ {5} } {(x) _ { infty} ^ {6}}},}$

také Ramanujan,^[9][10] kde notace ${ displaystyle (x) _ { infty}}$ označuje produkt definovaný

${ displaystyle (x) _ { infty} = prod _ {m = 1} ^ { infty} (1-x ^ {m}).}$

Krátký důkaz tohoto výsledku lze získat z funkce generující funkci oddílu.

Ramanujan také objevil kongruence modulo 7 a 11:^[8]

${ displaystyle { begin {aligned} p (7k + 5) & equiv 0 { pmod {7}}, p (11k + 6) & equiv 0 { pmod {11}}. end { zarovnaný}}}$

Pocházejí z Ramanujanovy identity^[10]

${ displaystyle sum _ {k = 0} ^ { infty} p (7k + 5) x ^ {k} = 7 ~ { frac {(x ^ {7}) _ { infty} ^ {3} } {(x) _ { infty} ^ {4}}} + 49x ~ { frac {(x ^ {7}) _ { infty} ^ {7}} {(x) _ { infty} ^ {8}}}.}$

Protože 5, 7 a 11 jsou po sobě jdoucí připraví, jeden by si mohl myslet, že bude analogická shoda pro příští prime 13, ${ displaystyle p (13k + a) equiv 0 { pmod {13}}}$ pro některé A. Neexistuje však žádná shoda formy ${ displaystyle p (bk + a) equiv 0 { pmod {b}}}$ pro všechny prime b jiné než 5, 7 nebo 11.^[11] Místo toho, aby se dosáhlo shody, argument ${ displaystyle p}$ by měl mít podobu ${ displaystyle cbk + a}$ pro některé ${ displaystyle c> 1}$. V šedesátých letech A. O. L. Atkin z University of Illinois v Chicagu objevil další kongruence této formy pro malé primární moduly. Například:

${ displaystyle p (11 ^ {3} cdot 13 cdot k + 237) equiv 0 { pmod {13}}.}$

Ken Ono  (2000 ) dokázal, že existují takové kongruence pro každý primární modul větší než 3. Později, Ahlgren & Ono (2001) ukázal, že existují kongruence oddílů modulo každé celé číslo coprime až 6.^[12][13]

Aproximační vzorce

Existují aproximační vzorce, které lze vypočítat rychleji než přesný vzorec uvedený výše.

An asymptotické výraz pro p(n) darováno

${ displaystyle p (n) sim { frac {1} {4n { sqrt {3}}}} exp left ({ pi { sqrt { frac {2n} {3}}}} že jo)}$ tak jako ${ displaystyle n rightarrow infty}$.

Tento asymptotický vzorec byl poprvé získán G. H. Hardy a Ramanujan v roce 1918 a samostatně J. V. Uspensky v roce 1920. Vzhledem k tomu ${ displaystyle p (1000)}$, asymptotický vzorec dává asi ${ displaystyle 2,4402 krát 10 ^ {31}}$, přiměřeně blízko k přesné odpovědi uvedené výše (o 1,415% větší než skutečná hodnota).

Hardy a Ramanujan získali asymptotická expanze s touto aproximací jako první termín:^[14]

${ displaystyle p (n) sim { frac {1} {2 pi { sqrt {2}}}} součet _ {k = 1} ^ {v} A_ {k} (n) { sqrt {k}} cdot { frac {d} {dn}} left ({{ frac {1} { sqrt {n - { frac {1} {24}}}}} exp left [ {{ frac { pi} {k}} { sqrt {{ frac {2} {3}} vlevo (n - { frac {1} {24}} vpravo)}}} , ,,dobře dobře),}$

kde

${ displaystyle A_ {k} (n) = součet _ {0 leq m$

Tady notace ${ displaystyle (m, k) = 1}$ znamená, že součet by se měl vyskytovat pouze nad hodnotami ${ displaystyle m}$ to jsou relativně prime na ${ displaystyle k}$. Funkce ${ displaystyle s (m, k)}$ je Dedekindova částka.

Chyba po ${ displaystyle v}$ podmínky jsou v pořadí následujícího období a ${ displaystyle v}$ lze považovat za řádově ${ displaystyle { sqrt {n}}}$. Jako příklad to ukázali Hardy a Ramanujan ${ displaystyle p (200)}$ je nejbližší celé číslo součtu prvního ${ displaystyle v = 5}$ pojmy ze série.^[14]

V roce 1937 Hans Rademacher byl schopen zlepšit výsledky Hardyho a Ramanujana poskytnutím a konvergentní série výraz pro ${ displaystyle p (n)}$. to je^[15][16]

${ displaystyle p (n) = { frac {1} { pi { sqrt {2}}}} součet _ {k = 1} ^ { infty} A_ {k} (n) { sqrt { k}} cdot { frac {d} {dn}} left ({{ frac {1} { sqrt {n - { frac {1} {24}}}}} sinh left [{ { frac { pi} {k}} { sqrt {{ frac {2} {3}} vlevo (n - { frac {1} {24}} vpravo)}}} , , ,dobře dobře).}$

Důkaz Rademacherova vzorce zahrnuje Ford kruhy, Farey sekvence, modulární symetrie a Funkce Dedekind eta.

Může se ukázat, že ${ displaystyle k}$Třetí termín Rademacherovy řady je řádový

${ displaystyle exp left ({ frac { pi} {k}} { sqrt { frac {2n} {3}}} vpravo),}$

takže první člen dává Hardy – Ramanujan asymptotické přiblížení.Paul Erdős  (1942 ) zveřejnil základní důkaz o asymptotickém vzorci pro ${ displaystyle p (n)}$.^[17][18]

Techniky pro efektivní implementaci vzorce Hardy – Ramanujan – Rademacher na počítači jsou diskutovány v Johansson (2012), který to ukazuje ${ displaystyle p (n)}$ lze vypočítat v čase ${ displaystyle O (n ^ {1/2 + varepsilon})}$ pro všechny ${ displaystyle varepsilon> 0}$. To je téměř optimální v tom, že odpovídá počtu číslic výsledku.^[19] Největší hodnota funkce oddílu vypočítaná přesně je ${ displaystyle p (10 ^ {20})}$, který má o něco více než 11 miliard číslic.^[20]

Reference

externí odkazy

• Prvních 4096 hodnot funkce oddílu