GitHub

Binomial Primary Decomposition

Introduction

A binomial is a polynomial consisting of at most two terms. A binomial ideal is an ideal which can be generated by binomials. A binomial primary decomposition is a primary decomposition of a binomial ideal into primary ideals which are binomial as well. In this section, focusing on polynomial rings over fields, we discuss functionality for computing such decompositions.

We begin by recalling that a proper ideal $I$ of a polynomial ring $K[x_1, \dots, x_n]$ over a field $K$ is called cellular if each variable $x_i$ is either a nonzerodivisor or nilpotent modulo $I$. In this case, we refer to the nonzerodivisors among the variables as the cell variables with respect to $I$. A cellular decomposition of a proper binomial ideal $I$ of $K[x_1, \dots, x_n]$ is a decomposition of $I$ into cellular binomial ideals. Using Noetherian induction, it is not too difficult to show that such decompositions exist.

With this notation, the algorithms for computing binomial primary decompositions proceed in two main steps:

  • First, compute a cellular decomposition of the given binomial ideal.
  • Then, decompose each cellular component into primary binomial ideals.

While the first step can be performed over any ground field for which Gröbner bases are implemented, the second step may require a field extension: From a theoretical point of view, the existence of binomial primary decompositions is only guaranteed if the ground field is algebraically closed.

Note

A pure difference binomial is a binomial which is the difference of two monomials. A unital binomial ideal is an ideal which can be generated by pure difference binomials and monomials. Note that cellular components of unital binomial ideals are unital as well. For unital binomial ideals in $\mathbb Q[x_1, \dots, x_n]$, binomial primary decompositions exist already over cyclotomic extensions of $\mathbb Q$. In particular, any such ideal can be decomposed over the abelian closure $\mathbb Q^{\text{ab}}$ of $\mathbb Q$. While OSCAR offers functionality for doing this, computing binomial primary decompositions in other cases is not yet supported.

See the number theory chapter for how to deal with $\mathbb Q^{\text{ab}}$.

Note

Binomial primary decompositions computed with OSCAR are not necessarily minimal.

Papers offering details on theory and algorithms as well as examples include:

Basic Tests

Binomiality Test

is_binomial — Method
is_binomial(f::MPolyRingElem)

Return true if f consists of at most 2 terms, false otherwise.

source
is_binomial — Method
is_binomial(I::MPolyIdeal)

Return true if I can be generated by polynomials consisting of at most 2 terms, false otherwise.

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

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

julia> is_binomial(f)
true

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

julia> is_binomial(J)
true

Cellularity Test

is_cellular — Method
is_cellular(I::MPolyIdeal)

Given a binomial ideal I, return true together with the indices of the cell variables if I is cellular. Return false together with the index of a variable which is a zerodivisor but not nilpotent modulo I, otherwise (return (false, [-1]) if I is not proper).

Examples

julia> R, x = polynomial_ring(QQ, :x => 1:6)
(Multivariate polynomial ring in 6 variables over QQ, QQMPolyRingElem[x[1], x[2], x[3], x[4], x[5], x[6]])

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

julia> is_cellular(I)
(true, [1, 2, 3, 4])

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,x^3-1,z*y^2-z])
Ideal generated by
  x - y
  x^3 - 1
  y^2*z - z

julia> is_cellular(I)
(false, [3])
source

Unitality Test

is_unital — Method
is_unital(I::MPolyIdeal)

Given a binomial ideal I, return true if I can be generated by differences of monomials and monomials.

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> is_unital(I)
false

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

julia> is_unital(J)
true
source

Cellular Decomposition

cellular_decomposition — Method
cellular_decomposition(I::MPolyIdeal)

Given a binomial ideal I, return a cellular decomposition 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,x^3-1,z*y^2-z])
Ideal generated by
  x - y
  x^3 - 1
  y^2*z - z

julia> cellular_decomposition(I)
2-element Vector{MPolyIdeal{QQMPolyRingElem}}:
 Ideal (y - 1, x - 1)
 Ideal (x - y, x^3 - 1, y^2*z - z, z)
source

Primary Decomposition of Cellular Ideals

cellular_hull — Method
cellular_hull(I::MPolyIdeal{QQMPolyRingElem})

Given a cellular binomial ideal I, return the intersection of the minimal primary components of I.

Examples

julia> R, x = polynomial_ring(QQ, :x => 1:6)
(Multivariate polynomial ring in 6 variables over QQ, QQMPolyRingElem[x[1], x[2], x[3], x[4], x[5], x[6]])

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

julia> is_cellular(I)
(true, [1, 2, 3, 4])

julia> cellular_hull(I)
Ideal generated by
  x[6]
  x[5]
source
cellular_associated_primes — Method
cellular_associated_primes(I::MPolyIdeal{QQMPolyRingElem})

Given a cellular binomial ideal I, return the associated primes of I.

The result is defined over the abelian closure of $\mathbb Q$. In the output, if needed, the generator for roots of unities is denoted by zeta. So zeta(3), for example, stands for a primitive third root of unity.

Examples

julia> R, x = polynomial_ring(QQ, :x => 1:6)
(Multivariate polynomial ring in 6 variables over QQ, QQMPolyRingElem[x[1], x[2], x[3], x[4], x[5], x[6]])

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

julia> cellular_associated_primes(I)
5-element Vector{MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}}:
 Ideal (x[5], x[6])
 Ideal (x[1] - x[2], x[5], x[6])
 Ideal (x[1] - zeta(3)*x[2], x[5], x[6])
 Ideal (x[1] + (zeta(3) + 1)*x[2], x[5], x[6])
 Ideal (x[3] - x[4], x[5], x[6])
source
cellular_minimal_associated_primes — Method
cellular_minimal_associated_primes(I::MPolyIdeal{QQMPolyRingElem})

Given a cellular binomial ideal I, return the minimal associated primes of I.

The result is defined over the abelian closure of $\mathbb Q$. In the output, if needed, the generator for roots of unities is denoted by zeta. So zeta(3), for example, stands for a primitive third root of unity.

Examples

julia> R, x = polynomial_ring(QQ, :x => 1:6)
(Multivariate polynomial ring in 6 variables over QQ, QQMPolyRingElem[x[1], x[2], x[3], x[4], x[5], x[6]])

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

julia> cellular_minimal_associated_primes(I::MPolyIdeal{QQMPolyRingElem})
1-element Vector{MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}}:
 Ideal (x[5], x[6])
source
cellular_primary_decomposition — Method
cellular_primary_decomposition(I::MPolyIdeal{QQMPolyRingElem})

Given a cellular binomial ideal I, return a binomial primary decomposition of I.

The result is defined over the abelian closure of $\mathbb Q$. In the output, if needed, the generator for roots of unities is denoted by zeta. So zeta(3), for example, stands for a primitive third root of unity.

Examples

julia> R, x = polynomial_ring(QQ, :x => 1:6)
(Multivariate polynomial ring in 6 variables over QQ, QQMPolyRingElem[x[1], x[2], x[3], x[4], x[5], x[6]])

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

julia> cellular_primary_decomposition(I)
5-element Vector{Tuple{MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}, MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}}}:
 (Ideal (x[6], x[5]), Ideal (x[5], x[6]))
 (Ideal (x[6], x[1] - x[2], x[5]^2), Ideal (x[1] - x[2], x[5], x[6]))
 (Ideal (x[6], x[1] - zeta(3)*x[2], x[5]^2), Ideal (x[1] - zeta(3)*x[2], x[5], x[6]))
 (Ideal (x[6], x[1] + (zeta(3) + 1)*x[2], x[5]^2), Ideal (x[1] + (zeta(3) + 1)*x[2], x[5], x[6]))
 (Ideal (x[5], x[3] - x[4], x[6]^2), Ideal (x[3] - x[4], x[5], x[6]))
source

Primary Decomposition of Binomial Ideals

binomial_primary_decomposition — Method
binomial_primary_decomposition(I::MPolyIdeal{QQMPolyRingElem})

Given a binomial ideal I, return a binomial primary decomposition of I.

The result is defined over the abelian closure of $\mathbb Q$. In the output, if needed, the generator for roots of unities is denoted by zeta. So zeta(3), for example, stands for a primitive third root of unity.

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,x^3-1,z*y^2-z])
Ideal generated by
  x - y
  x^3 - 1
  y^2*z - z

julia> binomial_primary_decomposition(I)
3-element Vector{Tuple{MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}, MPolyIdeal{AbstractAlgebra.Generic.MPoly{QQAbFieldElem{AbsSimpleNumFieldElem}}}}}:
 (Ideal (z, y - zeta(3), x - zeta(3)), Ideal (y - zeta(3), x - zeta(3), z))
 (Ideal (z, y + zeta(3) + 1, x + zeta(3) + 1), Ideal (y + zeta(3) + 1, x + zeta(3) + 1, z))
 (Ideal (y - 1, x - 1), Ideal (y - 1, x - 1, x*y - 1))
source