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 PolyRingElem{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.
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.
AbstractAlgebra.polynomial_ring — Methodpolynomial_ring(R::NCRing, s::VarName = :x; cached::Bool = true)Given a base ring R and symbol/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 depends 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.
Examples
julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, :y)
(Univariate polynomial ring in y over univariate polynomial ring, y)A shorthand version of this function is provided: given a base ring R, we abbreviate the constructor as follows.
R[:x]Here are some examples of creating polynomial rings and their associated generators.
Examples
julia> T, z = QQ["z"]
(Univariate polynomial ring in z over rationals, z)
julia> U, x = polynomial_ring(ZZ)
(Univariate polynomial ring in x over integers, x)All of the examples here are generic polynomial rings, but specialised implementations of polynomial rings provided by external modules will also usually provide a polynomial_ring 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 polynomial_ring 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 <: RingElementFor 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 <: IntegerConstruct 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::VarName=: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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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 = polynomial_ring(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 + 1Similar 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 <: RingElemConstruct 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::VarName=var(parent(x))) where T <: RingElem
similar(x::MyPoly{T}, var::VarName=var(parent(x))) where T <: RingElem
zero(x::MyPoly{T}, R::Ring, var::VarName=var(parent(x))) where T <: RingElem
zero(x::MyPoly{T}, var::VarName=var(parent(x))) where T <: RingElemConstruct 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 = polynomial_ring(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")
0Functions for types and parents of polynomial rings
base_ring(R::PolyRing)
base_ring(a::PolyRingElem)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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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 ringEuclidean polynomial rings
For polynomials over a field, the Euclidean Ring Interface is implemented.
mod(f::PolyRingElem, g::PolyRingElem)
divrem(f::PolyRingElem, g::PolyRingElem)
div(f::PolyRingElem, g::PolyRingElem)mulmod(f::PolyRingElem, g::PolyRingElem, m::PolyRingElem)
powermod(f::PolyRingElem, e::Int, m::PolyRingElem)
invmod(f::PolyRingElem, m::PolyRingElem)divides(f::PolyRingElem, g::PolyRingElem)
remove(f::PolyRingElem, p::PolyRingElem)
valuation(f::PolyRingElem, p::PolyRingElem)gcd(f::PolyRingElem, g::PolyRingElem)
lcm(f::PolyRingElem, g::PolyRingElem)
gcdx(f::PolyRingElem, g::PolyRingElem)
gcdinv(f::PolyRingElem, g::PolyRingElem)Examples
julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)
julia> S, = residue_ring(R, x^3 + 3x + 1);
julia> T, y = polynomial_ring(S, "y")
(Univariate polynomial ring in y over residue ring, 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::PolyRingElem)
isone(a::PolyRingElem)divexact(a::T, b::T) where T <: PolyRingElemAll functions in the polynomial interface are provided. The most important are the following.
var(S::PolyRing)
symbols(S::PolyRing{T}) where T <: RingElemReturn 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.
AbstractAlgebra.modulus — Methodmodulus(a::PolyRingElem{T}) where {T <: ResElem}Return the modulus of the coefficients of the given polynomial.
AbstractAlgebra.leading_coefficient — Methodleading_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::MPolyRingElem)Return the leading coefficient of the polynomial $p$.
AbstractAlgebra.trailing_coefficient — Methodtrailing_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::MPolyRingElem)Return the trailing coefficient of the polynomial $p$, i.e. the coefficient of the last nonzero term, or zero if the polynomial is zero.
AbstractAlgebra.constant_coefficient — Methodconstant_coefficient(a::PolynomialElem)Return the constant coefficient of the given polynomial. If the polynomial is the zero polynomial, the function will return zero.
AbstractAlgebra.set_coefficient! — Methodset_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$.
AbstractAlgebra.tail — Methodtail(a::PolynomialElem)Return the tail of the given polynomial, i.e. the polynomial without its leading term (if any).
AbstractAlgebra.gen — Methodgen(a::MPolyRing{T}, i::Int) where {T <: RingElement}Return the $i$-th generator (variable) of the given polynomial ring.
gen(R::AbsPowerSeriesRing{T}) where T <: RingElementReturn the generator of the power series ring, i.e. $x + O(x^n)$ where $n$ is the precision of the power series ring $R$.
AbstractAlgebra.is_gen — Methodis_gen(a::PolynomialElem)Return true if the given polynomial is the constant generator of its polynomial ring, otherwise return false.
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.
AbstractAlgebra.is_monic — Methodis_monic(a::PolynomialElem)Return true if the given polynomial is monic, i.e. has leading coefficient equal to one, otherwise return false.
AbstractAlgebra.is_square — Methodis_square(f::PolyRingElem{T}) where T <: RingElementReturn true if $f$ is a perfect square.
is_square(a::FracElem{T}) where T <: RingElemReturn true if $a$ is a square.
Base.length — Methodlength(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.)
AbstractAlgebra.degree — Methoddegree(a::PolynomialElem)Return the degree of the given polynomial. This is defined to be one less than the length, even for constant polynomials.
AbstractAlgebra.is_monomial — Methodis_monomial(a::PolynomialElem)Return true if the given polynomial is a monomial.
is_monomial(x::MPolyRingElem)Return true if the given polynomial has precisely one term whose coefficient is one.
AbstractAlgebra.is_monomial_recursive — Methodis_monomial_recursive(a::PolynomialElem)Return true if the given polynomial is a monomial. This function is recursive, with all scalar types returning true.
AbstractAlgebra.is_term — Methodis_term(a::PolynomialElem)Return true if the given polynomial has one term.
is_term(x::MPolyRingElem)Return true if the given polynomial has precisely one term.
AbstractAlgebra.is_term_recursive — Methodis_term_recursive(a::PolynomialElem)Return true if the given polynomial has one term. This function is recursive, with all scalar types returning true.
AbstractAlgebra.is_constant — Methodis_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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, y)
julia> T, z = polynomial_ring(QQ, "z")
(Univariate polynomial ring in z over rationals, z)
julia> U, = residue_ring(ZZ, 17);
julia> V, w = polynomial_ring(U, "w")
(Univariate polynomial ring in w over residue ring, 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 = polynomial_ring(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 + 1Iterators
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 = polynomial_ring(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
1Truncation
Base.truncate — Methodtruncate(a::PolynomialElem, n::Int)Return $a$ truncated to $n$ terms, i.e. the remainder upon division by $x^n$.
AbstractAlgebra.mullow — Methodmullow(a::PolyRingElem{T}, b::PolyRingElem{T}, n::Int) where T <: RingElementReturn $a\times b$ truncated to $n$ terms.
Examples
julia> R, x = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
Base.reverse — Methodreverse(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().
Base.reverse — Methodreverse(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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.shift_left — Methodshift_left(f::PolynomialElem, n::Int)Return the polynomial $f$ shifted left by $n$ terms, i.e. multiplied by $x^n$.
AbstractAlgebra.shift_right — Methodshift_right(f::PolynomialElem, n::Int)Return the polynomial $f$ shifted right by $n$ terms, i.e. divided by $x^n$.
Examples
julia> R, x = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.deflation — Methoddeflation(p::PolyRingElem)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.
AbstractAlgebra.inflate — Methodinflate(f::PolyRingElem, shift::Int64, n::Int64) -> PolyRingElemGiven a polynomial $f$ in $x$, return $f(x^n)*x^j$, i.e. multiply all exponents by $n$ and shift $f$ left by $j$.
AbstractAlgebra.inflate — Methodinflate(f::PolyRingElem, n::Int64) -> PolyRingElemGiven a polynomial $f$ in $x$, return $f(x^n)$, i.e. multiply all exponents by $n$.
AbstractAlgebra.deflate — Methoddeflate(f::PolyRingElem, shift::Int64, n::Int64) -> PolyRingElemGiven 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$.
AbstractAlgebra.deflate — Methoddeflate(f::PolyRingElem, n::Int64) -> PolyRingElemGiven a polynomial $f$ in $x^n$, write it as a polynomial in $x$, i.e. divide all exponents by $n$.
AbstractAlgebra.deflate — Methoddeflate(x::PolyRingElem) -> PolyRingElem, IntDeflate 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
Base.sqrt — MethodBase.sqrt(f::PolyRingElem{T}; check::Bool=true) where T <: RingElementReturn 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.
sqrt(a::Generic.PuiseuxSeriesElem{T}; check::Bool=true) where T <: RingElementReturn 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.
Examples
R, x = polynomial_ring(ZZ, "x")
g = x^2+6*x+1
sqrt(g^2)Change of base ring
AbstractAlgebra.change_base_ring — Methodchange_base_ring(R::Ring, p::PolyRingElem{<: 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.
AbstractAlgebra.change_coefficient_ring — Methodchange_coefficient_ring(R::Ring, p::PolyRingElem{<: 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.
AbstractAlgebra.map_coefficients — Methodmap_coefficients(f, p::PolyRingElem{<: 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 = polynomial_ring(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.
AbstractAlgebra.pseudorem — Methodpseudorem(f::PolyRingElem{T}, g::PolyRingElem{T}) where T <: RingElementReturn the pseudoremainder of $f$ divided by $g$. If $g = 0$ we throw a DivideError().
AbstractAlgebra.pseudodivrem — Methodpseudodivrem(f::PolyRingElem{T}, g::PolyRingElem{T}) where T <: RingElementReturn 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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.content — Methodcontent(a::PolyRingElem)Return the content of $a$, i.e. the greatest common divisor of its coefficients.
AbstractAlgebra.primpart — Methodprimpart(a::PolyRingElem)Return the primitive part of $a$, i.e. the polynomial divided by its content.
Examples
R, x = polynomial_ring(ZZ, "x")
S, y = polynomial_ring(R, "y")
k = x*y^2 + (x + 1)*y + 3
n = content(k)
p = primpart(k*(x^2 + 1))Evaluation, composition and substitution
AbstractAlgebra.evaluate — Methodevaluate(a::PolyRingElem, b::T) where T <: RingElementEvaluate the polynomial expression $a$ at the value $b$ and return the result.
AbstractAlgebra.compose — Methodcompose(f::PolyRingElem, g::PolyRingElem; inner)Compose the polynomial $a$ with the polynomial $b$ and return the result.
- If
inner = :right, thenf(g)is returned. - If
inner = :left, theng(f)is returned.
AbstractAlgebra.subst — Methodsubst(f::PolyRingElem{T}, a::Any) where T <: RingElementEvaluate 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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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; inner = :second)
(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
AbstractAlgebra.derivative — Methodderivative(a::PolynomialElem)Return the derivative of the polynomial $a$.
derivative(f::AbsPowerSeriesRingElem{T})Return the derivative of the power series $f$.
derivative(f::RelPowerSeriesRingElem{T})Return the derivative of the power series $f$.
julia> R, x = power_series_ring(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::MPolyRingElem{T}, j::Int) where {T <: RingElement}Return the partial derivative of f with respect to $j$-th variable of the polynomial ring.
derivative(f::MPolyRingElem{T}, x::MPolyRingElem{T}) where T <: RingElementReturn the partial derivative of f with respect to x. The value x must be a generator of the polynomial ring of f.
derivative(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElementReturn the derivative of the given Puiseux series $a$.
AbstractAlgebra.integral — Methodintegral(x::PolyRingElem{T}) where {T <: Union{ResElem, FieldElement}}Return the integral of the polynomial $x$.
integral(f::AbsPowerSeriesRingElem{T})Return the integral of the power series $f$.
integral(f::RelPowerSeriesRingElem{T})Return the integral of the power series $f$.
julia> R, x = power_series_ring(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)integral(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElementReturn the integral of the given Puiseux series $a$.
Examples
julia> R, x = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, y)
julia> T, z = polynomial_ring(QQ, "z")
(Univariate polynomial ring in z over rationals, z)
julia> U, = residue_ring(T, z^3 + 3z + 1);
julia> V, w = polynomial_ring(U, "w")
(Univariate polynomial ring in w over residue ring, 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
AbstractAlgebra.sylvester_matrix — Methodsylvester_matrix(p::PolyRingElem, q::PolyRingElem)Return the sylvester matrix of the given polynomials.
AbstractAlgebra.resultant — Methodresultant(p::PolyRingElem{T}, q::PolyRingElem{T}) where T <: RingElementReturn the resultant of the given polynomials.
AbstractAlgebra.resx — Methodresx(a::PolyRingElem{T}, b::PolyRingElem{T}) where T <: RingElementReturn 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$.
AbstractAlgebra.discriminant — Methoddiscriminant(a::PolyRingElem)Return the discriminant of the given polynomial.
Examples
julia> R, x = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.monomial_to_newton! — Methodmonomial_to_newton!(P::Vector{T}, roots::Vector{T}) where T <: RingElementConverts 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.
AbstractAlgebra.newton_to_monomial! — Methodnewton_to_monomial!(P::Vector{T}, roots::Vector{T}) where T <: RingElementConverts 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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.Generic.roots — Methodroots(f::PolyRingElem)Returns the roots of the polynomial f in the base ring of f as an array.
AbstractAlgebra.Generic.roots — Methodroots(R::Field, f::PolyRingElem)Returns the roots of the polynomial f in the field R as an array.
Interpolation
AbstractAlgebra.interpolate — Methodinterpolate(S::PolyRing, x::Vector{T}, y::Vector{T}) where T <: RingElementGiven 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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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
AbstractAlgebra.polynomial_to_power_sums — Methodpolynomial_to_power_sums(f::PolyRingElem{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.
AbstractAlgebra.power_sums_to_polynomial — Methodpower_sums_to_polynomial(P::Vector{T};
parent::PolyRing{T}=PolyRing(parent(P[1])) where T <: RingElement -> PolyRingElem{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 = polynomial_ring(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 - 5Special 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.
AbstractAlgebra.chebyshev_t — Methodchebyshev_t(n::Int, x::PolyRingElem)Return the Chebyshev polynomial of the first kind $T_n(x)$, defined by $T_n(x) = \cos(n \cos^{-1}(x))$.
AbstractAlgebra.chebyshev_u — Methodchebyshev_u(n::Int, x::PolyRingElem)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 = polynomial_ring(ZZ, "x")
(Univariate polynomial ring in x over integers, x)
julia> S, y = polynomial_ring(R, "y")
(Univariate polynomial ring in y over univariate polynomial ring, 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::AbstractUnitRange{Int}, v...)
rand(R::PolyRing, deg::Int, v...)Examples
R, x = polynomial_ring(ZZ, "x")
f = rand(R, -1:3, -10:10)
S, y = polynomial_ring(GF(7), "y")
g = rand(S, 2:2)
U, z = polynomial_ring(R, "z")
h = rand(U, 3:3, -1:2, -10:10)Ring homomorphisms
AbstractAlgebra.hom — Methodhom(R::AbstractAlgebra.PolyRing, S::NCRing, [coeff_map,] image)Given a homomorphism coeff_map from C to S, where C is the coefficient ring of R, and given an element image of S, return the homomorphism from R to S whose restriction to C is coeff_map, and which sends the generator of R to image.
If no coefficient map is entered, invoke a canonical homomorphism of C to S, if such a homomorphism exists, and throw an error, otherwise.
Examples
julia> Zx, x = ZZ["x"];
julia> F = hom(Zx, Zx, x + 1);
julia> F(x^2)
x^2 + 2*x + 1
julia> Fp = GF(3); Fpy, y = Fp["y"];
julia> G = hom(Zx, Fpy, c -> Fp(c), y^3);
julia> G(5*x + 1)
2*y^3 + 1