Univariate polynomials

Nemo allow the creation of dense, univariate polynomials over any ring $R$.

Polynomial types

Although the user rarely needs to deal directly with Julia types for Nemo objects, we provide the relevant information here for developers.

Generic univariate polynomials in Nemo have type GenPoly{T}, where T is the type of the coefficients of the polynomial.

The string representation of the variable and the base ring $R$ of a generic polynomial is stored in its parent object. Parent objects of generic univariate polynomials have type GenPolyRing{T}.

In addition to generic polynomials, Nemo provides access to numerous polynomial implementations over specific rings, provided by C/C++ libraries. The following table shows each of the polynomial types available in Nemo, their base ring $R$, the type of their parent objects and the library providing those types.

Base ring	Library	Element type	Parent type
Generic ring $R$	Nemo	GenPoly{T}	GenPolyRing{T}
$\mathbb{Z}$	Flint	fmpz_poly	FmpzPolyRing
$\mathbb{Z}/n\mathbb{Z}$ (small $n$)	Flint	nmod_poly	NmodPolyRing
$\mathbb{Z}/n\mathbb{Z}$ (large $n$)	Flint	fmpz_mod_poly	FmpzModPolyRing
$\mathbb{Q}$	Flint	fmpq_poly	FmpqPolyRing
$\mathbb{F}_{p^n}$ (small $n$)	Flint	fq_nmod_poly	FqNmodPolyRing
$\mathbb{F}_{p^n}$ (large $n$)	Flint	fq_poly	FqPolyRing

All polynomial element types belong to the abstract type PolyElem and all of the polynomial ring types belong to the abstract type PolyRing. This enables one to write generic functions that can accept any Nemo polynomial type.

Basic functionality

All univariate polynomial modules in Nemo must provide the functionality listed below. Note that only some of these functions are useful to a user.

Developers who are writing their own polynomial module, whether as an interface to a C library, or as some kind of generic module, must provide all of these functions for custom univariate polynomial types in Nemo.

We write T for the type of the polynomials in the polynomial ring.

All of these functions are provided for all existing polynomial types in Nemo.

parent_type{T <: PolyElem}(::Type{T})

Given the type of polynomial elements, should return the type of the corresponding parent object.

elem_type(R::PolyRing)

Given a parent object for the polynomial ring, return the type of elements of the polynomial ring.

Base.hash(a::PolyElem, h::UInt)

Return a UInt hexadecimal hash of the polynomial $a$. This should be xor'd with a fixed random hexadecimal specific to the polynomial type. The hash of each coefficient should be xor'd with the supplied parameter h as part of computing the hash.

fit!(a::PolyElem, n::Int)

By reallocating if necessary, ensure that the given polynomial has space for at least $n$ coefficients. This function does not change the length of the polynomial and will only ever increase the number of allocated coefficients. Any coefficients added by this function are initialised to zero.

normalise(a::PolyElem, n::Int)

Return the normalised length of the given polynomial, assuming its current length is $n$. Its normalised length is such that it either has nonzero leading term or is the zero polynomial. Note that this function doesn't normalise the polynomial. That can be done with a subsequent call to set_length! using the length returned by normalise.

set_length!(a::PolyElem, n::Int)

Set the length of an existing polynomial that has sufficient space allocated, i.e. a polynomial for which no reallocation is needed. Note that if the Julia type definition for a custom polynomial type has a field, length, which corresponds to the current length of the polynomial, then the developer doesn't need to supply this function, as the supplied generic implementation will work. Note that it can change the length to any value from zero to the number of coefficients currently allocated and initialised.

length(a::PolyElem)

Return the current length (not the number of allocated coefficients), of the given polynomial. Note that this function only needs to be provided by a developer for a custome polynomial type if the Julia type definition for polynomial elements doesn't contain a field length corresponding to the current length of the polynomial. Otherwise the supplied generic implementation will work.

coeff(a::PolyElem, n::Int)

Return the degree n coefficient of the given polynomial. Note coefficients are numbered from n = 0 for the constant coefficient. If $n$ is bigger then the degree of the polynomial, the function returns a zero coefficient. We require $n \geq 0$.

setcoeff!{T <: RingElem}(a::PolyElem{T}, n::Int, c::T)

Set the coefficient of the degree $n$ term of the given polynomial to the given value a. The polynomial is not normalised automatically after this operation, however the polynomial is automatically resized if there is not sufficient allocated space.

deepcopy(a::PolyElem)

Construct a copy of the given polynomial and return it. This function must recursively construct copies of all of the internal data in the given polynomial. Nemo polynomials are mutable and so returning shallow copies is not sufficient.

mul!(c::PolyElem, a::PolyElem, b::PolyElem)

Multiply $a$ by $b$ and set the existing polynomial $c$ to the result. This function is provided for performance reasons as it saves allocating a new object for the result and eliminates associated garbage collection.

addeq!(c::PolyElem, a::PolyElem)

In-place addition. Adds $a$ to $c$ and sets $c$ to the result. This function is provided for performance reasons as it saves allocating a new object for the result and eliminates associated garbage collection.

Given a parent object S for a polynomial ring, the following coercion functions are provided to coerce various elements into the polynomial ring. Developers provide these by overloading the call operator for the polynomial parent objects.

S()

Coerce zero into the ring $S$.

S(n::Integer)
S(n::fmpz)

Coerce an integer value or Flint integer into the polynomial ring $S$.

S(n::T)

Coerces an element of the base ring, of type T into $S$.

S(A::Array{T, 1})

Take an array of elements in the base ring, of type T and construct the polynomial with those coefficients, starting with the constant coefficient.

S(f::PolyElem)

Take a polynomial that is already in the ring $S$ and simply return it. A copy of the original is not made.

S(c::RingElem)

Try to coerce the given ring element into the polynomial ring. This only succeeds if $c$ can be coerced into the base ring.

In addition to the above, developers of custom polynomials must ensure the parent object of a polynomial type constains a field base_ring specifying the base ring, a field S containing a symbol (not a string) representing the variable name of the polynomial ring. They must also ensure that each polynomial element contains a field parent specifying the parent object of the polynomial.

Typically a developer will also overload the PolynomialRing generic function to create polynomials of the custom type they are implementing.

Polynomial ring constructors

In order to construct polynomials, one must first construct the polynomial ring itself. This is accomplished with the following constructor.

# Nemo.PolynomialRing — Method.

PolynomialRing(R::Ring, s::AbstractString{}; cached::Bool = true)

Given a base ring R and string s specifying how the generator (variable) should be printed, return a tuple S, x representing the new polynomial ring $S = R[x]$ and the generator $x$ of the ring. By default the parent object S will depend only on R and x and will be cached. Setting the optional argument cached to false will prevent the parent object S from being cached.

source

A shorthand version of this function is provided. Given a base ring R, we can abbreviate the above constructor as follows.

R["x"]

Here are some examples of creating polynomial rings and making use of the resulting parent objects to coerce various elements into the polynomial ring.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")
T, z = QQ["z"]

f = R()
g = R(123)
h = S(ZZ(1234))
k = S(x + 1)
m = T(z + 1)

Polynomial element constructors

Once a polynomial ring is constructed, there are various ways to construct polynomials in that ring.

The easiest way is simply using the generator returned by the PolynomialRing constructor and and build up the polynomial using basic arithmetic. Julia has quite flexible notation for the construction of polynomials in this way.

In addition we provide the following functions for constructing certain useful polynomials.

# Base.zero — Method.

zero(R::PolyRing)

Return the zero polynomial in the given polynomial ring.

source
# Base.one — Method.

one(R::PolyRing)

Return the constant polynomial $1$ in the given polynomial ring.

source
# Nemo.gen — Method.

gen(R::PolyRing)

Return the generator of the given polynomial ring.

source

Here are some examples of constructing polynomials.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x^3 + 3x + 21
g = (x + 1)*y^2 + 2x + 1

h = zero(S)
k = one(R)
m = gen(S)

Basic manipulation

Numerous functions are provided to manipulate polynomials and to set and retrieve coefficients and other basic data associated with the polynomials. Also see the section on basic functionality above.

# Nemo.base_ring — Method.

base_ring(R::PolyRing)

Return the base ring of the given polynomial ring.

source
# Nemo.base_ring — Method.

base_ring(a::PolyElem)

Return the base ring of the polynomial ring of the given polynomial.

source
# Base.parent — Method.

parent(a::PolyElem)

Return the parent of the given polynomial.

source
# Base.var — Method.

var(a::PolyRing)

Return the internal name of the generator of the polynomial ring. Note that this is returned as a Symbol not a String.

source
# Nemo.degree — Method.

degree(a::PolyElem)

Return the degree of the given polynomial. This is defined to be one less than the length, even for constant polynomials.

source
# Nemo.modulus — Method.

modulus{T <: ResElem}(a::PolyElem{T})

Return the modulus of the coefficients of the given polynomial.

source
# Nemo.lead — Method.

lead(x::PolyElem)

Return the leading coefficient of the given polynomial. This will be the nonzero coefficient of the term with highest degree unless the polynomial in the zero polynomial, in which case a zero coefficient is returned.

source
# Nemo.iszero — Method.

iszero(a::PolyElem)

Return true if the given polynomial is zero, otherwise return false.

source
# Nemo.isone — Method.

isone(a::PolyElem)

Return true if the given polynomial is the constant polynomial $1$, otherwise return false.

source
# Nemo.isgen — Method.

isgen(a::PolyElem)

Return true if the given polynomial is the constant generator of its polynomial ring, otherwise return false.

source
# Nemo.isunit — Method.

isunit(a::PolyElem)

Return true if the given polynomial is a unit in its polynomial ring, otherwise return false.

source
# Base.den — Method.

den(a::fmpq_poly)

Return the least common denominator of the coefficients of the polynomial $a$.

source

Here are some examples of basic manipulation of polynomials.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")
T, z = PolynomialRing(QQ, "z")

a = zero(S)
b = one(S)

c = ZZ(1)//2*z^2 + ZZ(1)//3
d = x*y^2 + (x + 1)*y + 3

U = base_ring(S)
V = base_ring(y + 1)
v = var(S)
T = parent(y + 1)

f = lead(d)

g = isgen(y)
h = isone(b)
k = iszero(a)
m = isunit(b)
n = degree(d)
p = length(b)
q = den(c)

Arithmetic operators

All the usual arithmetic operators are overloaded for Nemo polynomials. Note that Julia uses the single slash for floating point division. Therefore to perform exact division in a ring we use divexact. To construct an element of a fraction field one can use the double slash operator //.

# Base.- — Method.

-(x)

Unary minus operator.

source

-(a::PolyElem)

Return $-a$.

source
# Base.+ — Method.

+{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return $a + b$.

source

+{T <: RingElem}(a::T, b::PolyElem{T})

Return $a + b$.

source

+{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a + b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return $a - b$.

source

-{T <: RingElem}(a::T, b::PolyElem{T})

Return $a - b$.

source

-{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a - b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return $a\times b$.

source

*{T <: RingElem}(a::T, b::PolyElem{T})

Return $a\times b$.

source

*{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a\times b$.

source
# Nemo.divexact — Method.

divexact(a::PolyElem, b::PolyElem)

Return $a/b$ where the quotient is expected to be exact.

source

divexact{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a/b$ where the quotient is expected to be exact.

source

divexact(a::PolyElem, b::Integer)

Return $a/b$ where the quotient is expected to be exact.

source

divexact(a::PolyElem, b::fmpz)

Return $a/b$ where the quotient is expected to be exact.

source

The following ad hoc operators are also provided.

# Base.+ — Method.

+(a::Integer, b::PolyElem)

Return $a + b$.

source
# Base.+ — Method.

+(a::PolyElem, b::Integer)

Return $a + b$.

source
# Base.+ — Method.

+(a::fmpz, b::PolyElem)

Return $a + b$.

source
# Base.+ — Method.

+(a::PolyElem, b::fmpz)

Return $a + b$.

source
# Base.+ — Method.

+{T <: RingElem}(a::T, b::PolyElem{T})

Return $a + b$.

source
# Base.+ — Method.

+(x, y...)

Addition operator. x+y+z+... calls this function with all arguments, i.e. +(x, y, z, ...).

source

+{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return $a + b$.

source

+{T <: RingElem}(a::T, b::PolyElem{T})

Return $a + b$.

source

+(a::Integer, b::PolyElem)

Return $a + b$.

source

+(a::fmpz, b::PolyElem)

Return $a + b$.

source

+{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a + b$.

source

+(a::PolyElem, b::Integer)

Return $a + b$.

source

+(a::PolyElem, b::fmpz)

Return $a + b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-(a::Integer, b::PolyElem)

Return $a - b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-(a::PolyElem, b::Integer)

Return $a - b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-(a::fmpz, b::PolyElem)

Return $a - b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-(a::PolyElem, b::fmpz)

Return $a - b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source

-{T <: RingElem}(a::T, b::PolyElem{T})

Return $a - b$.

source
# Base.- — Method.

-(x, y)

Subtraction operator.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*(a::Integer, b::PolyElem)

Return $a\times b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*(a::PolyElem, b::Integer)

Return $a\times b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*(a::fmpz, b::PolyElem)

Return $a\times b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*(a::PolyElem, b::fmpz)

Return $a\times b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source

*{T <: RingElem}(a::T, b::PolyElem{T})

Return $a\times b$.

source
# Base.* — Method.

*(x, y...)

Multiplication operator. x*y*z*... calls this function with all arguments, i.e. *(x, y, z, ...).

source
# Nemo.divexact — Method.

divexact(a::PolyElem, b::Integer)

Return $a/b$ where the quotient is expected to be exact.

source
# Nemo.divexact — Method.

divexact(a::PolyElem, b::fmpz)

Return $a/b$ where the quotient is expected to be exact.

source
# Nemo.divexact — Method.

divexact{T <: RingElem}(a::PolyElem{T}, b::T)

Return $a/b$ where the quotient is expected to be exact.

source
# Base.^ — Method.

^(x, y)

Exponentiation operator.

source

If the appropriate promote_rule and coercion exists, these operators can also be used with elements of other rings. Nemo will try to coerce the operands to the dominating type and then apply the operator.

Here are some examples of arithmetic operations on polynomials.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3
g = (x + 1)*y + (x^3 + 2x + 2)

h = f - g
k = f*g
m = f + g
n = g - 4
p = fmpz(5) - g
q = f*7
r = divexact(f, -1)
s = divexact(g*(x + 1), x + 1)
t = f^3

Comparison operators

The following comparison operators are implemented for polynomials in Nemo.

# Base.== — Method.

=={T <: RingElem}(x::PolyElem{T}, y::PolyElem{T})

Return true if $x == y$ arithmetically, otherwise return false. Recall that power series to different precisions may still be arithmetically equal to the minimum of the two precisions.

source

=={T <: RingElem}(x::PolyElem{T}, y::T)

Return true if $x == y$ arithmetically, otherwise return false.

source

=={T <: RingElem}(x::T, y::PolyElem{T})

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.isequal — Method.

isequal{T <: RingElem}(x::PolyElem{T}, y::PolyElem{T})

Return true if $x == y$ exactly, otherwise return false. This function is useful in cases where the coefficients of the polynomial are inexact, e.g. power series. Only if the power series are precisely the same, to the same precision, are they declared equal by this function.

source

In addition we have the following ad hoc comparison operators.

# Base.== — Method.

=={T <: RingElem}(x::PolyElem{T}, y::T)

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.== — Method.

=={T <: RingElem}(x::T, y::PolyElem{T})

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.== — Method.

==(x::PolyElem, y::Integer)

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.== — Method.

==(x::Integer, y::PolyElem)

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.== — Method.

==(x::PolyElem, y::fmpz)

Return true if $x == y$ arithmetically, otherwise return false.

source
# Base.== — Method.

==(x::fmpz, y::PolyElem)

Return true if $x == y$ arithmetically, otherwise return false.

source

Here are some examples of comparisons.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3
g = x*y^2 + (x + 1)*y + 3
h = S(3)

f == g
isequal(f, g)
f != 3
g != x
h == fmpz(3)

Truncation

# Base.truncate — Method.

truncate(a::PolyElem, n::Int)

Return $a$ truncated to $n$ terms.

source
# Nemo.mullow — Method.

mullow{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T}, n::Int)

Return $a\times b$ truncated to $n$ terms.

source

Here are some examples of truncated operations.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3
g = (x + 1)*y + (x^3 + 2x + 2)

h = truncate(f, 1)
k = mullow(f, g, 4)

Reversal

# Base.reverse — Method.

reverse(x::PolyElem, len::Int)

Return the reverse of the polynomial $x$, thought of as a polynomial of the given length (the polynomial will be notionally truncated or padded with zeroes before the leading term if necessary to match the specified length). The resulting polynomial is normalised. If len is negative we throw a DomainError().

source
# Base.reverse — Method.

reverse(x::PolyElem)

Return the reverse of the polynomial $x$, i.e. the leading coefficient of $x$ becomes the constant coefficient of the result, etc. The resulting polynomial is normalised.

source

Here are some examples of reversal.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3

g = reverse(f, 7)
h = reverse(f)

Shifting

# Nemo.shift_left — Method.

shift_left(x::PolyElem, n::Int)

Return the polynomial $f$ shifted left by $n$ terms, i.e. multiplied by $x^n$.

source
# Nemo.shift_right — Method.

shift_right(f::PolyElem, n::Int)

Return the polynomial $f$ shifted right by $n$ terms, i.e. divided by $x^n$.

source

Here are some examples of shifting.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3

g = shift_left(f, 7)
h = shift_right(f, 2)

Modulo arithmetic

For polynomials over a field or residue ring, we can reduce modulo a given polynomial. This isn't always well-defined in the case of a residue ring, but when it is well-defined, we obtain the correct result. If Nemo encounters an impossible inverse, an exception will be raised.

# Nemo.mulmod — Method.

mulmod{T <: Union{ResElem, FieldElem}}(a::PolyElem{T}, b::PolyElem{T}, d::PolyElem{T})

Return $a\times b \pmod{d}$.

source
# Nemo.powmod — Method.

powmod{T <: Union{ResElem, FieldElem}}(a::PolyElem{T}, b::Int, d::PolyElem{T})

Return $a^b \pmod{d}$. There are no restrictions on $b$.

source
# Nemo.powmod — Method.

powmod(x::fmpz_mod_poly, e::fmpz, y::fmpz_mod_poly)

Return $x^e \pmod{y}$.

source
# Base.invmod — Method.

invmod{T <: Union{ResElem, FieldElem}}(a::PolyElem{T}, b::PolyElem{T})

Return $a^{-1} \pmod{d}$.

source

Here are some examples of modular arithmetic.

R, x = PolynomialRing(QQ, "x")
S = ResidueRing(R, x^3 + 3x + 1)
T, y = PolynomialRing(S, "y")

f = (3*x^2 + x + 2)*y + x^2 + 1
g = (5*x^2 + 2*x + 1)*y^2 + 2x*y + x + 1
h = (3*x^3 + 2*x^2 + x + 7)*y^5 + 2x*y + 1

invmod(f, g)
mulmod(f, g, h)
powmod(f, 3, h)

Euclidean division

For polynomials over a field, we have a euclidean domain, and in many cases for polynomials over a residue ring things behave as though we had a euclidean domain so long as we don't hit an impossible inverse. For such rings we define euclidean division of polynomials. If an impossible inverse is hit, we raise an exception.

# Base.mod — Method.

mod{T <: Union{ResElem, FieldElem}}(f::PolyElem{T}, g::PolyElem{T})

Return $f \pmod{g}$.

source
# Base.divrem — Method.

divrem{T <: Union{ResElem, FieldElem}}(f::PolyElem{T}, g::PolyElem{T})

Return a tuple $(q, r)$ such that $f = qg + r$ where $q$ is the euclidean quotient of $f$ by $g$.

source

Here are some examples of euclidean division.

R = ResidueRing(ZZ, 7)
S, x = PolynomialRing(R, "x")
T = ResidueRing(S, x^3 + 3x + 1)
U, y = PolynomialRing(T, "y")

f = y^3 + x*y^2 + (x + 1)*y + 3
g = (x + 1)*y^2 + (x^3 + 2x + 2)

h = mod(f, g)
q, r = divrem(f, g)

Pseudodivision

Given two polynomials $a, b$, pseudodivision computes polynomials $q$ and $r$ with length$(r) <$ length$(b)$ such that $L^d a = bq + r,$ where $d =$ length$(a) -$ length$(b) + 1$ and $L$ is the leading coefficient of $b$.

We call $q$ the pseudoquotient and $r$ the pseudoremainder.

# Nemo.pseudorem — Method.

pseudorem{T <: RingElem}(f::PolyElem{T}, g::PolyElem{T})

Return the pseudoremainder of $a$ divided by $b$. If $b = 0$ we throw a DivideError().

source
# Nemo.pseudodivrem — Method.

pseudodivrem{T <: RingElem}(f::PolyElem{T}, g::PolyElem{T})

Return a tuple $(q, r)$ consisting of the pseudoquotient and pseudoremainder of $a$ divided by $b$. If $b = 0$ we throw a DivideError().

source

Here are some examples of pseudodivision.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3
g = (x + 1)*y + (x^3 + 2x + 2)

h = pseudorem(f, g)
q, r = pseudodivrem(f, g)

Content, primitive part, GCD and LCM

In Nemo, we allow computation of the greatest common divisor of polynomials over any ring. This is enabled by making use of pseudoremainders when we aren't working over a euclidean domain or something mimicking such a domain. In certain cases this allows us to return a greatest common divisor when it otherwise wouldn't be possible. However, a greatest common divisor is not necessarily unique, or even well-defined.

If an impossible inverse is encountered whilst computing the greatest common divisor, an exception is thrown.

# Base.gcd — Method.

gcd{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return a greatest common divisor of $a$ and $b$ if it exists.

source
# Base.lcm — Method.

lcm{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return a least common multiple of $a$ and $b$ if it exists.

source
# Nemo.content — Method.

content(a::PolyElem)

Return the content of $a$, i.e. the greatest common divisor of its coefficients.

source
# Nemo.primpart — Method.

primpart(a::PolyElem)

Return the primitive part of $a$, i.e. the polynomial divided by its content.

source
# Base.gcdx — Method.

gcdx{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return a tuple $(r, s, t)$ such that $r$ is the resultant of $a$ and $b$ and such that $r = a\times s + b\times t$.

source
# Base.gcdx — Method.

gcdx{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return a tuple $(r, s, t)$ such that $r$ is the resultant of $a$ and $b$ and such that $r = a\times s + b\times t$.

source

gcdx{T <: Union{ResElem, FieldElem}}(a::PolyElem{T}, b::PolyElem{T})

Return a tuple $(g, s, t)$ such that $g$ is the greatest common divisor of $a$ and $b$ and such that $r = a\times s + b\times t$.

source
# Nemo.gcdinv — Method.

gcdinv{T <: Union{ResElem, FieldElem}}(a::PolyElem{T}, b::PolyElem{T})

Return a tuple $(g, s)$ such that $g$ is the greatest common divisor of $a$ and $b$ and such that $s = a^{-1} \pmod{b}$. This function is useful for inverting modulo a polynomial and checking that it really was invertible.

source

Here are some examples of content, primitive part and GCD.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

k = x*y^2 + (x + 1)*y + 3
l = (x + 1)*y + (x^3 + 2x + 2)
m = y^2 + x + 1

n = content(k)
p = primpart(k*(x^2 + 1))
q = gcd(k*m, l*m)
r = lcm(k*m, l*m)

R, x = PolynomialRing(QQ, "x")
T = ResidueRing(R, x^3 + 3x + 1)
U, z = PolynomialRing(T, "z")

g = z^3 + 2z + 1
h = z^5 + 1

r, s, t = gcdx(g, h)
u, v = gcdinv(g, h)

Evaluation, composition and substitution

# Nemo.evaluate — Method.

evaluate{T <: RingElem}(a::PolyElem{T}, b::T)

Evaluate the polynomial $a$ at the value $b$ and return the result.

source
# Nemo.evaluate — Method.

evaluate(a::PolyElem, b::Integer)

Evaluate the polynomial $a$ at the value $b$ and return the result.

source
# Nemo.evaluate — Method.

evaluate(a::PolyElem, b::fmpz)

Evaluate the polynomial $a$ at the value $b$ and return the result.

source
# Nemo.compose — Method.

compose(a::PolyElem, b::PolyElem)

Compose the polynomial $a$ with the polynomial $b$ and return the result, i.e. return $a\circ b$.

source
# Nemo.subst — Method.

subst{T <: RingElem}(f::PolyElem{T}, a::Any)

Evaluate the polynomial $f$ at $a$. Note that $a$ can be anything, whether a ring element or not.

source

We also overload the functional notation so that the polynomial $f$ can be evaluated at $a$ by writing $f(a)$. This feature is only available with Julia 0.5 however.

Here are some examples of polynomial evaluation, composition and substitution.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = x*y^2 + (x + 1)*y + 3
g = (x + 1)*y + (x^3 + 2x + 2)
M = R[x + 1 2x; x - 3 2x - 1]

h = evaluate(f, 3)
k = evaluate(f, x^2 + 2x + 1)
m = compose(f, g)
n = subst(f, M)
p = f(M)
k = f(23)

Derivative and integral

# Nemo.derivative — Method.

derivative(a::PolyElem)

Return the derivative of the polynomial $a$.

source
# Nemo.integral — Method.

integral{T <: Union{ResElem, FieldElem}}(x::PolyElem{T})

Return the integral of the polynomial $a$.

source

Here are some examples of integral and derivative.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")
T, z = PolynomialRing(QQ, "z")
U = ResidueRing(T, z^3 + 3z + 1)
V, w = PolynomialRing(U, "w")

f = x*y^2 + (x + 1)*y + 3
g = (z^2 + 2z + 1)*w^2 + (z + 1)*w - 2z + 4

h = derivative(f)
k = integral(g)   

Resultant and discriminant

# Nemo.resultant — Method.

resultant{T <: RingElem}(a::PolyElem{T}, b::PolyElem{T})

Return the resultant of the $a$ and $b$.

source
# Nemo.discriminant — Method.

discriminant(a::PolyElem)

Return the discrimnant of the given polynomial.

source

Here are some examples of computing the resultant and discriminant.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = 3x*y^2 + (x + 1)*y + 3
g = 6(x + 1)*y + (x^3 + 2x + 2)

h = resultant(f, g)
k = discriminant(f)

Newton representation

# Nemo.monomial_to_newton! — Method.

monomial_to_newton!{T <: RingElem}(P::Array{T, 1}, roots::Array{T, 1})

Converts a polynomial $p$, given as an array of coefficients, in-place from its coefficients given in the standard monomial basis to the Newton basis for the roots $r_0, r_1, \ldots, r_{n-2}$. In other words, this determines output coefficients $c_i$ such that $c_0 + c_1(x-r_0) + c_2(x-r_0)(x-r_1) + \ldots + c_{n-1}(x-r_0)(x-r_1)\cdots(x-r_{n-2})$ is equal to the input polynomial.

source
# Nemo.newton_to_monomial! — Method.

newton_to_monomial!{T <: RingElem}(P::Array{T, 1}, roots::Array{T, 1})

Converts a polynomial $p$, given as an array of coefficients, in-place from its coefficients given in the Newton basis for the roots $r_0, r_1, \ldots, r_{n-2}$ to the standard monomial basis. In other words, this evaluates $c_0 + c_1(x-r_0) + c_2(x-r_0)(x-r_1) + \ldots + c_{n-1}(x-r_0)(x-r_1)\cdots(x-r_{n-2})$ where $c_i$ are the input coefficients given by $p$.

source

Here are some examples of conversion to and from Newton representation.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = 3x*y^2 + (x + 1)*y + 3
g = deepcopy(f)
roots = [R(1), R(2), R(3)]

monomial_to_newton!(g.coeffs, roots)
newton_to_monomial!(g.coeffs, roots)

Interpolation

# Nemo.interpolate — Method.

interpolate{T <: RingElem}(S::PolyRing, x::Array{T, 1}, y::Array{T, 1})

Given two arrays of values $xs$ and $ys$ of the same length $n$, find the polynomial $f$ in the polynomial ring $R$ of length at most $n$ such that $f$ has the value $ys$ at the points $xs$. The values in the arrays $xs$ and $ys$ must belong to the base ring of the polynomial ring $R$.

source

Here is an example of interpolation.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

xs = [R(1), R(2), R(3), R(4)]
ys = [R(1), R(4), R(9), R(16)]

f = interpolate(S, xs, ys)

Signature

Signature is only available for certain coefficient rings.

# Nemo.signature — Method.

signature(f::fmpz_poly)

Return the signature of the polynomial $f$, i.e. a tuple $(r, s)$ such that $r$ is the number of real roots of $f$ and $s$ is half the number of complex roots.

source
# Nemo.signature — Method.

signature(f::fmpq_poly)

Return the signature of $f$, i.e. a tuple $(r, s)$ where $r$ is the number of real roots of $f$ and $s$ is half the number of complex roots.

source

Here is an example of signature.

R, x = PolynomialRing(ZZ, "x")

f = x^3 + 3x + 1

(r, s) = signature(f)

Lifting

When working over a residue ring it is useful to be able to lift to the base ring of the residue ring, e.g. from $\mathbb{Z}/n\mathbb{Z}$ to $\mathbb{Z}$.

# Nemo.lift — Method.

function lift(R::FmpzPolyRing, y::nmod_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

source
# Nemo.lift — Method.

function lift(R::FmpzPolyRing, y::fmpz_mod_poly)

Lift from a polynomial over $\mathbb{Z}/n\mathbb{Z}$ to a polynomial over $\mathbb{Z}$ with minimal reduced nonnegative coefficients. The ring R specifies the ring to lift into.

source

Here is an example of lifting.

R = ResidueRing(ZZ, 123456789012345678949)
S, x = PolynomialRing(R, "x")
T, y = PolynomialRing(ZZ, "y")

f = x^2 + 2x + 1

a = lift(T, f)

Factorisation

Polynomials can only be factorised over certain rings. In general we use the same format for the output as the Julia factorisation function, namely an associative array with polynomial factors as keys and exponents as values.

# Nemo.isirreducible — Method.

isirreducible(x::nmod_poly)

Return true if $x$ is irreducible, otherwise return false.

source
# Nemo.isirreducible — Method.

isirreducible(x::fmpz_mod_poly)

Return true if $x$ is irreducible, otherwise return false.

source
# Nemo.issquarefree — Method.

issquarefree(x::nmod_poly)

Return true if $x$ is squarefree, otherwise return false.

source
# Nemo.issquarefree — Method.

issquarefree(x::fmpz_mod_poly)

Return true if $x$ is squarefree, otherwise return false.

source
# Base.factor — Method.

factor(x::nmod_poly)

Return the factorisation of $x$.

source
# Base.factor — Method.

factor(x::fmpz_mod_poly)

Return the factorisation of $x$.

source
# Nemo.factor_squarefree — Method.

factor_squarefree(x::nmod_poly)

Return the squarefree factorisation of $x$.

source
# Nemo.factor_squarefree — Method.

factor_squarefree(x::fmpz_mod_poly)

Return the squarefree factorisation of $x$.

source
# Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::nmod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

source
# Nemo.factor_distinct_deg — Method.

factor_distinct_deg(x::fmpz_mod_poly)

Return the distinct degree factorisation of a squarefree polynomial $x$.

source

Here are some examples of factorisation.

R = ResidueRing(ZZ, 23)
S, x = PolynomialRing(R, "x")

f = x^2 + 2x + 1
g = x^3 + 3x + 1

R = factor(f*g)
S = factor_squarefree(f*g)
T = factor_distinct_deg((x + 1)*g*(x^5+x^3+x+1))

Special functions

The following special functions can be computed for any polynomial ring. Typically one uses the generator $x$ of a polynomial ring to get the respective special polynomials expressed in terms of that generator.

# Nemo.chebyshev_t — Method.

chebyshev_t(n::Int, x::PolyElem)

Return the Chebyshev polynomial of the first kind $T_n(x)$, defined by $T_n(x) = \cos(n \cos^{-1}(x))$.

source
# Nemo.chebyshev_u — Method.

chebyshev_u(n::Int, x::PolyElem)

Return the Chebyshev polynomial of the first kind $U_n(x)$, defined by $(n+1) U_n(x) = T'_{n+1}(x)$.

source

The following special polynomials are only available for certain base rings.

# Nemo.cyclotomic — Method.

cyclotomic(n::Int, x::fmpz_poly)

Return the $n$th cyclotomic polynomial, defined as $\Phi_n(x) = \prod_{\omega} (x-\omega),$ where $\omega$ runs over all the $n$th primitive roots of unity.

source
# Nemo.swinnerton_dyer — Method.

swinnerton_dyer(n::Int, x::fmpz_poly)

Return the Swinnerton-Dyer polynomial $S_n$, defined as the integer polynomial $S_n = \prod (x \pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5} \pm \ldots \pm \sqrt{p_n})$ where $p_n$ denotes the $n$-th prime number and all combinations of signs are taken. This polynomial has degree $2^n$ and is irreducible over the integers (it is the minimal polynomial of $\sqrt{2} + \ldots + \sqrt{p_n}$).

source
# Nemo.cos_minpoly — Method.

cos_minpoly(n::Int, x::fmpz_poly)

Return the minimal polynomial of $2 \cos(2 \pi / n)$. For suitable choice of $n$, this gives the minimal polynomial of $2 \cos(a \pi)$ or $2 \sin(a \pi)$ for any rational $a$.

source
# Nemo.theta_qexp — Method.

theta_qexp(e::Int, n::Int, x::fmpz_poly)

Return the $q$-expansion to length $n$ of the Jacobi theta function raised to the power $r$, i.e. $\vartheta(q)^r$ where $\vartheta(q) = 1 + \sum_{k=1}^{\infty} q^{k^2}$.

source
# Nemo.eta_qexp — Method.

eta_qexp(e::Int, n::Int, x::fmpz_poly)

Return the $q$-expansion to length $n$ of the Dedekind eta function (without the leading factor $q^{1/24}$) raised to the power $r$, i.e. $(q^{-1/24} \eta(q))^r = \prod_{k=1}^{\infty} (1 - q^k)^r$. In particular, $r = -1$ gives the generating function of the partition function $p(k)$, and $r = 24$ gives, after multiplication by $q$, the modular discriminant $\Delta(q)$ which generates the Ramanujan tau function $\tau(k)$.

source

Here are some examples of special functions.

R, x = PolynomialRing(ZZ, "x")
S, y = PolynomialRing(R, "y")

f = chebyshev_t(20, y)
g = chebyshev_u(15, y)
h = cyclotomic(120, x)
j = swinnerton_dyer(5, x)
k = cos_minpoly(30, x)
l = theta_qexp(3, 30, x)
m = eta_qexp(24, 30, x)
o = cyclotomic(10, 1 + x + x^2)