Ideal functionality
AbstractAlgebra.jl provides a module, implemented in src/generic/Ideal.jl
for ideals of a Euclidean domain (assuming the existence of a gcdx
function) or of a univariate or multivariate polynomial ring over the integers. Univariate and multivariate polynomial rings over other domains (other than fields) are not supported at this time.
Generic ideal types
AbstractAlgebra.jl provides a generic ideal type based on Julia arrays which is implemented in src/generic/Ideal.jl
.
These generic ideals have type Generic.Ideal{T}
where T
is the type of elements of the ring the ideals belong to. Internally they consist of a Julia array of generators and some additional fields for a parent object, etc. See the file src/generic/GenericTypes.jl
for details.
Parent objects of ideals have type Generic.IdealSet{T}
.
Abstract types
All ideal types belong to the abstract type Ideal{T}
and their parents belong to the abstract type Set
. This enables one to write generic functions that can accept any AbstractAlgebra ideal type.
Both the generic ideal type Generic.Ideal{T}
and the abstract type it belongs to, Ideal{T}
, are called Ideal
. The former is a (parameterised) concrete type for an ideal in the ring whose elements have type T
. The latter is an abstract type representing all ideal types in AbstractAlgebra.jl, whether generic or very specialised (e.g. supplied by a C library).
Ideal constructors
One may construct ideals in AbstractAlgebra.jl with the following constructor.
Generic.Ideal(R::Ring, V::Vector{T}) where T <: RingElement
Given a set of elements V
in the ring R
, construct the ideal of R
generated by the elements V
. Note that V
may be arbitrary, e.g. it can contain duplicates, zero entries or be empty.
Examples
julia> R, (x, y) = polynomial_ring(ZZ, [:x, :y]; internal_ordering=:degrevlex)
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])
julia> V = [3*x^2*y - 3*y^2, 9*x^2*y + 7*x*y]
2-element Vector{AbstractAlgebra.Generic.MPoly{BigInt}}:
3*x^2*y - 3*y^2
9*x^2*y + 7*x*y
julia> I = Generic.Ideal(R, V)
AbstractAlgebra.Generic.Ideal{AbstractAlgebra.Generic.MPoly{BigInt}}(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[7*x*y + 9*y^2, 243*y^3 - 147*y^2, x*y^2 + 36*y^3 - 21*y^2, x^2*y + 162*y^3 - 99*y^2])
julia> W = map(ZZ, [2, 5, 7])
3-element Vector{BigInt}:
2
5
7
julia> J = Generic.Ideal(ZZ, W)
AbstractAlgebra.Generic.Ideal{BigInt}(Integers, BigInt[1])
Ideal functions
Basic functionality
AbstractAlgebra.gens
— Methodgens(I::Ideal{T}) where T <: RingElement
Return a list of generators of the ideal I
in reduced form and canonicalised.
Examples
julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)
julia> V = [1 + 2x^2 + 3x^3, 5x^4 + 1, 2x - 1]
3-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
3*x^3 + 2*x^2 + 1
5*x^4 + 1
2*x - 1
julia> I = Generic.Ideal(R, V)
AbstractAlgebra.Generic.Ideal{AbstractAlgebra.Generic.Poly{BigInt}}(Univariate polynomial ring in x over integers, AbstractAlgebra.Generic.Poly{BigInt}[3, x + 1])
julia> gens(I)
2-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
3
x + 1
Arithmetic of Ideals
Ideals support addition, multiplication, scalar multiplication and equality testing of ideals.
Containment
Base.contains
— MethodBase.contains(I::Ideal{T}, J::Ideal{T}) where T <: RingElement
Return true
if the ideal J
is contained in the ideal I
.
Base.intersect
— Methodintersect(I::Ideal{T}, J::Ideal{T}) where T <: RingElement
Return the intersection of the ideals I
and J
.
Examples
julia> R, x = polynomial_ring(ZZ, :x)
(Univariate polynomial ring in x over integers, x)
julia> V = [1 + 2x^2 + 3x^3, 5x^4 + 1, 2x - 1]
3-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
3*x^3 + 2*x^2 + 1
5*x^4 + 1
2*x - 1
julia> W = [1 + 2x^2 + 3x^3, 5x^4 + 1]
2-element Vector{AbstractAlgebra.Generic.Poly{BigInt}}:
3*x^3 + 2*x^2 + 1
5*x^4 + 1
julia> I = Generic.Ideal(R, V)
AbstractAlgebra.Generic.Ideal{AbstractAlgebra.Generic.Poly{BigInt}}(Univariate polynomial ring in x over integers, AbstractAlgebra.Generic.Poly{BigInt}[3, x + 1])
julia> J = Generic.Ideal(R, W)
AbstractAlgebra.Generic.Ideal{AbstractAlgebra.Generic.Poly{BigInt}}(Univariate polynomial ring in x over integers, AbstractAlgebra.Generic.Poly{BigInt}[282, 3*x + 255, x^2 + 107])
julia> contains(J, I)
false
julia> contains(I, J)
true
julia> intersect(I, J) == J
true
Normal form
For ideal of polynomial rings it is possible to return the normal form of a polynomial with respect to an ideal.
AbstractAlgebra.Generic.normal_form
— Methodnormal_form(p::U, I::Ideal{U}) where {T <: RingElement, U <: Union{AbstractAlgebra.PolyRingElem{T}, AbstractAlgebra.MPolyRingElem{T}}}
Return the normal form of the polynomial p
with respect to the ideal I
.
Examples
julia> R, (x, y) = polynomial_ring(ZZ, [:x, :y]; internal_ordering=:degrevlex)
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])
julia> V = [3*x^2*y - 3*y^2, 9*x^2*y + 7*x*y]
2-element Vector{AbstractAlgebra.Generic.MPoly{BigInt}}:
3*x^2*y - 3*y^2
9*x^2*y + 7*x*y
julia> I = Generic.Ideal(R, V)
AbstractAlgebra.Generic.Ideal{AbstractAlgebra.Generic.MPoly{BigInt}}(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[7*x*y + 9*y^2, 243*y^3 - 147*y^2, x*y^2 + 36*y^3 - 21*y^2, x^2*y + 162*y^3 - 99*y^2])
julia> normal_form(30x^5*y + 2x + 1, I)
135*y^4 + 138*y^3 - 147*y^2 + 2*x + 1