ore_algebra¶

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)

class 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: 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: delta.dict()
{x1: 1, x3: x3}

dict()¶: Returns a dictionary representing self

ring()¶: Returns the ring for which this sigma object is defined

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,b\in 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 \(u\in 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: 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\}\) \(\{\}\)

Δ, F Forward difference \(\{x:x+1\}\) \(\{x:1\}\)

θ, 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.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.OreAlgebra_generic(base_ring, operator_class, gens, solvers, 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: 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\)

base_ring()¶: Returns this algebra’s base ring

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: 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 list 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.

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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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}

var(n=0)¶

Returns the name of the \(n\) th generator of this algebra.

EXAMPLES:

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: A.<Dx> = OreAlgebra(QQ['x'], 'Dx')
sage: A.variable_names() 
('Dx',)

class 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: 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: sigma.dict()
{'x2': -x2 + 1, 'x3': x3 + 1, 'x1': 2*x1}    

dict()¶: Returns a dictionary representing self

factorial(p, n)¶: Returns \(p\sigma(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: 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.is_OreAlgebra(A)¶: Checks whether \(A\) is an Ore algebra object.

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: R = GF(1091)['x, y'].fraction_field()['z']
sage: is_suitable_base_ring(R)
True
sage: is_suitable_base_ring(GF(9, 'a'))
False

ore_algebra¶

Previous topic

Next topic

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

Navigation

ore_algebra¶

Previous topic

Next topic

Quick search

Navigation