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: Euclidean Right and Left Division (ex-872ed1)

Run in calculator (opens in a new tab)

> 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 (opens in a new tab)

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: Greatest Common Right and Left Divisors (ex-5508d6)

Run in calculator (opens in a new tab)

> 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 (opens in a new tab)

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: Least Common Left Multiples (ex-22d5f6)

Run in calculator (opens in a new tab)

> 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 (opens in a new tab)

Example: Least Common Left Multiple of Conjugates (ex-138207)

Run in calculator (opens in a new tab)

> 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 (opens in a new tab)