# Gröbner Bases for Polynomial Ideals and Applications

Christian Eder, Rafael Mohr, Mohab Safey El Din

► To cite this version:

Christian Eder, Rafael Mohr, Mohab Safey El Din. Gröbner Bases for Polynomial Ideals and Applications. The Computer Algebra System OSCAR: Algorithms and Examples, 32, Springer Nature Switzerland, pp.271-295, 2025, Algorithms and Computation in Mathematics, 978-3-031-62127-7. 10.1007/978-3-031-62127-7_11. hal-04938971

HAL Id: hal-04938971

https://hal.science/hal-04938971v1

Submitted on 27 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Gröbner Bases for Polynomial Ideals and Applications

Christian Eder¹, Rafael Mohr¹,², and Mohab Safey El Din²

¹RPTU Kaiserslautern-Landau, Kaiserslautern, Germany

²Sorbonne Université, Paris, France

**Abstract**

We illustrate OSCAR's capabilities for computing with polynomial ideals using Gröbner bases. We give a detailed overview of the available Gröbner basis algorithms and provide some practical advice on how to use them. Based on this, we illustrate how to compute real solutions to polynomial systems in OSCAR. We then demonstrate with a range of examples from different areas of mathematics where Gröbner bases come into play when trying to answer computational questions.

*Keywords*— Polynomial ideals, Gröbner bases, polynomial system solving

# 1 Introduction

## Gröbner Bases of Polynomial Ideals

Algorithmically manipulating ideals in polynomial rings over fields is, as of today, heavily reliant on the notion of a *Gröbner basis*. Essentially, a Gröbner basis is a special generating set of a polynomial ideal *I* which allows for a membership test for *I* via multivariate polynomial long division. In fact, Gröbner bases let us make all sorts of ideal theoretic operations and invariants computable such as ideal intersection or the dimension of an ideal. Importantly, a Gröbner basis depends crucially on a chosen method to order monomials (a *monomial ordering*) – we need to know which is the leading term of a polynomial when performing a polynomial long division. Some important monomial orders are closely related to different geometric operations: some allow for projections of algebraic sets, some for hyperplane cuts, some give a local and some a global picture of the polynomial ideal at hand. We refer for example to chapter 15 in [Eis95] for a comprehensive introduction to Gröbner bases and to [BW93] for a detailed and comprehensive account of the area.
## How Gröbner Bases Are Used in OSCAR

OSCAR's implementation of polynomial ideals and algorithms operating on them also relies on Gröbner basis computations, mainly through its interfaces to the computer algebra system Singular and to the Gröbner basis library `msolve`. Since Gröbner bases can be quite expensive to compute, each polynomial ideal declared in `OSCAR` has its own Gröbner basis cache, storing lazily a Gröbner basis per monomial ordering when needed and reusing them, if possible, for future computations involving the same polynomial ideal.

An important design goal of `OSCAR`'s ideal theoretic capabilities is that polynomial ideals (and related objects such as quotient algebras) can be manipulated in `OSCAR` purely by typing in the correct ideal theoretic operation without any knowledge for how they are performed under the hood.

On the other hand, `OSCAR` also allows us to compute Gröbner bases explicitly, using a range of algorithms. This can allow the informed user to adapt the computation to their specific problem and hand pick which algorithm to use, for better efficiency.

To illustrate this, consider the problem of computing the Hilbert series of a homogeneous ideal, for example of the twisted cubic in $\mathbb{P}^3$. Of course we can ask `OSCAR` for the Hilbert series directly:

julia> R, (X0, X1, X2, X3) = graded_polynomial-ring(QQ, ["X$i" for i in
  ↦ 0:3]);

julia> I = ideal(R, [X0*X2 - X1^2, X1*X3 - X2^2, X0*X3 - X1*X2]);

julia> A, _ = quo(R, I);

julia> hilbert_series(A)
(2*t^3 - 3*t^2 + 1, (-t + 1)^4)

However, for larger examples the user will observe that this computation slows down considerably. This is because a Gröbner basis over the rational numbers using the famous *Buchberger algorithm* [Buc65] is computed in the background, out of this Gröbner basis the Hilbert series can be extracted (via the *leading monomials* (Definition 2.1) of the computed Gröbner basis, see e.g. Theorem 15.26 in [Eis95]). This computation is done by `Singular`. To speed things up, let us first specialize the problem to a random prime field, over which arithmetic is much easier, this will make all Gröbner basis computations faster than over $\mathbb{Q}$. For a "sufficiently random" prime (i.e. a prime outside of a certain finite subset of primes) the Hilbert series that we obtain will be the same as over $\mathbb{Q}$.

julia> p = next_prime(rand(1:10000))
4783

julia> R, (X0, X1, X2, X3) = graded_polynomial-ring(GF(p), ["X$i" for i in
  ↦ 0:3]);

julia> I = ideal(R, [X0*X2 - X1^2, X1*X3 - X2^2, X0*X3 - X1*X2]);

Now that we are working over a prime field we can use `msolve`'s efficient implementation of the *F4 algorithm* [Fau99] to compute the Gröbner basis that we need. F4 is
generally faster than Buchberger's algorithm. Additionally, `msolve`'s implementation of $F_4$ is limited to finite fields and one specific monomial ordering, but this limitation allows for optimizing the implementation for these settings. For us this limitation is not a problem: We are working over a finite field and, in this case, don't care which ordering is used when computing a Gröbner basis. Here is how we get access to this $F_4$ implementation in `OSCAR`:

julia> gb = groebner_basis_f4(forget_grading(I));

The Hilbert series of an ideal is the same as that of its leading monomial ideal (again, see 2.1 for a definition):

julia> lm_ideal = ideal(R, (leading_monomial).(gens(gb)));

julia> A, _ = quo(R, lm_ideal);

julia> hilbert_series(A)
(2*t^3 - 3*t^2 + 1, (-t + 1)^4)

## This Chapter

This chapter has two parts: In the first part we give an overview of the available Gröbner basis algorithms in `OSCAR`, their use cases and the settings in which they can be applied. We show with another brief example how explicitly using the provided algorithms, rather than just asking `OSCAR` for a Gröbner basis, can lead to faster computations. Using an example, we also briefly describe `msolve`'s capabilities for solving polynomial systems based on Gröbner basis computations.

In the second part we perform computations on polynomial ideals coming from a wide range of mathematical areas. We point out which Gröbner basis computations are performed in the background and where potential computational bottlenecks could lie in similar examples of larger size.

We have tried to keep this chapter as self-contained as possible. While it can be read without knowing anything about Gröbner bases, it is intended for those who have a basic understanding of the subject, like ideals in polynomial rings, want to gain some insight into how they can be computed explicitly in `OSCAR`, where and how they come up in examples of interest and where computational difficulties can lie when working with them.

## 2 Computing Gröbner Bases in `OSCAR`

In this section we discuss the different algorithms available in `OSCAR` for computing Gröbner bases explicitly in more detail. Let us recall the definition of a Gröbner basis, again see the algebraic geometry cornerstones chapter for more details:

**Definition 2.1.** Fix a monomial ordering $\leq$ on $R$, i.e. a total order on the set of monomials in $R$ which is preserved under multiplication and extends the partial ordering given by divisibility.

1. The leading monomial of an element $f \in R$, denoted $\text{lm}(f)$, is the $\leq$-largest monomial in the support of $f$. For a finite set $F \subset R$, denote

$$ \text{lm}(F) = \{\text{lm}(f) \mid f \in F\}. $$
2. For an ideal $I \subset k[x_1, \dots, x_n]$, the leading monomial ideal of $I$, denoted $\text{lm}(I)$, is given by

$$ \text{lm}(I) = \langle \text{lm}(f) \mid f \in I \rangle. $$

3. A Gröbner basis of $I$ w.r.t. $\le$ is a finite set $G \subset I$ such that

$$ \langle \text{lm}(G) \rangle = \text{lm}(I). $$

*Remark 2.1.* Note that the restriction that a monomial ordering extends the partial ordering given by divisibility is equivalent to $1 < m$ for every monomial $m \neq 1$. In certain contexts this is called a *global* monomial ordering whereas the reverse property (i.e. $m < 1$ for every monomial $m \neq 1$) is called a *local* monomial ordering. Working with local monomial orderings is quite different, see e.g. section 10.6 in [BW93]. In this chapter, we will consider computations only with global monomial orderings.

From this definition, one can conclude that different Gröbner bases for different monomial orderings share many properties. For example, using the third item in the above definition, any Gröbner basis provides a membership test for the ideal it generates. Certain other ideal theoretic invariants may also be extracted out of any given Gröbner basis (such as, for example, the dimension or Hilbert series).

On the other hand, certain ideal theoretic operations may require Gröbner basis computations with specific monomial orderings. For example, the `eliminate` command that we will frequently use in the second part of this chapter requires the computation of a Gröbner basis w.r.t. a block ordering (see e.g. [BW93, Exercise 4.61]): we choose two monomial orderings on two disjoint blocks of variables. Then we compare two monomials by comparing lexicographically the two blocks of these monomials, corresponding to the two blocks of variables, using the two underlying monomial orderings. Doing this explicitly in `OSCAR` with two blocks of the `degrevlex` monomial ordering looks like this:

julia> R, (x, y, z) = polynomial ring(QQ, ["x", "y", "z");

julia> o = degrevlex([x, y])*degrevlex([z]);

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

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

julia> eliminate(I, [x,y]) # internally computes the above Gröbner basis
Ideal generated by
  z^6 - 4*z^4 + 4*z^3 - z^2
Through Robbiano’s classification of monomial orderings as matrix orderings [Rob86], every possible monomial ordering is available in OSCAR, since we can define matrix orderings in OSCAR.

Depending on the chosen monomial ordering, Gröbner bases differ not only in their properties but also their computation with the classical Buchberger algorithm [Buc65] can wary wildly in difficulty, even for the same ideal. In many cases, computing a Gröbner basis with Buchberger’s algorithm is easiest using the *degree reverse lexicographical* ordering (herein referred to as the DRL ordering, called *degrevlex* in OSCAR): Two monomials are compared by first comparing their degree, then, if these two degrees are equal, one compares the monomials lexicographically starting with the last variable but reverses the outcome of this comparison. The heuristic that Gröbner bases for the DRL ordering are usually easiest to compute is also justified in certain complexity theoretic results for computing Gröbner bases: In generic coordinates, the degrees of the elements in a DRL Gröbner basis are bounded by the so-called *regularity* of the ideal, see e.g. [BM92]. For certain ideals, this improves the well-known general doubly exponential (in the number of variables) complexity for computing a Gröbner basis to a singly exponential complexity for computing a DRL Gröbner basis.

That is why OSCAR uses DRL as a default if we don’t explicitly specify another ordering.
Continuing the previous example:

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

As a general rule of thumb, when a Gröbner basis is required, one should use DRL whenever possible, and avoid the use of block orderings as much as possible (although eliminating a subset of the variables using block orderings is often hard to avoid in practice, as we will see in the next section).

Let us now discuss the different algorithms for computing Gröbner bases available in OSCAR and their use cases. A popular modification of Buchberger's algorithm, Faugère's F4 algorithm [Fau99], is available in OSCAR through the C-library `msolve` [BES21], which also enables the computation of real solutions to polynomial equations, as we will see later. F4 works by linearizing the problem of computing Gröbner bases in a certain way, which enables the use of fast linear algebra algorithms for computing Gröbner bases. `msolve` itself is accessible via the Julia package `AlgebraicSolving.jl`, which is maintained by the authors of this chapter. This package in turn is integrated into OSCAR. At the time of writing of this chapter, signature-based Gröbner basis computations (see e.g. [EF17] for a survey) are already part of `AlgebraicSolving.jl`, and a multi-modular method for computing Gröbner bases over the rational numbers is part of `msolve` and soon to be integrated into `AlgebraicSolving.jl`.

The F4 implementation in `msolve` is substantially faster than the available implementation of Buchberger's algorithm, both because of the inherent efficiency of F4 over Buchberger's algorithm and because of its more specialized nature: At the time of writing of this chapter, it only accepts ideals over fields of the form $\mathbb{Z}/p\mathbb{Z}$ with $p < 2^{31}$ and
computes Gröbner bases only for the DRL monomial ordering. It can also be used to eliminate the last *k* variables from an ideal, in which case it returns a DRL Gröbner basis of the corresponding elimination ideal.

The two other Gröbner basis algorithms (FGLM [FGLM93] and a Hilbert driven algorithm [Tra96]) available in OSCAR are useful if a Gröbner basis for a monomial ordering other than DRL is required. They use a “change of ordering” strategy: First compute a Gröbner basis for an “easy” ordering (usually DRL) via Buchberger’s algorithm or F4, then convert that Gröbner basis into one for the desired target ordering.

The four Gröbner basis algorithms available in OSCAR, together with the restrictions on their input, are summarized in table 1.

Each implemented algorithm is available to the user in two different ways:

1. By calling the function `groebner_basis` with the appropriate algorithm keyword, e.g. to use the F4 algorithm to compute a Gröbner basis for a polynomial ideal I we may call

```
groebner_basis(I, algorithm = :f4)
```

2. By calling directly the function corresponding to a specific algorithm e.g. to perform the same computation as in the previous item we may call

```
groebner_basis_f4(I)
```

The second option offers more user customization options than the first one but requires more work to be done by the user. For example the Hilbert driven algorithm to compute Gröbner bases, as such, works only for ideals homogeneous w.r.t. suitable weights. With a certain homogenization-dehomogenization strategy, this algorithm becomes available also for non-graded ideals.

When we choose this algorithm by calling `groebner_basis(I, algorithm = :hilb]ert)`, then OSCAR will take care of ensuring this homogeneity-condition for us. When we call `groebner_basis_hilbert_driven` ourselves, we are the ones who have to ensure that the input ideal is given by homogeneous generators (w.r.t. suitable weights).

Depending on the target ordering a change-of-ordering strategy can be substantially faster than computing a Gröbner basis for the desired ordering directly. Let us illustrate how to do this in OSCAR with an example. For our example, we start by computing a Gröbner basis w.r.t. the degrevlex ordering. Because we are working over a suitable finite field, `groebner_basis_f4` is our fastest option. In this example we measure the time of computation with Julia's `@time` macro:

```julia
julia> R, (x1, x2, x3, x4, x5, x6, x7, x8) = polynomial_ring(GF(65521),
    1, x1^2 - x1 + 2*x2^2 + 2*x3^2 + 2*x4^2 + 2*x5^2 + 2*x6^2 + 2*x7^2 +
    2*x8^2, 2*x1*x2 + 2*x2*x3 - x2 + 2*x3*x4 + 2*x4*x5 + 2*x5*x6 + 2*x6*x7
    + 2*x7*x8, 2*x1*x3 + x2^2 + 2*x2*x4 + 2*x3*x5 - x3 + 2*x4*x6 + 2*x5*x7
    + 2*x6*x8, 2*x1*x4 + 2*x2*x3 + 2*x2*x5 + 2*x3*x6 + 2*x4*x7 - x4 +
    2*x5*x8, 2*x1*x5 + 2*x2*x4 + 2*x2*x6 + x3^2 + 2*x3*x7 + 2*x4*x8 - x5,
    2*x1*x6 + 2*x2*x5 + 2*x2*x7 + 2*x3*x4 + 2*x3*x8 - x6, 2*x1*x7 + 2*x2*x6
    + 2*x2*x8 + 2*x3*x5 + x4^2 - x7));
```
<table><caption>Table 1: Gröbner basis algorithms in OSCAR.</caption><thead><tr><th rowspan="2">Algorithms</th><th rowspan="2">Keyword</th><th colspan="3">Restrictions</th></tr><tr><th>base ring</th><th>monomial ordering</th><th>other</th></tr></thead><tbody><tr><td>Buchberger</td><td>:buchberger</td><td>-</td><td>-</td><td>-</td></tr><tr><td>F<sub>4</sub></td><td>:f4</td><td>prime field Z/pZ</td><td>DRL</td><td>p &lt; 2<sup>31</sup></td></tr><tr><td>Hilbert Driven</td><td>:hilbert</td><td>field</td><td>global</td><td>-</td></tr><tr><td>FGLM</td><td>:fglm</td><td>field</td><td>global</td><td>dim 0</td></tr></tbody></table>

julia> @time groebner_basis_f4(I);
0.010955 seconds (57.13 k allocations: 3.081 MiB)

We check and discover that our ideal is zero-dimensional, so we may now use the FGLM algorithm to convert our degrevlex Gröbner basis into one for the lex ordering:

julia> dim(I) == 0
true

julia> @time fglm(I, destination_ordering = lex(R));
0.062046 seconds (130.52 k allocations: 3.313 MiB)

As the reader may verify, computing a lexicographic Gröbner basis for I by calling `gr` or `oebner_basis(I, ordering = lex(R))` takes substantially longer than the two Gröbner basis computations above combined.

Such a change-of-ordering strategy is also used by `msolve` itself to compute real solutions to polynomial systems of equations. Let us demonstrate this with an example as well.

## 2.1 Computing Real Solutions

For this demonstration we work with an example related to Euclidean distance problems, see [DHOST14].

Consider an algebraic map $\psi: \mathbb{R}^m \to \mathbb{R}^n$ and let $X := \overline{\mathrm{Im}(\psi)}$ be the Zariski closure of the image of $\psi$. For a given $u = (u_1, \dots, u_n) \in \mathbb{R}^n$ we are interested in the critical points of the function $d_u(x) = \sum_{i=1}^n (x_i - u_i)^2$ on the regular locus of $X$. Defining

$$D_u(t) = \sum_{i=1}^{n} (\psi_i(t) - u_i)^2$$

we have to solve the polynomial system

$$\frac{\partial D_u}{\partial t_1}(t) = \cdots = \frac{\partial D_u}{\partial t_m}(t) = 0$$

subject to the condition that the Jacobian of $\psi$ has maximal rank. Let us set this up in OSCAR for a randomly generated $\psi: \mathbb{R}^2 \to \mathbb{R}^3$ (see also example 3.1 in [DHOST14]):
julia> R, (t1, t2) = polynomial ring(QQ, ["t1", "t2"]);

julia> psi = [rand(R, 6:6, 3:5, -10:10) for _ in 1:3]
3-element Vector{QQMPolyRingElem}:
  1//2*t1^5*t2^3 - 2*t1^3*t2^4 + 2//9*t1^3*t2^3
  -3//5*t1^5*t2^5 - 8//7*t1^3*t2^4 - 17//4*t1^3*t2^3
  -23//12*t1^5*t2^5 - 3//7*t1^4*t2^3 - 13//6*t1^3*t2^5 - 9*t1^3*t2^4

julia> D = sum([f - rand(Int))^2 for f in psi];

julia> J = jacobian_ideal(D);

Next we have to add the condition that the Jacobean of $\psi$ has maximal rank. We introduce an extra variable, and add a random linear combination of the 2 × 2-minors of the Jacobean of $\psi$ as a nonzero condition, using Rabinowitsch's trick:

julia> S, (t1, t2, s) = polynomial ring(QQ, ["t1", "t2", "s");

julia> phi = hom(R, S, [t1, t2]);

julia> f = sum([rand(Int) * p for p in minors(jacobian_matrix(psi), 2)]);

julia> JJ = phi(J) + ideal(S, s*phi(f) - 1);

Finally, we can compute the real solutions of the resulting polynomial systems:

julia> sols, param = real_solutions(JJ);

julia> length(sols)

8

We see that in this case there are 8 critical points. real_solutions has also computed a rational parametrization for us, containing in particular a univariate polynomial parametrizing all *complex* solutions of the polynomial system in question. In this case there are 62 complex solutions:

julia> degree(param.elim)

62

Internally, `msolve` uses a multi-modular strategy, computing DRL Gröbner bases modulo a large set of primes, converting them into *lexicographic* Gröbner bases using a particular variant of FGLM called *sparse FGLM* (see [FM17]), out of which one extracts rational parametrizations for the polynomial systems in question which are then recomputed using the Chinese Remainder Theorem. The computations of the DRL Gröbner bases are optimized using *tracers* [Tra89]. The rational parametrization of our solution set then allows to compute them up to arbitrary precision.
### 3 Examples

Extending the algebraic geometry cornerstones chapter of this book, let us now go through a few examples of computational problems for polynomial ideals and point out where Gröbner bases come into play.

Two functions that we will frequently use are the eliminate and saturation functions. Let us recall their mathematical definition and geometric meaning. Let $k$ be a field and let $R := k[x_1, \dots, x_n]$ be a polynomial ring over $k$. Let $I \subseteq R$ be an ideal. Let $y \subset x := \{x_1, \dots, x_n\}$ be a subset of the variables.

**Definition 3.1.** We define the elimination ideal of $I$ eliminating $y$ as

$$I \cap k[x \setminus y].$$

Geometrically, this ideal cuts out the Zariski closure of the image of the projection of $V(I)$ to the $(x \setminus y)$-space. In OSCAR, we compute this ideal by calling eliminate($I$], $y$) where $y$ is a Vector consisting of the variables in $y$. Internally, it is computed via the elimination theorem [CLO15, Theorem 3.1.2]: If $G$ is a Gröbner basis for $I$ w.r.t. a block ordering on $x$, where the two blocks are $y$ and $x \setminus y$ and the $y$-block is considered lexicographically larger, then $G \cap k[x \setminus y]$ is a Gröbner basis for $I \cap k[x \setminus y]$. We want to stress again that computing Gröbner bases for block orderings is in general computationally more costly than computing DRL Gröbner bases.

Let $J \subseteq R$ be another ideal in $R$.

**Definition 3.2.** The saturation of $I$ by $J$ is defined as

$$(I : J^{\infty}) := \{ p \in R \mid pJ^k \subseteq I \text{ for some } k \in \mathbb{N} \}.$$

Geometrically, this ideal cuts out the Zariski closure of the locally closed set $V(I) \setminus V(J)$. In OSCAR, we compute it by calling saturation($I, J$). Internally, this ideal is computed using the Rabinowitsch trick, as above when we computed real solutions to polynomial systems. More precisely, if $J = \langle f \rangle$ is a principal ideal, then

$$(I : J^{\infty}) = (I + \langle tf - 1 \rangle) \cap k[x],$$

where $t$ is a new variable. An elimination-free algorithm for saturation has been given in the recent work [BES], this algorithm is already part of `msolve` but, as of the time of writing of this chapter, not yet ported over to OSCAR.

Knowing how to compute ideals of the form $(I : f^{\infty})$ we can then compute $(I : J^{\infty})$ for any $J$: If $J$ is generated by $f_1, \dots, f_r$ then

$$(I : J^{\infty}) = \bigcap_{i=1}^{r} (I : f_i^{\infty}).$$

We note that a probabilistic optimization of this, based on the prime avoidance lemma, is to instead choose a random linear combination $f$ of the $f_1, \dots, f_r$ and then compute $(I : f^{\infty})$. Again, we already used this trick when we computed real solutions above. With high probability this ideal will be equal to $(I : J^{\infty})$. It is easy to implement this trick in OSCAR, using `msolve`'s F4 implementation for the needed Gröbner basis computations, should the user require a quicker solution.
## Computing Non-Proper Points

Suppose $f: X \to Y$ is a dominant map between algebraic sets X and Y. We are interested in computing the *non-proper* values of $f$:

**Definition 3.3.** A point $y \in Y$ such that there exists no neighborhood $U$ of $y$ with $f^{-1}(\bar{U})$ compact is called a non-proper value of $f$.

This notion is, for example, related to the notion of *generalized critical values* in polynomial optimization (see e.g. [KOSoo; BFD21]).

In purely algebraic terms, the non-proper values are exactly the values over which $f$ is not finite, if we are working over the complex numbers.

To compute the set of non-proper values, we follow [Stao2]. Let $\Gamma := \{(x, y) | f(x) = y\} \subset X \times Y$ be the graph of $f$ and suppose that $X \subset \mathbb{A}^n$. Let $\bar{\Gamma}$ be the closure of $\Gamma$ in $\mathbb{P}^n \times Y$. Then:

**Proposition 3.4.** The set of non-proper values of $f$ is exactly the projection of $\bar{\Gamma} \setminus \Gamma$ to $Y$.

To compute this set in OSCAR consider the example

$$X = V(xy, xz, yz, x(x-1)) \subset \mathbb{C}^3$$

$$Y = \mathbb{A}^1$$

$$f: (x, y, z) \mapsto x$$

Let $t$ be our coordinate on $y$. We set up the graph of $f$ in OSCAR:

julia> R, (x, y, z, t) = polynomial-ring(QQ, ["x", "y", "z", "t"])

julia> graph_id = ideal(R, [x*y, x*z, y*z, x*(x-1), x-t]);

Next, we have to compute the closure $\bar{\Gamma}$ of $\Gamma$ in $\mathbb{P}^3 \times \mathbb{A}^1$. Just as the projective closure of an affine variety is computed by homogenizing a corresponding ideal, we compute $\bar{\Gamma}$ by homogenizing a corresponding ideal while treating the variable $t$ as a constant (see e.g. [CLO15]) – i.e. by homogenizing w.r.t. the weighted degree given by the weight vector $(1, 1, 1, 0)$. Note that this is not as simple as homogenizing arbitrary input generators – an ideal cutting out the projective closure of an algebraic set can be computed via a Gröbner basis computation with a suitable choice of monomial ordering, see e.g. [Eis95, Proposition 15.31]. More precisely, our monomial ordering has to extend the partial ordering on monomials given by the grading of interest. Such a Gröbner basis computation happens in the background of the following function call:

julia> w = [1 1 1 0]
1×4 Matrix{Int64}:
  1  1  1  0

julia> H = homogenizer(R, w, "w"); clo = H(graph_id)
Ideal generated by
  -x + t*w
  t^2 - t
  z*t
y*t
x*t - x
y*z
x*z
x*y
x^2 - x*w

Now, let $\pi$ be the projection from $\bar{\Gamma}$ to $\mathbb{A}^1$. Our goal is to compute the (Zariski-closed) set $\pi(\bar{\Gamma} \setminus \Gamma)$, i.e. to project the intersection of $\bar{\Gamma}$ with the hyperplanes at infinity in $\mathbb{P}^3 \times \mathbb{A}^1$ to the $t$-space. This set will be the set of non-proper values. In the following code snippet we always saturate by the irrelevant ideal of $\mathbb{P}^3 \times \mathbb{A}^1$ before eliminating: this ensures that when we then algebraically eliminate the variables $x, y, z, w$ that we indeed obtain an ideal cutting out the set $\pi(\bar{\Gamma} \setminus \Gamma)$, see p. 398 in [CLO15]:

julia> S = base ring(clo)
Multivariate polynomial ring in 5 variables over QQ graded by
  x -> [1]
  y -> [1]
  z -> [1]
  t -> [0]
  w -> [1]

julia> x, y, z, t, w = gens(S);

julia> irrel_ideal = ideal(S, [x,y,z,w]);

julia> eliminate(saturation(clo + ideal(S,x), irrel_ideal), [x,y,z,w])
Ideal generated by
t

julia> eliminate(saturation(clo + ideal(S,y), irrel_ideal), [x,y,z,w])
Ideal generated by
t^2 - t

julia> eliminate(saturation(clo + ideal(S,z), irrel_ideal), [x,y,z,w])
Ideal generated by
t^2 - t

julia> eliminate(saturation(clo + ideal(S,w), irrel_ideal), [x,y,z,w])
Ideal generated by
t

Hence the non-proper values of $f$ is the hypersurface defined by $t(t-1) = 0$.

## Computing Conormal Spaces and Whitney Stratifications

Suppose that $X \in \mathbb{P}^n$ is a singular projective variety of dimension $d$. Our goal in this section is to compute a *Whitney stratification* of $X$, which can be understood as a certain
decomposition of X into smooth pieces. For this, we will follow the algorithm presented in [HN22] and show how to perform the necessary computations in OSCAR. To introduce the problem, consider the variety cut out by the following hypersurface in $\mathbb{P}^3$:

julia> R, (x, y, z, w) = graded_polynomial-ring(QQ, ["x", "y", "z", "w"]) ;

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

Let us investigate the singular locus of this hypersurface $X := V(f)$ by imposing that the Jacobian of $f$ vanishes:

julia> J = jacobian_matrix(f)
[ -2*x*z^2]
[ 2*y*w^2]
[-2*x^2*z + 3*z^2*w]
[ 2*y^2*w + z^3]

julia> I_sing = ideal(R, [f, minors(J, 1)...])
Ideal generated by
  -x^2*z^2 + y^2*w^2 + z^3*w
  -2*x*z^2
  2*y*w^2
  -2*x^2*z + 3*z^2*w
  2*y^2*w + z^3

We see that the singular locus of $X$ consists of two lines. Let $X_1$ be the union of these two lines. A “naive” decomposition of $X$ into smooth pieces is now given as

$$X = X \setminus X_1 \cup X_1.$$

Losing some information about the singular locus of $X$ is an issue. We look at all associated primes of our singular locus, not just the minimal primes:

julia> minimal_primes(I_sing)
2-element Vector{MPolyIdeal{MPolyDecRingElem{QQFieldElem,
    -> QQMPolyRingElem}}}:
  Ideal (w, z)
  Ideal (z, y)

julia> (comp -> comp[2]).(primary_decomposition(I_sing))
6-element Vector{MPolyIdeal{MPolyDecRingElem{QQFieldElem,
    -> QQMPolyRingElem}}}:
  Ideal (w, z)
  Ideal (z, y)
  Ideal (w, z, y)
  Ideal (w, z, x)
  Ideal (z, y, x)
  Ideal (x, y, z, w)
In addition to our two lines, we discover the irrelevant ideal as well as three embedded points, lying on the two lines we saw previously. The fact that they appear in a primary decomposition of our singular locus suggests that they are somehow “more singular” in X than the two lines themselves. This information is lost in our decomposition above. The right geometric condition to impose additionally turns out to be the following ([HN22, section 2]):

**Definition 3.5.** Two complex manifolds $X, Y \subset \mathbb{C}^{n+1}$ with $\dim(Y) < \dim(X)$ satisfy Whitney's condition (b) if

* for any sequences of points $(x_i) \subset X$ and $(y_i) \subset Y$ converging to the same point $p$,

* such that the lines $[x_i, y_i]$ converge to some line $l$, and

* the tangent spaces $T_{x_i} X$ converge to some plane $T$

then $l \subset T$.

We refer to the introduction of [HN22] for a more detailed treatment of this example. Therein it is shown that the pair $(X \setminus X_1, X_1)$ does not satisfy Whitney's condition (b).

Whitney introduced this condition (b) in [Whi65] to define his Whitney stratifications:

**Definition 3.6.** A Whitney stratification of $X$ is a filtration of $X$ of the form

$$X = X_d \supset X_{d-1} \supset \dots \supset X_0 = \emptyset.$$

Each connected component of $X_k \setminus X_{k-1}$, $k = 1, \dots, d$, is called a stratum. Additionally, we want the filtration to satisfy the following assumptions:

* $X_k \setminus X_{k-1}$ is smooth for all $k = 1, \dots, d$,

* every point $p$ in $X$ admits an open neighborhood intersecting only finitely many strata, and

* each pair of strata satisfies Whitney's condition (b).

We now would like to translate Whitney's condition (b) into an algebraic condition. Let $X_{\text{reg}}$ be the set of smooth points of $X$, and $X_{\text{sing}}$ be the set of singular points of $X$. At each point $p \in X_{\text{reg}}$, the projective tangent space $T_p X$ naturally embeds as a linear space of dimension $d$ in $\mathbb{P}^n$. Denote by $(\mathbb{P}^n)^*$ the dual projective space of dimension $n$, parametrizing the hyperplanes in $\mathbb{P}^n$. We define

**Definition 3.7.** The conormal space $\text{Conorm}(X)$ of $X$ is defined as the Zariski-closure of

$$U := \{(p, H) \in X_{\text{reg}} \times (\mathbb{P}^n)^* \mid T_p X \subset V(H)\}.$$

Using this conormal space, the authors of [HN22] prove the following:

**Theorem 3.8.** Let $Y \subset X_{\text{sing}}$ be irreducible. Let $\kappa_X : \text{Conorm}(X) \to X$ be the canonical projection. Let

$$I(\kappa_X^{-1}(Y)) = \bigcap_{i=1}^{r} Q_i$$

be a primary decomposition. Define

$$A := \left[ \bigcup_{i \in \{1, \dots, s\}, \dim \kappa_X(V(Q_i)) < \dim Y} \kappa_X(V(Q_i)) \right] \cup Y_{\text{sing}}.$$

Then $(X_{\text{reg}}, Y \setminus A)$ satisfies Whitney's condition (b).
Our first goal is now to compute Conorm($X$). Let us denote our homogeneous coordinates on $\mathbb{P}^n$ by $x_0, \dots, x_n$. We write

$$H = a_0x_0 + \dots + a_nx_n$$

for our hyperplanes in $(\mathbb{P}^n)^*$. Let us compute this conormal space for the example $X := V(x_0^6 + x_0^4x_1x_2 + x_2^3x_3) \subset \mathbb{P}^3$. We start by setting up a coordinate ring for $X \times (\mathbb{P}^3)^*$ and storing the defining equation of $X$:

julia> R, (x0,x1,x2,x3,a0,a1,a2,a3) = polynomial ring(QQ,
    -> ["x0","x1","x2","x3","a0","a1","a2","a3"])

julia> f = x0^6 + x0^4*x1*x2 + x2^3*x3^3;

We compute the gradient of $f$, this time telling OSCAR to ignore the variables $a_0, \dots, a_3$:

julia> J = jacobian matrix(f) [1:4, 1:1]
[6*x0^5 + 4*x0^3*x1*x2]
[              x0^4*x2]
[x0^4*x1 + 3*x2^2*x3^3]
[            3*x2^3*x3^2]

The condition $T_pX \subset V(H)$ in the definition of $U$ is satisfied if and only if

$$\mathrm{rk} \left[ \begin{array}{c} J(p) \\ a_0 \dots a_3 \end{array} \right] = 1.$$

We encode this rank condition as a corresponding ideal of minors in OSCAR:

julia> JJ = hcat(J, R[a0; a1; a2; a3])
[6*x0^5 + 4*x0^3*x1*x2   a0]
[              x0^4*x2   a1]
[x0^4*x1 + 3*x2^2*x3^3   a2]
[            3*x2^3*x3^2   a3]

julia> id = ideal(R, minors(JJ, 2));

Finally, to compute Conorm($X$), we add the defining equation of $X$ to this ideal and saturate by the singular locus of $X$ (which corresponds to taking the Zariski closure in the definition of Conorm($X$)):

julia> id = ideal(R, minors(JJ, 2));

julia> I_sing = ideal(R, minors(J, 1));

julia> conorm = saturation(ideal(R, f) + id, I_sing);

To apply Theorem 3.8, we take $Y = X_{\mathrm{sing}}$:

julia> Y = radical(ideal(R,f) + I_sing)
Ideal generated by
  x0
  x2*x3
Let us now look at the image of each primary component of $I(\kappa_X^{-1}(Y))$, taking the image under this projection map corresponds to eliminating the variables $a_0, \dots, a_3$. Here we again saturate by the irrelevant ideal in the variables $x_0, \dots, x_3$.

julia> id_fib_Y = saturation(conorm + Y, ideal(R, [x0,x1,x2,x3]));
julia> prim_comps = (comp -> comp[2]).(primary_decomposition(id_fib_Y));
julia> [eliminate(comp, [a0,a1,a2,a3]) for comp in prim_comps]
6-element Vector{MPolyIdeal{QQMPolyRingElem}}:
  Ideal (x2, x0)
  Ideal (x3, x2, x0)
  Ideal (x3, x0)
  Ideal (x3, x2, x0)
  Ideal (x3, x1, x0)
  Ideal (x2, x0, 4*x1^3 + 27*x3^3)

We see the irreducible components of $Y$ ($\langle x_2, x_0 \rangle$ and $\langle x_3, x_0 \rangle$, both of dimension 1 in $\mathbb{P}^3$) and three distinct ideals corresponding to zero-dimensional varieties in $\mathbb{P}^3$ ($\langle x_3, x_2, x_0 \rangle$, $\langle x_3, x_1, x_0 \rangle$ and $\langle x_2, x_0, 4x_1^3 + 27x_3^2 \rangle$), the union of which gives our set $A$ in the setting of Theorem 3.8. In this case our Whitney stratification therefore consists of

$$X_3 := X, X_2 := Y = X_{\text{sing}}, X_1 := A \text{ and } X_0 := \emptyset.$$

We want to remark that, here, the core computational bottleneck for larger examples will be the required primary decomposition of an ideal – this is in general a very difficult problem. The algorithms for performing primary decomposition in OSCAR all make heavy use of elimination using Gröbner bases and polynomial factorization. We refer to [DGP97] for a survey on algorithms for primary and equidimensional decomposition available in OSCAR.

## An Example From Combinatorics

For this example we will use elimination theory to investigate a combinatorial problem. To introduce the flavor of the problem that we will be working on, consider walks in $\mathbb{N}^2$ with steps $\{\uparrow, \downarrow\}$ starting in the origin and ending at a point of the form $(x, 0)$. Let $c_n$ be the number of such walks with exactly $n$ steps and let $G(t) := \sum_{n=0}^{\infty} c_n t^n$ be its generating function. This function turns out to be algebraic over $Q(t)$ and we wish to compute its minimal polynomial. As is easy to see, this minimal polynomial corresponds exactly to a recurrence of the sequence $(c_n)_n$. One systematic way of computing this minimal polynomial is to introduce a *catalytic variable* as follows: Consider the number $c_{n,d}$ of walks ending at a point of the form $(x, d)$ and let $F(t, u) := \sum_{(n,d) \in \mathbb{N}^2} c_{n,d} t^n u^d$. The combinatorics of the problem allows us to derive the functional equation

$$F(t, u) = 1 + tuF(t, u) + t \frac{F(t, u) - F(t, 0)}{u}.$$

Note that $G(t) = F(t, 0)$. We define

$$P(x, z_0, t, v) = vx - t(x - z_0) - tu^2x - v,$$
so that we have the identity

$$P(F(t, u), G(t), t, u) = 0. \tag{1}$$

In [Bj06; NY23] the authors turn the equation 1 into a polynomial system which enables us to recover the algebraic equation eliminating $G(t)$ as follows: Consider

$$\begin{aligned} & \partial_u P(F(t, u), G(t), t, u) \\ & = \partial_u F(t, u) \partial_x P(F(t, u), G(t), t, u) + \partial_v P(F(t, u), G(t), t, u). \end{aligned}$$

If there exists a power series solution $U = U(t)$ to the equation

$$\partial_x P(F(t, U), G(t), t, U) = 0 \tag{2}$$

then also

$$\partial_v P(F(t, U), G(t), t, U) = 0. \tag{3}$$

So we have obtained a polynomial system consisting of the three equations (1), (2) and (3) in the four variables $x, z_0, t, v$. Eliminating the variables $x$ and $t$ from this polynomial system turns out to yield the desired minimal polynomial, see section 4 in [Bj06].

To work with a problem that turns out to be ideal-theoretically more interesting, consider the number of walks in $\mathbb{N}$ starting and ending at 0 with steps $\{+4, -3\}$. By again considering the endpoint as an additional parameter one obtains the functional equation

$$F(t, u) = 1 + t u^4 F(t, u) + t \frac{F(t, u) - F(t, 0) - u \partial_u F(t, 0) - \frac{u^2}{2} \partial_u^2 F(t, 0)}{u^3}.$$

We introduce sets of variables to represent $F(t, u)$, $F(t, 0)$ and its derivatives which appear in the above equation:

$$\begin{aligned} z_i &\sim \partial_u^i F(t, 0), \quad i = 0, 1, 2 \\ x &\sim F(t, u). \end{aligned}$$

Translating the above functional equation by plugging in these variables, the corresponding numerator yields a polynomial $P(x, z_0, z_1, z_2, t, u)$. Let us set this up in OSCAR. To make the required Gröbner basis computations easier we work modulo a large randomly chosen prime $p$, instead of over $\mathbb{Q}$. With high probability, this will allow us to recover the desired minimal polynomial at least modulo $p$. The reader can verify that working with this example over $\mathbb{Q}$ will make certain computations take a lot longer.

julia> F = GF(rand_bits_prime(ZZ, 20))
Prime field of characteristic 646637

julia> R, (z0, z1, z2, t, u, x) = polynomial-ring(F, ["z0", "z1", "z2", "t", "u", "x"]).

julia> P = (u^3 - t*(u^7 + 1))*x - u^3 + t*z0 + t*u*z1 + inv(F(2))*t*u^2*z2;

The polynomial system which has to be satisfied by $F(t, u(t))$ for a suitably chosen power series $u(t)$ is then:
julia> sys = [P,derivative(P,u),derivative(P,x)];

julia> I = saturation(ideal(R, sys), ideal(R, u));

Recall that our goal is now to eliminate every variable from this ideal except $z_0$ and $t$. We start by eliminating $x$:

julia> I = eliminate(ideal(R, sys), [x]);

Next follows the trick that will allow us to recover a unique polynomial in $z_0$ and $t$ in the corresponding elimination ideal which then necessarily annihilates $F(t,0)$. Let us look at the third equation of our system:

julia> sys[3]
646636*t*u^7 + 646636*t + u^3

This equation, when lifted to $\overline{\mathbb{Q}}$, permits three distinct solutions $u(t)$ in the power series ring $\overline{\mathbb{Q}}[[t^{1/3}]]$ (see Theorem 2 in [BJ06]). As a consequence, at fixed $(z_0, z_1, z_2) \in \overline{\mathbb{Q}}(t)^3$ there exist at least three distinct solutions $u(t)$ to our polynomial system. We want to consider only such solutions. To this end we introduce duplicates of our equations with the variable $u$ replaced by $u_1$ and $u_2$ respectively:

julia> S, (z0, z1, z2, t, u, u1, u2, x) = polynomial-ring(F,
  ->   ["z0", "z1", "z2", "t", "u", "u1", "u2", "x"])

julia> phi = hom(R,S,[z0,z1,z2,t,u,x]);

julia> I = phi(I);

julia> I += ideal(S, [f(z0,z1,z2,t,u1,u1,u2,x) for f in gens(I)]);

julia> I += ideal(S, [f(z0,z1,z2,t,u2,u1,u2,x) for f in gens(I)]);

Then we saturate by a polynomial which vanishes if and only if at least two of our coordinates coincide. Geometrically we are taking the closure of the locus where we have at least three distinct solutions in $u$ at fixed $z_0, z_1$ and $z_2$:

julia> I = saturation(I,ideal(S,(u-u1)*(u1-u2)*(u-u2)));

Now we can eliminate everything except $z_0$ and $t$:

julia> res = eliminate(I, [z1,z2,u,u1,u2,x]);

Note that we have indeed obtained a principal ideal. We verify that the generator of our polynomial ideal is irreducible to check that it is indeed the minimal polynomial of $G(t) = F(t,0)$:
julia> factor(first(gens(res)))
1 * (z0^35*t^35 + 646636*z0^31*t^28 + z0^30*t^28 + 646636*z0^29*t^28 +
   5*z0^28*t^28 + 646636*z0^25*t^21 + z0^24*t^21 + 3*z0^23*t^21 +
   646633*z0^22*t^21 + 10*z0^21*t^21 + z0^19*t^14 + 646636*z0^18*t^14 +
   5*z0^17*t^14 + 3*z0^16*t^14 + 646631*z0^15*t^14 + 10*z0^14*t^14 +
   z0^13*t^7 + 646636*z0^12*t^7 + 3*z0^10*t^7 + z0^9*t^7 + 646633*z0^8*t^7
   + 5*z0^7*t^7 + 646636*z0 + 1)

Note that the trick used above to consider only fibers of cardinality at least three requires again a difficult Gröbner basis computation – we introduce a lot of extra variables only to then eliminate them. See [NY23] for a more elegant way of doing this.

## Checking for Local Complete Intersections

We close with an example from pure commutative algebra that illustrates some ideal-theoretic capabilities of OSCAR that are more on the homological side rather than the elimination-and-saturation techniques used in the examples above. Again, let $R$ be a polynomial ring in $n$ variables and let $I$ be an ideal in $R$.

**Definition 3.9.** *I is a local complete intersection if the ring $(R/I)_p$ is a complete intersection ring for every prime $p \in \text{Spec}(R/I)$.

We wish to check for a given polynomial ideal if it is a local complete intersection. For this we use (see [Vas67]):

**Proposition 3.10.** *I is a local complete intersection if and only if the conormal module $I/I^2$ is a projective $R/I$-module locally at every prime $p \in \text{Spec}(R/I)$ (i.e. the module $(I/I^2)_p$ is projective, or equivalently free, for every prime $p$ of $R/I$).*

To check this condition we will use Fitting ideals (see e.g. chapter 20 in [Eis95]). For a module $M$ over some ring $S$ denote by $\text{Fitt}_i(M)$ the $i$th Fitting ideal. We have (see also [Eis95])

**Proposition 3.11.** *If $M$ can be generated by $r$ elements then $\text{Fitt}_r(M) = R$.*

2. $\text{Fitt}_0(M) \subset \text{Fitt}_1(M) \subset \dots \subset \text{Fitt}_r(M) = R$.

3. for an $S$-algebra $T$

$$ \text{Fitt}_i(M \otimes_S T) = \text{Fitt}_i(M)T. $$

4. $M$ is projective of constant rank $k$ if and only if $\text{Fitt}_k(M) = S$ and $\text{Fitt}_{k-1}(M) = 0$.

To check if a given polynomial ideal $I$ in $R$ is locally a complete intersection we may now proceed as follows: compute $I/I^2$ then compute the Fitting ideals up to index $r$, where $r$ is the number of given generators of $I$ (this suffices by the first and second item of Proposition 3.11). Computing Fitting ideals requires first computing syzygies for our module $I/I^2$. Unsurprisingly, this is again based on Gröbner bases. Out of any Gröbner basis, a Gröbner basis for the syzygy module can be extracted using Schreyer's theorem (see e.g. Theorem 15.10 in [Eis95]). We refer to the algebraic geometry cornerstones chapter for more details and to [EMSS16] for an efficient algorithm based on Schreyer's theorem available in OSCAR.
Once we have computed the required Fitting ideals we can check that the fourth condition in this proposition is met locally at every point $\mathfrak{p} \in \text{Spec}(R/I)$. Now, the third condition lets us compute the Fitting ideals over $R$ and then take their image in $R/I$. In particular, define

$$P_k(I/I^2) := \{ \mathfrak{p} \in \text{Spec}(R/I) \mid I/I^2 \text{ is projective of rank } k \}.$$

By the fourth item of Proposition 3.11 we have

$$P_k(I/I^2) = [V(I) \setminus V(\text{Fitt}_k(I/I^2))] \cap V(\text{Fitt}_{k-1}(I/I^2))$$

and we may check computationally if

$$V(I) = \bigcup_{k=1}^{r} P_k(I/I^2).$$

Let us do a computational sanity check with the simple example of the coordinate lines in 3-space defined by $I = \langle xy, xz, yz \rangle$:

julia> R, (x, y, z) = polynomial-ring(QQ, ["x", "y", "z"])

julia> I = ideal(R, [x*y, x*z, y*z]);

We set up the conormal module $I/I^2$ as a $\mathbb{Q}[x,y,z]$-module in OSCAR:

julia> conorm = subquotient(matrix(gens(I)), matrix(gens(I^2)))

Subquotient of Submodule with 3 generators

1 -> x*y*e[1]

2 -> x*z*e[1]

3 -> y*z*e[1]

by Submodule with 6 generators

1 -> x^2*y^2*e[1]

2 -> x^2*y*z*e[1]

3 -> x*y^2*z*e[1]

4 -> x^2*z^2*e[1]

5 -> x*y*z^2*e[1]

6 -> y^2*z^2*e[1]

The ideal $I$ is locally defined by a complete intersection of codimension 2 everywhere in $V(I)$ except for the origin. We would therefore expect that $P_2(I/I^2) = V(I) \setminus V(x,y,z)$. Indeed this is the case:

julia> fitting_ideal(conorm, 1)

Ideal generated by

y*z

x*z

x*y

julia> fitting_ideal(conorm, 2)

Ideal generated by
z

y

x

Note however that our ideal *I* here is a *generic* complete intersection: It is unmixed and the ring (*R*/*I*)<sub>p</sub> is a complete intersection ring for every *minimal* prime over *I*. We can check for a generic complete intersection using Proposition 3.2.1 in [VGSEH97]:

**Proposition 3.12.** Let *I* be unmixed of codimension *c*. Then *I* is a local complete intersection if and only if height *Fitt*<sub>*c*</sub>(*I*) ≥ *c* + 1.

Let us check this for our example. We first check, for the sake of demonstration, that *I* is unmixed. This can be done via equidimensional decomposition.

julia> equidimensional_decomposition_weak(I)
1-element Vector{MPolyIdeal{QQMPolyRingElem}}:
Ideal (x*y, x*z, y*z)

julia> F = fitting_ideal(ideal_as_module(I), 2);

julia> codim(F) >= codim(I) + 1
true

Next, let us take the disjoint union of a point with a line in 3-space:

julia> I1 = ideal(R, [x-1, y-1]);

julia> I2 = ideal(R, [x, y, z]);

julia> I = intersect(I1, I2);

julia> conorm = subquotient(matrix(gens(I)), matrix(gens(I^2)));

We set up a convenience function to compute the Zariski closures of the $P_k(I/I^2)$:

julia> Pk(conorm, k) = saturation(I, fitting_ideal(conorm, k)) +
    -> fitting_ideal(conorm, k-1);

We expect now that $P_2(I/I^2)$ gives us the line defined by $\langle x-1, y-1 \rangle$ and that $P_3(I/I^2)$ gives us the isolated point defined by $\langle x, y, z \rangle$:

julia> Pk(conorm, 2) == ideal(R, [x-1,y-1])
true

julia> Pk(conorm, 3) == ideal(R, [z,y,x])
true
Hence, we see in this case that *I* defines a local complete intersection. Note that while working with Fitting ideals can be mathematically convenient, they are more inconvenient computationally. They are *determinantal ideals*, i.e. ideals generated by minors of a polynomial matrix. The degrees of the defining equations of these ideals can thus become quite large, making Gröbner basis calculations quickly become infeasible for them. Let us remark, however, that the design of Gröbner basis algorithms for determinantal ideals is currently an active area of research, see e.g. [GNS23].

## Acknowledgements

This work has been supported by the Agence nationale de la recherche (ANR), grant agreement ANR-18-CE33-0011 (SESAME); by the EOARD-AFOSR grant agreement FA8665-20-1-7029; by the joint ANR-Austrian Science Fund FWF grant agreements ANR-19-CE48-0015 (ECARP) and ANR-22-CE91-0007 (EAGLES); by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 286237555 – TRR 195, and by the Forschungsinitiative Rheinland-Pfalz.

The authors wish to thank Martin Helmer and Hadrien Notarantonio for providing kind advice and examples respectively for the section on Whitney stratifications and the section on combinatorics.

## References

[BM92] D. Bayer and D. Mumford. "What Can Be Computed in Algebraic Geometry?" In: *In Computational Algebraic Geometry and Commutative Algebra*. University Press, 1992, pp. 1-48.

[BW93] T. Becker and V. Weispfenning. *Gröbner Bases*. Vol. 141. Graduate Texts in Mathematics. New York: Springer, 1993. doi: 10.1007/978-1-4612-0913-3.

[BES21] J. Berthomieu, C. Eder, and M. Safey El Din. "Msolve: A Library for Solving Polynomial Systems". In: *Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation*. ISSAC'21. Saint Petersburg, Russia, 2021. doi: 10.1145/3452143.3465545.

[BES] J. Berthomieu, C. Eder, and M. Safey El Din. *New efficient algorithms for computing Gröbner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon)*. doi: 10.48550/arXiv.2202.13387. arXiv: 2202.13387 [cs.SC].

[BFD21] J. Berthomieu, A. Ferguson, and M. S. E. Din. *On the Computation of Asymptotic Critical Values of Polynomial Maps and Applications*. Apr. 2021. doi: 10.48550/arXiv.2104.00913. arXiv: 2104.00913 [cs].

[BJ06] M. Bousquet-Mélou and A. Jehanne. "Polynomial Equations with One Catalytic Variable, Algebraic Series and Map Enumeration". *Journal of Combinatorial Theory, Series B* 96.5 (Sept. 2006), pp. 623-672. doi: 10.1016/j.jctb.2005.12.003.
[Buc65] B. Buchberger. "Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polonomideal". PhD thesis. University of Innsbruck, Innsbruck, 1965.

[CLO15] D. A. Cox, J. Little, and D. O'Shea. *Ideals, varieties, and algorithms*. Fourth. Undergraduate Texts in Mathematics. Springer, Cham, 2015, pp. xvi+646. doi: 10.1007/978-3-319-16721-3.

[DGP97] W. Decker, G.-M. Greuel, and G. Pfister. "Primary Decomposition: Algorithms and Comparisons". In: *Algorithmic Algebra and Number Theory*. 1997.

[DHOST14] J. Draisma, E. Horobet, G. Ottaviani, B. Sturmfels, and R. Thomas. "The Euclidean distance degree". In: *Proceedings of the 2014 symposium on symbolic-numeric computation, SNC 2014, Shanghai, China, July 28-31, 2014*. New York, NY: Association for Computing Machinery (ACM), 2014, pp. 9-16. doi: 10.1145/2631948.2631951.

[EF17] C. Eder and J.-C. Faugère. "A Survey on Signature-Based Algorithms for Computing Gröbner Bases". *J. Symbolic Comput.* 80 (2017), pp. 719-784. doi: 10.1016/j.jsc.2016.07.031.

[Eis95] D. Eisenbud. *Commutative Algebra: With a View toward Algebraic Geometry*. New York: Springer, 1995. doi: 10.1007/978-1-4612-5350-1.

[EMSS16] B. Eröcal, O. Motsak, F.-O. Schreyer, and A. Steenpaß. "Refined Algorithms to Compute Syzygies". *J. Symbolic Comput.* 74 (May 2016), pp. 308-327. doi: 10.1016/j.jsc.2015.07.004.

[FGLM93] J. C. Faugère, P. Gianni, D. Lazard, and T. Mora. "Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering". *J. Symbolic Comput.* 16.4 (Oct. 1993), pp. 329-344. doi: 10.1006/jsco.1993.1051.

[Fau99] J.-C. Faugère. "A New Efficient Algorithm for Computing Gröbner Bases (F4)". *J. Pure Appl. Algebra* 139.1 (1999), pp. 61-88. doi: 10.1016/S0022-4049(99)00005-5.

[FM17] J.-C. Faugère and C. Mou. "Sparse FGLM Algorithms". *J. Symbolic Comput.* 80 (May 2017), pp. 538-569. doi: 10.1016/j.jsc.2016.07.025.

[GNS23] S. Gopalakrishnan, V. Neiger, and M. Safey El Din. "Refined F5 Algorithms for Ideals of Minors of Square Matrices". In: *Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation*. ISSAC '23. New York, NY, USA: Association for Computing Machinery, July 2023, pp. 270-279. doi: 10.1145/3597066.3597077.

[HN22] M. Helmer and V. Nanda. "Conormal Spaces and Whitney Stratifications". *Foundations of Computational Mathematics* (June 2022). doi: 10.1007/s10208-022-09574-8. arXiv: 2106.14555 [cs, math].
[KOSoo] K. Kurdyka, P. Orro, and S. Simon. "Semialgebraic Sard Theorem for Generalized Critical Values". *J. Differ. Geom.* 56.1 (Sept. 2000), pp. 67–92. doi: 10.4310/jdg/1090347525.

[NY23] H. Notarantonio and S. Yurkevich. *Effective Algebraicity for Solutions of Systems of Functional Equations with One Catalytic Variable*. Mar. 2023. doi: 10.48550/arXiv.2211.07298. arXiv: 2211.07298 [math].

[Rob86] L. Robbiano. "On the Theory of Graded Structures". *J. Symbolic Comput.* 2.2 (June 1986), pp. 139–170. doi: 10.1016/S0747-7171(86) 80019-0.

[Sta02] A. Stasica. "An Effective Description of the Jelonek Set". *J. Pure Appl. Algebra* 169.2 (2002), pp. 321–326. doi: 10.1016/S0022-4049(01) 00063-9.

[Tra89] C. Traverso. "Gröbner Trace Algorithms". In: *Symbolic and Algebraic Computation*. Ed. by P. Gianni. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 1989, pp. 125–138. doi: 10.1007/3-540- 51084-2_12.

[Tra96] C. Traverso. "Hilbert Functions and the Buchberger Algorithm". *J. Symbolic Comput.* 22.4 (Oct. 1996), pp. 355–376. doi: 10.1006/jsco. 1996.0056.

[Vas67] W. V. Vasconcelos. "Ideals Generated by R-sequences". *J. Algebra* 6.3 (Aug. 1967), pp. 309–316. doi: 10.1016/0021-8693(67)90086-5.

[VGSEH97] W. V. Vasconcelos, D. R. Grayson, M. Stillman, D. Eisenbud, and J. Herzog. *Computational Methods in Commutative Algebra and Algebraic Geometry*. Berlin, Heidelberg: Springer, 1997.

[Whi65] H. Whitney. "Tangents to an Analytic Variety". *Ann. of Math.* 81.3 (1965), pp. 496–549. doi: 10.2307/1970400.