Univariate polynomials

Contents

• Creation of rings
• Ring basics
• Creation of polynomials
  • From coefficients
  • Coercion
• Polynomial basics
  • Degree
  • Coefficients
  • Valuation
  • Arithmetic
  • Derivative
  • Evaluate
  • Special forms
• Discriminant and Resultant
• Newton polygon
• Hensel lifting
• Approximation
• Root-finding and factorization

Creation of rings

PolynomialRing (F :: FldPadExact)

-> RngUPol_FldPadExact

The univariate polynomial ring over F.

Ring basics

BaseRing (R :: RngUPol_FldPadExact)

-> FldPadExact

The base ring of R.

AssignNames (~R :: RngUPol_FldPadExact, names :: [MonStgElt])

Assigns the name of the variable of R.

Names (R :: RngUPol_FldPadExact)

-> []

The names of R.

Name (R :: RngUPol_FldPadExact, i :: RngIntElt)

'.' (R :: RngUPol_FldPadExact, i :: RngIntElt)

-> RngUPolElt_FldPadExact

Gets the ith generator of R.

Generator (R :: RngUPol_FldPadExact)

-> RngUPolElt_FldPadExact

The generator of R.

'eq' (R :: RngUPol_FldPadExact, S :: RngUPol_FldPadExact)

-> BoolElt

Equality.

ExistsCoveringStructure (R :: RngUPol_FldPadExact, S :: RngUPol_FldPadExact)

ExistsCoveringStructure (R :: RngUPol_FldPadExact, S :: RngUPol)

ExistsCoveringStructure (S :: RngUPol, R :: RngUPol_FldPadExact)

ExistsCoveringStructure (R :: RngUPol_FldPadExact, S :: Str)

ExistsCoveringStructure (S :: Str, R :: RngUPol_FldPadExact)

ExistsCoveringStructure (R :: RngUPol, S :: FldPadExact)

ExistsCoveringStructure (S :: FldPadExact, R :: RngUPol)

-> BoolElt, Any

True if there is a polynomial ring containing both R and S.

Creation of polynomials

From coefficients

Polynomial (coeffs :: [FldPadExactElt])

-> RngUPolElt_FldPadExact

The polynomial with the given coefficients.

Polynomial (K :: FldPadExact, coeffs :: [])

-> RngUPolElt_FldPadExact

The polynomial over K with the given coefficients.

Coercion

IsCoercible (R :: RngUPol_FldPadExact, X)

-> BoolElt, Any

True if X is coercible to an element of R. If so, also returns the coerced element. Otherwise, also returns a string explaining why not.

Succeeds if either:

• X is an element of R
• X is coercible to the base ring of R
• X is a RngUPol or RngUPol_FldPadExact whose coefficients are coercible to the base ring of R
• X is a RngUPol[FldPad] coercible to the approximation ring of R
• X is a sequence of coefficients coercible to the base ring of R

CanChangeRing (f :: RngUPolElt_FldPadExact, K :: FldPadExact)

CanChangeRing (f :: RngUPolElt, K :: FldPadExact)

-> BoolElt, RngUPolElt_FldPadExact

True if f can be coerced to a polynomial over K. If so, also returns the coerced polynomial.

ChangeRing (f, K)

-> Any

Change the ring of f to K.

Polynomial basics

BaseRing (f :: RngUPolElt_FldPadExact)

-> FldPadExact

The base ring of f.

Degree

Degree (f :: RngUPolElt_FldPadExact)

-> BoolElt

The degree of f.

Parameters

• Strategy

WeakDegree (f :: RngUPolElt_FldPadExact)

-> RngIntElt

The weak degree of f, the degree of its approximation.

Coefficients

Coefficients (f :: RngUPolElt_FldPadExact)

-> BoolElt

The coefficients of f.

Parameters

• Strategy

WeakCoefficients (f :: RngUPolElt_FldPadExact)

-> []

The coefficients of f, possibly including some leading zeros.

LeadingCoefficient (f :: RngUPolElt_FldPadExact)

-> BoolElt

The leading coefficient of f.

Parameters

• Strategy

WeakLeadingCoefficient (f :: RngUPolElt_FldPadExact)

-> BoolElt

The leading weak coefficient of f.

Coefficient (f :: RngUPolElt_FldPadExact, i :: RngIntElt)

-> []

The ith coefficient of f.

Valuation

IsIntegral (f :: RngUPolElt_FldPadExact)

-> RngUPolElt

True if each coefficient of f is integral.

MinValuation (f :: RngUPolElt_FldPadExact)

-> RngIntElt

The smallest valuation of the coefficients of f.

Parameters

• Strategy

ValuationEq (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is n.

ValuationNe (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is not n.

ValuationLe (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is at most n.

ValuationLt (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is less than n.

ValuationGe (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is at least n.

ValuationGt (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> BoolElt

True if the valuation of f is greater than n.

Arithmetic

'-' (f :: RngUPolElt_FldPadExact)

'+' (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

'-' (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

'&+' (fs :: [RngUPolElt_FldPadExact])

'*' (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

'&*' (fs :: [RngUPolElt_FldPadExact])

'^' (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> RngUPolElt_FldPadExact

Negate, add, subtract, sum, multiply, product, power.

'div' (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

Exact division.

Parameters

• Strategy: Used to check that g is nonzero.

'/' (f :: RngUPolElt_FldPadExact, x :: FldPadExactElt)

-> RngUPolElt_FldPadExact

Scalar division.

Parameters

• Strategy: Used to check that x is nonzero.

ShiftValuation (f :: RngUPolElt_FldPadExact, ns)

-> RngUPolElt_FldPadExact

Shifts the valuation of the ith coefficient of f by ns(i).

ShiftSlope (f :: RngUPolElt_FldPadExact, n)

-> RngUPolElt_FldPadExact

Shifts the valuation of the ith coefficient of f by i*n.

Parameters

• Pivot: Shifts the valuation a further -n*Pivot so that the Pivotth coefficient is unchanged.
• Offset: Shifts the valuation a further Offset.

ShiftArgument (f :: RngUPolElt_FldPadExact, x :: FldPadExactElt)

-> RngUPol_FldPadExact

f(x+X) as a polnomial in X

Slice (f :: RngUPolElt_FldPadExact, idxs :: [RngIntElt])

-> RngUPolElt_FldPadExact

The polynomial with the given coefficients of f.

Reverse (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

The polynomial with the reversed coefficients of f: f(1/x)*x^deg(f).

Parameters

• Strategy

WeakReverse (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

The polynomial with the reversed weak coefficient of f: f(1/x)*x^weakdeg(f).

Decimate (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> RngUPolElt_FldPadExact

The polynomial of the ith coefficients of f where i=Phase mod n.

Parameters

• Phase

Derivative

Derivative (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

The first derivative of f.

Derivative (f :: RngUPolElt_FldPadExact, n :: RngIntElt)

-> RngUPolElt_FldPadExact

The nth derivative of f.

Evaluate

Evaluate (f :: RngUPolElt_FldPadExact, x :: FldPadExactElt)

Evaluate (f :: RngUPolElt_FldPadExact, x)

Evaluate (f :: RngUPolElt, x :: FldPadExactElt)

-> FldPadExactElt

Evaluates f at x.

Evaluate (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

Evaluates f at g.

Special forms

IsInertial (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is inertial (i.e. it is irreducible as a polynomial over the residue class field).

Parameters

• Strategy

IsEisenstein (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is Eisenstein.

Discriminant and Resultant

Discriminant (f :: RngUPolElt_FldPadExact)

-> FldPadExactElt

The discriminant of f.

Parameters

• Strategy

Resultant (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> FldPadExactElt

The resultant of f and g.

Parameters

• Strategy
• fStrategy
• gStrategy

WeakResultant (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> FldPadExactElt

The weak resultant of f and g.

Resultant (fs :: [RngUPolElt_FldPadExact])

-> FldPadExactElt

The generalized resultant of fs.

Parameters

• Strategy
• Strategies

WeakResultant (fs :: [RngUPolElt_FldPadExact])

-> FldPadExactElt

The weak resultant of fs, i.e. the resultant assuming the weak degree of each f in fs is correct.

Newton polygon

NewtonPolygon (f :: RngUPolElt_FldPadExact)

-> NwtnPgon

The Newton polygon of f.

Parameters

• Strategy
• Support := <0,WeakDegree(f)>: When given, must be a tuple <a,b> of two integers representing an interval; the support of the returned Newton polygon contains this. By default, returns the whole Newton polygon. If you are ok with f having one root very close to 0, then Support:=<1,WeakDegree(f)> may be appropriate.

WeakPartialNewtonPolygon (f :: RngUPolElt_FldPadExact)

-> NwtnPgon

A fragment of the Newton polygon of f, based on its non weakly zero coefficients.

Hensel lifting

IsHenselLiftable (f :: RngUPolElt_FldPadExact, x :: FldPadExactElt)

IsHenselLiftable (f :: RngUPolElt_FldPadExact, x)

IsHenselLiftable (f :: RngUPolElt, x :: FldPadExactElt)

-> BoolElt, FldPadExactElt

True if x is Hensel-liftable to a root of f. If so, also returns the root.

This uses a generalized statement of Hensel’s lemma which does not require the inputs to be integral, namely:

Hensel’s lemma. If $f(x) \in K[x]$ and $x \in K$ such that $x$ is closer to one root of $f$ than any other, then iterating $x \mapsto x - f(x)/f’(x)$ converges to that root.

Parameters

• Strategy

HenselLift (f :: RngUPolElt_FldPadExact, x)

HenselLift (f :: RngUPolElt, x)

-> FldPadExactElt

The root of f uniquely closest to x (see IsHenselLiftable).

Parameters

• Strategy

IsHenselLiftable (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> BoolElt, RngUPolElt_FldPadExact, RngUPolElt_FldPadExact

True if g is Hensel-liftable to a factor of f. If so, also returns the factor (with the same leading coefficient as g) and its cofactor.

Future. Optionally choose Slope, fShift and gShift automagically.

Parameters

• Strategy
• Slope := 0: A rational number, deslope the polynomials by this amount before applying Hensel’s lemma; usually Slope will be a slope of the Newton polygon of g.
• fShift := 0: A rational number, subtract this from the valuation of f after applying Slope.
• gShift := 0: A rational number, subtract this from the valuation of g after applying Slope.

Approximation

SetBaselineValuation (f :: RngUPolElt_FldPadExact, n)

Sets the baseline valuation of f to n.

IncreaseBaselinePrecision (f :: RngUPolElt_FldPadExact, n)

Increases the baseline precision of f to n.

WeakApproximation (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

An element weakly equal to x.

WeakMinValuation (f :: RngUPolElt_FldPadExact)

-> Val_FldPadElt

The minimum valuation of the coefficients of the approximation of f.

IncreaseAbsolutePrecision_Lazy (R :: RngUPol_FldPadExact, pr :: RngIntElt)

-> ExactpAdics_Gettr

Increases the precision of the approximation to R to at least pr.

Approximation_Lazy (R :: RngUPol_FldPadExact, pr :: RngIntElt)

-> ExactpAdics_Gettr

An approximation to R whose base field has default precision pr.

IsDefinitelyZero (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is precisely zero.

UpdateZero (f :: RngUPolElt_FldPadExact, aprs :: [RngIntElt])

Updates f to sum_i(O(pi^aprs[i+1])*x^i).

IsWeaklyZero (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is weakly zero.

Parameters

• Strategy

IsWeaklyEqual (f :: RngUPolElt_FldPadExact, g :: RngUPolElt_FldPadExact)

-> BoolElt

True if f and g are weakly equal.

Root-finding and factorization

Factorization (f :: RngUPolElt_FldPadExact)

-> [], FldPadElt, []

The factorization of f as a sequence of <factor, multiplicity> pairs.

It is only possible to factorize squarefree polynomials, so multiplicity is always 1. The factors are monic; also returns the leading coefficient of f.

Parameters

• Strategy: The precision strategy.
• Alg := "OM": The algorithm to use, either “Builtin” to use Magma’s bulitin algorithm or “OM” to use our implementation.
• Certificates: When true, also returns a corresponding sequence of certificates including fields F, E, Rho and Pi.
• Extensions: When true implies Certificates and also includes Extension in each certificate.

Roots (f :: RngUPolElt_FldPadExact)

-> []

The roots of f.

Parameters

• Strategy
• Alg

NewtonPolygonFactorization (f :: RngUPolElt_FldPadExact)

-> []

The factorization of f according to its Newton polygon, as a sequence of factors.

Parameters

• Strategy
• Residual := false: When true then further factorizes according to the factorization of each residual polynomial.

Builtin_Factorization (f :: RngUPolElt_FldPadExact)

-> [], FldPadElt, []

Called internally by Factorization with Alg:="Builtin".

Parameters

• Strategy: The precision strategy.
• Certificates: When true, also returns a corresponding sequence of certificates including fields F, E, Rho and Pi.
• Extensions: When true implies Certificates and also includes Extension in each certificate.
• Ideals: When true implies Certificates and also includes IdealGen1 and IdealGen2 in each certificate.
• UseNP := true: When true, factorizes f first by its Newton polygon. This can be a significant performance improvement for large degree polynomials with several faces.

Builtin_Roots (f :: RngUPolElt_FldPadExact)

-> []

Called internally by Roots with Alg:="Builtin".

Parameters

• Strategy: The precision strategy.
• UseNP := true: When true, factorizes f first by its Newton polygon.

ExactpAdics_Factorization (f :: RngUPolElt_FldPadExact)

-> [], FldPadExactElt, []

Called internally by Factorization with Alg:="OM".

Parameters

• Proof := true: When true, the output is proven.
• Certificates := false: When true, implies Proof:=true and returns certificates.
• Extensions := false: When true, implies Certificates:=true and certificates include extensions.
• InternalData := false: When true, implies Certificates:=true and certificates include the state of the branch leading to this factor.
• Strategy: The precision strategy.
• SimpleLift := false: When true, uses “single factor lifting” just enough to use simple Hensel lifting on the factors. Probably slower, but possibly more reliable.

ExactpAdics_Factorization (f :: RngUPolElt[FldPad])

-> [], FldPadElt, []

Our implementation of an OM factorization algorithm for Magma’s builtin p-adics.

Parameters

• Proof := true: When true, the output is proven.
• Certificates := false: When true, implies Proof:=true and also outputs certificates.
• Extensions := false: When true, implies Certificates:=true and certificates include extensions.
• InternalData := false: When true, implies Certificates:=true and certificates include the state of the branch leading to this factor.
• Lift := true: When false, does not lift the result to full precision. Hence faster, but gives less precise results.

ExactpAdics_Roots (f :: RngUPolElt_FldPadExact)

-> []

Called internally by Roots with Alg:="OM".

Parameters

• Strategy: The precision strategy.

ExactpAdics_Roots (f :: RngUPolElt[FldPad])

-> []

Our implementation of an OM factorization algorithm, specialised to root-finding, for Magma’s builtin p-adics.

Parameters

• Lift := true: When false, does not lift the result to full precision. Hence faster, but gives less precise results.