|
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.
Factorization(L) : RngDiffOpElt -> SeqEnum, SeqEnum
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].
The operator t 2.d/dt 2 - t.d/dt with coefficients in Q
has infinitely many factorisations, since it can be written as
(t.d/dt - c/(t + c)).(t.d/dt - t/(t + c)) for any rational
number c.
The factorisation code chooses a canonical right hand factor.
> 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
]
This example corresponds to Example 3.46 in [vdPS03].
> 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
]
This example corresponds to Example 3.49 in [vdPS03].
> 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
]
This example shows that not all operators may be factored by the factorisation routine.
Notice that the Newton polynomial of the operator is a square of a polynomial.
> 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
This example shows that one may not retrieve the factorisation as expected.
> 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)
One may wish to adjust the default precision to retrieve
enough terms in the coefficients in the factors.
This example shows the effect on a rational slope 1/5
on the number of terms in the series coefficients of the
factors obtained.
> 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.
This example is Example 3.49 from [vdPS03].
The same right hand factors as
in Example H121E68
are obtained.
> 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
This example corresponds to Example 3.52 in [vdPS03].
The answer in the book is erroneous.
> 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
The operator in this example is the same as in
Example H121E69
where the routine Factorisation was used.
The operator did not factor there, but does
when using RightHandFactors.
> 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 ]
This example corresponds to Example 3.53 in [vdPS03].
> 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)
A collection of operators having the same Newton
polynomial (T 2 + 1)(T - 1)(T + 1).
> 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 ]
This is the main example of [vH97b].
> 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 ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|