Gosper algorithm and Wilf-Zeilberger certificate

[rwst]

Pynac-0.7.3 introduces Gosper's hypergeometric summation algorithm. The ticket will implement the interface and add an extensive test file. Later tickets may call the function before delegating unsolved sums to Maxima.

Also, the WZ certificate can be computed to prove hypergeometric identities.

The test file has one test marked as known bug. Its resolution depends on handling of expressions with algebraic coefficients (i.e. manipulations of polynomials over algebraic fields).

Pynac-0.7.5 adds a crucial improvement and a faster implementation.

Depends on #22174
Depends on #22364

Component: symbolics

Author: Ralf Stephan

Branch/Commit: 70462e2

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/22090

[rwst]

Branch: u/rws/gosper_algorithm

[sagetrac-git]

Commit: 5003327

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dda7f2d	Merge branch 'develop' into t/22090/gosper_algorithm
5003327	22090: test file

[rwst]

Author: Ralf Stephan

[rwst]

Changed dependencies from #19461, pynac-0.7.3 to #19461, #22136

[rwst]

comment:6

I concede that we don't need really need #19461.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0e48511	22136: pkg version/chksum
c636059	Merge branch 't/22136/upgrade_to_pynac_0_7_3' into t/22090/gosper_algorithm
17c5e40	22090: fixes

[sagetrac-git]

Changed commit from 5003327 to 17c5e40

[rwst]

comment:8

Still missing is better documentation. As to performance 75% of complicated summations are spent in computation of one symbolic matrix determinant, of which 2/3 is expansions. It is astonishing that the 12x12 matrix determinant from the summation of (((n<sup>4-14*n</sup>2-24*n-9) * 2^n / n^2 / (n+1)^2 / (n+2)^2 / (n+3)^2)) needs 4,316 first level expansions, even with the supposedly optimized "enhanced Laplace-expansion" determinant algorithm used. Resultants should be later computed in Pynac via Singular which apparently uses a subresultant algorithm.

[rwst]

Changed dependencies from #19461, #22136 to none

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

88224d4	Merge branch 'develop' into t/22090/gosper_algorithm
7394ee1	22090: documentation

[sagetrac-git]

Changed commit from 17c5e40 to 7394ee1

[dimpase]

comment:10

How does one "delegate to Maxima"? Does it do these "known bugs" cases?

[rwst]

comment:11

Gosper summation is a subset of summation, i.e., it can handle only hypergeometric expressions (or sums of such). If one wants to use it in sum then if gosper_sum can't solve it, we would call Maxima's sum. The known bugs using Maxima's sum:

sage: (1 / (n^2 + sqrt(5)*n - 1)).sum(n,0,m)
-1/3*(m^3*(3*sqrt(5) - 7) - 3*m^2*(sqrt(5) - 1) - 2*m*(3*sqrt(5) - 2) - 6)/(m^3*(sqrt(5) - 3) - 3*m^2*(sqrt(5) - 1) - m*(sqrt(5) + 3) - 2)
sage: ((n*(n+a+b)*a^n*b^n)/factorial(n+a)/factorial(n+b)).sum(n,1,m)
-(a^(m + 1)*b^(m + 1)*factorial(a + 1)*factorial(b + 1) - ((a^2 + a)*b^2 + (a^2 + a)*b)*factorial(a + m)*factorial(b + m))/(factorial(a + m)*factorial(a + 1)*factorial(b + m)*factorial(b + 1))
sage: F(n, k) = binomial(n,k) * factorial(n) / factorial(k) / factorial(a-k) / f
....: actorial(a+n)
sage: (F(n+1, k) - F(n, k)).sum(k,0,m)
-sum(-(binomial(n + 1, k)*factorial(a + n)*factorial(n + 1) - binomial(n, k)*factorial(a + n + 1)*factorial(n))/(factorial(a - k)*factorial(k)), k, 0, m)/(factorial(a + n + 1)*factorial(a + n))

The last is clearly not solved. The first two seem correct.

I do not claim to add new functionality with this, just the starting point for speed optimizations and for Wilf-Zeilberger, which WOULD be new functionality.

[sagetrac-git]

Changed commit from 7394ee1 to e74a414

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4f4a8b5	Merge branch 'develop' into t/22090/gosper_algorithm
648e498	22174: Interface expression conversion to gamma() and normalization
29446a0	Merge branch 'u/rws/interface_expression_conversion_to_gamma___and_normalization' of git://trac.sagemath.org/sage into t/22090/gosper_algorithm
5b729ed	Merge branch 'develop' into t/22090/gosper_algorithm
11951c8	22219: pkg version/chksum
91973f1	22219: giac usage is GO
a178a75	22219: doctest fixes
c7eb7ff	Merge branch 'develop' into t/22219/upgrade_to_pynac_0_7_4
5fdc5ff	Merge branch 't/22219/upgrade_to_pynac_0_7_4' into t/22090/gosper_algorithm
e74a414	22090: add gosper_term and WZ_certificate

[rwst]

Dependencies: pynac-0.7.5

[rwst]

Changed dependencies from #22174, pynac-0.7.5 to #22174, #22364

[sagetrac-git]

Changed commit from 8b0684e to e7eddf7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

46697e0	pkg version/chksum
e7eddf7	Merge branch 'u/rws/upgrade_to_pynac_0_7_5' of git://trac.sagemath.org/sage into t/22090/gosper_algorithm

[fchapoton]

comment:25

there is a wrong INPUT:: (should be INPUT: with no indentation on the next lines)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5477616	Merge branch 'develop' into t/22090/gosper_algorithm
f307a8a	22090: doc fix

[sagetrac-git]

Changed commit from e7eddf7 to f307a8a

[fchapoton]

comment:27

doc (still) does not build

+[dochtml] OSError: [calculus ] docstring of sage.symbolic.expression.Expression.gosper_sum:7: WARNING: Bullet list ends without a blank line; unexpected unindent.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6c1cec1	Merge branch 'develop' into t/22090/gosper_algorithm
405c107	22090: cosmetics

[sagetrac-git]

Changed commit from f307a8a to 405c107

[fchapoton]

comment:29

• you should de-indent the paragraphs after INPUT:

• {n \choose k} is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead \binom{n}{k}

[sagetrac-git]

Changed commit from 405c107 to 87714b4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

87714b4

22090: cosmetics

[rwst]

comment:31

Replying to @fchapoton:

• {n \choose k} is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead \binom{n}{k}

Done. Does that plugin also check the output of Sage itself?

sage: latex(binomial(n,k))
{n \choose k}

[rwst]

Changed branch from u/rws/gosper_algorithm to u/rws/22090

[rwst]

comment:33

Squashed, rebased, and fixed doctest continuation.

---

New commits:

f089c13

22090: Gosper algorithm and Wilf-Zeilberger certificate

[rwst]

Changed commit from 87714b4 to f089c13

[fchapoton]

comment:34

• there is a .. MATH block start that is missing a blank line just after it

otherwise, looks good to me. You can set a positive review once the minor change above is done.

[fchapoton]

Reviewer: Frédéric Chapoton

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

70462e2

22090: cosmetics

[sagetrac-git]

Changed commit from f089c13 to 70462e2

[rwst]

comment:37

Thanks for the review!

[vbraun]

Changed branch from u/rws/22090 to 70462e2