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.

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

Return the modulus of the coefficients of the given polynomial.

source
AbstractAlgebra.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.

source
leading_coefficient(p::MPolyElem)

Return the leading coefficient of the polynomial $p$.

source
AbstractAlgebra.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.

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

source
AbstractAlgebra.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.

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

source
AbstractAlgebra.tailMethod
tail(a::PolynomialElem)

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

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

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

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

source
AbstractAlgebra.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.

source
is_gen(a::PolynomialElem)

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

source
AbstractAlgebra.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.

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

Return true if $f$ is a perfect square.

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

Return true if $a$ is a square.

source
Base.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.)

source
AbstractAlgebra.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.

source
AbstractAlgebra.is_monomialMethod
is_monomial(a::PolynomialElem)

Return true if the given polynomial is a monomial.

source
is_monomial(x::AbstractAlgebra.MPolyElem)

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

source
AbstractAlgebra.is_termMethod
is_term(a::PolynomialElem)

Return true if the given polynomial has one term.

source
is_term(x::MPoly)

Return true if the given polynomial has precisely one term.

source
AbstractAlgebra.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.

source
AbstractAlgebra.is_constantMethod
is_constant(a::PolynomialElem)

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

source

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

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

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

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

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

source

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

Base.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().

source
Base.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.

source

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

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

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

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

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

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

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

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

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

source

Square root

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

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

source

Examples

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

Change of base ring

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

source
AbstractAlgebra.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.

source
AbstractAlgebra.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.

source

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.

AbstractAlgebra.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().

source
AbstractAlgebra.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().

source

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

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

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

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

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

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

source
AbstractAlgebra.composeMethod
compose(a::PolyElem, b::PolyElem)

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

source
AbstractAlgebra.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.

source

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

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

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

source
derivative(a::PolynomialElem)

Return the derivative of the polynomial $a$.

source
derivative(f::AbsSeriesElem{T})

Return the derivative of the power series $f$.

source
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)
source
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.

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

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

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

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

Return the integral of the polynomial $x$.

source
integral(f::AbsSeriesElem{T})

Return the integral of the power series $f$.

source
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)
source

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

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

source

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

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

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

source

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

Interpolation

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

source

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

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

source
AbstractAlgebra.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.

source

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.

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

source
AbstractAlgebra.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)$.

source

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)