Petkovšek's algorithm: Difference between revisions

Revision as of 08:58, 27 July 2018

Latest revision as of 15:01, 13 September 2021

(8 intermediate revisions by 8 users not shown)

Line 1:

'''Petkovšek's algorithm''' (also '''Hyper''') is a [[computer algebra]] algorithm that computes a basis of [[Hypergeometric identity|hypergeometric terms]] solution of its input [[P-recursive equation|linear recurrence equation with polynomial coefficients]]. Equivalently, it computes a first order right factor of linear [[Differencedifference operator|difference operators]]s with polynomial coefficients. This algorithm was developed by [[Marko Petkovšek]] in his PhD-thesis 1992.<ref name=":0">{{Cite journal|last=Petkovšek|first=Marko|date=1992|title=Hypergeometric solutions of linear recurrences with polynomial coefficients|url=http://linkinghub.elsevier.com/retrieve/pii/0747717192900386|journal=Journal of Symbolic Computation|volume=14|issue=2-32–3|pages=243–264|doi=10.1016/0747-7171(92)90038-6|issn=0747-7171|viadoi-access=free}}</ref> The algorithm is implemented in all the major computer algebra systems.

== Gosper-Petkovšek representation ==

Line 12:

#<math display="inline">\gcd ( b(n), c(n+1))=1</math>.

This representation of <math display="inline">r(n)</math> is called Gosper-Petkovšek normal form. These polynomials can be computed explicitly. This construction of the representation is an essential part of [[Gosper's algorithm]].<ref>{{Cite journal |last=Gosper |first=R. William |date=1978 |title=Decision procedure for indefinite hypergeometric summation|url=https://pdfs.semanticscholar.org/c66e/0beca13f866f748971d18bd39ebdc2b88751.pdf |journal=[[Proc. Natl. Acad. Sci. USA]] |volume=75 |issue=1 |pages=40–42|doi=10.1073/pnas.75.1.40-42 |viapmid=16592483 |pmc=411178 |s2cid=26361864 |doi-access=free }}</ref> Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.<ref name=":0" />

== Algorithm ==

Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence <math display="inline">c(n)</math>. The other polynomials <math display="inline">a(n),b(n)</math> can be taken as the monic factors of the first coefficient polynomial <math display="inline">p_0 (n)</math> resp. the last coefficient polynomial shifted <math display="inline">p_r(n-r+1)</math>. Then <math display="inline">z</math> has to fulfill a certain [[algebraic equation]]. Taking all the possible finitely many triples <math display="inline">(a(n), b(n), z)</math> and computing the corresponding [[Polynomial solutions of P-recursive equations|polynomial solution]] of the transformed recurrence equation <math display="inline">c(n)</math> gives a hypergeometric solution if one exists.<ref name=":0" /><ref name=":1">{{Cite book|url=https://www.math.upenn.edu/~wilf/Downld.html|title=A=B|lastlast1=Petkovšek|firstfirst1=Marko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|others=|year=|isbn=1568810636|___location=|pages=|oclc=33898705}}</ref><ref>{{Cite book|url=https://www.worldcat.org/oclc/701369215|title=The concrete tetrahedron : symbolic sums, recurrence equations, generating functions, asymptotic estimates|lastlast1=Kauers|firstfirst1=Manuel|last2=Paule|first2=Peter|date=2011|publisher=Springer|others=|year=|isbn=9783709104453|___location=Wien|pages=|oclc=701369215}}</ref><p>

In the following pseudocode the degree of a polynomial <math display="inline">p(n) \in \mathbb{K}[n]</math> is denoted by <math display="inline">\deg (p (n))</math> and the coefficient of <math display="inline">n^d</math> is denoted by <math display="inline">\text{coeff} ( p(n), n^d )</math>.</p>

<b>'''algorithm</b>''' petkovsek <b>'''is</b>'''

'''input:''' Linear recurrence equation <math display="inline">\sum_{k=0}^r p_k(n) \, y (n+k) = 0, p_k \in \mathbb{K}[n], p_0, p_r \neq 0</math>.

<b>'''output:</b>''' A hypergeometric solution <math display="inline">y</math> if there are any hypergeometric solutions.

<b>'''for each</b>''' monic divisor <math display="inline">a(n)</math> of <math display="inline">p_0(n)</math> <b>'''do</b>'''

<b>'''for each</b>''' monic divisor <math display="inline">b(n)</math> of <math display="inline">p_r(n-r+1)</math> <b>'''do</b>'''

'''for each''' <math display="inline">k=0,\dots,r</math> '''do'''

<math display="inline">\tilde{p}_k (n)= p_k (n) \prod_{j=0}^{k-1} a(n+j) \prod_{i=k}^{r-1} b(n+i)</math>