ore_algebra.guessing¶
Guessing tools
TESTS:
sage: from ore_algebra import OreAlgebra, guess
sage: guess([SR(1/(i+1)) for i in range(10)], OreAlgebra(QQ['n'], 'Sn'))
(n  2)*Sn + n + 1
Functions
guess (data, algebra, **kwargs) 
Searches for an element of the algebra which annihilates the given data. 
guess_deq (data, x, D, **kwargs) 
Shortcut for guess applied with an Ore algebra of differential operators in D over K[x] where K is the parent of data[0] . 
guess_hp (data, A[, order, degree, lift, …]) 
Guesses differential equations or algebraic equations for a given sample of terms. 
guess_mult (data, algebra, **kwargs) 
Searches for elements of the algebra which annihilates the given data. 
guess_mult_raw (C, data, terms, points, …) 
Lowlevel multivariate guessing function. 
guess_qrec (data, qn, Q, q, **kwargs) 
Shortcut for guess applied with an Ore algebra of qrecurrence operators in Q over K[qn] where K is the parent of q. 
guess_raw (data, A[, order, degree, lift, …]) 
Guesses recurrence or differential equations for a given sample of terms. 
guess_rec (data, n, S, **kwargs) 
Shortcut for guess applied with an Ore algebra of shift operators in S over K[n] where K is the parent of data[0] . 

ore_algebra.guessing.
guess
(data, algebra, **kwargs)¶ Searches for an element of the algebra which annihilates the given data.
INPUT:
data
– a list of elements of the algebra’s base ring’s base ring K (or at least of objects which can be casted into this ring). Ifdata
is a string, it is assumed to be the name of a text file which contains the terms, one per line, encoded in a way that can be interpreted by the element constructor of K.algebra
– a univariate Ore algebra over a univariate polynomial ring whose generator is the standard derivation, the standard shift, the forward difference, a qshift, or a commutative variable.
Optional arguments:
cut
– if N is the minimum number of terms needed for some particular choice of order and degree, and iflen(data)
is more thanN+cut
, usedata[:N+cut]
instead ofdata
. This must be a nonnegative integer orNone
. Default:None
.ensure
– if N is the minimum number of terms needed for some particular choice of order and degree, and iflen(data)
is less thanN+ensure
, raise an error. This must be a nonnegative integer. Default: 0.ncpus
– number of processors to be used. Defaut: 1.order
– bounds the order of the operators being searched for. Default: infinity.min_order
– smallest order to be considered in the search. The output may nevertheless have lower order than this bound. Default: 1degree
– bounds the degree of the operators being searched for. The method may decide to overrule this setting if it thinks this may speed up the calculation. Default: infinity.min_degree
– smallest degree to be considered in the search. The output may nevertheless have lower degree than this bound. Default: 0path
– a list of pairs (r, d) specifying which orders and degrees the method should attempt. If this value is equal toNone
(default), a path is chosen which examines all the (r, d) which can be tested with the given amount of data.solver
– function to be used for computing the right kernel of a matrix with elements in K.infolevel
– an integer specifying the level of details of progress reports during the calculation.method
– either “linalg” (for linear algebra) or “hp” (for HermitePade) or “automatic” (for the default choice), or a callable with the specification of a raw guesser.
OUTPUT:
 An element of
algebra
which annihilates the givendata
.
An error is raised if no such element is found.
Note
 This method is designed to find equations for Dfinite objects. It may exhibit strange behaviour for objects which are holonomic but not Dfinite.
 When the generator of the algebra is a commutative variable, the method searches for algebraic equations.
EXAMPLES:
sage: from ore_algebra import * sage: rec = guess([(2*i+1)^15 * (1 + 2^i + 3^i)^2 for i in range(1000)], OreAlgebra(ZZ['n'], 'Sn')) # long time (5 s) sage: rec.order(), rec.degree() # long time (6, 90) sage: R.<t> = QQ['t'] sage: rec = guess([1/(i+t) + t^i for i in range(100)], OreAlgebra(R['n'], 'Sn')) sage: rec ((t + 1)*n^2 + (2*t^2  t + 2)*n  t^3  2*t^2)*Sn^2 + ((t^2  1)*n^2 + (2*t^3 + 3*t^2  2*t  1)*n + t^4 + 3*t^3 + t^2  t)*Sn + (t^2 + t)*n^2 + (2*t^3 + t)*n  t^4  t^3 + t^2 sage: R.<C> = OreAlgebra(ZZ['x']) sage: cat = [binomial(2*n,n) // (n+1) for n in range(10)] sage: guess(cat, R) x*C^2 + C  1

ore_algebra.guessing.
guess_deq
(data, x, D, **kwargs)¶ Shortcut for
guess
applied with an Ore algebra of differential operators in D over K[x] where K is the parent ofdata[0]
.See the docstring of
guess
for further information.

ore_algebra.guessing.
guess_hp
(data, A, order=1, degree=1, lift=None, cut=25, ensure=0, infolevel=0)¶ Guesses differential equations or algebraic equations for a given sample of terms.
INPUT:
data
– list of termsA
– an Ore algebra of differential operators or ordinary polynomials.order
– maximum order of the sought operatorsdegree
– maximum degree of the sought operatorslift
(optional) – a function to be applied to the terms indata
prior to computationcut
(optional) – if N is the minimum number of terms needed for the the specified order and degree andlen(data)
is more thanN+cut
, usedata[:N+cut]
instead ofdata
. This must be a nonnegative integer orNone
.ensure
(optional) – if N is the minimum number of terms needed for the specified order and degree andlen(data)
is less thanN+ensure
, raise an error. This must be a nonnegative integer.infolevel
(optional) – an integer indicating the desired amount of progress report to be printed during the calculation. Default: 0 (no output).
OUTPUT:
A basis of the
K
vector space of all the operators L inA
of order at mostorder
and degree at mostdegree
such that L applied to the truncated power series withdata
as terms gives the zero power series.An error is raised in the following situations:
 the algebra
A
has more than one generator, or its unique generator is neither a standard derivation nor a commutative variable. data
contains some item which does not belong toK
, even after application oflift
 if the condition on
ensure
is violated.
ALGORITHM:
HermitePade approximation.
Note
This is a lowlevel method. Don’t call it directly unless you know what you are doing. In usual applications, the right method to call is
guess
.EXAMPLES:
sage: from ore_algebra import * sage: from ore_algebra.guessing import guess_hp sage: K = GF(1091); R.<x> = K['x']; sage: data = [binomial(2*n, n)*fibonacci(n)^3 for n in range(2000)] sage: guess_hp(data, OreAlgebra(R, 'Dx'), order=4, degree=4, lift=K) [(x^4 + 819*x^3 + 136*x^2 + 17*x + 635)*Dx^4 + (14*x^3 + 417*x^2 + 952*x + 605)*Dx^3 + (598*x^2 + 497*x + 99)*Dx^2 + (598*x + 794)*Dx + 893] sage: len(guess_hp(data, OreAlgebra(R, 'C'), order=16, degree=64, lift=K)) 1

ore_algebra.guessing.
guess_mult
(data, algebra, **kwargs)¶ Searches for elements of the algebra which annihilates the given data.
INPUT:
data
– a nested list of elements of the algebra’s base ring’s base ring K (or at least of objects which can be casted into this ring). The depth of the nesting must match the number of generators of the algebra.algebra
– an Ore algebra over a polynomial ring all of whose generators are the standard derivation, the standard shift, or a qshift.
Optional arguments:
cut
– if N is the minimum number of terms needed for some particular choice of order and degree, and iflen(data)
is more thanN+cut
, usedata[:N+cut]
instead ofdata
. This must be a nonnegative integer orNone
. Default: 100.ensure
– if N is the minimum number of terms needed for some particular choice of order and degree, and iflen(data)
is less thanN+ensure
, raise an error. This must be a nonnegative integer. Default: 0.order
– maximum degree of the algebra generators in the sought operators. Alternatively: a list or tuple specifying individual degree bounds for each generator of the algebra. Default: 2degree
– maximum total degree of the polynomial coefficients in the sought operators. Default: 3point_filter
– a callable such that index tuples of data array for which the callable returns ‘False’ will not be used. Default: None (everything allowed).term_filter
– a callable such that operators containing power products of the algebra generators for which the callable returns ‘False’ are excluded. Default: None (everything allowed).solver
– function to be used for computing the right kernel of a matrix with elements in K.infolevel
– an integer specifying the level of details of progress reports during the calculation.
OUTPUT:
 The left ideal of
algebra
generated by all the operators of the specified order and degree that annihilate the givendata
. It may be the zero ideal.
Note
This method is designed to find equations for Dfinite objects. It may exhibit strange behaviour for objects which are holonomic but not Dfinite.
EXAMPLES:
sage: from ore_algebra import * sage: from ore_algebra.guessing import guess_mult sage: data = [[binomial(n,k) for n in range(10)] for k in range(10)] sage: guess_mult(data, OreAlgebra(ZZ['n','k'], 'Sn', 'Sk'), order=1, degree=0) Left Ideal (Sn*Sk  Sn  1) of Multivariate Ore algebra in Sn, Sk over Fraction Field of Multivariate Polynomial Ring in n, k over Integer Ring sage: guess_mult(data, OreAlgebra(ZZ['x','y'], 'Dx', 'Dy'), order=1, degree=1) Left Ideal ((x + 1)*Dx + (y)*Dy) of Multivariate Ore algebra in Dx, Dy over Fraction Field of Multivariate Polynomial Ring in x, y over Integer Ring sage: guess_mult(data, OreAlgebra(ZZ['n','y'], 'Sn', 'Dy'), order=1, degree=1) Left Ideal ((y + 1)*Sn*Dy  Sn + (y)*Dy  1, (n  1)*Sn + y*Dy  n, (y + 1)*Sn  y) of Multivariate Ore algebra in Sn, Dy over Fraction Field of Multivariate Polynomial Ring in n, y over Integer Ring sage: guess_mult(data, OreAlgebra(ZZ['x','k'], 'Dx', 'Sk'), order=1, degree=1) Left Ideal (Dx*Sk + (x  1)*Dx  1, x*Dx*Sk + (x + 1)*Dx + (k)*Sk  x, (x + 1)*Dx  k, (x + 1)*Dx*Sk + (k  1)*Sk) of Multivariate Ore algebra in Dx, Sk over Fraction Field of Multivariate Polynomial Ring in x, k over Integer Ring

ore_algebra.guessing.
guess_mult_raw
(C, data, terms, points, power, A, B, **kwargs)¶ Lowlevel multivariate guessing function. Do not call this method unless you know what you are doing. In most situations, you will want to call the function guess instead.
INPUT:
 data – a nested list of elements of C
 terms – a list of pairs of tuples (u, v) specifying exponent vectors u, v representing terms x^u D^v
 points – a list of tuples specifying indices of the data array
 power – a list of functions f mapping triples (n, u, v) of nonnegative integers to elements of C
 A – a list of functions mapping triples (n, u, v) to integers
 B – a list of functions mapping triples (n, u, v) to integers
OUTPUT:
A list of vectors generating the space of all vectors in C^len(terms) for which all(sum(prod(f[i][A[i][n[i],u[i],v[i]]]*a[B[i][n[i],u[i],v[i]]] for i in range(len(A))) for (u,v) in terms) == 0 for n in points)
SIDE EFFECT:
Elements of the list points which lead to a zero equation will be discarded.

ore_algebra.guessing.
guess_qrec
(data, qn, Q, q, **kwargs)¶ Shortcut for
guess
applied with an Ore algebra of qrecurrence operators in Q over K[qn] where K is the parent of q.See the docstring of
guess
for further information.

ore_algebra.guessing.
guess_raw
(data, A, order=1, degree=1, lift=None, solver=None, cut=25, ensure=0, infolevel=0)¶ Guesses recurrence or differential equations for a given sample of terms.
INPUT:
data
– list of termsA
– an Ore algebra of recurrence operators, differential operators, or qdifferential operators.order
– maximum order of the sought operatorsdegree
– maximum degree of the sought operatorslift
(optional) – a function to be applied to the terms indata
prior to computationsolver
(optional) – a function to be used to compute the nullspace of a matrix with entries in the base ring of the base ring ofA
cut
(optional) – if N is the minimum number of terms needed for the the specified order and degree andlen(data)
is more thanN+cut
, usedata[:N+cut]
instead ofdata
. This must be a nonnegative integer orNone
.ensure
(optional) – if N is the minimum number of terms needed for the specified order and degree andlen(data)
is less thanN+ensure
, raise an error. This must be a nonnegative integer.infolevel
(optional) – an integer indicating the desired amount of progress report to be printed during the calculation. Default: 0 (no output).
OUTPUT:
A basis of the
K
vector space of all the operators L inA
of order at mostorder
and degree at mostdegree
such that L applied todata
gives an array of zeros. (resp. L applied to the truncated power series withdata
as terms gives the zero power series)An error is raised in the following situations:
 the algebra
A
has more than one generator, or its unique generator is neither a standard shift nor a qshift nor a standard derivation. data
contains some item which does not belong toK
, even after application oflift
 if the condition on
ensure
is violated.  if the linear system constructed by the method turns out to be underdetermined for some other reason, e.g., because too many linear constraints happen to be trivial.
ALGORITHM:
Ansatz and linear algebra.
Note
This is a lowlevel method. Don’t call it directly unless you know what you are doing. In usual applications, the right method to call is
guess
.EXAMPLES:
sage: from ore_algebra import * sage: K = GF(1091); R.<n> = K['n']; A = OreAlgebra(R, 'Sn') sage: data = [(5*n+3)/(3*n+4)*fibonacci(n)^3 for n in range(200)] sage: guess_raw(data, A, order=5, degree=3, lift=K) [(n^3 + 546*n^2 + 588*n + 786)*Sn^5 + (356*n^3 + 717*n^2 + 381*n + 449)*Sn^4 + (8*n^3 + 569*n^2 + 360*n + 214)*Sn^3 + (31*n^3 + 600*n^2 + 784*n + 287)*Sn^2 + (1078*n^3 + 1065*n^2 + 383*n + 466)*Sn + 359*n^3 + 173*n^2 + 503, (n^3 + 1013*n^2 + 593*n + 754)*Sn^5 + (797*n^3 + 56*n^2 + 7*n + 999)*Sn^4 + (867*n^3 + 1002*n^2 + 655*n + 506)*Sn^3 + (658*n^3 + 834*n^2 + 1036*n + 899)*Sn^2 + (219*n^3 + 479*n^2 + 476*n + 800)*Sn + 800*n^3 + 913*n^2 + 280*n]

ore_algebra.guessing.
guess_rec
(data, n, S, **kwargs)¶ Shortcut for
guess
applied with an Ore algebra of shift operators in S over K[n] where K is the parent ofdata[0]
.See the docstring of
guess
for further information.