Gröbner/Standard Bases Over Fields

We fix our notation in the context of standard (Gröbner) bases and present relevant OSCAR functions.

Let $K[x] = K[x_1, \dots, x_n]$ be a polynomial ring over a field $K$, and let $>$ be a monomial ordering on $\text{Mon}_n(x)$.

Given a polynomial $f\in K[x]\setminus \{0\}$, write $f$ as the sum of its nonzero terms as follows:

\[f = a_\alpha x^\alpha + a_{\beta_1} x^{\beta_1} + \dots + a_{\beta_s} x^{\beta_s},\quad x^\alpha > x^{\beta_1} > \dots > x^{\beta_s} .\]

Then, with respect to $>$, we refer to $\text{LT}_>(f) = a_\alpha x^\alpha$, $\text{LM}_>(f) = x^\alpha$, $\text{LE}_>(f) = \alpha$, $\text{LC}_>(f) = a_\alpha$, and $\text{tail}_>(f) = f - \text{LT}_>(f)$ as the leading term, the leading monomial, the leading exponent, the leading coefficient, and the tail of $f$, respectively.

Next note that the set

\[U_>:= \{u\in K[x]\setminus \{0\} \mid {\text{LM}}_>(u)=1 \}\]

is a multiplicatively closed subset of $K[x]$. Consider the localization

\[K[x]_>:= K[x][U^{-1}] = \left\{ \frac{f}{u} \:\bigg|\: f \in K[x], \, u\in U_>\right\}.\]

Then $K[x]\subseteq K[x]_>\subseteq K[x]_{\langle x \rangle},$ where $K[x]_{\langle x \rangle}$ is the localization of $K[x] $ at the maximal ideal $\langle x \rangle .$ Moreover,

  • $K[x] = K[x]_>$ iff $>$ is global, and

  • $K[x]_> = K[x]_{\langle x \rangle}$ iff $>$ is local.

Extending the notation introduced for polynomials, let now $f\in K[x]_>\setminus \{0\}$. Choose $u\in U_>$ such that $uf\in K[x]$. Then, with respect to $>$, the leading term of $f$ is defined to be $\text{LT}_>(f) = \text{LT}_>(uf)$ (this definition is independent of the choice of $u$). The leading monomial $\text{LM}_>(f)$, the leading exponent $\text{LE}_>(f)$, the leading coefficient $\text{LC}_>(f)$, and the tail $\text{tail}_>(f)$ of $f$ are defined similarly.

Note

Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation extends naturally to elements of $K[x]^p$ and $K[x]_>^p$, respectively. There is one particularity: Given an element $f = K[x]^p\setminus \{0\}$ with leading term $\text{LT}(f) = x^\alpha e_i$, we write $\text{LE}_>(f) = (\alpha, i)$.

Note

The OSCAR functions discussed in this section depend on a monomial ordering which is entered as a keyword argument. Given a polynomial ring $R$, the default_ordering for this is degrevlex except if $R$ is $\mathbb Z$-graded with positive weights. Then the corresponding wdegrevlex ordering is used. Given a free $R$-module $F$, the default_ordering is default_ordering(R)*lex(gens(F)).

Here are some illustrating OSCAR examples:

Examples
julia> R, (x, y, z) = PolynomialRing(QQ, ["x", "y", "z"])
(Multivariate Polynomial Ring in x, y, z over Rational Field, fmpq_mpoly[x, y, z])

julia> default_ordering(R)
degrevlex([x, y, z])

julia> F = free_module(R, 2)
Free module of rank 2 over Multivariate Polynomial Ring in x, y, z over Rational Field

julia> default_ordering(F)
degrevlex([x, y, z])*lex([gen(1), gen(2)])

julia> S, _ = grade(R, [1, 2, 3])
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by 
  x -> [1]
  y -> [2]
  z -> [3], MPolyElem_dec{fmpq, fmpq_mpoly}[x, y, z])

julia> default_ordering(S)
wdegrevlex([x, y, z], [1, 2, 3])
julia> R, (x, y, z) = PolynomialRing(QQ, ["x", "y", "z"])
(Multivariate Polynomial Ring in x, y, z over Rational Field, fmpq_mpoly[x, y, z])

julia> f = 3*z^3+2*x*y+1
2*x*y + 3*z^3 + 1

julia> terms(f)
terms iterator of 3*z^3 + 2*x*y + 1

julia> collect(ans)
3-element Vector{fmpq_mpoly}:
 3*z^3
 2*x*y
 1

julia> monomials(f, ordering = lex(R))
monomials iterator of 2*x*y + 3*z^3 + 1

julia> coefficients(f)
coefficients iterator of 3*z^3 + 2*x*y + 1

julia> exponents(f, ordering = neglex(R))
exponents iterator of 1 + 3*z^3 + 2*x*y

julia> coefficients_and_exponents(f)
coefficients and exponents iterator of 3*z^3 + 2*x*y + 1

julia> collect(ans)
3-element Vector{Tuple{fmpq, Vector{Int64}}}:
 (3, [0, 0, 3])
 (2, [1, 1, 0])
 (1, [0, 0, 0])

julia> leading_term(f)
3*z^3

julia> leading_monomial(f, ordering = lex(R))
x*y

julia> leading_exponent(f, ordering = neglex(R))
3-element Vector{Int64}:
 0
 0
 0

julia> leading_coefficient(f)
3

julia> tail(f)
2*x*y + 1

Division With Remainder

The computation of Gröbner (standard) bases relies on multivariate division with remainder which is interesting in its own right. If a monomial ordering $>$ is given, the basic idea is to mimic Euclidean division with remainder, allowing more than one divisor: At each step of the resulting process, this amounts to removing the leading term of the intermediate dividend, using the leading term of some divisor by which it is divisible. In its basic form, the process works well if $>$ is global, but may not terminate, however, for local and mixed orderings. In the latter case, Mora's division algorithm, which relies on a restricted selection strategy for the divisors to be used, comes to our rescue.

We dicuss this in more detail:

First suppose that $>$ is global and let polynomials $g\in K[x]$ and $f_1, \dots, f_r\in K[x]\setminus \{0\}$ be given. In this situation, multivariate division with remainder allows us to compute expressions

\[g = q_1f_1+\dots q_rf_r + h, \; h\in K[x], \;\text{ all }\; q_i \in K[x]\]

such that:

  • $\text{LM}_>(g) \ge \text{LM}_>(q_if_i)$ whenever both sides are nonzero.
  • If $h$ is nonzero, then $\text{LM}_>(h)$ is not divisible by any $\text{LM}_>(f_i)$.

Each such expression is called a standard representation for $g$ with quotients $q_i$ and remainder $h$ (on division by the $f_i$, with respect to $>$). If, at each step of the division process, we allow to remove some term of the current dividend instead of just focusing on its leading term, then the algorithm will return a standard expression in which the remainder is fully reduced. That is, $h$ satisfies the stronger condition below:

  • If $h$ is nonzero, then no term of $h$ is divisible by any $\text{LM}_>(f_i)$.

Without restrictions on $>$, let elements $g\in K[x]_>$ and $f_1, \dots, f_r\in K[x]\setminus \{0\}$ be given. In this situation, Mora division with remainder allows us to compute expressions

\[ug = q_1f_1+\dots q_rf_r + h, \; h\in K[x]_>, \;\text{ all }\; q_i \in K[x]_>\]

such that:

  • $u$ is a unit of $K[x]_>$, that is, $\text{LM}_>(u)=1$.
  • $\text{LM}_>(g) \ge \text{LM}_>(q_if_i)$ whenever both sides are nonzero.
  • If $h$ is nonzero, then $\text{LM}_>(h)$ is not divisible by any $\text{LM}_>(f_i)$.

Each such expression is called a weak standard representation for $g$ with quotients $q_i$ and remainder $h$ (on division by the $f_i$, with respect to $>$). If $g\in K[x]$, we speak of a polynomial weak standard representation if $u$ and the $q_i$ are elements of $K[x].$ Using power series expansions, it makes still sense to speak of fully reduced remainders. However, even if we start from polynomial data, such remainders may not be computable (in finitely many steps).

Note

Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation and the division algorithms extend naturally to $K[x]^p$ and $K[x]_>^p$, respectively.

The OSCAR functions discussed below compute standard representations and polynomial weak standard representations, respectively. In the global case, they always return fully reduced remainders.

reduceMethod
reduce(g::T, F::Vector{T}; 
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

If ordering is global, return the remainder in a standard representation for g on division by the polynomials in F with respect to ordering. Otherwise, return the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.

reduce(G::Vector{T}, F::Vector{T};
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

Return a Vector which contains, for each element g of G, a remainder as above.

Note

In the global case, the returned remainders are fully reduced.

Examples

julia> R, (x, y) = PolynomialRing(QQ, ["x", "y"]);

julia> reduce(y^3, [x^2, x*y-y^3])
x*y

julia> reduce(y^3, [x^2, x*y-y^3], ordering = lex(R))
y^3
julia> R, (z, y, x) = PolynomialRing(QQ, ["z", "y", "x"]);

julia> f1 = y-x^2; f2 = z-x^3;

julia> g = x^3*y-3*y^2*z^2+x*y*z;

julia> reduce(g, [f1, f2], ordering = lex(R))
-3*x^10 + x^6 + x^5
source
reduce_with_quotientsMethod
reduce_with_quotients(g::T, F::Vector{T}; 
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

If ordering is global, return the quotients and the remainder in a standard representation for g on division by the polynomials in F with respect to ordering. Otherwise, return the quotients and the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.

reduce_with_quotients(G::Vector{T}, F::Vector{T}; 
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

Return a Vector which contains, for each element g of G, quotients and a remainder as above.

Note

In the global case, the returned remainders are fully reduced.

Examples

julia> R, (z, y, x) = PolynomialRing(QQ, ["z", "y", "x"]);

julia> f1 = y-x^2; f2 = z-x^3;

julia> g = x^3*y-3*y^2*z^2+x*y*z;

julia> Q, h = reduce_with_quotients(g, [f1, f2], ordering = lex(R));

julia> Q
[-3*y*x^6 - 3*x^8 + x^4 + x^3   -3*z*y^2 - 3*y^2*x^3 + y*x]

julia> h
-3*x^10 + x^6 + x^5

julia> g == Q[1]*f1+Q[2]*f2+h
true

julia> G = [g, x*y^3-3*x^2*y^2*z^2];

julia> Q, H = reduce_with_quotients(G, [f1, f2], ordering = lex(R));

julia> Q
[          -3*y*x^6 - 3*x^8 + x^4 + x^3   -3*z*y^2 - 3*y^2*x^3 + y*x]
[y^2*x - 3*y*x^8 + y*x^3 - 3*x^10 + x^5     -3*z*y^2*x^2 - 3*y^2*x^5]

julia> H
2-element Vector{fmpq_mpoly}:
 -3*x^10 + x^6 + x^5
 -3*x^12 + x^7

julia> G == Q*[f1, f2]+H
true
source
reduce_with_quotients_and_unitMethod
reduce_with_quotients_and_unit(g::T, F::Vector{T};
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

Return the unit, the quotients and the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.

reduce_with_quotients(G::Vector{T}, F::Vector{T};
      ordering::MonomialOrdering = default_ordering(parent(F[1]))) where {T <: MPolyElem}

Return a Vector which contains, for each element g of G, a unit, quotients, and a remainder as above.

Note

In the global case, a standard representation with a fully reduced remainder is computed.

Examples

julia> R, (x, y, z) = PolynomialRing(QQ, ["x", "y", "z"]);

julia> f1 = x^2+x^2*y; f2 = y^3+x*y*z; f3 = x^3*y^2+z^4;

julia> g = x^3*y+x^5+x^2*y^2*z^2+z^6;

julia> u, Q, h = reduce_with_quotients_and_unit(g, [f1,f2, f3], ordering = negdegrevlex(R))
([y+1], [x^3-x*y^2*z^2+x*y+y^2*z^2 0 y*z^2+z^2], 0)

julia> u*g == Q[1]*f1+Q[2]*f2+Q[3]*f3+h
true

julia> G = [g, x*y^3-3*x^2*y^2*z^2];

julia> U, Q,  H = reduce_with_quotients_and_unit(G, [f1, f2, f3], ordering = lex(R));

julia> U
[1   0]
[0   1]

julia> H
2-element Vector{fmpq_mpoly}:
 -z^9 + z^7 + z^6 + z^4
 -3*z^7 + z^6

julia> U*G == Q*[f1, f2, f3]+H
true
source

Gröbner and Standard Bases

Still keeping the notation introduced at the beginning of this section, let $G$ be a subset of $K[x]_>$. Then the leading ideal of $G$ is the ideal of $K[x]$ defined by

\[\text{L}_>(G)=\langle \text{LT}_>(g) \mid g\in G\setminus\{0\}\rangle\subset K[x].\]

A finite subset $G$ of an ideal $I\subset K[x]_>$ is called a standard basis of $I$ (with respect to $>$) if $\text{L}_>(G) = \text{L}_>(I)$. A finite subset of $K[x]_>$ is a standard basis if it is a standard basis of the ideal it generates. A standard basis with respect to a global monomial ordering is also called a Gröbner basis.

Note

Every standard basis of $I$ generates $I$.

Note

Gröbner bases (standard bases) can be computed using Buchberger's algorithm (Buchberger's algorithm as enhanced by Mora).

We call a standard basis $G = \{g_1,\dots, g_r\}\subset K[x]_>\setminus \{0\}$ minimal if $\text{LM}_>(g_i)\neq \text{LM}_>(g_j)$ for $i\neq j$.

Note

The definition of minimal above deviates from the definition in most textbooks as we do not ask that the leading coefficients of the standard basis elements are 1.

Note

The standard bases returned by OSCAR are always minimal in the sense above.

We call a standard basis $G = \{g_1,\dots, g_r\}$ with respect to a global monomial ordering reduced if it is minimal and no term of $g_i$ i s divisible by $\text{LM}_>(g_j)$, for $i\neq j$. Using power series expansions, we may extend this notion to local and mixed orderings. However, while reduced standard bases can be computed in the global case, they may not be computable (in finitely many steps) in the other cases.

Note

Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation and results extend naturally to submodules of $K[x]_>^p$.

Here are the relevant OSCAR functions for computing Gröbner and standard bases. The elements of a computed basis can be retrieved by using the elements function or and its alias gens.

groebner_basisMethod
groebner_basis(I::MPolyIdeal;
  ordering::MonomialOrdering = default_ordering(base_ring(I)),
  complete_reduction::Bool = false, algorithm::Symbol = :buchberger)

If ordering is global, return a Gröbner basis of I with respect to ordering. algorithm can be set to :buchberger (Singular's Buchberger algorithm), :fglm (compute first via a "good" monomial ordering, then convert to the chosen ordering via the FGLM algorithm), :f4 (msolve's implementation of Faugère's F4 algorithm).

Note

The returned Gröbner basis is reduced if complete_reduction = true.

Examples

julia> R, (x, y, z) = PolynomialRing(QQ, ["x", "y", "z"]);

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

julia> G = groebner_basis(I)
Gröbner basis with elements
1 -> y^2 - x*z
2 -> x*y - z
3 -> x^2 - y
with respect to the ordering
degrevlex([x, y, z])

julia> elements(G)
3-element Vector{fmpq_mpoly}:
 -x*z + y^2
 x*y - z
 x^2 - y

julia> elements(G) == gens(G)
true

julia> groebner_basis(I, ordering = lex(R))
Gröbner basis with elements
1 -> y^3 - z^2
2 -> x*z - y^2
3 -> x*y - z
4 -> x^2 - y
with respect to the ordering
lex([x, y, z])
julia> R, (x, y) = GradedPolynomialRing(QQ, ["x", "y"], [1, 3]);

julia> I = ideal(R, [x*y-3*x^4,y^3-2*x^6*y]);

julia> groebner_basis(I)
Gröbner basis with elements
1 -> 3*x^4 - x*y
2 -> 2*x^3*y^2 - 3*y^3
3 -> x*y^3
4 -> y^4
with respect to the ordering
wdegrevlex([x, y], [1, 3])
source
standard_basisMethod
standard_basis(I::MPolyIdeal;
  ordering::MonomialOrdering = default_ordering(base_ring(I)),
  complete_reduction::Bool = false, algorithm::Symbol = :buchberger)

Return a standard basis of I with respect to ordering. algorithm can be set to :singular (Singular's Buchberger (resp. Mora) algorithm), :fglm (compute first via a "good" monomial ordering, then convert to the chosen ordering via the FGLM algorithm), :f4 (msolve's implementation of Faugère's F4 algorithm).

Note

The returned standard basis is reduced if ordering is global and complete_reduction = true.

Examples

julia> R,(x,y) = PolynomialRing(QQ, ["x","y"]);

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

julia> standard_basis(I, ordering = negdegrevlex(R))
Standard basis with elements
1 -> x
2 -> y
with respect to the ordering
negdegrevlex([x, y])
source

Gröbner Bases with transformation matrix

groebner_basis_with_transformation_matrixMethod
groebner_basis_with_transformation_matrix(I::MPolyIdeal;
  ordering::MonomialOrdering = default_ordering(base_ring(I)),
  complete_reduction::Bool=false)

Return a pair G, T, say, where G is a Gröbner basis of I with respect to ordering, and T is a transformation matrix from gens(I) to G. That is, gens(I)*T == G.

Note

The returned Gröbner basis is reduced if complete_reduction = true.

Examples

julia> R,(x,y) = PolynomialRing(QQ,["x","y"]);

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

julia> G, T = groebner_basis_with_transformation_matrix(I)
(Gröbner basis with elements
1 -> x*y^2 - 1
2 -> x^3 + x*y + y^2
3 -> y^4 + x^2 + y
with respect to the ordering
degrevlex([x, y]), [1 0 -x^2-y; 0 1 y^2])

julia> gens(I)*T == gens(G)
true
source
standard_basis_with_transformation_matrixMethod
standard_basis_with_transformation_matrix(I::MPolyIdeal;
  ordering::MonomialOrdering = default_ordering(base_ring(I)),
  complete_reduction::Bool=false)

Return a pair G, T, say, where G is a standard basis of I with respect to ordering, and T is a transformation matrix from gens(I) to G. That is, gens(I)*T == G.

Note

The returned Gröbner basis is reduced if ordering is a global monomial odering and complete_reduction = true.

Examples

julia> R,(x,y) = PolynomialRing(QQ,["x","y"]);

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

julia> G, T = standard_basis_with_transformation_matrix(I, ordering=neglex(R))
(Standard basis with elements
1 -> 1 - x*y^2
with respect to the ordering
neglex([x, y]), [-1; 0])

julia> gens(I)*T == gens(G)
true
source

Gröbner Basis Conversions

fglmMethod
fglm(G::IdealGens; ordering::MonomialOrdering)

Converts a Groebner basis G w.r.t. a given global monomial ordering for <G> to a Groebner basis H w.r.t. another monomial ordering ordering for <G>.

NOTE: fglm assumes that G is a reduced Gröbner basis (i.e. w.r.t. a global monomial ordering) and that ordering is a global monomial ordering.

Examples

julia> R, (x1, x2, x3, x4) = PolynomialRing(GF(101), ["x1", "x2", "x3", "x4"])
(Multivariate Polynomial Ring in x1, x2, x3, x4 over Galois field with characteristic 101, gfp_mpoly[x1, x2, x3, x4])

julia> J = ideal(R, [x1+2*x2+2*x3+2*x4-1,
       x1^2+2*x2^2+2*x3^2+2*x4^2-x1,
       2*x1*x2+2*x2*x3+2*x3*x4-x2,
       x2^2+2*x1*x3+2*x2*x4-x3
       ])
ideal(x1 + 2*x2 + 2*x3 + 2*x4 + 100, x1^2 + 100*x1 + 2*x2^2 + 2*x3^2 + 2*x4^2, 2*x1*x2 + 2*x2*x3 + 100*x2 + 2*x3*x4, 2*x1*x3 + x2^2 + 2*x2*x4 + 100*x3)

julia> groebner_basis(J, ordering=degrevlex(R), complete_reduction=true)
Gröbner basis with elements
1 -> x1 + 2*x2 + 2*x3 + 2*x4 + 100
2 -> x3^2 + 2*x2*x4 + 19*x3*x4 + 76*x4^2 + 72*x2 + 86*x3 + 42*x4
3 -> x2*x3 + 99*x2*x4 + 40*x3*x4 + 11*x4^2 + 65*x2 + 58*x3 + 30*x4
4 -> x2^2 + 2*x2*x4 + 30*x3*x4 + 45*x4^2 + 43*x2 + 72*x3 + 86*x4
5 -> x3*x4^2 + 46*x4^3 + 28*x2*x4 + 16*x3*x4 + 7*x4^2 + 58*x2 + 63*x3 + 15*x4
6 -> x2*x4^2 + 67*x4^3 + 56*x2*x4 + 58*x3*x4 + 45*x4^2 + 14*x2 + 86*x3
7 -> x4^4 + 65*x4^3 + 26*x2*x4 + 47*x3*x4 + 71*x4^2 + 37*x2 + 79*x3 + 100*x4
with respect to the ordering
degrevlex([x1, x2, x3, x4])

julia> fglm(J.gb[degrevlex(R)], ordering=lex(R))
Gröbner basis with elements
1 -> x4^8 + 36*x4^7 + 95*x4^6 + 39*x4^5 + 74*x4^4 + 7*x4^3 + 45*x4^2 + 98*x4
2 -> x3 + 53*x4^7 + 93*x4^6 + 74*x4^5 + 26*x4^4 + 56*x4^3 + 15*x4^2 + 88*x4
3 -> x2 + 25*x4^7 + 57*x4^6 + 13*x4^5 + 16*x4^4 + 78*x4^3 + 31*x4^2 + 16*x4
4 -> x1 + 46*x4^7 + 3*x4^6 + 28*x4^5 + 17*x4^4 + 35*x4^3 + 9*x4^2 + 97*x4 + 100
with respect to the ordering
lex([x1, x2, x3, x4])
source
Gröbner walks

Hilbert-driven
Expert function for computing Gröbner bases

With many adjustable keyword arguments, the following function provides low-level implementations of various versions of the Gröbner basis algorithm. Use these functions only if you know what you are doing.

f4Method
f4(I::MPolyIdeal, <keyword arguments>)

Compute a Gröbner basis of I with respect to degrevlex using Faugère's F4 algorithm. See Jean-Charles Faugère (1999) for more information.

Note

At current state only prime fields of characteristic 0 < p < 2^{31} are supported.

Possible keyword arguments

  • initial_hts::Int=17: initial hash table size log_2.
  • nr_thrds::Int=1: number of threads for parallel linear algebra.
  • max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
  • la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
  • eliminate::Int=0: size of first block of variables to be eliminated.
  • complete_reduction::Bool=true: compute a reduced Gröbner basis for I
  • info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).

Examples

julia> R,(x,y,z) = PolynomialRing(GF(101), ["x","y","z"], ordering=:degrevlex)
(Multivariate Polynomial Ring in x, y, z over Galois field with characteristic 101, gfp_mpoly[x, y, z])

julia> I = ideal(R, [x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])
ideal(x + 2*y + 2*z + 100, x^2 + 2*y^2 + 2*z^2 + 100*x, 2*x*y + 2*y*z + 100*y)

julia> f4(I)
Gröbner basis with elements
1 -> x + 2*y + 2*z + 100
2 -> y*z + 82*z^2 + 10*y + 40*z
3 -> y^2 + 60*z^2 + 20*y + 81*z
4 -> z^3 + 28*z^2 + 64*y + 13*z
with respect to the ordering
degrevlex([x, y, z])

julia> isdefined(I, :gb)
true
source

Leading Ideals

leading_idealMethod

leadingideal(G::Vector{T}; ordering::MonomialOrdering = defaultordering(parent(G[1]))) where { T <: MPolyElem }

Return the leading ideal of G with respect to ordering.

Examples

julia> R, (x, y) = PolynomialRing(QQ, ["x", "y"])
(Multivariate Polynomial Ring in x, y over Rational Field, fmpq_mpoly[x, y])

julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=degrevlex(R))
ideal(x*y^2, y^5)

julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=lex(R))
ideal(x*y^2, x^3)
source
leading_idealMethod
leading_ideal(I::MPolyIdeal; ordering::MonomialOrdering = default_ordering(base_ring(I)))

Return the leading ideal of I with respect to ordering.

Examples

julia> R, (x, y) = PolynomialRing(QQ, ["x", "y"])
(Multivariate Polynomial Ring in x, y over Rational Field, fmpq_mpoly[x, y])

julia> I = ideal(R,[x*y^2-3*x, x^3-14*y^5])
ideal(x*y^2 - 3*x, x^3 - 14*y^5)

julia> L = leading_ideal(I, ordering=degrevlex(R))
ideal(x*y^2, x^4, y^5)

julia> L = leading_ideal(I, ordering=lex(R))
ideal(y^7, x*y^2, x^3)
source

Normal Forms

Given a polynomial $g\in K[x]$, an ideal $I\subset K[x]$, and a global monomial ordering $>$ on the monomials in $x$, the fully reduced remainder $h$ in a standard expression on division by the elements of a Gröbner basis of $I$ with respect to $>$ is uniquely determined by $g$, $I$, and $>$ (and does not depend on the choice of Gröbner basis). We refer to such a remainder as the normal form of $g$ mod $I$, with respect to $>$.

normal_formMethod
normal_form(g::T, I::MPolyIdeal; 
  ordering::MonomialOrdering = default_ordering(base_ring(I))) where { T <: MPolyElem }

Compute the normal form of g mod I with respect to ordering.

normal_form(G::Vector{T}, I::MPolyIdeal; 
  ordering::MonomialOrdering=default_ordering(base_ring(I))) where { T <: MPolyElem }

Return a Vector which contains for each element g of G a normal form as above.

Examples

julia> R,(a,b,c) = PolynomialRing(QQ,["a","b","c"])
(Multivariate Polynomial Ring in a, b, c over Rational Field, fmpq_mpoly[a, b, c])

julia> J = ideal(R,[-1+c+b,-1+b+c*a+2*a*b])
ideal(b + c - 1, 2*a*b + a*c + b - 1)

julia> gens(groebner_basis(J))
2-element Vector{fmpq_mpoly}:
 b + c - 1
 a*c - 2*a + c

julia> normal_form(-1+c+b+a^3, J)
a^3

julia> R,(a,b,c) = PolynomialRing(QQ,["a","b","c"])
(Multivariate Polynomial Ring in a, b, c over Rational Field, fmpq_mpoly[a, b, c])

julia> A = [-1+c+b+a^3,-1+b+c*a+2*a^3,5+c*b+c^2*a]
3-element Vector{fmpq_mpoly}:
 a^3 + b + c - 1
 2*a^3 + a*c + b - 1
 a*c^2 + b*c + 5

julia> J = ideal(R,[-1+c+b,-1+b+c*a+2*a*b])
ideal(b + c - 1, 2*a*b + a*c + b - 1)

julia> gens(groebner_basis(J))
2-element Vector{fmpq_mpoly}:
 b + c - 1
 a*c - 2*a + c

julia> normal_form(A, J)
3-element Vector{fmpq_mpoly}:
 a^3
 2*a^3 + 2*a - 2*c
 4*a - 2*c^2 - c + 5
source

Syzygies

We refer to the section on modules for more on syzygies.

syzygy_generatorsMethod
syzygy_generators(G::Vector{<:MPolyElem})

Return generators for the syzygies on the polynomials given as elements of G.

Examples

julia> R, (x, y) = PolynomialRing(QQ, ["x", "y"])
(Multivariate Polynomial Ring in x, y over Rational Field, fmpq_mpoly[x, y])

julia> S = syzygy_generators([x^3+y+2,x*y^2-13*x^2,y-14])
3-element Vector{FreeModElem{fmpq_mpoly}}:
 (-y + 14)*e[2] + (-13*x^2 + x*y^2)*e[3]
 (-169*y + 2366)*e[1] + (-13*x*y + 182*x - 196*y + 2744)*e[2] + (13*x^2*y^2 - 2548*x^2 + 196*x*y^2 + 169*y + 338)*e[3]
 (-13*x^2 + 196*x)*e[1] + (-x^3 - 16)*e[2] + (x^4*y + 14*x^4 + 13*x^2 + 16*x*y + 28*x)*e[3]
source