Petkovšeks algoritm

Petkovšeks algoritm (även Hyper ) är en datoralgebraalgoritm som beräknar en bas av hypergeometriska termer och dess indata linjära återfallsekvation med polynomkoefficienter . På motsvarande sätt beräknar den en första ordningens högerfaktor för linjära skillnadsoperatorer med polynomkoefficienter. Denna algoritm utvecklades av Marko Petkovšek i sin doktorsavhandling 1992. Algoritmen är implementerad i alla stora datoralgebrasystem.

Gosper-Petkovšek representation

Låt ${\textstyle \mathbb {K} }$ vara ett fält med karakteristiken noll. En sekvens som inte är noll ${\textstyle y(n)}$ kallas hypergeometrisk om förhållandet mellan två på varandra följande termer är rationellt , dvs ${\textstyle y( n+1)/y(n)\in \mathbb {K} (n)}$ . Petkovšek-algoritmen använder som nyckelbegrepp att denna rationella funktion har en specifik representation, nämligen Gosper-Petkovšek normalformen . Låt ${\textstil r(n)\in \mathbb {K} [n]}$ vara en rationell funktion som inte är noll. Sedan finns det moniska polynom ${\textstil a,b,c\in \mathbb {K} [n]}$ och ${\textstyle 0\neq z\in \mathbb {K} }$ så att

$r(n)=z{\frac {a(n)}{b(n)}}{ \frac {c(n+1)}{c(n)}}$

och

1. ${\textstyle \gcd(a(n),b(n+k))=1}$ för varje icke-negativt heltal ${\textstyle k\in \mathbb {N} }$ ,
2. ${\textstyle \gcd(a(n),c(n))=1}$ och
3. ${\textstil \gcd(b(n),c(n+1))=1}$ .

Denna representation av ${\textstyle r(n)}$ kallas Gosper-Petkovšek normalform. Dessa polynom kan beräknas explicit. Denna konstruktion av representationen är en viktig del av Gospers algoritm . Petkovšek lade till villkoren 2. och 3. i denna representation som gör denna normala form unik.

Algoritm

Med hjälp av Gosper-Petkovšek-representationen kan man omvandla den ursprungliga återkommande ekvationen till en återkommande ekvation för en polynomsekvens ${\textstyle c(n)}$ . De andra polynomen ${\textstyle a(n),b(n)}$ kan tas som moniska faktorer för det första koefficientpolynomet ${\textstyle p_{0}(n) )}$ resp. det sista koefficientpolynomet skiftat ${\textstyle p_{r}(n-r+1)}$ . Då måste ${\textstyle z} uppfylla en viss$ algebraisk ekvation . Att ta alla möjliga ändligt många trippel ${\textstyle (a(n),b(n),z)}$ och beräkna motsvarande polynomlösning av den transformerade recurrencekvationen ${\textstyle c(n)}$ ger en hypergeometrisk lösning om en sådan finns.

betecknas graden av ett polynom ${\textstyle p(n)\in \mathbb {K} [n]} med$${\textstyle \deg(p(n))}$ och koefficienten för ${\textstyle n^{d}}$ betecknas med ${\textstyle {\text{coeff}}(p( n),n^{d})}$ .

     
         
              
                
        
         
            
                
                 algoritm  petkovsek  matas  in:  Linjär återkommande ekvation ${\textstyle \sum _{k=0}^ {r}p_{k}(n)\,y(n+k)=0,p_{k}\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$ .  output:  En hypergeometrisk lösning ${\textstyle y}$ om det finns några hypergeometriska lösningar.  för varje  monisk divisor ${\textstyle a(n)}$ av ${\textstyle p_{0}(n)}$ gör  för varje  monisk divisor ${\textstyle b(n)}$ av ${\textstyle p_{r}(n-r+1)}$ gör  för varje ${\textstyle k=0,\dots ,r}$ do ${\textstyle {\tilde {p}}_{k}(n) =p_{k}(n)\prod _{j=0}^{k-1}a(n+j)\prod _{i=k}^{r-1}b(n+i)}$${\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k} (n))}$ för varje  rot ${\textstyle z}$ av ${\textstyle \sum _{k=0}^{r}{\ text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}} do Hitta polynomlösning som inte är noll c ( n )$ {  \ $) )}$ av ${\textstyle \sum _{k=0}^{r}z^{k}\,{\tilde {p} }_{k}(n)\,c(n+k)=0}$ om  en sådan icke-nolllösning ${\textstyle c(n)}$ existerar  då ${\textstil r(n)=z\,a(n)/b(n)\,c(n+1)/c(n)}$ returnera  en lösning som inte är noll ${\textstil y(n)}$ av ${\textstil y(n+1)=r(n)\, y(n)}$

Om man inte slutar om en lösning hittas är det möjligt att kombinera alla hypergeometriska lösningar för att få en generell hypergeometrisk lösning av recidivekvationen, dvs en genereringsmängd för kärnan av recidivekvationen i det linjära spannet av hypergeometriska sekvenser.

Petkovšek visade också hur det inhomogena problemet kan lösas. Han övervägde fallet där den högra sidan av återfallsekvationen är en summa av hypergeometriska sekvenser. Efter att ha grupperat vissa hypergeometriska sekvenser på högersidan, löses för var och en av dessa grupper en viss återfallsekvation för en rationell lösning. Dessa rationella lösningar kan kombineras för att få en speciell lösning av den inhomogena ekvationen. Tillsammans med den allmänna lösningen av det homogena problemet ger detta den allmänna lösningen av det inhomogena problemet.

Exempel

Signerade permutationsmatriser

Antalet teckenförsedda permutationsmatriser med storleken ${\textstyle n\ gånger n}$ kan beskrivas av sekvensen ${\textstyle y(n)}$ som bestäms av återfallsekvationen

$$4(n+1)^{2}\,y(n) +2\,y(n+1)+(-1)\,y(n+2)=0$$

över ${\textstyle \mathbb {Q} }$ . Med ${\textstil a(n)=n+1,b(n)=1}$ som moniska divisorer av ${\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1}$ respektive, man får ${\textstyle z=\pm 2}$ . För ${\textstyle z=2}$ är motsvarande återkommande ekvation som löses i Petkovšeks algoritm

$$4( n+1)^{2}\,c(n)+4(n+1)\,c(n+1)-4(n+1)(n+2)\,c(n+2)= 0.$$

Denna återkommande ekvation har polynomlösningen ${\textstil c(n)=c_{0}}$ för ett godtyckligt ${\textstil c_{0}\in \mathbb {Q} }$ . Därför är ${\textstil r(n)=2(n+1)}$ och ${\textstyle y(n)=2^{n}\,n!}$ är en hypergeometrisk lösning. I själva verket är det (upp till en konstant) den enda hypergeometriska lösningen och beskriver antalet signerade permutationsmatriser.

Irrationalitet hos $\zeta (3)$

Givet summan

$a(n)=\summa _{k=0}^{n}{{\binom {n}{ k}}^{2}{\binom {n+k}{k}}^{2}},$

kommer från Apérys bevis på irrationaliteten hos ${\displaystyle \zeta (3)} ,$ beräknar Zeilbergers algoritm det linjära återfallet

$(n+2)^{3}\,a(n+2)-(17n^{2}+51n+39)(2n+3)\,a(n+1)+(n+1)^{3}\,a(n)=0.$

Med tanke på denna upprepning returnerar inte algoritmen någon hypergeometrisk lösning, vilket bevisar att $a(n)$ inte förenklas till en hypergeometrisk term .