=================================== 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. .. |ore_algebra| replace:: ``ore_algebra`` .. _ore_algebra: https://github.com/mkauers/ore\_algebra 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 :class:`rec_sequences.CFiniteSequenceRing` and :class:`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 :class:`rec_sequences.C2FiniteSequenceRing` and :class:`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. .. toctree:: :maxdepth: 1 modules_docs/RecurrenceSequenceRing modules_docs/CFiniteSequenceRing modules_docs/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. .. toctree:: :maxdepth: 1 modules_docs/DifferenceDefinableSequenceRing modules_docs/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. .. toctree:: :maxdepth: 1 modules_docs/ArithmeticProgression modules_docs/ZeroPattern modules_docs/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``. .. toctree:: :maxdepth: 1 modules_docs/C2FiniteSequenceRingBounded modules_docs/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. .. toctree:: :maxdepth: 1 modules_docs/LinearSolveSequence modules_docs/FunctionalEquation modules_docs/SequenceRingOfFraction modules_docs/SequenceFieldOfFraction modules_docs/utility References ------------ .. [GK05] 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] 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 ================== * :ref:`genindex` * :ref:`modindex` * :ref:`search`