guessing

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). If data 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, or a q-shift.

Optional arguments:

• cut – if \(N\) is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None. Default: None.
• ensure – if \(N\) is the minimum number of terms needed for some particular choice of order and degree, and if len(data) is less than N+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: 1
• degree – 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: 0
• path – a list of pairs \((r, d)\) specifying which orders and degrees the method should attempt. If this value is equal to None (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.

OUTPUT:

• An element of algebra which annihilates the given data.

An error is raised if no such element is found.

Note

This method is designed to find equations for D-finite objects. It may exhibit strange behaviour for objects which are holonomic but not D-finite.

EXAMPLES:

sage: rec = guess([(2*i+1)^15 * (1 + 2^i + 3^i)^2 for i in xrange(1000)], OreAlgebra(ZZ['n'], 'Sn'))
sage: rec.order(), rec.degree()
(6, 90)
sage: R.<t> = QQ['t']
sage: rec = guess([1/(i+t) + t^i for i in xrange(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

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 of data[0].

See the docstring of guess for further information.

guessing.guess_qrec(data, qn, Q, q, **kwargs)

Shortcut for guess applied with an Ore algebra of \(q\)-recurrence operators in \(Q\) over \(K[qn]\) where \(K\) is the parent of \(q\).

See the docstring of guess for further information.

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 terms
• A – an Ore algebra of recurrence operators, differential operators, or q-differential operators.
• order – maximum order of the sought operators
• degree – maximum degree of the sought operators
• lift (optional) – a function to be applied to the terms in data prior to computation
• solver (optional) – a function to be used to compute the nullspace of a matrix with entries in the base ring of the base ring of A
• cut (optional) – if \(N\) is the minimum number of terms needed for the the specified order and degree and len(data) is more than N+cut, use data[:N+cut] instead of data. This must be a nonnegative integer or None.
• ensure (optional) – if \(N\) is the minimum number of terms needed for the specified order and degree and len(data) is less than N+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\) in A of order at most order and degree at most degree such that \(L\) applied to data gives an array of zeros. (resp. \(L\) applied to the truncated power series with data 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 q-shift nor a standard derivation.
• data contains some item which does not belong to K, even after application of lift
• 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 low-level 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: 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 xrange(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]

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 of data[0].

See the docstring of guess for further information.