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.
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)$.
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 + 1Division 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).
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.
reduce — Methodreduce(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.
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^3julia> 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^5reduce_with_quotients — Methodreduce_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.
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
truereduce_with_quotients_and_unit — Methodreduce_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.
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
trueGrö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.
Every standard basis of $I$ generates $I$.
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$.
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.
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.
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_basis — Methodgroebner_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).
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])standard_basis — Methodstandard_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).
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])Gröbner Bases with transformation matrix
groebner_basis_with_transformation_matrix — Methodgroebner_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.
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)
truestandard_basis_with_transformation_matrix — Methodstandard_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.
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)
trueGröbner Basis Conversions
fglm — Methodfglm(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])Gröbner walks
Hilbert-drivenWith 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.
f4 — Methodf4(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.
At current state only prime fields of characteristic 0 < p < 2^{31} are supported.
Possible keyword arguments
initial_hts::Int=17: initial hash table sizelog_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 if0.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 forIinfo_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)
trueLeading Ideals
leading_ideal — Methodleadingideal(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)leading_ideal — Methodleading_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)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_form — Methodnormal_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 + 5Syzygies
We refer to the section on modules for more on syzygies.
syzygy_generators — Methodsyzygy_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]