DifferenceDefinableSequence
and DifferenceDefinableSequenceRing
Difference definable sequence ring.
Sublasses rec_sequences.RecurrenceSequenceRing
and defines
sequences satisfying a linear
recurrence equation with coefficients in some sequence
ring. Such a recurrence sequence
\(a(n)\) is defined by a recurrence
with \(c_r(n) \neq 0\) for all \(n\) and initial values \(a(0),...,a(r-1)\). This is based on the theory and algorithms developed in [JPNP21a].
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import *
sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)
sage: C2 = DifferenceDefinableSequenceRing(C) # C^2-finite sequence ring
sage: n = var("n")
sage: print( C2([C((-2)^n), -1], [1]) )
Difference definable sequence of order 1 and degree 1 with coefficients:
> c0 (n) : C-finite sequence c0(n): (2)*c0(n) + (1)*c0(n+1) = 0 and c0(0)=1
> c1 (n) : C-finite sequence c1(n)=-1
and initial values a(0)=1
sage: c = C(2^n+(-1)^n)
sage: d = C(2^n+1)
sage: a = C2([c,-1], [1], name="a")
sage: b = C2([d,-1], [1], name="b")
sage: a[:10]
[1, 2, 2, 10, 70, 1190, 36890, 2397850, 304526950, 78263426150]
sage: b[:10]
[1, 2, 6, 30, 270, 4590, 151470, 9845550, 1270075950, 326409519150]
sage: a_plus_b = a+b
sage: a_plus_b[:10]
[2, 4, 8, 40, 340, 5780, 188360, 12243400, 1574602900, 404672945300]
sage: a_plus_b.order(), a_plus_b.degree()
(3, 8)
sage: a_times_b = a*b
sage: a_times_b[:7]
[1, 4, 12, 300, 18900, 5462100, 5587728300]
- class rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequence(parent, coefficients, initial_values, name='a', check_lc=False, is_gen=False, construct=False, cache=True)
Bases:
rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceElement
A difference definable sequence, i.e. a sequence where every term can be determined by a linear recurrence with coefficients coming from a difference ring and finitely many initial values. We assume that this recurrence holds for all values and that the leading coefficient is non-zero for all n (this is not checked).
- __init__(parent, coefficients, initial_values, name='a', check_lc=False, is_gen=False, construct=False, cache=True)
Construct a difference definable sequence \(a(n)\) with recurrence
\[c_0(n) a(n) + \dots + c_r(n) a(n+r) = 0 \text{ for all } n \geq 0\]from given list of coefficients \(c_0, ... , c_r\) and given list of initial values \(a(0), ..., a(r-1)\).
INPUT:
parent
– aDifferenceDefinableSequenceRing
coefficients
– the coefficients of the recurrenceinitial_values
– a list of initial values, determining the sequence with at least order of the recurrence many values; it is assumed that any additional initial values are consistent with the recurrence.name
(default:"a"
) – a name for the sequencecheck_lc
(default:False
) – ifTrue
the zeros of theleading coefficient are checked. In this case in may have finitely many zeros if enough initial values are given such that the sequence can be continued uniquely. If
False
nothing is checked and it is assumed that the leading coefficient has no zeros.
OUTPUT:
A sequence determined by the given recurrence and initial values.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C((-2)^n), -1], [1]) sage: print(a) Difference definable sequence of order 1 and degree 1 with coefficients: > c0 (n) : C-finite sequence c0(n): (2)*c0(n) + (1)*c0(n+1) = 0 and c0(0)=1 > c1 (n) : C-finite sequence c1(n)=-1 and initial values a(0)=1 sage: a[:10] [1, 1, -2, -8, 64, 1024, -32768, -2097152, 268435456, 68719476736]
- _add_(right, *args, **kwargs)
Return the termwise sum of
self
andright
.INPUTS:
right
– a sequence over the same ring asself
.
OUTPUTS:
The addition of
self
withright
.EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: c = C(2^n+(-1)^n) sage: d = C(2^n+1) sage: a = C2([c,-1], [1], name="a") sage: b = C2([d,-1], [1], name="b") sage: a[:10] [1, 2, 2, 10, 70, 1190, 36890, 2397850, 304526950, 78263426150] sage: b[:10] [1, 2, 6, 30, 270, 4590, 151470, 9845550, 1270075950, 326409519150] sage: a_plus_b = a+b sage: a_plus_b[:10] [2, 4, 8, 40, 340, 5780, 188360, 12243400, 1574602900, 404672945300]
- _latex_(name=None)
Creates a latex representation of the sequence. This is done by creating the latex representation of the closed form of the coefficients.
OUTPUT:
A latex representation showing the recurrence and the initial values of the sequence.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C((-2)^n), -1], [1]) sage: print(latex(a)) \left(\left(-2\right)^{n}\right)\cdot a(n) + \left(-1\right) \cdot a(n+1) = 0 \quad a(0)=1
- _mul_(right, *args, **kwargs)
Return the product of
self
andright
. The result is the termwise product (Hadamard product) ofself
andright
.INPUTS:
right
– a sequence over the same ring asself
.
OUTPUTS:
The product of
self
withright
.EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: c = C(2^n+(-1)^n) sage: d = C(2^n+1) sage: a = C2([c,-1], [1], name="a") sage: b = C2([d,-1], [1], name="b") sage: a[:10] [1, 2, 2, 10, 70, 1190, 36890, 2397850, 304526950, 78263426150] sage: b[:10] [1, 2, 6, 30, 270, 4590, 151470, 9845550, 1270075950, 326409519150] sage: a_times_b = a*b sage: a_times_b[:7] [1, 4, 12, 300, 18900, 5462100, 5587728300]
- _repr_(name=None, ring_name='Difference definable')
Produces a string representation of the sequence.
INPUT:
name
(optional) – a string used as the name of the sequence; if not given,self.name()
is used.ring_name `` (default: ``"Difference definable"
) – used to specify from which ring the given sequence is coming from.
OUTPUT:
A string representation of the sequence consisting of the recurrence and enough initial values to uniquely define the sequence.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C((-2)^n), -1], [1]) sage: print(a) Difference definable sequence of order 1 and degree 1 with coefficients: > c0 (n) : C-finite sequence c0(n): (2)*c0(n) + (1)*c0(n+1) = 0 and c0(0)=1 > c1 (n) : C-finite sequence c1(n)=-1 and initial values a(0)=1
- base()
OUTPUT:
The base of the parent of
self
, c.f.DifferenceDefinableSequenceRing.base()
.
- clear_common_factor()
Tries to clear a common factor in the coefficients.
OUTPUT:
The same sequence with possible smaller coefficients in the recurrence.
- coefficients()
Returns the list of polynomial coefficients of the recurrence of
self
in the format[c0,...,cr]
representing the recurrence\[c_0(n) a(n) + \dots + c_r(n) a(n+r) = 0.\]OUTPUT:
The coefficients of the recurrence of the sequence.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C(2^n)+1, -1], [1]) sage: a.coefficients() [C-finite sequence a(n): (2)*a(n) + (-3)*a(n+1) + (1)*a(n+2) = 0 and a(0)=2 , a(1)=3, C-finite sequence a(n)=-1]
- companion_matrix(field=False)
Returns the \(r \times r\) companion matrix
\[\begin{split}\begin{pmatrix} 0 & 0 & \dots & 0 & -c_0/c_r \\ 1 & 0 & \dots & 0 & -c_1/c_r \\ 0 & 1 & \dots & 0 & -c_2/c_r \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -c_{r-1}/c_r \end{pmatrix} .\end{split}\]of
self
with entries in theSequenceRingOfFraction
of the base.INPUT:
field
(default:False
) – ifTrue
the companion matrix is defined over aSequenceFieldOfFraction
, ifFalse
it is defined over aSequenceRingOfFraction
.
OUTPUT:
The companion matrix.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C(2^n)+1, -1], [1]) sage: a.companion_matrix() [Fraction sequence: > Numerator: C-finite sequence a(n): (2)*a(n) + (-3)*a(n+1) + (1)*a(n+2) = 0 and a(0)=2 , a(1)=3 > Denominator: C-finite sequence a(n)=1 ]
- compress()
Tries to compress the recurrence defining the sequence by compressing all coefficients.
OUTPUT:
The same sequence with possible compressed coefficients in the recurrence.
- degree()
OUTPUT:
The degree of the recurrence, i.e. the maximal order of the coefficients
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C(2^n)+1, -1], [1]) sage: (C(2^n)+1).order() 2 sage: a.degree() 2
- interlace(*others)
Returns the interlaced sequence of self with
others
.INPUT:
others
– other difference definable sequences
OUTPUT:
The interlaced sequence of self with
others
.EXAMPLES:
sage: from rec_sequences.C2FiniteSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = C2FiniteSequenceRing(QQ) sage: n = var("n") sage: c = C(2^n+1) sage: a = C2([c, -1], [3]) sage: a[:6] [3, 6, 18, 90, 810, 13770] sage: f = C([1,1, -1], [0,1]) # define fibonacci numbers sage: f_fac = f.factorial(C2) # define fibonorials sage: f_fac[:6] [1, 1, 1, 2, 6, 30] sage: interlaced = a.interlace(f_fac) sage: interlaced.order() 2 sage: interlaced[:12] [3, 1, 6, 1, 18, 1, 90, 2, 810, 6, 13770, 30] sage: interlaced2 = a.interlace(f_fac, f) sage: interlaced2.order() 6 sage: interlaced2[:12] [3, 1, 0, 6, 1, 1, 12, 1, 1, 36, 1, 2]
- log = <Logger DDS (WARNING)>
- multiple(d)
Computes the sequence \(c(\left \lfloor{n/d}\right \rfloor)\).
INPUT:
d
– a natural number
OUTPUT:
The sequence \(c(\left \lfloor{n/d}\right \rfloor)\).
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: a = C2([C(2^n)+1, -1], [1]) sage: a[:10] [1, 2, 6, 30, 270, 4590, 151470, 9845550, 1270075950, 326409519150] sage: a2 = a.multiple(2) sage: a2.order() 2 sage: a2[:10] [1, 1, 2, 2, 6, 6, 30, 30, 270, 270]
- subsequence(u, v=0, *args, **kwargs)
Returns the sequence \(c(n u + v)\).
INPUT:
u
– a natural numberv
(default:0
) – a natural number
OUTPUT:
The sequence \(c(n u + v)\).
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: f = C([1,1,-1], [0,1]) # Fibonacci numbers sage: c0 = f.subsequence(2, 3)*(f.subsequence(2, 1)*f.subsequence(2, 3)-f.subsequence(2, 2)^2) sage: c1 = f.subsequence(2, 2)*(f.subsequence(2, 3)+f.subsequence(2, 1)) sage: c2 = -f.subsequence(2, 1) sage: fs = C2([c0,c1,c2],[0, 1]) # f(n^2) sage: fs_subs = fs.subsequence(2, 1) # long time sage: fs_subs.order() # long time 2 sage: fs_subs[:5] # long time [1, 34, 75025, 7778742049, 37889062373143906]
- class rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequenceRing(base, guess=False, verified=True, name=None, element_class=None, category=None)
Bases:
rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceRing
A Ring of difference definable sequences over a ring of sequences.
- __init__(base, guess=False, verified=True, name=None, element_class=None, category=None)
Constructor for a difference definable sequence ring.
INPUT:
base
– a difference ring, e.g. the ring of C-finite sequences or D-finite sequencesguess
(default:False
) – ifTrue
, the linear systems that arise in the computations are solved with guessing (if possible)verified
(default:True
) – ifTrue
, the solutions of the linear system are verified to be correct. IfFalse
there can be rare cases, for which the solutions are wrong.
OUTPUT:
A ring of difference definable sequences over
base
.EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: DifferenceDefinableSequenceRing(C) Ring of difference definable sequences over Ring of C-finite sequences over Rational Field
- _element_constructor_(x, y=None, name='a', check=True, is_gen=False, construct=False, **kwds)
Tries to construct a sequence \(a(n)\).
This is possible if:
x
is already a difference definable sequence.x
is a list ofbase
elements andy
is a list of field elements. Thenx
is interpreted as the coefficients of the sequence andy
as the initial values of the sequence, i.e. \(a(0), ..., a(r-1)\).x
is inbase
.x
can be converted into a field element. Then it is interpreted as the constant sequence \((x)_{n \in \mathbb{N}}\)
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: n = var("n") sage: c = C(2^n+(-1)^n) sage: d = C(2^n+1) sage: a = C2([c,-d], [1], name="a") sage: print(latex(a)) \left(2^{n} + \left(-1\right)^{n}\right)\cdot a(n) + \left(-2^{n} - 1\right) \cdot a(n+1) = 0 \quad a(0)=1 sage: a2 = C2(a) sage: b = C2(c) sage: print(b) Difference definable sequence of order 2 and degree 1 with coefficients: > c0 (n) : C-finite sequence c0(n)=2 > c1 (n) : C-finite sequence c1(n)=1 > c2 (n) : C-finite sequence c2(n)=-1 and initial values a(0)=2 , a(1)=1
- _latex_()
OUTPUT:
A latex representation of the sequence ring.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: print(latex(DifferenceDefinableSequenceRing(C))) \mathcal{D_\sigma}(\mathcal{C}(\Bold{Q}))
- _repr_()
OUTPUT:
A string representation of the sequence ring.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: DifferenceDefinableSequenceRing(C) Ring of difference definable sequences over Ring of C-finite sequences over Rational Field
- base()
OUTPUT:
Return the base over which the sequence ring is defined.
EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: C2.base()==C True
- change_base_ring(R)
Return a copy of
self
but with the base ringR
.OUTPUT:
A differene definable sequence ring with base
R
.
- log = <Logger DDR (WARNING)>
- random_element(order=2, degree=1, *args, **kwds)
Return a random difference definable sequence.
INPUT:
-
order
(default:2
) – the order of the recurrence of the random difference definable sequence -degree
(default1
) – the order of the coefficient sequencesOUTPUT:
A difference definable sequence with a random recurrence of order
order
, random coefficient sequences of orderdegree
and random initial values constisting of integers between-100
and100
.Note
It is only guaranteed that the leading coefficient of the recurrence has no zeros in the first
20
values.EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: C2.random_element(order=2).order() 2
- random_monic_element(order=2, degree=1, *args, **kwds)
Return a random difference definable sequence where the leading coefficient of the recurrence is
1
.INPUT:
-
order
(default:2
) – the order of the recurrence of the random difference definable sequence -degree
(default:1
) – the order of the coefficient sequencesOUTPUT:
A difference definable sequence with a random recurrence of order
order
, random coefficient sequences of orderdegree
and random initial values constisting of integers between-100
and100
where the leading coefficient of the recurrence is1
.EXAMPLES:
sage: from rec_sequences.DifferenceDefinableSequenceRing import * sage: from rec_sequences.CFiniteSequenceRing import * sage: C = CFiniteSequenceRing(QQ) sage: C2 = DifferenceDefinableSequenceRing(C) sage: a = C2.random_monic_element(order=2) sage: a.leading_coefficient().is_one() True
- verified()
OUTPUT:
True
if solutions of linear systems are verified to be correct.False
if they are not verified.
- with_guessing()
OUTPUT:
True
if solutions of linear systems are obtained via guessing (if possible).False
if they are always computed using a generalized inverse approach.
- class rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequenceRingFunctor
Bases:
rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceRingFunctor
- __init__()
Constructs a
DifferenceDefinableSequenceRingFunctor
.
- _repr_()
Returns a string representation of the functor.
OUTPUT:
The string “DifferenceDefinableSequenceRing(*)”