Off-by-one error in CFiniteSequence slices

[seragunn]

I was trying to calculate the finite differences of http://oeis.org/A000127 as follows:

C.<x> = CFiniteSequences(QQ)
S = C.guess([1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794, 1093])
X = C(x)

S[0:10]         # [ 1, 2, 4, 8, 16, 31, 57, 99, 163, 256 ]
(X*S)[0:10]     # [ 0, 1, 2, 4, 8, 16, 31, 31, 57, 99 ]
(S - X*S)[0:10] # [ 1, 1, 2, 4, 8, 26, 42, 64, 93, 130 ]

f(n) = (S - X*S).closed_form()
[f(n) for n in range(10)] # [ 0, 1, 2, 4, 8, 15, 26, 42, 64, 93 ]

For some reason, the slice operator is skipping S[5] = 15 and yielding 26 instead. Here is the sequence in recurrence form:

T = C.from_recurrence([-1,4,-6,4],[1,1,2,4,8])
T == S - X*S # True
4 * T[4] - 6 * T[3] + 4 * T[2] - T[1] == T[5] # 15 == 26

It seems to have something to do with the fact that there are more than 4 initial terms. The "natural" sequence starts 0,1,2,4,8

(S - X*S - S[0])[0:10] # [ 0, 1, 2, 4, 8, 15, 26, 42, 64, 93 ]

Component: combinatorics

Keywords: CFiniteSequence, recurrence, rings, slice

Author: Trevor Gunn

Branch/Commit: 9d914fe

Reviewer: Frédéric Chapoton

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

[seragunn]

Description changed:

--- 
+++ 
@@ -23,3 +23,8 @@
 4 * T[4] - 6 * T[3] + 4 * T[2] - T[1] == T[5] # 15 == 26

+It seems to have something to do with the fact that there are more than 4 initial terms. The "natural" sequence starts 0,1,2,4,8 + +sage +(S - X*S - S[0])[0:10] # [ 0, 1, 2, 4, 8, 15, 26, 42, 64, 93 ] +

[seragunn]

comment:2

The error seems to occur when the length of the initial values is 1 more than the coefficients.

C.from_recurrence([1,1],[1,1,1])[0:10]   # [ 1, 1, 1, 3, 5, 8, 13, 21, 34, 55 ]
C.from_recurrence([1,1],[1,1,1,1])[0:10] # [ 1, 1, 1, 1, 2, 3, 5, 8, 13, 21 ]

[seragunn]

comment:3

I believe I've tracked down the problem.

# determine start values (may be different from _get_item_ values)
alen = max(self._deg, num.degree() + 1)
R = LaurentSeriesRing(br, parent.variable_name(), default_prec=alen)
rem = num % den
if den != 1:
    self._a = R(num / den).list()
    self._aa = R(rem / den).list()[:self._deg]  # needed for _get_item_
else:
    self._a = num.list()
if len(self._a) < alen:
    self._a.extend([0] * (alen - len(self._a)))

In the initializer, R(rem / den).list() starts at the first non-zero coefficient. For the example above C.from_recurrence([1,1],[1,1,1]) has rem = x and the extra 0 isn't accounted for in the list. This is necessary for self._aa in order to get the correct answers.

I will see if I can write a patch.

[seragunn]

Branch: u/gh-trevorgunn/cfiniteseq-offbyone

[seragunn]

Commit: a293555

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a293555 to 5b3e106

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5b3e106

Fix off-by-one error in CFiniteSequence __getitem__

[seragunn]

comment:7

New tests are failing (these errors have something to do with the offset rather than the _aa vector)

**********************************************************************
File "cfinite_sequence.py", line 644, in sage.rings.cfinite_sequence.?.__getitem__
Failed example:
    s = x^2 * C.guess([1,2,3,4,5,6]); s[0:10]
Expected:
    [0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
Got:
    [0, 0, 1, 2, 3, 2, 3, 4, 5, 6]
**********************************************************************
File "cfinite_sequence.py", line 646, in sage.rings.cfinite_sequence.?.__getitem__
Failed example:
    s = x^3 * C.guess([1,2,3,4,5,6]); s[0:10]
Expected:
    [0, 0, 0, 1, 2, 3, 4, 5, 6, 7]
Got:
    [0, 0, 0, 1, 2, 3, 4, 2, 3, 4]
**********************************************************************

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5b3e106 to 9d914fe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9d914fe

Fix CFiniteSequence.__getitem__ when quo != 0

[seragunn]

comment:10

Each commit addresses a separate bug. The first bug is that R(rem / den).list() needs to include the initial zeroes from the Taylor series. This causes the test

sage: s = C.from_recurrence([1,1],[1,1,1])
sage: s[0:5]
[1, 1, 1, 2, 3]

to fail.

The second bug is that when we are using self._aa it is because we are computing from degree 0 and this needs to be addressed by resetting the offset to 0. This causes the tests

sage: s = C(x^2 * (1 - x)^-2); s[0:10]
[0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: s = C(x^3 * (1 - x)^-2); s[0:10]
[0, 0, 0, 1, 2, 3, 4, 5, 6, 7]

to fail.

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:12

ok, let it be. When you want a review, you may add somebody interested in cc

[vbraun]

Changed branch from u/gh-trevorgunn/cfiniteseq-offbyone to 9d914fe