`C2FiniteSequence` and `C2FiniteSequenceRing`

Ring of \(C^2\)-finite sequences

Sublasses rec_sequences.DifferenceDefinableSequenceRing and defines sequences satisfying a linear recurrence equation with coefficients which are C-finite sequence. Such a \(C^2\)-finite 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] and [JPNP21b].

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[:10]
[3, 6, 18, 90, 810, 13770, 454410, 29536650, 3810227850, 979228557450]

sage: f = C([1,1, -1], [0,1]) # define fibonacci numbers
sage: l = C([1,1,-1], [2,1]) # define lucas numbers
sage: f_fac = f.factorial(C2) # define fibonorials
sage: f_fac
C^2-finite sequence of order 1 and degree 2 with coefficients:
> c0 (n) : C-finite sequence c0(n): (1)*c0(n) + (1)*c0(n+1) + (-1)*c0(n+2) = 0 and c0(0)=1 , c0(1)=1
> c1 (n) : C-finite sequence c1(n)=-1
and initial values a(0)=1
sage: f_fac[:10]
[1, 1, 1, 2, 6, 30, 240, 3120, 65520, 2227680]

sage: a_plus_f = a+f_fac
sage: a_plus_f.order(), a_plus_f.degree()
(2, 25)
sage: a_plus_f[:10]
[4, 7, 19, 92, 816, 13800, 454650, 29539770, 3810293370, 979230785130]

sage: l_sparse = l.sparse_subsequence(C2) # define l(n^2)
sage: l_sparse[:8]
[2, 1, 7, 76, 2207, 167761, 33385282, 17393796001]

sage: f_times_l = f_fac * l_sparse # long time
sage: f_times_l.order(), f_times_l.degree() # long time
(2, 15)
sage: f_times_l[:5] # long time
[2, 1, 7, 152, 13242]

class rec_sequences.C2FiniteSequenceRing.C2FiniteSequence(parent, coefficients, initial_values, name='a', is_gen=False, construct=False, cache=True, *args, **kwds)

Bases: rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequence

A C^2-finite sequence, i.e. a sequence where every term can be determined by a linear recurrence with coefficients coming from a C-finite sequence 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', is_gen=False, construct=False, cache=True, *args, **kwds)

Construct a \(C^2\)-finite 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)\).

Note

We assume that the leading coefficient \(c_r\) does not contain any zero terms. If it does, this might yield problems in later computations.

INPUT:

parent – a C2FiniteSequenceRing
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
name (default “a”) – a name for the sequence

OUTPUT:

A sequence determined by the given recurrence and initial values.

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
C^2-finite sequence of order 1 and degree 2 with coefficients:
> c0 (n) : C-finite sequence c0(n): (2)*c0(n) + (-3)*c0(n+1) + (1)*c0(n+2) = 0 and c0(0)=2 , c0(1)=3
> c1 (n) : C-finite sequence c1(n)=-1
and initial values a(0)=3

_latex_(name=None)

Creates a latex representation of the sequence. This is done by creating the latex representation of the closed forms of the coefficients and showing the recurrence and the initial values.

OUTPUT:

A latex representation showing the closed form of the sequence.

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: d = C(3^n)
sage: a = C2([c, d], [1])

sage: print(latex(a))
\left(2^{n} + 1\right)\cdot a(n) + \left(3^{n}\right) \cdot a(n+1) = 0 \quad a(0)=1

_repr_(name=None)

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.

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.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)
sage: a = C2([c, -1], [1])
sage: a
C^2-finite 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  

functional_equation()

Computes the functional equation corresponding to the sequence. This functional equation is given as object of type rec_sequences.FunctionalEquation and represents a functional equation of the form

\[\sum_{k=1}^m \alpha_k x^{j_k} g^{(d_k)} (\lambda_k x) = p(x)\]

for constants \(\alpha_k, \lambda_k\), natural numbers \(j_k, d_k\) and a polynomial \(p(x)\) where \(g\) denotes the generating function of the sequence.

OUTPUT:

A functional equation for the generating function of the sequence.

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: d = C(3^n)
sage: a = C2([c, d], [1])

sage: print(a.functional_equation())
(x)g(2x) + (x)g(x) + (1/3)g(3x) = 1/3

log = <Logger C2Fin (WARNING)>

class rec_sequences.C2FiniteSequenceRing.C2FiniteSequenceRing(base_ring, name=None, element_class=None, category=None, *args, **kwds)

Bases: rec_sequences.DifferenceDefinableSequenceRing.DifferenceDefinableSequenceRing

A Ring of C^2-finite sequences.

Element: alias of rec_sequences.C2FiniteSequenceRing.C2FiniteSequence

__init__(base_ring, name=None, element_class=None, category=None, *args, **kwds)

Constructor for a \(C^2\)-finite sequence ring.

INPUT:

field (default: QQ) – a field of characteristic zero over which the \(C^2\)-finite sequence ring is defined.

OUTPUT:

A ring of \(C^2\)-finite sequences

EXAMPLES:

sage: from rec_sequences.C2FiniteSequenceRing import *
sage: C2FiniteSequenceRing(QQ)
Ring of C^2-finite sequences with base field Rational Field

_element_constructor_(x, y=None, name='a', check=True, is_gen=False, construct=False, *args, **kwds)

Tries to construct a sequence \(a(n)\).

This is possible if:

x is already a \(C^2\)-finite sequence.
x is a list of C-finite sequences and y is a list of field elements. Then x is interpreted as the coefficients of the recurrence and y as the initial values of the sequence, i.e. \(a(0), ..., a(r-1)\).
x is a C-finite sequence.
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.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)^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)
C^2-finite 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.C2FiniteSequenceRing import *
sage: print(latex(C2FiniteSequenceRing(QQ)))
\mathcal{C^2}(\Bold{Q})

_repr_()

OUTPUT:

A string representation of the sequence ring.

EXAMPLES:

sage: from rec_sequences.C2FiniteSequenceRing import *
sage: C2FiniteSequenceRing(QQ)
Ring of C^2-finite sequences with base field Rational Field

guess(data, zeros, order_bound=2, degree_bound=0, ensure=1, simple=False)

Given a list of terms \(a(0), a(1), a(2), \dots\), try to guess a \(C^2\)-finite recurrence

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

satisfied by these terms. The eigenvalues of the coefficient sequences \(c_i\) are chosen among the given values zeros.

Note

We assume that the base field is big enough to also contain the zeros of the characteristic polynomials of the coefficient sequences.

INPUT:

data – a list of elements in the base field of the ring used for guessing
zeros – a list of elements in the base field of the ring used for the roots of the coefficient sequences
order_bound (default: 2) – a natural number, the bound on the order \(r\) of the recurrence
degree_bound (default: 0) – a natural number, the maximal multiplicity of the given roots in the coefficient polynomials.
ensure (default: 1) – a natural number, the number of excess equations used for the linear system; the larger this value the more confident one can be about the result.
simple (default: False) – a boolean; if True a simple \(C^2\)-finite recurrence (i.e., a recurrence with leading coefficient 1) is guessed.

OUTPUT:

A \(C^2\)-finite sequence with the given initial values \(a(0),a(1), \dots\). If no \(C^2\)-finite recurrence could be found, a ValueError is raised.

EXAMPLES:

sage: from rec_sequences.C2FiniteSequenceRing import *
sage: C2 = C2FiniteSequenceRing(QQ)

sage: zeros = [1,2,4]
sage: data = [2^(n^2) for n in range(100)]
sage: a = C2.guess(data, zeros)
sage: a[:100] == data
True

sage: data2 = [n^2*2^(n^2) for n in range(100)]
sage: C2.guess(data2, zeros)
Traceback (most recent call last):
...
ValueError: No recurrence found.

sage: a2 = C2.guess(data2, zeros, degree_bound=2)
sage: a2.degree()
3

sage: # guess recurrence for f(n^2)
sage: from itertools import *
sage: K.<a> = NumberField(x^2-5)
sage: CK = CFiniteSequenceRing(K)
sage: CCK = C2FiniteSequenceRing(K)
sage: zeros = set([1,(1+a)/2,(1-a)/2])
sage: all_zeros = zeros
sage: for comb in combinations_with_replacement(zeros, 4) :
....:     all_zeros.add(mul(comb))
sage: f = CK([1,1,-1],[0,1])
sage: data = [f[n^2] for n in range(100)]
sage: f2 = CCK.guess(data, all_zeros) # long time
sage: f2[:100] == data # long time
True

sage: f2_simple = CCK.guess(data, all_zeros, 3, 0, True) # long time
sage: f2_simple[:100] == data # long time
True

C2FiniteSequence and C2FiniteSequenceRing

`C2FiniteSequence` and `C2FiniteSequenceRing`