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 LCM 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. For example, for polynomials which are coprime 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.
Determine the greatest common divisor of polynomials f and g where f and g are over a free precision 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. The GCD is computed by echelonizing the Sylvester matrix of f and g.
> L := pAdicRing(5, 20);
> R<x> := PolynomialRing(L);
> elts := [Random(L) : i in [1..3]];
> f := (x - elts[1])^3 * (x - elts[2])^2 * (x - elts[3]);
> f;
x^6 + 31722977012336*x^5 - 34568128687249*x^4 +
4655751767246*x^3 + 11683626356181*x^2 -
29833674388290*x + 32360011367900
> GCD(f, Derivative(f));
(1 + O(5^18))*x^3 - (934087632277 + O(5^18))*x^2 -
(89130566204 + O(5^18))*x + 1178670674955 + O(5^18)
> f mod $1;
O(5^18)*x^5 + O(5^18)*x^4 + O(5^18)*x^3 + O(5^18)*x^2 +
O(5^18)*x + O(5^19)
> (x - elts[1])^2 * (x - elts[2]);
x^3 + 14324701430223*x^2 + 26613750293171*x +
31696248799955
> ChangePrecision($1, 18);
(1 + O(5^18))*x^3 - (934087632277 + O(5^18))*x^2 -
(89130566204 + O(5^18))*x + 1178670674955 + O(5^18)
Shifts the valuation of each coefficient of f by n, ie. scales the polynomial by πn.
Roots of a polynomial f defined over a local ring or field can be found by first determining their valuation (using the Newton polygon), finding a first approximation over the finite field and finally improving this approximation until the Hensel condition v(f(a)) > 2v(f'(a)) is satisfied.
The Newton polygon of a polynomial f = ∑i=0n ci xi (over a local ring or field) is the lower convex hull of the points (i, v(ci)). The slopes of the Newton polygon determine the valuations of the roots of f in a splitting ring and the number of roots with that valuation. The faces of the Newton polygon can be determined using the function Faces which returns the faces expressed as the line mx + ny = c which coincides with the face. The function GradientVector will return the m and n values from the line so that the valuation (gradient) can be calculated. The function 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 roots of f and the number of roots of f which have that valuation.
> Z3 := pAdicRing(3, 30);
> R<y> := PolynomialRing(Z3);
> pi := UniformizingElement(Z3);
> roots := [ pi^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 := &* [ y - r : 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 pAdicRing(3, 30)
> 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 one root of valuation 6, five of valuation 3, two of valuation
2, one of valuation 1 and one root with valuation zero. This information
could also have been gained using ValuationsOfRoots.
> ValuationsOfRoots(g); [ <6, 1>, <3, 5>, <2, 2>, <1, 1>, <0, 1> ]
Return a root of the polynomial f over a local ring or field by lifting the approximate root x to a root with precision k (or the default precision of the structure if not specified). This results in an error, if the Hensel condition v(f(x)) > 2v(f'(x)) is not satisfied.
> Zx<x> := PolynomialRing(Integers()); > L1<a> := ext<pAdicRing(3, 20) | 2>; > L2<b> := ext<L1 | x^2 + 3*x + 3>; > R<y> := PolynomialRing(L2); > c := (a+b)^42; > r := L2 ! Sqrt(ResidueClassField(L2) ! c); > r; a > rr := HenselLift(y^2-c, r); > rr; (-1513703643*a - 1674232545)*b - 1219509587*a + 760894776 > Valuation(rr^2 - c); 40 > ChangePrecision(rr, 1); a + O(b)For p=2 the situation is a bit more difficult, since the derivative of y2 - c is not a unit at this point.
> Zx<x> := PolynomialRing(Integers());
> L1<a> := ext<pAdicRing(2, 20) | 2>;
> L2<b> := ext<L1 | x^2 + 2*x + 2>;
> R<y> := PolynomialRing(L2);
> c := (a+b)^42;
> r := L2 ! Sqrt(ResidueClassField(L2) ! c);
> r;
1
> HenselLift(y^2-c, r);
>> HenselLift(y^2-c, r);
^
Runtime error in 'HenselLift': Hensel lift condition is not satisfied
We have to find a better approximation for the square root first.
> for d in GF(2,2) do > if Valuation((r + b*L2!d)^2 - c) gt 4 then > print L2!d; > end if; > end for; a + 1 > r +:= b * (a+1); > HenselLift( y^2-c, r ); (-199021*a + 100463)*b + 204032*a - 31859 + O(b^38) > ChangePrecision($1, 1); 1 + O(b) > ChangePrecision($2, 2); (a + 1)*b + 1 + 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.
IsSquarefree: BoolElt Default: false
Return the roots of the polynomial f over a local ring or field R as a sequence of tuples of elements in R and multiplicities. If R is not specified it is taken to be the coefficient ring of f. If the polynomial is known to be squarefree, the root-finding algorithm may run considerably faster.
Try to find a root of the polynomial f 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, ext<pAdicRing(2, 20) | g>); > 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 Q2 of degree 2 are in bijection to the 7 non-trivial classes of Q2 * / (Q2 * )2 and one of these classes yields the unramified extension.
It is possible to factorize (to some precision) polynomials over a local ring or field. Approximate factorizations can also be lifted to a factorization to greater precision.
Given a sequence s of polynomials with coefficients that can be coerced into the coefficient ring of f such that f ≡ ∏i=1#s s[i] modulo π, s[i] and [j] are co--prime modulo π for all i and j, and s[i] is monic for all i, find a more accurate factorization t[1], t[2], ... t[#s] such that f ≡ ∏i=1#s t[i] modulo πk, where k is the minimum precision of the coefficients of f.
> Z2 := pAdicRing(2, 25);
> R<x> := PolynomialRing(Z2);
> f := &* [ x - i : i in [1..8] ];
> F2 := ResidueClassField(Z2);
> Factorization( PolynomialRing(F2)!f );
[
<$.1, 4>,
<$.1 + 1, 4>
]
> h1 := x^4;
> h2 := (x+1)^4;
> h := HenselLift(f, [h1, h2]);
> h[1], h[2], f - h[1]*h[2];
x^4 - 20*x^3 + 140*x^2 - 400*x + 384
x^4 - 16*x^3 + 86*x^2 - 176*x + 105
0
Given a polynomial f with coefficients lying in a local ring or field L, return true if and only if f is irreducible over L. Currently, this only works over p-adic rings, unramified extensions of p-adic rings, totally ramified extensions of p-adic rings, and totally ramified extension of unramified extensions of p-adic rings.
Return 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 f (to some precision). Currently, this only works over p-adic rings, unramified extensions of p-adic rings, totally ramified extensions of p-adic rings, and totally ramified extension of unramified extensions of p-adic rings.
Certificates: BoolElt Default: false
IsSquarefree: BoolElt Default: false
Ideals: BoolElt Default: false
Extensions: BoolElt Default: false
Return the factorization of the polynomial f 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.
The precision the factorization is returned to is reduced for multiple factors.
The optional parameter IsSquarefree can be set to true, if the polynomial is known to be square-free. The Certificates parameter can be set to true to compute certificates for the irreducibility of the individual factors returned. This information can be used to compute the p-maximal order of the equation order defined by the factor. If the Extensions parameter is set to true then certificates will be returned which will include an extension given by each factor.
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 obtain 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.
Currently, this only works over p-adic rings, unramified extensions of p-adic rings, totally ramified extensions of p-adic rings, and totally ramified extension of unramified extensions of p-adic rings.
Given two irreducible polynomials over the same p-adic field, test if the extensions defined by them are isomorphic.
Given two Eisenstein polynomials of the same degree and discriminant compute their distance, i.e. the minimal weighted valuation of the difference of the coefficients.
> L<b> := ext<ext<pAdicRing(5, 20) | 2> | y^2 + 5*y + 5>;
> R<x> := PolynomialRing(L);
> f := (x - 1)^3*(x - b)^2*(x - b^2 + b - 1);
> SuggestedPrecision(f);
80
> Factorization(f);
[
<x - b + O(b^40), 2>,
<x - 1 + O(b^40), 3>,
<x + 6*b + 4 + O(b^40), 1>
]
1 + O(b^40)
> f := (x + 2)^3*(x + b)*(x + 3)^4;
> f;
x^8 + (b + 18 + O(b^40))*x^7 + (18*b + 138 + O(b^40))*x^6 + (138*b + 584 +
O(b^40))*x^5 + (584*b + 1473 + O(b^40))*x^4 + (1473*b + 2214 + O(b^40))*x^3
+ (2214*b + 1836 + O(b^40))*x^2 + (1836*b + 648 + O(b^40))*x + 648*b +
O(b^40)
> SuggestedPrecision(f);
80
> Precision(L);
80
> P<y> := PolynomialRing(Integers());
> R<b> := ext<ext<pAdicRing(3, 20) | 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);
48
> Factorization(f);
[
<x + 153560934 + O(b^40), 1>,
<x - 1595360367 + O(b^40), 1>,
<x + 1273329451*$.1 - 1037496066 + O(b^40), 1>,
<x + -1273329451*$.1 - 97370567 + O(b^40), 1>,
<x^4 + (-1598252738*$.1 - 309919655 + O(b^40))*x^3 + (-280421715*$.1 -
102998055 + O(b^40))*x^2 + (1263867503*$.1 + 923047935 + O(b^40))*x +
-1252549104*$.1 - 786365260 + O(b^40), 1>,
<x^4 + (1598252738*$.1 - 600198580 + O(b^40))*x^3 + (280421715*$.1 +
457845375 + O(b^40))*x^2 + (-1263867503*$.1 - 1604687071 + O(b^40))*x +
1252549104*$.1 + 1718732948 + O(b^40), 1>
]
1 + O(b^40)
> R<b> := ext<ext<pAdicRing(3, 25) | 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;
> Factorization(f);
[
<x + 143905694229 + O(b^50), 1>,
<x - 399882754935 + O(b^50), 1>,
<x + 46601526664*$.1 + 229090274400 + O(b^50), 1>,
<x + -46601526664*$.1 + 135887221072 + O(b^50), 1>,
<x^4 + (242476655332*$.1 + 187976437999 + O(b^50))*x^3 + (372805509192*$.1 -
38457626466 + O(b^50))*x^2 + (126788105939*$.1 + 60198382752 +
O(b^50))*x + 347425890996*$.1 + 215394267602 + O(b^50), 1>,
<x^4 + (-242476655332*$.1 - 296976872665 + O(b^50))*x^3 + (-372805509192*$.1
+ 63219964593 + O(b^50))*x^2 + (-126788105939*$.1 - 193377829126 +
O(b^50))*x + -347425890996*$.1 + 367831095053 + O(b^50), 1>
]
1 + O(b^50)
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 to sufficient
precision.
> 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 S5.
Std: BoolElt Default: true
Splitting field F of a squarefree polynomial f over a p-adic ring or field K, and the roots of f in F. The optional parameter Std (true by default) specifies whether F/K should be converted to a standard form --- at most one ramified extension over one unramified extension of K.
> K:=pAdicField(3,20); > R<x>:=PolynomialRing(K); > F:=SplittingField(x^9-3); > Degree(F,K), RamificationDegree(F,K), InertiaDegree(F,K); 54 54 1