Various simple operations for polynomials as well as root finding and factorization functions have been implemented for polynomials over p-adic rings and fields.
A number of functions for polynomials in general are applicable for polynomials over p-adic 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 p-adic 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 p-adic ring is not a principal ideal domain, it is useful to have a GCD function available without explicitly using p-adic fields. For example, for polynomials which are co--prime over the p-adic field, the ideal generated by the two polynomials contains some power of the uniformizing element of the p-adic 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 p-adic 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.
> Zp<p> := pAdicRing(17);
> R<x> := PolynomialRing(Zp);
> f := (x + p)^3*(x + p + 1)^2*(x + p^7 + p^19);
> f;
x^6 + 239072435685151735185913*x^5 + 20799301904608200961169889*x^4 +
723672262818954302407547951*x^3 + 12586924666387553705799010850*x^2 +
109441623318206020726428274788*x + 380558371992852753889620056712
> Gcd(f, Derivative(f));
x^3 + 52*x^2 + 901*x + 5202
> f mod $1;
0
> Derivative(f) mod $2;
0
> (x + p)^2*(x + p + 1);
x^3 + 52*x^2 + 901*x + 5202
> g := (x - 1)*(x + 1)*(x + p);
> Gcd(f, g);
x + 17
> Lcm(f, g);
x^8 + 239072435685151735185913*x^7 + 20799301904608200961169888*x^6 +
723433190383269150672362038*x^5 + 12566125364482945504837840961*x^4 +
108717951055387066424020726837*x^3 + 367971447326465200183821045862*x^2 -
109441623318206020726428274788*x - 380558371992852753889620056712
> Lcm(f, Derivative(f));
6*x^8 + 2629796792536669087044731*x^7 +
285778147522155064100949730808721445480453585317*x^6 +
29892394230817419704942555897479988775503187324145*x^5 +
1302633952035487213183973762285116776856338822973369*x^4 +
30270821653766257440816322704820045432905006426459072*x^3 +
395630810184635435292896801026566992314699344887898536*x^2 +
2757378924341332893474304523994804539305310534038311408*x +
8006329488318245865373526863526875165138650637850995728
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 p-adic 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 p-adic 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.
> Zp := pAdicRing(5); > R<x> := PolynomialRing(Zp); > Zp!11; 1 + 2*p > HenselLift(x^2 - 11, Zp!1); 1 + p + 2*p^2 + 2*p^5 + 3*p^7 + 3*p^8 + 2*p^9 + p^11 + 4*p^12 + 3*p^13 + 2*p^14 + 3*p^15 + 3*p^16 + 4*p^17 + 2*p^20 + 4*p^21 + 4*p^22 + 2*p^23 + 2*p^24 + p^25 + p^27 + 3*p^28 + 2*p^29 > Zp!111; 1 + 2*p + 4*p^2We would have to find a better approximation for the root first in order to Hensel Lift an approximate root. But in this case it can be found by other means that Zp!111 does not have a 5th root. But this does not prevent Zp!111 from having square roots.
> HenselLift(x^5 - 111, Zp!1); >> HenselLift(x^5 - 111, Zp!1); Runtime error in 'HenselLift': Hensel lift condition is not satisfied > Valuation(Evaluate(x^5 - 111, Zp!1)); 1 > 2*Valuation(Evaluate(Derivative(x^5 - 111), Zp!1)); 2
> HenselLift(x^2 - 111, Zp!1); 1 + p + 4*p^2 + 3*p^3 + 3*p^5 + 4*p^6 + p^7 + 3*p^9 + 2*p^10 + 3*p^11 + 3*p^13 + 2*p^14 + 2*p^15 + 3*p^16 + 4*p^17 + 4*p^19 + p^20 + 4*p^21 + 4*p^22 + p^23 + 2*p^24 + 3*p^25 + 2*p^27 + 4*p^28 > HenselLift(x^2 - 111, Zp!4); 4 + 3*p + p^3 + 4*p^4 + p^5 + 3*p^7 + 4*p^8 + p^9 + 2*p^10 + p^11 + 4*p^12 + p^13 + 2*p^14 + 2*p^15 + p^16 + 4*p^18 + 3*p^20 + 3*p^23 + 2*p^24 + p^25 + 4*p^26 + 2*p^27 + 4*p^29
These functions determine the roots of a polynomial from the factorization of the polynomial.
Return the roots of the polynomial g over a p-adic ring or field as a sequence of tuples of elements in the p-adic 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 p-adic ring or field. If a root is found, this function returns {true} and a root as a second value; otherwise it returns false.
> HasRoot(x^5 - 111); false > IsPower(Zp!111, 5); falseIt can be verified as follows that Zp!111 is a square in Zp.
> Roots(x^2 - 111);
[
<1 + p + 4*p^2 + 3*p^3 + 3*p^5 + 4*p^6 + p^7 + 3*p^9 + 2*p^10 + 3*p^11 +
3*p^13 + 2*p^14 + 2*p^15 + 3*p^16 + 4*p^17 + 4*p^19 + p^20 + 4*p^21 + 4*p^22
+ p^23 + 2*p^24 + 3*p^25 + 2*p^27 + 4*p^28, 1>,
<4 + 3*p + p^3 + 4*p^4 + p^5 + 3*p^7 + 4*p^8 + p^9 + 2*p^10 + p^11 + 4*p^12
+ p^13 + 2*p^14 + 2*p^15 + p^16 + 4*p^18 + 3*p^20 + 3*p^23 + 2*p^24 + p^25 +
4*p^26 + 2*p^27 + 4*p^29, 1>
]
> Roots(x^2 - 111, ChangePrecision(Zp, 10));
[
<4 + 3*5 + 5^3 + 4*5^4 + 5^5 + 3*5^7 + 4*5^8 + 5^9, 1>,
<1 + 5 + 4*5^2 + 3*5^3 + 3*5^5 + 4*5^6 + 5^7 + 3*5^9, 1>
]
> IsSquare(Zp!111);
true 1 + p + 4*p^2 + 3*p^3 + 3*p^5 + 4*p^6 + p^7 + 3*p^9 + 2*p^10 + 3*p^11 +
3*p^13 + 2*p^14 + 2*p^15 + 3*p^16 + 4*p^17 + 4*p^19 + p^20 + 4*p^21 + 4*p^22 +
p^23 + 2*p^24 + 3*p^25 + 2*p^27 + 4*p^28
It is possible to factorize (to some precision) most polynomials over a p-adic ring or field. Approximate factorizations can also be lifted to a factorization to greater precision.
Precision: RngIntElt Default:
Given g and h over a p-adic ring or field P or the residue class field of the coefficient ring of f where f = g * h modulo P.1, g and h are co--prime modulo P.1 and g is monic, find a more accurate factorization g1, h1 such that g1 * h1 = f modulo P.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 p-adic 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 p-adic 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 p-adic 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 := pAdicRing(19); > W<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;However, if the polynomial does not have all coefficients with infinite precision it is possible that there will not be enough precision in the polynomial to get an accurate enough factorization.
> SuggestedPrecision(f); >> SuggestedPrecision(f); ^ Runtime error in 'SuggestedPrecision': No suggestion needed for infinite precision polynomials > time Factorization(f); [ <(1 + O(19^20))*x - 14446834425304955424443391 + O(19^20), 1>, <(1 + O(19^20))*x^2 - (5609388171337087358652919 + O(19^20))*x - 14081587203751416188789491 + O(19^20), 1>, <(1 + O(19^20))*x^3 + (2832342316180202454542878 + O(19^20))*x^2 - (4005709785439322304277046 + O(19^20))*x - 14104991364984436311946897 + O(19^20), 1>, <(1 + O(19^20))*x^6 + (17223880280461840328553532 + O(19^20))*x^5 + (10668266671860251918917332 + O(19^20))*x^4 - (4059507677066572199871037 + O(19^20))*x^3 - (3534094707911540334290219 + O(19^20))*x^2 + (1517004691647344359494161 + O(19^20))*x - 1971012072558959799129857 + O(19^20), 1> ] Time: 2.030 > R`DefaultPrecision := 50; > time Factorization(f); [ <(1 + O(19^50))*x - 2826747782432136347308755771960076349733312226714457025807518294 + O(19^50), 1>, <(1 + O(19^50))*x^2 + (2485182579514598181381503536971821683300131452327688841093125038 + O(19^50))*x - 1887591438340589332549813953027466132427657690157445421534748920 + O(19^50), 1>, <(1 + O(19^50))*x^3 + (4041092233797197847074783324006535862431383078369825103126333549 + O(19^50))*x^2 - (506894955814872380209673626307169197389570477092856046824884933 + O(19^50))*x + 3616420531785147546868821254228179180804169201434702779512442289 + O(19^50), 1>, <(1 + O(19^50))*x^6 - (3699527030879659681147531089018281195998202303983056918411940193 + O(19^50))*x^5 + (756411338357447122928367507445544337947698991739581426965523579 + O(19^50))*x^4 + (326095699717535743746818013168874923408520706048765501998412417 + O(19^50))*x^3 - (151559375838314214369134197504427139557668674974347221534016972 + O(19^50))*x^2 + (3962531588516235951511681988204893021105733431180488296718644767 + O(19^50))*x + 3871892307218031422806496505390244920408163654366263008731758552 + O(19^50), 1> ] Time: 3.580
> f +:= O(R.1^10); > SuggestedPrecision(f); 10 > f +:= O(R.1^8)*x^3; > SuggestedPrecision(f); 8 > f +:= O(R.1^5)*x^7; > SuggestedPrecision(f); 5In 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 - R.1)^3;
> time Factorization(f);
[
<x - 19, 3>,
<x - 1, 2>
]
Time: 0.000
> f := (x - 1)^2*(x - R.1)*(x - 15)^5;
> Factorization(f);
[
<x - 19, 1>,
<x - 15, 5>,
<x - 1, 2>
]
Time: 0.000
> R<p> := pAdicRing(5, 50);
> W<x> := PolynomialRing(R);
> f := (x - 1)^3*(x - p)^2*(x - p^2 + p - 1);
> SuggestedPrecision(f);
50
> Factorization(f);
[
<x - 21, 1>,
<x - 5, 2>,
<x - 1, 3>
]
> f := (x + 2)^3*(x + p)*(x + 3)^4;
> f;
x^8 + 23*x^7 + 228*x^6 + 1274*x^5 + 4393*x^4 + 9579*x^3 + 12906*x^2 + 9828*x +
3240
> SuggestedPrecision(f);
50
> Precision(R);
50
> R<p> := pAdicRing(3, 20);
> W<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);
25
> Factorization(f);
>> Factorization(f);
^
Runtime error in 'Factorization': Correct factorization could not be found with
the given precision. Try with precision at least 25
> R<p> := pAdicRing(3, 25);
> W<x> := PolynomialRing(R);
> f := W!f;
> Factorization(f);
>> Factorization(f);
^
Runtime error in 'Factorization': Correct factorization could not be found with
the given precision. Try with precision at least 25
> f;
(1 + O(p^20))*x^12 + (100 + O(p^20))*x^11 + (4050 + O(p^20))*x^10 + (83700 +
O(p^20))*x^9 + (888975 + O(p^20))*x^8 + (3645000 + O(p^20))*x^7 - (10570500
+ O(p^20))*x^6 - (107163000 + O(p^20))*x^5 + (100875375 + O(p^20))*x^4 +
(1131772500 + O(p^20))*x^3 - (329614375 + O(p^20))*x^2 + (1328602500 +
O(p^20))*x + 332150625 + O(p^20)
> 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 - 399882754935, 1>,
<x + 143905694229, 1>,
<x^2 + 364977495472*x + 54943219994, 1>,
<x^8 - 109000434666*x^7 + 312072209386*x^6 + 387377169350*x^5 -
127623535354*x^4 + 155014613169*x^3 + 67266015200*x^2 - 288402527672*x +
365083238197, 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.
> 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.
[Next][Prev] [_____] [Left] [Up] [Index] [Root]