Various simple operations for polynomials as well as root finding and factorization functions have been implemented for polynomials over local rings and fields.
A number of functions for polynomials in general are applicable for polynomials over local rings and fields. Arithmetic functions, including div and mod can be used with such polynomials (though there may be some precision loss), as well as all the elementary functions to access coefficients and so forth. Derivatives can be taken and polynomials over local rings and fields can be Evaluated at elements coercible into the coefficient ring. Along with GCD for these polynomials, the LeastCommonMultiple of two polynomials can also be found.
Although the ring of polynomials over a local ring is not a principal ideal domain, it is useful to have a GCD function available without explicitly using local fields. For example, for polynomials which are co--prime over the local field, the ideal generated by the two polynomials contains some power of the uniformizing element of the local ring. This power determines whether an approximate factorization can be lifted to a proper factorization. For best results polynomials should be over an infinite precision ring whenever possible.
Determine the greatest common divisor of g and h where g and h are over a local ring or field. The Gcd returned is such that the cofactors of the polynomials will have coefficients in the ring (if the polynomial is not over a field). The process of computing the Gcd of two polynomials may result in some inaccuracy.
> L<b> := LocalRing(5, x^2 + 3, x^3 + 5*x^2 + 5);
> R<x> := PolynomialRing(L);
> K<pi> := TotallyRamifiedExtension(L, x^6 + b);
> K;
Local Ring with Eisenstein polynomial x^18 - 5*x^12 - 5 over Inertia Ring of
degree 3 over 5-adic Ring
> R<x> := PolynomialRing(K);
> f := (x + pi)^3*(x + pi + 1)^2*(x + pi^7 + pi^19);
> f;
x^6 + (2 + 10*pi + pi^7 + 5*pi^13)*x^5 + (1 + 18*pi + 35*pi^2 + 2*pi^7 + 5*pi^8
+ 10*pi^13 + 25*pi^14)*x^4 + (8*pi + 52*pi^2 + 60*pi^3 + pi^7 + 8*pi^8 +
10*pi^9 + 5*pi^13 + 40*pi^14 + 50*pi^15)*x^3 + (18*pi^2 + 68*pi^3 + 55*pi^4
+ 3*pi^8 + 12*pi^9 + 10*pi^10 + 15*pi^14 + 60*pi^15 + 50*pi^16)*x^2 +
(16*pi^3 + 42*pi^4 + 26*pi^5 + 3*pi^9 + 8*pi^10 + 5*pi^11 + 15*pi^15 +
40*pi^16 + 25*pi^17)*x + 25 + 5*pi^4 + 10*pi^5 + 5*pi^6 + pi^10 + 2*pi^11 +
26*pi^12 + 5*pi^16 + 10*pi^17
> Gcd(f, Derivative(f));
x^3 + (1 + 3*pi)*x^2 + (2*pi + 3*pi^2)*x + pi^2 + pi^3
> f mod $1;
0
> (x + pi)^2*(x + pi + 1);
x^3 + (1 + 3*pi)*x^2 + (2*pi + 3*pi^2)*x + pi^2 + pi^3
> g := (x - 1)*(x + 1)*(x + pi);
> g;
x^3 + pi*x^2 - x - pi
> Gcd(f, g);
x + pi
Roots of polynomials can be found (to some precision) by hensel lifting an approximation or by factorizing the polynomial and looking for linear factors from which the roots can be read off.
Roots of polynomials can be found by first determining their valuation (using the Newton polygon), finding a first approximation over the finite field and then improving this approximation until the Hensel condition (Valuation(g(a)) > 2 * Valuation(g'(a))) is satisfied.
The Newton polygon of a polynomial g = sum_(i=0)^n c_i x^i (over a local ring or field) is the (lower) convex hull of the points (i, Valuation(c_i)). The slopes of the Newton polygon determine the valuations of the roots of g in a splitting ring and the number of roots with that valuation. The faces of the newton polygon can be determined using Faces which returns the faces expressed as the line m * x + n * y = c which coincides with the face. GradientVector will return the m and n values from the line so that the valuation (gradient) can be calculated. EndVertices will return the end points of the face, the x coordinates of which will give the number of roots with valuation equal to the gradient of the face.Newton polygons are discussed in greater detail in Chapter NEWTON POLYGONS and are illustrated below.
Return a sequence containing pairs which are valuations of non infinite precision zero roots of g and the number of roots of g which have that valuation.
> Z3 := pAdicRing(3, 30);
> R<y> := PolynomialRing(Z3);
> roots := [ Z3.1^Random([0..3]) * Random(Z3) : i in [1..10] ];
> [ Valuation(r) : r in roots ];
[ 3, 1, 6, 3, 0, 3, 2, 3, 3, 2 ]
> g := &* [ PolynomialRing(Z3) ! [ -r, 1 ] : r in roots ];
> N := NewtonPolygon(g);
> N;
Newton Polygon of y^10 + 44594997030169*y^9 - 85346683389318*y^8 +
76213593390537*y^7 + 74689026811236*y^6 - 48671968754502*y^5 -
58608670426020*y^4 - 63609139981179*y^3 + 77334553491246*y^2 +
39962036019861*y - 94049035648173 over Z3
> F := Faces(N);
> F;
[ <6, 1, 26>, <3, 1, 23>, <2, 1, 17>, <1, 1, 9>, <0, 1, 0> ]
> [GradientVector(F[i]) : i in [1 .. #F]];
[ <6, 1>, <3, 1>, <2, 1>, <1, 1>, <0, 1> ]
> [$1[i][1]/$1[i][2] : i in [1 ..#$1]];
[ 6, 3, 2, 1, 0 ]
> [EndVertices(F[i]) : i in [1 .. #F]];
[
[ <0, 26>, <1, 20> ],
[ <1, 20>, <6, 5> ],
[ <6, 5>, <8, 1> ],
[ <8, 1>, <9, 0> ],
[ <9, 0>, <10, 0> ]
]
> [$1[i][2][1] - $1[i][1][1] : i in [1 .. #$1]];
[ 1, 5, 2, 1, 1 ]
So there is 1 root of valuation 6, 5 of valuation 3, 2 of valuation
2, 1 of valuation 1 and 1 root with valuation zero. This information
could also have been gained using ValuationsOfRoots.
> ValuationsOfRoots(g); [ <0, 1>, <1, 1>, <2, 2>, <3, 5>, <6, 1> ]Infinite precision zero roots of a polynomial are ignored since their valuation is not a rational.
> Zp := pAdicRing(3); > R<x> := PolynomialRing(Zp); > g := x^3; > ValuationsOfRoots(g); []
Return a root of the polynomial g over a local ring or field by lifting the approximate root r to a root with precision m. This results in an error, if the Hensel condition Valuation(g(r)) > 2 *Valuation(g'(r)) is not satisfied.
> Zx<x> := PolynomialRing(Integers()); > L<b,a> := LocalRing(3, 2, x^2 + 3*x + 3, 20); > R<y> := PolynomialRing(L); > c := (a+b)^42; > r := L ! Sqrt( ResidueClassField(L) ! c ); > r; a > rr := HenselLift( y^2-c, r ); > rr; -13517*a + 21978 + (-20751*a - 417)*b > rr^2 eq c; true > ChangePrecision(rr, 1); a + O(b)For p=2 the situation is a bit more difficult, since the evaluation of the derivative of y^2 - c is not a unit.
> L<b,a> := LocalRing(2, 2, x^2 + 2*x + 2, 20); > R<y> := PolynomialRing(L); > c := (a+b)^42; > r := L ! Sqrt( ResidueClassField(L) ! c ); > r; 1We have to find a better approximation for the square root first.
> HenselLift( y^2-c, r ); >> HenselLift( y^2-c, r ); ^ Runtime error in 'HenselLift': Hensel lift condition is not satisfied
> for d in GF(2,2) do > if Valuation( (r + b*L!d)^2 - c ) gt 4 then > print L!d; > end if; > end for; a+1 > r +:= b * (a+1); > HenselLift( y^2-c, r ); 256*a - 115 + (147*a + 111)*b + O(b^18) > ChangePrecision($1, 1); 1 + O(b) > ChangePrecision($2, 2); 1 + (a + 1)*b + O(b^2)The square root is an element of reduced precision, since the proper root is only guaranteed to coincide with the approximation up to valuation 18.
These functions determine the roots of a polynomial from the factorization of the polynomial.
Return the roots of the polynomial g over a local ring or field as a sequence of tuples of elements in the local ring or field R and multiplicities. If R is not specified it is taken to be the coefficient ring of g.
Try to find a root of the polynomial g over a local ring or field. If a root is found, this function returns {true} and a root as a second value; otherwise it returns false.
> Zx<x> := PolynomialRing(Integers()); > RamExt := []; > for c0 in [2, -2, 6, -6] do > for c1 in [0, 2, -2, 4, -4, 6, -6] do > g := x^2 + c1*x + c0; > new := true; > for L in RamExt do > if HasRoot(PolynomialRing(L)!g) then > new := false; > break L; > end if; > end for; > if new then > print "new field with polynomial", g; > Append( RamExt, LocalRing(2, g, 20)); > end if; > end for; > end for; new field with polynomial x^2 + 2 new field with polynomial x^2 + 2*x + 2 new field with polynomial x^2 + 4*x + 2 new field with polynomial x^2 + 2*x - 2 new field with polynomial x^2 + 4*x - 2 new field with polynomial x^2 + 6These are all such extensions, since the extensions of Q_2 of degree 2 are in bijection to the 7 non-trivial classes of Q_2^ * / (Q_2^ * )^2 and one of these classes yields the unramified extension.
It is possible to factorize (to some precision) most polynomials over a local ring or field. Approximate factorizations can also be lifted to a factorization to greater precision.
Precision: RngIntElt Default:
Given g and h with coefficients that can be coerced into the coefficient ring of f such that f = g * h modulo L.1, g and h are co--prime modulo L.1 and g is monic, find a more accurate factorization g1, h1 such that g1 * h1 = f modulo L.1^(( Precision)) and g1 and g have the same degree. If Precision is not specified the minimum precision of the coefficients of f is used if this is finite, otherwise a precision is calculated which is greater than the highest valuation of any term of a coefficient of f and no smaller than the default precision. If Precision is specified then it must not be greater than the minimum of the precisions of the coefficients of f.
> Z2 := pAdicRing(2, 25);
> R<x> := PolynomialRing(Z2);
> g := &* [ x - i : i in [1..8] ];
> F2 := ResidueClassField(Z2);
> Factorization( PolynomialRing(F2)!g );
[
<$.1, 4>,
<$.1 + 1, 4>
]
> h1 := x^4;
> h2 := (x+1)^4;
> g1, g2 := HenselLift(g, h1, h2);
> g1, g2, g - g1*g2;
x^4 - 20*x^3 + 140*x^2 - 400*x + 384
x^4 - 16*x^3 + 86*x^2 - 176*x + 105
0
true if and only if the polynomial g over a local ring or field is irreducible.
Returns a sequence of tuples of polynomials and multiplicities where the polynomials are not divisible by any square of a polynomial. The product of the polynomials to the corresponding multiplicities is the polynomial g (to some precision). The polynomials must be over a field.
Return the factorization of the polynomial g over a local ring or field into irreducible factors as a sequence of pairs, the first entry giving the irreducible factor and the second its multiplicity.Precision is important since for polynomials over rings of relatively small precision a correct factorization may not be possible and an error will result. A lower bound on the precision needed for the factorization to succeed is given by SuggestedPrecision; this precision may still be insufficient, however.
Lack of precision errors should not occur if the polynomial is over an infinite precision ring and each of the coefficients has infinite precision since the algorithm can pick a precision at which the polynomial will factor. The factorization will be returned to the default precision of the coefficient ring.
The precision the factorization is returned to is reduced for multiple factors.
For a polynomial f over a local ring or field return a precision at which the factorization of f as given by Factorization(f) will be Hensel liftable to the correct factorization.The precision returned is not guaranteed to be enough to gain a factorization of the polynomial. It may be that a correct factorization cannot be found at that precision but may be possible with a little more precision.
> R<b, a> := LocalRing(3, y^3 + y^2 + 2, y^2 + 3*y + 3);
> P<x> := PolynomialRing(R);
> f := x^12 + 100*x^11 + 4050*x^10 + 83700*x^9 + 888975*x^8 + 3645000*x^7 -
> 10570500*x^6 - 107163000*x^5 + 100875375*x^4 + 1131772500*x^3 -
> 329614375*x^2 + 1328602500*x + 332150625;
> SuggestedPrecision(f);
81
> Factorization(f);
[
<(1 + O(b^20))*x - 25515 + O(b^20), 1>,
<(1 + O(b^20))*x + 25515 + O(b^20), 1>,
<(1 + O(b^20))*x^2 - (3902 + O(b^20))*x + 15062 + O(b^20), 1>,
<(1 + O(b^20))*x^8 + (4002 + O(b^20))*x^7 + (15856 + O(b^20))*x^6 + (22316 +
O(b^20))*x^5 + (13130 + O(b^20))*x^4 + (5055 + O(b^20))*x^3 - (7444 +
O(b^20))*x^2 - (7694 + O(b^20))*x - 17936 + O(b^20), 1>
]
> R`DefaultPrecision := 100;
> Factorization(f);
[
<(1 + O(b^100))*x - 24661426543658311412232 + O(b^100), 1>,
<(1 + O(b^100))*x + 59686213397626427351265 + O(b^100), 1>,
<(1 + O(b^100))*x^2 + (147636902010797938340401 + O(b^100))*x +
230137255583614436400743 + O(b^100), 1>,
<(1 + O(b^100))*x^8 - (182661688864766054279334 + O(b^100))*x^7 +
(233480746202725370828770 + O(b^100))*x^6 + (190666220330376795913817 +
O(b^100))*x^5 - (12879501298263994482397 + O(b^100))*x^4 +
(232164244892823391360734 + O(b^100))*x^3 - (141814183147011022730293 +
O(b^100))*x^2 + (254523779712429378140998 + O(b^100))*x +
25414885929387072890359 + O(b^100), 1>
]
In some cases the factorization
can be detected to be exact and not one involving an
infinite expansion in the uniformizing element. The factorization is
returned with infinite precision if this is found to be true.
> f := (x - 1)^2*(x - b)^3;
> Factorization(f);
[
<x - 1, 2>,
<x - b, 3>
]
> f := (x - 1)^2*(x - b)*(x - a^3)^5;
> Factorization(f);
[
<x - 1, 2>,
<x + a^2 + 2, 5>,
<x - b, 1>
]
Differing precisions may appear in the different factors of the polynomial
since a multiple factor can only
be determined to a lesser precision than a single factor.
> f := (x - 1)^3*(x - b*a^3)^7*(x - b^5*a^2)^2;
> Factorization(f);
[
<(1 + O(b^29))*x + (a^2 + 2)*b + O(b^29), 7>,
<(1 + O(b^67))*x - 1 + O(b^67), 3>,
<(1 + O(b^100))*x - 27*a^2 - 9*a^2*b + O(b^100), 2>
]
> L<b, a> := LocalRing(5, 2, y^2 + 5*y + 5, 40);
> R<x> := PolynomialRing(L);
> f := (x - 1)^3*(x - b)^2*(x - b^2 + b - 1);
> SuggestedPrecision(f);
40
> Factorization(f);
[
<x - 1, 3>,
<x - b, 2>,
<x + 4 + 6*b, 1>
]
> f := (x + 2)^3*(x + b)*(x + 3)^4;
> f;
x^8 + (18 + b)*x^7 + (138 + 18*b)*x^6 + (584 + 138*b)*x^5 + (1473 + 584*b)*x^4 +
(2214 + 1473*b)*x^3 + (1836 + 2214*b)*x^2 + (648 + 1836*b)*x + 648*b
> SuggestedPrecision(f);
40
> Precision(L);
40
> R<b, a> := LocalRing(3, 2, y^2 + 3*y + 3);
> P<x> := PolynomialRing(R);
> f := x^12 + 100*x^11 + 4050*x^10 + 83700*x^9 + 888975*x^8 + 3645000*x^7 -
> 10570500*x^6 - 107163000*x^5 + 100875375*x^4 + 1131772500*x^3 -
> 329614375*x^2 + 1328602500*x + 332150625;
> SuggestedPrecision(f);
49
> Factorization(f);
>> Factorization(f);
^
Runtime error in 'Factorization': Correct factorization could not be found with
the given precision. Try with precision at least 49
> R<b, a> := LocalRing(3, 2, y^2 + 3*y + 3, 50);
> P<x> := PolynomialRing(R);
> f := P!f;
> Factorization(f);
>> Factorization(f);
^
Runtime error in 'Factorization': Correct factorization could not be found with
the given precision. Try with precision at least 49
> f;
(1 + O(b^40))*x^12 + (100 + O(b^40))*x^11 + (4050 + O(b^40))*x^10 + (83700 +
O(b^40))*x^9 + (888975 + O(b^40))*x^8 + (3645000 + O(b^40))*x^7 - (10570500
+ O(b^40))*x^6 - (107163000 + O(b^40))*x^5 + (100875375 + O(b^40))*x^4 +
(1131772500 + O(b^40))*x^3 - (329614375 + O(b^40))*x^2 + (1328602500 +
O(b^40))*x + 332150625 + O(b^40)
> f := x^12 + 100*x^11 + 4050*x^10 + 83700*x^9 + 888975*x^8 + 3645000*x^7 -
> 10570500*x^6 - 107163000*x^5 + 100875375*x^4 + 1131772500*x^3 - 329614375*x^2 +
> 1328602500*x + 332150625;
> SuggestedPrecision(f);
50
> Factorization(f);
[
<x - 399882754935, 1>,
<x + 143905694229, 1>,
<x - 71481729371*a + 229090274400, 1>,
<x + 71481729371*a + 135887221072, 1>,
<x^4 + (-8823781555*a - 296976872665)*x^3 + (324366393666*a +
63219964593)*x^2 + (46831894972*a - 193377829126)*x + 283850215170*a +
367831095053, 1>,
<x^4 + (8823781555*a + 187976437999)*x^3 + (-324366393666*a -
38457626466)*x^2 + (-46831894972*a + 60198382752)*x - 283850215170*a +
215394267602, 1>
]
Note that the polynomial itself must have coefficients with precision at
least that given by SuggestedPrecision (and not just the coefficient
ring) for Factorization to succeed. Sometimes this will not be
possible if the coefficients of the polynomial are not known well enough.
> Zx<x> := PolynomialRing(Integers());
> g := x^5 - x + 1;
> Factorization(Discriminant(g));
[ <19, 1>, <151, 1> ]
> g2 := Factorization( PolynomialRing(pAdicRing(2, 10)) ! g );
> g2;
[
<$.1^2 + 367*$.1 - 93, 1>,
<$.1^3 - 367*$.1^2 - 386*$.1 + 11, 1>
]
> g3 := Factorization( PolynomialRing(pAdicRing(3, 10)) ! g );
> g3;
[
<$.1^5 - $.1 + 1, 1>
]
> g7 := Factorization( PolynomialRing(pAdicRing(7, 10)) ! g );
> g7;
[
<$.1^2 + 138071312*$.1 + 2963768, 1>,
<$.1^3 - 138071312*$.1^2 + 132202817*$.1 - 84067650, 1>
]
This shows that the Galois group of g contains elements of orders 2, 3, 5
and 6, and therefore is isomorphic to S_5.