# 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)$.

## Default Orderings

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) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[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 3 variables over QQ
julia> default_ordering(F)
degrevlex([x, y, z])*lex([gen(1), gen(2)])
julia> S, _ = grade(R, [1, 2, 3])
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])
julia> default_ordering(S)
wdegrevlex([x, y, z], [1, 2, 3])
```

## Monomials, Terms, and More

Here are examples which indicate how to recover monomials, terms, and more from a given polynomial.

```
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 = 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{QQMPolyRingElem}:
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{QQFieldElem, 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
```

```
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> F = free_module(R, 3)
Free module of rank 3 over Multivariate polynomial ring in 2 variables over QQ
julia> f = (5*x*y^2-y^10+3)*F[1]+(4*x^3+2*y) *F[2]+16*x*F[3]
(5*x*y^2 - y^10 + 3)*e[1] + (4*x^3 + 2*y)*e[2] + 16*x*e[3]
julia> default_ordering(F)
degrevlex([x, y])*lex([gen(1), gen(2), gen(3)])
julia> collect(terms(f))
6-element Vector{FreeModElem{QQMPolyRingElem}}:
-y^10*e[1]
4*x^3*e[2]
5*x*y^2*e[1]
16*x*e[3]
2*y*e[2]
3*e[1]
julia> collect(terms(f, ordering = lex(F)*lex(R)))
6-element Vector{FreeModElem{QQMPolyRingElem}}:
5*x*y^2*e[1]
-y^10*e[1]
3*e[1]
4*x^3*e[2]
2*y*e[2]
16*x*e[3]
julia> tail(f)
(5*x*y^2 + 3)*e[1] + (4*x^3 + 2*y)*e[2] + 16*x*e[3]
julia> leading_exponent(f)
([0, 10], 1)
julia> leading_exponent(f, ordering = lex(F)*lex(R))
([1, 2], 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 for local and mixed orderings. In the latter case, Mora's division algorithm, which relies on a more restricted selection strategy for the divisors to be used, comes to our rescue.

We discuss 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.

`reduce`

— Method```
reduce(g::T, F::Vector{T};
ordering::MonomialOrdering = default_ordering(parent(F[1])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

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])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

Return a `Vector`

which contains, for each element `g`

of `G`

, a remainder as above.

The returned remainders are fully reduced if `complete_reduction`

is set to `true`

and `ordering`

is global.

The reduction strategy behind the `reduce`

function and the reduction strategy behind the functions `reduce_with_quotients`

and `reduce_with_quotients_and_unit`

differ. As a consequence, the computed remainders may differ.

**Examples**

```
julia> R, (z, y, x) = polynomial_ring(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
```

```
julia> R, (x, y, z) = polynomial_ring(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> reduce(g, [f1, f2, f3], ordering = lex(R))
x^5 + x^3*y + x^2*y^2*z^2 + z^6
julia> reduce(g, [f1,f2, f3], ordering = lex(R), complete_reduction = true)
x^5 - x^3 + y^6 + z^6
```

`reduce_with_quotients`

— Method```
reduce_with_quotients(g::T, F::Vector{T};
ordering::MonomialOrdering = default_ordering(parent(F[1])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

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])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

Return a `Vector`

which contains, for each element `g`

of `G`

, quotients and a remainder as above.

The returned remainders are fully reduced if `complete_reduction`

is set to `true`

and `ordering`

is global.

**Examples**

```
julia> R, (x, y, z) = polynomial_ring(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> Q, h = reduce_with_quotients(g, [f1,f2, f3], ordering = lex(R));
julia> h
x^5 - x^3 + y^6 + z^6
julia> g == Q[1]*f1+Q[2]*f2+Q[3]*f3+h
true
```

`reduce_with_quotients_and_unit`

— Method```
reduce_with_quotients_and_unit(g::T, F::Vector{T};
ordering::MonomialOrdering = default_ordering(parent(F[1])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

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_and_unit(G::Vector{T}, F::Vector{T};
ordering::MonomialOrdering = default_ordering(parent(F[1])), complete_reduction::Bool = false) where T <: MPolyRingElem
```

Return a `Vector`

which contains, for each element `g`

of `G`

, a unit, quotients, and a remainder as above.

The returned remainders are fully reduced if `complete_reduction`

is set to `true`

and `ordering`

is global.

The reduction strategy behind the `reduce`

function and the reduction strategy behind the functions `reduce_with_quotients`

and `reduce_with_quotients_and_unit`

differ. As a consequence, the computed remainders may differ.

**Examples**

```
julia> R, (x, y, z) = polynomial_ring(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 = lex(R));
julia> u
[1]
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 = negdegrevlex(R));
julia> U
[y + 1 0]
[ 0 y + 1]
julia> Q
[ x^3 - x*y^2*z^2 + x*y + y^2*z^2 0 y*z^2 + z^2]
[x*y*z^2 + y^3*z - 3*y^2*z^2 - y*z -x^2*y*z - x^2*z + x*y + x 0]
julia> H
2-element Vector{QQMPolyRingElem}:
0
0
julia> U*G == Q*[f1, f2, f3]+H
true
```

## Computing Gröbner/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$ is 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 its alias `gens`

.

`groebner_basis`

— Method```
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`

.

The keyword `algorithm`

can be set to

`:buchberger`

(implementation of Buchberger's algorithm in*Singular*),`:hilbert`

(implementation of a Hilbert driven Gröbner basis computation in*Singular*),`:fglm`

(implementation of the FGLM algorithm in*Singular*), and`:f4`

(implementation of Faugère's F4 algorithm in the*msolve*package).

See the description of the functions `groebner_basis_hilbert_driven`

, `fglm`

, and `f4`

in the OSCAR documentation for some more details and for restrictions on the input data when using these versions of the standard basis algorithm.

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

.

**Examples**

```
julia> R, (x, y, z) = polynomial_ring(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{QQMPolyRingElem}:
-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) = graded_polynomial_ring(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])
```

```
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> V = [3*x^3*y+x^3+x*y^3+y^2*z^2, 2*x^3*z-x*y-x*z^3-y^4-z^2,
2*x^2*y*z-2*x*y^2+x*z^2-y^4];
julia> I = ideal(R, V);
julia> G = groebner_basis(I, ordering = lex(R), algorithm = :fglm);
julia> length(G)
8
julia> total_degree(G[8])
34
julia> leading_coefficient(G[8])
-91230304237130414552564280286681870842473427917231798336639893796481988733936505735341479640589040146625319419037353645834346047404145021391726185993823650399589880820226804328750
```

`standard_basis`

— Method```
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`

.

The keyword `algorithm`

can be set to

`:buchberger`

(implementation of Buchberger's algorithm in*Singular*),`:hilbert`

(implementation of a Hilbert driven Gröbner basis computation in*Singular*),`:fglm`

(implementation of the FGLM algorithm in*Singular*), and`:f4`

(implementation of Faugère's F4 algorithm in the*msolve*package).

See the description of the functions `groebner_basis_hilbert_driven`

, `fglm`

, and `f4`

in the OSCAR documentation for some more details and for restrictions on the input data when using these versions of the standard basis algorithm.

The returned standard basis is reduced if `ordering`

is `global`

and `complete_reduction = true`

.

**Examples**

```
julia> R,(x,y) = polynomial_ring(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`

— Method```
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`

.

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

.

**Examples**

```
julia> R,(x,y) = polynomial_ring(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
```

`standard_basis_with_transformation_matrix`

— Method```
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`

.

The returned Gröbner basis is reduced if `ordering`

is a global monomial odering and `complete_reduction = true`

.

**Examples**

```
julia> R,(x,y) = polynomial_ring(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
```

### Gröbner Basis Conversion Algorithms

The performance of Buchberger's Gröbner basis algorithm is sensitive to the choice of monomial ordering. A Gröbner basis computation with respect to a less favorable ordering such as `lex`

may easily run out of time or memory even in cases where a Gröbner basis computation with respect to a more efficient ordering such as `degrevlex`

is very well feasible. *Gröbner basis conversion algorithms* and the *Hilbert driven Buchberger algorithm* discussed subsequently take their cue from this observation.

Gröbner basis conversion algorithms proceed along the following lines:

- Given an ideal $I$ of a multivariate polynomial ring over a field and a slow
`destination_ordering`

, compute a Gröbner basis for $I$ with respect to an appropriately chosen fast`start_ordering`

. - Convert the result to a Gröbner basis with respect to the given slow
`destination_ordering`

.

The algorithms differ in how they perform the conversion.

#### The FGLM Algorithm

`fglm`

— Method```
fglm(I::MPolyIdeal; start_ordering::MonomialOrdering = default_ordering(base_ring(I)),
destination_ordering::MonomialOrdering)
```

Given a **zero-dimensional** ideal `I`

, return the reduced Gröbner basis of `I`

with respect to `destination_ordering`

.

Both `start_ordering`

and `destination_ordering`

must be global and the base ring of `I`

must be a polynomial ring over a field.

The function implements the Gröbner basis conversion algorithm by **F**augère, **G**ianni, **L**azard, and **M**ora. See [FGLM93] for more information.

**Examples**

```
julia> R, (a, b, c, d, e) = polynomial_ring(QQ, ["a", "b", "c", "d", "e"]);
julia> f1 = a+b+c+d+e;
julia> f2 = a*b+b*c+c*d+a*e+d*e;
julia> f3 = a*b*c+b*c*d+a*b*e+a*d*e+c*d*e;
julia> f4 = b*c*d+a*b*c*e+a*b*d*e+a*c*d*e+b*c*d*e;
julia> f5 = a*b*c*d*e-1;
julia> I = ideal(R, [f1, f2, f3, f4, f5]);
julia> G = fglm(I, destination_ordering = lex(R));
julia> length(G)
8
julia> total_degree(G[8])
60
julia> leading_coefficient(G[8])
83369589588385815165248207597941242098312973356252482872580035860533111990678631297423089011608753348453253671406641805924218003925165995322989635503951507226650115539638517111445927746874479234
```

#### Gröbner Walk Algorithms

### The Hilbert driven Buchberger Algorithm

Calling the functions `standard_basis`

and `groebner_basis`

with `algorithm = :hilbert`

in OSCAR triggers a version of the Hilbert driven Gröbner basis algorithm which proceeds along the following lines.

Given an ideal $I$ of a multivariate polynomial ring $R$ over a field $K$ and a slow

`destination_ordering`

, check whether $I$ is homogeneous with respect to the standard $\mathbb Z$-grading on $R$. If so, set`start_ordering`

to`degrevlex`

and go to step 3.Check whether there exists a $\mathbb Z$-grading on $R$ with positive weights such that $I$ is homogeneous with respect to this grading. If so, let

`start_ordering`

be the corresponding weight ordering. If not, go to step 5.Compute a Gröbner basis of $I$ with respect to

`start_ordering`

and use this Gröbner basis to compute the Hilbert function of $R/I$.Compute a Gröbner basis with respect to

`destination_ordering`

, proceeding by increasing (weighted) degree, and skipping all further Buchberger tests in a given (weighted) degree as soon as the leading terms found so far account for the Hilbert function in that (weighted) degree. Return the computed Gröbner basis.Extend $R$ to a polynomial ring $S$ by appending an extra variable, equip $S$ with the standard $\mathbb Z$-grading, and let $I^{h}\subset S$ be the homogenization of $I$ with respect to the extra variable. Compute a Gröbner basis of $I$ with respect to

`degrevlex`

on`R`

, and homogenize its elements to obtain a Gröbner basis of $I^{h}$ with respect to`degrevlex`

on $S$. Use the latter basis to compute the Hilbert function of $S/I^{h}$. Extend`destination_ordering`

to a block ordering on`S`

. Following the recipe in step 4, compute a Gröbner basis of $S/I^{h}$ with respect to the extended ordering. Return the dehomogenization of this basis with respect to the extra variable.

If the characteristic of $K$ is zero, by semi-continuity of the Hilbert function, it is sufficient to perform step 3 for the reduction of $I$ modulo a conveniently chosen prime number rather than for $I$ itself.

If appropriate weights and/or the Hilbert function with respect to appropriate weights are already known to the user, this information can be entered when calling the Hilbert driven Gröbner basis algorithm as follows:

`groebner_basis_hilbert_driven`

— Method```
groebner_basis_hilbert_driven(I::MPolyIdeal{P}; destination_ordering::MonomialOrdering,
complete_reduction::Bool = false,
weights::Vector{Int} = ones(Int, ngens(base_ring(I))),
hilbert_numerator::Union{Nothing, ZZPolyRingElem} = nothing)
where {P <: MPolyRingElem}
```

Return a Gröbner basis of `I`

with respect to `destination_ordering`

.

The function implements a version of the Hilbert driven Gröbner basis algorithm. See the corresponding section of the OSCAR documentation for some details.

All weights must be positive. If no weight vector is entered by the user, all weights are set to 1. An error is thrown if the generators of `I`

are not homogeneous with respect to the corresponding (weighted) degree.

If $R$ denotes the parent ring of $I$, and $p, q\in\mathbb Z[t]$ are polynomials such that $p/q$ represents the Hilbert series of $R/I$ as a rational function with denominator $q = (1-t^{w_1})\cdots (1-t^{w_n}),$ where $n$ is the number of variables of $R$, and $w_1, \dots, w_n$ are the assigned weights, then `hilbert_numerator`

is meant to be $p$. If this numerator is not entered by the user, it will be computed internally.

**Examples**

```
julia> R, (a, b, c, d, e, f, g) = polynomial_ring(QQ, ["a", "b", "c", "d", "e", "f", "g"]);
julia> V = [-3*a^2+2*f*b+3*f*d, (3*g*b+3*g*e)*a-3*f*c*b,
-3*g^2*a^2-c*b^2*a-g^2*f*e-g^4, e*a-f*b-d*c];
julia> I = ideal(R, V);
julia> o = degrevlex([a, b, c])*degrevlex([d, e, f, g]);
julia> G = groebner_basis_hilbert_driven(I, destination_ordering = o);
julia> length(G)
296
julia> total_degree(G[49])
30
```

```
julia> R, (x, y, z) = polynomial_ring(GF(32003), ["x", "y", "z"]);
julia> f1 = x^2*y+169*y^21+151*x*y*z^10;
julia> f2 = 6*x^2*y^4+x*z^14+3*z^24;
julia> f3 = 11*x^3+5*x*y^10*z^10+2*y^20*z^10+y^10*z^20;
julia> I = ideal(R, [f1, f2,f3]);
julia> W = [10, 1, 1];
julia> GB = groebner_basis_hilbert_driven(I, destination_ordering = lex(R), weights = W);
julia> length(GB)
40
```

```
julia> R, (x, y, z) = polynomial_ring(GF(32003), ["x", "y", "z"]);
julia> f1 = x^2*y+169*y^21+151*x*y*z^10;
julia> f2 = 6*x^2*y^4+x*z^14+3*z^24;
julia> f3 = 11*x^3+5*x*y^10*z^10+2*y^20*z^10+y^10*z^20;
julia> I = ideal(R, [f1, f2,f3]);
julia> W = [10, 1, 1];
julia> S, t = polynomial_ring(ZZ, "t")
(Univariate polynomial ring in t over ZZ, t)
julia> hn = -t^75 + t^54 + t^51 + t^45 - t^30 - t^24 - t^21 + 1
-t^75 + t^54 + t^51 + t^45 - t^30 - t^24 - t^21 + 1
julia> GB = groebner_basis_hilbert_driven(I, destination_ordering = lex(R), weights = W, hilbert_numerator = hn);
julia> length(GB)
40
```

### Faugère's F4 Algorithm

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.

`groebner_basis_f4`

— Method`groebner_basis_f4(I::MPolyIdeal, <keyword arguments>)`

Compute a Gröbner basis of `I`

with respect to `degrevlex`

using Faugère's F4 algorithm. See [Fau99] 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 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) = polynomial_ring(GF(101), ["x","y","z"])
(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[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 generated by
x + 2*y + 2*z + 100
x^2 + 100*x + 2*y^2 + 2*z^2
2*x*y + 2*y*z + 100*y
julia> groebner_basis_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])
```

## Leading Ideals

`leading_ideal`

— Method```
leading_ideal(G::Vector{T}; ordering::MonomialOrdering = default_ordering(parent(G[1])))
where T <: MPolyRingElem
```

Return the leading ideal of `G`

with respect to `ordering`

.

**Examples**

```
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=degrevlex(R))
Ideal generated by
x*y^2
y^5
julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=lex(R))
Ideal generated by
x*y^2
x^3
```

`leading_ideal`

— Method`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) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> I = ideal(R,[x*y^2-3*x, x^3-14*y^5])
Ideal generated by
x*y^2 - 3*x
x^3 - 14*y^5
julia> L = leading_ideal(I, ordering=degrevlex(R))
Ideal generated by
x*y^2
x^4
y^5
julia> L = leading_ideal(I, ordering=lex(R))
Ideal generated by
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`

— Method```
normal_form(g::T, I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I))) where T <: MPolyRingElem
```

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 <: MPolyRingElem
```

Return a `Vector`

which contains for each element `g`

of `G`

a normal form as above.

**Examples**

```
julia> R,(a,b,c) = polynomial_ring(QQ,["a","b","c"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[a, b, c])
julia> J = ideal(R,[-1+c+b,-1+b+c*a+2*a*b])
Ideal generated by
b + c - 1
2*a*b + a*c + b - 1
julia> gens(groebner_basis(J))
2-element Vector{QQMPolyRingElem}:
b + c - 1
a*c - 2*a + c
julia> normal_form(-1+c+b+a^3, J)
a^3
julia> R,(a,b,c) = polynomial_ring(QQ,["a","b","c"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[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{QQMPolyRingElem}:
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 generated by
b + c - 1
2*a*b + a*c + b - 1
julia> gens(groebner_basis(J))
2-element Vector{QQMPolyRingElem}:
b + c - 1
a*c - 2*a + c
julia> normal_form(A, J)
3-element Vector{QQMPolyRingElem}:
a^3
2*a^3 + 2*a - 2*c
4*a - 2*c^2 - c + 5
```

## Syzygies

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

`syzygy_generators`

— Method`syzygy_generators(G::Vector{<:MPolyRingElem})`

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

.

**Examples**

```
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> S = syzygy_generators([x^3+y+2,x*y^2-13*x^2,y-14])
3-element Vector{FreeModElem{QQMPolyRingElem}}:
(-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]
```