rec_sequences: A Sage package

Introduction

This SageMath package provides a framework to work with sequences satisfying linear recurrence equations.

• In the simple case, these are sequences satisfying recurrences with constant coefficients (so called \(C\)-finite sequences) or polynomial coefficients (so called \(D\)-finite sequences). The implementation of these sequences is based on the ore_algebra package (cf. [KJJ15]).

• From these simple sequences one can create more complicated sequences, e.g. sequences satisfying a linear recurrence with \(C\)-finite coefficients, so called \(C^2\)-finite sequences (cf. [JPNP21a], [JPNP21b])..

• The package furthermore provides methods to show inequalities of \(C\)-finite and \(D\)-finite sequences based on the Gerhold-Kauers method and methods based on arbitrary precision computations (cf. [GK05], [KP10], [NP22]).

A tutorial for the package can be found below and in [N22].

The package is developed by Philipp Nuspl and published under the GNU General Public License v3.0. The research is funded by the Austrian Science Fund (FWF): W1214-N15, project DK15.

Installation

The package depends on the ore_algebra package. Several methods are available to install the rec_sequences package:

1. Using sage pip one can install the package using

   sage --pip install git+https://github.com/PhilippNuspl/rec_sequences.git
   

   This assumes that Sage was built from sources or installed from official packages. The command will also automatically install the ore_algebra package. The flag --user can be used for a user local installation.

2. One can clone the repository and run make install in the main directory of the repository. Again, this will automatically install the ore_algebra package.

3. One can move the folder rec_sequences containing the sources to a directory where Sage can find it. Then, ore_algebra has to be installed separately.

In any case, for showing inequalities the optional Sage package qepcad is used. This can usually be installed using

sage -i qepcad

The rec_sequences package was developed under Sage 9.4. However, the package should also run under older Sage versions (Sage 8.7 or more recent).

Examples

After the installation, the modules can be imported. Here, we want to compute with \(C\)-finite and \(C^2\)-finite sequences and import the corresponding modules:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: from rec_sequences.C2FiniteSequenceRing import *

Before we can specify specific sequences, we have to create the rings where these sequences will live:

sage: C = CFiniteSequenceRing(QQ)
sage: C2 = C2FiniteSequenceRing(QQ)

Now, we can already specify some \(C\)-finite sequences, e.g. by giving the recurrence or by using some symbolic expression:

sage: fib = C([1,1,-1], [0,1], name="f")
sage: fib
C-finite sequence f(n): (1)*f(n) + (1)*f(n+1) + (-1)*f(n+2) = 0 and f(0)=0 , f(1)=1
sage: var("n")
sage: alt = C((-1)^n)
sage: alt
C-finite sequence a(n): (1)*a(n) + (1)*a(n+1) = 0 and a(0)=1

Using these sequences, we can already extract terms, perform computations and check identities (like Cassini's identity here):

sage: fib[:10]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
sage: alt[5]
-1
sage: c = fib+alt
sage: c.order()
3
sage: fib.shift(-1)*fib.shift(1) - fib^2 == alt
True

Furthermore, using the Gerhold-Kauers method ([GK05], [KP10]) we can check termwise inequalities for \(C\)-finite (or \(D\)-finite) sequences:

sage: fib > 0
False
sage: fib.sum() <= 2*fib
False
sage: fib.sum() <= 3*fib
True

For more information one can check out the documentation rec_sequences.CFiniteSequenceRing and rec_sequences.DFiniteSequenceRing (its superclass).

Now, we can also define \(C^2\)-finite sequences. Using closure properties we can for instance check whether a certain recurrence is really satisfied by the subsequence \(f(n^2)\) of the Fibonacci sequence \(f(n)\):

sage: sparse_fib = fib.sparse_subsequence(C2)
sage: sparse_fib[:10]
[0, 1, 3, 34, 987, 75025, 14930352, 7778742049]
sage: sparse_fib.order(), sparse_fib.degree()
(2, 2)
sage: d = C([1, -54, 331, -54, 1], [136, 6710, 317434, 14927768])
sage: sparse_fib2 = C2([-fib.subsequence(6,11),-d,fib.subsequence(6,9), 1],
....:                  [0, 1, 3])
sage: sparse_fib == sparse_fib2
True

For more information one can check out the documentation rec_sequences.C2FiniteSequenceRing and rec_sequences.DifferenceDefinableSequenceRing (its superclass).

Module documentations

Here, the detailed documentation of all modules can be found.

Base rings

\(C\)-finite and \(D\)-finite sequence rings, based on the ore_algebra, package are implemented. They can serve as the base rings for creating more complicated rings. All sequence rings are derived from RecurrenceSequenceRing which provides common functionality for all sequence rings where a sequence is defined by a linear recurrence equation.

• RecurrenceSequenceElement and RecurrenceSequenceRing
• CFiniteSequence and CFiniteSequenceRing
• DFiniteSequence and DFiniteSequenceRing

Difference definable rings

Using the \(C\)-finite and \(D\)-finite sequence base rings we can create more complicated rings. Namely, rings of sequences which are defined by linear recurrences with coefficients in one of these base rings. The class DifferenceDefinableSequenceRing allows to create these rings. A special kind of such a ring, is the ring of \(C^2\)-finite sequences. Such a ring contains sequences satisfying a linear recurrence with \(C\)-finite coefficients. The special class C2FiniteSequenceRing contains several additional functionalities for this ring, including the computation of generating functions and a basic guessing routine.

• DifferenceDefinableSequence and DifferenceDefinableSequenceRing
• C2FiniteSequence and C2FiniteSequenceRing

Arithmetic Progressions and Zero Patterns

The package provides functionalities to compute zeros and sign patterns of sequences. The class ArithmeticProgression encapsulates functionality to work with arithmetic progressions. By the Skolem-Mahler-Lech theorem, the zeros of a \(C\)-finite sequence is a finite set together with a finite number of arithmetic progressions. Such sets of zeros can be handled using the class ZeroPattern. Similarly, SignPattern provides a framework to work with a sign pattern of a sequence which is cyclic from some term on.

• ArithmeticProgression
• ZeroPattern
• SignPattern

Bounded Sequences

\(C^2\)-finite sequences which are defined by a linear recurrence with coefficients being \(C\)-finite sequences where the leading coefficient is allowed to have finitely many zeros are defined in the ring C2FiniteSequenceRingBounded. This definition allows us to find bounds for the orders of closure properties and lets us compute these closure properties in a different more classical ways. For this, there is also an implementation of Ge’s algorithm for computing the exponent lattice of algebraic numbers in the class IntegerRelations.

• C2FiniteSequenceBounded and C2FiniteSequenceRingBounded
• IntegerRelations

Additional Modules

The following modules contain auxiliary methods. The class LinearSolveSequence provides methods to solve linear systems of equations over sequence rings. The class SequenceRingOfFraction provides a ring structure for sequences which can be defined as the quotient of two sequences. The class FunctionalEquation represents equations satisfied by the generating functions of \(C^2\)-finite sequences. Finally, utility contains various other auxiliary methods.

• LinearSolveSequence
• FunctionalEquation
• FractionSequence and SequenceRingOfFraction
• FractionFieldSequence and SequenceFieldOfFraction
• utility

References

GK05(1,2)

Stefan Gerhold, Manuel Kauers: A Procedure for Proving Special Function Inequalities Involving a Discrete Parameter. In: Proceedings of ISSAC’05, pp. 156-162. 2005.

KP10(1,2)

Manuel Kauers, Veronika Pillwein: When can we detect that a P-finite sequence is positive? In: Proceedings of ISSAC’10, pp. 195-202. 2010.

OW14

Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In: Proceedings of SODA 14. 2014

F14

Paolo Faccin. Computational problems in algebra: units in group rings and subalgebras of real simple Lie algebras. PhD thesis. University of Trento. 2014

KJJ15

Manuel Kauers, Maximilian Jaroschek, Frederik Johansson: Ore Polynomials in Sage. In: Computer Algebra and Polynomials. Lecture Notes in Computer Science. 2015

AKKOW21

Shaull Almagor, Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell. 2021. Deciding ω-regular properties on linear recurrence sequences. Proc. ACM Program. Lang. 5, POPL, Article 48 (January 2021)

JPNP21a

Antonio Jiménez-Pastor, Philipp Nuspl, Veronika Pillwein: An extension of holonomic sequences: \(C^2\)-finite sequences. In: J. Symb. Comput. 116, pp.400-424, 2023, doi: 10.1016/j.jsc.2022.10.008

JPNP21b

Antonio Jiménez-Pastor, Philipp Nuspl, Veronika Pillwein: On \(C^2\)-finite sequences. In: Proceedings of ISSAC’21, pp. 217-224. 2021. preprint

NP22

Philipp Nuspl, Veronika Pillwein: A Comparison of Algorithms for Proving Positivity of Linearly Recurrent Sequences. In: Proceedings of CASC 2022, pp. 268-287. 2022, doi: 10.1007/978-3-031-14788-3_15

N22

Philipp Nuspl: \(C\)-finite and \(C^2\)-finite Sequences in SageMath. In: Software Presentation at ISSAC 2022, doi: 10.35011/risc.22-06

Indices and tables

• Index

• Module Index

• Search Page