Inverse Zeibelger Problem

Inverse Zeibelger Problem in Sage

pseries_basis is a SageMath package that allow to transform linear operators to compute definite-sum solutions of differential or recurrence equations.

This package is based on the work of the following research articles:

  • A. Jiménez-Pastor, M. Petkovšek: The factorial-basis method for finding definite-sum solutions of linear recurrences with polynomial coefficients. arXiv:2202.05550 (under revision in Journal of Symbolic Computation).

Some information about the module

Main use-case

Let \(\mathbb{K}\) be a computable field and consider \(\mathbb{K}[[x]]\) its ring of formal power series. The problem of creative telescoping can be stated as follows: let \(F(x,n)\) be a function. Is there any linear operator that annihilates the sum \(\sum_n F(x,n)\)?

Solving this problem is equivalent to find an operator \(L\) acting only on \(x\) and a function \(G(x,n)\) (called a certificate) such that:

\[L \cdot F(x,n) = G(x, n+1) - G(x,n),\]

since once we have this telescoping equation for \(F(x,n)\) we can then sum-up w.r.t. \(n\) obtaining the equation

\[L \cdot \sum_n F(x,n) = 0.``\]

There are many studies with respect to this problem and, in fact, it has been solved in many cases. This package, however, tries to solved a somehow inverse problem:

Problem: let \(L\) be a linear operator and \(K(x,n)\) be a kernel. Compute a new operator \(\tilde{L}\) such that for any solution of the form \(f(x) = \sum_n a_nK(x,n)\) to \(L \cdot f(x) = 0\), we have

\[\tilde{L} \cdot a_n = 0.``\]

This is a partial solution to the more general case of Inverse Zeilberger Problem:

Inverse Zeilberger Problem: let \(L\) be a linear operator. Find all the possible solutions that can be express as a definite-sum in such a way that Zeilberger algorithm will succeed.

Installation

This package can be installed, used, modified and distributed freely under the conditions of the GNU General Public License v3.

There are two different ways of installing the package into your SageMath distribution:

Install from source code

The package can be obtained from the public git repository on GitHub: * from the repository: GitHub: Antonio-JP/pseries_basis for the webpage view, * or by cloning the repository using https: GitHub: Antonio-JP/pseries_basis.git, * or downloading the latest version: GitHub: Antonio-JP/pseries_basis/archive/master.zip.

After cloning or downloading the source code, you may install it by running the following command line from the main folder of the repository:

$ make install

Install via pip

Another option to install this package is to use the pip functionality within SageMath. This will install the latest stable version of the package and will take care of any dependencies that may be required.

To install it via pip, run the following in a terminal where sage can be executed:

$ sage -pip install [--user] git+https://github.com/Antonio-JP/pseries_basis.git

The optional argument –user allows to install the package just for the current user instead of a global installation.

Loading the package

Once installed, the full functionality of the package can be used after importing it with the command:

sage: from pseries_basis import *

Examples of use

This package is based on the concept of compatibility of a basis with a linear operator (see the main paper for a proper definition). The bases can be obtained in several ways and they usually include a set of operator they are compatible with. For example, consider the binomial basis \(P_n(x) = \binom{x}{n}\). It is well known that for \(n\in\mathbb{N}\), \(P_n(x)\) is a polynomial of degree \(n\). We can create this basis easily:

sage: B = BinomialBasis
sage: B
Basis of Sequences over Rational Field: (binomial(n, k))
sage: [el.generic() for el in B[:3]]
[1, n, 1/2*n^2 - 1/2*n]

We can also create basis using the idea of a falling factorial:

sage: F = FallingBasis(1,0,1)
sage: F
Basis of Sequences over Rational Field: (1, n, n^2 - n, n^3 - 3*n^2 + 2*n, n^4 - 6*n^3 + 11*n^2 - 6*n,...)
sage: [el.generic() for el in F[:3]]
[1, n, n^2 - n]
sage: F.rho[:10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

There are plenty of methods to check compatibility with a basis. We refer to the documentation for further information.

Dependencies

This package has been developed on top of SageMath and depends on the following packages:

Package under active development

This package is still under an active development and further features will be included in future version of the code. This means that several bugs may exist or appear. We would thank anyone that, after detecting any error, would post it in the issues page (GitHub: Antonio-JP/pseries_basis/issues) of the repository using the label bug (GitHub: github/docs/labels/bug).

Moreover, any requested feature can be post in the issues page (GitHub: Antonio-JP/pseries_basis/issues) of the repository using the label enhancement (GitHub: github/docs/labels/enhancement).

Acknowledgements

This package has been developed with the financial support of the following institutions:

  • The Austrian Science Fund (FWF): by W1214-N15, project DK15.

  • The Oberösterreich region: by the Innovatives OÖ-2010 plus program.

  • The Île-de-France region: by the project “XOR”.

  • The Poul Due Jensen Foundation: grant 883901.

pseries_basis.pseries_bases_version()

Method to obtain the current version of the installed package pseries_basis.

Submodules

Indices and Tables