|
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.
f div g : RngUPolElt, RngUPolElt -> RngUPolElt
f mod g : RngUPolElt, RngUPolElt -> RngUPolElt
LeastCommonMultiple(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
Coefficient(f, i) : RngUPolElt, RngIntElt -> RngElt
LeadingCoefficient(f) : RngUPolElt -> RngElt
Derivative(f) : RngUPolElt -> RngUPolElt
Evaluate(f, x) : RngUPolElt, RngElt -> RngElt
Gcd(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
GCD(f, g) : RngUPolElt, RngUPolElt -> RngUPolElt
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.
This example illustrates the usage and results of the GCD functions. Note
the precision loss in the answer.
> 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.
For a polynomial of the form g := ∏(x - r i) we demonstrate that
the Newton polygon determines the valuations of the roots of g.
> 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> ]
HenselLift(f, x) : RngUPolElt, RngPadResElt -> RngPadResElt
HenselLift(f, x) : RngUPolElt, RngPadResExtElt -> RngPadResExtElt
HenselLift(f, x) : RngUPolElt, FldPadElt -> FldPadElt
HenselLift(f, x, k) : RngUPolElt, RngPadElt, RngIntElt -> RngPadElt
HenselLift(f, x, k) : RngUPolElt, RngPadResElt, RngIntElt -> RngPadResElt
HenselLift(f, x, k) : RngUPolElt, RngPadResExtElt, RngIntElt -> RngPadResExtElt
HenselLift(f, x, k) : RngUPolElt, FldPadElt, RngIntElt -> FldPadElt
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.
This examples illustrates how Hensel lifting is used to compute square roots.
> 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 y 2 -
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.
Roots(f, R) : RngUPolElt, RngPad -> [ <RngPadElt, RngIntElt> ]
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.
We generate the ramified extensions of Z 2 of degree 2 by looping over
some Eisenstein polynomials with small coefficients and checking whether a new
polynomial has a root in one of the already known rings.
> 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 + 6
These 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) 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.
If the reduction of a polynomial over the residue class field is not a power
of an irreducible polynomial, the factorization into powers of different
irreducibles can be lifted to a factorization over the local ring.
> 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.
LocalFactorization(f) : RngUPolElt -> [ < RngUPolElt, RngIntElt >]
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.
The use of SuggestedPrecision along with Factorization is
illustrated below for a few different cases.
> 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.
In this example we demonstrate how factorizations of a rational polynomial
over some local rings can give information on the Galois group.
> 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.
SplittingField(f) : RngUPolElt[RngPad] -> FldPad, SeqEnum
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.
|