Content deleted Content added
No edit summary |
Citation bot (talk | contribs) Add: doi-access, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 625/924 |
||
| (13 intermediate revisions by 11 users not shown) | |||
Line 1:
'''Petkovšek's algorithm''' (also '''Hyper''') is a [[computer algebra]] algorithm that computes a basis of [[
== Gosper-Petkovšek representation ==
== Examples ==▼
Let <math display="inline">\mathbb{K}</math> be a [[Field (mathematics)|field]] of [[Characteristic (algebra)|characteristic]] zero. A nonzero sequence <math display="inline">y(n)</math> is called hypergeometric if the ratio of two consecutive terms is [[Rational function|rational]], i.e. <math display="inline">y (n+1) /y(n) \in \mathbb{K}(n)</math>. The Petkovšek algorithm uses as key concept that this rational function has a specific representation, namely the ''Gosper-Petkovšek normal form''. Let <math display="inline">r(n) \in \mathbb{K}[n]</math> be a nonzero rational function. Then there exist monic [[Ring of polynomial functions|polynomials]] <math display="inline">a, b, c \in \mathbb{K} [n]</math> and <math display="inline">0 \neq z \in \mathbb{K}</math> such that
and
#<math display="inline">\gcd (a(n), b(n+k)) = 1</math> for every nonnegative integer <math display="inline">k \in \N</math>,
#<math display="inline">\gcd (a(n), c(n))=1</math> and
#<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 |journal=[[Proc. Natl. Acad. Sci. USA]] |volume=75 |issue=1 |pages=40–42|doi=10.1073/pnas.75.1.40 |pmid=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 ==
* Given the sum▼
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|last1=Petkovšek|first1=Marko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|isbn=1568810636|oclc=33898705}}</ref><ref>{{Cite book|title=The concrete tetrahedron : symbolic sums, recurrence equations, generating functions, asymptotic estimates|last1=Kauers|first1=Manuel|last2=Paule|first2=Peter|date=2011|publisher=Springer|isbn=9783709104453|___location=Wien|oclc=701369215}}</ref>
:<math>a(n)=\sum_{k=0}^n{\binom{n}{k}^2\binom{n+k}{k}^2},</math>▼
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>.
coming from [[Roger Apéry|Apéry]]'s proof of the irrationality of <math>\zeta(3)</math>, [[Doron Zeilberger|Zeilberger]]'s algorithm computes the linear recurrence▼
'''algorithm''' petkovsek '''is'''
:<math>(n+2)^3a(n+2)-(17n^2+51n+39)(2n+3)a(n+1)+(n+1)^3a(n)=0.</math>▼
'''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>.
'''output:''' A hypergeometric solution <math display="inline">y</math> if there are any hypergeometric solutions.
'''for each''' monic divisor <math display="inline">a(n)</math> of <math display="inline">p_0(n)</math> '''do'''
'''for each''' monic divisor <math display="inline">b(n)</math> of <math display="inline">p_r(n-r+1)</math> '''do'''
'''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>
<math display="inline">d = \max_{k=0,\dots,r} \deg (\tilde{p}_k (n))</math>
'''for each''' root <math display="inline">z</math> of <math display="inline">\sum_{k=0}^r \text{coeff} (\tilde{p}_k (n), n^d ) z^k</math> '''do'''
Find non-zero polynomial solution <math display="inline">c(n)</math> of <math display="inline">\sum_{k=0}^r z^k \,\tilde{p}_k(n) \, c(n+k)=0</math>
'''if''' such a non-zero solution <math display="inline">c(n)</math> exists '''then'''
<math display="inline">r(n)=z \, a(n)/b(n) \, c(n+1)/c(n)</math>
'''return''' a non-zero solution <math display="inline">y (n)</math> of <math display="inline">y (n+1) = r(n) \, y (n)</math>
If one does not end if a solution is found it is possible to combine all hypergeometric solutions to get a general hypergeometric solution of the recurrence equation, i.e. a generating set for the kernel of the recurrence equation in the linear span of hypergeometric sequences.<ref name=":0" />
Petkovšek also showed how the inhomogeneous problem can be solved. He considered the case where the right-hand side of the recurrence equation is a sum of hypergeometric sequences. After grouping together certain hypergeometric sequences of the right-hand side, for each of those groups a certain recurrence equation is solved for a rational solution. These rational solutions can be combined to get a particular solution of the inhomogeneous equation. Together with the general solution of the homogeneous problem this gives the general solution of the inhomogeneous problem.<ref name=":0" />
▲== Examples ==
=== Signed permutation matrices ===
The number of [[Generalized permutation matrix|signed permutation matrices]] of size <math display="inline">n \times n</math> can be described by the sequence <math display="inline">y(n)</math> which is determined by the recurrence equation<math display="block">4 (n+1)^2 \, y(n) + 2 \, y(n+1) + (-1) \, y(n+2) = 0</math>over <math display="inline">\Q</math>. Taking <math display="inline">a(n) = n+1,b(n)=1</math> as monic divisors of <math display="inline">p_0 (n) = 4(n+1)^2, p_2(n) = -1</math> respectively, one gets <math display="inline">z = \pm 2</math>. For <math display="inline">z=2</math> the corresponding recurrence equation which is solved in Petkovšek's algorithm is<math display="block">4(n+1)^2 \, c(n) + 4(n+1)\, c(n+1) - 4(n+1)(n+2) \, c(n+2) = 0.</math>This recurrence equation has the polynomial solution <math display="inline">c(n) = c_0 </math> for an arbitrary <math display="inline">c_0 \in \Q</math>. Hence <math display="inline">r(n)=2 (n+1)</math> and <math display="inline">y(n) = 2^n \, n!</math> is a hypergeometric solution. In fact it is (up to a constant) the only hypergeometric solution and describes the number of signed permutation matrices.<ref>{{Cite web|url=https://oeis.org/A000165|title=A000165 - OEIS|website=oeis.org|access-date=2018-07-02}}</ref>
=== Irrationality of <math>\zeta(3)</math> ===
▲: <math>a(n)=\sum_{k=0}^n{\binom{n}{k}^2\binom{n+k}{k}^2},</math>
▲coming from [[Roger Apéry|Apéry]]'s proof of the irrationality of <math>\zeta(3)</math>, [[Doron Zeilberger|Zeilberger]]'s algorithm computes the linear recurrence
Given this recurrence, the algorithm does not return any hypergeometric solution, which '''proves''' that <math>a(n)</math> does not simplify to a [[hypergeometric identity|hypergeometric term]].▼
▲Given this recurrence, the algorithm does not return any hypergeometric solution, which
== References ==
<references />
{{DEFAULTSORT:Petkovsek's algorithm}}
| |||