When factoring a non-trivial linear differential operator in P[δ] := k((t))[δ], with constant field k, differential Laurent Series ring k((t)) in t, and derivation δ, one at least wants to compute two operators L and R in P such that f=L.R. It is important to distinguish the left and right hand operators (L and R) as such as multiplication generally is non-commutative. When considering differential operators in the operator ring P, it is common to consider δ to be t.d/dt. This specific form has the advantage that the degree of δ.t in t remains one, since δ.t=t.δ + t. This specific derivation is called the projective derivation and we consider this derivation in the rest of this section. In this sense powers of t are eigenvectors under the application of the derivation.
A possible approach for factoring a linear operator would be to compute all non-constant irreducible right hand factors and then use recursion on the appropriate left hand factors. However, this causes a problem as there may be infinitely many factorisations. For instance δ2 - δ has infinitely many factorisations (parametrisations) (δ - c/(t + c))(δ - t/(t + c)) for any c∈P1(k). The approach we take to find right hand factors follows [vH97b], and chooses a canonical representative from a class of right hand factors. The obtained representatives can be used in the factorisation of linear differential operators over a rational function field, see [vH97a].
A non-trivial linear differential operator f in P acts on the solution space V of all differential operators in the differential closure of k((t)). This action is bar(k)-linear and surjective on V. The kernel V(f) of this map has dimension equal to the order of the operator. The general solution space V can be split into a direct sum of smaller bar(k)-vector spaces Ve. These are minimal such that f(Ve)⊂Ve for every operator in P. Its kernel Ve(f) consists of all solutions of f(y)=0 in Ve. As a consequence the solution space of the operator then is V(f)= direct-sum e Ve(f). For each of the e with non-trivial solution space of f, the idea now is to find an irreducible right hand factor of f in k((t))[δ] that annihilates Ve(f).
The Newton Polynomial of an operator f and its slopes contain useful information regarding its factorisation possibilities. It was proved by Malgrange that an operator over a Laurent series ring is reducible if its Newton polygon has at least two slopes. When on the other hand the Newton polygon has one positive slope, and the accompanying Newton polynomial has two relatively prime factors, then the operator is irreducible as well. It can be shown that an irreducible right hand factor has an irreducible Newton polynomial that divides the Newton polynomial of f. When an appropriate irreducible factor of the polynomial of f is taken, One can start building a right hand factor operator with coefficients of a certain precision that has exactly the irreducible factor as its Newton polynomial. Subsequently one can try to lift the coefficients to a better, possibly predescribed precision.
Various measures for the precision are possible, for instance the absolute precision of the coefficients is common. Another valuation metric is or one related to the slope of the Newton polynomial. It is defined as follows. Assume that P:=k((t))[δ] has projective derivation t.d/dt, Let s be a rational with numerator n and denominator d such that gcd(n, d)=1 and d>0 hold. Then the slope valuation of a monomial ctiδj, c∈k {0}, with respect to s is defined as Vs(ctiδj):=id - jn. The slope valuation of the operator L∈P with respect to s subsequently is defined as the minimum of the slope valuation of each non-zero monomial in L w.r.t s. Commonly s is a slope of the Newton polynomial of L. If the operator is the zero operator, the slope valuation is defined to be infinite.
Returns the valuation of L, with respect to the rational slope s, when the derivation of L is projective.
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > P<D>:=DifferentialOperatorRing(S); > L:=t^(-2)*D^3+t^7; > SlopeValuation(L,0); -2 > SlopeValuation(L,1/2); -7 > SlopeValuation(L,5); -17 > L:=(0+O(t^6))*D; > SlopeValuation(L,0); Infinity > Valuation(0+O(t^6)); 6 > SlopeValuation(P!0,3); Infinity
Coprime index 1 factorisation and LCLM factorisation are two factorisation methods that use similar factorisation machinery, but may result in different factorisations, see [vH97b]. Given an operator f∈k((t))[δ], both compute a right hand factor with respect to each distinct irreducible factor of the Newton polynomial of f. A local lifting procedure with respect to the slope valuation metric is performed to obtain the coefficients of the right hand factors up to a certain accuracy. In addition, no intermediate differential field extensions of k((t)) are used.
The coprime index 1 algorithm does not factor an operator f that has Newton polynomial of the form pn, n ge2, with slope s>0. The sum of the degrees of the obtained right hand factors of f may be less than the degree of f itself. Their least common left divisor M divides f on the right (i.e. f=N * M) with a kernel of dimension less or equal to deg(f). The LCLM algorithm, on the other hand, produces a set of right hand factors of a monic operator f whose LCLM is exactly f up to some precision.
Precision: RngIntElt Default: -1
Algorithm: MonStgElt Default: "Default"
Returns a sequence M of operator sequences [A, B] such that L=A.B holds, and B does not have a non-trivial coprime index 1 or LCLM factorisation. As the algorithm sometimes cannot conclude if a right hand factor is irreducible, a second sequence entry N[i] states True if the right hand factor M[i][2] is undisputedly irreducible. The optional argument for the precision is the accuracy up to which the lifting procedure would be performed. The default accuracy is the relative precision of the basering of L. The algorithms used can be either "LCLM" or "CoprimeIndexOne". The algorithms used are based on various algorithms in [vH97b].
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> R<D>:=DifferentialOperatorRing(S);
> L := D^2 -D;
> factsL,blsL:=Factorisation(L:Algorithm:="LCLM");
Ring precision as default precision taken.
Performing coprime index 1 LCLM factorisation.
The number of slopes of the Newton polynomial: 1
> (#factsL eq #blsL) and (#factsL eq 1);
true
> blsL;
[ false ]
> factsL[1];
[
1,
D^2 + -1*D
]
> factsL,blsL:=Factorization(L:Algorithm:="CoprimeIndexOne");
Ring precision as default precision taken.
Performing coprime index 1 factorisation.
> (#factsL eq #blsL) and (#factsL eq 1);
true
> blsL;
[ true ]
> factsL[1];
[
D,
D + -1
]
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> R<D>:=DifferentialOperatorRing(S);
> L:=D*(D+1/t);
> L;
D^2 + t^-1*D + -t^-1
> factsL,blsL:=Factorisation(L:Precision:=4);
Performing coprime index 1 LCLM factorisation.
> blsL;
[ true, true ]
> #factsL eq 2;
true
> factsL[1];
[
D + t^-1 + 1 - t + 3*t^2 + O(t^3),
D + -1 + t - 3*t^2 + 13*t^3 + O(t^4)
]
> factsL[2];
[
D,
D + t^-1
]
> factsL:=Factorisation(L:Algorithm:="CoprimeIndexOne");
Ring precision as default precision taken.
Performing coprime index 1 factorisation.
> #factsL eq 2;
true
> blsL;
[ true, true ]
> [v[1]*v[2]:v in factsL];
[
D^2 + (t^-1 + O(t^19))*D + -t^-1 + O(t^19),
D^2 + t^-1*D + -t^-1
]
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> R<D>:=DifferentialOperatorRing(S);
> L:=(D+1/t)*(D+1/t^2);
> L;
D^2 + (t^-2 + t^-1)*D + t^-3 - 2*t^-2
> factsL, blsL:=Factorisation(L:Algorithm:="CoprimeIndexOne",Precision:=6);
Performing coprime index 1 factorisation.
> blsL;
[ true, true ]
> #factsL;
2
> factsL[1];
[
D + t^-2 + 2 + t - 3*t^2 - 8*t^3 + O(t^4),
D + t^-1 - 2 - t + 3*t^2 + 8*t^3 - 9*t^4 + O(t^5)
]
> factsL[2];
[
D + t^-1,
D + t^-2
]
> [v[1]*v[2] :v in factsL];
[
D^2 + (t^-2 + t^-1 + O(t^4))*D + t^-3 - 2*t^-2 + O(t^3),
D^2 + (t^-2 + t^-1)*D + t^-3 - 2*t^-2
]
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> R<D>:=DifferentialOperatorRing(S);
> L:=(D+2/t)^2;
> np:=NewtonPolygon(L);
> faces:=Faces(np);
> #faces eq 1;
true
> NewtonPolynomial(faces[1]);
$.1^2 + 4*$.1 + 4
> factsL_lclm,blsL_lclm:=Factorisation(L);
Ring precision as default precision taken.
Performing coprime index 1 LCLM factorisation.
> factsL_lclm;
[
[
1,
D^2 + 4*t^-1*D + 4*t^-2 - 2*t^-1
]
]
> blsL_lclm;
[ false ]
> factsL_c1,blsL_c1:=Factorisation(L:Algorithm:="CoprimeIndexOne");
Ring precision as default precision taken.
Performing coprime index 1 factorisation.
> factsL_c1 eq factsL_lclm;
true
> blsL_c1 eq blsL_lclm;
true
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > R<D>:=DifferentialOperatorRing(S); > L := (D+1/(t+1))*D; > factsL_c1,blsL_c1:=Factorisation(L:Algorithm:="CoprimeIndexOne"); Ring precision as default precision taken. Performing coprime index 1 factorisation. > (#factsL_c1 eq 1) and (#blsL_c1 eq 1); true > factsL_c1[1][2]; D + O(t^20) > factsL_lclm, blsL_lclm:=Factorisation(L:Algorithm:="LCLM"); Ring precision as default precision taken. Performing coprime index 1 LCLM factorisation. The number of slopes of the Newton polynomial: 1 > (#factsL_lclm eq 1) and (#blsL_lclm eq 1); true > factsL_c1[1][2], blsL_lclm[1]; D + O(t^20) false > M:=(D+1/(t-1))*D; > factsM:=Factorisation(M:Algorithm:="CoprimeIndexOne"); Ring precision as default precision taken. Performing coprime index 1 factorisation. > # factsM eq 1; > factsM[1][2]+O(t^4); D + -1 - 1/2*t - 5/12*t^2 - 3/8*t^3 + O(t^4)
> S<t>:=DifferentialLaurentSeriesRing(Rationals():Precision:=15);
> R<D>:=DifferentialOperatorRing(S);
> L:=(D^5+t^(-1))*D;
> np:=NewtonPolygon(L);
> Slopes(np);
[ 0 , 1/5 ]
> factsL,blsL:=Factorisation(L:Algorithm:="LCLM");
Ring precision as default precision taken.
Performing coprime index 1 LCLM factorisation.
> blsL;
[ true, true ]
> [v[2]:v in factsL];
[
D,
D^5 + (-1 - t - 63*t^2 + O(t^3))*D^4 + (1 + 3*t + 253*t^2 +
O(t^3))*D^3 + (-1 - 7*t - 825*t^2 + O(t^3))*D^2 + (1 + 15*t + 2545*t^2
+ O(t^3))*D + t^-1 - 1 - 31*t - 7713*t^2 + O(t^3)
]
> [v[1]*v[2]:v in factsL];
[
D^6 + t^-1*D,
D^6 + O(t^3)*D^5 + O(t^3)*D^4 + O(t^3)*D^3 + O(t^3)*D^2 + (t^-1 +
O(t^3))*D + O(t^2)
]
> factsL:=Factorisation(L:Algorithm:="LCLM",Precision:=75);
Performing coprime index 1 LCLM factorisation.
> [v[1]*v[2]:v in factsL];
[
D^6 + t^-1*D,
D^6 + O(t^15)*D^5 + O(t^15)*D^4 + O(t^15)*D^3 + O(t^15)*D^2 + (t^-1 +
O(t^15))*D + O(t^14)
]
While resorting to field extensions can result in more complex and time consuming computations, they can be used for obtaining irreducible right hand factors over the original base field.
An effective algorithm to obtain a monic irreducible right hand factor of degree one tilde(L) of L∈k((t))[δ] in some field extension tilde(k)((tilde(t)))[tilde(δ)] is presented in [vH97b, Para 5.1]. Such a factor tilde(L)=tilde(δ) - r(tilde(t)) of L is called a Ricatti factor of L. The operator mathop(LCLM)(tilde(δ) - σ1(r), tilde(δ) - σ2(r), ..., tilde(δ) - σm(r)) where the σi are the Galois group elements of tilde(k)((tilde(t)))/k((t)), then is a monic and irreducible operator invariant under the Galois action. Hence, it naturally reduces to a monic irreducible right hand factor of L.
Other right hand factors of L, that may be defined over a finite field extensions of k((t)) are the so-called semi-regular parts of L. Such an operator Re(L) is the monic right hand semi-regular factor of the translation Se(L) of L by e. Its degree is equal to the dimension of a non-trivial bar(k)-linear vector space Ve(L), and acts as zero on it. In other words S - e(Re) is a monic right hand factor of L, possibly defined over a field extension of k((t)). It can be shown that L is the least common left multiple of all such right hand factors.
The routine RightHandFactors returns right hand factors of a given operator possibly by using temporary field extensions. Each of these are canonical representatives of all right hand factors belonging the slopes of the Newton polynomial of the operator. Currently one of the internal routines may fail when performing calculations for some specific right hand factor. In this case we cannot conclude it to be irreducible.
Precision: RngIntElt Default: -1
The canonical list of monic right hand factors of L, one per slope of the Newton polynomial of L. The ith entry in the second sequence returned is true if the ith right hand factor is undisputedly irreducible. The precision attribute relates to the absolute precision a coefficient in a right hand factor should minimally have.
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > RS<DS> := DifferentialOperatorRing(S); > L:=DS^2+(1/t^2+1/t)*DS +(1/t^3-2/t^2); > rhf, bl := RightHandFactors(L); Performing coprime index 1 LCLM factorisation. > #rhf eq 2; true > bl; [ true, true ] > (Parent(rhf[1]) eq RS) and (Parent(rhf[2]) eq RS); true > lhf,rem := EuclideanRightDivision(L, rhf[1]); > rem; O(t^20) > lhf*rhf[1]; DS^2 + (t^-2 + t^-1 + O(t^22))*DS + t^-3 - 2*t^-2 + O(t^20) > EuclideanRightDivision(L, rhf[2]); DS + t^-1 0
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > RS<DS> := DifferentialOperatorRing(S); > L:=DS^2-3/2*DS+(2*t-1)/(4*t); > rhf, bl := RightHandFactors(L); Performing coprime index 1 LCLM factorisation. > bl; [ true ] > #rhf eq 1; true > rhf[1] eq L; true
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> RS<DS> := DifferentialOperatorRing(S);
> L:=(DS+2/t)^2;
> rhf, bl := RightHandFactors(L);
Performing coprime index 1 LCLM factorisation.
Calculating semi-regular parts.
Performing coprime index 1 LCLM factorisation.
Performing coprime index 1 LCLM factorisation.
Computing a first order Ricatti factor.
Performing LCLM calculation on the Ricatti factor.
> rhf;
[
DS + 2*t^-1
]
> bl;
[ true ]
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > RS<DS> := DifferentialOperatorRing(S); > L:=DS^2 +(4+2*t-t^2-3*t^3)/(t^2)*DS+ (4+4*t-5*t^2-8*t^3-3*t^4+2*t^6)/(t^4); > np:=NewtonPolygon(L); > faces:=Faces(np); > #faces eq 1; true > _<T> := PolynomialRing(Rationals()); > NewtonPolynomial(faces[1]); T^2 + 4*T + 4 > factsL, blsL := Factorisation(L); Ring precision as default precision taken. Performing coprime index 1 LCLM factorisation. > blsL; [ false ] > (#factsL eq 1) and (factsL[1][2] eq L); true > rhf, bl := RightHandFactors(L); Performing coprime index 1 LCLM factorisation. Calculating semi-regular parts. Performing coprime index 1 LCLM factorisation. Performing coprime index 1 LCLM factorisation. Performing coprime index 1 LCLM factorisation. Computing a first order Ricatti factor. Performing LCLM calculation on the Ricatti factor. > Degree(rhf[1]); 1 > bl; [ true ] > Parent (rhf[1]) eq RS; true > L - EuclideanRightDivision(L, rhf[1])*rhf[1]; O(t^22)*DS + O(t^20)
> S<t>:=DifferentialLaurentSeriesRing(Rationals());
> RS<DS> := DifferentialOperatorRing(S);
> L := DS^4-1/t^4;
> faces:=Faces(NewtonPolygon(L));
> faces;
[ <-1, 1, -4> ]
> _<T> := PolynomialRing(Rationals());
> NewtonPolynomial(faces[1]);
T^4 - 1
> rhf, bl := RightHandFactors(L);
Performing coprime index 1 LCLM factorisation.
> bl;
[ true, true, true ]
> [Degree(v) : v in rhf];
[ 1, 1, 2 ]
> L - EuclideanRightDivision(L, rhf[1])*rhf[1];
O(t^23)*DS^3 + O(t^22)*DS^2 + O(t^21)*DS + O(t^20)
> L - EuclideanRightDivision(L, rhf[2])*rhf[2];
O(t^23)*DS^3 + O(t^22)*DS^2 + O(t^21)*DS + O(t^20)
> L - EuclideanRightDivision(L, rhf[3])*rhf[3];
O(t^23)*DS^3 + O(t^22)*DS^2 + O(t^21)*DS + O(t^20)
> M := DS^4-1;
> faces:=Faces(NewtonPolygon(M));
> faces;
[ <0, 1, 0> ]
> NewtonPolynomial(faces[1]);
T^4 - 1
> rhf, bl := RightHandFactors(M);
Performing coprime index 1 LCLM factorisation.
Calculating semi-regular parts.
Performing coprime index 1 LCLM factorisation.
Performing LCLM calculation on a semi-regular part.
Calculating semi-regular parts.
Performing coprime index 1 LCLM factorisation.
Computing a first order Ricatti factor.
Performing LCLM calculation on the Ricatti factor.
> rhf;
[
DS^2 + 1,
DS + -1
]
> bl;
[ true, true ]
> S<t>:=DifferentialLaurentSeriesRing(Rationals()); > RS<DS> := DifferentialOperatorRing(S); > L:=DS^9 + 2*t^-1*DS^8 + 3*t^-2*DS^7 + 2*t^-3*DS^6 + (t^-4 + 2*t^-2)*DS^5 + > (-3*t^-5 + 5*t^-4)*DS^3 + 3*t^-5*DS^2 + (2*t^-6 + 2*t^-5)*DS + 7*t^-5; > facts := Factorisation(L); Ring precision as default precision taken. Performing coprime index 1 LCLM factorisation. > [Degree(v[2]): v in facts]; [ 1 2 2 4 ] > isweaklyzero := []; > vals :=[]; > for i in [1..4] do > _,rem := EuclideanRightDivision(L, facts[i][2]); > isweaklyzero[i] := IsWeaklyZero(rem); > vals[i] := [Valuation(v) : v in Eltseq(rem)]; > end for; > isweaklyzero; [ true, true, true, true ] > [Minimum(v) : v in vals]; [ 14 , 4 , 4 , 11] > rhf, bl := RightHandFactors(L:Precision:=30); Performing coprime index 1 LCLM factorisation. Calculating semi-regular parts. Performing coprime index 1 LCLM factorisation. Performing coprime index 1 LCLM factorisation. Performing coprime index 1 LCLM factorisation. Performing LCLM calculation on a semi-regular part. Computation of the LCLM failed. > bl; [ true, true, true, false ] > [Degree(v): v in rhf]; [ 1 2 2 4 ] > isweaklyzero := []; > vals := []; > for i in [1..4] do > [Degree(v): v in Eltseq(rhf[i])]; > _,rem := EuclideanRightDivision(L, rhf[i]); > isweaklyzero[i] := IsWeaklyZero(rem); > vals[i] := [Valuation(v) : v in Eltseq(rem)]; > end for; [ 35, 0 ] [ 35, 35, 0 ] [ 35, 35, 0 ] [ 31, 32, 33, 34, 0 ] > isweaklyzero; [ true, true, true, true ] > [ Minimum(v) : v in vals]; [ 30, 30, 30, 27 ]