Gosper algorithm and Wilf-Zeilberger certificate

[rws]

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.

[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

[rws]

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

[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

[rws]

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^4-14*n^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.

[git]

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

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

[dimpase]

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

[rws]

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.

[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

[git]

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

​2ef02d4

22090: improvements, stress testing

[git]

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

​32d1ca4

22090: more tests in gosper-sum.py

[dimpase]

Is pynac-0.7.5 a dependence? Is there a ticket for it that should be referred to? Otherwise it's not clear how this can be reviewed.

[git]

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

​fd5ec4d	Merge branch 'develop' into t/22090/gosper_algorithm
​8b0684e	Merge branch 'develop' into t/22090/gosper_algorithm

[rws]

Pynac-0.7.5 is a dependence to make all doctests work. What you could already review is the Python interface code and the correctness of the doctests.

[dimpase]

Do you mean to say that 0.7.5 isn't even on trac yet?

[rws]

I'm still introducing new code and fleshing out bugs in Pynac master. Trying to implement a complex algorithm has been a big benefit for Pynac already.

[rws]

Anyway, current Pynac git passes all doctests in 7 seconds, so I'll prepare a release.

[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

[chapoton]

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

[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

[chapoton]

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.

[git]

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

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

[chapoton]

• 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}

[git]

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

​87714b4

22090: cosmetics

[rws]

Replying to chapoton:

• {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}

[rws]

Squashed, rebased, and fixed doctest continuation.

---

New commits:

​f089c13

22090: Gosper algorithm and Wilf-Zeilberger certificate

[chapoton]

• 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.

[git]

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

​70462e2

22090: cosmetics

[rws]

Thanks for the review!