Partitionsfunktion (talteori)

Värdena $p(1),\dots ,p(8)$ för partitionsfunktionen (1, 2, 3, 5, 7, 11, 15 och 22 ) kan bestämmas genom att räkna Young-diagrammen för partitionerna av siffrorna från 1 till 8.

I talteorin representerar partitionsfunktionen p ( n ) antalet möjliga partitioner av ett icke-negativt heltal n . Till exempel, p (4) = 5 eftersom heltal 4 har de fem partitionerna 1 + 1 + 1 + 1 , 1 + 1 + 2 , 1 + 3 , 2 + 2 och 4 .

Inget uttryck i sluten form för partitionsfunktionen är känt, men den har både asymptotiska expansioner som exakt approximerar den och återkommande relationer med vilka den kan beräknas exakt. Det växer som en exponentiell funktion av kvadratroten av sitt argument. Den multiplikativa inversen av dess genererande funktion är Euler-funktionen ; med Eulers femkantiga talsats är denna funktion en alternerande summa av femkantiga talpotenser i dess argument.

Srinivasa Ramanujan upptäckte först att partitionsfunktionen har icke-triviala mönster i modulär aritmetik , nu känd som Ramanujans kongruenser . Till exempel, när decimalrepresentationen av n slutar på siffran 4 eller 9, kommer antalet partitioner av n att vara delbart med 5.

Definition och exempel

För ett positivt heltal n är p ( n ) antalet distinkta sätt att representera n som summan av positiva heltal. För ändamålen med denna definition är ordningen på termerna i summan irrelevant: två summor med samma termer i en annan ordning anses inte vara distinkta.

Enligt konventionen p (0) = 1 , eftersom det finns ett sätt (den tomma summan ) att representera noll som en summa av positiva heltal. Dessutom p ( n ) = 0 när n är negativ.

De första värdena för partitionsfunktionen, som börjar med p (0) = 1 , är:

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

Några exakta värden på p ( n ) för större värden på n inkluderar:

$${\begin{aligned}p(100)&=190,\!569,\!292\\p(1000)&=24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991\approx 2.40615\times 10^{31}\\p(10000)&=36,\!167,\!251,\!325,\!\dots ,\!906,\!916,\!435,\!144\approx 3.61673\times 10^{106}\end{aligned}}$$

är det största kända primtalet bland värdena för p ( n ) p (1289844341) , med 40 000 decimalsiffror. Fram till mars 2022 var detta också det största primtal som har bevisats med hjälp av elliptisk kurvaprimalitetsbevis .

Genererande funktion

Använder Eulers metod för att hitta p (40) : En linjal med plus- och minustecken (grå ruta) skjuts nedåt, de relevanta termerna läggs till eller subtraheras. Tecknens positioner ges av skillnader mellan omväxlande naturliga (blå) och udda (orange) tal. i SVG-filen för att flytta linjalen.

Huvudartikel: Pentagonal nummersats

Genereringsfunktionen för p ( n ) ges av

$${\begin{aligned}\sum _{n=0}^{\infty }p(n)x^{n}&=\prod _{k=1}^{\infty }\left({ \frac {1}{1-x^{k}}}\right)\\&=\left(1+x+x^{2}+x^{3}+\cdots \right)\left(1 +x^{2}+x^{4}+x^{6}+\cdots \right)\left(1+x^{3}+x^{6}+x^{9}+\cdots \ höger)\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}.\end{aligned}}$$

Likheten mellan produkterna på den första och andra raden i denna formel erhålls genom att expandera varje faktor $1/(1-x^{k})$ till den geometriska serien $(1+x^{k}+x^{2k}+x^{3k}+\cdots ).$ För att se att den utökade produkten är lika med summan på första raden, tillämpa den fördelande lagen på produkten . Detta expanderar produkten till en summa av monomer av formen $x^{a_{1}}x^{2a_{2}}x^{3a_{3} }\cdots$ för någon sekvens av koefficienter ${\displaystyle a_{i}} ,$ av vilka endast ändligt många kan vara icke-noll. Termens exponent är ${\textstyle n=\sum ia_{i}}$ , och denna summa kan tolkas som en representation av $n$ som en partition i $a_{i}$ kopior av varje nummer $i$ . Därför är antalet termer för produkten som har exponent $n$ exakt $p(n)$ , samma som koefficienten för $x^{n}$ i summan till vänster. Därför är summan lika med produkten.

Funktionen som visas i nämnaren på formelns tredje och fjärde rad är Euler-funktionen . Likheten mellan produkten på första raden och formlerna på tredje och fjärde raden är Eulers femkantiga talsats . Exponenterna för $x$ på dessa rader är de femkantiga talen $P_{k}=k(3k-1)/2$ för ${\displaystyle k\in \{0,1,-1,2,-2,\dots \}} ($ generaliserat något från de vanliga femkantiga talen, som kommer från samma formel för de positiva värdena för ${\displaystyle k} )$ . Mönstret av positiva och negativa tecken på den tredje raden kommer från termen $(-1)^{k}$ på den fjärde raden: även val av $k$ ger positiva termer, och udda val ger negativa termer.

Mer allmänt kan genereringsfunktionen för partitionerna av $n$ i tal valda från en uppsättning $A$ av positiva heltal hittas genom att endast ta de termer i den första produkten för vilka ${\ displaystil k\in A}$ . Detta resultat beror på Leonhard Euler . Formuleringen av Eulers genererande funktion är ett specialfall av en $q$ -Pochhammer-symbol och liknar produktformuleringen för många modulära former , och specifikt Dedekind eta-funktionen .

Återkommande relationer

Samma sekvens av femkantiga tal visas i en återkommande relation för partitionsfunktionen:

$${\begin{aligned}p(n)&=\ summa _{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{aligned} }$$

Som basfall tas $p(0)$ lika med $1$ , och $p(k)$ tas till noll för negativ $k$ . Även om summan på höger sida verkar oändlig, har den bara ändligt många termer som inte är noll, som kommer från värdena som inte är noll för $k$ i intervallet

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

En annan återkommande relation för $p(n)$ kan ges i termer av summan av divisorfunktion σ :

$$p(n)={\frac {1}{n}}\sum _{k=0}^{n-1}\sigma (nk)p(k).$$

Om $q(n)$ anger antalet partitioner av $n$ utan upprepade delar, följer det genom att dela upp varje partition i dess jämna delar och udda delar, och dividera de jämna delarna med två, det

$$p(n)=\summa _{k=0}^{\left\lfloor n/2\right\rfloor}q(n-2k)p(k).$$

Kongruenser

Huvudartikel: Ramanujans kongruenser

Srinivasa Ramanujan är krediterad för att ha upptäckt att partitionsfunktionen har icke-triviala mönster i modulär aritmetik . Till exempel är antalet partitioner delbart med fem när decimalrepresentationen av $n$ slutar på siffran 4 eller 9, uttryckt av kongruensen

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

Till exempel är antalet partitioner för heltal 4 5. För heltal 9 är antalet partitioner 30; för 14 finns det 135 partitioner. Denna kongruens antyds av den mer allmänna identiteten

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

även av Ramanujan, där notationen $(x)_{\infty }$ anger produkten som definieras av

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

Ett kort bevis på detta resultat kan erhållas från den genererande funktionen för partitionsfunktioner.

Ramanujan upptäckte också kongruenserna modulo 7 och 11:

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

Den första kommer från Ramanujans identitet

$$\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}}}.$$

$) {\displaystyle p(13k+a)\equiv 0{\pmod {13}}}$ och 11 är på varandra följande primtal kan man tro att det skulle finnas en analog kongruens för nästa primtal 13, för vissa en . Det finns dock ingen kongruens av formen $p(bk+a)\equiv 0{\pmod {b}}$ för något primtal b annat än 5, 7 , eller 11. Istället, för att få en kongruens, bör argumentet för $p$ ha formen $cbk+a$ för vissa $c>1$ . På 1960-talet AOL Atkin vid University of Illinois i Chicago ytterligare kongruenser av denna form för små primmoduler. Till exempel:

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

Ken Ono ( 2000 ) bevisade att det finns sådana kongruenser för varje primmodul större än 3. Senare visade Ahlgren & Ono (2001) att det finns partitionskongruenser modulo varje heltals coprime till 6.

Approximationsformler

Approximationsformler finns som är snabbare att beräkna än den exakta formeln ovan.

Ett asymptotiskt uttryck för p ( n ) ges av

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\ pi {\sqrt {\frac {2n}{3}}}}\right)$ som $n\to \infty$ .

Denna asymptotiska formel erhölls först av GH Hardy och Ramanujan 1918 och oberoende av JV Uspensky 1920. Med tanke på $p(1000)$ ger den asymptotiska formeln cirka ${\02\stime 2,444 10^{31}}$ , ganska nära det exakta svaret ovan (1,415 % större än det sanna värdet).

Hardy och Ramanujan fick en asymptotisk expansion med denna approximation som första term:

$$p (n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{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}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\ eller hur),$$

var

$$A_{k}(n)=\summa _{0\leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/ k\right)}.$$

Här betyder notationen $(m,k)=1$ att summan endast tas över värdena på $m$ som är relativt primtal till $k$ . Funktionen $s(m,k)$ är en Dedekind summa .

Felet efter $v$ termer är av samma ordning som nästa term, och $v$ kan anses vara av storleksordningen ${\sqrt {n}}$ . Som ett exempel visade Hardy och Ramanujan att $p(200)$ är det närmaste heltal till summan av de första $v=5$ termerna i serien.

1937 kunde Hans Rademacher förbättra Hardy och Ramanujans resultat genom att tillhandahålla ett konvergent serieuttryck för $p(n)$ . Det är

$$p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{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}}\left(n-{\frac {1}{24}}\right)}}}\,\, \,\eller hur).$$

Beviset för Rademachers formel involverar Ford-cirklar , Farey-sekvenser , modulär symmetri och Dedekind eta-funktionen .

Det kan visas att ${\displaystyle k}:$ te termen i Rademachers serie är av ordningen

$$\exp \left({\frac {\pi }{k}}{\sqrt {\frac {2n}{3}}}\right),$$

så att den första termen ger Hardy–Ramanujan asymptotisk approximation. Paul Erdős ( 1942 ) publicerade ett elementärt bevis på den asymptotiska formeln för $p(n)$ .

Tekniker för att implementera Hardy–Ramanujan–Rademacher-formeln effektivt på en dator diskuteras av Johansson (2012) , som visar att $p(n)$ kan beräknas i tiden $O(n^{1/2+\varepsilon })$ för alla $\varepsilon >0$ . Detta är nästan optimalt eftersom det matchar antalet siffror i resultatet. Det största värdet på partitionsfunktionen som beräknas exakt är ${\displaystyle p(10^{20})} ,$ som har något mer än 11 ​​miljarder siffror.

Strikt partitionsfunktion

Definition och egenskaper

En partition där ingen del förekommer mer än en kallas strikt , eller sägs vara en partition i distinkta delar . Funktionen q ( n ) ger antalet av dessa strikta partitioner av den givna summan n . Till exempel, q (3) = 2 eftersom partitionerna 3 och 1 + 2 är strikta, medan den tredje partitionen 1 + 1 + 1 av 3 har upprepade delar. Antalet q ( n ) är också lika med antalet partitioner av n där endast udda summeringar är tillåtna.

Exempelvärden för q ( n ) och tillhörande partitioner

n	q ( n )	Strikta partitioner	Skiljeväggar med endast udda delar
0	1	() tom partition	() tom partition
1	1	1	1
2	1	2	1+1
3	2	1+2, 3	1+1+1, 3
4	2	1+3, 4	1+1+1+1, 1+3
5	3	2+3, 1+4, 5	1+1+1+1+1, 1+1+3, 5
6	4	1+2+3, 2+4, 1+5, 6	1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5
7	5	1+2+4, 3+4, 2+5, 1+6, 7	1+1+1+1+1+1+1, 1+1+1+1+3, 1+3+3, 1+1+5, 7
8	6	1+3+4, 1+2+5, 3+5, 2+6, 1+7, 8	1+1+1+1+1+1+1+1, 1+1+1+1+1+3, 1+1+3+3, 1+1+1+5, 3+5, 1+ 7
9	8	2+3+4, 1+3+5, 4+5, 1+2+6, 3+6, 2+7, 1+8, 9	1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+3, 1+1+1+3+3, 3+3+3, 1+ 1+1+1+5, 1+3+5, 1+1+7, 9

Genererande funktion

Genereringsfunktionen för talen q ( n ) ges av en enkel oändlig produkt:

$$\sum _{n=0}^{\infty }q (n)x^{n}=\prod _{k=1}^{\infty }(1+x^{n})=(x;x^{2})_{\infty }^{-1 },$$

där notationen $(a;b)_{\infty }$ representerar Pochhammer-symbolen ${\displaystyle (a;b)_{\infty }=\prod _{k=0}^{\infty }(1-ab^{k}).} Från$ denna formel kan man enkelt få de första termerna (sekvens A000009 i OEIS ):

$$\sum _{n=0}^{\infty }q(n)x^{n}=1+1x+1x^{2}+2x^{3}+2x^{4}+3x^ {5}+4x^{6}+5x^{7}+6x^{8}+8x^{9}+10x^{10}+\ldots .$$

Denna serie kan också skrivas i termer av theta-funktioner som

$$\sum _{n=0}^{\infty }q(n)x^{n}=\vartheta _{00}(x)^{1/6}\vartheta _{01}( x)^{-1/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _ {01}(x)^{4}{\bigr ]}{\biggr \}}^{1/24},$$

var

$$\vartheta _{00}(x)=1+2\summa _{n=1}^{\infty }x^{n ^{2}}$$

och

$$\vartheta _{01}(x)=1+2\summa _{n=1}^{\infty }(-1)^{n}x^{n^{2}}.$$

I jämförelse har genereringsfunktionen för de vanliga partitionsnumren p ( n ) denna identitet med avseende på theta-funktionen:

$$\sum _{n=0}^{\infty }p(n)x^{n}=(x;x)_{\infty }^{-1}=\vartheta _{00}(x )^{-1/6}\vartheta _{01}(x)^{-2/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}{\biggr \}}^{-1/24}.$$

Identiteter om strikta partitionsnummer

Följande identitet är giltig för Pochhammer-produkterna:

$(x;x)_{\infty }^{-1}=(x^ {2};x^{2})_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}$

Från denna identitet följer den formeln:

${\biggl [}\sum _{ n=0}^{\infty }p(n)x^{n}{\biggr ]}={\biggl [}\summa _{n=0}^{\infty }p(n)x^{2n }{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }q(n)x^{n}{\biggr ]}$

Därför är dessa två formler giltiga för syntesen av talsekvensen p(n):

$p(2n)=\summa _{k=0}^{n}p(nk)q(2k)$

$p(2n+1)=\summa _{k=0}^{n}p(nk )q(2k+1)$

I det följande är två exempel korrekt utförda:

$p(8)=\summa _{k=0}^{4}p(4-k)q(2k) )=$

$=p(4)q(0)+p(3)q(2)+p(2)q(4)+p(1)q(6)+p(0)q(8)=$

$=5\ gånger 1+3\ gånger 1+2\ gånger 2+1\ gånger 4+1\ gånger 6=22$

$p(9)=\summa _{k=0}^{4}p(4-k)q (2k+1)=$

$=p(4)q(1)+p(3)q(3)+p(2)q(5)+p(1)q(7)+p(0)q(9) =$

$=5\ gånger 1+3\ gånger 2+2\ gånger 3+1\ ​​gånger 5+1\ gånger 8=30$

Begränsad partitionsfunktion

Mer generellt är det möjligt att betrakta partitioner som är begränsade till endast element i en delmängd A av de naturliga talen (till exempel en begränsning av delarnas maximala värde), eller med en begränsning av antalet delar eller den maximala skillnaden mellan delarna . Varje speciell begränsning ger upphov till en associerad partitionsfunktion med specifika egenskaper. Några vanliga exempel ges nedan.

Euler och Glaishers sats

Två viktiga exempel är partitionerna begränsade till endast udda heltalsdelar eller endast jämna heltalsdelar, med motsvarande partitionsfunktioner ofta betecknade $p_{o}(n)$ och $p_{e}(n)$ .

Ett teorem från Euler visar att antalet strikta partitioner är lika med antalet partitioner med endast udda delar: för alla n , $q(n)=p_{o}( n)$ . Detta är generaliserat som Glaishers sats , som säger att antalet partitioner med högst d-1 repetitioner av någon del är lika med antalet partitioner utan del som är delbart med d .

Gaussisk binomial koefficient

Om vi ​​betecknar $p(N,M,n)$ antalet partitioner av n i högst M delar, med varje del mindre eller lika med N , då genererar funktionen för $p(N,M,n)$ är följande gaussiska binomialkoefficient :

$\sum _{n=0}^{\infty }p(N,M,n)q^{n}={N +M \välj M}_{q}={\frac {(1-q^{N+M})(1-q^{N+M-1})\cdots (1-q^{N+1) })}{(1-q)(1-q^{2})\cdots (1-q^{M})}}$

Asymptotika

Vissa allmänna resultat om de asymptotiska egenskaperna hos begränsade partitionsfunktioner är kända. Om p _A ( n ) är partitionsfunktionen för partitioner som är begränsade till endast element i en delmängd A av de naturliga talen, då:

Om A har positiv naturlig densitet α så ${\displaystyle \log p_{A}(n)\sim C{\sqrt {\alpha n}}} ,$ med $C=\pi {\sqrt {\frac {2}{3}}}$

och omvänt om denna asymptotiska egenskap gäller för p _A ( n ) så har A naturlig densitet α. Detta resultat angavs, med en skiss av bevis, av Erdős 1942.

Om A är en finit mängd gäller inte denna analys (densiteten för en finit mängd är noll). Om A har k element vars största gemensamma delare är 1, då

$p_{A}(n)=\left(\prod _{a\in A}a^{-1}\right)\cdot {\frac {n^{k-1}}{(k- 1)!}}+O(n^{k-2}).$

externa länkar

• De första 4096 värdena för partitionsfunktionen