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

\[c_0(n) a(n) + \dots + c_r(n) a(n+r) = 0 \text{ for all } n \geq 0\]

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 – a DifferenceDefinableSequenceRing

  • coefficients – the coefficients of the recurrence

  • initial_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 sequence

  • check_lc (default: False) – if True the zeros of the

    leading 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 and right.

INPUTS:

  • right – a sequence over the same ring as self.

OUTPUTS:

The addition of self with right.

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 and right. The result is the termwise product (Hadamard product) of self and right.

INPUTS:

  • right – a sequence over the same ring as self.

OUTPUTS:

The product of self with right.

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 the SequenceRingOfFraction of the base.

INPUT:

  • field (default: False) – if True the companion matrix is defined over a SequenceFieldOfFraction, if False it is defined over a SequenceRingOfFraction.

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 number

  • v (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.

Element

alias of rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequence

__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 sequences

  • guess (default: False) – if True, the linear systems that arise in the computations are solved with guessing (if possible)

  • verified (default: True) – if True, the solutions of the linear system are verified to be correct. If False 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 of base elements and y is a list of field elements. Then x is interpreted as the coefficients of the sequence and y as the initial values of the sequence, i.e. \(a(0), ..., a(r-1)\).

  • x is in base.

  • 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 ring R.

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 (default 1) – the order of the coefficient sequences

OUTPUT:

A difference definable sequence with a random recurrence of order order, random coefficient sequences of order degree and random initial values constisting of integers between -100 and 100.

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 sequences

OUTPUT:

A difference definable sequence with a random recurrence of order order, random coefficient sequences of order degree and random initial values constisting of integers between -100 and 100 where the leading coefficient of the recurrence is 1.

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(*)”