implement CFiniteSequence

[rwst]

The upcoming inclusion of ore_algebra will provide the means for a PFiniteSequence class. Nevertheless a lightweight implementation of CFiniteSequence has its place in Sage, and it is available now.

The interface:

• constructed from generating function or recurrence
• guessed from sequence
• provides gf, recurrence, sequence, so practically a conversion between all three
• other: textual description of recurrence, sequence iterator

Possible extensions, not implemented: output of egf, power sum closed form

CC: @burcin @mezzarobba @VivianePons

Component: combinatorics

Keywords: recurrence, sequence, ogf

Author: Ralf Stephan, Viviane Pons

Branch/Commit: 84c909d

Reviewer: Ralf Stephan, Viviane Pons

Issue created by migration from https://trac.sagemath.org/ticket/15714

[rwst]

Branch: u/rws/ticket/15714

[rwst]

comment:4

Please comment on the interface/documentation

---

New commits:

9d8a0eb

skeleton interface

[rwst]

Commit: 9d8a0eb

[sagetrac-git]

Changed commit from 9d8a0eb to 70a29e1

[sagetrac-git]

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

70a29e1

core functionality

[sagetrac-git]

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

6df1fc6

guess(), random_element(), some refactoring

[sagetrac-git]

Changed commit from 70a29e1 to 6df1fc6

[sagetrac-git]

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

9095be0

ref doc completed; coefficients(), slicing added

[sagetrac-git]

Changed commit from 6df1fc6 to 9095be0

[sagetrac-git]

Changed commit from 9095be0 to f73e11e

[sagetrac-git]

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

f73e11e

handle ogf > 1

[rwst]

Changed keywords from recurrence ogf to recurrence, sequence, ogf

[rwst]

Author: rws

[mezzarobba]

comment:13

Some more comments:

• Your code is apparently limited to sequences with integer or rational coefficients. IMHO it would be best to handle C-finite sequences over arbitrary rings (or perhaps integral domains?). If you don't want to do that, the scope of the code should be clearly documented and there should be a few checks in suitable places^[1].
• How about making CFiniteSequences Elements of a proper Parent? Sure, it is not absolutely essential at this point, but that's something we will certainly want in the long run—C-finite sequences [over a given ring] form a ring!—, and designing a suitable interface from the start would save the trouble of deprecating the current one later on!
• If you do implement a "ring of C-Finite sequences over ...", I'd suggest moving it outside of combinat (perhaps to a new package sage.rings.sequences?).

[1] Currently, the following examples all behave differently:

sage: R.<x> = RR[]; fibo = CFiniteSequence(x/(1-x-x^2)); fibo[10]
55
sage: R.<x> = GF(3)[]; fibo = CFiniteSequence(x/(1-x-x^2)); fibo[10]
...
ValueError: Cannot convert to CFiniteSequence.
sage: R.<x> = CC[]; fibo = CFiniteSequence(x/(1-x-x^2)); fibo[10]
...
TypeError: Unable to coerce 0.000000000000000 (<type 'sage.rings.complex_number.ComplexNumber'>) to Rational

Their behaviour is not entirely unreasonable, but it only makes sense if you know that CFiniteSequence is going to try converting the input to a rational fraction over QQ.

[sagetrac-git]

Changed commit from f73e11e to a2d5116

[sagetrac-git]

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

e7958b0	Merge branch 'ticket/15714' into develop
21fbcca	move to rings/, allow 1/x, subclass from FractionFieldElement
8a1b3a4	add, sub functions
d69aaac	mul, div
a62b72c	be specific about base ring, more doctests
ffea32f	Merge branch 'develop' into ticket/15714
9ee1a05	specify applicability, handle constants, more doctests, better documentation
4218ac8	Merge branch 'develop' into ticket/15714
03f82ba	use pari script default for guessing; safeguards in ctor
a2d5116	last doctests, fix documentation

[VivianePons]

comment:43

I have changed the architecture so that C-Finite Sequences are no longer sub classes of fraction field elements. Instead, they just store the ogf and belong to their own ring with a proper parent and everything.

I think the new implementation is much cleaner and it's addressing the issues that had been raised before: the behavior and coercions are much more consistent.

Also, it actually makes things easy for the user as you can write directly

sage: CFiniteSequence(1+x)
Finite sequence [1, 1], offset = 0

even if x is a symbolic variable, it gets transformed into a proper fraction field element and the result still has the right parent and everything.

Someone can start reviewing my changes, rws I guess and also mmezzarobba (or whoever wants to look at it).

I still haven't recompiled the doc but I will do shortly.

[VivianePons]

Changed author from Ralf Stephan to Ralf Stephan, Viviane Pons

[sagetrac-git]

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

f1eebe7

Fixing doc and tests

[sagetrac-git]

Changed commit from 504eb03 to f1eebe7

[sagetrac-git]

Changed commit from f1eebe7 to a31adf7

[sagetrac-git]

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

f8906ca	Merge branch 'develop' into t/15714/public/ticket/15714
a31adf7	15714: fix shortcomings of default guessing method

[rwst]

comment:46

Nice work! I think this is fine. So someone just needs to look over this last commit, where I fixed the default guessing method. Also, since you while adapting the original code also reviewed it, you should insert your name in the Reviewers field.

Having this finally in mainstream Sage would motivate me to complete the already existing code for automated closed form output.

[rwst]

Reviewer: Ralf Stephan

[fchapoton]

comment:47

Luca should be Lucas, I think.

I have also noted some alignement problems at the beginning of
class CFiniteSequence(FieldElement)

[sagetrac-git]

Changed commit from a31adf7 to a0aba76

[sagetrac-git]

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

a0aba76

15714: cosmetics

[fchapoton]

comment:49

please use ....: for doctest continuation (see patchbot report)

[sagetrac-git]

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

f81de8b

15714: cosmetics

[sagetrac-git]

Changed commit from a0aba76 to f81de8b

[sagetrac-git]

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

84c909d

Fixing a doc output

[sagetrac-git]

Changed commit from f81de8b to 84c909d

[VivianePons]

comment:52

I've recompiled the doc and tests and everything seems fine now. The problems reported by Chapoton have been fixed. From my point of view, this is all good. Maybe someone else could give green flag? Anyway, if nobody complains in the near future, I'll move this to positive review.

[rwst]

comment:53

As you are positive, and your own last commit is fine, and a recent patchbot run passed, I'll set positive myself. Please add yourself to the reviewers, too. Marc?

[VivianePons]

Changed reviewer from Ralf Stephan to Ralf Stephan, Viviane Pons

[mezzarobba]

comment:55

Replying to @rwst:

As you are positive, and your own last commit is fine, and a recent patchbot run passed, I'll set positive myself. Please add yourself to the reviewers, too. Marc?

Sorry, I don't have time to have a look now. But if you both are happy with the current code, I guess all is fine!

[vbraun]

Changed branch from public/ticket/15714 to 84c909d