Univariate polynomial functionality

AbstractAlgebra.jl provides a module, implemented in src/Poly.jl for polynomials over any commutative ring belonging to the AbstractAlgebra abstract type hierarchy. This functionality will work for any univariate polynomial type which follows the Univariate Polynomial Ring interface.

Generic univariate polynomial types

AbstractAlgebra.jl provides a generic polynomial type based on Julia arrays which is implemented in src/generic/Poly.jl.

These generic polynomials have type Generic.Poly{T} where T is the type of elements of the coefficient ring. Internally they consist of a Julia array of coefficients and some additional fields for length and a parent object, etc. See the file src/generic/GenericTypes.jl for details.

Parent objects of such polynomials have type Generic.PolyRing{T}.

The string representation of the variable of the polynomial ring and the base/coefficient ring $R$ is stored in the parent object.

Abstract types

All univariate polynomial element types belong to the abstract type PolyElem{T} and the polynomial ring types belong to the abstract type PolyRing{T}. This enables one to write generic functions that can accept any AbstractAlgebra polynomial type.

Note

Both the generic polynomial ring type Generic.PolyRing{T} and the abstract type it belongs to, PolyRing{T}, are called PolyRing. The former is a (parameterised) concrete type for a polynomial ring over a given base ring whose elements have type T. The latter is an abstract type representing all polynomial ring types in AbstractAlgebra.jl, whether generic or very specialised (e.g. supplied by a C library).

Polynomial ring constructors

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

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.

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

R["x"]

It is also possible to create a polynomial ring with default symbol as follows. This is a lightweight constructor and should be used in generic algorithms wherever possible when creating polynomial rings where the symbol does not matter.

PolyRing(R::Ring)

Given a base ring R return the polynomial ring $S = R[x]$. Note that unlike the constructors above, the return type is not a tuple. Only the ring is returned and not the generator. The polynomial ring is not cached.

Here are some examples of creating polynomial rings and their associated generators.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> T, z = QQ["z"]
(Univariate Polynomial Ring in z over Rationals, z)

julia> U = PolyRing(ZZ)
Univariate Polynomial Ring in x over Integers

All of the examples here are generic polynomial rings, but specialised implementations of polynomial rings provided by external modules will also usually provide a PolynomialRing constructor to allow creation of their polynomial rings.

Polynomial 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 build up the polynomial using basic arithmetic.

The Julia language has special syntax for the construction of polynomials in terms of a generator, e.g. we can write 2x instead of 2*x.

A second way is to use the polynomial ring to construct a polynomial. There are the usual ways of constructing an element of a ring.

(R::PolyRing)() # constructs zero
(R::PolyRing)(c::Integer)
(R::PolyRing)(c::elem_type(R))
(R::PolyRing{T})(a::T) where T <: RingElement

For polynommials there is also the following more general constructor accepting an array of coefficients.

(S::PolyRing{T})(A::Vector{T}) where T <: RingElem
(S::PolyRing{T})(A::Vector{U}) where T <: RingElem, U <: RingElem
(S::PolyRing{T})(A::Vector{U}) where T <: RingElem, U <: Integer

Construct the polynomial in the ring S with the given array of coefficients, i.e. where A[1] is the constant coefficient.

A third way of constructing polynomials is to construct them directly without creating the polynomial ring.

polynomial(R::Ring, arr::Vector{T}, var::String="x"; cached::Bool=true)

Given an array of coefficients construct the polynomial with those coefficients over the given ring and with the given variable.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> f = x^3 + 3x + 21
x^3 + 3*x + 21

julia> g = (x + 1)*y^2 + 2x + 1
(x + 1)*y^2 + 2*x + 1

julia> R()
0

julia> S(1)
1

julia> S(y)
y

julia> S(x)
x

julia> S, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> f = S(Rational{BigInt}[2, 3, 1])
x^2 + 3*x + 2

julia> g = S(BigInt[1, 0, 4])
4*x^2 + 1

julia> h = S([4, 7, 2, 9])
9*x^3 + 2*x^2 + 7*x + 4

julia> p = polynomial(ZZ, [1, 2, 3])
3*x^2 + 2*x + 1

julia> f = polynomial(ZZ, [1, 2, 3], "y")
3*y^2 + 2*y + 1

Similar and zero

Another way of constructing polynomials is to construct one similar to an existing polynomial using either similar or zero.

similar(x::MyPoly{T}, R::Ring=base_ring(x)) where T <: RingElem
zero(x::MyPoly{T}, R::Ring=base_ring(x)) where T <: RingElem

Construct the zero polynomial with the same variable as the given polynomial with coefficients in the given ring. Both functions behave the same way for polynomials.

similar(x::MyPoly{T}, R::Ring, var::String=String(var(parent(x)))) where T <: RingElem
similar(x::MyPoly{T}, var::String=String(var(parent(x)))) where T <: RingElem
zero(x::MyPoly{T}, R::Ring, var::String=String(var(parent(x)))) where T <: RingElem
zero(x::MyPoly{T}, var::String=String(var(parent(x)))) where T <: RingElem

Construct the zero polynomial with the given variable and coefficients in the given ring, if specified, and in the coefficient ring of the given polynomial otherwise.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> f = 1 + 2x + 3x^2
3*x^2 + 2*x + 1

julia> g = similar(f)
0

julia> h = similar(f, QQ)
0

julia> k = similar(f, QQ, "y")
0

Functions for types and parents of polynomial rings

base_ring(R::PolyRing)
base_ring(a::PolyElem)

Return the coefficient ring of the given polynomial ring or polynomial.

parent(a::NCRingElement)

Return the polynomial ring of the given polynomial..

characteristic(R::NCRing)

Return the characteristic of the given polynomial ring. If the characteristic is not known, an exception is raised.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> U = base_ring(S)
Univariate Polynomial Ring in x over Integers

julia> V = base_ring(y + 1)
Univariate Polynomial Ring in x over Integers

julia> T = parent(y + 1)
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers

Euclidean polynomial rings

For polynomials over a field, the Euclidean Ring Interface is implemented.

mod(f::PolyElem, g::PolyElem)
divrem(f::PolyElem, g::PolyElem)
div(f::PolyElem, g::PolyElem)
mulmod(f::PolyElem, g::PolyElem, m::PolyElem)
powermod(f::PolyElem, e::Int, m::PolyElem)
invmod(f::PolyElem, m::PolyElem)
divides(f::PolyElem, g::PolyElem)
remove(f::PolyElem, p::PolyElem)
valuation(f::PolyElem, p::PolyElem)
gcd(f::PolyElem, g::PolyElem)
lcm(f::PolyElem, g::PolyElem)
gcdx(f::PolyElem, g::PolyElem)
gcdinv(f::PolyElem, g::PolyElem)

Examples

julia> R, x = PolynomialRing(QQ, "x")
(Univariate Polynomial Ring in x over Rationals, x)

julia> S = ResidueRing(R, x^3 + 3x + 1)
Residue ring of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1

julia> T, y = PolynomialRing(S, "y")
(Univariate Polynomial Ring in y over Residue ring of Univariate Polynomial Ring in x over Rationals modulo x^3 + 3*x + 1, y)

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

julia> g = (5*x^2 + 2*x + 1)*y^2 + 2x*y + x + 1
(5*x^2 + 2*x + 1)*y^2 + 2*x*y + x + 1

julia> h = (3*x^3 + 2*x^2 + x + 7)*y^5 + 2x*y + 1
(2*x^2 - 8*x + 4)*y^5 + 2*x*y + 1

julia> invmod(f, g)
(707//3530*x^2 + 2151//1765*x + 123//3530)*y - 178//1765*x^2 - 551//3530*x + 698//1765

julia> mulmod(f, g, h)
(-30*x^2 - 43*x - 9)*y^3 + (-7*x^2 - 23*x - 7)*y^2 + (4*x^2 - 10*x - 3)*y + x^2 - 2*x

julia> powermod(f, 3, h)
(69*x^2 + 243*x + 79)*y^3 + (78*x^2 + 180*x + 63)*y^2 + (27*x^2 + 42*x + 18)*y + 3*x^2 + 3*x + 2

julia> h = mod(f, g)
(3*x^2 + x + 2)*y + x^2 + 1

julia> q, r = divrem(f, g)
(0, (3*x^2 + x + 2)*y + x^2 + 1)

julia> div(g, f)
(-5//11*x^2 + 2//11*x + 6//11)*y - 13//121*x^2 - 3//11*x - 78//121

julia> d = gcd(f*h, g*h)
y + 1//11*x^2 + 6//11

julia> k = gcdinv(f, h)
(y + 1//11*x^2 + 6//11, 0)

julia> m = lcm(f, h)
(-14*x^2 - 23*x - 2)*y - 4*x^2 - 5*x + 1

julia> flag, q = divides(g^2, g)
(true, (5*x^2 + 2*x + 1)*y^2 + 2*x*y + x + 1)

julia> valuation(3g^3, g) == 3
true

julia> val, q = remove(5g^3, g)
(3, 5)

julia> r, s, t = gcdx(g, h)
(1, 311//3530*x^2 - 2419//3530*x + 947//1765, (707//3530*x^2 + 2151//1765*x + 123//3530)*y - 178//1765*x^2 - 551//3530*x + 698//1765)

Functions in the Euclidean Ring interface are supported over residue rings that are not fields, except that if an impossible inverse is encountered during the computation an error is thrown.

Polynomial functions

Basic functionality

All basic ring functionality is provided for polynomials. The most important such functions are the following.

zero(R::PolyRing)
one(R::PolyRing)
iszero(a::PolyElem)
isone(a::PolyElem)
divexact(a::T, b::T) where T <: PolyElem

All functions in the polynomial interface are provided. The most important are the following.

var(S::PolyRing)
symbols(S::PolyRing{T}) where T <: RingElem

Return a symbol or length 1 array of symbols, respectively, specifying the variable of the polynomial ring. This symbol is converted to a string when printing polynomials in that ring.

In addition, the following basic functions are provided.

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

Return the modulus of the coefficients of the given polynomial.

leading_coefficientMethod
leading_coefficient(a::PolynomialElem)

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.

leading_coefficient(p::MPolyElem)

Return the leading coefficient of the polynomial $p$.

trailing_coefficientMethod
trailing_coefficient(a::PolynomialElem)

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

trailing_coefficient(p::MPolyElem)

Return the trailing coefficient of the polynomial $p$, i.e. the coefficient of the last nonzero term, or zero if the polynomial is zero.

constant_coefficientMethod
constant_coefficient(a::PolynomialElem)

Return the constant coefficient of the given polynomial. If the polynomial is the zero polynomial, the function will return zero.

set_coefficient!Method
set_coefficient!(c::PolynomialElem{T}, n::Int, a::T) where T <: RingElement
set_coefficient!(c::PolynomialElem{T}, n::Int, a::U) where {T <: RingElement, U <: Integer}

Set the coefficient of degree $n$ to $a$.

tailMethod
tail(a::PolynomialElem)

Return the tail of the given polynomial, i.e. the polynomial without its leading term (if any).

genMethod
gen(a::MPolyRing{T}, i::Int) where {T <: RingElement}

Return the $i$-th generator (variable) of the given polynomial ring.

gen(R::AbsSeriesRing{T}) where T <: RingElement

Return the generator of the power series ring, i.e. $x + O(x^n)$ where $n$ is the precision of the power series ring $R$.

gen(M::SubQuo{T}, i::Int) where T

Return the ith generator of M.

source
is_genMethod
is_gen(x::MPoly{T}) where {T <: RingElement}

Return true if the given polynomial is a generator (variable) of the polynomial ring it belongs to.

is_gen(a::PolynomialElem)

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

is_monicMethod
is_monic(a::PolynomialElem)

Return true if the given polynomial is monic, i.e. has leading coefficient equal to one, otherwise return false.

is_squareMethod
is_square(f::PolyElem{T}) where T <: RingElement

Return true if $f$ is a perfect square.

is_square(a::FracElem{T}) where T <: RingElem

Return true if $a$ is a square.

lengthMethod
length(a::PolynomialElem)

Return the length of the polynomial. The length of a univariate polynomial is defined to be the number of coefficients in its dense representation, including zero coefficients. Thus naturally the zero polynomial has length zero and additionally for nonzero polynomials the length is one more than the degree. (Note that the leading coefficient will always be nonzero.)

degreeMethod
degree(a::PolynomialElem)

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

is_monomialMethod
is_monomial(a::PolynomialElem)

Return true if the given polynomial is a monomial.

is_monomial(x::AbstractAlgebra.MPolyElem)

Return true if the given polynomial has precisely one term whose coefficient is one.

is_monomial_recursiveMethod
is_monomial_recursive(a::PolynomialElem)

Return true if the given polynomial is a monomial. This function is recursive, with all scalar types returning true.

is_termMethod
is_term(a::PolynomialElem)

Return true if the given polynomial has one term.

is_term(x::MPoly)

Return true if the given polynomial has precisely one term.

is_term_recursiveMethod
is_term_recursive(a::PolynomialElem)

Return true if the given polynomial has one term. This function is recursive, with all scalar types returning true.

is_constantMethod
is_constant(a::PolynomialElem)

Return true if a is a degree zero polynomial or the zero polynomial, i.e. a constant polynomial.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> T, z = PolynomialRing(QQ, "z")
(Univariate Polynomial Ring in z over Rationals, z)

julia> U = ResidueRing(ZZ, 17)
Residue ring of Integers modulo 17

julia> V, w = PolynomialRing(U, "w")
(Univariate Polynomial Ring in w over Residue ring of Integers modulo 17, w)

julia> var(R)
:x

julia> symbols(R)
1-element Vector{Symbol}:
 :x

julia> a = zero(S)
0

julia> b = one(S)
1

julia> isone(b)
true

julia> c = BigInt(1)//2*z^2 + BigInt(1)//3
1//2*z^2 + 1//3

julia> d = x*y^2 + (x + 1)*y + 3
x*y^2 + (x + 1)*y + 3

julia> f = leading_coefficient(d)
x

julia> y = gen(S)
y

julia> g = is_gen(w)
true

julia> divexact((2x + 1)*(x + 1), (x + 1))
2*x + 1

julia> m = is_unit(b)
true

julia> n = degree(d)
2

julia> r = modulus(w)
17

julia> is_term(2y^2)
true

julia> is_monomial(y^2)
true

julia> is_monomial_recursive(x*y^2)
true

julia> is_monomial(x*y^2)
false

julia> S, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> f = x^3 + 3x + 1
x^3 + 3*x + 1

julia> g = S(BigInt[1, 2, 0, 1, 0, 0, 0]);

julia> n = length(f)
4

julia> c = coeff(f, 1)
3

julia> g = set_coefficient!(g, 2, ZZ(11))
x^3 + 11*x^2 + 2*x + 1

julia> g = set_coefficient!(g, 7, ZZ(4))
4*x^7 + x^3 + 11*x^2 + 2*x + 1

Iterators

An iterator is provided to return the coefficients of a univariate polynomial. The iterator is called coefficients and allows iteration over the coefficients, starting with the term of degree zero (if there is one). Note that coefficients of each degree are given, even if they are zero. This is best illustrated by example.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> f = x^2 + 2
x^2 + 2

julia> C = collect(coefficients(f))
3-element Vector{BigInt}:
 2
 0
 1

julia> for c in coefficients(f)
          println(c)
       end
2
0
1

Truncation

truncateMethod
truncate(a::PolynomialElem, n::Int)

Return $a$ truncated to $n$ terms, i.e. the remainder upon division by $x^n$.

mullowMethod
mullow(a::PolyElem{T}, b::PolyElem{T}, n::Int) where T <: RingElement

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

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

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

julia> h = truncate(f, 1)
3

julia> k = mullow(f, g, 4)
(x^2 + x)*y^3 + (x^4 + 3*x^2 + 4*x + 1)*y^2 + (x^4 + x^3 + 2*x^2 + 7*x + 5)*y + 3*x^3 + 6*x + 6

Reversal

reverseMethod
reverse(x::PolynomialElem, 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().

reverseMethod
reverse(x::PolynomialElem)

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.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

julia> g = reverse(f, 7)
3*y^6 + (x + 1)*y^5 + x*y^4

julia> h = reverse(f)
3*y^2 + (x + 1)*y + x

Shifting

shift_leftMethod
shift_left(f::PolynomialElem, n::Int)

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

shift_rightMethod
shift_right(f::PolynomialElem, n::Int)

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

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

julia> g = shift_left(f, 7)
x*y^9 + (x + 1)*y^8 + 3*y^7

julia> h = shift_right(f, 2)
x

Inflation and deflation

deflationMethod
deflation(p::PolyElem)

Return a tuple (shift, defl) where shift is the exponent of the trailing term of $p$ and defl is the gcd of the distance between the exponents of the nonzero terms of $p$. If $p = 0$, both shift and defl will be zero.

inflateMethod
inflate(f::PolyElem, shift::Int64, n::Int64) -> PolyElem

Given a polynomial $f$ in $x$, return $f(x^n)*x^j$, i.e. multiply all exponents by $n$ and shift $f$ left by $j$.

inflateMethod
inflate(f::PolyElem, n::Int64) -> PolyElem

Given a polynomial $f$ in $x$, return $f(x^n)$, i.e. multiply all exponents by $n$.

deflateMethod
deflate(f::PolyElem, shift::Int64, n::Int64) -> PolyElem

Given a polynomial $g$ in $x^n$ such that f = g(x)*x^{shift}, write $f$ as a polynomial in $x$, i.e. divide all exponents of $g$ by $n$.

deflateMethod
deflate(f::PolyElem, n::Int64) -> PolyElem

Given a polynomial $f$ in $x^n$, write it as a polynomial in $x$, i.e. divide all exponents by $n$.

deflateMethod
deflate(x::PolyElem) -> PolyElem, Int

Deflate the polynomial $f$ maximally, i.e. find the largest $n$ s.th. $f$ can be deflated by $n$, i.e. $f$ is actually a polynomial in $x^n$. Return $g, n$ where $g$ is the deflation of $f$.

Square root

sqrtMethod
sqrt(a::Generic.PuiseuxSeriesElem{T}; check::Bool=true) where T <: RingElement

Return the square root of the given Puiseux series $a$. By default the function will throw an exception if the input is not square. If check=false this test is omitted.

Base.sqrt(f::PolyElem{T}; check::Bool=true) where T <: RingElement

Return the square root of $f$. By default the function checks the input is square and raises an exception if not. If check=false this check is omitted.

Examples

R, x = PolynomialRing(ZZ, "x")
g = x^2+6*x+1
sqrt(g^2)

Change of base ring

change_base_ringMethod
change_base_ring(R::Ring, p::PolyElem{<: RingElement}; parent::PolyRing)

Return the polynomial obtained by coercing the non-zero coefficients of p into R.

If the optional parent keyword is provided, the polynomial will be an element of parent. The caching of the parent object can be controlled via the cached keyword argument.

change_coefficient_ringMethod
change_coefficient_ring(R::Ring, p::PolyElem{<: RingElement}; parent::PolyRing)

Return the polynomial obtained by coercing the non-zero coefficients of p into R.

If the optional parent keyword is provided, the polynomial will be an element of parent. The caching of the parent object can be controlled via the cached keyword argument.

map_coefficientsMethod
map_coefficients(f, p::PolyElem{<: RingElement}; cached::Bool=true, parent::PolyRing)

Transform the polynomial p by applying f on each non-zero coefficient.

If the optional parent keyword is provided, the polynomial will be an element of parent. The caching of the parent object can be controlled via the cached keyword argument.

Examples

R, x = PolynomialRing(ZZ, "x")
g = x^3+6*x + 1
change_base_ring(GF(2), g)
change_coefficient_ring(GF(2), 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.

pseudoremMethod
pseudorem(f::PolyElem{T}, g::PolyElem{T}) where T <: RingElement

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

pseudodivremMethod
pseudodivrem(f::PolyElem{T}, g::PolyElem{T}) where T <: RingElement

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

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

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

julia> h = pseudorem(f, g)
x^7 + 3*x^5 + 2*x^4 + x^3 + 5*x^2 + 4*x + 1

julia> q, r = pseudodivrem(f, g)
((x^2 + x)*y - x^4 - x^2 + 1, x^7 + 3*x^5 + 2*x^4 + x^3 + 5*x^2 + 4*x + 1)

Content and primitive part

contentMethod
content(a::PolyElem)

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

primpartMethod
primpart(a::PolyElem)

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

Examples

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

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

n = content(k)
p = primpart(k*(x^2 + 1))

Evaluation, composition and substitution

evaluateMethod
evaluate(a::PolyElem, b::T) where T <: RingElement

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

evaluateMethod
evaluate(a::PolyElem, b::T) where T <: RingElement

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

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

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

substMethod
subst(f::PolyElem{T}, a::Any) where T <: RingElement

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

We also overload the functional notation so that the polynomial $f$ can be evaluated at $a$ by writing $f(a)$.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)


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

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

julia> M = R[x + 1 2x; x - 3 2x - 1]
[x + 1       2*x]
[x - 3   2*x - 1]

julia> k = evaluate(f, 3)
12*x + 6

julia> m = evaluate(f, x^2 + 2x + 1)
x^5 + 4*x^4 + 7*x^3 + 7*x^2 + 4*x + 4

julia> n = compose(f, g)
(x^3 + 2*x^2 + x)*y^2 + (2*x^5 + 2*x^4 + 4*x^3 + 9*x^2 + 6*x + 1)*y + x^7 + 4*x^5 + 5*x^4 + 5*x^3 + 10*x^2 + 8*x + 5

julia> p = subst(f, M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

julia> q = f(M)
[3*x^3 - 3*x^2 + 3*x + 4       6*x^3 + 2*x^2 + 2*x]
[3*x^3 - 8*x^2 - 2*x - 3   6*x^3 - 8*x^2 + 2*x + 2]

julia> r = f(23)
552*x + 26

Derivative and integral

derivativeMethod
derivative(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the derivative of the given Puiseux series $a$.

derivative(x::spoly{T}, n::Int) where T <: Nemo.RingElem

Return the derivative of $x$ with respect to the variable of index $n$.

derivative(x::spoly{T}, v::spoly{T}) where T <: Nemo.RingElem

Return the derivative of $x$ with respect to the variable $v$.

derivative(a::PolynomialElem)

Return the derivative of the polynomial $a$.

derivative(f::AbsSeriesElem{T})

Return the derivative of the power series $f$.

derivative(f::RelSeriesElem{T})

Return the derivative of the power series $f$.

julia> R, x = PowerSeriesRing(QQ, 10, "x")
(Univariate power series ring in x over Rationals, x + O(x^11))

julia> f = 2 + x + 3x^3
2 + x + 3*x^3 + O(x^10)

julia> derivative(f)
1 + 9*x^2 + O(x^9)
derivative(f::AbstractAlgebra.MPolyElem{T}, j::Int) where {T <: RingElement}

Return the partial derivative of f with respect to $j$-th variable of the polynomial ring.

derivative(f::AbstractAlgebra.MPolyElem{T}, x::AbstractAlgebra.MPolyElem{T}) where T <: RingElement

Return the partial derivative of f with respect to x. The value x must be a generator of the polynomial ring of f.

integralMethod
integral(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the integral of the given Puiseux series $a$.

integral(f::RelSeriesElem{T}) -> RelSeriesElem

Return the integral of the power series $f$.

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

Return the integral of the polynomial $x$.

integral(f::AbsSeriesElem{T})

Return the integral of the power series $f$.

integral(f::RelSeriesElem{T})

Return the integral of the power series $f$.

julia> R, x = PowerSeriesRing(QQ, 10, "x")
(Univariate power series ring in x over Rationals, x + O(x^11))

julia> f = 2 + x + 3x^3
2 + x + 3*x^3 + O(x^10)

julia> integral(f)
2*x + 1//2*x^2 + 3//4*x^4 + O(x^11)

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> T, z = PolynomialRing(QQ, "z")
(Univariate Polynomial Ring in z over Rationals, z)

julia> U = ResidueRing(T, z^3 + 3z + 1)
Residue ring of Univariate Polynomial Ring in z over Rationals modulo z^3 + 3*z + 1

julia> V, w = PolynomialRing(U, "w")
(Univariate Polynomial Ring in w over Residue ring of Univariate Polynomial Ring in z over Rationals modulo z^3 + 3*z + 1, w)

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

julia> g = (z^2 + 2z + 1)*w^2 + (z + 1)*w - 2z + 4
(z^2 + 2*z + 1)*w^2 + (z + 1)*w - 2*z + 4

julia> h = derivative(f)
2*x*y + x + 1

julia> k = integral(g)
(1//3*z^2 + 2//3*z + 1//3)*w^3 + (1//2*z + 1//2)*w^2 + (-2*z + 4)*w

Resultant and discriminant

sylvester_matrixMethod
sylvester_matrix(p::PolyElem, q::PolyElem)

Return the sylvester matrix of the given polynomials.

resultantMethod
resultant(p::PolyElem{T}, q::PolyElem{T}) where T <: RingElement

Return the resultant of the given polynomials.

resxMethod
resx(a::PolyElem{T}, b::PolyElem{T}) where T <: RingElement

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

discriminantMethod
discriminant(a::PolyElem)

Return the discriminant of the given polynomial.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

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

julia> S = sylvester_matrix(f, g)
[    3*x           x + 1               3]
[6*x + 6   x^3 + 2*x + 2               0]
[      0         6*x + 6   x^3 + 2*x + 2]

julia> h = resultant(f, g)
3*x^7 + 6*x^5 - 6*x^3 + 96*x^2 + 192*x + 96

julia> k = discriminant(f)
x^2 - 34*x + 1

Newton representation

monomial_to_newton!Method
monomial_to_newton!(P::Vector{T}, roots::Vector{T}) where T <: RingElement

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.

newton_to_monomial!Method
newton_to_monomial!(P::Vector{T}, roots::Vector{T}) where T <: RingElement

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

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

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

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

julia> roots = [R(1), R(2), R(3)]
3-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
 1
 2
 3

julia> monomial_to_newton!(g.coeffs, roots)

julia> newton_to_monomial!(g.coeffs, roots)

Roots

rootsMethod
roots(f::PolyElem)

Returns the roots of the polynomial f in the base ring of f as an array.

rootsMethod
roots(f::PolyElem, R::Field)

Returns the roots of the polynomial f in the field R as an array.

Interpolation

interpolateMethod
interpolate(S::PolyRing, x::Vector{T}, y::Vector{T}) where T <: RingElement

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$. If no such polynomial exists, an exception is raised.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> xs = [R(1), R(2), R(3), R(4)]
4-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
 1
 2
 3
 4

julia> ys = [R(1), R(4), R(9), R(16)]
4-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
 1
 4
 9
 16

julia> f = interpolate(S, xs, ys)
y^2

Power sums

polynomial_to_power_sumsMethod
polynomial_to_power_sums(f::PolyElem{T}, n::Int=degree(f)) where T <: RingElement -> Vector{T}

Uses Newton (or Newton-Girard) formulas to compute the first $n$ sums of powers of the roots of $f$ from the coefficients of $f$, starting with the sum of (first powers of) the roots. The input polynomial must be monic, at least degree $1$ and have nonzero constant coefficient.

power_sums_to_polynomialMethod
power_sums_to_polynomial(P::Vector{T};
                 parent::AbstractAlgebra.PolyRing{T}=

AbstractAlgebra.PolyRing(parent(P[1])) where T <: RingElement -> PolyElem{T}

Uses the Newton (or Newton-Girard) identities to obtain the polynomial with given sums of powers of roots. The list must be nonempty and contain degree(f) entries where $f$ is the polynomial to be recovered. The list must start with the sum of first powers of the roots.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> f = x^4 - 2*x^3 + 10*x^2 + 7*x - 5
x^4 - 2*x^3 + 10*x^2 + 7*x - 5

julia> V = polynomial_to_power_sums(f)
4-element Vector{BigInt}:
   2
 -16
 -73
  20

julia> power_sums_to_polynomial(V)
x^4 - 2*x^3 + 10*x^2 + 7*x - 5

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.

chebyshev_tMethod
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))$.

chebyshev_uMethod
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)$.

Examples

julia> R, x = PolynomialRing(ZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> S, y = PolynomialRing(R, "y")
(Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Integers, y)

julia> f = chebyshev_t(20, y)
524288*y^20 - 2621440*y^18 + 5570560*y^16 - 6553600*y^14 + 4659200*y^12 - 2050048*y^10 + 549120*y^8 - 84480*y^6 + 6600*y^4 - 200*y^2 + 1

julia> g = chebyshev_u(15, y)
32768*y^15 - 114688*y^13 + 159744*y^11 - 112640*y^9 + 42240*y^7 - 8064*y^5 + 672*y^3 - 16*y

Random generation

One may generate random polynomials with degrees in a given range. Additional parameters are used to construct coefficients as elements of the coefficient ring.

rand(R::PolyRing, deg_range::UnitRange{Int}, v...)
rand(R::PolyRing, deg::Int, v...)

Examples

R, x = PolynomialRing(ZZ, "x")
f = rand(R, -1:3, -10:10)

S, y = PolynomialRing(GF(7), "y")
g = rand(S, 2:2)

U, z = PolynomialRing(R, "z")
h = rand(U, 3:3, -1:2, -10:10)