RISC JKU

Positivity C-finite sequences

This website accompanies the paper A comparison of algorithms for proving positivity of linearly recurrent sequences by Philipp Nuspl and Veronika Pillwein.

Packages

The package rec_sequences implements many of the algorithms presented in the paper for SageMath. It can be obtained on GitHub. Instructions for the implementation and the documentation including many examples can also be found there.

The package PositiveSequence is part of the collection of packages RISCErgoSum. It provides implementations of the methods for Mathematica. A demo file can be found at PositiveSequence. The source code can be found on GitHub.

Tests

The algorithms are tested with C-finite sequences that are guessed from terms from sequences listed in the OEIS. This test set consists of the first 1000 sequences where guessing yields a C-finite recurrence and the first 500 terms are strictly positive. Below are the tables with the results from the respective algorithms. The tables contain the following columns:
  1. A-identifier from the OEIS database
  2. List of the coefficients (of the form [c0,...,cr] for a recurrence c0 a(n) + ... + cr a(n+r) = 0)
  3. List of initial values of the sequence (of the form [a(0),...,a(r-1)])
  4. Order of the recurrence r
  5. Squarefreeness of the characteristic polynomial (if False, a shorter D-finite recurrence exists)
  6. Order of the D-finite recurrence satisfied by the sequence
  7. Number of dominant eigenvalues
Note that the recurrences are only guessed. I.e., the respective sequences from the OEIS are ot guaranteed to be actually C-finite. The remaining columns show the runtime (in seconds) for the respective algorithms (given below). The value -1 indicates that the algorithm did not terminate in 60 seconds.

Sage

The experiments were run on a notebook with 32GB RAM and a i7-10610U CPU @ 1.80 GHz using the following algorithms:
  1. Algo 1: Uses Algorithm 1 from [Kauers, Pillwein 2010] as implemented in is_positive_algo1.
  2. Algo 2: Uses Algorithm 2 from [Kauers, Pillwein 2010] as implemented in is_positive_algo2.
  3. Dominant: Uses Algorithm C from the paper as implemented in is_positive_dominant_root.
  4. Dominant decompose: Decomposes the sequence into non-degenerate sequences and uses Algorithm C from the paper on these subsequences as implemented in is_positive_dominant_root_decompose.
  5. Combination: Uses a combination of these algorithms as implemented in is_positive.
> Table of results for SageMath

Mathematica

The experiments were run on a computer with 32GB RAM and a i7-9700 CPU @ 3 GHz using the following algorithms:
  1. Algo 1: Uses Algorithm 1 from [Kauers, Pillwein 2010] as implemented in KPAlgorithm1.
  2. Algo 2: Uses Algorithm 2 from [Kauers, Pillwein 2010] as implemented in KPAlgorithm2.
  3. Dominant Classic: Uses Algorithm C from the paper as implemented in AlgorithmDominantRootClassic.
  4. Dominant CAD: Uses Algorithm P from the paper as implemented in AlgorithmDominantRootCAD.
  5. Decompose Classic: Decomposes the sequence into non-degenerate sequences and uses Algorithm C from the paper on these subsequences as implemented in AlgorithmClassic.
  6. Decompose CAD: Decomposes the sequence into non-degenerate sequences and uses Algorithm P from the paper on these subsequences as implemented in AlgorithmCAD.
  7. PositiveSequence: Uses a combination of these algorithms as implemented in PositiveSequence.
  8. PositiveSequenceLong: Uses a combination of these algorithms as implemented in PositiveSequence with an increased time limit of 12 hours per sequence.
> Table of results for Mathematica