# ore_algebra.ore_algebra¶

Ore algebras

The ore_algebra package provides functionality for doing computations with Ore polynomials.

Ore polynomials are operators which can be used to describe special functions or combinatorial sequences. Typical examples are linear differential operators with polynomial coefficients.

Ore polynomials are elements of Ore algebras. Ore algebras are ring objects created by the function OreAlgebra as described below.

Depending on the particular parent algebra, Ore polynomials may support different functionality. For example, for Ore polynomials representing recurrence operators, there is a method for computing interlacing operatos, an operation which does not make sense for differential operators.

The typical user will only need two functions defined in the package:

• OreAlgebra – for creating a new Ore algebra object.
• guess – for fitting an Ore polynomial to a given set of data.

Ore polynomials are created using OreAlgebra objects, and most of the functionality for doing calculations with Ore polynomials is available in the methods attached to them.

For examples and further information, see the docstring of OreAlgebra below, or the tutorial paper Ore Polynomials in Sage by the authors.

AUTHOR:

• Manuel Kauers, Maximilian Jaroschek, Fredrik Johansson (2013-06-15)

Functions

 DifferentialOperators([base, var]) Shorthand to construct an Ore algebra of differential operators. OreAlgebra(base_ring, *generators, **kwargs) An Ore algebra is a noncommutative polynomial ring whose elements are interpreted as operators. is_OreAlgebra(A) Checks whether A is an Ore algebra object. is_suitable_base_ring(R) Checks whether R is suitable as base ring of an Ore algebra. taylor_shift_univ_int_poly(p, i) taylor_shift_univ_int_ratfun(q, i) taylor_shift_univ_modp_poly(p, i) taylor_shift_univ_modp_ratfun(q, i)

Classes

 Delta_class(R, d, s) A skew-derivation for suitable rings. OreAlgebraFunctor(*gens) Construction functor for Ore algebras. OreAlgebra_generic(base_ring, …) Sigma_class(R, d) A ring endomorphism for suitable rings.
class ore_algebra.ore_algebra.Delta_class(R, d, s)

A skew-derivation for suitable rings.

A delta object is created by a ring R on which it operates, some piece of information defining the action, and an associated Sigma object. The action is defined through a dictionary which has generators of R on its left hand side and elements of R on its right hand side. Generators of R which are not contained in the dictionary are mapped to zero.

Instead of a dictionary, the constructor also accepts arbitrary callable objects. In this case, a dictionary is created based on the values this callable object produces when applied to the generators of R.

It is assumed without test that the ring R is “suitable”.

EXAMPLES:

sage: from ore_algebra.ore_algebra import *
sage: R.<x1,x2,x3> = QQ['x1,x2,x3']
sage: sigma = Sigma_class(R, {x1:2*x1, x2:1-x2, x3:x3+1})
sage: delta = Delta_class(R, {x1:1, x3:x3}, sigma)
sage: delta(x1+x2+x3)
x3 + 1
sage: delta(x1*x2*x3)
-2*x1*x2*x3 + 2*x1*x3 + x2*x3
sage: sorted(delta.dict().items(), key=str)
[('x1', 1), ('x3', x3)]

dict()

Returns a dictionary representing self

ring()

Returns the ring for which this sigma object is defined

ore_algebra.ore_algebra.DifferentialOperators(base=Rational Field, var='x')

Shorthand to construct an Ore algebra of differential operators.

Return an Ore algebra of differential operators with polynomial coefficients, along with objects representing, x and d/dx.

INPUT:

• base (default QQ) - base ring of the polynomial coefficients
• var (default x) - variable name

EXAMPLE:

sage: from ore_algebra import *
sage: Dops, x, Dx = DifferentialOperators()
sage: Dops
Univariate Ore algebra in Dx over Univariate Polynomial Ring in x over
Rational Field
sage: x*Dx + 1
x*Dx + 1

sage: DifferentialOperators(GF(2), 't')
(Univariate Ore algebra in Dt over Univariate Polynomial Ring in t over
Finite Field of size 2 (...),
t, Dt)

ore_algebra.ore_algebra.OreAlgebra(base_ring, *generators, **kwargs)

An Ore algebra is a noncommutative polynomial ring whose elements are interpreted as operators.

An Ore algebra has the form A=R[partial_1,partial_2,dots,partial_n] where R is an integral domain and partial_1,dots,partial_n are indeterminates. For each of them, there is an associated automorphism sigma:R\rightarrow R and a skew-derivation delta:R\rightarrow R satisfying delta(a+b)=delta(a)+delta(b) and delta(ab)=delta(a)b+sigma(a)delta(b) for all a,bin R.

The generators partial_i commute with each other, but not with elements of the base ring R. Instead, we have the commutation rules partial u = sigma(u) partial + delta(u) for all uin R.

The base ring R must be suitable according to the following definition: ZZ, QQ, GF(p) for primes p, and finite algebraic extensions of QQ are suitable, and if R is suitable then so are R[x], R[x_1,x_2,…] and Frac(R). It is assumed that all the sigma leave R.base_ring() fixed and all the delta map R.base_ring() to zero.

A typical example of an Ore algebra is the ring of linear differential operators with rational function coefficients in one variable, e.g. A=QQ[x][D]. Here, sigma is the identity and delta is the standard derivation d/dx.

To create an Ore algebra, supply a suitable base ring and one or more generators. Each generator has to be given in form of a triple (name,sigma,delta) where name is the desired name of the variable (used for printout), sigma and delta are arbitrary callable objects which applied to the base ring return other base ring elements in accordance with the relevant laws. It is not checked whether they do.

sage: from ore_algebra import *

sage: R.<x> = QQ['x']
sage: K = R.fraction_field()

# This creates an Ore algebra of linear differential operators
sage: A.<D> = OreAlgebra(K, ('D', lambda p: p, lambda p: p.derivative(x)))
sage: A
Univariate Ore algebra in D over Fraction Field of Univariate Polynomial Ring in x over Rational Field

# This creates an Ore algebra of linear recurrence operators
sage: A.<S> = OreAlgebra(K, ('S', lambda p: p(x+1), lambda p: K.zero()))
sage: A
Univariate Ore algebra in S over Fraction Field of Univariate Polynomial Ring in x over Rational Field


Instead of a callable object for sigma and delta, also a dictionary can be supplied which for every generator of the base ring specifies the desired image. If some generator is not in the dictionary, it is understood that sigma acts as identity on it, and that delta maps it to zero.

sage: U.<x, y> = ZZ['x', 'y']

# here, the base ring represents the differential field QQ(x, e^x)
sage: A.<D> = OreAlgebra(U, ('D', {}, {x:1, y:y}))

# here, the base ring represents the difference field QQ(x, 2^x)
sage: B.<S> = OreAlgebra(U, ('S', {x:x+1, y:2*y}, {}))

# here too, but the algebra's generator represents the forward difference instead of the shift
sage: C.<Delta> = OreAlgebra(U, ('Delta', {x:x+1, y:2*y}, {x:1, y:y}))


For the most frequently needed operators, the constructor accepts their specification as a string only, without explicit statement of sigma or delta. The string has to start with one of the letters listed in the following table. The remainder of the string has to be the name of one of the generators of the base ring. The operator will affect this generator and leave the others untouched.

Prefix Operator sigma delta
C Commutative variable {} {}
D Standard derivative {} {x:1}
S Standard shift {x:x+1} {}
u0394, F Forward difference {x:x+1} {x:1}
u03B8, T, E Euler derivative {} {x:x}
Q q-shift {x:q*x} {}
J Jackson’s q-derivative {x:q*x} {x:1}

In the case of C, the suffix need not be a generator of the ground field but may be an arbitrary string. In the case of Q and J, either the base ring has to contain an element q, or the base ring element to be used instead has to be supplied as optional argument.

sage: R.<x, y> = QQ['x', 'y']
sage: A = OreAlgebra(R, 'Dx') # This creates an Ore algebra of differential operators
sage: A == OreAlgebra(R, ('Dx', {}, {x:1}))
True
sage: A == OreAlgebra(R, ('Dx', {}, {y:1})) # the Dx in A acts on x, not on y
False

# This creates an Ore algebra of linear recurrence operators
sage: A = OreAlgebra(R, 'Sx')
sage: A == OreAlgebra(R, ('Sx', {x:x+1}, {}))
True
sage: A == OreAlgebra(R, ('Sx', {y:y+1}, {})) # the Sx in A acts on x, not on y
False
sage: OreAlgebra(R, 'Qx', q=2)
Univariate Ore algebra in Qx over Multivariate Polynomial Ring in x, y over Rational Field


A generator can optionally be extended by a vector (w_0,w_1,w_2) of base ring elements which encodes the product rule for the generator: D(u*v) == w_0*u*v + w_1*(D(u)*v + u*D(v)) + w_2*D(u)*D(v). This data is needed in the computation of symmetric products.

Ore algebras support coercion from their base rings. Furthermore, an Ore algebra A knows how to coerce commutative polynomials p to elements of A if the generators of the parent of p have the same names as the generators of A, and the base ring of the parent of p admits a coercion to the base ring of A. The ring of these polynomials is called the associated commutative algebra of A, and it can be obtained by calling A.associated_commutative_algebra().

Elements of Ore algebras are called Ore operators. They can be constructed from the same data from which also elements of the associated commutative algebra can be constructed.

The conversion from data to an Ore operator is equivalent to the conversion from the given data to an element of the associated commutative algebra, and from there to an Ore operator. This has the consequence that possible implicit information about multiplication order may be lost, for example when generating operators from strings:

sage: A = OreAlgebra(QQ['x'], 'Dx')
sage: A("Dx*x")
x*Dx
sage: A("Dx")*A("x")
x*Dx + 1


A safer way of creating operators is via a list of coefficients. These are then always interpreted as standing to the left of the respective algebra generator monomial.

sage: R.<x> = QQ['x']
sage: A.<Dx> = OreAlgebra(R, 'Dx')
sage: A([x^2+1, 5*x-7, 7*x+18])
(7*x + 18)*Dx^2 + (5*x - 7)*Dx + x^2 + 1
sage: (7*x + 18)*Dx^2 + (5*x - 7)*Dx + x^2 + 1
(7*x + 18)*Dx^2 + (5*x - 7)*Dx + x^2 + 1
sage: _^2
(49*x^2 + 252*x + 324)*Dx^4 + (70*x^2 + 180*x)*Dx^3 + (14*x^3 + 61*x^2 + 49*x + 216)*Dx^2 + (10*x^3 + 14*x^2 + 107*x - 49)*Dx + x^4 + 12*x^2 + 37

sage: R.<x> = QQ['x']
sage: A.<Sx> = OreAlgebra(QQ['x'], 'Sx')
sage: A([x^2+1, 5*x-7, 7*x+18])
(7*x + 18)*Sx^2 + (5*x - 7)*Sx + x^2 + 1
sage: (7*x + 18)*Sx^2 + (5*x - 7)*Sx + x^2 + 1
(7*x + 18)*Sx^2 + (5*x - 7)*Sx + x^2 + 1
sage: _^2
(49*x^2 + 350*x + 576)*Sx^4 + (70*x^2 + 187*x - 121)*Sx^3 + (14*x^3 + 89*x^2 + 69*x + 122)*Sx^2 + (10*x^3 - 4*x^2 + x - 21)*Sx + x^4 + 2*x^2 + 1

class ore_algebra.ore_algebra.OreAlgebraFunctor(*gens)

Construction functor for Ore algebras.

Such a functor is made from the same data as an Ore algebra, except for the base ring. In particular, Ore algebra functors contain sigmas and deltas, which do act on certain domains. The sigmas and deltas are represented by dictionaries. The functor is applicable to rings that contain generators named like the left hand sides of the sigmas and deltas, and to which the right hand sides can be casted.

class ore_algebra.ore_algebra.OreAlgebra_generic(base_ring, operator_class, gens, product_rules)
associated_commutative_algebra()

Returns a polynomial ring with the same base ring as this algebra and whose generators have the same name as this Ore algebra’s generators.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: R.<x> = QQ['x']
sage: A = OreAlgebra(R.fraction_field(), "Dx")
sage: A
Univariate Ore algebra in Dx over Fraction Field of Univariate
Polynomial Ring in x over Rational Field
sage: A.associated_commutative_algebra()
Univariate Polynomial Ring in Dx over Fraction Field of Univariate
Polynomial Ring in x over Rational Field

base_extend(R)

Creates the Ore algebra obtained from self by replacing the base ring by R

change_delta(delta, n=0)

Creates the Ore algebra obtained from self by replacing the skew-derivation associated to the n th generator to delta, which may be a callable or a dictionary.

change_ring(R)

Creates the Ore algebra obtained from self by replacing the base ring by R

change_sigma(sigma, n=0)

Creates the Ore algebra obtained from self by replacing the homomorphism associated to the n th generator to sigma, which may be a callable or a dictionary.

change_var(var, n=0)

Creates the Ore algebra obtained from self by renaming the n th generator to var

change_var_sigma_delta(var, sigma, delta, n=0)

Creates the Ore algebra obtained from self by replacing the n th generator and its associated homomorphism and skew-derivation by var, sigma, and delta, respectively. The maps sigma and delta may be specified as callables or dictionaries.

characteristic()

Return the characteristic of this Ore algebra, which is the same as that of its base ring.

construction()

Returns a functorial description of this Ore algebra

delta(n=0)

Returns the delta callable associated to the n th generator of this algebra. The generator can be specified by index (as integer), or by name (as string), or as algebra element.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Dx> = OreAlgebra(QQ['x'].fraction_field(), 'Dx')
sage: A.delta()
Skew-derivation defined through {'x': 1} for Endomorphism defined through {'x': x}
sage: A.delta(0)
Skew-derivation defined through {'x': 1} for Endomorphism defined through {'x': x}
sage: A.delta("Dx")
Skew-derivation defined through {'x': 1} for Endomorphism defined through {'x': x}
sage: A.delta(Dx)
Skew-derivation defined through {'x': 1} for Endomorphism defined through {'x': x}

gen(n=0)

Return the indeterminate generator(s) of this Ore algebra.

gens()

Return a tuple of generators of this Ore algebra.

gens_dict()

Returns a dictionary whose keys are the variable names of this Algebra as strings and whose values are the corresponding generators.

ideal(gens, coerce=True, is_known_to_be_a_groebner_basis=False)

Creates the left ideal generated by the given generators.

The generators must be elements of self.

is_C(n=0)

Checks whether the n th generator of this algebra is a commutative variable. If so, it returns True, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<C> = OreAlgebra(ZZ['x'], 'C')
sage: A.is_C()
True
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_C()
False

is_D(n=0)

Checks whether the n th generator of this algebra is the standard derivation d/dx for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_D()
x
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_D()
False

is_Delta(n=0)

Checks whether the n th generator of this algebra is the forward difference p(x)rightarrow p(x+1)-p(x) for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Fx> = OreAlgebra(ZZ['x'], 'Fx')
sage: A.is_F()
x
sage: A.is_Delta()
x
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_F()
False
sage: A.is_Delta()
False

is_E(n=0)

Checks whether the n th generator of this algebra is the Euler derivation x*d/dx for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Tx> = OreAlgebra(ZZ['x'], 'Tx')
sage: A.is_T(), A.is_E()
(x, x)
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_T(), A.is_E()
(False, False)

is_F(n=0)

Checks whether the n th generator of this algebra is the forward difference p(x)rightarrow p(x+1)-p(x) for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Fx> = OreAlgebra(ZZ['x'], 'Fx')
sage: A.is_F()
x
sage: A.is_Delta()
x
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_F()
False
sage: A.is_Delta()
False

is_J(n=0)

Checks whether the n th generator of this algebra is the q-derivation p(x)rightarrow (p(q*x)-p(x))/(x*(q-1)) for some generator x of the base ring and some element q, different from 1, of the base ring’s base ring. If so, it returns the pair (x, q), otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Jx> = OreAlgebra(ZZ['x'], 'Jx', q=2)
sage: A.is_J()
(x, 2)
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_J()
False
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_J()
False

is_Q(n=0)

Checks whether the n th generator of this algebra is the q-shift p(x)rightarrow p(q*x) for some generator x of the base ring and some element q of the base ring’s base ring. If so, it returns the pair (x, q), otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Qx> = OreAlgebra(ZZ['x'], 'Qx', q=2)
sage: A.is_Q()
(x, 2)
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_Q()
False

is_S(n=0)

Checks whether the n th generator of this algebra is the standard shift p(x)rightarrow p(x+1) for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Sx> = OreAlgebra(ZZ['x'], 'Sx')
sage: A.is_S()
x
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_S()
False

is_T(n=0)

Checks whether the n th generator of this algebra is the Euler derivation x*d/dx for some generator x of the base ring. If so, it returns x, otherwise False.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Tx> = OreAlgebra(ZZ['x'], 'Tx')
sage: A.is_T(), A.is_E()
(x, x)
sage: A.<Dx> = OreAlgebra(ZZ['x'], 'Dx')
sage: A.is_T(), A.is_E()
(False, False)

is_exact()

This algebra is exact iff its base ring is

is_field(proof=True)

Returns False since Ore algebras are not fields (unless they have 0 generators and the base ring is a field)

is_finite()

Return False since Ore algebras are not finite (unless the base ring is 0).

is_integral_domain(proof=True)

Returns True because Ore algebras are always integral domains.

is_noetherian()

Returns True because Ore algebras are always noetherian.

krull_dimension()

Returns the Krull dimension of this algebra, which is the Krull dimension of the base ring plus the number of generators of this algebra.

ngens()

Return the number of generators of this Ore algebra

random_element(*args, **kwds)

Return a random operator. The random operator is constructed by coercing a random element of the associated commutative algebra to an element of this algebra.

sigma(n=0)

Returns the sigma callable associated to the n th generator of this algebra. The generator can be specified by index (as integer), or by name (as string), or as algebra element.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Dx> = OreAlgebra(QQ['x'].fraction_field(), 'Dx')
sage: A.sigma()
Endomorphism defined through {'x': x}
sage: A.sigma(0)
Endomorphism defined through {'x': x}
sage: A.sigma('Dx')
Endomorphism defined through {'x': x}
sage: A.sigma(Dx)
Endomorphism defined through {'x': x}

subalgebra(gens)

Returns the subalgebra of ‘self’ generated by the given generators. The given generators must be generators (“variables”) of ‘self’. The base ring is not affected.

var(n=0)

Returns the name of the n th generator of this algebra.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Dx> = OreAlgebra(QQ['x'].fraction_field(), 'Dx')
sage: A.var()
'Dx'

variable_names()

Returns a tuple with the names (as strings) of the generators of this algebra.

EXAMPLES:

sage: from ore_algebra import OreAlgebra
sage: A.<Dx> = OreAlgebra(QQ['x'], 'Dx')
sage: A.variable_names()
('Dx',)

class ore_algebra.ore_algebra.Sigma_class(R, d)

A ring endomorphism for suitable rings.

A sigma object is created by a ring R on which it operates, and some piece of defining the action. The action is defined through a dictionary which has generators of R on its left hand side and elements of R on its right hand side. Generators of R which are not contained in the dictionary are mapped to themselves.

Instead of a dictionary, the constructor also accepts arbitrary callable objects. In this case, a dictionary is created based on the values this callable object produces when applied to the generators of R.

It is assumed without test that the ring R is “suitable”.

EXAMPLES:

sage: from ore_algebra.ore_algebra import Sigma_class
sage: R.<x1,x2,x3> = QQ['x1,x2,x3']
sage: sigma = Sigma_class(R, {x1:2*x1, x2:1-x2, x3:x3+1})
sage: sigma(x1+x2+x3)
2*x1 - x2 + x3 + 2
sage: sigma = Sigma_class(R.fraction_field(), {x1:2*x1, x2:1-x2, x3:x3+1})
sage: sigma(x1+x2+x3)
2*x1 - x2 + x3 + 2


Repeated application of a sigma object to some ring element can be specified by an optional second argument. There are also functions for computing sigma factorials, for constructing the compositional inverse of a (sufficiently simple) sigma object, and for converting a sigma object into a dictionary

EXAMPLES:

sage: R.<x1,x2,x3> = QQ['x1,x2,x3']
sage: sigma = Sigma_class(R, {x1:2*x1, x2:1-x2, x3:x3+1})
sage: sigma(x1+x2+x3, 5)
32*x1 - x2 + x3 + 6
sage: sigma.factorial(x1+x2+x3, 4).factor()
(x1 + x2 + x3) * (2*x1 - x2 + x3 + 2) * (4*x1 + x2 + x3 + 2) * (8*x1 - x2 + x3 + 4)
sage: sigma_inv = sigma.inverse()
sage: sigma_inv(x1+x2+x3)
1/2*x1 - x2 + x3
sage: sigma(x1+x2+x3, -1)
1/2*x1 - x2 + x3
sage: sigma.inverse().inverse() == sigma
True
sage: sorted(sigma.dict().items(), key=str)
[('x1', 2*x1), ('x2', -x2 + 1), ('x3', x3 + 1)]

dict()

Returns a dictionary representing self

factorial(p, n)

Returns psigma(p)…sigma^{n-1}(p) if n is nonnegative, and and 1/(sigma(p)…sigma^n(p) otherwise.

inverse()

Returns a sigma object which represents the compositional inverse of self.

The inverse can be constructed if sigma is such that it maps every generator x of the base ring to a linear combination a*x+b where a and b belong to the base ring of the parent of x.

If the method fails in constructing the inverse, it raises a ValueError.

EXAMPLES:

sage: from ore_algebra import *
sage: R.<x> = QQ['x']
sage: A.<Sx> = OreAlgebra(R.fraction_field(), "Sx")
sage: sigma = A.sigma()
sage: sigma_inverse = sigma.inverse()
sage: sigma(x)
x + 1
sage: sigma_inverse(x)
x - 1

ring()

Returns the ring for which this sigma object is defined

ore_algebra.ore_algebra.is_OreAlgebra(A)

Checks whether A is an Ore algebra object.

ore_algebra.ore_algebra.is_suitable_base_ring(R)

Checks whether R is suitable as base ring of an Ore algebra. This is the case if and only if: (a) R is one of ZZ, QQ, GF(p) for a prime p, or a finite algebraic extension of QQ, (b) R is a fraction field of a suitable base ring, (c) R is a (univariate or multivariate) polynomial ring over a suitable base ring.

This function returns True or False.

EXAMPLES:

sage: from ore_algebra.ore_algebra import is_suitable_base_ring
sage: R = GF(1091)['x, y'].fraction_field()['z']
sage: is_suitable_base_ring(R)
True
sage: is_suitable_base_ring(GF(9, 'a'))
False