Ore_algebra, a Package for Skew Operators
Several algorithms for integration and summation have a natural description in terms of linear differential and difference operators, which in turn are well described by skew (or Ore) polynomials. This was the starting point for the Ore_algebra package.
restart:
withOre_algebra;
Ore_to_DESol,Ore_to_RESol,Ore_to_diff,Ore_to_shift,annihilators,applyopr,diff_algebra,dual_algebra,dual_polynomial,poly_algebra,qshift_algebra,rand_skew_poly,reverse_algebra,reverse_polynomial,shift_algebra,skew_algebra,skew_elim,skew_gcdex,skew_pdiv,skew_power,skew_prem,skew_product
Declaration of an Ore algebra
To work with an Ore algebra, we first have to declare it. The package creates a table that implements and remembers the operations in this algebra. Here is the example of the algebra of linear differential operators in the differential operator Dx with (rational) coefficients in x.
A:=diff_algebra⁡Dx,x
A:=Ore_algebra
(This is the name of the table.)
Although the usual product in Maple is commutative, we use `*` to denote skew products, with the convention that powers of Dx are on the right.
Multiplication of operators is obtained by the function skew_product.
P1:=x⁢Dx2−1:P2:=Dx−x:P1_P2:=skew_product⁡P1,P2,A
P1_P2:=x+−2⁢x−1⁢Dx+x⁢Dx3−x2⁢Dx2
Remember that in skew algebras of linear operators, factorizations are seldom unique.
DEtoolsDFactorP1_P2,Dx,x
x⁢Dx2−1x,Dx−x
A First Application
(Univariate) Ore polynomial rings have a Euclidean algorithm. This is implemented in the following routines: skew_pdiv, skew_prem, skew_gcdex, and skew_elim. An extension to the multivariate case is available through Groebner bases computations (see Groebner and in particular Groebner[Basis] and Groebner[Reduce]).
Here we show how the package can be used to derive a proof of the Reed-Dawson identity:
Un=∑k=0nbinomial⁡n,k⁢binomial⁡2⁢k,k⁢−2n−k
is
binomial⁡n,n2
binomial⁡n,12⁢n
for even n and 0 for odd n.
Let us introduce an algebra of linear recurrence operators in n and k. Sn and Sk denote the shift operators in n and k, respectively.
A:=shift_algebra⁡Sn,n,Sk,k,polynom=k:
We compute first-order recurrences satisfied by the summand (which we denote by h).
h:=binomial⁡n,k⁢binomial⁡2⁢k,k⁢−2n−k
Sn−normal⁡applyopr⁡Sn,h,Ah,expanded
Sn−−2⁢n−2n+1−k
Sk−normal⁡applyopr⁡Sk,h,Ah,expanded
Sk−2⁢k2−2⁢n⁢k+k−nk2+2⁢k+1
G:=mapnumer,,:
We eliminate k between these operators by computing their greatest common right divisor.
GCD:=skew_gcdex⁡op⁡G,k,A
GCD:=−8⁢n2−16−24⁢n+4⁢Sk⁢Sn2⁢n+4⁢Sn2⁢Sk+Sk⁢Sn2⁢n2−12⁢Sn−14⁢Sn⁢n−4⁢Sn⁢n2+12⁢Sn⁢Sk+14⁢Sk⁢Sn⁢n+4⁢Sk⁢Sn⁢n2+8⁢Sk+4⁢Sk⁢n2+12⁢Sk⁢n,Sn2,−8−4⁢n+Sn⁢Sk⁢k−Sn−−3−n⁢Sn⁢Sk−−2⁢n−4⁢Sk−2⁢Sn⁢k,2⁢Sn2⁢n+6⁢Sn2+Sn3⁢n+2⁢Sn3−Sn3⁢k,−Sn2⁢Sk−Sn2⁢n−2⁢Sn2−2⁢Sn2⁢Sk⁢k−3⁢Sn2⁢k−2⁢k⁢Sn2⁢n−Sn2⁢Sk⁢k2+2⁢Sn2⁢k2
series⁡GCD1,Sk=1
−4⁢n2−8−12⁢n+4⁢Sn2⁢n+4⁢Sn2+Sn2⁢n2+12⁢Sn+14⁢Sn⁢n+4⁢Sn2⁢n+4⁢Sn⁢n2+8+4⁢Sn2+4⁢n2+Sn2⁢n2+12⁢n⁢Sk−1
The factor Sk−1 corresponds to taking a finite difference. Definite summation for k over all integers yields a telescoping series that collapses to 0. We therefore get:
∑k=−∞∞applyopr⁡coeff⁡,Sk−1,0,un,k,A=0
∑k=−∞∞−8−4⁢n2−12⁢n⁢un,k+4⁢n+4+n2⁢un+2,k=0
Therefore, the sum Un satisfies
collect⁡primpart⁡coeff⁡,Sk−1,0,Sn,Sn,normal
n+2⁢Sn2−4−4⁢n
applyopr⁡,Un,A
−4−4⁢n⁢Un+n+2⁢Un+2
Now, the announced result follows from the initial conditions:
For n=1,
U1:=add⁡subs⁡n=1,h,k=0..1
U1:=0
so that Un=0 for odd n.
For n=0,
U0:=add⁡subs⁡n=0,h,k=0..0
U0:=1
so that V⁡p=U2⁢p is given by
2⁢p+1⁢V⁡p+1−4⁢2⁢p+1⁢V⁡p
LREtoolshypergeomsols,Vp,V⁡0=1,output=basis
4p⁢Γ⁡p+12Γ⁡p+1
which is binomial⁡2⁢p,p.
A More Advanced Application
Here we derive contiguity relations for the Gauss hypergeometric function. This function is known to Maple as:
f:=hypergeom⁡a,b,c,z
It is ∑n=0∞un⁢zn for
u:=pochhammer⁡a,n⁢pochhammer⁡b,npochhammer⁡c,n⁢n!:
When considering the summand, we introduce the following algebra:
A:=shift_algebra⁡Sn,n,Sa,a,comm=b,c:
The bivariate sequence u vanishes at both of the following operators:
G:=c+n⁢n+1⁢Sn−a+n⁢b+n,a⁢Sa−a+n:
normal⁡map⁡applyopr,G,u,A,expanded
0
(General algorithms exist to find such operators.)
From the previous first-order recurrences, we derive relations on f in the mixed differential difference algebra.
A:=skew_algebradiff=Dz,z,shift=Sa,a,comm=b,c:
The equations are obtained by multiplication of the recurrences by zn, followed by summation over all non-negative n. Formally, this corresponds to changing Sn into 1z and n into z⁢Dz.
mapprocpcollect⁡add⁡add⁡coeff⁡coeff⁡p,Sn,i,n,j*skew_product⁡skew_power⁡z*Dz,j,A,1/z^i,A,j=0..degree⁡coeff⁡p,Sn,i,n,i=0..degree⁡p,Sn,Dz,factorend proc,G
−z⁢z−1⁢Dz2+c−z−z⁢a−z⁢b⁢Dz−a⁢b,−z⁢Dz+a⁢Sa−1
Therefore, we set
P:=z⁢1−z⁢Dz2+c−a+b+1⁢z⁢Dz−a⁢b:
H:=z⁢Dza+1:
G:=P,numer⁡Sa−H
G:=a⁢Sa−a−z⁢Dz,z⁢−z+1⁢Dz2+c−a+b+1⁢z⁢Dz−a⁢b
The linear differential operator Sa=z⁢Dza+1 is called a step-up operator. It relates the forward shift of f to derivatives of t by the following equation.
hypergeom⁡a+1,b,c,z=z⁢ⅆⅆz⁢hypergeom⁡a,b,c,za+hypergeom⁡a,b,c,z
hypergeom⁡b,a+1,c,z=z⁢b⁢hypergeom⁡b+1,a+1,c+1,zc+hypergeom⁡a,b,c,z
The elimination of Dz between this step-up operator and the differential equation yields a contiguity relation for f--a purely recurrence equation. It is obtained by the extended skew gcd algorithm:
C:=collect⁡skew_elim⁡P,numer⁡Sa−H,Dz,A,Sa,factor
C:=−z−1⁢a+1⁢Sa2+z−2⁢a−z⁢b−2+z⁢a+c⁢Sa−c+1+a
In other words, the Gauss hypergeometric function satisfies the following equation:
applyopr⁡C,hypergeom⁡a,b,c,z,A=0
−c+1+a⁢hypergeom⁡a,b,c,z−z−1⁢a+1⁢hypergeom⁡a+2,b,c,z+z−2⁢a−z⁢b−2+z⁢a+c⁢hypergeom⁡a+1,b,c,z=0
More interestingly, the extended Euclidean algorithm yields a step-down operator for f - a relation between an inverse shift of f and its derivatives. This is obtained by computing an inverse of H modulo P.
GCD:=skew_gcdex⁡P,numer⁡H,Dz,A
GCD:=−c⁢a+a+a2,z,1−−z2+z⁢Dz−c+z⁢b+a,−z⁢Dz−a−1,−z2⁢Dz2+z⁢Dz2−Dz⁢z⁢a−Dz⁢z⁢b−2⁢z⁢Dz−b−a⁢b+Dz⁢c
From this result, we have GCD2⁢P+GCD3⁢numer⁡H=GCD1 and GCD4⁢P+GCD5⁢numer⁡H=0. In particular,
B:=collect⁡a−1⁢subs⁡a=a−1,GCD3GCD1,Dz,factor
B:=z⁢z−1⁢Dza−c+−c+z⁢b+aa−c
is the step-down operator:
hypergeom⁡a−1,b,c,z=z⁢1−z⁢ⅆⅆz⁢hypergeom⁡a,b,c,za−c+c−a−z⁢b⁢hypergeom⁡a,b,bc,zc−a
hypergeom⁡b,a−1,c,z=z⁢−z+1⁢a⁢b⁢hypergeom⁡b+1,a+1,c+1,zc⁢a−c+c−a−z⁢b⁢hypergeom⁡a,b,bc,zc−a
An algorithm is also available to compute (one-sided) Groebner bases in Ore algebras. This is demonstrated in the presentation of the Groebner package.
Return to Index for Example Worksheets
Download Help Document