# Local antimagic orientation of graphs with positive real numbers as the
labels

Eranda Dhananjaya Department of Applied Mathematics, National Chung Hsing
University, Taichung 40227, Taiwan<EMAIL_ADDRESS>supported
by NSTC 112-2115-M-005 -002 -MY2. Wei-Tian Li Department of Applied
Mathematics, National Chung Hsing University, Taichung 40227, Taiwan
<EMAIL_ADDRESS>supported by NSTC 112-2115-M-005 -002 -MY2.

###### Abstract

An undirected graph $G$ is said to admits a local antimagic orientation if
there exists an orientation $D$ and a bijection between $E(G)$ and
$\\{1,2,\ldots,|E(G)|\\}$ such that any two adjacent vertices have distinct
vertex sums, where the vertex sum of a vertex is the sum of the labels of the
in-edges minus that of the out-edges incident to the vertex. Chang, Jing, and
Wang [6] conjectured that every connected graph admits a local antimagic
orientation. In this paper, we give an affirmative answer to this conjecture.

Keywords: Antimagic orientation, local antimagic orientation, breadth-first
search.

##  1 Introduction

Given an undirected simple graph on $m$ edges, can one label its edges with
$1,2,\ldots,m$ one on one so that when every vertex receives the sum of the
labels of all edges incident to the vertex, all sums are pairwise distinct?
This graph labeling problem was proposed by by Hartsfield and Ringel [10] in
the 1990s. They conjectured that such kind of labelings exist for all
connected graphs on at least two edges. Nowadays, many graphs have been
verified to satisfy the conjecture and many analogous problems are posed. Let
$G$ be a graph, and let $V(G)$ and $E(G)$ be the vertex and edge sets of $G$,
respectively. Whenever there is a mapping from $E(G)$ to a set $L$ of real
numbers, we define the vertex sum of a vertex, induced by the mapping, to be
the sum of the labels of the edges incident to the vertex. The original
problem of Hartsfield and Ringel is looking for a mapping $\tau$ such that

(1) $\tau$ is an injection.

(2) $L=\\{1,2\ldots,|E(G)|\\}$.

(3) the vertex sums are pairwise distinct.

A graph equipped with a mapping $\tau$ satisfying all the conditions is called
antimagic. The statement of the conjecture of Hartsfield and Ringel in [10] is
the following:

###### Conjecture 1.1

[10] Every connected graph other than $K_{2}$ is antimagic.

The most pioneering results on Conjecture 1.1 are the result of Alon, Kaplan,
Lev, Roditty, and Yuster for dense graphs [1], and the results of Cranston,
Liang, and Zhu [7] for odd regular graphs, and Chang, Liang, Pan, and Zhu for
even regular graphs [5]. In the following, we introduce some variations of the
ordinary antimagic labeling. For the set $L$ in condition (2), if it is
replaced by a set of $|E(G)|$ consecutive integers starting with $k+1$, then
the graph with such a mapping is called $k$-shifted antimagic, see [4]; If for
each set $L$ of $|E(G)|$ positive real numbers there is a corresponding
mapping, then the graph is universal antimagic, named by Matamala and Zamora
[18]; Moreover, if $L$ could be any set of $|E(G)|$ real numbers, then the
graph is $\mathbb{R}$-antimagic, named by Chang and Liu [18]. For the up-to-
date results on these different types of antimagic problems, we recommend the
readers the survey [8].

Some graph labeling problems are aiming to find distinct vertex sums for
adjacent vertices using $L$ as small as possible. Let $k$ be a positive
integer. A $k$-edge-weighting is a mapping from $E(G)$ to $\\{1,2,\ldots,k\\}$
and is neighbor-sum-distinguishing (nsd) if the vertex sums of any two
adjacent vertices are distinct. This concept was introduced with the 1-2-3
Conjecture in 2004 by Karoński, Łuczak, and Thomason in [15].

###### Conjecture 1.2

[15] Every graph with no isolated edge admits an nsd $3$-edge-weighting.

The above conjecture is generally known as the 1-2-3 Conjecture. The most
significant progress toward the 1-2-3 Conjecture thus far is attributed to
Kalkowski, Karoński, and Pfender [14], who established that every graph
lacking isolated edges can be equipped with an nsd 5-edge-weighting. Inspired
by the 1-2-3 Conjecture, Bensmail, Senhaji, and Lyngsie [2] introduced the
concept of local antimagic labelings for graphs. A local antimagic labeling of
a graph $G$ is an nsd bijective mapping denoted as
$\phi:E(G)\rightarrow\\{1,2,\ldots,|E(G)|\\}$. Bensmail et al. in [2] proposed
a conjecture asserting that every graph without isolated edges can be assigned
a local antimagic labeling. Subsequently, Haslegrave [11] validated this
conjecture through the utilization of the probabilistic method.

The exploration of antimagic labeling in directed graphs began considerably
later, with its initiation by Hefetz, Mütze, and Schwartz in 2010 [12]. For a
directed graph $\vec{G}$, the vertex sum of a vertex $v$ is defined as the sum
of the labels of all edges entering $v$ minus the sum of the labels of all
edges leaving $v$. An antimagic orientation for an undirected graph $G$ is
characterized by the existence of an orientation $D$ on its edge set $E(G)$
and a bijective mapping from $E(G)$ to the set $\\{1,2,\ldots,|E(G)|\\}$ such
that the orientation and the bijective mapping must fulfill the requirement
that the vertex sums, as previously defined in this paragraph are distinct for
all vertices in the graph. In their work [12], Hefetz et al. posed two
thought-provoking questions. The first question delves into whether every
orientation of a connected graph demonstrates antimagic properties, while the
second question scrutinizes the possibility of affording an antimagic
orientation to each connected graph. Furthermore, they provided partial
results for these inquiries and introduced the conjecture “Every connected
graph admits an antimagic orientation” in connection with the latter question.

###### Conjecture 1.3

[12] Every connected graph admits an antimagic orientation.

Over the past decade, the above conjecture has garnered significant attention
and garnered substantial support in various studies. Despite this, it still
stands as an unsolved question. Diverse research communities have
independently demonstrated that several graph families, as cited in works such
as [9, 17, 16, 21, 22, 19, 23, 20, 25, 24, 26], are consistent with Conjecture
1.3.

The efforts to extend the 1-2-3 Conjecture to directed graphs have indeed met
with success. Borowiecki, Grytczuk, and Pilśniak [3] established that every
simple directed graph can be equipped with an nsd $2$-edge-weighting. Chang,
Jing, and Wang [6] drew motivation from the directed version of the 1-2-3
Conjecture to introduce the concept of local antimagic orientation in a
similar manner as follows: An undirected graph $G$ is said to admit a local
antimagic orientation, if there exist an orientation $D$ on $E(G)$ and a
bijective mapping $\tau$ from the set of arcs in $G_{D}$ to the set
$L=\\{1,\ldots,|E(G)|\\}$ such that $\tau$ is nsd. Moreover, they proved that
every connected graph with maximum degree at most $4$ admits a local antimagic
orientation by combinatorial nullstellensatz and proposed the following
conjecture.

###### Conjecture 1.4

[6] Every connected undirected graph admits a local antimagic orientation.

By relaxing the size of $L$, Hu, Ouyang, and Wang [13] proved that every
$d$-degenerate graph $G$ admits a local
$\\{1,2,\ldots,|E(G)|+d+2\\}$-antimagic orientation. In other words, one can
find an orientation $D$ of $G$ and an injective mapping from the set of the
arcs $A(G_{D})$ to $L=\\{1,2,\ldots,|E(G)|+d+2\\}$ such that the adjacent
vertices receive distinct vertex sums.

In this paper, we completely resolve Conjecture 1.4 by showing a more general
result. Imitating the terminologies in the literature, we say that a graph $G$
is universal local antimagic orientable provided that for every set $L$ of
$|E(G)|$ positive numbers, there exist an orientation $D$ and a bijection from
the set of directed edges $A(G_{D})$ to $L$ that lead to pairwise distinct
vertex sums for all vertices. We mange to show the following theorem:

###### Theorem 1.1

Every graph is universal local antimagic orientable.

The eccentricity of a vertex $v$ in a graph $G$ is the maximum distance of a
vertex in $G$ to $v$, and the radius of a graph $G$ is the minimum
eccentricity of a vertex in $G$. By modifying the method for proving Theorem
1.1, we can show that every graph of radius two satisfies Conjecture 1.3. In
the next section, we will present the proof of Theorem 1.1 by introducing
first a modification of a frequently used lemma for the study of the antimagic
orientation problems. Then we give the by-product for Conjecture 1.3. Some
potential future research problems are discussed in the last section.

##  2 Main Result

Let $G$ be an undirected graph. Then $d_{G}(v)$ denote the degree of the
vertex $v$ in $G$. When $G$ endowed with an orientation $D$, we use
$d_{D}^{+}(v)$ and $d_{D}^{-}(v)$ to denote the out-degree and in-degree of a
vertex $v$, respectively. If an edge labeling $\tau$ is also given, then we
denote the vertex sum of $v$ with $s_{(D,\tau)}(v)$. By utilizing Euler
circuits, it is possible to approximate the vertex sums that are generated by
the circuit. This method has been used in in several recent publications, such
as Lemma 2.2 in [23], Lemma 2.1 in[25], and Lemma 7 in [19], to show different
classes of graphs satisfying Conjecture 1.3. We apply the idea in these lemmas
to obtain Lemma 2.1, which is of significant importance in proving our main
theorem.

###### Lemma 2.1

Let $G$ be a graph on $m$ edges and $L$ be a set of $m$ positive real numbers.
There exist an orientation $D$ of $G$ and a bijection $\tau:E(G)\rightarrow L$
such that for any $v\in V(G)$, either $s_{(D,\tau)}(v)<0$ or
$s_{(D,\tau)}(v)\leq\max L$.

Proof. If $G$ comprises more than one connected component, we can partition
$L$ into disjoint subsets. This allows us to handle each component separately
with labels falling within their respective subset. Consequently, it suffices
demonstrate the lemma for connected graphs. Let $V_{1}=\\{v\in V(G)\mid
d_{G}(v)\text{ is odd}\\}$. According to the handshaking lemma, $|V_{1}|=2t$
is an even number. If $V_{1}=\varnothing$, we define $G^{*}=G$, otherwise, we
define $G^{*}$ by incorporating $t$ new edges into $G$ in such a way that each
new edge connects a pair of vertices in $V_{1}$, and denote this set of new
edges as $E^{*}$. Note that $G^{*}$ may be a multiple graph and the degree of
every vertex in $G^{*}$ is an even number.

Now, we construct an Euler circuit, denoted as $C$ in $G^{*}$ according to the
following rules: If $G^{*}=G$, then we have the flexibility to select any
vertex as the starting point and construct $C$. However, if $G^{*}\neq G$, we
opt for a vertex in $V_{1}$ as our initial vertex. Since this chosen vertex is
incident to exactly one edge in $E^{*}$, we designate this edge as the first
edge of $C$. Suppose that

$C=u_{1},e_{1},u_{2},e_{2},\ldots,u_{m+t},e_{m+t},u_{1},$

where $u_{i}$’s are the vertices in $V(G)$, allowing for possible repetitions
, and $e_{1},e_{2},\ldots,e_{m+t}$ are exactly the edges in $E(G^{*}).$

Let $e_{i_{1}},e_{i_{2}},\ldots,e_{i_{m}}$, $i_{1}<i_{2}<\cdots<i_{m}$, be the
edges in $E(G)$. By orienting each edge a direction the same as it is in $C$,
we obtain an orientation $D$ of $G$ such that every vertex $v$ in the directed
graph $D$ satisfies $\left|d^{+}_{D}(v)-d^{-}_{D}(v)\right|\leq 1$. Suppose
$L=\\{a_{1},a_{2},\ldots,a_{m}\\}$ and $a_{j}$ is increasing in $j$. Define
$\tau:E(G)\rightarrow L$ with $\tau(e_{i_{j}})=a_{j}$ for $1\leq j\leq m$. The
orientation $D$ and labeling $\tau$ induce the vertex sums as follows: When
$G^{*}=G$, the a vertex sum of a vertex is the sum of an alternating series

$s_{(D,\tau)}(v)=-a_{j_{1}}+a_{j_{2}}-a_{j_{3}}+\cdots+a_{j_{d_{G}(v)}},$ (1)

for $v=u_{1}$, the initial vertex of $C$, or

$s_{(D,\tau)}(v)=a_{j_{1}}-a_{j_{2}}+a_{j_{3}}-\cdots-a_{j_{d_{G}(v)}},$ (2)

where $1\leq j_{1}<j_{2}<\cdots\leq j_{d_{G}(v)}$. It is straightforward to
verify that the vertex sum in (1) is less than $a_{m}$ and the vertex sum in
(2) is negative. For $G^{*}\neq G$, if
$\left|d^{+}_{D}(v)-d^{-}_{D}(v)\right|=0$, then the vertex sum
$s_{(D,\tau)}(v)$ has a form the same as (2), which is negative. Consider
$|d^{+}_{D}(v)-d^{-}_{D}(v)|=1$. If $v=u_{1}$, by the choice of $e_{1}$, we
have

$s_{(D,\tau)}(v)=a_{j_{1}}-a_{j_{2}}+a_{j_{3}}-\cdots+a_{j_{d_{G}(v)}},$

where $1\leq j_{1}<j_{2}<\cdots<j_{d_{G}(v)}$. So $s_{(D,\tau)}(v)<a_{m}$. If
$v\neq u_{1}$, then $s_{(D,\tau)}(v)$ can be viewed as the sum of a series
similar to (2) but one term $a_{j_{k}}$ is missing. Once the missing term is
associated with a plus sign, then $s_{(D,\tau)}(v)$ is negative. Otherwise,
the $s_{(D,\tau)}(v)$ is the missing term plus a negative number, which is
less than $a_{m}$. $\square$

Remark. By reversing the direction of every edge in the above orientation $D$,
we can obtain another orientation $D^{\prime}$ of $G$ that gives either
$s_{(D^{\prime},\tau)}(v)>0$ or $s_{(D^{\prime},\tau)}(v)\geq-\max L$ for any
$v\in V(G)$.

To establish the proof of Theorem 1.1, we employ the technique originally
utilized by Cranston, Liang, and Zhu [7] to establish the antimagic labeling
for odd regular graphs. Their approach can be summarized as follows: Begin by
selecting a vertex $u$ from the graph $G$. Then, partition the vertex set
$V(G)$ into levels $V_{0},V_{1},\ldots,V_{d}$, where $V_{i}=\\{v\mid
d(v,u)=i\\}$, $d(v,u)$ is the distance of $v$ and $u$, and $d$ represents the
maximum distance of a vertex from $v$. Define $G[V_{i}]$ as the subgraph
induced by $V_{i}$ and $G[V_{i},V_{i-1}]$ as the bipartite subgraph induced by
the two sets $V_{i}$ and $V_{i-1}$. For every positive $i$ and every vertex
$v$ in $V_{i}$, reserve an edge $e_{v}$ that is incident to vertices in
$V_{i}$ and $V_{i-1}$. Next, create a labeling $f$ by sequentially labeling
the edges in $G[V_{d}]$, $G[V_{d},V_{d-1}]$ and $\\{e_{v}:v\in V_{d}\\}$, and
so on, up to $G[V_{1}]$ and $G[V_{1},V_{0}]$, while ensuring that the smallest
unused labels are used and adhering to specific additional rules. It is worth
mentioning that we can accomplish the partition of the set $V(G)$ and the
selection of the edges $e_{v}$ by using the breadth-first search (BFS) to
construct a rooted tree for $G$.

Proof of Theorem 1.1. Since vertices in two components of a graph are not
adjacent, it suffices to show the theorem for connected graphs.

Let $G$ be a connected graph, and let $L$ be a set of $|E(G)|$ positive real
numbers. First pick a vertex $u$ and construct a rooted tree $T$ using the BFS
with root $u$. Suppose that the set $V(G)$ is partitioned into sets
$V_{0},V_{1},\ldots,V_{d}$, where $V_{i}$ is the set of vertices in the $i$th
level of $T$. Then partition the set $L$ into subsets
$L_{0},L_{1},\ldots,L_{d}$ satisfying

(1) $|E(G[V_{i}])|=|L_{i}|$ for $1\leq i\leq d$ and $L_{0}=L-(L_{1}\cup
L_{2}\cup\cdots\cup L_{d})$;

(2) For $1\leq i\leq d$, $\min L_{0}>\max L_{i}$.

Next, we apply Lemma 2.1 to construct the orientations $D_{i}$ of $G[V_{i}]$
and define the corresponding labeling $\tau_{i}:E(G[V_{i}])\rightarrow L_{i}$
for $1\leq i\leq d$ such that for any $v\in V(G_{i})$ either
$s_{(D_{i},\tau_{i})}(v)<0$ or $s_{(D_{i},\tau_{i})}(v)\leq\max L_{i}$ when
$i$ is odd, and for any $v\in V(G_{i})$ either $s_{(D_{i},\tau_{i})}(v)>0$ or
$s_{(D_{i},\tau_{i})}(v)\geq-\max L_{i}$ when $i$ is even. We complete the
orientation of $G$ by directing the edges in $G[V_{i},V_{i-1}]$ from $V_{i}$
to $V_{i-1}$ if $i$ is odd and from $V_{i-1}$ to $V_{i}$ if $i$ is even. For
each vertex $v\neq u$, we choose the edge incident to $v$ on the path
connecting $u$ and $v$ in $T$ as $e_{v}$. For each unlabeled edge not in $T$,
we arbitrary label it with an unused label in $L_{0}$. Finally, we label the
edges $e_{v}$. In the following, we assume that $d$ is odd, the case of even
$d$ is analogous. For each vertex $v$ in $V_{d}$, $e_{v}$ is the only
unlabeled edge incident to $v$. Recall that we have either
$s_{(D_{d},\tau_{d})}(v)<0$ or $s_{(D_{d},\tau_{d})}(v)\leq\max L_{d}$.
Moreover, all edges in $G[V_{d},V_{d-1}]$ are directed from $V_{d}$ to
$V_{d-1}$. So the partial vertex sum of a vertex $v$, $s(v)$, induced by the
labeled edges is either a negative number or at most $\max L_{d}$. We label
each $e_{v}$ with an unused label $\tau(e_{v})$ in $L_{0}$ with the condition
that $\tau(e_{v})<\tau(e_{v^{\prime}})$ implies $s(v)\geq s(v^{\prime})$.
Since $\min L_{0}>\max L_{d}$, not only the vertex sums are all distinct but
also all of them are negative. The next step is to label $e_{v}$ for each
vertex $v$ in $V_{d-1}$, which is only unlabeled edge incident to $v$ now. The
partial vertex sum $s(v)$, induced by the labeled edges is either a positive
number or at least $-\max L_{d-1}$. This time we label each $e_{v}$ with an
unused label $\tau(e_{v})$ in $L_{0}$ with the condition that
$\tau(e_{v})<\tau(e_{v^{\prime}})$ implies $s(v)\leq s(v^{\prime})$. Thus, the
vertex sums of all vertices in $V_{d-1}$ are distinct and positive. We use the
above strategies to label the unlabeled edges $e_{v}$ in
$G[V_{d},V_{d-1}],G[V_{d-1},V_{d-2}],\ldots,G[V_{1},V_{0}]$, accordingly.

Based on the BFS construction, two vertices can be adjacent to each other in
the same level or in two consecutive levels. We have demonstrated that for any
two consecutive levels, the vertex sums of their vertices exhibit distinct
signs. Also, we have established that for any pair of vertices belonging to
the same $V_{i}$, the vertex sums are distinct. As a conclusion, we complete
the proof of Theorem 1.1. $\square$

For a graph of radius two, we can construct a rooted tree of it with three
levels by designating the vertex of the minimum eccentricity as the root.
Thereby, when applying the labeling method in the proof of Theorem 1.1 to a
tree of radius two, it turn out that either the vertex sums are pairwise
distinct or at most one pair of vertices have the same vertex sum. When the
latter case happens, one of the two vertices is the root and the other is a
vertex which is not adjacent to the root. Indeed, we can make all the vertex
sums different by modifying the labeling strategies. We say a graph $G$ is
universal antimagic orientable provided that for any given set $L$ of $|E(G)|$
positive real numbers, there exist a bijection between $E(G)$ and $L$ and an
orientation of $E(G)$ such that all vertex sums are pairwise distinct.

###### Theorem 2.2

Every graph of radius two is universal antimagic orientable.

Proof. Let $G$ be a graph of radius two $u$ be a vertex with the minimum
eccentricity. First use BFS to construct a rooted tree $T$ with root $u$. The
terms $V_{i}$, $L_{i}$, and $e_{v}$ are defined analogously as in the proof of
Theorem 1.1.

We orient the edges, label the edges in $G[V_{1}]$ and $G[V_{2}]$ with the
labels in $L_{1}$ and $L_{2}$, and arbitrary label all the unlabeled edges not
in $T$ with the labels in $L_{0}$ as previous. Next, for the edges in $T$ we
label the all but one edges incident to $u$. Thus, for the root $u$ or a
vertex in $V_{2}$, there is exactly one unlabeled edge incident to it. Now, we
label these edges with the remaining labels according to the partial vertex
sums of the vertices in $V_{0}\cup V_{2}$. More precisely, let $s(v)$ be sum
of the labels of the labeled edges incident to $v$. We label each $e_{v}$ (for
the root $u$, $e_{u}$ refers to the unlabeled edge incident to $v$) with an
unused label $\tau(e_{v})$ in $L_{0}$ with the condition that
$\tau(e_{v})<\tau(e_{v^{\prime}})$ implies $s(v)\leq s(v^{\prime})$. This
guarantees that the vertex sums for vertices in $V_{0}\cup V_{2}$ are all
distinct and positive. However, we might encounter the problem that two
vertices in $V_{1}$ have the same vertex sum. Once this happens, the solution
is to rearrange the labels of $e_{v}$ for $v$ in $V_{1}$. Namely, we compare
the partial vertex sums of the vertices in $V_{1}$ contributed by the edges in
$G[V_{1}]$ and in $G[V_{2},V_{1}]$, then reassign the labels to the edges
$e_{v}$ accordingly to make the vertex sums distinct. Since this rearrangement
does not change the vertex sum of $u$, the vertex sums for vertices in
$V_{0}\cup V_{2}$ are all positive and distinct, while the vertex sums for
vertices in $V_{1}$ are all negative and distinct. So the theorem is proved.
$\square$

Immediately, we have the following result for Conjecture 1.3

###### Corollary 2.3

Every graph of radius two admits an antimagic orientation.

##  3 Future work

Since we have settled Conjecture 1.4 and generalized it to the case of using
any positive labels, it is natural to investigate the possibility of labeling
the edges with any real numbers. When every component of a graph contains at
most one edge and $0$ is one of the label, it is clear that for this graph
there will be two adjacent vertices of the same vertex sum $0$ no matter how
we orient and label the edges. Except for this example, so far we are not
aware of any other pair of graph $G$ and set $L$ of $|E(G)|$ real numbers so
that every orientation of $G$ and every bijection between $E(G)$ and $L$ will
always lead to a pair of adjacent vertices of the same vertex sum. We propose
the conjecture:

###### Conjecture 3.1

Let $G$ be a graph such that at least one component of $G$ contains more than
one edge. Then $G$ is local $\mathbb{R}$-antimagic orientable. Namely, for
every set $L$ of $|E(G)|$ real numbers, one can find an orientation $D$ on
$E(G)$ and a bijection $\tau$ between $E(G)$ and $L$ such that the vertex sums
$s_{(D,\tau)}(v)$ for every pair of adjacent vertices are distinct.

0$a$$-a$$-a$$0$$a$

0$a$$-a$

Figure 1: $P_{4}$ and $S_{3}$ with $L=\\{0,\pm a\\}$

For Conjecture 1.3, one can consider the analogous generalizations on the
label sets as well. However, in addition to $G=K_{2}$ and $L=\\{0\\}$, we find
some graphs $G$ and sets $L$ of real numbers so that no matter how we oriented
the edges, there always exist some pair of vertices having the same vertex
sums. The graphs are $P_{4}$, a path on 4 vertices, and $S_{3}$, a star on 3
leaves, while the sets are $L=\\{0,\pm a\\}$ for every $a\neq 0$. When
orienting the edges of the two graphs and labeling the edges with the labels
in $L$, there always exist two vertices whose vertex sums are both $0$, or
both $a$, or both $-a$.

## References

  * [1] N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (2004), no. 4, 297–309.
  * [2] J. Bensmail, M. Senhaji, K. S. Lyngsie, On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture Discrete Math. Theor. Comput. Sci., 19 (2017)
  * [3] M. Borowiecki, J. Grytczuk, M. Pilśniak, Coloring chip configurations on graphs and digraphs Inform. Process. Lett., 112 (2012), pp. 1-4
  * [4] F.-H. Chang, H.-B. Chen, W.-T. Li and Z. Pan, Shifted-antimagic labelings for graphs, Graphs Combin. 37 (2021), 1065–1082.
  * [5] F.-H. Chang, Y.-C. Liang, Z. Pan and X. Zhu, Antimagic labeling of regular graphs, J. Graph Theory 82 (2016), no. 4, 339–349.
  * [6] Y. Chang, F. Jing and G. Wang, Local antimagic orientation of graphs. Journal of Combinatorial Optimization, 39(4), (2020), 1129-1152.
  * [7] D. W. Cranston, Y.-C. Liang, and X. Zhu, Regular graphs of odd degree are antimagic, Journal of Graph Theory, 80 (2015), 28-33.
  * [8] J. A. Gallian, A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatorics (2019).
  * [9] Y. Gao and S. Shan, Antimagic orientation of lobsters, Discrete Applied Mathematics, 287 (2020), 21-26.
  * [10] N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston 1990.
  * [11] J. Haslegrave, Proof of a local antimagic conjecture Discrete Math. Theor. Comput. Sci., 20 (2018)
  * [12] D. Hefetz, T. Mütze, and J. Schwartz, On antimagic directed graphs. Journal of Graph Theory, 64 (2010), 219–232.
  * [13] J. Hu, Q. Ouyang, and G. Wang, Local antimagic orientations of $d$-degenerate graphs, Discrete Applied Mathematics, 257(2019), 206 - 215.
  * [14] M. Kalkowski, M. Karoński, F. Pfender, Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J. Combin. Theory Ser. B, 100 (2010), pp. 347-349
  * [15] M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours J. Combin. Theory Ser. B, 91 (2004), pp. 151-157
  * [16] T. Li, Z.-X. Song, G. Wang , D. Yang, and C.-Q. Zhang, Antimagic orientations of even regular graphs. Journal of Graph Theory, 90 (2019), 46–53.
  * [17] A. Lozano, Caterpillars have antimagic orientations, Analele Universitatii ”Ovidius” Constanta - Seria Matematica, 26(3) (2018), 171–180.
  * [18] M. Matamala and J. Zamora, Graphs admitting antimagic labeling for arbitrary set of positive integers, Electronic Notes in Discrete Mathematics, 62 (2017), 159-164.
  * [19] S. Shan, Antimagic orientation of graphs with minimum degree at least 33, Journal of Graph theory, 98(4), (2021), 676–690.
  * [20] S. Shan and X. Yu, Antimagic orientation of biregular bipartite graphs, Electronic Journal of Combinatorics, 24(4) (2017), paper P4.31.
  * [21] C. Song and R. X. Hao, Antimagic orientations for the complete $k$-ary trees, Journal Combinatorial Optimization, 38 (2019), 1077–1085.
  * [22] C. Song and R. X. Hao, Antimagic orientations of disconnected even regular graphs, Discrete Mathematics, 342(8) (2019), 2350-2355.
  * [23] Z.-X. Song, D. Yang, and F. Zhang, Antimagic orientations of graphs with given independence number, Discrete Applied Mathematics, 291 (2021), 163-170.
  * [24] D. Yang, A note on anti-magic orientation of even regular graphs, Discrete Applied Mathematics, 267 (2019), 224-228.
  * [25] D. Yang, J. Carlson, A. Owens, K. E. Perry, I. Singgih, Z.-X. Song, F. Zhang, and X. Xhang, Antimagic orientations of graph with large maximum degree, Discrete Mathematics, 343 (2020), 112-123.
  * [26] X. Yu, Y. Chang, and S. Zhou, Antimagic orientation of Halin graphs, Discrete Mathematics, 342 (2019), 3160-3165.


We describe a recursive algorithm that decomposes an algebraic set
into locally closed equidimensional sets, i.e. sets which each have
irreducible components of the same dimension. At the core of this
algorithm, we combine ideas from the theory of triangular sets,
a.k.a. regular chains, with Gröbner bases to encode and work with
locally closed algebraic sets. Equipped with this, our algorithm
avoids projections of the algebraic sets that are decomposed and
certain genericity assumptions frequently made when decomposing
polynomial systems, such as assumptions about Noether position. This
makes it produce fine decompositions on more structured systems
where ensuring genericity assumptions often destroys the structure
of the system at hand.  Practical experiments demonstrate its
efficiency compared to state-of-the-art implementations.

§ INTRODUCTION

Problem statement

Let $\field$ be an algebraically closed field, let $R = \field[x_1,\dotsc,x_n]$ be a polynomial
ring and let $f_1,\dotsc,f_c \in R$ be a polynomial system generating an
ideal $I\subseteq R$.  The zero set $X$ of the
polynomials $f_1,\dotsc,f_c$ in $\field$, decomposes uniquely as a union of irreducible
algebraic sets such that none of them contains
another.  These are the irreducible components of $X$ and
correspond to the minimal associated primes of $I$.  The
variety $X$ is equidimensional if all its irreducible
components have the same dimension.

It is clear that $X$ always admits a
decomposition $X = Y_1 \cup \dotsb \cup Y_c$ where the $Y_i$ are
equidimensional algebraic sets.

Suppose $X = \bigcup_{i=1}^s X_i$ is the decomposition of $X$ into
irreducible components. For $k=0,\dots,n$ define
$Y_k:= \bigcup_{i\text{ s.t. }\dim X_i=k}X_i$, then each $Y_k$ is
equidimensional so that $X = \bigcup_{k=0}^n Y_k$ is an
equidimensional decomposition of $X$. Given
$f_1,\dots,f_c \in R$, we aim at computing such an equidimensional
decomposition of $X$.

It will be clear that our algorithms will only have to do arithmetic
over the subfield of $\field$ that the coefficients of $f_1,\dots,f_c$
lie in, the output will also be defined over the same subfield. In the
following we will work only over $\field$ for the purpose of simplicity
of presentation.

This problem finds natural applications in singularity analysis of
sensor-based controllers of mechanism design [e.g.][and
references therein]pascualescudero:hal-03070525,
garciafontan:hal-03499974, in algorithms of real algebraic geometry
[e.g.][]AUBRY2002543, el2004properness and real algebra
SYZ18, SAFEYELDIN2021259 as well as automated theorem
proving and geometry [e.g.][]wu2007mathematics,
yang2001complete, yang1998automated, chen2013application.

Prior Works
The importance of this computational problem fostered a vast body of
literature often also as an intermediate step towards primary
decomposition of ideals or prime decomposition of
varieties. Algorithms for equidimensional decomposition of algebraic
sets can be classified along the data structures which they employ to
represent (equidimensional) algebraic sets.

There are two prominent strategies for equidimensional decomposition
using Gröbner bases frequently implemented in computer algebra
systems. The first one uses algebraic elimination techniques. It
combines the knowledge of the dimension of the ideal generated by the
input polynomials with the elimination theorem
[Theorem 3.1.2]CoLiOS07 to compute a description of the
projection of the algebraic set under study on a well-suited affine
linear subspace to deduce how to split the corresponding ideal
gianni1988, krick1991, caboara1997, decker1999,
KALKBRENER1994365.  The projection of the equidimensional component
of highest dimension (frequently called the equidimensional
hull) of the algebraic set under question will then be cut out by a
hypersurface whose defining polynomial has degree equal to the degree
of this equidimensional hull. As a consequence, such algorithms
have the disadvantage that they need to manipulate polynomials of
degree in the order of the Bezout bound of the input system. To
circumvent this drawback, another set of methods, called direct methods has been introduced by
eisenbud1992.  They rely on homological algebra to reduce the
problem of equidimensional decomposition to the computation of
syzygies which are then used to split the polynomial ideal under
study, while avoiding projections.
These algorithms often provide an intermediate step towards
primary decomposition of ideals. For this problem, modular techniques
and dedicated algorithms for the case where $\field$ is a finite field
have been designed NORO20041227, yokoyama2002prime,

Another body of work uses lazy representations of algebraic
sets. Frequently, the core idea is to exploit the fact that any
equidimensional algebraic set is locally almost everywhere a complete
intersection, i.e. an equidimensional algebraic set of codimension $c$
can be represented by the vanishing of $c$ polynomials on a dense
Zariski open subset of itself.  Hence, equidimensional algebraic sets
can be understood as the Zariski closures of locally closed sets
defined by polynomial equations and inequations. Taking this
perspective, one additionally enforces these $c$ polynomial equations
to form a triangular set. These have their origin in the Wu-Ritt
characteristic sets ritt1950a, wu1986, chou1990, wang1993,
Gallo1991.  Triangularity is therein understood with respect to the
variables of the underlying polynomial ring (i.e. in a sense analogous
to the notion of triangular matrices in linear algebra). This
triangular structure naturally also yields the equations of the
algebraic set where the $c$ polynomials fail to define the algebraic
set at hand and thus triangular sets have a description of the
previously mentioned Zariski open subset attached to them in a natural
way. Because of their triangular structure they allow the reduction of
certain algorithmic challenges to a univariate problem. Of particular
importance, especially in the realm of equdimensional decomposition,
are certain special triangular sets called regular chains,
introduced by kalkbrener1993, lu1994. A regular chain
models an unmixed dimensional ideal and has good algorithmic
properties with respect to the ideal it represents. A related
frequently implemented algorithm was also given by
lazard1991. Algorithms using regular chains are prominently
part of the computer algebra system Maple chen2007a,
chen2012. We refer to wang2001, hubert2003 for
introductions to the subject and to aubry1999 for a
theoretical account as to how certain different notions of triangular
sets relate to each other.

It should be noted that, as for methods based on Gröbner bases
combined with algebraic elimination, these triangular encodings make
use of polynomials whose degrees, in the worst case, can be as high as
is the degree of the equidimensional components they do
encode. Nonetheless, algorithms based on triangular representations
can be quite well behaved compared to Gröbner basis techniques
especially on certain sparse polynomial systems.

Another data structure naturally encoding equidimensional algebraic
sets is that of a geometric resolution developed by
lecerf2000, lecerf2003.  A geometric resolution is a
certain zero-dimensional parametrization of an algebraic set in
Noether position. In our setting, these zero-dimensional
parametrizations are used to encode generic points in the
equidimensional components of the algebraic set under study (the
numerical counterpart of this encoding is known as the notion of
witness sets sommese2005, a notion that will be utilized
in this paper as well). Under certain generically satisfied
assumptions on the input, these can be combined with straight
line programs to obtain the best known complexity bounds for
equidimensional decomposition. See also jeronimo2002 for a
related approach.

To bypass the “projection-degree” problem, incremental
approaches have been investigated in combination with Gröbner
bases algorithms.  Incremental means here that they feed the
decomposition algorithm with one input polynomial after another, in
the same way as lazard1991 or lecerf2000, for
example, to identify when some polynomial is a zero divisor in the
ring of polynomials quotiented by the ideal generated by the previous
polynomials.  moroz2008 combines Gröbner bases
computations with representations of equidimensional algebraic sets by
means of locally closed sets. In a previous work, we also investigated
this approach by exploiting properties of signature-based Gröbner
bases algorithms to enhance the detection and exploitation of zero
divisors and compute the so-called nondegenerate locus of a polynomial
system eder2022.

This Work
In this work, we again take the incremental approach previously mentioned.
As in the other incremental algorithms, the foundation of our
algorithm is a decomposition algorithm to, given an equidimensional
algebraic set $X$ and some $f\in R$, determine the locus of
proper intersection of $f$ on $X$, i.e. the set of points
$p\in k^n$ such that $X\cap V(f)$ has dimension one less than $X$. This is
then used to iterate over the input equations $f_1,\dots,f_r$. More
precisely, one starts by decomposing $V(f_1,f_2)$ then uses the output
to decompose $V(f_1,f_2,f_3)$ and so on.

In contrast to a lot of other algorithms for equidimensional
decomposition based on Gröbner bases we borrow from the theory of
triangular sets and work with locally closed sets instead of
polynomial ideals simlarly to moroz2008. In the iterative
approach outlined above this turns out to have two benefits.

First, it naturally removes from the output sets of our iterative
algorithm certain embedded components that appear during the
decomposition. To illustrate this consider the following example:

Let $R:=\mathbb{Q}[x,y,z]$, $X:=V(xy), f:=xz$. To decompose $X\cap V(f)$ into
equidimensional components one may start by decomposing $X = V(x) \cup V(y)$.
Then one intersects these two components with $V(f)$ to obtain the
equidimensional decomposition $X\cap V(f) = V(x) \cup V(y,xz)$. The latter set
has the irreducible component $V(y,x)$ which is embedded in $V(x)$. If one
instead splits into a disjoint union $X = V(x) \cup \left[ V(y)\setminus
V(x) \right]$ and again intersects both components with $V(f)$ one obtains
$X = V(x) \cup \left(V(y,z)\setminus V(x) \right)$ and the latter component no
longer has the irreducible component $V(y,x)$.

Second, an iterative equidimensional decomposition algorithm may
produce redundant components, which, if they are not deduplicated, may
yield an exponential blow-up in the number of components: if one has
decomposed $X = \bigcup_i X_i$ with the $X_i$ sharing a large number of
irreducible components then decomposing each $X_i\cap V(f)$ to obtain a
decomposition of $X\cap V(f)$ results in an even more redundant
decomposition.  Because we use locally closed sets to model our
equidimensional sets we are enabled to enforce that every time we
decompose a locally closed set the resulting output sets be pairwise
set-theoretically disjoint. Our experiments indicate that this seems
to enforce a sufficiently strong irredundancy between our components
to avoid an exponential blow-up in the number of components.

In this paper we provide two methods to work with the locally closed
sets appearing in our algorithm: One method models them “naively” in
the sense that we encode them by storing their defining equations and
inequations and use Gröbner bases of their associated ideals to work
with them algorithmically. The other method tries to avoid having to
know a Gröbner basis for the ideal associated to a locally closed set
as much as possible by storing instead a Gröbner basis for a
witness set of the locally closed set in question. Using
Gröbner bases here with the graded reverse lexicographical ordering
has the effect that, compared to algorithms using triangular sets, we
are able to

* avoid computing projections of the algebraic sets to be
decomposed and certain frequently made genericity assumptions such
as ideals being in Noether position;

* obtain desciptions of these sets with lower degree polynomials.

Borrowing further from the theory of triangular sets we also adopt the
heuristic that it is a good idea to decompose given algebraic sets as
often and as finely as possible when working with them. This
philosophy is baked into the recursive structure of our algorithms
which exists so as to decompose a given locally closed set as much as
possible given generating sets for certain saturation ideals.

We implemented our algorithm in the computer algebra system
Oscar2023 using its interface to the library
berthomieu2021 for all necessary Gröbner basis
computations. Experimental results indicate that our algorithm is able
to tackle polynomial systems which are out of reach of state-of-the
art implementations of algorithms for equidimensional decomposition
which are available in leading computer algebra systems.

§ ALGORITHMS

§.§ Principles

To illustrate the basic principles behind our equidimensional
decomposition algorithm, consider an equidimensional variety $X$ in
the affine space $\affspace{\field}$.  Let $f \in R$.  The
variety $X$ is partitioned into:

* Points $p$ where $f$ is a non zero divisor locally at $p$ (that
is in the ring $R_p/I(X) R_p$). The polynomial $f$ takes nonzero
values in any open neighborhood of $p$ in $X$.

This defines an open
subset $X_\text{proper}$ of $X$.

* Points $p$ contained in an irreducible component of $X$ on which $f$
vanishes identically.

This defines a closed subset $X_\text{improper}$ of $X$.

It is clear that $X = X_\text{proper} \sqcup X_\text{improper}$
(where $\sqcup$ denotes a disjoint union) and
that $X_\text{improper} \subseteq V(f)$, so that

\[ X\cap V(f) = \left( X_\text{proper} \cap V(f) \right) \sqcup
X_\text{improper}. \]
By construction, the
$ X_\text{proper} \cap V(f)$ is a proper intersection: it is
equidimensional of dimension $\dim X -1$, or empty. As a union of
irreducible components of $X$, the closed set $X_\text{improper}$ is
equidimensional, with the same dimension as the one of $X$, unless it
is empty. So we obtain an equidimensional decomposition
of $X\cap V(f)$. Given defining equations for $X$, this process can be
applied iteratively to obtain an equidimensional decomposition of any
affine algebraic variety.

In our algorithm we apply the above idea without directly computing
$X_{{text}{proper}}$ and $X_{\text{improper}}$. Let $I(X)\subset R$ be an
ideal such that $V(I(X)) = X$. Further, we denote by $\satu{I(X)}{f}$
the saturation ideal of $I(X)$ by $f$. Recall that $V(\satu{I(X)}{f})$
is the Zariski closure of $X \setminus V(f)$
[Theorem 4.4.10]CoLiOS07.

We look for an element $g \in \satu{I(X)}{f} \setminus I(X)$. If there is none,
this implies that $X_\text{improper} = \varnothing$ so $X \cap V(f)$ is
equidimensional. If there is such a $g$, then we consider the
following partition of $X$:

* the closed locus $X_1$ of points $p$ where $g$ has nonzero
values in any neighborhood of $p$ in $X$;

* the open locus $X_2$ of points $p$ where $g$ is zero in some
neighborhood of $p$ in $X$.

These two sets are equidimensional.  By construction, $fg$ vanishes
identically on $X$, so $X_1 \subseteq X_\text{improper}$ and this gives the
following decomposition of $X$:

\begin{equation}
X = X_1 \sqcup \left( X_2\cap V(f) \right).\label{eq:2}
\end{equation}

The ideal of $X_1$ is given by $\satu{I(X)}{g}$.  The term
$X_2\cap V(f)$ may not be equidimensional but we may apply the above idea
recursively: We again split $X_2$ along an element in
$\satu{I(X_2)}{f}\setminus I(X_2)$ if it exists.  This leads to Algorithm

The set $X_2$ is not closed, this raises the need to deal not only
with closed sets of the affine space, but more generally locally
closed sets.  We do so by partitioning them into special locally
closed sets, more precisely into closed sets in the complement of a
hypersurface in the affine space, which we call affine cells.
Concretely, suppose that $I(X_1) = \satu{I(X)}{g}$ is given by a
finite generating set $H\sqcup \{h\}\subset R$. We then recursively decompose
$X_2 = X\setminus V(H\sqcup \{h\})$ via

\[ X_2 = X \setminus V(H \cup \left\{ h \right\}) = ( X\setminus V(h)) \sqcup \big( (X\setminus V(H))
\cap V(h) \big). \]
The intersection with $V(h)$ is computed with
split to ensure equidimensionality.  Algorithm remove
below performs these operations.  Findally we obtain an
equidimensional decomposition algorithm following an incremental
strategy by repeated application of split, see
Algorithm equidim.

The primitive operations we use to manipulate affine cells are
presented next, while the proof of correctness and termination of the
algorithms are in Section <ref>.

§.§ Primitives

An affine cell $X$ is a locally closed set
of $\field^n$ of the form $Z\setminus V(g)$ where $Z$ is an
algebraic set and $g\in R$. An affine cell $X$ is
equidimensional if all the irreducible components of the
Zariski closure $\overline X$ have the same dimension.

Regardless of the mode of representation of an affine cells, we
assume that we can perform the following operations on any affine
cell $X$:

*  Given $f\in R$, compute the affine cell $X\cap V(f)$;

*  Given $f\in R$, compute the affine cell $X \setminus V(f)$;

As often in effective algebraic geometry,
algebraic sets are defined by ideals that are not always radical
so our affine cells come with a distinguished ideal $I(X)\subseteq R$
such that $\overline X = V(I(X))$.
The radical of $I(X)$ is denoted $\rad I(X)$.
We assume that operations <ref> and <ref>
satisfy $I(X) + \langle f\rangle \subseteq I( X\cap V(f) )$ and $I(X) \subseteq I(X \setminus V(f))$.
We assume further that we can perform the following operations on any affine cell $X$:

* Given $f\in R$, decide if $f\in I(X)$;

* Compute a basis of $I(X)$, denoted basis(X).

For example, we may represent an affine cell $X$ by a pair $(F, g)$,
where $F$ is a Gröbner basis of $I(X)$, for some monomial ordering,
and $g$ a polynomial such that $X = \overline{X}\setminus V(g)$
[see][for an introduction to Gröbner bases]becker1993.  We
denote $X = V(F; g)$.  For a set $F\subseteq R$ and an element
$g\in R$, let $\fn{sat}(F, g)$ denote a Gröbner basis of the saturation
ideal $\satu{\langle F \rangle}{g}$.  Recall that

\[ \satu{I}{g} \stackrel{\text{def}}= \left\{ f\in R \ \middle|\  \exists k\in \mathbb{N}, fg^k \in I \right\}.\]

Using these primitive sat, we can perform all the four operations above:

* $V(F; g) \cap V(f) = V( \fn{sat}(F \cup \left\{ f \right\}, g); g)$;

* $V(F; g) \setminus V(f) = V( \fn{sat}(F, f); fg)$;

* $f \in I(X)$ if and only if the normal form of $f$ w.r.t. $F$ is zero;

* $\fn{basis}(V(F; g)) = F$.

In Section <ref> we explain how to perform the above
primitive operations on an affine cell $X$ using a notion called
witness sets, introduced for the purpose of equidimensional
decomposition by lecerf2003 under the name lifting
fibers.  This leads to a lazier representation of $X$, one where a
Gröbner basis for $I(X)$ is not always required.

Equidimensional decompositions

Input An equidimensional affine cell $X$, an element $f\in R$

Output A partition of $X\cap V(f)$ into equidimensional affine cells

function split(X, f)
$G \gets \fn{basis}( X\setminus V(f))$

if $G \subseteq I(X)$  can be replaced by $G\subseteq \rad I(X)$
return $\left\{ X\cap V(f) \right\}$
$g\gets $ any element of $G \setminus I(X)$

$H \gets \fn{basis}(X \setminus V(g))$

$\mathcal{D} \gets\left\{ X\cap V(H) \right\}$

for $Y \in \fn{remove}(X \cap V(g), H)$
$\mathcal{D} \gets \mathcal{D} \cup \fn{split}(Y, f)$

return $\mathcal{D}$

Input An  affine cell $X$, a finite set $H \subset R$

Precondition $X\setminus V(H)$ is equidimensional

Output A partition of $X\setminus V(H)$ into equidimensional affine cells

function remove(X, H)
if $H = \varnothing$
return $\varnothing$
-    else
$h\gets $ any element of $H$

$\mathcal{D} \gets \left\{ X \setminus V(h) \right\}$

for $Y \in \fn{remove}(X, H\setminus \left\{ h \right\})$
$\mathcal{D} \gets \mathcal{D} \cup \fn{split}(Y, h)$

return $\mathcal{D}$

Input a finite set $F \subseteq R$

Output A partition of $V(F)$ into equidimensional affine cells

function equidim(F)
$\mathcal{D} \gets \left\{ V(\varnothing; 1) \right\}$ the full affine space

for $f$ in $F$
$\mathcal{D} \gets \bigcup_{X\in \mathcal{D}} \fn{split}(X, f)$

return $\mathcal{D}$

To illustrate Algorithm split we spell out how it behaves on
the input $X := V(xy,zw)$ and $f:=xz$. Using the notation of
Algorithm split we find $G = \{y,w\}$. This is not contained
in $I(X)$, so we may choose $g := y$ in line 6 of
Algorithm split. Then we find $H = \{x,zw\}$. Note that
$X\setminus V(zw) = \emptyset$ and so Algorithm split returns

\begin{align*}
&X\cap V(H) \text{ and }\text{\emph{split}}(\text{\emph{remove}}(X,H),f)\\
=\; &V(zw,x) \text{ and } \text{\emph{split}}(V(y,zw)\setminus V(x), xz).
\end{align*}

This second call to Algorithm split finds $G = \{y,w\}$,
again this set is not contained in $I(V(y,zw)\setminus V(x))$, and so we can choose
$g := w$ in line 6. Then we find $H = \{z\}$ which this time yields

\begin{align*}
\text{\emph{split}}(V(y,zw)\setminus V(x), xz) = &V(y,z)\setminus V(x) \\
&\text{and } \text{\emph{split}}(V(y,w)\setminus V(xz),xz)
\end{align*}

The last call to split simply finds the empty set and so all
in all we have obtained the decomposition

\begin{align*}
V(xy,zw,xz) = V(x,zw) \cup V(y,z)\setminus V(x).
\end{align*}

Example <ref> illustrates the fact that Algorithm
split may split an algebraic set even if it is
equidimensional. Heuristically, the finer the intermediate
decomposition in Algorithm equidim is, the computationally
easier subsequent steps will be.

§.§ Correctness and Termination

When computing an interection of an equidimensional affine cell $X$
with a hypersurface $V(f)$, we distinguish two cases, depending on whether $V(f)$ intersects $X$ properly or not.
Lemma <ref> deals with the first case, while Lemma <ref> deals with the second.

Let $X$ be an equidimensional affine cell.
Let $f \in R$, such that $\satu{I(X)}{f} \subseteq \rad I(X)$.
Then $X \cap V(f)$ is empty or equidimensional with dimension $\dim X - 1$.

Let $I = I(X)$.  We may assume that $I$ is radical: the
assumption $\satu{I}{f} \subseteq \rad I$ also
implies $\satu{\rad(I)}{f} \subseteq \rad I$.
If $a \in \satu{\rad(I)}{f}$, then $a f^r \in \rad I$, for
some $r \geq 0$, and so $(a f^r)^s \in I$, for some $s \geq 0$. In
particular, $a^s \in \satu{I}{f} \subseteq \rad I$.
So $a\in \rad I$.  Suppose that $X \cap V(f)$ is not empty. By Krull's
principal ideal theorem any minimal prime over
$I + \langle f \rangle$ has codimension at most
$\operatorname{codim}I + 1$.  The
condition $\satu{I}{f} \subseteq \rad I$ means geometrically
that $X\subseteq \overline{X\setminus V(f)}$, so that $f$ has nonzero values in the
neighborhood of any point in $X$.  So $f$ is a not a zero divisor
in $R/I$.  In particular, there is a regular sequence of length
$\operatorname{codim}I + 1$ in $I + \langle f \rangle$.  Since the polynomial
ring $R$ is Cohen-Macaulay it follows that every minimal prime over
$I + \langle f \rangle$ has at least codimension $\operatorname{codim} I + 1$.

Let $X$ be an equidimensional affine cell.
Let $f \in R$, let $g \in \satu{I(X)}{f}$
and let $I_g = \satu{I(X)}{g}$.
Let $X_1 = X\cap V(I_g)$ and $X_2 = (X \cap V(g)) \setminus V(I_g)$.

*  $X = X_1\sqcup X_2$;

*  $X \cap V(f) = X_1 \sqcup \left( X_2 \cap V(f) \right)$ ;

*  $X_1$ is empty or equidimensional with $\dim X_1 = \dim X$;

*  $X_2$ is empty or equidimensional with $\dim X_2 = \dim X$;

Obviously $X = X_1 \sqcup (X \setminus V(I_g))$.
As a set, $X_1$ is the union of the components of $X$ on which $g$ is not identically zero.
In particular $X \setminus V(I_g)$ is the set of points of $X$ in a neighborhood of which $g$ is identically zero.
Therefore $X \setminus V(I_g) \subseteq V(g)$, so we obtain

\[ X \setminus V(I_g) = (X \cap V(g)) \setminus V(I_g), \]

which gives <ref>.

Next, we have $I(X_1) = I(X) + I_g = \satu{I(X)}{g}$.
Moreover $f \in \operatorname{rad} I(X_1)$.
Indeed, $g f^k \in I(X)$ for some $k \geq 0$, by definition of $g$,
and therefore $f \in \operatorname{rad} \left( I(X) : g \right) \subseteq \operatorname{rad}\satu{I(X)}{g}$.
So $X_1 \subseteq V(f)$.
It follows that $X \cap V(f) = X_1 \sqcup \left( X_2 \cap V(f) \right)$.
This proves <ref>.

Since $X$ is equimensional, it follows that $X_1$ (as a union of components of $X$) is also equidimensional
of same dimension, unless it is empty.
This proves <ref>.
As for $X_2$, it is open in $X$, so it inherits the equidimensionality and the dimension of $X$, unless it is empty.
This proves <ref>.

We now prove correctness and termination of Algorithms split and remove
with a mutual induction.
On line <ref>, the test $G\subseteq I(X)$ can be replaced by $G\subseteq \rad I(X)$,
or any condition which holds when $G\subseteq I(X)$ and doee not hold when $G\not\subseteq \rad I(X)$,
this does not affect correctness or termination. We will use this variant in Section <ref>.

For any affine cell $X$:

*  If $X$ is equidimensional, then for any $f\in R$, the procedure split terminates on input $X$ and $f$
and outputs a partition of $X\cap V(f)$ into equidimensional affine cells $Y$ with $I(X) \subseteq I(Y)$.

*  For any finite set $H\subset R$ such that $X \setminus V(H)$ is equidimensional,
the procedure remove terminates on input $X$ and $H$ and outputs a partition of $X\cap V(H)$ into equidimensional affine cells $Y$ with $I(X) \subseteq I(Y)$;

We proceed by Noetherian induction on $I(X)$ and assume the statement holds for any affine cell $X'$ with $I(X) \subsetneq  I(X')$.

We begin with split.
Let $f \in R$ and let $I_f = \satu{I(X)}{f}$.
If $I_f \subseteq I(X)$,
then Lemma <ref> applies and $X\cap V(f)$ is equidimensional.
So $\fn{split}(X, f)$ terminates and is correct in this case.

Assume now that there is some $g\in I_f \setminus I(X)$.
Let $I_g= \satu{I}{g}$.
Lemma <ref> applies: an equidimensional decomposition of $X\cap V(f)$
is given by $X\cap V(I_g)$ and an equidimensional decomposition of $\left( (X\cap V(g))\setminus V(I_g) \right)\cap V(f)$.
Moreover $(X\cap V(g)) \setminus V(I_g)$ is equidimensional.
Since $g\not\in I(X)$, we have $I(X) \subsetneq I(X\cap V(g))$
so remove(X∩V(g), H)  (using the notations of Algorithm split, where $H$ is a generating set of $I_g$)
is correct and terminates, by induction hypothesis. Moreover, it outputs affine cells $Y$ such that $I(X) \subsetneq I(X \cap V(g)) \subseteq I(Y)$.
So the recursive calls split(Y, f) are correct and terminate.

As for remove,
let $H \subset R$ finite such that $X \setminus V(H)$ is equidimensional.
If $H = \varnothing$, then <ref> holds trivially.
As for the case $H\neq \varnothing$, let $ h\in H$ and $H' = H\setminus h$.
Since $V(H) = V(h) \cap V(H')$, we have

\begin{equation}
X \setminus V(H) = (X \setminus V(h)) \sqcup \left( (X \setminus V(H')) \cap V(h) \right).\label{eq:1}
\end{equation}

The set $X\setminus V(h)$ and $X\setminus V(H')$ are open in $X\setminus V(H)$ so equidimensional (or empty).
By induction on the cardinal of $H$, we assume that remove(X, H') is a partition of $X \setminus V(H')$ into equidimensional affine cells,
and that every cell $Y$ of this partition satisfies $I(X) \subseteq I(Y)$.
By <ref>, the calls
split( Y, h)  terminates and yield a partition of
$(X \setminus V(H')) \cap V(h)$ into cells $Y$ with $I(X) \subseteq I(Y)$.
Moreover the affine cell $Y = X\setminus V(h)$ also satisfies $I(X) \subseteq I(Y)$.
By (<ref>), remove(X, H) terminates too and is a partition of $X \setminus V(H)$
into cells $Y$ with $I(X) \subset I(Y)$.

Algorithm equidim is correct and terminates.

§ IMPLEMENTATION AND EXPERIMENTAL RESULTS

§.§ Implementation Details

In this section we give some implementation details and alternatives.
In particular, we show a lazier data structure for affine cells
which is able to delay some Gröbner basis computations
at the cost of a Monte Carlo randomization.
We have implemented both the method described
in Section <ref> and the method described in this section.

For either method, we will need an algorithm that, given generators
for an ideal $I$ and an element $f\in R$, computes generators for the
saturation $\satu{I}{p}$. Even for our lazy representation, this will
still sometimes be needed to compute a Gröbner basis for the ideal
$I(X)$, where $X$ is an affine cell. In the probabilistic setting,
some saturations will be replaced by saturations of zero dimensional

In our implementation we chose the standard method of performing
saturations using Gröbner bases.
To compute generators for
$\satu{I}{p}$, fix a monomial order $\leq$ on $R[t]$ for a new variable
$t$ such that $\leq$ eliminates $t$. Compute a Gröbner basis $G$ for the
ideal $I + \langle tp - 1\rangle \subset R[t]$ w.r.t $\leq$. Then the elements in
$G$ that do not contain the variable $t$ give a Gröbner basis of
$\satu{I}{p}$ by the elimination theorem.

Other saturation methods also exist such as the methods
presented in eder2022 or berthomieu2022.

Randomization relies on intersecting with random linear subspaces of
appropriate dimension to reduce to the zero-dimensional case. This
idea is well known in symbolic computation lecerf2003 and
numerical algebraic geometry [e.g.]bates2013 wherein these
intersections of algebraic sets with random suitable random linear
subspaces are known under the name witness sets.

Let $X\subseteq \affspace{\field}$ be  an equidimensional affine cell of dimension
$d$ and let $f\in R$.
Then, for a
generic linear subspace $L\subset \affspace{\field}$ of codimension $d$ the
following statements hold:

* $f\in \rad{I(X)}$ if and only if $f \in \rad{I(X\cap L)}$.

* $I(X\setminus V(f)) \subseteq \rad{I(X)}$ if and only if $X \cap L \cap V(f) = \varnothing$.

We always have $\rad I(X) \subseteq \rad I(X \cap L)$.
assume that $f\not\in \rad I(X)$.
Let $U = \left\{ p\in X\ \middle|\  f(p) \neq 0 \right\}$/
It is an open subset of $X$ and it is non empty, by hypothesis.
Since $X$ is equidimensional, $U$ has dimension $d$
and the intersection $U\cap L$ is nonempty (because $L$ is generic).
Therefore $f$ is nonzero on a nonempty subset of $X\cap L$.
In particular, $f \not \in \rad I(X\cap L)$.
This proves the first point.

For the second point note that $I(X\setminus V(f)) \subseteq \rad{I(X)}$
if and only if $X$ and $V(f)$ intersect properly,
that is $X\cap V(f)$ is equidimensional of dimension $d-1$.
The intersection of $X\cap V(f)$ with the codimension $d$ generic space $L$ is empty if and only if the dimension of $X\cap V(f)$ is less than $d$.
The proves the second point.

In this setting, we represent an equidimensional affine cell $X$ by a
triple $(F, G, W, d)$, where $F$, $G$ and $W$ are subsets of $R$
and $d$ is an integer such that $\dim X = d$,
$X = V(F) \setminus V(\prod_{g\in G} G)$ and $W$ (stands for witness set) is
a Gröbner basis of $I(X \cap L)$ for some generic linear subspace
space $L$ of $\field^n$ of codimension $d$.  We
denote $X = V(F; G, W, d)$.  In practice, $L$ will only be random and
sufficient genericity will only hold with high probability (assuming
that $\field$ has enough elements).  Given only $F$, $G$ and $d$, we
can compute a suitable set $W$ by choosing a set $J\subseteq R$ of $d$ random
linear forms and computing a Gröbner basis
of $(((F : g_1^\infty) : \dotsb): g_r^\infty)$,
where $G = \left\{ g_1,\dotsc,g_r \right\}$.  This procedure is
denoted witness(F, G, d).

The four primitive operations are perfomed as follows.
For the intersection operation, we need some additional knowledge on the expected dimension of the output.
Let $X = V(F; G, W, d)$ be an equidimensional cell.

* [Proper intersection] Given $f\in R$ such that $X$ intersects $V(f)$ properly,

\[ X \cap V(f) = V\big(F' ; G, \fn{witness}(F', G, d-1), d-1\big), \]

with $F' = F \cup \left\{ f \right\}$;

(1') [Purely improper intersection] Given $H\subset R$ such that $X \cap V(H)$ is a union of components of $X$,

\[ X \cap V(H) = V\big(F \cup H ; G, \fn{gb}(W \cup H), d \big), \]

where gb(W∪H) denotes a Gröbner basis of the ideal generated by $X\cup H$;

* for $f\in R$, $X\setminus V(f) = V(F; G\cup \left\{ f \right\}, \fn{sat}(H, f), d)$;

* $f\in \rad I(X)$ if and only if $1 \in (W : f^\infty)$;

* $I(X)$ is computed by saturating $\langle F\rangle$ successively by all the elements of $G$.

In the decomposition algorithm, we always know a priori
the kind of each intersection.
The intersection on line <ref> of split is proper,
the intersection on line <ref> is purely improper.
The one on line <ref> is more subtle. Indeed, the decomposition algorithm may produce here a nonequidimensional cell
when considering $X\cap V(g)$.
With the notations of this algorithm, the cell $X' = X\cap V(g)$ is only equidimensional outside of $V(H)$ (of dimension $\dim X$).
This nonequidimensional cell will go through only one operation among the four primitives: $X'\setminus V(h)$ for some $h\in H$.
This operation restores equidimensionality.
So we can mostly ignore this issue and compute the intersection $X\cap V(g)$ as a purely improper intersection, pretending that $X\cap V(g)$ is equidimensional.

In addition we obtain
a fifth operation: a probabilistic algorithm to
check if $X\cap V(f)$ is empty or equidimensional of dimension one less
than $X$ (or, equivalently $\satu{I(X)}{f} \subseteq \rad I(X)$).
This is given by Algorithm isProper.
Equipped with this algorithm, we can replace the if-condition in line <ref> of Algorithm split with
$\fn{isProper}(X,f)$. Only if this is not satisfied we proceed to
compute a Gröbner basis for $I(X\setminus V(f))$.

Proper intersection check

Input An equidimensional affine cell $X$, an element $f\in R$

Output true if $X\cap V(f)$ is a proper intersection, false otherwise

function isProper(X, f)
$W \gets $ the withness set of $X$

$W' \gets$ a Gröbner basis of $\satu{\langle W\rangle}{f}$

return $1 \in W'$

Lastly we want to note the following: In Algorithm split, on
input $X$ and $f$, we may have to compute
$G := \fn{basis}(X\setminus V(f))$ but we use only one element in $G$ in line <ref>
of Algorithm split. This situation can be improved by a
simple caching mechanism: Note that in line <ref> of Algorithm
split we call $\fn{split}(Y,f)$ with affine cells $Y$
satisfying $Y \subset X$. This certainly means
$G = \fn{basis}(X\setminus V(f)) \subseteq \fn{basis}(Y \setminus V(f))$.  Hence we may first
try to pick an element from the already computed set $G$ in 6 of the
call $\fn{split}(Y,f)$ before computing $\fn{basis}(Y\setminus V(f))$.

§.§.§ Rationale for the new Data Structure

Always knowing a Gröbner basis for the affine cells appearing in
Algorithm equidim puts a large penalty on the cost of our

This is actually related to well-known observations on the complexity
of Gröbner bases under some regularity assumptions. Indeed, for a
regular sequence in strong Noether position, the cost of linear
algebra steps needed to compute intermediate Gröbner bases in an
incremental manner is higher than the final steps
BARDET201549. Dimension dependent complexity bounds
provide another confirmation of
this behaviour 10.1145/3087604.3087624.

Using witness sets we can potentially avoid a lot of intermediate
Gröbner basis computations in our algorithms. In our experience, for a
large number of cases, using witness sets greatly improves the efficiency
of our algorithm which is theoretically backed up by the previously mentioned complexity results.

Furthermore, in the data structure for affine cells presented in the
last subsection we store the definining inequation of our affine cells
as a factorization. If one wants to saturate a polynomial ideal $I$ by
an element $f\in R$ which is known to have a factorization
$f = \prod_{g\in G}g$ given by a finite set $G$ then it is expected to be
cheaper to saturate by the elements $g\in G$ one-by-one instead of
saturating by $f$ directly using the above elimination method. This
lowers the degrees of the polynomials involved.

§.§.§ A Better Version of remove

Furthermore, we encountered the following problem when implementing
Algorithm remove as presented in Section
<ref>. In this algorithm $H$ is
a Gröbner basis so it tends to be very redundant (that is very far from being a minimal set of generators).
So it often happens that there are
two or more elements $h_1,h_2\in H$ such that for
$X_1 := X\setminus V(h_1)$ and $X_2:=X\setminus V(h_2)$ we have
$I(X_1) = I(X_2)$. Eventually the sets $X_1$ and $X_2$ become
disjoint, since eventually $X_1$ is intersected with $V(h_1)$ or $X_2$
is intersected with $V(h_1)$, but Algorithm split may have to
split $X_1$ and $X_2$ before that happens.  Since splitting an affine
cell with Algorithm split depends only on the underlying ideals
we may then repeat the exact same operations on the level of ideals
twice or more. This issue then compounds exponentially due to the
recursive nature of our algorithms. We therefore modified Algorithm
remove to obtain disjoint equidimensional affine cells from
$X_1$ and $X_2$ as fast as possible, resulting in
Algorithm <ref>. Note that when we use witness sets this
algorithm avoids knowing Gröbner bases for the ideals $I(X_i)$ until
potentially line 12.

Input An affine cell $X$, a finite set $H\subset R$

Output A partition of $X\setminus V(H)$ into equidimensional affine cells

function remove'(X, H)
$\mathcal{D} \gets \emptyset$

for $i$ from $1$ to $r$
$X_i \gets X\setminus V(h_i)$

$H_i\gets \emptyset$

for $j$ from $1$ to $i-1$
if isProper(X_i, h_j)
$X_i\gets X_i\cap V(h_j)$
$H_i\gets H_i\cup \{h_j\}$

$\mathcal{D}_i\gets $ decomposition of $X_i\cap V(H_i)$
by repeated application of split

$\mathcal{D} \gets \mathcal{D} \cup \mathcal{D}_i$

return $\mathcal{D}$

§.§ Experimental Results

In this section we give some experimental results. We compare the
timings of our implementation of Algorithm equidim and methods
for equidimensional decomposition of algebraic sets available in
various computer algebra systems in a table given below. Some of the
timings are discussed in more detail in the next section. We compared
to the following implementations:

* The function  from the
library in Maple
which decomposes a polynomial system into regular chains,

* The function  in
Oscar2023 which is a wrapper around a
corresponding  function singular.

* The Magma bosma1997 functions

(corresponding to the column
“Magma” in the table) and

(corresponding to the column
“Magma (prime dec.)” in the table) and

* The numerical polynomial systems solver Bertini bates2013
which we ran on each system at hand by requesting a witness set
decomposition into irreducible components with fixed precision set
to Bertini's default value.

The implementation of our algorithms is itself done in  which
is written in the programming language Julia
bezanson2017. Its source code is available at

For all necessary Gröbner basis computations
we employ the library  berthomieu2021 for which
offers an interface.  Our suite of example systems is
comprised as follows:

* Cyclic$(8)$, coming from the classical Cyclic$(n)$ benchmark.

* The systems P4L 1 to 3 come from the perspective-four line problem
in robotics, see garciafontan:hal-03499974.

* The systems C1 to C3 are certain jacobian ideals of single
multivariate polynomials which define singular hypersurfaces.

* Ps$(n)$, encoding pseudo-singularities via polynomials

with $f_i\in \mathbb{K}[x_1, \ldots, x_{n-2}, z_1, z_2]$,
$g_i\in \mathbb{K}[y_1, \ldots, y_{n-2}, z_1, z_2]$, the $f_i$ being chosen
as a random dense quadrics, and $g_i$ chosen such that
$g_i(x_1,\dots,x_{n-2},z_1,z_2) = f$, i.e. as a copy of $f_i$ in the
variables $y_1,\dots,y_{n-2},z_1,z_2$.

* sos$(s, n)$, encoding the critical points of the restriction of
the projection on the first coordinate to a hypersurface which is a
sum of $s$ random dense quadrics in $\mathbb{K}[x_1, \ldots, x_n]$.

$$f, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n},
\quad f = \sum_{i=1}^s g_i^2.$$

* sing$(n)$, encoding the critical points of the restriction of
the projection on the first coordinate to a (generically singular)
hypersurface which is defined by the resultant of two random dense
quadrics $A, B$ in $\mathbb{K}[x_1, \ldots, x_{n+1}]$:

$$f, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n},
\quad f = \textrm{resultant}(A, B, x_{n+1}).$$

* The Steiner polynomial system, coming from breiding2020.

* All remaining examples are part of the BPAS library
asadi2021. The BPAS library offers an alternative to the
library in Maple with special emphasis on
paralellism and it will be interesting to compare it to our
algorithm in the future.

To obtain the timings in the table below we almost exclusively used
the witness set based data structure for affine cells. Every
polynomial system was computed with in characteristic 65521 with the
exception of Bertini which, as a numerical piece of software, computes
over the complex numbers. Due to this difference a comparison between
Bertini's and our timings needs to be considered carefully. We tried
to indicate this in the table below by coloring the Bertini column in
grey. All computations except for Magma were done on an single core of
an Intel Xeon Gold 6244 CPU @ 3.60GHz. All Magma computations were
done on a single core of an Intel Xeon E5-2690 @ 2.90GHz. We let every
algorithm run for at least an hour or 50 times the time it took for
the fastest algorithm to complete the system in question, whichever
was bigger.

Using the witness sets of our output we also did the following to
compare to Bertini: We ran our algorithm in a large random prime
charateristic. We then removed the embedded irreducible components
from each of our output components and computed the degrees of the
output components. This gives us the degree in each dimension of the
algebraic set defined by the input. Whenever Bertini reports different
degrees, we marked it in the respective column. Due to the randomly
chosen large characteristic these degrees should be the same one
obtains when considering the algebraic set in question over the
complex numbers.

In the second column of this table, we additionally provide the number
of affine cells that Algorithm equidim decomposed the
respective system into. All timings in this table are given in
seconds. Due to the way we measured the timings of Bertini we can only
report them without any decimal places, rounded up.

§.§ Discussion of Experimental Results

We provide here some further information about some of the examples
and the behaviour of the different implementations on these examples
compared below.

Our algorithm, i.e. Algorithm equidim, seems to behave best in
comparison to the other implementations when the input system is dense
in the sense that each of the input equations of the system in
question involves most, or all, of the variables. This is the case for
cyclic 8, the class of the Ps($\bullet$) systems, the class of the
Sing($\bullet$) systems, the class of the sos($\bullet,\bullet$) systems and the Steiner
polynomial system.

On certain polynomial systems, where each input equation involves only
a small subset of the variables, we were able to improve our timings
by foregoing the witness set based data structure and instead running
a deterministic version of our algorithm akin to the version in
Section <ref>. The improvement we thusly obtained can be
explained by the fact that intersecting very sparse systems with
random hyperplanes can “destroy their sparsity” and make certain
Gröbner basis computations much harder. This was the case for the
example Leykin-1: Here running the deterministic version improved our
timing to 2.6 seconds.

The Gonnet and dgp6 polynomial systems demonstrate that our algorithm
is highly sensitive to the ordering of the input equations: By default
we ran our implementation by iterating over the input equations degree
by degree in Algorithm equidim. With this ordering, our
algorithm did not terminate within several hours of computation. When
we changed this ordering on these two examples and sorted the input
equations instead by length of support, our algorithm terminated in
less than one second on these two examples. Our algorithms practical
efficiency depends highly on the difficulty of the intermediate
polynomial systems which it encounters, these in turn depend on the
order of the input equations. On the Gonnet polynomial system, the new
ordering resulted in only a subset of the variables being involved in
the first few intermediate systems, thus making Gröbner basis for them
more tractable. On the dgp6 example the new ordering resulted in an
intermediate polynomial system consisting of monomials and binomials
which our algorithm decomposes very finely, making the treatment of
the remaining equations substantially easier

The system sys2874 can be attacked by both changing the order of the
input equations to be ordered by length of support and by using the
deterministic version of our algorithm: Doing this, the timing
improved by several orders of magnitude to 0.26 seconds.

We also remark that 's timings improved significantly on
the examples sys2449, sys2297 and Leykin-1 (each to less than one
second) if one decomposes the radicals of these systems instead of the
systems themselves.

For the examples KdV and sys2882 we seem to be bottlenecked by very
difficult Gröbner basis computations and less by the inherent
structure of our algorithm. Informal experiments where we tried to
compute just a Gröbner basis for these systems using msolve suggest
that even this is a highly non-trivial computation. For these two
systems, techniques involving regular chains seem to be vastly
superior over anything that involves Gröbner basis computations.

All in all, these experiments illustrate that on a wide range of
examples, our algorithm performs on average better than
state-of-the-art implementations and can tackle some problems which
were previously unrea

§ ACKNOWLEDGEMENTS

The authors wish to thank Marc Moreno Maza for providing feedback on
the BPAS library and its benchmark examples. Additionally the
authors thank the two anonymous reviewers for their helpful comments
and careful reading of this manuscript.

This work has been supported by the Agence nationale de la recherche
(ANR), grant agreements ANR-18-CE33-0011 (SESAME), ANR-19-CE40-0018
(Re Rerum Natura); by the joint ANR-Austrian Science Fund FWF grant
agreements ANR-19-CE48-0015 (ECARP) and ANR-22-CE91-0007 (EAGLES);
by the EOARD-AFOSR grant agreement FA8665-20-1-7029; by the DFG
Sonderforschungsbereich TRR 195; the Forschungsinitiative
Rheinland-Pfalz; and by the European Research Council (ERC) under
the European Union’s Horizon Europe research and innovation
programme, grant agreement 101040794 (10000 DIGITS).

Timings are in seconds, except otherwise indicated. The ratio with respect to the best time is given when the latter is over 1 second.

We made some minor preparation of the input (like reordering the input equations, or disabling the probabilistic representation of affine cells) to improve the timing.

Bertini terminated the computation with an error.

The result given by Bertini is not consistent with our result in terms of degree/dimension.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

titleBasic Polynomial Algebra Subprograms (BPAS) (Version 1.791)

journaltitleJ. Symb. Comput.
titleOn the Theories of Triangular Sets

journaltitleJ. Symb. Comput.
titleReal Solving for Positive Dimensional Systems

journaltitleJ. Symb. Comput.
titleOn the Complexity of the F5 Gröbner Basis Algorithm

titleNumerically Solving Polynomial Systems with Bertini

seriesGraduate Texts in Mathematics
titleGröbner Bases

journaltitleProc. ISSAC 2021
titleMsolve: A Library for Solving Polynomial Systems

titleNew Efficient Algorithms for Computing Gröbner Bases of Saturation Ideals (F4SAT) and Colon Ideals (Sparse-FGLM-colon)

journaltitleSIAM Rev.
titleJulia: A Fresh Approach to Numerical Computing

journaltitleJ. Symb. Comput.
titleThe Magma Algebra System. I. The User Language

journaltitleNot. Am. Math. Soc.
title3264 Conics in a Second

journaltitleAAECC 1997
seriesLecture Notes in Computer Science
titleYet Another Ideal Decomposition Algorithm

World Scientific

journaltitleInt. J. Bifurc. Chaos
titleAn Application of Regular Chain Theory to the Study of Limit Cycles

journaltitleInt. Conf. Comput. Sci.
titleEfficient Computations of Irredundant Triangular Decompositions with the Regularchains Library

journaltitleJ. Symb. Comput.
titleAlgorithms for Computing Triangular Decomposition of Polynomial Systems

journaltitle10th Int. Conf. Autom. Deduc.
seriesLecture Notes in Computer Science
titleRitt-Wu's Decomposition Algorithm and Geometry Theorem Proving

seriesUndergraduate Texts in Mathematics
titleIdeals, Varieties, and Algorithms

journaltitleAlgorithmic Algebra Number Theory
titlePrimary Decomposition: Algorithms and Comparisons

titleSingular 4-2-1 — A computer algebra system for polynomial computations

titleA Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System

journaltitleInvent. Math.
titleDirect Methods for Primary Decomposition

booktitleEffective Methods in Algebraic Geometry
titleEfficient Algorithms and Bounds for Wu-Ritt Characteristic Sets

Springer Verlag

journaltitleInt. J. Comput. Vis.
titleSingularity Analysis for the Perspective-Four and Five-Line Problems

journaltitleJ. Symb. Comput.
titleGröbner Bases and Primary Decomposition of Polynomial Ideals

journaltitleProc. ISSAC 2017
titleDimension-Dependent Upper Bounds for Gröbner Bases

journaltitleSymb. Numer. Sci. Comput.
seriesLecture Notes in Computer Science
titleNotes on Triangular Sets and Triangulation-Decomposition Algorithms I

journaltitleProc. ISSAC 2022
titleModular Techniques for Intermediate Primary Decomposition

journaltitleJ. Pure Appl. Algebra
titleEffective Equidimensional Decomposition of Affine Varieties

journaltitleJ. Symb. Comput.
titleA Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties

journaltitleJ. Symb. Comput.
titlePrime Decompositions of Radicals in Polynomial Rings

booktitleAAECC 1991
titleAn Algorithm for the Computation of the Radical of an Ideal in the Ring of Polynomials

journaltitleDiscrete Appl. Math.
titleA New Method for Solving Algebraic Systems of Positive Dimension

journaltitleProc. ISSAC 2000
titleComputing an Equidimensional Decomposition of an Algebraic Variety by Means of Geometric Resolutions

journaltitleJ. Complex.
titleComputing the Equidimensional Decomposition of an Algebraic Closed Set by Means of Lifting Fibers

journaltitleACM SIGSAM Bull.
titleThe RegularChains Library in MAPLE

shorttitleSearching Dependency between Algebraic Equations
titleSearching Dependency between Algebraic Equations: An Algorithm Applied to Automated Reasoning

booktitleComput. Math.
seriesLecture Notes in Computer Science
titleRegular Decompositions

journaltitleJ. Symb. Comput.
titleImplementation of Prime Decomposition of Polynomial Ideals over Small Finite Fields

journaltitleInt. J. Comput. Vis.
titleComplete Singularity Analysis for the Perspective-Four-Point Problem

titleDifferential Algebra

journaltitleDiscrete Comput. Geom.
titleProperness Defects of Projections and Computation of at Least One Point in Each Connected Component of a Real Algebraic Set

Association for Computing Machinery

journaltitleProc. ISSAC 2018
seriesISSAC '18
titleOn the Complexity of Computing Real Radicals of Polynomial Systems

journaltitleJ. Symb. Comput.
titleComputing Real Radicals and S-radicals of Polynomial Systems

booktitleSolving Polynomial Equations
seriesAlgorithms and Computation in Mathematics
titleIntroduction to Numerical Algebraic Geometry
family=The OSCAR team,

titleOSCAR – Open Source Computer Algebra Research System

journaltitleJ. Symb. Comput.
titleAn Elimination Method for Polynomial Systems

seriesTexts and Monographs in Symbolic Computation
titleElimination Methods

journaltitleFront. Comput. Sci. China
titleMathematics Mechanization and Applications after Thirty Years

titleBasic Principles of Mechanical Theorem Proving in Elementary Geometries

journaltitleInt. Workshop Autom. Deduc. Geom.
titleAutomated Discovering and Proving for Geometric Inequalities

journaltitleSci. China Ser. F Inf. Sci.
titleA Complete Algorithm for Automated Discovering of a Class of Inequality-Type Theorems

World Scientific

booktitleMathematical Software
titlePrime Decomposition of Polynomial Ideals over Finite Fields