Ore_algebra, a Package for Skew Operators

はじめる前に
新機能一覧
Maple ワークシートの作成
Mapleワークシートを共有
Maple ウィンドウのカスタマイズ
Maple システムのカスタマイズ
コネクティビティ
Mathematics
数学
- テンソル解析
- パッケージ
- ファンクションアドバイザ
- ベキ級数
- ベクトル解析
- 不活性関数
- 代数
  - Magma
  - 多項式
  - 式の処理
  - 有理式表現
  - 歪多項式
    - Ore Algebra
    - OreTools
    - Ore Algebra サンプル
- 因数分解と方程式解法
- 基本数学
- 基本的な注意事項
- 変分法
- 変換
- 幾何
- 微分代数方程式
- 微分幾何学
- 微分方程式
- 微積分
- 数
- 数値計算
- 数学関数
- 数論
- 最適化
- 特殊関数
- 統計
- 線形代数
- 群論
- 評価
- 論理
- 過去のパッケージ
- 金融
- 離散数学
- piecewise examples
- グラフ電卓
- 区分関数
物理
プログラミング
グラフィックス
Student パッケージ
Science and Engineering
科学・エンジニアリング
アプリケーションと例題
リファレンス
システム
MapleSim
MapleSim ツールボックス
MapleSim ヘルプ
Tasks
Toolboxes
エラーメッセージガイド
マニュアル
数学アプリ

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.

[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]

(1)

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 with (rational) coefficients in .

(1.1)

(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 are on the right.

Multiplication of operators is obtained by the function skew_product.

(1.2)

Remember that in skew algebras of linear operators, factorizations are seldom unique.

(1.3)

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:

U[n] = Sum(binomial(n, k)*binomial(2*k, k)*(-2)^(n-k), k = 0 .. n)

(2.1)

(2.2)

for even and for odd .

Let us introduce an algebra of linear recurrence operators in and . and denote the shift operators in and , respectively.

We compute first-order recurrences satisfied by the summand (which we denote by ).

(2.3)

(2.4)

Sk-(2*k^2-2*n*k+k-n)/(k^2+2*k+1)

(2.5)

>	$G := map(numer, {Sn-(-2n-2)/(n+1-k), Sk-(2k^2-2nk+k-n)/(k^2+2*k+1)}):$

We eliminate between these operators by computing their greatest common right divisor.

[-8*n^2-16-24*n+4*Sk*Sn^2*n+4*Sn^2*Sk+Sk*Sn^2*n^2-12*Sn-14*Sn*n-4*Sn*n^2+12*Sn*Sk+14*Sk*Sn*n+4*Sk*Sn*n^2+8*Sk+4*Sk*n^2+12*Sk*n, Sn^2, -8-4*n+Sn*Sk*k-Sn-(-3-n)*Sn*Sk-(-2*n-4)*Sk-2*Sn*k, 2*Sn^2*n+6*Sn^2+Sn^3*n+2*Sn^3-Sn^3*k, -Sn^2*Sk-Sn^2*n-2*Sn^2-2*Sn^2*Sk*k-3*Sn^2*k-2*k*Sn^2*n-Sn^2*Sk*k^2+2*Sn^2*k^2]

(2.6)

(2.7)

The factor corresponds to taking a finite difference. Definite summation for over all integers yields a telescoping series that collapses to 0. We therefore get:

Sum(applyopr(coeff(series((-4*n^2-8-12*n+4*Sn^2*n+4*Sn^2+Sn^2*n^2)+(12*Sn+14*Sn*n+4*Sn^2*n+4*Sn*n^2+8+4*Sn^2+4*n^2+Sn^2*n^2+12*n)*(Sk-1),Sk = 1), Sk-1, 0), u[n, k], A), k = -infinity .. infinity) = 0

Sum((-8-4*n^2-12*n)*u[n, k]+(4*n+4+n^2)*u[n+2, k], k = -infinity .. infinity) = 0

(2.8)

Therefore, the sum satisfies

(2.9)

(2.10)

Now, the announced result follows from the initial conditions:

For ,

(2.11)

so that for odd .

For ,

(2.12)

so that is given by

(2.13)

[4^p*GAMMA(p+1/2)/GAMMA(p+1)]

(2.14)

which is .

A More Advanced Application

Here we derive contiguity relations for the Gauss hypergeometric function. This function is known to Maple as:

(3.1)

It is Sum(u[n]*z^n, n = 0 .. infinity) for

When considering the summand, we introduce the following algebra:

>	$A := shift_algebra([Sn, n], [Sa, a], comm = {b, c})$

The bivariate sequence vanishes at both of the following operators:

(3.2)

(General algorithms exist to find such operators.)

From the previous first-order recurrences, we derive relations on in the mixed differential difference algebra.

>	$A := skew_algebra(diff = [Dz, z], shift = [Sa, a], comm = {b, c})$

The equations are obtained by multiplication of the recurrences by , followed by summation over all non-negative . Formally, this corresponds to changing into and into .

map(proc (p) collect(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, factor) end proc, G)

${-z*(z-1)*Dz^2+(c-z-z*a-z*b)*Dz-a*b, -z*Dz+a*(Sa-1)}$

(3.3)

Therefore, we set

${a*Sa-a-z*Dz, z*(-z+1)*Dz^2+(c-(a+b+1)*z)*Dz-a*b}$

(3.4)

The linear differential operator is called a step-up operator. It relates the forward shift of to derivatives of by the following equation.

hypergeom([a+1, b], [c], z) = z*(diff(hypergeom([a, b], [c], z), z))/a+hypergeom([a, b], [c], z)

(3.5)

The elimination of between this step-up operator and the differential equation yields a contiguity relation for --a purely recurrence equation. It is obtained by the extended skew gcd algorithm:

(3.6)

In other words, the Gauss hypergeometric function satisfies the following equation:

(3.7)

More interestingly, the extended Euclidean algorithm yields a step-down operator for - a relation between an inverse shift of and its derivatives. This is obtained by computing an inverse of modulo .

(3.8)

From this result, we have and . In particular,

B := collect((a-1)*subs(a = a-1, GCD[3]/GCD[1]), Dz, factor)

(3.9)

is the step-down operator:

hypergeom([a-1, b], [c], z) = z*(1-z)*(diff(hypergeom([a, b], [c], z), z))/(a-c)+(c-a-z*b)*hypergeom([a, b], [bc], z)/(c-a)

hypergeom([b, a-1], [c], z) = z*(-z+1)*a*b*hypergeom([b+1, a+1], [c+1], z)/(c*(a-c))+(c-a-z*b)*hypergeom([a, b], [bc], z)/(c-a)

(3.10)

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