Computer Science Department, Smith College, Northampton MA, USA and
http://goranmalic.com<EMAIL_ADDRESS><EMAIL_ADDRESS>https://orcid.org/0000-0001-9340-7827 Computer Science Department, Smith
College, Northampton, MA, USA and http://cs.smith.edu/~istreinu
<EMAIL_ADDRESS><EMAIL_ADDRESS>https://orcid.org/0000-0002-1825-0097
Goran Malić and Ileana Streinu <ccs2012> <concept>
<concept_id>10002944.10011123.10011674</concept_id> <concept_desc>General and
reference Performance</concept_desc>
<concept_significance>100</concept_significance> </concept> <concept>
<concept_id>10002944.10011123.10011131</concept_id> <concept_desc>General and
reference Experimentation</concept_desc>
<concept_significance>100</concept_significance> </concept> <concept>
<concept_id>10003752.10010061.10010063</concept_id> <concept_desc>Theory of
computation Computational geometry</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10002950.10003624.10003633.10003647</concept_id>
<concept_desc>Mathematics of computing Matroids and greedoids</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10002950.10003705.10011686</concept_id> <concept_desc>Mathematics
of computing Mathematical software performance</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10010147.10010148.10010149.10003628</concept_id>
<concept_desc>Computing methodologies Combinatorial algorithms</concept_desc>
<concept_significance>300</concept_significance> </concept> <concept>
<concept_id>10010147.10010148.10010149.10010150</concept_id>
<concept_desc>Computing methodologies Algebraic algorithms</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[100]General and reference Performance [100]General and reference
Experimentation [500]Theory of computation Computational geometry
[500]Mathematics of computing Matroids and greedoids [500]Mathematics of
computing Mathematical software performance [300]Computing methodologies
Combinatorial algorithms [300]Computing methodologies Algebraic algorithms
This is the full paper accompanying the extended abstract [33] Both authors
acknowledge funding from the NSF CCF:1703765 grant to Ileana Streinu.

# Combinatorial Resultants in the Algebraic Rigidity Matroid

Goran Malić  Ileana Streinu111Corresponding author

###### Abstract

Motivated by a rigidity-theoretic perspective on the Localization Problem in
2D, we develop an algorithm for computing circuit polynomials in the algebraic
rigidity matroid $\operatorname{CM}_{n}$ associated to the Cayley-Menger ideal
for $n$ points in 2D. We introduce combinatorial resultants, a new operation
on graphs that captures properties of the Sylvester resultant of two
polynomials in the algebraic rigidity matroid. We show that every rigidity
circuit has a construction tree from $K_{4}$ graphs based on this operation.
Our algorithm performs an algebraic elimination guided by the construction
tree, and uses classical resultants, factorization and ideal membership. To
demonstrate its effectiveness, we implemented our algorithm in Mathematica: it
took less than 15 seconds on an example where a Gröbner Basis calculation took
5 days and 6 hrs.

###### keywords:

Cayley-Menger ideal, rigidity matroid, circuit polynomial, combinatorial
resultant, inductive construction, Gröbner basis elimination

##  1 Introduction

This paper addresses combinatorial, algebraic and algorithmic aspects of a
question motivated by the following ubiquitous problem from distance geometry:

### Localization.

A graph together with weights associated to its edges is given. The goal is to
find placements of the graph in some Euclidean space, so that the edge lengths
match the given weights. In this paper, we work in 2D. A system of quadratic
equations can be easily set up so that the possible placements are among the
(real) solutions of this system. Rigidity Theory can help predict, a priori,
whether the set of solutions will be discrete (if the given weighted graph is
rigid) or continuous (if the graph is flexible). In the rigid case, the
double-exponential Gröbner basis algorithm can be used, in principle, to
eliminate all but one of the variables. Once a polynomial in a single variable
is obtained, numerical methods are used to solve it. We then select one
solution, substitute it in the original equations, eliminate to get a
polynomial in a new variable and repeat.

### Single Unknown Distance Problem.

Instead of attempting to directly compute the coordinates of all the vertices,
we restrict our attention to the related problem of finding the possible
values of a single unknown distance corresponding to a non-edge (a pair of
vertices that are not connected by an edge). Indeed, if we could solve this
problem for a collection of non-edge pairs that form a trilateration when
added to the original collection of edges, then a single solution in Cartesian
coordinates could be easily computed afterwards in linearly many steps of
quadratic equation solving.

### Rigidity circuits.

We formulate the single unknown distance problem in terms of Cayley rather
than Cartesian coordinates. Known theorems from Distance Geometry, Rigidity
Theory and Matroid Theory help reduce this problem to finding a certain
irreducible polynomial in the Cayley-Menger ideal, called the circuit
polynomial. Its support is a graph called a circuit in the rigidity matroid,
or shortly a rigidity circuit. Substituting given edge lengths in the circuit
polynomial results in a uni-variate polynomial which can be solved for the
unknown distance.

The focus of this paper is the following:

######  Main Problem.

Given a rigidity circuit, compute its corresponding circuit polynomial.

### Related work.

While both _distance geometry_ and _rigidity theory_ have a distinguished
history for which a comprehensive overview would be too long to include here,
very little is known about computing _circuit polynomials._ _To the best of
our knowledge,_ their study in _arbitrary_ polynomial ideals was initiated in
the PhD thesis of Rosen [39]. His Macaulay2 code [40] is useful for exploring
small cases, but the Cayley-Menger ideal is beyond its reach. A recent article
[41] popularizes algebraic matroids and uses for illustration the smallest
circuit polynomial $K_{4}$ in the Cayley-Menger ideal. _We could not find non-
trivial examples anywhere._ Indirectly related to our problem are results such
as [46], where an explicit univariate polynomial of degree 8 is computed (for
an unknown angle in a $K_{3,3}$ configuration given by edge lengths, from
which the placement of the vertices is determined) and [42], for its usage of
Cayley coordinates in the study of configuration spaces of some families of
distance graphs. A closely related problem is that of computing the _number of
embeddings of a minimally rigid graph_ [6], which has received _a lot_ of
attention in recent years (e.g. [8, 1, 16, 15], to name a few). References to
specific results in the literature that are relevant to the theory developed
here and to our proofs are given throughout the paper.

### How tractable is the problem?

Circuit polynomial computations can be done, in principle, with the double-
exponential time Gröbner basis algorithm with an elimination order. On one
example, the GroebnerBasis function of Mathematica 12 (running on a 2019 iMac
computer with 6 cores at 3.6Ghz) took 5 days and 6 hours, but in most cases it
timed out or crashed. Our goal is to make such calculations more tractable by
taking advantage of structural information inherent in the problem.

### Our Results.

We describe a new algorithm to compute a circuit polynomial with known
support. It relies on resultant-based elimination steps guided by a novel
inductive construction for rigidity circuits. While inductive constructions
have been often used in Rigidity Theory, most notably the Henneberg sequences
for Laman graphs [24] and Henneberg II sequences for rigidity circuits [3], we
argue that our construction is more natural due to its direct algebraic
interpretation. In fact, this paper originated from our attempt to interpret
Henneberg II algebraically. We have implemented our method in Mathematica and
applied it successfully to compute all circuit polynomials on up to $6$
vertices and a few on $7$ vertices, the largest of which having over two
million terms. The previously mentioned example that took over 5 days to
complete with GroebnerBasis, was solved by our algorithm in less than 15
seconds.

### Main Theorems.

We first define the combinatorial resultant of two graphs as an abstraction of
the classical resultant. Our main theoretical result is split into the
combinatorial Theorem 1.1 and the algebraic Theorem 1.2, each with an
algorithmic counterpart.

######  Theorem 1.1.

Each rigidity circuit can be obtained, inductively, by applying combinatorial
resultant operations starting from $K_{4}$ circuits. The construction is
captured by a binary resultant tree whose nodes are intermediate rigidity
circuits and whose leaves are $K_{4}$ graphs.

Theorem 1.1 leads to a graph algorithm for finding a combinatorial resultant
tree of a circuit. Each step of the construction can be carried out in
polynomial time using variations on the Pebble Game matroidal sparsity
algorithms [30] combined with Hopcroft and Tarjan’s linear time
$3$-connectivity algorithm [25]. However, it is conceivable that the tree
could be exponentially large and thus the entire construction could take an
exponential number of steps: understanding in detail the algorithmic
complexity of our method remains a problem for further investigation.

######  Theorem 1.2.

Each circuit polynomial can be obtained, inductively, by applying resultant
operations. The procedure is guided by the combinatorial resultant tree from
Theorem 1.1 and builds up from $K_{4}$ circuit polynomials. At each step, the
resultant produces a polynomial that may not be irreducible. A polynomial
factorization and a test of membership in the ideal is applied to identify the
factor which is the circuit polynomial.

The resulting algebraic elimination algorithm runs in exponential time, in
part because of the growth in size of the polynomials that are being produced.
Several theoretical open questions remain, whose answers may affect the
precise time complexity analysis.

### Computational experiments.

We implemented our algorithms in Mathematica V12.1.1.0 on two personal
computers with the following specifications: Intel i5-9300H 2.4GHz, 32 GB RAM,
Windows 10 64-bit; and Intel i5-9600K 3.7GHz, 16 GB RAM, macOS Mojave 10.14.5.
We also explored Macaulay2, but it was much slower than Mathematica (hours vs.
seconds) in computing one of our examples. The polynomials resulting from our
calculations are made available on a github repository [31].

### Overview of the paper.

In Section 2 we introduce the background concepts from matroid theory and
rigidity theory. We introduce combinatorial resultants in Section 3, prove
Theorem 1.1 and describe the algorithm for computing a combinatorial resultant
tree. In Section 4 we introduce the background concepts pertaining to
resultants and elimination ideals. In Section 5 we introduce algebraic
matroids. In Section 6 we introduce the Cayley-Menger ideal and define
properties of its circuit polynomials. In Section 7 we prove Theorem 1.2 and
in Section 8 we present a summary of the preliminary experimental results we
carried with our implementation. We conclude in Section 9 with a summary of
remaining open questions.

##  2 Preliminaries: rigidity circuits

We start with the combinatorial aspects of our problem. In this section we
review the essential notions and results from combinatorial rigidity theory of
bar-and-joint frameworks in dimension $2$ that are relevant for our paper.

### Notation.

We work with (sub)graphs given by subsets $E$ of edges of the complete graph
$K_{n}$ on vertices $[n]:=\\{1,\cdots,n\\}$. If $G$ is a (sub)graph, then
$V(G)$, resp. $E(G)$ denote its vertex, resp. edge set. The support of $G$ is
$E(G)$. The vertex span $V(E)$ of edges $E$ is the set of all edge-endpoint
vertices. A subgraph $G$ is spanning if its edge set $E(G)$ spans $[n]$. The
neighbours $N(v)$ of $v$ are the vertices adjacent to $v$ in $G$.

### Frameworks.

A 2D bar-and-joint framework is a pair $(G,p)$ of a graph $G=(V,E)$ whose
vertices $V=[n]:=\\{1,2,\dots,n\\}$ are mapped to points
$p=\\{p_{1},\dots,p_{n}\\}$ in $\mathbb{R}^{2}$ via the _placement map_
$p\colon V\to\mathbb{R}^{2}$ given by $i\mapsto p_{i}$. We view the edges as
rigid bars and the vertices as rotatable joints which allow the framework to
deform continuously as long as the bars retain their original lengths. The
realization space of the framework is the set of all its possible placements
in the plane with the same bar lengths. Two realizations are congruent if they
are related by a planar isometry. The configuration space of the framework is
made of congruence classes of realizations. The deformation space of a given
framework is the particular connected component of the configuration space
that contains it.

A framework is rigid if its deformation space consists in exactly one
configuration, and flexible otherwise. Combinatorial rigidity theory of bar-
and-joint frameworks seeks to understand the rigidity and flexibility of
frameworks in terms of their underlying graphs.

### Laman Graphs.

The following theorem relates rigidity theory of 2D bar-and-joint frameworks
to graph sparsity.

######  Theorem 2.1 (Laman’s Theorem).

A bar-and-joint framework is generically minimally rigid in 2D iff its
underlying graph $G=(V,E)$ has exactly $|E|=2|V|-3$ edges, and any proper
subset $V^{\prime}\subset V$ of vertices spans at most $2|V^{\prime}|-3$
edges.

The genericity condition appearing in the statement of this theorem refers to
the placements of the vertices. We’ll introduce this concept rigorously in
Section 6. For now we retain the most important consequence of the genericity
condition, namely that small perturbations of the vertex placements do not
change the rigidity or flexibility properties of the framework. This allows us
to refer to the rigidity and flexibility of a (generic) framework solely in
terms of its underlying graph.

A graph satisfying the conditions of Laman’s theorem is called a Laman graph.
It is minimally rigid in the sense that it has just enough edges to be rigid:
if one edge is removed, it becomes flexible. Adding extra edges to a Laman
graph keeps it rigid, but the minimality is lost. Such graphs are said to be
rigid and overconstrained. In short, for a graph to be rigid, its vertex set
must span a Laman graph; otherwise the graph is flexible.

### Matroids.

A matroid is an abstraction capturing (in)dependence relations among
collections of elements from a ground set, and is inspired by both linear
dependencies (among, say, rows of a matrix) and by algebraic constraints
imposed by algebraic equations on a collection of otherwise free variables.
The standard way to specify a matroid is via its independent sets, which have
to satisfy certain axioms [38] (skipped here, since they are not relevant for
our presentation). A base is a maximal independent set and a set which is not
independent is said to be dependent. A minimal dependent set is called a
circuit. Relevant for our purposes are the following general aspects: (a)
(hereditary property) a subset of an independent set is also independent; (b)
all bases have the same cardinality, called the rank of the matroid. Further
properties will be introduced in context, as needed.

In this paper we encounter three types of matroids: a graphic matroid, defined
on a ground set given by all the edges $E_{n}:=\\{ij:1\leq i<j\leq n\\}$ of
the complete graph $K_{n}$; this is the $(2,3)$-sparsity matroid or the
generic rigidity matroid described below; a linear matroid, defined on an
isomorphic set of row vectors of the rigidity matrix associated to a bar-and-
joint framework; and an algebraic matroid, defined on an isomorphic ground set
of variables $X_{n}:=\\{x_{ij}:1\leq i<j\leq n\\}$; this is the algebraic
matroid associated to the Cayley-Menger ideal and will be defined in Section
6.

### The $(2,3)$-sparsity matroid: independent sets, bases, circuits.

The $(2,3)$-sparse graphs on $n$ vertices form the collection of independent
sets for a matroid $\operatorname{\mathcal{S}}_{n}$ on the ground set $E$ of
edges of the complete graph $K_{n}$ [47], called the (generic) 2D rigidity
matroid. The bases of the matroid $\operatorname{\mathcal{S}}_{n}$ are the
maximal independent sets, hence the Laman graphs. A set of edges which is not
sparse is a dependent set. For instance, adding one edge to a Laman graph
creates a dependent set of $2n-2$ edges, called a Laman-plus-one graph (Fig.
1).

Figure 1: A Laman-plus-one graph contains a unique circuit (highlighted):
(Left two) The circuit is not spanning the entire vertex set. (Right) A
spanning circuit.

A minimal dependent set is a (sparsity) circuit. The edges of a circuit span a
subset of the vertices of $V$. A circuit spanning $V$ is said to be a spanning
or maximal circuit in the sparsity matroid $\operatorname{\mathcal{S}}_{n}$.
See Fig. 2 for examples.

Figure 2: The four types of circuits on $n=6$ vertices: 2D double-banana,
$5$-wheel $W_{5}$, Desargues-plus-one and $K_{3,3}$-plus-one.

A Laman-plus-one graph contains a unique subgraph which is minimally
dependent, in other words, a unique circuit. A spanning rigidity circuit
$C=(V,E)$ is a special case of a Laman-plus-one graph: it has a total of
$2n-2$ edges but it satisfies the $(2,3)$-sparsity condition on all proper
subsets of at most $n^{\prime}\leq n-1$ vertices. Simple sparsity
considerations can be used to show that the removal of any edge from a circuit
results in a Laman graph.

Figure 3: Splitting a $2$-connected circuit into $3$-connected circuits via
inverse of two-sum operations.

### Operations on circuits.

If $G_{1}$ and $G_{2}$ are two graphs, we use a consistent notation for their
number of vertices and edges $n_{i}=|V(G_{i})|$, $m_{i}=|E(G_{i})|$, $i=1,2$,
and for their union and intersection of vertices and edges, as in
$V_{\cup}=V(G_{1})\cup V(G_{2})$, $V_{\cap}=V(G_{1})\cap V(G_{2})$,
$n_{\cup}=|V_{\cup}|$, $n_{\cap}=|V_{\cap}|$ and similarly for edges, with
$m_{\cup}=|E_{\cup}|$ and $m_{\cap}=|E_{\cap}|$. Let $C_{1}$ and $C_{2}$ be
two circuits with exactly one common edge $uv$. Their $2$-sum is the graph
$C=(V,E)$ with $V=V_{\cup}$ and $E=E_{\cup}\setminus\\{uv\\}$. The inverse
operation of splitting $C$ into $C_{1}$ and $C_{2}$ is called a $2$-split
(Fig. 3).

######  Lemma 2.2.

Any $2$-sum of two circuits is a circuit. Any 2-split of a circuit is a pair
of circuits.

######  Proof 2.3.

From sparsity consideration, we prove that the $2$-sum has $2n-2$ edges (on
$n$ vertices), and $(2,3)$-sparsity is also maintained on subsets. Indeed, the
total number of edges in the $2$-sum is
$m_{1}+m_{2}-2=2n_{1}-2+2n_{2}-2-2=2(n_{1}+n_{2}-2)-2=2n-2$.

See also [3], Lemmas 4.1, 4.2.

Note that not every circuit admits a $2$-separation, e.g. the Desargues-plus-
one circuit does not admit a $2$-separation. However every circuit that is not
$3$-connected does admit a $2$-separation (see also Lemma 2.4(c) in [3]).

### Connectivity.

It is well known and easy to show that a circuit is always a $2$-connected
graph. If a circuit is not $3$-connected, we refer to it simply as a
$2$-connected circuit. The Tutte decomposition [43] of a $2$-connected graph
into $3$-connected components amounts to identifying separating pairs of
vertices. For a circuit, the separating pairs induce $2$-splits (inverse of
$2$-sum) operations and produce smaller circuits. Thus a $2$-connected circuit
can be constructed from $3$-connected circuits via $2$-sums (Fig. 3).

Figure 4: A Henneberg II extension of the Desargues-plus-one circuit.

### Inductive constructions for $3$-connected circuits.

A Henneberg II extension (also called an edge splitting operation) is defined
for an edge $uv$ and a non-incident vertex $w$, as follows: the edge $uv$ is
removed, a new vertex $a$ and three new edges $au,av,aw$ are added. Berg and
Jordan [3] have shown that, if $G$ is a $3$-connected circuit, then a
Henneberg II extension on $G$ is also a $3$-connected circuit. The inverse
Henneberg II operation on a circuit removes one vertex of degree $3$ and adds
a new edge among its three neighbors in such a way that the result is also a
circuit. Berg and Jordan have shown that every $3$-connected circuit admits an
inverse Henneberg II operation which also maintains $3$-connectivity. As a
consequence, a $3$-connected circuit has an inductive construction, i.e. it
can be obtained from $K_{4}$ by Henneberg II extensions that maintain
$3$-connectivity. Their proof is based on the existence of two non-adjacent
vertices with $3$-connected inverse Henneberg II circuits. We will make use in
Section 3 of the following weaker result, which does not require the
maintenance of $3$-connectivity in the inverse Henneberg II operation.

######  Lemma 2.4 (Theorem 3.8 in [3]).

Let $G=(V,E)$ be a $3$-connected circuit with $|V|\geq 5$. Then $G$ either has
four vertices that admit an inverse Henneberg II that is a circuit, or $G$ has
three pairwise non-adjacent vertices that admit an inverse Henneberg II that
is a circuit (not necessarily $3$-connected).

##  3 Combinatorial Resultants

We define now the combinatorial resultant operation on two graphs, prove
Theorem 1.1 and describe its algorithmic implications.

Figure 5: A $4$-wheel $W_{4}$, a complete $K_{4}$ graph, their common Laman
graph (dotted, with red elimination edge) and their combinatorial resultant,
which is a Laman-plus-one graph but not a circuit.

### Combinatorial resultant.

Let $G_{1}$ and $G_{2}$ be two distinct graphs with non-empty intersection
$E_{\cap}\neq\emptyset$ and let $e\in E_{\cap}$ be a common edge. The
combinatorial resultant of $G_{1}$ and $G_{2}$ on the elimination edge $e$ is
the graph $\operatorname{CRes}(G_{1},G_{2},e)$ with vertex set $V_{\cup}$ and
edge set $E_{\cup}\setminus\\{e\\}$.

The 2-sum appears as a special case of a combinatorial resultant when the two
graphs have exactly one edge in common, which is eliminated by the operation.
Circuits are closed under the $2$-sum operation, but they are not closed under
general combinatorial resultants (Fig. 5). We are interested in combinatorial
resultants that produce circuits from circuits.

### Circuit-valid combinatorial resultant sequences.

Two circuits are said to be properly intersecting if their common subgraph is
Laman.

######  Lemma 3.1.

The combinatorial resultant of two circuits has $m=2n-2$ edges iff the common
subgraph $G_{\cap}$ of the two circuits is Laman.

Figure 6: A $4$-wheel $W_{4}$ and a complete $K_{4}$ graph, their common Laman
graph (dotted, with red elimination edge) and their combinatorial resultant,
the $5$-wheel $W_{5}$ circuit.

######  Proof 3.2.

Let $C_{1}$ and $C_{2}$ be two circuits with $n_{i}$ vertices and $m_{i}$
edges, $i=1,2$, and let $C$ be their combinatorial resultant with $n$ vertices
and $m$ edges. By inclusion-exclusion $n=n_{1}+n_{2}-n_{\cap}$ and
$m=m_{1}+m_{2}-m_{\cap}-1$. Substituting here the values for $m_{1}=2n_{1}-2$
and $m_{2}=2n_{2}-2$, we get
$m=2n_{1}-2+2n_{2}-2-m_{\cap}-1=2(n_{1}+n_{2}-n_{\cap})-2+2n_{\cap}-3-m_{\cap}=(2n-2)+(2n_{\cap}-3)-m_{\cap}$.
We have $m=2n-2$ iff $m_{\cap}=2n_{\cap}-3$. Since both $C_{1}$ and $C_{2}$
are circuits, it is not possible that one edge set be included in the other:
circuits are minimally dependent sets of edges and thus cannot contain other
circuits. As a proper subset of both $E_{1}=E(C_{1})$ and $E_{2}=E(C_{2})$,
$E_{\cap}$ satisfies the hereditary $(2,3)$-sparsity property. If furthermore
$G_{\cap}$ has exactly $2n_{\cap}-3$ edges, then it is Laman.

A combinatorial resultant operation applied to two properly intersecting
circuits is said to be circuit-valid if it results in a spanning circuit. An
example is shown in Fig. 6. Being properly intersecting is a necessary but not
sufficient condition for the combinatorial resultant of two circuits to
produce a circuit (Fig. 5).

######  Problem 3.3.

Find necessary and sufficient conditions for the combinatorial resultant of
two circuits to be a circuit.

In Section 2 we have seen that a $2$-connected circuit can be obtained from
$3$-connected circuits via $2$-sums. The proof of Theorem 1.1 is completed by
Proposition 3.4 below.

######  Proposition 3.4.

Let $C=(V,E)$ be a $3$-connected circuit spanning $n+1\geq 5$ vertices. Then,
in polynomial time, we can find two circuits $A$ and $B$ such that $A$ has $n$
vertices, $B$ has at most $n$ vertices and $C$ can be represented as the
combinatorial resultant of $A$ and $B$.

######  Proof 3.5.

We apply a weaker version of Lemma 2.4 to find two non-adjacent vertices $a$
and $b$ of degree 3 such that a circuit
$A=(V\setminus{\\{a\\}},E\setminus{\\{au,av,aw\\}})$ can be produced via an
inverse Henneberg II operation on vertex $a$ in $C$ (see Fig. 7). Let the
neighbors of vertex $a$ be $N(a)=\\{u,v,w\\}$ such that $e=uw$ was not an edge
of $C$ and is the one added to obtain the new circuit $A$.

Figure 7:  The 3-connected circuit $C$ spanning $n+1$ vertices with two non-
adjacent vertices $a$ (red) and $b$ (blue) of degree 3. Note that $N(a)$ and
$N(b)$ may not be disjoint. An inverse Henneberg II at $a$ removes the red
edges at $a$ and adds dotted red edge $e=uv$. Circuit $A$ (red).

To define circuit $B$, we first let $L$ be the subgraph of $C$ induced by
$V\setminus\\{b\\}$. Simple sparsity consideration show that $L$ is a Laman
graph. The graph $D$ obtained from $L$ by adding the edge $e=uv$, as in Fig. 8
(left), is a Laman-plus-one graph containing the three edges incident to $a$
(which are not in $A$) and the edge $e$ (which is in $A$). $D$ contains a
unique circuit $B$ (Fig. 8 left) with edge $e\in B$ (see e.g. [38, Proposition
1.1.6]). It remains to prove that $B$ contains $a$ and its three incident
edges. If $B$ does not contain $a$, then it is a proper subgraph of $A$. But
this contradicts the minimality of $A$ as a circuit. Therefore $a$ is a vertex
in $B$, and because a vertex in a circuit can not have degree less than $3$,
$B$ contains all its three incident edges.

Figure 8:  Remove from $C$ the edges from $b$ (blue dotted) and add red edge
$e$. Circuit $B$ (blue).

The combinatorial resultant $\operatorname{CRes}(A,B,e)$ of the circuits $A$
and $B$ with $e$ the eliminated edge satisfies the desired property that
$C=\operatorname{CRes}(A,B,e)$.

The algorithm below captures this procedure. The main steps, the Inverse
Henneberg II step on a circuit at line 4 and finding the unique circuit in a
Laman-plus-one graph at line 6 can be done in polynomial time using properties
of the $(2,3)$ and $(2,2)$-sparsity pebble games from [30].

Algorithm 1 Inverse Combinatorial Resultant

Input: $3$-connected circuit $C$
Output: circuits $A$, $B$ and edge $e$ such that
$C=\operatorname{CRes}(A,B,e)$

1:for each vertex $a$ of degree $3$ do

2: if inverse Henneberg II is possible on $a$

3: and there is a non-adjacent degree $3$ vertex $b$ then

4: Get circuit $A$ and edge $e$ by inverse Henneberg II in $C$ on $a$

5: Let $D=C$ without $b$ (and its edges) and with new edge $e$

6: Compute unique circuit $B$ in $D$

7: return circuits $A,B$ and edge $e$

8: end if

9:end for

### Resultant tree.

The inductive construction of a circuit using combinatorial resultant
operations can be represented in a tree structure. Let $C$ be a rigidity
circuit with $n$ vertices. A _resultant tree_ $T_{C}$ for the circuit $C$ is a
rooted binary tree with $C$ as its root and such that: (a) the nodes of
$T_{C}$ are circuits; (b) circuits on level $l$ have at most $n-l$ vertices;
(c) the two children $\\{C_{j},C_{k}\\}$ of a parent circuit $C_{i}$ are such
that $C_{i}=\operatorname{CRes}(C_{j},C_{k},e)$, for some common edge $e$, and
(d) the leaves are complete graphs on 4 vertices. The complexity of finding a
resultant tree depends on the size of the tree, whose depth is at most $n-4$.
The combinatorial resultant tree may thus be anywhere between linear to
exponential in size. The best case occurs when the resultant tree is path-
like, with each internal node having a $K_{4}$ leaf. The worst case could be a
complete binary tree: each internal node at level $k$ would combine two
circuits with the same number of vertices $n-k-1$ into a circuit with $n-k$
vertices. Sporadic examples of small balanced combinatorial resultant trees
exist (e.g. $K_{33}$-plus-one), but it remains an open problem to find
infinite families of such examples. Even if such a family would be found, it
is still conceivable that alternative, non-balanced combinatorial resultant
trees could yield the same circuit.

######  Problem 3.6.

Characterize the circuits produced by the worst-case size of the combinatorial
resultant tree.

######  Problem 3.7.

Are there infinite families of circuits with only balanced combinatorial
resultant trees?

######  Problem 3.8.

Refine the time complexity analysis of the combinatorial resultant tree
algorithm.

######  Corollary 3.9.

The representation of $C$ as the combinatorial resultant of two smaller
circuits is not unique, in general. An example is the “double-banana”
2-connected circuit shown in Figure 9.

Figure 9: The 2-connected double-banana circuit can be obtained as
combinatorial resultant from two $K_{4}$ graphs (left, $2$-sum), and from two
wheels on 4 vertices (right). Dashed lines indicate the eliminated edges, and
in each case one of the two circuits is highlighted to distinguish $K_{4}$
from $W_{4}$.

##  4 Preliminaries: Resultants and Elimination Ideals

We turn now to the algebraic aspects of our problem. In this section we review
known concepts and facts about resultants and elimination ideals that are
essential ingredients of our proofs in Section 7.

### Resultants.

The resultant can be introduced in several equivalent ways [19]. Here we use
its definition as the determinant of the Sylvester matrix.

Let $R$ be a ring of polynomials and $f,g\in R[x]$ with $\deg_{x}f=r$ and
$\deg_{x}g=s$ be such that at least one of $r$ or $s$ is positive and

$\displaystyle f(x)$ $\displaystyle=a_{r}x^{r}+\cdots+a_{1}x+a_{0},$
$\displaystyle g(x)$ $\displaystyle=b_{s}x^{s}+\cdots+b_{1}x+b_{0}$

The _resultant_ of $f$ and $g$ with respect to the indeterminate $x$, denoted
$\operatorname{Res}(f,g,x)$, is the determinant of the $(r+s)\times(r+s)$
Sylvester matrix

$\operatorname{Syl}(f,g,x)=\begin{pmatrix}a_{r}&a_{r-1}&a_{r-2}&\cdots&a_{0}&0&0&\cdots&0\\\
0&a_{r}&a_{r-1}&\cdots&a_{1}&a_{0}&0&\cdots&0\\\
0&0&a_{r}&\cdots&a_{2}&a_{1}&a_{0}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&0\\\
0&0&0&\cdots&a_{r}&a_{r-1}&a_{r-2}&\ddots&a_{0}\\\
b_{s}&b_{s-1}&b_{s-2}&\cdots&b_{0}&0&0&\cdots&0\\\
0&b_{s}&b_{s-1}&\cdots&b_{1}&b_{0}&0&\cdots&0\\\
0&0&b_{s}&\cdots&b_{2}&b_{1}&b_{0}&\cdots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&0\\\
0&0&0&\cdots&b_{s}&b_{s-1}&b_{s-2}&\ddots&b_{0}\end{pmatrix}$

where the submatrix $S_{f}$ containing only the coefficients of $f$ is of
dimension $s\times(r+s)$, and the submatrix $S_{g}$ containing only the
coefficients of $g$ is of dimension $r\times(r+s)$. Unless $r=s$, the columns
$(a_{0}\leavevmode\nobreak\ a_{1}\leavevmode\nobreak\
\cdots\leavevmode\nobreak\ a_{r})$ and $(b_{0}\leavevmode\nobreak\
b_{1}\leavevmode\nobreak\ \cdots\leavevmode\nobreak\ b_{s})$ of $S_{f}$ and
$S_{g}$, respectively, are not aligned in the same column of
$\operatorname{Syl}(f,g,x)$, as displayed above, but rather the first is
shifted to the left or right of the second, depending on the relationship
between $r$ and $s$. We will make implicit use of the following well-known
symmetric and multiplicative properties of the resultant:

######  Proposition 4.1.

([19, pp. 398]) Let $f,g,h\in R[x]$. The resultant of $f$ and $g$ satisfies

  * •

$\operatorname{Res}(f,g,x)=(-1)^{rs}\operatorname{Res}(g,f,x)$,

  * •

$\operatorname{Res}(fg,h,x)=\operatorname{Res}(f,h,x)\operatorname{Res}(g,h,x)$.

######  Proposition 4.2.

Let $R$ be a unique factorization domain and $f,g\in R[x]$. Then $f$ and $g$
have a common factor in $R[x]$ if and only if $\operatorname{Res}(f,g,x)=0$.

This proposition is stated in [22, pp. 9] without proof. When $R$ is a field,
a proof of this property can be found in [9, Chapter 3, Proposition 3 of §6],
which directly generalizes to polynomial rings via Hilbert’s Nullstellensatz.

### Homogeneous properties.

Circuit polynomials in the Cayley-Menger ideal are homogeneous polynomials
(see Proposition 6.8), hence we are interested in the properties of the
resultant of homogenous polynomials. It is well known that the resultant
$\operatorname{Res}(f,g,x)$ of two homogeneous polynomials is itself
homogeneous, and with degree
$m\deg_{x}{g}+n\deg_{x}{f}-\deg_{x}{f}\cdot\deg_{x}{g}$, where $m$, resp. $n$
are the homogeneous degrees of $f$, resp. $g$. For completeness we prove these
two facts; the exposition follows [9].

Let $m$, $n$, $r$ and $s$ be positive integers such that $m\geq r$ and $n\geq
s$. Let $f$ and $g$ be polynomials of degree $r$ and $s$ in $x$, with generic
coefficients $a_{m-r}$, $\dots$, $a_{m}$ and $b_{n-s}$, $\dots$, $b_{n}$,
respectively, i.e.

$\displaystyle f(x)$ $\displaystyle=a_{m-r}x^{r}+\cdots+a_{m-1}x+a_{m},$
$\displaystyle g(x)$ $\displaystyle=b_{n-s}x^{s}+\cdots+b_{n-1}x+b_{n}.$

######  Proposition 4.3.

The resultant $\operatorname{Res}(f,g,x)$ is a homogeneous polynomial in the
ring $\mathbb{Z}[a_{m-r},\dots,a_{m},$ $b_{n-s},\dots,b_{n}]$ of degree $r+s$.

######  Proof 4.4.

This property follows from the Leibniz expansion of the determinant of the
Sylvester matrix $\operatorname{Syl}(f,g,x)=(S_{i,j})$, where $S_{i,j}$ is the
$(i,j)$-th entry, which shows that each term of $\operatorname{Res}(f,g,x)$
is, up to sign, equal to

$\prod_{i=1}^{r+s}{S_{i,\sigma(i)}}$

for some permutation $\sigma$ of the set $[r+s]$. This term is non-zero if and
only if $S_{i,\sigma(i)}\neq 0$ for all $i\in[r+s]$, and since
$S_{i,\sigma(i)}\in\\{a_{m-r},\dots,a_{m},b_{n-s},\dots,b_{n}\\}$, the
homogeneous degree of $\operatorname{Res}(f,g,x)$ is $r+s$.

######  Proposition 4.5.

Let $f=a_{m-r}x^{r}+\cdots+a_{m-1}x+a_{m}$ and
$g=b_{n-s}x^{s}+\cdots+b_{n-1}x+b_{n}$ be homogeneous polynomials in
$k[y_{1},\dots,y_{t},x]$ of homogeneous degree $m$ and $n$, respectively, so
that $a_{i},b_{j}\in k[y_{1},\dots,y_{t}]$ are homogeneous of degree $i$, for
all $i\in\\{m-r,\dots,m\\}$ and all $j\in\\{n-s,\dots,n\\}$. If
$\operatorname{Res}(f,g,x)\neq 0$, then it is a homogeneous polynomial in
$k[y_{1},\dots,y_{t}]$ of degree

$m\deg_{x}{g}+n\deg_{x}{f}-\deg_{x}{f}\cdot\deg_{x}{g}=ms+nr-rs.$

We were not able to find a reference for this proposition in the literature,
however the case when $f$, resp. $g$ are homogeneous of degree $r$, resp. $s$
and such that $\deg_{x}f=r$ and $\deg_{x}g=s$, so that

$\displaystyle f$ $\displaystyle=a_{0}x^{r}+\cdots+a_{1}x+a_{r},$
$\displaystyle g$ $\displaystyle=b_{0}x^{s}+\cdots+b_{1}x+b_{s},$

can be found in e.g. [9, pp. 454] as Lemma 5 of $\S 7$ of Chapter 8, stating
that in that case $\operatorname{Res}(f,g,x)$ is of homogeneous degree $rs$.
The proof below is a direct adaptation of the proof of Lemma 5 in [9, pp.
454], and the Lemma 5 itself follows directly from Proposition 4.5 by
substituting $m\to r$ and $n\to s$ so to obtain $rs+sr-rs=rs$.

######  Proof 4.6.

Let $\operatorname{Syl}(f,g,x)=(S_{i,j})$ be the Sylvester matrix of $f$ and
$g$ with respect to $x$, and let, up to sign,
$\prod_{i=1}^{r+s}S_{i,\sigma(i)}$ be a non-zero term in the Leibniz expansion
of its determinant for some permutation $\sigma$ of $[r+s]$.

A non-zero entry $S_{i,\sigma(i)}$ has degree $m-(r+i-\sigma(i))$ if $1\leq
i\leq s$ and degree $n-(i-\sigma(i))$ if $s+1\leq i\leq r+s$. Therefore, the
total degree of $\prod_{i=1}^{r+s}S_{i,\sigma(i)}$ is

$\displaystyle\sum_{i=1}^{s}[m-(r+i-\sigma(i))]+\sum_{i=s+1}^{r+s}[n-(i-\sigma(i))]=\sum_{i=1}^{s}(m-r)+\sum_{i=s+1}^{s+r}n-\sum_{i=1}^{r+s}(i-\sigma(i))$
$\displaystyle=$ $\displaystyle
s(m-r)+rn-0=m\deg_{x}g+n\deg_{x}f-\deg_{x}f\cdot\deg_{x}g.$

### Elimination ideals.

Let $I$ be an ideal of $\mathbb{Q}[X]$ and $X^{\prime}\subset X$ non-empty.
The _elimination ideal_ of $I$ with respect to $X^{\prime}$ is the ideal
$I\cap\mathbb{Q}[X^{\prime}]$ of the ring $\mathbb{Q}[X^{\prime}]$.

Elimination ideals frequently appear in the context of Gröbner bases [7, 9]
which give a general approach for computing elimination ideals: if
$\mathcal{G}$ is a Gröbner basis for $I$ with respect to an _elimination
order_ (see Exercises 5 and 6 in §1 of Chapter 3 in [9]), e.g. the
lexicographic order $x_{i_{1}}>x_{i_{2}}>\dots>x_{i_{n}}$, then the
elimination ideal $I\cap\mathbb{Q}[x_{i_{k+1}},\dots,x_{i_{n}}]$ which
eliminates the first $k$ indeterminates from $I$ in the specified order has
$\mathcal{G}\cap\mathbb{Q}[x_{i_{k+1}},\dots,x_{i_{n}}]$ as its Gröbner basis.

We will frequently make use of the following well-known result.

######  Proposition 4.7.

If $I$ is a prime ideal of $\mathbb{Q}[X]$ and $X^{\prime}\subset X$ is non-
empty, then the elimination ideal $I\cap\mathbb{Q}[X^{\prime}]$ is prime.

######  Proof 4.8.

If $f\cdot g\in I\cap\mathbb{Q}[X^{\prime}]$ then certainly $f\cdot g\in I$ so
at least one of $f$ or $g$ is in $I\cap\mathbb{Q}[X^{\prime}]$.

Let $X^{\prime}\subset X$ be non-empty and $R=\mathbb{Q}[X^{\prime}]$.
Furthermore, let $f,g\in R[x]$, where $x\in X\setminus X^{\prime}$. It is
clear from the definition of the resultant that $\operatorname{Res}(f,g,x)\in
R$. In Section 7 we will make use of the following proposition.

######  Proposition 4.9.

Let $I$ be an ideal of $R[x]$ and $f,g\in I$. Then $\operatorname{Res}(f,g,x)$
is in the elimination ideal $I\cap R$.

A proof of this proposition can be found in [9, pp. 167].

##  5 Preliminaries: Ideals and Algebraic Matroids

Recall that a set of vectors in a vector space is linearly dependent if there
is a non-trivial linear relationship between them. Similarly, given a finite
collection $A$ of complex numbers, we say that $A$ is _algebraically
dependent_ if there is a non-trivial polynomial relationship between the
numbers in $A$.

More precisely, let $k$ be a field (e.g. $k=\mathbb{Q}$) and $k\subset F$ a
field extension of $k$. Let $A=\\{\alpha_{1},\dots,\alpha_{n}\\}$ be a finite
subset of $F$.

######  Definition 5.1.

We say that $A$ is algebraically dependent over $k$ if there is a non-zero
(multivariate) polynomial with coefficients in $k$ vanishing on $A$.
Otherwise, we say that $A$ is algebraically independent over $k$.

### Algebraic independence and algebraic matroids.

It was noticed by van der Waerden that the algebraically independent subsets
$A$ of a finite subset $E$ of $F$ satisfy matroid axioms [44, 45] and
therefore define a matroid called _the algebraic matroid on $E$ over $k$_.

######  Definition 5.2.

Let $k$ be a field and $k\subset F$ a field extension of $k$. Let
$E=\\{\alpha_{1},\dots,\alpha_{n}\\}$ be a finite subset of $F$. The
_algebraic matroid on $E$ over $k$_ is the matroid $(E,\mathcal{I})$ such that
$I\in\mathcal{I}$ if and only if $I$ is algebraically independent over $k$.

In this paper we use an equivalent definition of algebraic matroids in terms
of polynomial ideals. Before stating this equivalent defintion, we will first
recall some elementary definitions and properties of ideals in polynomial
rings. For a general reference on polynomial rings the reader may consult
[29].

### Notations and conventions.

To keep the presentation focused on the goal of the paper, we refrain from
giving the most general form of a statement or a proof. We work over the field
of rational numbers $\mathbb{Q}$. In this section, the set of variables
$X_{n}$ denotes $X_{n}=\\{x_{i}:1\leq i\leq n\\}$. Polynomial rings $R$ are
always of the form $R=\mathbb{Q}[X]$, over sets of variables $X\subset X_{n}$.
The _support_ $\operatorname{supp}{f}$ of a polynomial $f\in\mathbb{Q}[X_{n}]$
is the set of indeterminates appearing in $f$. The degree of a variable $x$ in
a polynomial $f$ is denoted by $\deg_{x}f$.

### Polynomial ideals.

A set of polynomials $I\subset\mathbb{Q}[X]$ is an _ideal of_ $\mathbb{Q}[X]$
if it is closed under addition and multiplication by elements of
$\mathbb{Q}[X]$. Every ideal contains the zero ideal $\\{0\\}$, and if an
ideal $I$ contains an element of $\mathbb{Q}$, then $I=\mathbb{Q}[X]$. A
generating set for an ideal is a set $S\subset\mathbb{Q}[X]$ of polynomials
such that every polynomial in the ideal is an algebraic combination (addition
and multiplication) of elements in $S$ with coefficients in $\mathbb{Q}[X]$.
Hilbert Basis Theorem (see [9]) guarantees that every ideal in a polynomial
ring has a finite generating set. Ideals generated by a single polynomial are
called _principal_. An ideal $I$ is a _prime_ ideal if, whenever $fg\in I$,
then either $f\in I$ or $g\in I$. A polynomial is irreducible (over
$\mathbb{Q}$) if it cannot decomposed into a product of non-constant
polynomials in $\mathbb{Q}[X]$. A principal ideal is prime iff it is generated
by an irreducible polynomial. However, an ideal generated by two or more
irreducible polynomials is not necessarily prime.

Let $I$ be an ideal of $R=\mathbb{Q}[X_{n}]$. A _minimal prime ideal over_ $I$
is a prime ideal of $R$ minimal among all prime ideals containing $I$ with
respect to set inclusion. By Zorn’s lemma a proper ideal of
$\mathbb{Q}[X_{n}]$ always has at least one minimal prime ideal above it.

### Dimension.

By definition, the _dimension of the ring_ $\mathbb{Q}[X_{n}]$ is $n$. This
definition of dimension of a polynomial ring is a special case of the more
general concept of Krull dimension of a commutative ring. The _dimension_
$\dim I$ of an ideal $I$ of $\mathbb{Q}[X_{n}]$ is the cardinality of the
maximal subset $X\subseteq X_{n}$ with the property
$I\cap\mathbb{Q}[X]=\\{0\\}$.

We say that a (strict) chain $I_{0}\subset I_{1}\subset\cdots\subset I_{h}$ of
prime ideals of $\mathbb{Q}[X_{n}]$ has length $h$. The _codimension_ or
_height_ $\operatorname{codim}{I}$ of a prime ideal $I$ of $\mathbb{Q}[X_{n}]$
is defined as the supremum of the lengths of maximal chains of prime ideals
$\\{0\\}=I_{0}\subset I_{1}\subset\cdots\subset I_{h}$ such that $I_{h}=I$.

In a polynomial ring $\mathbb{Q}[X_{n}]$ all prime ideals have a finite height
and any two maximal chains of prime ideals terminating at $I$ have the same
height. Furthermore, we have $\dim I+\operatorname{codim}{I}=n$.

An important bound on the codimension of a prime ideal
$I\subset\mathbb{Q}[X_{n}]$ is given by:

######  Theorem 5.3 (Krull’s Height Theorem).

Let $J\subset\mathbb{Q}[X_{n}]$ be an ideal generated by $m$ elements, and let
$I$ be a prime ideal over $J$. Then $\operatorname{codim}{I}\leq m$.
Conversely, if $I$ is a prime ideal such that $\operatorname{codim}{I}\leq m$,
then it is a minimal prime of an ideal generated by $m$ elements.

Krull’s Height Theorem holds more generally for all Noetherian rings, see [14,
Chapter 10] or [27, Chapter 7]. An immediate consequence of the Height Theorem
is that prime ideals of codimension 1 are principal.

######  Corollary 5.4.

If $I\subset\mathbb{Q}[X_{n}]$ is a prime ideal of codimension $1$, then $I$
is principal.

######  Proof 5.5.

By Krull’s Height Theorem $I$ is minimal over the ideal $\left\langle
f\right\rangle$ generated by some $f\in I$. If $f$ is not irreducible, then it
has an irreducible factor $p$ that is in $I$. Therefore, we have
$\\{0\\}\subset\left\langle f\right\rangle\subseteq I\text{ and
}\\{0\\}\subset\left\langle f\right\rangle\subseteq\left\langle
p\right\rangle$. By minimality we must have $I=\left\langle p\right\rangle$.

### Algebraic matroid of a prime ideal.

Intuitively, a collection of variables is independent if it is not constrained
by any polynomial in the ideal, and dependent otherwise. Thus the _algebraic
matroid_ $\operatorname{\mathcal{A}}(I)$ induced by the ideal is, informally,
a matroid on the ground set of variables $X_{n}$ whose independent sets are
subsets of variables that are not supported by any polynomial in the ideal.
Its dependent sets are supports of polynomials in the ideal.

Every algebraic matroid of a prime ideal arises as an algebraic matroid of a
field extension in the sense of Definition 5.2, and vice-versa. This
equivalence is well-known and we include it for completeness.

Formally, let $I$ be a prime ideal of the polynomial ring $\mathbb{Q}[X_{n}]$.
We define a matroid on $X_{n}$, depending on the ideal $I$, called _the
algebraic matroid of_ $I$ and denoted $\operatorname{\mathcal{A}}(I)$, in the
following way.

The quotient ring $\mathbb{Q}[X_{n}]/I$ is an integral domain with a well
defined fraction field $K=\operatorname{Frac}{(\mathbb{Q}[X_{n}]/I)}$ which
contains $\mathbb{Q}$ as a subfield. The image of $X_{n}$ under the canonical
injections

$\mathbb{Q}[X_{n}]\hookrightarrow\mathbb{Q}[X_{n}]/I\hookrightarrow\operatorname{Frac}{(\mathbb{Q}[X_{n}]/I)}=K$

is the subset $\\{\overline{x_{1}},\dots,\overline{x_{n}}\\}$ of $K$, where
$\overline{x_{j}}$ denotes the equivalence class of $x_{j}$ in both
$\mathbb{Q}[X_{n}]/I$ and $K$.

Let $X$ be a non-empty subset of $X_{n}$. Consider its image $\overline{X}$ in
$K$ under the canonical injections. For clarity, let
$X=\\{x_{1},\dots,x_{i}\\}$ and
$\overline{X}=\\{\overline{x_{1}},\dots,\overline{x_{i}}\\}$ for some fixed
$i\leq n$. The set $\overline{X}$ is by definition algebraically dependent
over $\mathbb{Q}$ if and only if there exists a non-zero polynomial
$f\in\mathbb{Q}[x_{1},\dots,x_{i}]$ vanishing on $\overline{X}$, i.e.

$f(\overline{x_{1}},\dots,\overline{x_{i}})=\overline{0}.$

Clearly, $\overline{X}$ is algebraically dependent over $\mathbb{Q}$ if and
only if $f(x_{1},\dots,x_{i})\in I$, that is if and only if

$I\cap\mathbb{Q}[X]\neq\\{0\\},$

where $\mathbb{Q}[X]$ denotes the ring of polynomials supported on subsets of
$X$. Similarly, $\overline{X}$ is algebraically independent over $\mathbb{Q}$
if and only if

$I\cap\mathbb{Q}[X]=\\{0\\}.$

######  Definition 5.6.

Let $I$ be a prime ideal in the polynomial ring $\mathbb{Q}[X_{n}]$. The
_algebraic matroid of_ $I$, denoted $\operatorname{\mathcal{A}}(I)$, is the
matroid $(X_{n},\mathcal{I})$ on the ground set
$X_{n}=\\{x_{1},\dots,x_{n}\\}$ with

$\mathcal{I}=\\{X\subseteq X_{n}\mid I\cap\mathbb{Q}[X]=\\{0\\}\\},$

where $\mathbb{Q}[X]$ denotes the ring of polynomials supported on subsets of
$X$.

### Equivalence of the two definitions

The above construction shows that any algebraic matroid with respect to a
prime ideal $I\subset\mathbb{Q}[X_{n}]$ can be realized as an algebraic
matroid over $\mathbb{Q}$ with the ground set
$\\{\overline{x_{1}},\dots,\overline{x_{n}}\\}$ in the field extension
$\operatorname{Frac}{(\mathbb{Q}[X_{n}]/I)}$ of $\mathbb{Q}$. Conversely,
given a set of elements $E=\\{\alpha_{1},\dots,\alpha_{n}\\}$ in a field
extension of $\mathbb{Q}$, we can realize any algebraic matroid $\mathcal{M}$
on $E$ over $\mathbb{Q}$ as an algebraic matroid of a prime ideal of
$\mathbb{Q}[X_{n}]$ in the following way: let $\varphi$ be the homomorphism

$\varphi\colon\mathbb{Q}[X_{n}]\to\mathbb{Q}(\alpha_{1},\dots,\alpha_{n})$

mapping $x_{i}\mapsto\alpha_{i}$ for all $i\in\\{1,\dots,n\\}$ and $a\mapsto
a$ for all $a\in\mathbb{Q}$. Let $A\subset\\{\alpha_{1},\dots,\alpha_{n}\\}$
be a dependent set in $\mathcal{M}$. Then $A$ vanishes on a polynomial in
$\mathbb{Q}[X_{n}]$ so the kernel $\ker\varphi$ is non-zero, and clearly any
polynomial in $\ker\varphi$ defines a dependency in $\mathcal{M}$. Therefore,
if we denote by $\mathbb{Q}[A]$ the ring of polynomials supported on subsets
of $\varphi^{-1}(A)$, we have

$\ker\varphi\cap k[A]\neq{0}$

if and only if $A$ is a dependent set of $\mathcal{M}$.

For the rest of the paper we will work exclusively with algebraic matroids of
prime ideals.

### Circuits and circuit polynomials.

A circuit is a minimal set of variables supported by a polynomial in $I$. A
polynomial whose support is a circuit is called a circuit polynomial. A
theorem of Lovasz and Dress [11] states that a circuit polynomial $p_{C}$ is
unique in the ideal with the given support $C\subset X_{n}$, up to
multiplication by a constant (we’ll just say, shortly, that it is unique).
Furthermore, the circuit polynomial is irreducible.

We retain the following property, stating that circuit polynomials generate
elimination ideals supported on circuits.

######  Theorem 5.7.

Let $I$ be a prime ideal in $\mathbb{Q}[X]$ and $C\subset X$ a circuit of the
algebraic matroid $\operatorname{\mathcal{A}}(I)$. The ideal
$I\cap\mathbb{Q}[C]$ is principal and generated by an irreducible circuit
polynomial $p_{C}$, which is unique up to multiplication by a constant.

######  Proof 5.8.

Since $C$ is a circuit the ideal $I\cap\mathbb{Q}[C]$ has dimension at least
equal to $|C|-1$. It can not have dimension greater than or equal to $|C|$
since $\dim k[C]=|C|$. Therefore $I\cap\mathbb{Q}[C]$ has dimension $|C|-1$
and codimension $1$. By Corollary 5.4, $I\cap\mathbb{Q}[C]$ is principal, and
since $p_{C}\in I\cap\mathbb{Q}[C]$ is irreducible over $\mathbb{Q}$, it also
generates $I\cap\mathbb{Q}[C]$.

##  6 The Cayley-Menger ideal and its algebraic matroid

In this section we introduce the 2D Cayley-Menger ideal
$\operatorname{CM}_{n}$. We then define the corresponding circuit polynomials
and their supports, and make the connection with combinatorial rigidity
circuits.

We will show that the algebraic matroid of $\operatorname{CM}_{n}$ is
isomophic to the $(2,3)$-sparsity matroid $\operatorname{\mathcal{S}}_{n}$.
This equivalence is well-known, however we were not able to track down the
original reference, and include a proof for completeness.

### The Cayley-Menger ideal and its algebraic matroid.

We use variables $X_{n}=\\{x_{i,j}:1\leq i<j\leq n\\}$ for unknown squared
distances between pairs of points. The distance matrix of $n$ labeled points
is the matrix of squared distances between pairs of points. The Cayley matrix
is the distance matrix bordered by a new row and column of 1’s, with zeros on
the diagonal:

$\begin{pmatrix}0&1&1&1&\cdots&1\\\ 1&0&x_{1,2}&x_{1,3}&\cdots&x_{1,n}\\\
1&x_{1,2}&0&x_{2,3}&\cdots&x_{2,n}\\\ 1&x_{1,3}&x_{2,3}&0&\cdots&x_{3,n}\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{1,n}&x_{2,n}&x_{3,n}&\cdots&0\end{pmatrix}$

Cayley’s Theorem says that, if the distances come from a point set in the
Euclidean space $\mathbb{R}^{d}$, then the rank of this matrix must be at most
$d+2$. Thus all the $(d+3)\times(d+3)$ minors of the Cayley-Menger matrix
should be zero. These minors induce polynomials in $\mathbb{Q}[X_{n}]$ which
generate the $(n,d)$-Cayley-Menger ideal. They are called the _standard
generators_ , are homogeneous polynomials with integer coefficients and are
irreducible over $\mathbb{Q}$. The $(n,d)$-Cayley-Menger ideal is a prime
ideal of dimension $dn-{\binom{d+1}{2}}$ [5, 20, 23, 28] and codimension
$\binom{n}{2}-dn+{\binom{d+1}{2}}$. We work with the 2D Cayley-Menger ideal
$\operatorname{CM}_{n}$, generated by the $5\times 5$ minors of the Cayley
matrix. The algebraic matroid of the 2D Cayley-Menger ideal
$\operatorname{CM}_{n}$ is denoted by
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$.

### The algebraic matroid of $\operatorname{CM}_{n}^{d}$.

As defined in Section 5, the algebraic matroid
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n}^{d})$ is the matroid on the
ground set $X_{n}=\\{x_{i,j}\mid 1\leq i<j\leq n\\}$ where $X\subseteq X_{n}$
is independent if

$\operatorname{CM}_{n}^{d}\cap\leavevmode\nobreak\ \mathbb{Q}[X]=\\{0\\},$

where, as before, $\mathbb{Q}[X]$ denotes the ring of polynomials over
$\mathbb{Q}$ supported on the indeterminates in $X$.

######  Proposition 6.1.

The rank of $\operatorname{\mathcal{A}}(\operatorname{CM}_{n}^{d})$ is equal
to $\dim{\operatorname{CM}_{n}^{d}}=dn-{\binom{d+1}{2}}$.

######  Proof 6.2.

Immediate from the definition of dimension of an ideal in a ring of
polynomials (Section 5).

When $d=2$ the rank of $\operatorname{CM}_{n}^{2}$ is precisely the rank of
the $(2,3)$-sparsity matroid $\operatorname{\mathcal{S}}_{n}$ on $n$ vertices.
In fact, the two matroids are isomorphic. For the rest of the paper we fix
$d=2$ and abbreviate $\operatorname{CM}_{n}^{2}$ with just
$\operatorname{CM}_{n}$.

######  Theorem 6.3.

The algebraic matroid $\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$ and
the $(2,3)$-sparsity matroid $\operatorname{\mathcal{S}}_{n}$ are isomorphic.

We will prove the equivalence of
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$ and
$\operatorname{\mathcal{S}}_{n}$ by proving that both are equivalent to the
$2$-dimensional generic linear rigidity matroid that we now introduce.

Let $G=(V,E)$ be a graph and $(G,p)$ a $2D$ bar-and-joint framework with
points $\\{p_{1},\dots,p_{n}\\}\subset\mathbb{R}^{2}$.

######  Definition 6.4.

The rigidity matrix $R_{(G,p)}$ (or just $R_{G}$ when there is no possibility
of confusion) of the bar-and-joint framework $(G,p)$ is the $|E|\times n$
matrix with columns indexed by the vertices $\\{1,2,\dots,n\\}$ and rows
indexed by the edges $ij\in E$ with $i<j$. The $i$-th entry in the row $ij$ is
$p_{i}-p_{j}$, the $j$-th entry is $p_{j}-p_{i}$, and all other entries are
$0$.

The rigidity matrix is defined up to an order of the vertices and the edges;
to eliminate this ambiguity we fix the order on the vertices as $1<2<\cdots<n$
and we order the edges $ij$ with $i<j$ lexicographically.

For example, let $G=K_{4}$. Then the rows are ordered as $12$, $13$, $14$,
$23$, $24$ and $34$ and the corresponding rigidity matrix $R_{K_{4}}$ is given
by

$R_{K_{4}}=\begin{pmatrix}p_{1}-p_{2}&p_{2}-p_{1}&0&0\\\
p_{1}-p_{3}&0&p_{3}-p_{1}&0\\\ p_{1}-p_{4}&0&0&p_{4}-p_{1}\\\
0&p_{2}-p_{3}&p_{3}-p_{2}&0\\\ 0&p_{2}-p_{4}&0&p_{4}-p_{2}\\\
0&0&p_{3}-p_{4}&p_{4}-p_{3}\\\ \end{pmatrix}.$

######  Definition 6.5.

Let $G=(V,E)$ be a graph and $(G,p)$ a $2D$ bar-and-joint framework. The
_2-dimensional linear rigidity matroid_ $\operatorname{\mathcal{L}}_{(G,p)}$
is the matroid $(E,\mathcal{I})$ where $I\in\mathcal{I}$ if and only if the
rows of $R_{(G,p)}$ indexed by $I$ are linearly independent.

Note that the matroid $\operatorname{\mathcal{L}}_{(G,p)}$ depends on the
plane configuration $p$. For example, if $G=K_{4}$, $p$ a configuration in
which at most two vertices of $K_{4}$ are on a line, and $q$ a configuration
in which the vertices $\\{2,3,4\\}$ are on the same line, then
$\operatorname{rank}\operatorname{\mathcal{L}}_{K_{4},p}>\operatorname{rank}\operatorname{\mathcal{L}}_{K_{4},q}$.

Let $G$ be a graph and consider the set $\mathcal{X}_{G}$ of all possible
plane configurations $p$ for $G$.

######  Definition 6.6.

We say that a 2D bar-and-joint framework $(G,p)$ is _generic_ if the rank of
the row space of $R_{(G,p)}$ is maximal among all plane configurations in
$\mathcal{X}_{G}$.

If $p$ and $p^{\prime}$ are distinct generic plane configurations for a graph
$G$, the 2D linear matroids $\operatorname{\mathcal{L}}_{(G,p)}$ and
$\operatorname{\mathcal{L}}_{(G,p^{\prime})}$ are isomorphic [21, Theorem
2.2.1], hence the following matroid is well-defined.

######  Definition 6.7.

Let $G$ be a graph. The _2-dimensional generic linear matroid_
$\operatorname{\mathcal{L}}_{G}$ is the 2D linear matroid
$\operatorname{\mathcal{L}}_{(G,p)}$ where $p$ is any generic plane
configuration for $G$.

That for a given graph $G$ on $n$ vertices the generic linear matroid
$\operatorname{\mathcal{L}}_{(G,p)}$ and the sparsity matroid
$\operatorname{\mathcal{S}}_{n}$ are isomorphic follows from Laman’s theorem
(Theorem 2.1).

We now have to show that $\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$
is equivalent to the generic linear rigidity matroid
$\operatorname{\mathcal{L}}_{K_{n}}$. This equivalence will be the consequence
of a classical result of Ingleton [26, Section 6] (see also [13, Section 2])
stating that algebraic matroids over a field $k$ of characteristic zero are
linearly representable over an extension of $k$, with the linear
representation given by the Jacobian. We now note that the Cayley-Menger
variety is realized as the Zariski closure of the image of the map
$f=(f_{ij})_{\\{i,j\\}\in{\binom{n}{2}}}\colon(\mathbb{C}^{2})^{n}\to\mathbb{C}^{\binom{n}{2}}$
given by

$(p_{1},\dots,p_{n})\mapsto(||p_{i}-p_{j}||^{2})_{\\{i,j\\}\in{\binom{n}{2}}}.$

The Jacobian of the edge function
$(p_{1},\dots,p_{n})\mapsto(||p_{i}-p_{j}||^{2})_{\\{i,j\\}\in{\binom{n}{2}}}$
at a generic point in $(\mathbb{C}^{2})^{n}$ is precisely the matrix
$2R_{(K_{n},p)}$ for a generic configuration $p$.

This completes the proof of Theorem 6.3. From now on, we will use the
isomorphism to move freely between the formulation of algebraic circuits as
subsets of variables $X\subset X_{n}$ and their graph-theoretic interpretation
as graphs that are rigidity circuits. Given a (rigidity) circuit $C$, we
denote by $p_{C}$ the corresponding circuit polynomial in the Cayley-Menger
ideal $\operatorname{CM}_{n}$.

### Comments: beyond dimension 2?

Note that the $d$-dimensional linear rigidity matroid
$\operatorname{\mathcal{L}}_{n}$ and the algebraic matroid
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n}^{d})$ of the $(n,d)$-Cayley-
Menger matroid are isomorphic by the same Jacobian argument as above. However,
the equivalence between the 2D sparsity matroid
$\operatorname{\mathcal{S}}_{n}$ and
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$ does not extend to higher
dimension to some known graphical matroid. The generalization
$dn-\binom{d+1}{2}$ of the $(2n-3)$-sparsity condition from dimension $2$ to
dimension $d$, called Maxwell’s sparsity [35], does not satisfy matroid
axioms. In fact, Maxwell’s sparsity is known to be only a necessary but not
sufficient condition for minimal rigidity in dimensions $d\geq 3$.

### Circuits of $\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$ and
circuit polynomials in $\operatorname{CM}_{n}$.

The isomorphism between the algebraic matroid
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$ and the sparsity matroid
$\operatorname{\mathcal{S}}_{n}$ immediately implies that the sets of circuits
of these two matroids are in a one-to-one correspondence. We will identify a
sparsity circuit $C=(V_{C},E_{C})\in\operatorname{\mathcal{S}}_{n}$, with the
circuit

$\\{x_{i,j}\mid ij\in
E_{C}\\}\in\operatorname{\mathcal{A}}(\operatorname{CM}_{n}),$

and in the same way the dependent sets of $\operatorname{\mathcal{S}}_{n}$
will be identified with the dependent sets of
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$. Conversely, we will
identify the support of a polynomial $f\in\mathbb{Q}[\\{x_{i,j}\mid 1\leq
i<j\leq n\\}]$ with the graph $S_{f}=(V_{f},E_{f})$ where

$V_{f}=\\{i\mid x_{i,j}\text{ or }x_{h,i}\in\operatorname{supp}{f}\\}\text{
and }E_{f}=\\{ij\mid x_{i,j}\in\operatorname{supp}{f}\\}.$

Recall that the circuit polynomial of a circuit $C$ in $\operatorname{CM}_{n}$
is the (up to multiplication with a unit) unique polynomial $p_{C}$
irreducible over $\mathbb{Q}$ such that $\operatorname{supp}{p_{C}}=C$. Hence
we will identify from now on a circuit $C$ with the support
$\operatorname{supp}{p}_{C}$ of its circuit polynomial $p_{C}$. Furthermore,
$p_{C}$ generates the elimination ideal
$\operatorname{CM}_{n}\cap\mathbb{Q}[C]$.

######  Proposition 6.8.

Circuit polynomials in $\operatorname{CM}_{n}$ are homogeneous polynomials.

######  Proof 6.9.

Since $\operatorname{CM}_{n}$ is generated by homogeneous polynomials, any
reduced Gröbner basis of $\operatorname{CM}_{n}$ consists only of homogeneous
polynomials (see e.g. Theorem 2 in §3 of Chapter 8 of [9]). Now if $C$ is a
circuit in $\operatorname{CM}_{n}$, we can choose an elimination order in
which all the indeterminates in the complement of $C$ are greater than those
in $C$. The Gröbner basis $\mathcal{G}_{C}$ with respect to that elimination
order will necessarily contain $p_{C}$ because
$\mathcal{G}_{C}\cap\mathbb{Q}[C]$ must generate the elimination ideal
$\operatorname{CM}_{n}\cap\mathbb{Q}[C]$.

By Theorem 6.3 any circuit polynomial in $\operatorname{CM}_{n}$ is supported
on a sparsity circuit. Therefore, the simplest examples of circuit polynomials
in $\operatorname{CM}_{n}$ are the standard generators that are supported on
the $\binom{n}{4}$ complete graphs on 4 vertices in $[n]$.

Example: the $K_{4}$ circuit. Among the generators of $\operatorname{CM}_{n}$
we find the smallest circuit polynomials. Their supports are in correspondence
with the edges of complete graphs $K_{4}$ on all subsets of $4$ vertices in
$[n]$. The $K_{4}$ circuit polynomial (given below on vertices $1234$) is
homogeneous of degree 3, has 22 terms and has degree 2 in any of its
variables.

$\displaystyle p_{K_{4}^{1234}}$
$\displaystyle=x_{3,4}x_{1,2}^{2}+x_{3,4}^{2}x_{1,2}+x_{1,3}x_{2,3}x_{1,2}-x_{1,4}x_{2,3}x_{1,2}-x_{1,3}x_{2,4}x_{1,2}$
$\displaystyle+x_{1,4}^{2}x_{2,3}+x_{1,3}x_{2,4}^{2}+x_{1,4}x_{2,4}x_{1,2}-x_{1,3}x_{3,4}x_{1,2}-x_{1,4}x_{3,4}x_{1,2}$
$\displaystyle+x_{1,3}^{2}x_{2,4}+x_{1,4}x_{2,3}^{2}-x_{2,3}x_{3,4}x_{1,2}-x_{2,4}x_{3,4}x_{1,2}+x_{2,3}x_{2,4}x_{3,4}$
$\displaystyle-
x_{1,3}x_{2,4}x_{3,4}-x_{1,3}x_{1,4}x_{2,3}-x_{1,3}x_{1,4}x_{2,4}-x_{1,3}x_{2,3}x_{2,4}$
$\displaystyle-
x_{1,4}x_{2,3}x_{2,4}+x_{1,3}x_{1,4}x_{3,4}-x_{1,4}x_{2,3}x_{3,4}$

### Cayley-Menger variety.

The $(n,d)$-Cayley-Menger variety can also be obtained from the ideal
generated by the $(d+1)\times(d+1)$ minors of the symmetric $(n-1)\times(n-1)$
_Gram matrix_ $[\text{Gram}_{i,j}]$ on $n$ points defined as follows: we first
pick one of the points $\\{p_{1},\dots,p_{n}\\}$ as a reference point, say
$p_{n}$ and set

$\text{Gram}_{i,j}=\frac{1}{2}(x_{i,n}+x_{j,n}-x_{i,j})\text{ for
}i,j\in\\{1,\dots,n-1\\}$

with $x_{i,i}=0$ so that $\text{Gram}_{i,i}=x_{i,n}$.

For our purposes, it is preferable to work with the Cayley-Menger matrix and
the standard generators as there will be no need for a reference point.

### Resultants in the Cayley-Menger ideal.

Let $f,g$ be two polynomials in the Cayley-Menger ideal with $x_{ij}$ one of
their common variables. We treat them as polynomials in $x_{ij}$, therefore
the coefficients are themselves polynomials in the remaining variables. Our
main observation, which motivated the definition of the combinatorial
resultant, is that the entries in the Sylvester matrix are polynomials
supported exactly on the variables corresponding to the combinatorial
resultant of the supports of $f$ and $g$ on elimination variable (edge) $ij$.

The following lemma, whose proof follows immediately from Proposition 4.9,
will be used frequently in the rest of the paper.

######  Lemma 6.10.

Let $I$ be an ideal in $\mathbb{Q}[X_{n}]$, $f,g\in I$ with supports
$S_{f}=\operatorname{supp}{f}$ and $S_{g}=\operatorname{supp}{g}$, and let
$x_{ij}$ be a common variable in $S_{f}\cap S_{g}$. Let $S$ be the
combinatorial resultant of the supports
$S=\operatorname{CRes}(S_{f},S_{g},ij)\subset X_{n}$ (i.e. viewed as a set of
variables). Then $\operatorname{Res}(f,g,x_{ij})\in I\cap\mathbb{Q}[S]$.

### Homogeneous properties.

The standard generators of the Cayley-Menger ideal, in particular those that
correspond to $K_{4}$ graphs, are obviously homogeneous. We apply Proposition
4.5 to infer that their resultants are themselves homogeneous polynomials and
to compute their homogeneous degrees.

##  7 Resultants of circuit polynomials

We are now ready to prove our main result, Theorem 1.2, by showing that
combinatorial resultants are the combinatorial analogue of classical
polynomial resultants in the following sense: if a (rigidity) circuit $C$ is
obtained as the combinatorial resultant $\operatorname{CRes}(A,B,e)$ of two
circuits $A$ and $B$ with the edge $e$ eliminated, then the resultant
$\operatorname{Res}(p_{A},p_{B},x_{e})$ of circuit polynomials $p_{A}$ and
$p_{B}$ with respect to the indeterminate $x_{e}$ is supported on $C$ and
contained in the elimination ideal $\left\langle p_{C}\right\rangle$ generated
by the circuit polynomial $p_{C}$. When
$\operatorname{Res}(p_{A},p_{B},x_{e})$ is irreducible then it will be equal
to $p_{C}$. However in general $p_{C}$ will only be one of its irreducible
factors over $\mathbb{Q}$. In fact exactly one factor (counted with
multiplicity) of $\operatorname{Res}(p_{A},p_{B},x_{e})$ can correspond to
$p_{C}$ and that factor can be deduced by examining the supports of the
factors and performing an ideal membership test on those factors that have the
support of $p_{C}$. Our approach is algorithmic, but its precise complexity
analysis depends on answers to a few remaining open questions:

######  Problem 7.1.

Identify sufficient conditions under which
$\operatorname{Res}(p_{A},p_{B},x_{e})$ is $p_{C}$.

######  Problem 7.2.

Identify sufficient conditions for which
$\operatorname{Res}(p_{A},p_{B},x_{e})$ has exactly one factor (up to
multiplicity) supported on $C$.

### Resultants of circuit polynomials.

In this section we refer to a (combinatorial) circuit as a sparsity circuit,
to avoid confusion with the usage of the same concept (circuit) in the circuit
polynomial.

######  Lemma 7.3.

Let $A$ and $B$ be distinct sparsity circuits. The resultant
$\operatorname{Res}(p_{A},p_{B},x_{e})$ of the circuit polynomials $p_{A}$ and
$p_{B}$ with respect to a variable
$x_{e}\in\operatorname{supp}{p_{A}}\cup\leavevmode\nobreak\
\operatorname{supp}{p_{B}}$ is a non-constant polynomial in
$\mathbb{Q}[(\operatorname{supp}{p_{A}}\cup\leavevmode\nobreak\
\operatorname{supp}{p_{B}})\setminus\\{x_{e}\\}]$.

######  Proof 7.4.

Circuit polynomials are irreducible over $\mathbb{Q}$, hence the resultant of
two distinct circuit polynomials is non-zero (by Proposition 4.2 in the
Appendix).

Let $A$ and $B$ be distinct sparsity circuits and let $p_{A}$ and $p_{B}$ be
the corresponding circuit polynomials. Assuming $e\in A\cap B$, the
polynomials $p_{A}$ and $p_{B}$ belong to the ring $R[x_{e}]$, where
$R=\mathbb{Q}[(\operatorname{supp}{p_{A}}\cup\operatorname{supp}{p_{B}})\setminus\\{x_{e}\\}].$

######  Theorem 7.5.

Let $C$ be a sparsity circuit on $n+1$ vertices and $p_{C}$ its corresponding
circuit polynomial. There exist sparsity circuits $A$ and $B$ on at most $n$
vertices with circuit polynomials $p_{A}$ and $p_{B}$ such that $p_{C}$ is an
irreducible factor over $\mathbb{Q}$ of
$\operatorname{Res}(p_{A},p_{B},x_{e})$, where $e\in A\cap B$.

######  Proof 7.6.

Given a sparsity circuit $C$ on $n+1$ vertices we can find two sparsity
circuits $A$ and $B$ on at most $n$ vertices such that
$C=\operatorname{CRes}(A,B,e)$ for some $e\in A\cap B$ by the proof of Theorem
1.1 in Section 3. Let $p_{A}$ and $p_{B}$ be the corresponding circuit
polynomials.

The polynomials $p_{A}$ and $p_{B}$ are contained in $\operatorname{CM}_{m}$
for some $m\geq n+1$ and the resultant $\operatorname{Res}(p_{A},p_{B},x_{e})$
is a non-constant polynomial in
$R=\mathbb{Q}[(\operatorname{supp}{p_{A}}\cup\operatorname{supp}{p_{B}})\setminus\\{x_{e}\\}]$
supported on $\operatorname{supp}{p_{C}}$. Since $\left\langle
p_{A},{p_{B}}\right\rangle\subset\operatorname{CM}_{m}$, we have that
$\operatorname{Res}(p_{A},p_{B},x_{e})$ is contained in the elimination ideal
$\operatorname{CM}_{m}\cap\mathbb{Q}[\operatorname{supp}{p_{C}}]=\left\langle
p_{C}\right\rangle$ (by Lemma 6.10).

######  Corollary 7.7.

Under the assumptions of Theorem 7.5, the resultant
$\operatorname{Res}(p_{A},p_{B},x_{e})$ is a circuit polynomial if and only if
it is irreducible (over $\mathbb{Q}$).

Indeed, it is not always the case that the resultant of two circuit
polynomials, such that its support corresponds to a sparsity circuit is
irreducible. Recall from Corollary 3.9 that in general a sparsity circuit $C$
can be represented as the combinatorial resultant of two circuits in more than
one way. If
$C=\operatorname{CRes}(C_{1},C_{2},e)=\operatorname{CRes}(C_{3},C_{4},f)$ and
$p_{C_{i}}$ for $i\in\\{1,\dots,4\\}$ are the corresponding circuit
polynomials, then $\operatorname{Res}(p_{C_{1}},p_{C_{2}},x_{e})$ and
$\operatorname{Res}(p_{C_{3}},p_{C_{4}},x_{f})$ will in general be distinct
elements of $\left\langle p_{C}\right\rangle$. Moreover, the resultant with
the higher homogeneous degree must necessarily have a non-trivial factor.

######  Example 7.8.

Let $C$ be the 2-connected circuit $\\{12,13,23,24,34,15,16,56,45,46\\}$ as
shown in Figure 9. This circuit can be obtained as the combinatorial resultant
of the circuits $C_{1}$ and $C_{2}$ given by the $K_{4}$ graph on $1234$ and
$1456$, respectively, with the edge $14$ eliminated (Figure 9, left). It can
also be obtained as the combinatorial resultant of the circuits $C_{3}$ and
$C_{4}$ given by the wheels on $1245$ with $3$ in the center and $1346$ with
$5$ in the center, with the edge $35$ eliminated (Figure 9, right). However,
$\operatorname{Res}(p_{C_{1}},p_{C_{2}},x_{1,4})$ is the resultant of two
quadratic polynomials of homogeneous degree 3, whereas
$\operatorname{Res}(p_{C_{3}},p_{C_{4}},x_{3,5})$ is the resultant of two
quartic polynomials of homogeneous degree 8. Therefore, by Proposition 4.5,
$\operatorname{Res}(p_{C_{1}},p_{C_{2}},x_{1,4})$ is homogeneous of degree 8,
whereas $\operatorname{Res}(p_{C_{3}},p_{C_{4}},x_{3,5})$ is of homogeneous
degree 48. Both resultants have the same circuit as its supporting set, hence
they are both in the elimination ideal $\left\langle p_{C}\right\rangle$ of
$\operatorname{CM}_{6}$ which is generated by
$\operatorname{Res}(p_{C_{1}},p_{C_{2}},x_{1,4})$. Therefore
$\operatorname{Res}(p_{C_{1}},p_{C_{2}},x_{1,4})=\alpha\cdot p_{C}$ and
$\operatorname{Res}(p_{C_{3}},p_{C_{4}},x_{3,5})=q\cdot p_{C}$ where
$\alpha\in\mathbb{Q}$ and $q$ is a non-constant polynomial in $\mathbb{Q}[C]$.

We can generalize Example 7.8 in the following way. Let $C$ be a sparsity
circuit on $n\geq 5$ vertices. Consider the set $\Gamma_{C}$ of all possible
representations of $C$ as a combinatorial resultant of two sparsity circuits
$A$ and $B$ on at most $n$ vertices

$\Gamma_{C}=\\{(A,B,e)\mid
C=\operatorname{CRes}(A,B,e),|V(A)|,|V(B)|\leq|V(C)|\\}$

and the set

$\rho_{C}=\\{\operatorname{Res}(p_{A},p_{B},x_{e})\mid(A,B,e)\in\Gamma_{C}\\}$

of all resultants of corresponding circuit polynomials. The circuit polynomial
$p_{C}$ of the circuit $C$ of Example 7.8 had the property of being the
polynomial in $\rho_{C}$ of minimal homogeneous degree. One might therefore
conjecture that for any sparsity circuit $C$, the polynomial in $\rho_{C}$ of
minimal homogeneous degree is the circuit polynomial for $C$; in that case no
irreducibility check would be required as we can compute the homogeneous
degree of $\operatorname{Res}(p_{A},p_{B},x_{e})$ from the homogeneous degrees
and the degrees in $x_{e}$ of $p_{A}$ and $p_{B}$ (Proposition 4.5). However,
we will show in Proposition 8.1 that in general the circuit polynomial of a
circuit $C$ is not necessarily in $\rho_{C}$. This fact leads to the following
natural question.

######  Problem 7.9.

Let $C$, $A$ and $B$ be sparsity circuits such that
$C=\operatorname{CRes}(A,B,e)$ with $p_{C}$, $p_{A}$ and $p_{B}$ the
corresponding circuit polynomials. Under which conditions on $A$, $B$, $p_{A}$
and $p_{B}$ is $\operatorname{Res}(p_{A},p_{B},x_{e})=\alpha\cdot p_{C}$ for
some $\alpha\in\mathbb{Q}$?

### Algorithms: determining the circuit polynomial from the resultant.

If $\operatorname{Res}(p_{A},p_{B},x_{e})$ is not irreducible, then (up to
multiplicity) exactly one of its irreducible factors (over $\mathbb{Q}$) is in
$\operatorname{CM}_{n}$, and that factor is precisely the circuit polynomial
$p_{C}$. This factor can be deduced in two steps: an analysis of the supports
of the factors and an ideal membership test.

Step 1: analysing the supports of the irreducible factors. If
$C=\operatorname{CRes}(A,B,e)$ then we know that $C$ and
$\operatorname{supp}{p}_{C}$ are identified. Recall that the elimination ideal
$\left\langle p_{C}\right\rangle$ is an ideal of $\mathbb{\mathbb{Q}}[C]$, and
since $\operatorname{Res}(p_{A},p_{B},x_{e})\in\left\langle
p_{C}\right\rangle$, any irreducible factor (over $\mathbb{Q}$) of this
resultant is supported on a subset of $\operatorname{supp}{p}_{C}$ that is not
necessarily proper. At least one these factors must be supported on exactly
$\operatorname{supp}{p}_{C}$, and if there is only one such factor, then that
factor must be $p_{C}$. Otherwise, we proceed to Step 2.

Step 2: ideal membership test. Take into consideration only those irreducible
factors of $\operatorname{Res}(p_{A},p_{B},x_{e})$ that are supported on
$\operatorname{supp}{p_{C}}$. Test each factor for membership in
$\operatorname{CM}_{n}$ via a Gröbner basis algorithm with respect to some
monomial order, not necessarily an elimination order. The first factor
determined to be in $\operatorname{CM}_{n}$ is $p_{C}$.

Algorithm 2 Circuit polynomial: resultant step

Input: Circuits $A$, $B$ and edge $e$ such that
$C=\operatorname{CRes}(A,B,e)$. Circuit polynomials $p_{A}$ and $p_{B}$ and
elimination variable $x_{e}$.
Output: Circuit polynomial $p_{C}$ for $C$.

1:Compute the resultant $p$ = Res($p_{A}$,$p_{B}$,$x_{e}$).

2:if $p$ is irreducible then

3: $p_{C}=p$ return $p_{C}$

4:else

5: factors = factorize $p$ over $\mathbb{Q}$

6: factors = discard factors with support not equal to $C$

7: if exactly one remaining factor (possibly with multiplicity) then

8: $p_{C}$ = the unique factor supported on $C$

9: else

10: apply a test of membership in the $CM$ ideal on the remaining factors

11: $p_{C}$ = unique factor for which ideal membership test succeeded

12: return $p_{C}$

13: end if

14:end if

Every circuit polynomial can inductively be computed from the circuit
polynomials supported on complete graphs on $4$ vertices by repeatedly
calculating resultants and applying steps 1 and 2. Hence we can preform all
the computations in a prime ideal that is minimal over an ideal generated only
by circuit polynomials of complete graphs on 4 vertices. In order to define
this ideal we first define the following tree.

Let $C$ be a sparsity circuit on $n$ vertices and $T_{C}$ a resultant tree for
$C$. Denote by $\operatorname{supp}{T}_{C}$ the union of the supports of all
leaves in $T_{C}$:

$\operatorname{supp}{T}_{C}=\\{x_{i,j}\mid\\{i,j\\}\text{ is an edge of a leaf
in }T_{C}\\}.$

Consider in $S_{T_{C}}=\mathbb{C}[\operatorname{supp}{T}_{C}]$ the ideal

$K_{T_{C}}=\langle\\{p_{K}\text{ is a circuit polynomial
in}\operatorname{CM}_{n}\mid K\text{ is a leaf of }T_{C}\\}\rangle$

generated by all circuit polynomials supported on the complete graphs on $4$
vertices that appear in $T_{C}$. This ideal need not be prime (see Proposition
8.1), however it always has at least one minimal prime ideal $P_{T_{C}}$ above
it.

######  Theorem 7.10.

Let $C$ be a sparsity circuit on $n$ vertices, $T_{C}$ a resultant tree for
$C$ and $p_{C}\in\operatorname{CM}_{n}$ its circuit polynomial. If $P_{T_{C}}$
is a minimal prime ideal over $K_{T_{C}}$, then $p_{C}\in P_{T_{C}}$.

######  Proof 7.11.

By assumption the circuit polynomials of the leaves of $T_{C}$ are in
$P_{T_{C}}$. By computing the resultants along the tree $T_{C}$, at each node
$C_{i}$ we obtain a polynomial $r_{i}\in P_{T_{C}}$ that has the circuit
polynomial $p_{C_{i}}$ of $C_{i}$ as a factor. Since $P_{T_{C}}$ is a prime
ideal and
$P_{T_{C}}\cap\mathbb{Q}[C_{i}]\subseteq\operatorname{CM}_{n}\cap\mathbb{Q}[C_{i}]=\left\langle
p_{C_{i}}\right\rangle$ it follows that the only irreducible factor of $r_{i}$
that can be in $P_{T_{C}}$ is $p_{C_{i}}$. Therefore $p_{C}\in P_{T_{C}}$.

Note that we can either perform a factorization and a membership test in the
ideal $P_{T_{C}}$ at each node, or we can can preform these two operations
only once at the root of $T_{C}$ because of the multiplicativity of resultants
(Proposition 4.1 (ii)). In both cases we have to compute a minimal prime ideal
over $K_{T_{C}}$ which requires a Gröbner basis computation (see [10] for a
survey of methods for computing prime ideals minimal over a given ideal),
although both options have their advantages and drawbacks:

  * •

by factorizing the resultant $r_{i}$ and applying an ideal membership test to
its factors at each node $C_{i}$, we can discard unnecessary factors and carry
to the parent level only the circuit polynomial $p_{C_{i}}$, reducing the
complexity of the subsequent computation of the resultant in the parent node
of $C_{i}$. The drawback is that we have to preform a factorization at every
non-leaf node, and a membership tests at every node at which the resultant has
distinct factors.

  * •

By choosing to forgo factorization and an ideal membership test at each node
except the root, we have to perform only one factorization and only one ideal
membership test at the root of $T_{C}$ for the resultant
$\operatorname{Res}(A,B,x_{e})$ with respect to some common indeterminate
$x_{e}$, where $A$ and $B$ themselves are resultants of resultants obtained in
the previous levels. However, the drawback is that not just the factorization,
but even the computation of $\operatorname{Res}(A,B,x_{e})$ itself becomes
very difficult.

### Comments on complexity.

The main bottleneck in our approach for computing circuit polynomials is that
we still have to compute a Gröbner basis with respect to some monomial order
in order to apply an ideal membership test. It is difficult to know a priori
which monomial order will be the most efficient. However in practice
elimination orders, necessary for the general method for computing elimination
ideals, behave badly (see [2, Section 4] and the Section _Complexity Issues_
in [9, §10 of Chapter 2]) while graded orders show better performance but
cannot be used to compute elimination ideals.

Our approach however avoids the use of an elimination order, requires only one
elimination step that is obtained with resultants, and is followed by a
factorization with a potential ideal membership test that can be preformed
with respect to _any_ monomial order. Hence we are free to choose a monomial
order for $\operatorname{CM}_{n}$ that we expect to have better performance
than an elimination order.

A measure of complexity of a Gröbner basis computation is given by bounds on
the total degrees222The total degree of a polynomial is the maximum of the
homogeneous degrees of its monomials of polynomials in the basis, with an
exponential lower bound and a doubly exponential upper bound in the number of
indeterminates of the underlying ring (see the recent survey [37]). In
particular, Dubé [12] gives the following bound.

######  Theorem 7.12.

([12]) Let $I=\left\langle f_{1},\dots,f_{s}\right\rangle$ be an ideal of
$R[x_{1},\dots,x_{n}]$, where $R$ is a ring and $s,n\geq 1$. If $d$ is the
maximum of the total degrees of polynomials in $\\{f_{1},\dots,f_{s}\\}$, then
every reduced Gröbner basis $B$ of $I$ with respect to an monomial order
consists of polynomials $g\in B$ satisfying

$\deg(g)\leq 2\left(\frac{d^{2}}{2}+d\right)^{2^{n-1}}.$

With respect to $\operatorname{CM}_{n}$ for $n\geq 5$ the standard generators
are of homogeneous degree 3, 4 and 5, therefore this bound is
$2(25/2+5)^{2^{\binom{n}{2}-1}}$.

For large $n$ there will be circuits $C$ on $n$ vertices that have a resultant
tree $T_{C}$ such that $|\operatorname{supp}{T}_{C}|$ is relatively small
compared to $\binom{n}{2}$. In that case it can be more feasible to preform
Gröbner basis computations in the lower-dimensional ring
$\mathbb{Q}[\operatorname{supp}{T}_{C}]$ than to compute a Gröbner basis for
$\operatorname{CM}_{n}$ in the ring on $\binom{n}{2}$ indeterminates; first we
have to compute a Gröbner basis for $K_{T_{C}}$ which has Dubé’s bound reduced
to $2(9/2+3)^{2^{|\operatorname{supp}{T}_{C}|-1}}$, and use that basis to
compute a Gröbner basis for $P_{T_{C}}$.

Mayr and Ritscher [36] have shown that the total degrees of the polynomials in
the Gröbner basis $B$ are bounded doubly-exponentially in the dimension of
$I$.

######  Theorem 7.13.

([36]) Let $I=\left\langle f_{1},\dots,f_{s}\right\rangle$ be an ideal of
$k[x_{1},\dots,x_{n}]$, where $k$ is an infinite field and $s,n\geq 1$. If $d$
is the maximum of the total degrees of polynomials in
$\\{f_{1},\dots,f_{s}\\}$, then every reduced Gröbner basis $B$ of $I$ with
respect to an monomial order consists of polynomials $g\in B$ satisfying

$\deg(g)\leq
2\left(\frac{1}{2}\left(d^{2(\operatorname{codim}{I})^{2}}+d\right)\right)^{2^{\dim
I}}.$

Thus a strategy of computing a circuit polynomial of a circuit $C$ on $n$
vertices is to find the ideal $P_{T_{C}}$ of least possible dimension (which
cannot be smaller than $2n-3$). If the dimension of $P_{T_{C}}$ is the best
possible, i.e. equal to $2n-3$, then its codimension is also smaller than the
codimension of $\operatorname{CM}_{n}$ because the underlying ring of
$P_{T_{C}}$ has less than $\binom{n}{2}$ indeterminates. Therefore, when $\dim
P_{T_{C}}=2n-3$ the Mayr-Ritscher bound for $P_{T_{C}}$ will be smaller than
the bound for $\operatorname{CM}_{n}$ even though we also have
$\dim{\operatorname{CM}_{n}}=2n-3$. However, determining the dimension of an
ideal in general requires polynomial space [4].

##  8 Experiments

### Computation of circuit polynomials via Gröbner bases.

In principle a circuit polynomial $p\in\operatorname{CM}_{n}$ can be computed
by computing a Gröbner basis $\mathcal{G}_{\operatorname{CM}_{n}}$ for
$\operatorname{CM}_{n}$ with respect to an _elimination order_ 333See
Excercises 5 and 6 in §1 of Chapter 3 in [9] on the set $\\{x_{i,j}\mid 1\leq
i<j\leq n\\}$ in which all the indeterminates in $\operatorname{supp}{p}$ are
greater than all the indeterminates in its complement.

Given $\mathcal{G}_{\operatorname{CM}_{n}}$ it is straightforward to determine
a Gröbner basis $\mathcal{G}_{\left\langle p\right\rangle}$ for the ideal
$\left\langle
p\right\rangle=\operatorname{CM}_{n}\cap\mathbb{C}[\operatorname{supp}{p}]$:
it is the intersection

$\mathcal{G}_{\left\langle
p\right\rangle}=\mathcal{G}_{\operatorname{CM}_{n}}\cap\mathbb{C}[\operatorname{supp}{p}].$

Therefore, the only element in $\mathcal{G}_{\operatorname{CM}_{n}}$ supported
on $\operatorname{supp}{p}$ is precisely $p$, possibly multiplied by a non-
zero scalar.

The complexity and performance of algorithms for computing Gröbner bases
depends heavily on the choice of a monomial order. The method described above
holds only for elimination orders which in practice often quickly become
infeasible. In general, the main problems of Elimination Theory, such as the
Ideal Triviality Problem, the Ideal Membership Problem for Complete
Intersections, the Radical Membership Problem, the General Elimination
Problem, and the Noether Normalization are in the PSPACE compelxity class
[34].

In the particular case of Cayley-Menger ideals $\operatorname{CM}_{n}$,
already for $n=6$ we were not able to compute444The two computers that we used
scored 2.43 and 2.92 on Mathematica’s V12.1.1.0 Benchmark Report, considerably
higher than the highest score of 1.89 that the report is comparing against. a
Gröbner basis with respect to an elimination order, neither within Mathematica
nor within Macaulay2. Nevertheless, in the next Section 7 we will present a
more efficient method for computing circuit polynomials that allowed us to
compute all circuit polynomials for $\operatorname{CM}_{6}$.

### Circuit polynomials in $\operatorname{CM}_{6}$.

We demonstrate now the effectiveness of our method for computing circuit
polynomials by computing all the circuit polynomials in
$\operatorname{CM}_{6}$. These polynomials are supported on six types of
graphs: a $K_{4}$, a wheel on $4$ vertices, a wheel on $5$ vertices, a
$2$-dimensional “double banana”, the Desargues-plus-one-edge graph, and the
$K_{3,3}$-plus-one-edge graph. These graphs are shown in Fig. 5 and Fig. 2. To
the best of our knowledge, except for the circuit polynomial of a $K_{4}$
graph which is the unique minor generating $\operatorname{CM}_{4}$, these
circuit polynomials have not been computed before.

### The $K_{4}$ circuits.

The circuit polynomial for the $K_{4}$ graph on the vertices $1234$ is the (up
to a multiplication with a scalar) unique generator of $\operatorname{CM}_{4}$
given by

$\displaystyle p_{K_{4}^{1234}}$
$\displaystyle=x_{3,4}x_{1,2}^{2}+x_{3,4}^{2}x_{1,2}+x_{1,3}x_{2,3}x_{1,2}-x_{1,4}x_{2,3}x_{1,2}-x_{1,3}x_{2,4}x_{1,2}$
$\displaystyle+x_{1,4}^{2}x_{2,3}+x_{1,3}x_{2,4}^{2}+x_{1,4}x_{2,4}x_{1,2}-x_{1,3}x_{3,4}x_{1,2}-x_{1,4}x_{3,4}x_{1,2}$
$\displaystyle+x_{1,3}^{2}x_{2,4}+x_{1,4}x_{2,3}^{2}-x_{2,3}x_{3,4}x_{1,2}-x_{2,4}x_{3,4}x_{1,2}+x_{2,3}x_{2,4}x_{3,4}$
$\displaystyle-
x_{1,3}x_{2,4}x_{3,4}-x_{1,3}x_{1,4}x_{2,3}-x_{1,3}x_{1,4}x_{2,4}-x_{1,3}x_{2,3}x_{2,4}$
$\displaystyle-
x_{1,4}x_{2,3}x_{2,4}+x_{1,3}x_{1,4}x_{3,4}-x_{1,4}x_{2,3}x_{3,4}.$

This polynomial has 22 terms, its homogeneous degree is 3, and it is of degree
2 in any of its variables.

### Wheel on 4 vertices.

The circuit polynomial $p_{W^{1234,5}}$ supported on the wheel $W^{1234,5}$ on
vertices $1234$ with $5$ in the centre is the resultant
$\operatorname{Res}(p_{K_{4}^{1245}},p_{K_{4}^{2345}},x_{2,4})$, where
$p_{K_{4}^{1245}}$ and $p_{K_{4}^{2345}}$ are circuit polynomials supported on
$K_{4}$ on the vertices $1245$ and $2345$, respectively. It can be verified
with a computer algebra package that this resultant is irreducible.

This polynomial has 843 terms, its homogeneous degree is 8, and it is of
degree 4 in each of its variables.

### The “2D double banana”.

The circuit polynomial supported on the 2D double banana
$\\{12,13,23,24,34,15,16,56,45,46\\}$ is the resultant
$\operatorname{Res}(p_{K_{4}^{1234}},p_{K_{4}^{1456}},x_{1,4})$, where
$p_{K_{4}^{1234}}$ and $p_{K_{4}^{1456}}$ are circuit polynomials supported on
$K_{4}$ on the vertices $1245$ and $2345$, respectively. It can be verified
with a computer algebra package that this resultant is irreducible.

This polynomial has 1752 terms, its homogeneous degree is 8, and it is of
degree 4 in each of its variables.

### Wheel on 5 vertices.

The circuit polynomial $p_{W^{12345,6}}$ supported on the wheel $W^{12345,6}$
on vertices $12345$ with $6$ in the centre is the resultant
$\operatorname{Res}(p_{W^{1245,6}},p_{K_{4}^{2346}},x_{2,4})$, where
$p_{W^{1245,6}}$ and $p_{K_{4}^{2346}}$ are circuit polynomials supported on
the wheel $W^{1245,6}$ on the four vertices $1245$ with 6 in the centre and
the $K_{4}$ on te vertices $2345$, respectively. It can be verified with a
computer algebra package that this resultant is irreducible.

This polynomial has 273123 terms, its homogeneous degree is 20, and it is of
degree 8 in each of its variables.

### The Desargues-plus-one circuit.

Let $D$ be the Desargues graph $\\{12,14,15,23,26,34,36,45$, $56\\}$. The
graph $D$ can be completed to a circuit by adjoining to it exactly one of the
edges in the set $\\{13,16,24,25,35,46\\}$, however all choices result in
isomorphic graphs. We will therefore only show how to obtain the circuit
polynomial $p_{D\cup\\{16\\}}$ as the other circuit polynomials can be
obtained by appropriate relabeling.

The circuit polynomial $p_{D\cup\\{16\\}}$ is the resultant
$\operatorname{Res}(p_{W^{1234,5}},p_{K_{4}^{1245}},x_{2,5})$. Its
irreducibility can be verified with a computer algebra package. It has 658175
terms, its homogeneous degree is 20, it is of degree 12 in the variable
$x_{1,6}$ and of degree $8$ in the remaining variables.

### The $K_{3,3}$-plus-one circuit.

Consider the complete bipartite graph $K_{3,3}$ on the vertex partition
$\\{1,4,5\\}\cup\\{2,3,6\\}$. It can be completed to a circuit by adjoining to
it exactly one of the edges in the set $\\{14,15,45,23,26,36\\}$, say $45$,
and as in the case of the Desargues-plus-one circuit, any other choice will
result in a graph isomorphic to $K_{3,3}\cup\\{45\\}$.

The circuit polynomial $p_{K_{3,3,}\cup\\{45\\}}$ is an irreducible polynomial
with 1018050 terms, of homogeneous degree 18, and of degree 8 in each of its
variables.

######  Proposition 8.1.

The circuit polynomial $p_{K_{3,3,}\cup\\{45\\}}$ can not be obtained directly
as the resultant of two circuit polynomials supported on circuits with 6 or
less vertices.

Here by directly we mean that no choice of two circuit polynomials on at most
6 vertices will give an irreducible resultant supported on
${K_{3,3}\cup\\{45\\}}$.

######  Proof 8.2.

Let $p_{1}$ and $p_{2}$ be any two circuit polynomials supported on a circuit
with 6 or less vertices. Consider the resultant
$\operatorname{Res}(p_{1},p_{2},x_{e})$ for some common variable $x_{e}$. Let
$h_{1}$ and $h_{2}$ be the homogeneous degrees, and let $d_{1}$ and $d_{2}$ be
the degrees in $x_{e}$ of $p_{1}$ and $p_{2}$, respectively.

By Proposition 4.5, the homogeneous degree of
$\operatorname{Res}(p_{1},p_{2},x_{e})$ is $h_{1}d_{2}+h_{2}d_{1}-d_{1}d_{2}$,
so if $\operatorname{Res}(p_{1},p_{2},x_{e})=p_{K_{3,3,}\cup\\{45\\}}$, then
$h_{1}d_{2}+h_{2}d_{1}-d_{1}d_{2}=18$. However, the only possible choices for
$(h_{i},d_{i})$ are $(3,2)$, $(8,4)$, $(18,8)$, $(20,8)$ and $(20,12)$ (say
which graph they correspond to), none of which result with
$h_{1}d_{2}+h_{2}d_{1}-d_{1}d_{2}=18$.

However, $K_{3,3}\cup\\{45\\}$ is the combinatorial resultant of the wheels
$W^{1234,5}$ and $W^{1346,5}$ on 1234 with 5 in the centre, and on 1346 with 5
in the centre, respectively, with the edge 15 eliminated. Since
$p_{W^{1234,5}}$ and $p_{W^{1346,5}}$ are of homogeneous degree 8, and have
degree $4$ in $x_{1,5}$, it follows from Proposition 4.5 that
$\operatorname{Res}(p_{W^{1234,5}},p_{W^{1346,5}},x_{1,5})$ has homogeneous
degree 48, hence $p_{K_{3,3}\cup\\{45\\}}$ appears in
$\operatorname{Res}(p_{W^{1234,5}},p_{W^{1346,5}},x_{1,5})$ as a factor, with
multiplicity not greater than 2.

We were not able to compute the resultant
$\operatorname{Res}(p_{W^{1234,5}},p_{W^{1346,5}},x_{1,5})$ before our
machines ran out of memory. We are currently exploring a High Performance
Computer platform to test the limits of our method. Meanwhile, we developed an
extension of our algorithm [32] and computed $p_{K_{3,3}\cup\\{45\\}}$ with
it.

##  9 Concluding Remarks

In this paper we introduced the combinatorial resultant operation, analogous
to the classical resultant of polynomials. To demonstrate the effectiveness of
our method we conclude by listing in Table 1 the circuit polynomials that we
could compute within a reasonable amount of time. The most challenging was the
$K_{3,3}$-plus-one circuit, which required an extension of the method
presented here: this extended resultant is the topic of an upcoming paper
[32].

However, this method still has computational drawbacks in the sense that it
requires an irreducibility check, with a possible further factorization and an
ideal membership test for those factors that have the support of a circuit.

Ideally we would like to detect combinatorially when a resultant of two
circuit polynomials that has the support of a circuit will be irreducible. The
absolute irreducibility test of Gao [17] which states that a polynomial is
absolutely irreducible if and only if its Newton polytope is integrally
indecomposable, in conjunction with the description of the Newton polytope of
the resultant of two polynomials by Gelfand, Kapranov and Zelevinsky [18, 19]
gives a combinatorial criterion for absolute irreducibility, but not for
irreducibility over $\mathbb{Q}$. However, not every circuit polynomial is
absolutely irreducible, for example the circuit polynomial of a wheel on 4
vertices is irreducible over $\mathbb{Q}$ but not absolutely irreducible.

### What we observed in practice.

It is worthwhile to note that whenever in our computations we had to decide
which factor of a resultant belonged to $\operatorname{CM}_{n}$ we never had
to preform an ideal membership test. It was always sufficient to inspect only
the supports of the irreducible factors of the resultant, and in all cases we
had the situation where all but one irreducible factor were supported on Laman
graphs, and one factor was supported on a dependent set. It seems unlikely
that this is the general case, and it would be of interest to determine under
which conditions does the resultant have exactly one factor (up to
multiplicity) supported on a dependent set in
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$.

We conclude the paper with a list of open problems about the algebraic and
geometric structure of the resultant of two circuit polynomials.

######  Problem 9.1.

Let $C$, $A$ and $B$ be sparsity circuits such that
$C=\operatorname{CRes}(A,B,e)$. Let $p_{C}$, $p_{A}$ and $p_{B}$ be the
corresponding circuit polynomials and assume that
$\operatorname{Res}(p_{A},p_{B},x_{e})$ is reducible.

Under which conditions on $C$, $A$, $B$, $p_{A}$ and $p_{B}$ does
$\operatorname{Res}(p_{A},p_{B},x_{e})$ have up to multiplicity exactly one
irreducible factor over $\mathbb{Q}$ equal to $p_{C}$?

######  Problem 9.2.

More generally, if $p,q\in\operatorname{CM}_{n}$ with
$x_{e}\in\operatorname{supp}{p}\cap\operatorname{supp}{q}$, under which
conditions on $p$, $q$, $\operatorname{supp}{p}$ and $\operatorname{supp}{q}$
does $\operatorname{Res}(p,q,x_{e})$ have up to multiplicity exactly one
irreducible factor supported on a dependent set in
$\operatorname{\mathcal{A}}(\operatorname{CM}_{n})$?

The irreducible factor of $\operatorname{Res}(p_{A},p_{B},x_{e})$
corresponding to the circuit polynomial $p_{C}$ defines the variety in
$\mathbb{C}^{\binom{n}{2}}$ of complex placements of $C$, however it is not
clear what is the geometric significance of other factors, if there are any.

######  Problem 9.3.

If $\operatorname{Res}(p_{A},p_{B},x_{e})$ has a factor supported on a Laman
graph, what is its significance? Does this factor have a geometric
interpretation?

The degree with respect to a single variable in the support of a circuit
polynomial is bounded by the number of complex placements of the underlying
Laman graph [6], with an upper bound of $\binom{2n-4}{n-2}\approx 4^{n}$. We
have observed that the number of terms of circuit polynomials quickly becomes
large, as shown in the Table 1.

######  Problem 9.4.

How big do circuit polynomials get, i.e. what are the upper and lower bounds
on the number of monomial terms relative to the number of vertices $n$?

Table 1: Results: all circuit polynomials on $n\leq 6$ vertices and two circuit polynomials on $n=7$ vertices. For the definition of Extended Resultant, see [32]. $n$ | Circuit | Method |  Comp. time (seconds) | No. terms |  Hom. degree
---|---|---|---|---|---
4 | $K_{4}$ | Determinant |  0.0008 | 22 |  3
|
5 | Wheel on 4 vertices | Gröbner |  0.02 | 843 |  8
Resultant |  0.013 |
6 | 2D double banana | Gröbner |  0.164 | 1 752 |  8
Resultant |  0.029 |
6 | Wheel on 5 vertices | Gröbner |  10 857 | 273 123 |  20
Resultant |  7.07 |
6 | Desargues-plus-one | Gröbner |  454 753 | 658 175 |  20
Resultant |  14.62 |
6 | $K_{3,3}$-plus-one | Extended Resultant |  1 402 | 1 018 050 |  18
|
7 | 2D double banana $\oplus_{16}$ $K_{4}^{1567}$ | Resultant |  38.14 | 1 053 933 |  20
|
7 | 2D double banana $\oplus_{56}$ $K_{4}^{4567}$ | Resultant |  89.86 | 2 579 050 |  20
|

## References

  * [1] Evangelos Bartzos, Ioannis Z. Emiris, Jan Legerský, and Elias Tsigaridas.  On the maximal number of real embeddings of minimally rigid graphs in ${R}^{2}$ , ${R}^{3}$ and ${S}^{2}$.  Journal of Symbolic Computation, 102:189–208, 2021.
  * [2] Dave Bayer and David Mumford.  What Can Be Computed In Algebraic Geometry?  In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra, pages 1–48. Cambridge University Press, 1993\.
  * [3] Alex R Berg and Tibor Jordán.  A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid.  Journal of Combinatorial Theory, Series B, 88(1):77 – 97, 2003\.
  * [4] Anna Bernasconi, Ernst W Mayr, Michal Mnuk, and Martin Raab.  Computing the dimension of a polynomial ideal, 2002.
  * [5] Ciprian S. Borcea.  Point configurations and Cayley-Menger varieties.  Technical report, 2002.  ArXiv math/0207110.
  * [6] Ciprian S. Borcea and Ileana Streinu.  The number of embeddings of minimally rigid graphs.  Discrete and Computational Geometry, 31:287–303, February 2004\.
  * [7] B. Buchberger.  Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems.  Aequationes Math., 4:374–383, 1970.
  * [8] Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho.  Computing the number of realizations of a Laman graph.  Electronic notes in Discrete Mathematics, 61:207–213, 2017.
  * [9] David A. Cox, John Little, and Donal O’Shea.  Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra.  Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015\.
  * [10] W. Decker, GM. Greuel, and G. Pfister.  Primary Decomposition: Algorithms and Comparisons.  In B.H. Matzat, GM. Greuel, and G. Hiss, editors, Algorithmic Algebra and Number Theory, pages 187–220. Springer, Berlin, Heidelberg, 1999\.
  * [11] A. Dress and L. Lovász.  On some combinatorial properties of algebraic matroids.  Combinatorica, 7(1):39–48, 1987.
  * [12] Thomas W. Dubé.  The structure of polynomial ideals and Gröbner bases.  SIAM J. Comput., 19(4):750–775, 1990.
  * [13] Richard Ehrenborg and Gian-Carlo Rota.  Apolarity and canonical forms in homogeneous polynomials.  European Journal of Combinatorics, 14(3):157–181, May 1993.
  * [14] David Eisenbud.  Commutative Algebra, with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.
  * [15] I. Emiris and B. Mourrain.  Computer algebra methods for studying and computing molecular conformations.  Algorithmica, 25:372–402, 1999.  doi:10.1007/PL00008283.
  * [16] Ioannis Z. Emiris, Elias P. Tsigaridas, and Antonios Varvitsiotis.  Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs.  In Mucherino, Antonio and Lavor, Carlile and Liberti, Leo and Maculan, Nelson, editor, Distance Geometry. Theory, Methods, and Applications, chapter 2, pages 23–46. Springer, New York, Heidelberg, Dordrecht, London, 2013.  doi:10.1007/978-1-4614-5128-0.
  * [17] Shuhong Gao.  Absolute irreducibility of polynomials via newton polytopes.  Journal of Algebra, 237(2):501 – 520, 2001.
  * [18] I.M. Gelfand, M. Kapranov, and A. Zelevinsky.  Newton Polytopes of the Classical Resultant and Discriminant.  Advances in Mathematics, 84:237 – 254, 1990.
  * [19] I.M. Gelfand, M. Kapranov, and A. Zelevinsky.  Discriminants, Resultants, and Multidimensional Determinants.  Modern Birkhäuser Classics. Birkhäuser Boston, 2009.
  * [20] G.Z. Giambelli.  Sulle varietá rappresentate coll’annullare determinanti minori contenuti in un determinante simmetrico od emisimmetrico generico di forme.  Atti della R. Acc. Sci, di Torino, 44:102–125, 1905/06.
  * [21] Jack Graver, Brigitte Servatius, and Herman Servatius.  Combinatorial rigidity, volume 2 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 1993.
  * [22] Phillip A Griffiths and Joseph Harris.  Principles of algebraic geometry.  Wiley classics library. Wiley, New York, NY, 1994.
  * [23] J. Harris and L.W. Tu.  On symmetric and skew-symmetric determinantal varieties.  Topology, 23:71–84, 1984.  A general result on the dimension of determinantal varieties, mentioned in lecture notes of DA Cox.
  * [24] Lebrecht Henneberg.  Die graphische Statik der starren Systeme.  B. G. Teubner, 1911.
  * [25] John E. Hopcroft and Robert Endre Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2(3):135–158, 1973.
  * [26] A.W. Ingleton.  Representation of Matroids.  In D.J.A. Welsh, editor, Combinatorial mathematics and its applications (Proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969), pages 149–167. Academic Press, 1971.
  * [27] N. Jacobson.  Basic Algebra II: Second Edition.  Dover Books on Mathematics. Dover Publications, 2012.
  * [28] T. Józefiak, A. Lascoux, and P. Pragacz.  Classes of determinantal varieties associated with symmetric and skew-symmetric matrices.  Math. USSR Izvestija, 18:575–586, 1982.
  * [29] Serge Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 2002.
  * [30] Audrey Lee-St. John and Ileana Streinu.  Pebble game algorithms and sparse graphs.  Discrete Mathematics, 308(8):1425–1437, April 2008.
  * [31] Goran Malić and Ileana Streinu.  CayleyMenger - Circuit Polynomials in the Cayley Menger ideal, a GitHub repository.  https://github.com/circuitPolys/CayleyMenger, 2020.
  * [32] Goran Malić and Ileana Streinu.  Circuit polynomial for the $K_{3,3}$-plus-one circuit, 2021.  In preparation.
  * [33] Goran Malić and Ileana Streinu.  Combinatorial Resultants in the Algebraic Rigidity Matroid.  In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021)), 2021.  To appear.
  * [34] Guillermo Matera and Jose Maria Turull Torres.  The space complexity of elimination theory: upper bounds.  In Foundations of computational mathematics (Rio de Janeiro, 1997), pages 267–276. Springer, Berlin, 1997.
  * [35] James Clerk Maxwell.  On the calculation of the equilibrium and stiffness of frames.  Philosophical Magazine, 27:294–299, 1864.
  * [36] Ernst W. Mayr and Stephan Ritscher.  Dimension-dependent bounds for Gröbner bases of polynomial ideals.  J. Symbolic Comput., 49:78–94, 2013.
  * [37] Ernst W. Mayr and Stefan Toman.  Complexity of membership problems of different types of polynomial ideals.  In Gebhard Böckle, Wolfram Decker, and Gunter Malle, editors, Algorithmic and experimental methods in algebra, geometry, and number theory, pages 481–493. Springer, Cham, 2017.
  * [38] James Oxley.  Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, second edition, 2011.
  * [39] Zvi Rosen.  Algebraic Matroids in Applications.  PhD thesis, University of California, Berkeley, 2015.
  * [40] Zvi Rosen.  algebraic-matroids, a GitHub repository.  https://github.com/zvihr/algebraic-matroids, 2017.
  * [41] Zvi Rosen, Jessica Sidman, and Louis Theran.  Algebraic matroids in action.  The American Mathematical Monthly, 127(3):199–216, February 2020\.
  * [42] Meera Sitharam and Heping Gao.  Characterizing graphs with convex and connected Cayley configuration spaces.  Discrete and Computational Geometry, 43(3):594–625, 2010.
  * [43] William T. Tutte.  Connectivity in graphs.  Toronto University Press, Toronto, 1966.
  * [44] B. L. van der Waerden.  Moderne Algebra, 2nd edition.  Translated by Fred Blum and John R. Schulenberger. Springer, Berlin, Heidelberg, New York, 1967.
  * [45] B. L. van der Waerden.  Algebra. Vol. 2.  Translated by John R. Schulenberger. Frederick Ungar Publishing Co., New York, 1970.
  * [46] D. Walter and M.L. Husty.  On a nine-bar linkage, its possible configurations and conditions for flexibility.  In Merlet J.-P. and M. Dahan, editors, Proceedings of IFFToMM 2007, Besançon, France, 2007.
  * [47] Walter Whiteley.  Some matroids from discrete applied geometry.  In J. Bonin, James G. Oxley, and Brigitte Servatius, editors, Matroid Theory, volume 197 of Contemporary Mathematics, pages 171–311. American Mathematical Society, 1996.