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.

Info

A more complete implementation for ideals defined over other rings is provided by Hecke and Oscar.

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.

Note

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.gensMethod
gens(I::Ideal{T}) where T <: RingElement

Return a list of generators of the ideal I in reduced form and canonicalised.

source

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.containsMethod
Base.contains(I::Ideal{T}, J::Ideal{T}) where T <: RingElement

Return true if the ideal J is contained in the ideal I.

source
Base.intersectMethod
intersect(I::Ideal{T}, J::Ideal{T}) where T <: RingElement

Return the intersection of the ideals I and J.

source

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_formMethod
normal_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.

source

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