Univariate polynomials

Contents

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

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.

Creation of polynomials

Special values

Generator (R :: RngUPol_FldPadExact)

-> RngUPolElt_FldPadExact

The generator of R.

Zero (R :: RngUPol_FldPadExact)

-> RngUPolElt_FldPadExact

Zero and one.

From coefficients

Polynomial (cs :: [FldPadExactElt])

Polynomial (cs :: ModTupFldElt_FldPadExact)

-> RngUPolElt_FldPadExact

The polynomial with coefficients cs.

Polynomial (F :: FldPadExact, cs :: [])

-> RngUPolElt_FldPadExact

The polynomial over F with coefficients cs.

Coercion

We can coerce the following to a polynomial in R:

• A polynomial in R
• A polynomial whose coefficients are coercible to the base ring of R
• A sequence or vector of anything coercible to the base ring of R
• Anything coercible to the base ring of R

IsCoercible (R :: RngUPol_FldPadExact, X)

-> BoolElt, Any

True if X is coercible to R.

ChangeRing (f :: RngUPolElt_FldPadExact, F :: FldPadExact)

ChangeRing (f :: RngUPolElt, F :: FldPadExact)

-> RngUPolElt_FldPadExact

Changes the base ring of f to F.

Polynomial basics

Degree

Degree (f :: RngUPolElt_FldPadExact)

-> RngIntElt

The degree of f.

Coefficients

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

-> RngIntElt

The ith coefficient of f.

Coefficients (f :: RngUPolElt_FldPadExact)

-> []

The coefficients of f.

LeadingCoefficient (f :: RngUPolElt_FldPadExact)

-> FldPadExactElt

The leading coefficient of f.

Arithmetic

'-' (f :: RngUPolElt_FldPadExact)

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

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

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

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

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

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

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

-> RngUPolElt_FldPadExact

Negate, add, subtract, multiply, divide by scalar, power, sum, product.

Parameters

• Safe := false: When true, this may be used as an intermediate variable in WithDependencies with the Fast option.

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

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

-> RngUPolElt_FldPadExact

Division and remainder.

Parameters

• Safe := false: When true, this may be used as an intermediate variable in WithDependencies with the Fast option.

Derivative

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

-> RngUPolElt_FldPadExact

The mth or first derivative of f.

Derivative (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

The derivative of f.

Evaluate

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

-> FldPadExact

Evaluates f(x).

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

-> RngUPolElt_FldPadExact

Evaluates f(g).

Special forms

IsEisenstein (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is Eisenstein. That is, the leading coefficient has valuation 0, the constant coefficient has valuation 1, and the other coefficients have valuation at least 1. Eisenstein polynomials define totally ramified extensions.

IsInertial (f :: RngUPolElt_FldPadExact)

-> BoolElt

True if f is inertial. That is, it is integral, the leading coefficient has valuation 0, and it is irreducible over the residue class field. Inertial polynomials define unramified extensions.

Discriminant and resultant

Discriminant (f :: RngUPolElt_FldPadExact)

-> FldPadExact

The discriminant of f.

Parameters

• Safe := false: When true, this may be used as an intermediate variable in WithDependencies with the Fast option.

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

-> FldPadExact

The resultant of f and g.

Parameters

• Safe := false: When true, this may be used as an intermediate variable in WithDependencies with the Fast option.

Newton polygon

NewtonPolygon (f :: RngUPolElt_FldPadExact)

-> NwtnPgon

The Newton polygon of f.

If some of the coefficients of f are weakly zero, it can sometimes be quicker to find just part of the polygon. The Support parameter controls how much of the Newton polygon is required, and is one of:

• A single integer or rational, which must be in the support.
• A sequence or tuple of two integers or rationals, which specify an interval which must be in the support.
• A function accepting a Newton polygon and returning true if its support is valid.

Parameters

• Support: Specifies a lower bound on the support of the returned polygon.

Hensel lifting

IsHenselLiftable (f :: RngUPolElt_FldPadExact, 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.

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

• 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.

Root-finding and factorization

Roots (f :: RngUPolElt_FldPadExact)

-> []

The roots of f over its base ring, as a sequence of <root,multiplicity> pairs. Aside from some (exactly) zero roots, which are handled separately, f must be squarefree.

HasRoot (f :: RngUPolElt_FldPadExact)

-> BoolElt, FldPadExactElt

True if f has a root it its base ring. If so, returns one.

Factorization (f :: RngUPolElt_FldPadExact)

-> [], FldPadExactElt, []

The factorization of f over its base ring, as a sequence of <factor,multiplicty> pairs. Aside from some (exactly) zero roots, which are handled separately, f must be squarefree. Also returns the leading coefficient of f.

Internally, this calls ExactpAdics_Factorization, which has more parameters.

Parameters

• Certificates := false: When true, also returns a sequence of certificates corresponding to the factors.
• Extensions := false: When true, implies Certificates:=true, and the certificates also include the extension defined by the factor.

IsIrreducible (f :: RngUPolElt_FldPadExact)

-> BoolElt, Any

True if f is irreducible.

Parameters

• Certificate := false: When true, also returns a certificate when f is irreducible.
• Extension := false: When true, implies Certificates:=true, and the certificate also includes the extension defined by the factor.

NewtonPolygonFactorization (f :: RngUPolElt_FldPadExact)

-> []

The factorization of f according to its Newton polygon, as a sequence of factors. The factors are ordered by slope, from lowest (most negative) to highest.

Parameters

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

SplittingField (f :: RngUPolElt_FldPadExact)

-> FldPadExact

A splitting field for f.

Set the verbosity of ExactpAdics_SplittingField to 1 to see timings of intermediate steps and degrees of intermediate fields.

Parameters

• Alg := "": A space-separated string of flags defining the algorithm. Alg1 (default), Alg2: Which algorithm to use; Alg1 maintains a pool of factors of f, whereas Alg2 factors f each iteration. MaxDeg, MinDeg (default), Oldest, Newest: how to choose which factor to adjoin a root of. Std, NoStd (default): wheter or not to put each extension into standard form (using StandardForm whose linear algebra can dominate any time saved). Opt (default),NoOpt: whether or not to make an optimized representation of each extension (using OptimizedRepresentation). Hensel, NoHensel (default): whether or not to Hensel-lift each factor over each extension, thus making it depend only on f and the extension. Unram, NoUnram (default): whether or not to immediately make an unramified extension when possible.

ExactpAdics_Factorization (f :: RngUPolElt_FldPadExact)

-> [], FldPadExactElt, []

Called internally by Factorization.

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.
• SimpleLift := false: When true, uses “single factor lifting” just enough to use simple Hensel lifting on the factors. Probably slower, but possibly more reliable.
• DegreeMle := 0: Only returns factors whose degree divides this, i.e. the degree is “multiplicatively less than” this.
• DegreeGe := 1: Only returns factors whose degree is at least this.
• Limit: A bound on the number of factors returned.

ExactpAdics_Roots (f :: RngUPolElt_FldPadExact)

-> []

Called internally by Roots.

Parameters

• Limit

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.
• DegreeMle := 0: Only returns factors whose degree divides this, i.e. the degree is “multiplicatively less than” this.
• DegreeGe := 1: Only returns factors whose degree is at least this.
• Limit: A bound on the number of factors returned.

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.

Internals

Approximation

WeakValuation (f :: RngUPolElt_FldPadExact)

-> ValRngUPolElt_FldPadExact

The weak valuation of f.

AbsolutePrecision (f :: RngUPolElt_FldPadExact)

-> ValRngUPolElt_FldPadExact

The weak valuation of f.

WeakDegree (f :: RngUPolElt_FldPadExact)

-> RngIntElt

The weak degree of f, an upper bound on the actual degree.

WeakApproximation (f :: RngUPolElt_FldPadExact)

-> RngUPolElt_FldPadExact

A polynomial weakly equal to f at its current precision.

IsDefinitelyFullDegree (f :: RngUPolElt_FldPadExact)

-> BoolElt, RngIntElt

True if f is definitely full degree.

Parameters

• Minimize

EnsureAllApproximationsFullDegree (f :: RngUPolElt_FldPadExact)

Ensures that all approximations of f are full-degree.