GitHub

Ideals in Multivariate Rings

Types

The OSCAR type for ideals in multivariate polynomial rings is of parametrized form MPolyIdeal{T}, where T is the element type of the polynomial ring.

Constructors

ideal — Method
ideal(R::MPolyRing, V::Vector)

Given a vector V of polynomials in R, return the ideal of R generated by these polynomials.

Note

In the graded case, the entries of V must be homogeneous.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x*y-3*x,y^3-2*x^2*y])
Ideal generated by
  x*y - 3*x
  -2*x^2*y + y^3

julia> typeof(I)
MPolyIdeal{QQMPolyRingElem}

julia> S, (x, y) = graded_polynomial_ring(QQ, [:x, :y],  [1, 2])
(Graded multivariate polynomial ring in 2 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y])

julia> J = ideal(S, [(x^2+y)^2])
Ideal generated by
  x^4 + 2*x^2*y + y^2

julia> typeof(J)
MPolyIdeal{MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}}
source

Data Associated to Ideals

Basic Data

If I is an ideal of a multivariate polynomial ring R, then

  • base_ring(I) refers to R,
  • gens(I) to the generators of I,
  • number_of_generators(I) / ngens(I) to the number of these generators, and
  • gen(I, k) as well as I[k] to the k-th such generator.
Examples
julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> base_ring(I)
Multivariate polynomial ring in 2 variables x, y
  over rational field

julia> gens(I)
3-element Vector{QQMPolyRingElem}:
 x^2
 x*y
 y^2

julia> number_of_generators(I)
3

julia> gen(I, 2)
x*y

Dimension

dim — Method
dim(I::MPolyIdeal)

Return the Krull dimension of I.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [y-x^2, x-z^3])
Ideal generated by
  -x^2 + y
  x - z^3

julia> dim(I)
1
source

Codimension

In the graded case, we additionally have:

Minimal Sets of Generators

minimal_generating_set — Method
minimal_generating_set(I::MPolyIdeal{<:MPolyDecRingElem})

Given a (homogeneous) ideal I in a graded multivariate polynomial ring over a field, return an array containing a minimal set of generators of I. If I is the zero ideal, an empty list is returned.

Examples

julia> R, (x, y, z) = graded_polynomial_ring(QQ, [:x, :y, :z]);

julia> V = [x, z^2, x^3+y^3, y^4, y*z^5];

julia> I = ideal(R, V)
Ideal generated by
  x
  z^2
  x^3 + y^3
  y^4
  y*z^5

julia> minimal_generating_set(I)
3-element Vector{MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}}:
 x
 z^2
 y^3

julia> I = ideal(R, zero(R))
Ideal generated by
  0

julia> minimal_generating_set(I)
MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[]
source

Castelnuovo-Mumford Regularity

cm_regularity — Method
cm_regularity(I::MPolyIdeal)

Given a (homogeneous) ideal I in a standard $\mathbb Z$-graded multivariate polynomial ring with coefficients in a field, return the Castelnuovo-Mumford regularity of I.

Examples

julia> R, (w, x, y, z) = graded_polynomial_ring(QQ, [:w, :x, :y, :z]);

julia> I = ideal(R, [y^2*z − x^2*w, z^4 − x*w^3]);

julia> cm_regularity(I)
6

julia> minimal_betti_table(I);
source

Degree

degree — Method
degree(I::MPolyIdeal)

Given a (homogeneous) ideal I in a standard $\mathbb Z$-graded multivariate polynomial ring, return the degree of I (that is, the degree of the quotient of base_ring(I) modulo I). Otherwise, return the degree of the homogenization of I with respect to the standard $\mathbb Z$-grading.

Note

Geometrically, the degree of a homogeneous ideal as above is the number of intersection points of its projective variety with a generic linear subspace of complementary dimension (counted with multiplicities). See also [MS21].

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [y-x^2, x-z^3])
Ideal generated by
  -x^2 + y
  x - z^3

julia> degree(I)
6
source

Operations on Ideals

Simple Ideal Operations

Powers of Ideal

^ — Method
^(I::MPolyIdeal, m::Int)

Return the m-th power of I.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [x, y])
Ideal generated by
  x
  y

julia> I^3
Ideal generated by
  x^3
  x^2*y
  x*y^2
  y^3
source

Sum of Ideals

+ — Method
+(I::MPolyIdeal{T}, J::MPolyIdeal{T}) where T

Return the sum of I and J.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [x, y])
Ideal generated by
  x
  y

julia> J = ideal(R, [z^2])
Ideal generated by
  z^2

julia> I+J
Ideal generated by
  x
  y
  z^2
source

Product of Ideals

* — Method
*(I::MPolyIdeal{T}, J::MPolyIdeal{T}) where T

Return the product of I and J.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [x, y])
Ideal generated by
  x
  y

julia> J = ideal(R, [z^2])
Ideal generated by
  z^2

julia> I*J
Ideal generated by
  x*z^2
  y*z^2
source

Intersection of Ideals

intersect — Method
intersect(I::MPolyIdeal{T}, Js::MPolyIdeal{T}...) where T
intersect(V::Vector{MPolyIdeal{T}}) where T

Return the intersection of two or more ideals.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x, y])^2;

julia> J = ideal(R, [y^2-x^3+x]);

julia> intersect(I, J)
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> intersect([I, J])
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2
source

Ideal Quotients

Given two ideals $I, J$ of a ring $R$, the ideal quotient of $I$ by $J$ is the ideal

\[I:J= \bigl\{f \in R\:\big|\: f J \subset I\bigr\}\subset R.\]

quotient — Method
quotient(I::MPolyIdeal{T}, J::MPolyIdeal{T}) where T

Return the ideal quotient of I by J. Alternatively, use I:J.

quotient(I::MPolyIdeal{T}, f::MPolyRingElem{T}) where T

Return the ideal quotient of I by the ideal generated by f. Alternatively, use I:f.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [x^4+x^2*y*z+y^3*z, y^4+x^3*z+x*y^2*z, x^3*y+x*y^3])
Ideal generated by
  x^4 + x^2*y*z + y^3*z
  x^3*z + x*y^2*z + y^4
  x^3*y + x*y^3

julia> J = ideal(R, [x, y, z])^2
Ideal generated by
  x^2
  x*y
  x*z
  y^2
  y*z
  z^2

julia> L = quotient(I, J)
Ideal generated by
  x^3*z + x*y^2*z + y^4
  x^3*y + x*y^3
  x^4 + x^2*y*z + y^3*z
  x^3*z^2 - x^2*y*z^2 + x*y^2*z^2 - y^3*z^2
  x^2*y^2*z - x^2*y*z^2 - y^3*z^2
  x^3*z^2 + x^2*y^3 - x^2*y^2*z + x*y^2*z^2

julia> I:J
Ideal generated by
  x^3*z + x*y^2*z + y^4
  x^3*y + x*y^3
  x^4 + x^2*y*z + y^3*z
  x^3*z^2 - x^2*y*z^2 + x*y^2*z^2 - y^3*z^2
  x^2*y^2*z - x^2*y*z^2 - y^3*z^2
  x^3*z^2 + x^2*y^3 - x^2*y^2*z + x*y^2*z^2

julia> I:x
Ideal generated by
  x^2*y + y^3
  x^3*z + x*y^2*z + y^4
  x^2*z^2 + x*y^3 - x*y^2*z + y^2*z^2
  x^4
  x^3*z^2 - x^2*z^3 + 2*x*y^2*z^2 - y^2*z^3
  -x^2*z^4 + x*y^2*z^3 - y^2*z^4
source

Saturation

Given two ideals $I, J$ of a ring $R$, the saturation of $I$ with respect to $J$ is the ideal

\[I:J^{\infty} = \bigl\{ f \in R \:\big|\: f J^k \!\subset I {\text{ for some }}k\geq 1 \bigr\} = \textstyle{\bigcup\limits_{k=1}^{\infty} (I:J^k)}.\]

saturation — Method
saturation(I::MPolyIdeal{T}, 
           J::MPolyIdeal{T} = ideal(base_ring(I), gens(base_ring(I))); 
           iteration::Bool=false) where T

Return the saturation of I with respect to J.

If the second ideal J is not given, the ideal generated by the generators (variables) of base_ring(I) is used.

If iteration is set to true, the saturation is done by carrying out successive ideal quotient computations as in the definition of saturation. Otherwise, a more sophisticated Gröbner basis approach is used which is typically faster. Applying the two approaches may lead to different generating sets of the saturation.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [z^3, y*z^2, x*z^2, y^2*z, x*y*z, x^2*z, x*y^2, x^2*y])
Ideal generated by
  z^3
  y*z^2
  x*z^2
  y^2*z
  x*y*z
  x^2*z
  x*y^2
  x^2*y

julia> J = ideal(R, [x, y, z])
Ideal generated by
  x
  y
  z

julia> K = saturation(I, J)
Ideal generated by
  z
  x*y

julia> K = saturation(I)
Ideal generated by
  z
  x*y
source
saturation_with_index — Method
saturation_with_index(I::MPolyIdeal{T}, 
                      J::MPolyIdeal{T} = ideal(base_ring(I), gens(base_ring(I)))) where T

Return $I:J^{\infty}$ together with the smallest integer $m$ such that $I:J^m = I:J^{\infty}$ (saturation index).

If the second ideal J is not given, the ideal generated by the generators (variables) of base_ring(I) is used.

Note

If the saturation index is not needed, we recommend to use saturation(I, J) which is typically faster.

Examples

julia> R, (x, y, z) = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> I = ideal(R, [z^3, y*z^2, x*z^2, y^2*z, x*y*z, x^2*z, x*y^2, x^2*y])
Ideal generated by
  z^3
  y*z^2
  x*z^2
  y^2*z
  x*y*z
  x^2*z
  x*y^2
  x^2*y

julia> J = ideal(R, [x, y, z])
Ideal generated by
  x
  y
  z

julia> K, m = saturation_with_index(I, J)
(Ideal (z, x*y), 2)

julia> K, m = saturation_with_index(I)
(Ideal (z, x*y), 2)
source

Elimination

eliminate — Method
eliminate(I::MPolyIdeal{T}, V::Vector{T}) where T <: MPolyRingElem

Given a vector V of polynomials which are variables, these variables are eliminated from I. That is, return the ideal generated by all polynomials in I which only involve the remaining variables.

eliminate(I::MPolyIdeal, V::AbstractVector{Int})

Given a vector V of indices which specify variables, these variables are eliminated from I. That is, return the ideal generated by all polynomials in I which only involve the remaining variables.

Note

The return value is an ideal of the original ring.

Examples

julia> R, (t, x, y, z) = polynomial_ring(QQ, [:t, :x, :y, :z])
(Multivariate polynomial ring in 4 variables over QQ, QQMPolyRingElem[t, x, y, z])

julia> I = ideal(R, [t-x, t^2-y, t^3-z])
Ideal generated by
  t - x
  t^2 - y
  t^3 - z

julia> A = [t]
1-element Vector{QQMPolyRingElem}:
 t

julia> TC = eliminate(I, A)
Ideal generated by
  -x*z + y^2
  x*y - z
  x^2 - y

julia> A = [1]
1-element Vector{Int64}:
 1

julia> TC = eliminate(I, A)
Ideal generated by
  -x*z + y^2
  x*y - z
  x^2 - y

julia> base_ring(TC)
Multivariate polynomial ring in 4 variables t, x, y, z
  over rational field
source

Truncation

truncate — Method
truncate(I::MPolyIdeal, g::FinGenAbGroupElem)

Given a (homogeneous) ideal I in a $\mathbb Z$-graded multivariate polynomial ring with positive weights, return the truncation of I at degree g.

truncate(I::MPolyIdeal, d::Int)

Given an ideal I as above, and given an integer d, convert d into an element g of the grading group of base_ring(I) and proceed as above.

Examples

julia> R, (x, y, z) = graded_polynomial_ring(QQ, [:x, :y, :z]);

julia> I = ideal(R, [x, y^4, z^6])
Ideal generated by
  x
  y^4
  z^6

julia> truncate(I, 3)
Ideal generated by
  x*z^2
  x*y*z
  x*y^2
  x^2*z
  x^2*y
  x^3
  y^4
  z^6
julia> R, (x, y, z) = graded_polynomial_ring(QQ, [:x, :y, :z], [3,2,1]);

julia> I = ideal(R, [x, y^4, z^6])
Ideal generated by
  x
  y^4
  z^6

julia> truncate(I, 3)
Ideal generated by
  x
  y^4
  z^6

julia> truncate(I, 4)
Ideal generated by
  x*z
  z^6
  y^4
source

Tests on Ideals

Basic Tests

is_zero — Method
is_zero(I::MPolyIdeal)

Return true if I is the zero ideal, false otherwise.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, y-x^2)
Ideal generated by
  -x^2 + y

julia> is_zero(I)
false
source
is_one — Method
is_one(I::MPolyIdeal)

Return true if I is generated by 1, false otherwise.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x, x + y, y - 1])
Ideal generated by
  x
  x + y
  y - 1

julia> is_one(I)
true
source
is_monomial — Method
is_monomial(f::MPolyRingElem)

Return true if f is a monomial, false otherwise.

is_monomial(I::MPolyIdeal)

Return true if I can be generated by monomials, false otherwise.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> f = 2*x+y
2*x + y

julia> g = y
y

julia> is_monomial(f)
false

julia> is_monomial(g)
true

julia> is_monomial(ideal(R, [f, g]))
true
source

Containment of Ideals

is_subset — Method
is_subset(I::MPolyIdeal, J::MPolyIdeal)

Return true if I is contained in J, false otherwise.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x^2])
Ideal generated by
  x^2

julia> J = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> is_subset(I, J)
true
source

Equality of Ideals

== — Method
==(I::MPolyIdeal, J::MPolyIdeal)

Return true if I is equal to J, false otherwise.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x^2])
Ideal generated by
  x^2

julia> J = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> I == J
false
source

Ideal Membership

ideal_membership — Method
ideal_membership(f::T, I::MPolyIdeal{T}) where T

Return true if f is contained in I, false otherwise. Alternatively, use f in I.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> f = x^2
x^2

julia> I = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> ideal_membership(f, I)
true

julia> g = x
x

julia> g in I
false
source

Radical Membership

radical_membership — Method
radical_membership(f::T, I::MPolyIdeal{T}) where T

Return true if f is contained in the radical of I, false otherwise. Alternatively, use inradical(f, I).

Examples

julia> R, (x,) = polynomial_ring(QQ, [:x])
(Multivariate polynomial ring in 1 variable over QQ, QQMPolyRingElem[x])

julia> f = x
x

julia> I = ideal(R,  [x^2])
Ideal generated by
  x^2

julia> radical_membership(f, I)
true

julia> g = x+1
x + 1

julia> inradical(g, I)
false
source

Primality Test

is_prime — Method
is_prime(I::MPolyIdeal)

Return true if I is prime, false otherwise.

Warning

The function computes the minimal associated primes of I. This may take some time.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> is_prime(I)
false
source

Primary Test

is_primary — Method
is_primary(I::MPolyIdeal)

Return true if I is primary, false otherwise.

Warning

The function computes a primary decomposition of I. This may take some time.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = ideal(R, [x, y])^2
Ideal generated by
  x^2
  x*y
  y^2

julia> is_primary(I)
true
source

Decomposition of Ideals

We discuss various decomposition techniques. They are implemented for polynomial rings over fields and, if explicitly mentioned, also for polynomial rings over the integers. See [DGP99] for a survey.

Radical

radical — Method
radical(f::SesquilinearForm{T})

Return the radical of the sesquilinear form f, i.e. the subspace of all v such that f(u,v)=0 for all u. The radical of a quadratic form Q is the set of vectors v such that Q(v)=0 and v lies in the radical of the corresponding bilinear form.

source

Primary Decomposition

primary_decomposition — Method
primary_decomposition(I::MPolyIdeal; algorithm = :GTZ, cache=true)

Return a minimal primary decomposition of I.

The decomposition is returned as a vector of tuples $(Q_1, P_1), \dots, (Q_t, P_t)$, say, where each $Q_i$ is a primary ideal with associated prime $P_i$, and where the intersection of the $Q_i$ is I.

Implemented Algorithms

If the base ring of I is a polynomial ring over a field, the algorithm of Gianni, Trager, and Zacharias is used by default (algorithm = :GTZ). Alternatively, the algorithm by Shimoyama and Yokoyama can be used by specifying algorithm = :SY. For polynomial rings over the integers, the algorithm proceeds as suggested by Pfister, Sadiq, and Steidel. See [GTZ88], [SY96], and [PSS11].

Warning

The algorithm of Gianni, Trager, and Zacharias may not terminate over a small finite field. If it terminates, the result is correct.

Warning

If computations are done in a ring over a number field, then the output may contain redundant components.

If cache=false is set, the primary decomposition is recomputed and not cached.

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = primary_decomposition(I)
3-element Vector{Tuple{MPolyIdeal{QQMPolyRingElem}, MPolyIdeal{QQMPolyRingElem}}}:
 (Ideal (x^3 - x - y^2), Ideal (x^3 - x - y^2))
 (Ideal (x^2 - 2*x*y - 2*x + y^2 + 2*y + 1), Ideal (x - y - 1))
 (Ideal (y, x^2), Ideal (x, y))

julia> L = primary_decomposition(I, algorithm = :SY, cache=false)
3-element Vector{Tuple{MPolyIdeal{QQMPolyRingElem}, MPolyIdeal{QQMPolyRingElem}}}:
 (Ideal (x^3 - x - y^2), Ideal (x^3 - x - y^2))
 (Ideal (x^2 - 2*x*y - 2*x + y^2 + 2*y + 1), Ideal (x - y - 1))
 (Ideal (y, x^2), Ideal (y, x))
julia> R, (a, b, c, d) = polynomial_ring(ZZ, [:a, :b, :c, :d])
(Multivariate polynomial ring in 4 variables over ZZ, ZZMPolyRingElem[a, b, c, d])

julia> I = ideal(R, [1326*a^2*d^5, 1989*a^2*c^5, 102*b^4*d^5, 153*b^4*c^5,
       663*a^2*c^5*d^5, 51*b^4*c^5*d^5, 78*a^2*d^15, 117*a^2*c^15,
       78*a^15*d^5, 117*a^15*c^5, 6*a^2*b^4*d^15, 9*a^2*b^4*c^15,
       39*a^2*c^5*d^15, 39*a^2*c^15*d^5, 6*a^2*b^15*d^5, 9*a^2*b^15*c^5,
       6*a^15*b^4*d^5, 9*a^15*b^4*c^5, 39*a^15*c^5*d^5, 3*a^2*b^4*c^5*d^15,
       3*a^2*b^4*c^15*d^5, 3*a^2*b^15*c^5*d^5, 3*a^15*b^4*c^5*d^5])
Ideal generated by
  1326*a^2*d^5
  1989*a^2*c^5
  102*b^4*d^5
  153*b^4*c^5
  663*a^2*c^5*d^5
  51*b^4*c^5*d^5
  78*a^2*d^15
  117*a^2*c^15
  78*a^15*d^5
  117*a^15*c^5
  6*a^2*b^4*d^15
  9*a^2*b^4*c^15
  39*a^2*c^5*d^15
  39*a^2*c^15*d^5
  6*a^2*b^15*d^5
  9*a^2*b^15*c^5
  6*a^15*b^4*d^5
  9*a^15*b^4*c^5
  39*a^15*c^5*d^5
  3*a^2*b^4*c^5*d^15
  3*a^2*b^4*c^15*d^5
  3*a^2*b^15*c^5*d^5
  3*a^15*b^4*c^5*d^5

julia> L = primary_decomposition(I)
8-element Vector{Tuple{MPolyIdeal{ZZMPolyRingElem}, MPolyIdeal{ZZMPolyRingElem}}}:
 (Ideal (d^5, c^5), Ideal (d, c))
 (Ideal (a^2, b^4), Ideal (b, a))
 (Ideal (2, c^5), Ideal (2, c))
 (Ideal (3), Ideal (3))
 (Ideal (13, b^4), Ideal (13, b))
 (Ideal (17, a^2), Ideal (17, a))
 (Ideal (17, d^15, c^15, b^15, a^15), Ideal (17, d, c, b, a))
 (Ideal (9, 3*d^5, d^10), Ideal (3, d))
source

Absolute Primary Decomposition

absolute_primary_decomposition — Method
absolute_primary_decomposition(I::MPolyIdeal{<:MPolyRingElem{QQFieldElem}})

Given an ideal I in a multivariate polynomial ring over the rationals, return an absolute minimal primary decomposition of I.

Return the decomposition as a vector of tuples $(Q_i, P_i, P_{ij}, d_{ij})$, say, where $(Q_i, P_i)$ is a (primary, prime) tuple as returned by primary_decomposition(I), and $P_{ij}$ represents a corresponding class of conjugated absolute associated primes defined over a number field of degree $d_{ij}$ whose generator prints as _a.

Implemented Algorithms

The implementation combines the algorithm of Gianni, Trager, and Zacharias for primary decomposition with absolute polynomial factorization.

Warning

Over number fields this proceduce might return redundant output.

Examples

julia> R, (y, z) = polynomial_ring(QQ, [:y, :z])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[y, z])

julia> p = z^2+1
z^2 + 1

julia> q = z^3+2
z^3 + 2

julia> I = ideal(R, [p*q^2, y-z^2])
Ideal generated by
  z^8 + z^6 + 4*z^5 + 4*z^3 + 4*z^2 + 4
  y - z^2

julia> L = primary_decomposition(I)
2-element Vector{Tuple{MPolyIdeal{QQMPolyRingElem}, MPolyIdeal{QQMPolyRingElem}}}:
 (Ideal (z^2 + 1, y - z^2), Ideal (z^2 + 1, y - z^2))
 (Ideal (z^6 + 4*z^3 + 4, y - z^2), Ideal (z^3 + 2, y - z^2))

julia> AL = absolute_primary_decomposition(I)
2-element Vector{Tuple{MPolyIdeal{QQMPolyRingElem}, MPolyIdeal{QQMPolyRingElem}, MPolyIdeal{AbstractAlgebra.Generic.MPoly{AbsSimpleNumFieldElem}}, Int64}}:
 (Ideal (z^2 + 1, y + 1), Ideal (z^2 + 1, y + 1), Ideal (z - _a, y + 1), 2)
 (Ideal (z^6 + 4*z^3 + 4, y - z^2), Ideal (z^3 + 2, y - z^2), Ideal (z - _a, y - _a^2), 3)

julia> AP = AL[1][3]
Ideal generated by
  z - _a
  y + 1

julia> RAP = base_ring(AP)
Multivariate polynomial ring in 2 variables y, z
  over number field of degree 2 over QQ

julia> NF = coefficient_ring(RAP)
Number field with defining polynomial x^2 + 1
  over rational field

julia> a = gen(NF)
_a

julia> minpoly(a)
x^2 + 1
julia> R, (x, y) = graded_polynomial_ring(QQ, [:x, :y])
(Graded multivariate polynomial ring in 2 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y])

julia> I = ideal(R, [x^2+y^2])
Ideal generated by
  x^2 + y^2

julia> AL = absolute_primary_decomposition(I)
1-element Vector{Tuple{MPolyIdeal{MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}}, MPolyIdeal{MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}}, MPolyIdeal{MPolyDecRingElem{AbsSimpleNumFieldElem, AbstractAlgebra.Generic.MPoly{AbsSimpleNumFieldElem}}}, Int64}}:
 (Ideal (x^2 + y^2), Ideal (x^2 + y^2), Ideal (x + _a*y), 2)

julia> AP = AL[1][3]
Ideal generated by
  x + _a*y

julia> RAP = base_ring(AP)
Multivariate polynomial ring in 2 variables over number field graded by 
  x -> [1]
  y -> [1]
source

Minimal Associated Primes

minimal_primes — Method
minimal_primes(I::MPolyIdeal; algorithm::Symbol = :GTZ)

Return a vector containing the minimal associated prime ideals of I.

Implemented Algorithms

If the base ring of I is a polynomial ring over a field, the algorithm of Gianni, Trager, and Zacharias is used by default (algorithm = :GTZ). Alternatively, characteristic sets can be used by specifying algorithm = :charSets. For polynomial rings over the integers, the algorithm proceeds as suggested by Pfister, Sadiq, and Steidel. See [GTZ88] and [PSS11].

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = minimal_primes(I)
2-element Vector{MPolyIdeal{QQMPolyRingElem}}:
 Ideal (x - y - 1)
 Ideal (x^3 - x - y^2)

julia> L = minimal_primes(I, algorithm = :charSets)
2-element Vector{MPolyIdeal{QQMPolyRingElem}}:
 Ideal (x - y - 1)
 Ideal (x^3 - x - y^2)
julia> R, (a, b, c, d) = polynomial_ring(ZZ, [:a, :b, :c, :d])
(Multivariate polynomial ring in 4 variables over ZZ, ZZMPolyRingElem[a, b, c, d])

julia> I = ideal(R, [1326*a^2*d^5, 1989*a^2*c^5, 102*b^4*d^5, 153*b^4*c^5,
       663*a^2*c^5*d^5, 51*b^4*c^5*d^5, 78*a^2*d^15, 117*a^2*c^15,
       78*a^15*d^5, 117*a^15*c^5, 6*a^2*b^4*d^15, 9*a^2*b^4*c^15,
       39*a^2*c^5*d^15, 39*a^2*c^15*d^5, 6*a^2*b^15*d^5, 9*a^2*b^15*c^5,
       6*a^15*b^4*d^5, 9*a^15*b^4*c^5, 39*a^15*c^5*d^5, 3*a^2*b^4*c^5*d^15,
       3*a^2*b^4*c^15*d^5, 3*a^2*b^15*c^5*d^5, 3*a^15*b^4*c^5*d^5])
Ideal generated by
  1326*a^2*d^5
  1989*a^2*c^5
  102*b^4*d^5
  153*b^4*c^5
  663*a^2*c^5*d^5
  51*b^4*c^5*d^5
  78*a^2*d^15
  117*a^2*c^15
  78*a^15*d^5
  117*a^15*c^5
  6*a^2*b^4*d^15
  9*a^2*b^4*c^15
  39*a^2*c^5*d^15
  39*a^2*c^15*d^5
  6*a^2*b^15*d^5
  9*a^2*b^15*c^5
  6*a^15*b^4*d^5
  9*a^15*b^4*c^5
  39*a^15*c^5*d^5
  3*a^2*b^4*c^5*d^15
  3*a^2*b^4*c^15*d^5
  3*a^2*b^15*c^5*d^5
  3*a^15*b^4*c^5*d^5

julia> L = minimal_primes(I)
6-element Vector{MPolyIdeal{ZZMPolyRingElem}}:
 Ideal (d, c)
 Ideal (b, a)
 Ideal (2, c)
 Ideal (3)
 Ideal (13, b)
 Ideal (17, a)
source

Weak Equidimensional Decomposition

equidimensional_decomposition_weak — Method
equidimensional_decomposition_weak(I::MPolyIdeal)

Return a vector of equidimensional ideals where the last entry is the equidimensional hull of I, that is, the intersection of the primary components of I of maximal dimension. Each of the previous entries is an ideal of lower dimension whose associated primes are exactly the associated primes of I of that dimension.

Implemented Algorithms

The implementation relies on ideas of Eisenbud, Huneke, and Vasconcelos. See [EHV92].

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = equidimensional_decomposition_weak(I)
2-element Vector{MPolyIdeal{QQMPolyRingElem}}:
 Ideal (y, x)
 Ideal with 1 generator
source

Equidimensional Decomposition of radical

equidimensional_decomposition_radical — Method
equidimensional_decomposition_radical(I::MPolyIdeal)

Return a vector of equidimensional radical ideals increasingly ordered by dimension. For each dimension, the returned radical ideal is the intersection of the associated primes of I of that dimension.

Implemented Algorithms

The implementation combines the algorithms of Krick and Logar (with modifications by Laplagne) and Kemper. See [KL91] and [Kem02].

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = equidimensional_decomposition_radical(I)
2-element Vector{MPolyIdeal{QQMPolyRingElem}}:
 Ideal (y, x)
 Ideal (x^4 - x^3*y - x^3 - x^2 - x*y^2 + x*y + x + y^3 + y^2)
source

Equidimensional Hull

equidimensional_hull — Method
equidimensional_hull(I::MPolyIdeal)

If the base ring of I is a polynomial ring over a field, return the intersection of the primary components of I of maximal dimension. In the case of polynomials over the integers, return the intersection of the primary components of I of minimal height. If I is the unit ideal, return [ideal(1)].

Implemented Algorithms

For polynomial rings over a field, the implementation relies on ideas as used by Gianni, Trager, and Zacharias or Krick and Logar. For polynomial rings over the integers, the algorithm proceeds as suggested by Pfister, Sadiq, and Steidel. See [GTZ88], [KL91], and [PSS11].

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = equidimensional_hull(I)
Ideal generated by
  x^5 - 2*x^4*y - 2*x^4 + x^3*y^2 + 2*x^3*y - x^2*y^2 + 2*x^2*y + 2*x^2 + 2*x*y^3 + x*y^2 - 2*x*y - x - y^4 - 2*y^3 - y^2
julia> R, (a, b, c, d) = polynomial_ring(ZZ, [:a, :b, :c, :d])
(Multivariate polynomial ring in 4 variables over ZZ, ZZMPolyRingElem[a, b, c, d])

julia> I = ideal(R, [1326*a^2*d^5, 1989*a^2*c^5, 102*b^4*d^5, 153*b^4*c^5,
       663*a^2*c^5*d^5, 51*b^4*c^5*d^5, 78*a^2*d^15, 117*a^2*c^15,
       78*a^15*d^5, 117*a^15*c^5, 6*a^2*b^4*d^15, 9*a^2*b^4*c^15,
       39*a^2*c^5*d^15, 39*a^2*c^15*d^5, 6*a^2*b^15*d^5, 9*a^2*b^15*c^5,
       6*a^15*b^4*d^5, 9*a^15*b^4*c^5, 39*a^15*c^5*d^5, 3*a^2*b^4*c^5*d^15,
       3*a^2*b^4*c^15*d^5, 3*a^2*b^15*c^5*d^5, 3*a^15*b^4*c^5*d^5])
Ideal generated by
  1326*a^2*d^5
  1989*a^2*c^5
  102*b^4*d^5
  153*b^4*c^5
  663*a^2*c^5*d^5
  51*b^4*c^5*d^5
  78*a^2*d^15
  117*a^2*c^15
  78*a^15*d^5
  117*a^15*c^5
  6*a^2*b^4*d^15
  9*a^2*b^4*c^15
  39*a^2*c^5*d^15
  39*a^2*c^15*d^5
  6*a^2*b^15*d^5
  9*a^2*b^15*c^5
  6*a^15*b^4*d^5
  9*a^15*b^4*c^5
  39*a^15*c^5*d^5
  3*a^2*b^4*c^5*d^15
  3*a^2*b^4*c^15*d^5
  3*a^2*b^15*c^5*d^5
  3*a^15*b^4*c^5*d^5

julia> L = equidimensional_hull(I)
Ideal generated by
  3
source

Radical of the Equidimensional Hull

equidimensional_hull_radical — Method
equidimensional_hull_radical(I::MPolyIdeal)

Return the intersection of the associated primes of I of maximal dimension. If I is the unit ideal, return [ideal(1)].

Implemented Algorithms

The implementation relies on a combination of the algorithms of Krick and Logar (with modifications by Laplagne) and Kemper. See [KL91] and [Kem02].

Examples

julia> R, (x, y) = polynomial_ring(QQ, [:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> I = intersect(ideal(R, [x, y])^2, ideal(R, [y^2-x^3+x]))
Ideal generated by
  x^3*y - x*y - y^3
  x^4 - x^2 - x*y^2

julia> I = intersect(I, ideal(R, [x-y-1])^2)
Ideal generated by
  x^5*y - 2*x^4*y^2 - 2*x^4*y + x^3*y^3 + 2*x^3*y^2 - x^2*y^3 + 2*x^2*y^2 + 2*x^2*y + 2*x*y^4 + x*y^3 - 2*x*y^2 - x*y - y^5 - 2*y^4 - y^3
  x^6 - 2*x^5 - 3*x^4*y^2 - 2*x^4*y + 2*x^3*y^3 + 3*x^3*y^2 + 2*x^3*y + 2*x^3 + 5*x^2*y^2 + 2*x^2*y - x^2 + 3*x*y^4 - 5*x*y^2 - 2*x*y - 2*y^5 - 4*y^4 - 2*y^3

julia> L = equidimensional_hull_radical(I)
Ideal generated by
  x^4 - x^3*y - x^3 - x^2 - x*y^2 + x*y + x + y^3 + y^2
source

Homogenization and Dehomogenization

Referring to [KR05] for definitions and technical details, we discuss homogenization and dehomogenization in the context of $\mathbb Z^m$-gradings.

homogenizer — Method
homogenizer(P::MPolyRing, h::VarName;  pos::Int=1+ngens(P))

Create a "homogenizing operator" assuming a standard grading; h is the name of the homogenizing variable; pos indicates where to put the homogenizing variable in the list of generators of the graded polynomial ring (default is after all the other variables).

Examples

julia> P, (x,y) = polynomial_ring(QQ, [:x, :y]);

julia> H = homogenizer(P, "h");

julia> H(x^2+y)
x^2 + y*h

julia> V = H.([x^2+y, x+y^2]);

julia> parent(V[1]) == parent(V[2])
true

julia> H(ideal([x^2+y]))
Ideal generated by
  x^2 + y*h
source
homogenizer — Method
homogenizer(P::MPolyRing, W::Union{ZZMatrix, Matrix{<:IntegerUnion}}, h::VarName;  pos::Int=1+ngens(P))

Create a "homogenizing operator" using the grading specified by the columns of W; h is the prefix for the homogenizing variables; pos indicates where to put the homogenizing variables in the list of generators of the graded polynomial ring (default is after all the other variables).

Examples

julia> P, (x,y) = polynomial_ring(QQ, [:x, :y]);

julia> W = ZZMatrix(2,2, [2,3,5,7]);

julia> H = homogenizer(P, W, "h");

julia> H(x^2+y)
x^2 + y*h[1]*h[2]^3

julia> V = H.([x^2+y, x+y^2]);

julia> parent(V[1]) == parent(V[2])
true

julia> H(ideal([x^2+y]))
Ideal generated by
  x^2 + y*h[1]*h[2]^3
source
dehomogenizer — Method
dehomogenizer(H::Homogenizer)

Create a "dehomogenizing operator" from a Homogenizer; it is effectively a polynomial ring homomorphism mapping all homogenizing variables to 1. A Dehomogenizer is a post-inverse for the Homogenizer it was created from.

Examples

julia> P, (x,y) = polynomial_ring(QQ, [:x, :y]);

julia> H = homogenizer(P, "h");

julia> DH = dehomogenizer(H);

julia> F = H(x^2+y)
x^2 + y*h

julia> DH(F)
x^2 + y

julia> V = [x^2+y, x*y+y^2]; HV = H.(V);

julia> parent(DH(HV[1])) == P  &&  parent(DH(HV[2])) == P
true

julia> DH(H(ideal(V)))
Ideal generated by
  x*y + y^2
  x^2 + y
  y^3 + y^2
source
julia> P, (x, y) = polynomial_ring(QQ, [:x, :y]);

julia> I = ideal([x^2+y, x*y+y^2]);

julia> H = homogenizer(P, "h");

julia> Ih = H(I)     # homogenization of ideal I
Ideal generated by
  x*y + y^2
  x^2 + y*h
  y^3 + y^2*h

julia> DH = dehomogenizer(H);

julia> DH(Ih) == I   # dehomogenization of Ih
true

Generating Special Ideals

Katsura-n

These systems appeared in a problem of magnetism in physics. For a given $n$ katsura(n) has $2^n$ solutions and is defined in a polynomial ring with $n+1$ variables over the rational numbers. For a given polynomial ring R with $n$ variables katsura(R) defines the corresponding system with $2^{n-1}$ solutions.

katsura — Method
katsura(n::Int)

Given a natural number n return the Katsura ideal over the rational numbers generated by $u_m - \sum_{l=-n}^n u_{l-m} u_l$, $1 - \sum_{l = -n}^n u_l$ where $u_{-i} = u_i$, and $u_i = 0$ for $i > n$ and $m \in \{-n, \ldots, n\}$.

Note that indices have been shifted to start from 1.

Examples

julia> I = katsura(2)
Ideal generated by
  x1 + 2*x2 + 2*x3 - 1
  x1^2 - x1 + 2*x2^2 + 2*x3^2
  2*x1*x2 + 2*x2*x3 - x2
julia> base_ring(I)
Multivariate polynomial ring in 3 variables x1, x2, x3
  over rational field
source
katsura — Method
katsura(R::MPolyRing)

Return the Katsura ideal in the given polynomial ring R.

Examples

julia> R, _ = QQ[:x, :y, :z]
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> katsura(R)
Ideal generated by
  x + 2*y + 2*z - 1
  x^2 - x + 2*y^2 + 2*z^2
  2*x*y + 2*y*z - y
source