Euclidean Algorithms, GCDs and LCMs#

A ring of differential operators shares many properties with a univariate polynomial ring. Two of them are GCD and LCM algorithms. However, a consequence of the non–commutative multiplication of a differential operator ring is that the GCD and LCM algorithms cannot be used directly. For instance, in the euclidean algorithm multiplication of the quotient can be done on the left or the right. Therefore one needs to specify the direction of the multiplication in the GCD and LCM algorithms for differential operator rings.

Euclidean Right and Left Division#

EuclideanRightDivision(N, D): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt, RngDiffOpElt#: Given differential operators \(N\) and \(D\), return two differential operators \(Q\) and \(R\), such that \(N=Q\cdot D + R\), with Degree(R) < Degree(D). An error occurs if \(D\) is \(0\).

EuclideanLeftDivision(D, N): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt, RngDiffOpElt#: Given differential operators \(D\) and \(N\), return two differential operators \(Q\) and \(R\), such that \(N=D\cdot Q + R\), with Degree(R) < Degree(D). An error occurs if \(D\) is \(0\).

Example Eucl Alg (ex-872ed1)#

> F<z> := RationalDifferentialField(Rationals());
> R<D> := DifferentialOperatorRing(F);
> L1 := D;
> L2 := (D-3)*(D+z);
> EuclideanRightDivision(L1, L2);
0
D
> Q, R := EuclideanRightDivision(L2, L1);
> Q, R;
D + z - 3
-3*z + 1
> L2 eq Q*L1+R;
true
> EuclideanLeftDivision(L2, L1);
0
D
> S, T := EuclideanLeftDivision(L1, L2);
> S, T;
D + z - 3
-3*z
> L2 eq L1*S+T;
true

Run in calculator

Greatest Common Right and Left Divisors#

GreatestCommonRightDivisor(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#
GCRD(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#: Given two differential operators \(A, B\in R\), return the unique monic differential operator \(G\in R\) that generates the left ideal \(R A+R B\).

ExtendedGreatestCommonRightDivisor(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt, RngDiffOpElt, RngDiffOpElt#: Given two differential operators \(A, B\in R\), this function returns three operators \(G,U,V\in R\), that satisfy \(U\cdot A + V\cdot B =G\). The differential operator \(G\) is the unique monic right GCD of \(A\) and \(B\).

GreatestCommonLeftDivisor(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#
GCLD(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#: Given two differential operators \(A, B\in R\), return the unique monic differential operator \(G\in R\) that generates the right ideal \(AR+BR\).

ExtendedGreatestCommonLeftDivisor(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt, RngDiffOpElt, RngDiffOpElt#: Given two differential operators \(A, B\in R\), this function returns three operators \(G,U,V\in R\), that satisfy \(A\cdot U + B\cdot V =G\). The differential operator \(G\) is the unique monic left GCD of \(A\) and \(B\).

Example GCRD GCLD (ex-5508d6)#

> F<z> := RationalDifferentialField(Rationals());
> R<D> := DifferentialOperatorRing(F);
> L1 := D^3+z*D^2+D-z;
> L2 := D^2+(z-3)*D-3*z+1;
> GreatestCommonRightDivisor(L1, L2);
D + z
> GreatestCommonRightDivisor(L1, L2) eq GCRD(L1, L2);
true
> G, U, V :=ExtendedGreatestCommonRightDivisor(L1, L2);
> G, U, V;
D + z
1/8
-1/8*D + -3/8
> G eq U*L1+V*L2;
true
> GreatestCommonLeftDivisor(L1, L2);
1
> GCLD(L2,L2*L1) eq L2;
true

Run in calculator

Least Common Left Multiples#

LeastCommonLeftMultiple(L): RngDiffOpElt -> RngDiffOpElt#: Let \(L=D-r\) be a monic operator of degree \(1\) in \(R=F[D]\). Return the least common left multiple of \(L\) and all its conjugates over the base ring of \(F\), with respect to the coercion of this base ring into \(F\).

LeastCommonLeftMultiple(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#
LCLM(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt#: Given two differential operators \(A, B\in R\), return the unique monic differential operator \(L\in R\), that generates the left ideal \(RA\cap RB\). The order of the least common multiple of \(A\) and \(B\) is at most Order(A)+ Order(B).

ExtendedLeastCommonLeftMultiple(A, B): RngDiffOpElt, RngDiffOpElt -> RngDiffOpElt, RngDiffOpElt, RngDiffOpElt#: Given two differential operators \(A, B\in R\), return three operators \(L,U,V\in R\), that satisfy \(L=U\cdot A= V\cdot B\). The differential operator \(L\) is the unique monic left LCM of \(A\) and \(B\).

ExtendedLeastCommonLeftMultiple(S): [RngDiffOpElt] -> RngDiffOpElt, SeqEnum#: Given the non–empty sequence of differential operators \(S\), this function returns the unique monic left LCM \(L\) of the entries of \(S\), as well as a sequence \(Q\) of length \(\#S\), satisfying \(L=Q[i]\cdot S[i]\) for \(i=1,2,\ldots,\#S\).

Example LCLM (ex-22d5f6)#

> F<z> := RationalDifferentialField(Rationals());
> R<D> := DifferentialOperatorRing(F);
> LCLM(D, D-z);
D^2 + (-z^2 - 1)/z*D
> L1 := D^3+z*D^2+D-z;
> L2 := D^2+(z-3)*D-3*z+1;
> LeastCommonLeftMultiple(L1, L2);
D^4 + (z - 3)*D^3 + (-3*z + 2)*D^2 + (-z - 3)*D + 3*z - 1
> L, U, V := ExtendedLeastCommonLeftMultiple(L1, L2);
> L, U, V;
D^4 + (z - 3)*D^3 + (-3*z + 2)*D^2 + (-z - 3)*D + 3*z - 1
D + -3
D^2 + -1
> L eq U*L1;
true
> L eq V*L2;
true
> L, Q := ExtendedLeastCommonLeftMultiple([D,D+1,z*D+1]);
> L;
D^3 + (z^2 - 6)/(z^2 - 2*z)*D^2 + (2*z - 6)/(z^2 - 2*z)*D
> Q[3]*(z*D+1) eq L;
true

Run in calculator

Example LCLM Conjugates (ex-138207)#

> F<z> := RationalDifferentialField(Rationals());
> P<T> := PolynomialRing(F);
> M<u> := ext<F|T^2+T+1>;
> RM<DM> := DifferentialOperatorRing(M);
> LeastCommonLeftMultiple(DM-u^2);
DM^2 + DM + 1
> lclm := LeastCommonLeftMultiple(DM-u+1);
DM^2 + 3*DM + 3
> EuclideanRightDivision(lclm, DM-u+1);
DM + u + 2
0
> N<v>, mp := ext<F|T^2-z>;
> RN<DN> := DifferentialOperatorRing(N);
> lclm := LeastCommonLeftMultiple(DN-v);
> lclm;
DN^2 + -1/2/z*DN + -z
> LeastCommonLeftMultiple(DN-v, DN+v) eq lclm;
true
> EuclideanRightDivision(lclm,DN-v);
DN + v - 1/2/z
0
> EuclideanRightDivision(lclm,DN+v);
DN + -v - 1/2/z
0

Run in calculator