arXiv:1109.2368v2 [math.AG] 24 Mar 2013

COMPUTING TROPICAL RESULTANTS
ANDERS JENSEN AND JOSEPHINE YU

Abstract. We fix the supports A = (A1 , . . . , Ak ) of a list of tropical polynomials and define the tropical resultant T R(A) to be the set of choices of
coefficients such that the tropical polynomials have a common solution. We
prove that T R(A) is the tropicalization of the algebraic variety of solvable
systems and that its dimension can be computed in polynomial time. The
tropical resultant inherits a fan structure from the secondary fan of the Cayley configuration of A, and we present algorithms for the traversal of T R(A) in
this structure. We also present a new algorithm for recovering a Newton polytope from the support of its tropical hypersurface. We use this to compute the
Newton polytope of the sparse resultant polynomial in the case when T R(A)
is of codimension 1. Finally we consider the more general setting of specialized
tropical resultants and report on experiments with our implementations.

1. Introduction
We study generalizations of the problem of computing the Newton polytope of
the sparse resultant combinatorially, without first computing the resultant polynomial. The input is a tuple A = (A1 , A2 , . . . , Ak ) of integer point configurations
in Zn . The sparse resultant R(A) of A, or the variety of solvable systems, is the
closure in (C∗ )A1 × (C∗ )A2 × · · · × (C∗ )Ak of the collection of tuples of polynomials
(f1 , f2 , . . . , fk ) such that f1 = f2 = · · · = fk = 0 has a solution in (C∗ )n and each
fi has support Ai . This variety is irreducible and defined over Q [Stu94]. If R(A)
is a hypersurface, then it is defined by a polynomial, unique up to scalar multiple,
called the (sparse) resultant polynomial of A. Its Newton polytope is called the
resultant polytope of A.
In the hypersurface case, Sturmfels gave a combinatorial description of the resultant polytope [Stu94], giving rise to a combinatorial algorithm for computing
its vertices from the vertices of the secondary polytope of the Cayley configuration
Cay(A). A drawback of this construction is that the secondary polytope typically has far more vertices than the resultant polytope. There have been attempts
to compute the resultant polytopes without enumerating all vertices of the secondary polytope [EFK10]. A main contribution of our paper is an algorithm (Section 2.5) for traversing the tropicalization of R(A) as a subfan of the secondary
fan of Cay(A). This approach allows us to compute tropicalizations of resultant
varieties of arbitrary codimension.
The tropical resultant T R(A) consists of tuples of tropical polynomials having
a common solution. We show in Theorem 2.4 that T R(A) coincides with the
tropicalization of R(A). The tropical resultant is combinatorial in nature, and we
Date: March 26, 2013.
2010 Mathematics Subject Classification: 14T05, 13P15, 14M25, 52B20, 52B55
Keywords: tropical geometry, resultant, Newton polytope, computational geometry .
1

2

ANDERS JENSEN AND JOSEPHINE YU

present in Theorem 2.9 a simple description of it as a union of polyhedral cones,
each of which is the sum of a positive orthant and a linear space.
In [DFS07], the tropical discriminant is described as a sum of a tropical linear
space and an ordinary linear space. This description carries over to the tropical
resultant when A is essential, and in particular R(A) is a hypersurface. Our description in Theorem 2.9 is different and also works for non-essential cases and
non-hypersurface cases. Moreover, it is simpler, and we do not need to compute a
nontrivial tropical linear space.
The tropicalization of a variety is a polyhedral fan of the same dimension as
the original variety. We derive a new formula for the codimension of the (tropical)
resultant in Theorem 2.23 and show that it can be computed in polynomial time
using the cardinality matroid intersection algorithm.
Specialized resultants are obtained by fixing some coefficients of fi ’s and considering the collection of other coefficients giving a polynomial system solvable in
the algebraic torus. In other words, the specialized resultants are intersections of
sparse resultants and subspaces parallel to coordinate subspaces. When the specialized coefficient values are generic, the tropicalization T RS (A) of the specialized
resultant is the stable intersection of the tropical resultant T R(A) with a coordinate subspace. This is a subfan of the restriction of the secondary fan of Cay(A)
to the subspace and can be computed by a fan traversal. The algorithms are significantly more complex and are described in Section 3. Moreover, using the results
from our concurrent work on tropical stable intersections [JY], we describe the specialized tropical resultant as a union of cones, each of which is the intersection of a
coordinate subspace and the sum of a positive orthant and a linear space.
Computation of resultants and specialized resultants, of which the implicitization
problem is a special case, is a classical problem in commutative algebra that remains
an active area. In the concurrent work [EFKP11] an algorithm for computing
Newton polytopes of specialized resultant polynomials using Sturmfels’ formula
and the beneath-beyond method is presented and implemented, and the work is
therefore highly relevant for our project. While the main focus of [EFKP11] is
the efficiency of the computation of the Newton polytopes of specialized resultant
polynomials, our main interest has been the geometric structure of secondary fans
which allows traversal of tropical resultants of arbitrary codimension.
The tropical description of a polytope P is a collection of cones whose union
is the support of the codimension one skeleton of the normal fan of P , with multiplicities carrying lengths of the edges of P . That is, the union is the tropical
hypersurface defined by P . For example, the tropical hypersurface of a zonotope is
the union of the dual hyperplanes (zones), and the tropical hypersurface of the secondary polytope of a point configuration contains codimension one cones spanned
by vectors in the Gale dual. See Section 2.3. The tropical description uniquely
identifies the polytope up to translation, and we consider it to be an equally important representation of a polytope as the V- and H-descriptions. Furthermore,
the conversion algorithms between these representations deserve the same attention
as other fundamental problems in convex geometry. A contribution of this paper
is an algorithm (Algorithm 4.1) for reconstructing normal fans of polytopes from
their tropical descriptions. We apply the algorithm to the tropical description of
resultant polytopes in Theorem 2.9 to recover the combinatorics of the resultant

COMPUTING TROPICAL RESULTANTS

3

polytope. From the normal fan, we can efficiently obtain the V-description of the
polytope.
All the algorithms described in this paper have been implemented in the software
Gfan [Jen]. Computational experiments and examples are presented in Section 5.
A list of open problems is presented in Section 6.
2. Resultants
Let A = (A1 , A2 , . . . , Ak ) where each Ai = {ai,1 , ai,2 , . . . , ai,mi } is a multi-subset
of Zn , and let m = m1 + m2 + · · · + mk . Throughout this paper, we assume that
mi ≥ 2 for all i. However, the points in Ai need not be distinct. This is important
for some applications such as implicitization. Let Q1 , Q2 , . . . , Qk be the convex
∗ Ai
denote the set of polynomials of
hulls of AP
1 , A2 , . . . , Ak respectively. Let (C )
mi
aij
in C[x1 , x2 , . . . , xn ], where each cj is in C∗ := C\{0}. Let
the form j=1 cj x
Q
Z ⊆ ki=1 (C∗ )Ai be the set consisting of tuples (f1 , f2 , . . . , fk ) such that the system
of equations f1 = f2 = · · · = fk = 0 has a solution in (C∗ )n .
Definition 2.1. The resultant variety, or the variety of solvable systems, is the
Qk
closure Z of Z in i=1 (C∗ )Ai and is denoted R(A).
Qk
The resultant variety is usually defined as a subvariety of i=1 CAi or its projecQk
tivization [GKZ94, Stu94], but we chose to work in i=1 (C∗ )Ai as tropicalizations
are most naturally defined for subvarieties of tori.
2.1. A simple description of the tropical resultant and its multiplicities.
The tropical semiring T = (R, ⊕, ⊙) is the set of real numbers with minimum as
tropical addition ⊕ and usual addition as tropical multiplication ⊙. A tropical
(Laurent) polynomial F in n variables x = (x1 , x2 , . . . , xn ) is a multiset of terms
(c, a) or c ⊙ xa where c ∈ R is the coefficient
and a = (a1 , a2 , . . . , an ) ∈ Zn is
L
the exponent. We will also write F = (c,a)∈F (c ⊙ xa ). The support of F is the
multiset of a’s, and the Newton polytope of F is the convex hull of its support.
The tropical solution set T (F ) of a tropical polynomial F is the locus of points
x ∈ Rn such the minimum is attained at least twice in the expression
M
(c ⊙ xa ) = min (c + a1 x1 + a2 x2 + · · · + an xn ).
(c,a)∈F

(c,a)∈F

In other words, a point x ∈ Rn is in T (F ) if and only if the minimum for (1, x)·(c, a)
is attained for two terms in F , which may be repeated elements. Therefore, T (F )
is a (not necessarily pure dimensional) subcomplex of a polyhedral complex dual
to the marked regular subdivision of the support of F induced by the coefficients
c, consisting of duals of cells with at least two marked points. See Section 2.2 for
definitions of subdivisions and marked points.
When F contains no repeated elements, the tropical solution set coincides with
the non-smooth
locus of the piecewise-linear function from Rn to R given by x 7→
L
F (x) = (c,a)∈F (c ⊙ xa ), which is also called a tropical hypersurface. In particular,
if all coefficients of F are the same and if F contains no repeated elements, then
the tropical hypersurface is the codimension one skeleton of the inner normal fan
of the Newton polytope of F .
Let A = (A1 , A2 , . . . , L
Ak ) be as before, and let RAi denote the set of tropical
mi
(cij ⊙ x⊙aij ).
polynomials of the form j=1

4

ANDERS JENSEN AND JOSEPHINE YU

Definition 2.2. The tropical resultant T R(A) of A is the subset of Rm , or RA1 ×
RA2 × · · · × RAk , consisting of tuples (F1 , F2 , . . . , Fk ) such that the tropical solution
sets of F1 , F2 , . . . , Fk have a nonempty common intersection in Rn .
Q
We can also consider the tropical resultant as a subset of ki=1 RAi /(1, 1, . . . , 1)R,
but we prefer to work with Rm in this paper.
For two univariate tropical polynomials, the term “tropical resultant” had been
used by other authors to describe a tropical polynomial analogous to ordinary
resultants. In [Oda08] it is defined as the tropical determinant of the tropical
Sylvester matrix. In [Tab08] it is defined as the tropicalization of the ordinary
resultant polynomial. In this paper the term “tropical resultant” always refers to
a fan and never a tropical polynomial.
Definition 2.3. Let k be a field and I ⊆ k[x1 , . . . , xn ] an ideal. The tropical
variety T (I) of I, or the tropicalization of V (I), is a polyhedral fan with support
T (I) := {ω ∈ Rn : the initial ideal inω (I) contains no monomials}.
For ω in the relative interior of a cone Cω ∈ T (I) we define its multiplicity as
multω (T (I)) := dimk (k[Zn ∩ Cω⊥ ]/hinω (I)i)
when the right hand side is finite, in particular when Cω is a Gröbner cone of the
same dimension as T (I).
In this definition we refer to the “constant coefficient” initial ideal as in [BJS+ 07],
where we disregard any valuation of the ground field even if it is non-trivial, except that we are picking out the terms with smallest ω-degree. If the ideal I is
homogeneous, T (I) gets a fan structure from the Gröbner fan of I. When Cω is
the smallest Gröbner cone in T (I) containing ω, the initial ideal inω (I) is homogeneous with respect to any weight in the linear span of Cω . Hence after multiplying
each homogeneous element of inω (I) by a Laurent monomial they generate an ideal
hinω (I)i in the ring k[Zn ∩ Cω⊥ ] of Laurent polynomials in x1 , x2 , . . . , xn which are
of degree zero with respect to the weight vector ω.
The following is the first main result toward a combinatorial description of the
tropicalization of R(A).
Theorem 2.4. The support of the tropicalization of the resultant variety R(A)
coincides with the tropical resultant T R(A).
A consequence is that we may identify T R(A) with the tropicalization of R(A)
and we define its multiplicities accordingly.
We will use incidence varieties to give a proof of Theorem 2.4. Let the incidence
variety be
(1)

W := {(f1 , f2 , . . . , fk , x) : fi (x) = 0 for all i} ⊆

k
Y

(C∗ )Ai × (C∗ )n ,

i=1

and let the tropical incidence variety be the set

T W := {(F1 , F2 , . . . , Fk , X) : X ∈ T (Fi ) for all i} ⊆

k
Y

i=1
+

RA i × Rn .

The tropical incidence variety is the tropical prevariety [BJS 07] defined by the
tropicalization of the polynomials f1 , f2 , . . . , fk , where fi is considered as a polynomial in mi + n variables whose support in the n variables is Ai and whose mi terms

COMPUTING TROPICAL RESULTANTS

5

have indeterminate coefficients. Even if Ai contains repeated points, the support
of fi in mi + n variables has no repeated points.
Lemma 2.5. The polynomials f1 , f2 , . . . , fk form a tropical basis for the incidence
variety W , i.e. the tropical incidence variety coincides with the support of the tropicalization of the incidence variety.
Proof. Let K be the field of Puiseux series in t with complex coefficients. By
the Fundamental Theorem of Tropical Geometry [JMM08, MS], ω ∈ T (I) ∩ Qn
if and only if ω = val(x) for some K-valued point x in the variety of I. Since
our fans are rational, it suffices to check that they agree on rational points. Let
(F1 , F2 , . . . , Fk , X) be a rational point in the tropical prevariety, i.e. F1 , F2 , . . . , Fk
are (coefficient vectors of) tropical polynomials with support sets A1 , A2 , . . . , Ak ,
and X ∈ Qn is a tropical solution for each Fi . We will show that this tuple can
be lifted to a K-valued point in W , by first lifting X, then F1 , F2 , . . . , Fn . Let
x0 = (tX1 , tX2 , . . . , tXk ) ∈ (K ∗ )n . Then Fi ∈ Qmi is contained in the tropical
hypersurface of fi (x0 ) considered as a polynomial in the indeterminate coefficients.
By the hypersurface case of the Fundamental Theorem (also known as Kapranov’s
Theorem) there is a tuple ci ∈ (K ∗ )mi of coefficients of fi with val(ci ) = Fi giving
fi (x0 ) = 0. Therefore (F1 , F2 , . . . , Fk , X) can be lifted to the incidence variety and
lies in the tropicalization of the incidence variety.

A consequence of Lemma 2.5 is that we may identify the tropical incidence
variety with the support of the tropicalization of W and we define its multiplicities
accordingly.
The following lemma follows immediately from the definitions. It is a tropical
counterpart of an analogous statement for classical resultants.
Lemma 2.6. The tropical resultant is the projection of the tropical incidence variety onto the first factor.
Let π be the projection from Rm × Rn , where the incidence variety lies, to the
first factor Rm . We can now prove Theorem 2.4.
Proof of Theorem 2.4. The resultant variety R(A) is obtained from the incidence
Qk
variety W by projecting onto the first factor i=1 (C∗ )Ai and taking the closure.
This proves the first of the following equalities.
T (R(A)) = T (π(W )) = π(T (W )) = π(T W ) = T R(A)

The second follows from [ST08] which says that the tropicalization of the closure
of a projection of W is the projection of the tropicalization of W . The third is
Lemma 2.5, and the last is Lemma 2.6.

For each i = 1, 2, . . . , k, let Pei be the Newton polytope of fi in Rmi × Rn , which
is in turn embedded in Rm × Rn . The tropical incidence variety is equal to the
f1 ) ∩ · · · ∩ T (P
fk ), which is a union of normal cones of P
f1 + · · · + P
fk
intersection T (P
associated to faces that are Minkowski sums of faces of dimension at least one.
f1 , . . . , P
fk together linearly span an m-dimensional subspace in
The vertices of P
m
n
R × R . Projecting this onto Rm takes each Pei isomorphically onto the standard
f1 +
simplex in Rmi which is embedded in Rm . In particular, the Minkowski sum P
f
· · · + Pk projects isomorphically onto the Minkowski sum of standard simplices
lying in orthogonal subspaces. It follows that every maximal cone in the tropical

6

ANDERS JENSEN AND JOSEPHINE YU

incidence variety appears uniquely as the intersection of some normal cones to edges
f1 , P
f2 , . . . , P
fk .
of P
The tropical incidence variety is
!
k
\
[
fi )
N (E
(2)
(E1 ,E2 ,...,Ek )

i=1

fi )
where the union runs over all choices of pairs Ei of points from Ai and N (E
f
e
denotes the inner normal cone of the corresponding edge Ei in Pi . Even if the pair
fi is always an edge
Ei does not form an edge in the convex hull Qi of Ai , the pair E
e
f
of the simplex Pi , so N (Ei ) has the right dimension.

Lemma 2.7. Every maximal cone in the tropical incidence variety T W = T (W )
has multiplicity one.

Proof. Since every vertex of every Pei has its own coordinate, the dimension of a
f1 + P
f2 + · · · + P
fk minimizing a vector ω ∈ Rm × Rn is
face of the Minkowski sum P
the sum of the dimensions of the faces of each Pei with respect to ω. The dimension
of the incidence variety is m + n − k and therefore, for a generic ω ∈ T (W ), the
f1 + P
f2 + · · · + P
fk minimizing ω has dimension k and must be a zonotope.
face of P
Consequently the forms inω (f1 ), inω (f2 ), . . . , inω (fk ) are binomials, each with an
associated edge vector vi ∈ Zm+n . The vectors v1 , v2 , . . . , vk generate Cω⊥ and after
multiplying each inω (fi ) by a monomial it ends up in hinω (I)i ⊆ C[Zm+n ∩ Cω⊥ ].
Hence using the binomials to rewrite modulo hinω (I)i we get that dimC (C[Zm+n ∩
Cω⊥ ]/hinω (I)i) is bounded by the index of the sublattice generated by v1 , v2 , . . . , vn
in Zm+n ∩ Cω⊥ . If we write the edge vectors as columns of a matrix, then the matrix
contains a full-rank identity submatrix, so the sublattice has index one.

The tropical resultant is the projection of the tropical incidence variety, so
!
k
\
[
fi ) .
N (E
π
T R(A) =
(E1 ,E2 ,...,Ek )

i=1

The Cayley configuration Cay(A) of a tuple A = (A1 , A2 , . . . , Ak ) of point configurations in Zn is defined to be the point configuration
Cay(A) = ({e1 } × A1 ) ∪ · · · ∪ ({ek } × Ak )
in Zk × Zn . We will also use Cay(A) to denote a matrix whose columns are points
in the Cayley configuration. See Example 2.10.
Lemma 2.8. Let E = (E1 , E2 , . . . , Ek ) be a tuple of pairs from A1 , A2 , . . . , Ak
respectively. Then the following cones coincide:
!
k
\
fi ) = R≥0 {eij : aij ∈
N (E
/ Ei } + rowspace(Cay(A)).
π
i=1

Proof. Let E be fixed. The left hand side consists of tuples of tropical polynomiQk
als (F1 , F2 , . . . , Fk ) ∈ i=1 RAi for which there is a point w ∈ Rn attaining the
minimum for Fi at Ei for every i.
On the other hand, the cone R≥0 {eij : aij ∈
/ Ei } consists of all F = (F1 , F2 , . . . , Fk )
such that the minimum for Fi evaluated at the point 0 ∈ Rn has value 0 and is
attained at Ei for every i. The tropical solution sets remains the same if coefficients

COMPUTING TROPICAL RESULTANTS

7

of Fi are changed by a tropical scalar multiple, which corresponds to adding to F
a multiple of the i-th row of Cay(A). For w ∈ Rn and F ∈ RA ,
F (x − w) = min c + a · (x − w) = (F − w · A)(x),
(c,a)∈F

where A denotes the matrix whose columns are points in A1 ∪· · ·∪Ak , i.e. A consists
of the last n rows of Cay(A), so
T (F ) + w = T (F − wA).
Therefore, changing the coefficients (F1 , F2 , . . . , Fk ) by an element in the row space
of Cay(A) has the effect of tropically scaling Fi ’s and translating all the tropical
solution sets together. Thus the set on the right hand side consists of all tuples
(F1 , F2 , . . . , Fk ) having a point w ∈ Rn achieving the minimum for Fi at Ei for
every i.

The following result gives a simple description of the tropical resultant as a union
of cones with multiplicities.
Theorem 2.9. The tropical resultant of A is the set
[
(3)
T R(A) =
R≥0 {eij : aij ∈
/ Ei } + rowspace(Cay(A))
E

where E = (E1 , E2 , . . . , Ek ) and each Ei consists of two elements in Ai . The
multiplicity of the cone associated to E is the index of the lattice spanned by the
rows of Cay(E) in rowspace(Cay(E)) ∩ Zm .

The set described in the right hand side of (3) may not have a natural fan structure.
See Example 2.18(b).
For a generic ω ∈ T R(A), we can compute the multiplicity of T R(A) at ω as
follows. We say that ω is generic if all the cones on the right hand side of (3)
that contain ω are maximal-dimensional, contain ω in their relative interior, and
have the same span. Then the multiplicity at ω is the sum of multiplicities of the
cones that contain ω. The generic points form a dense open set in T R(A), and the
lower-dimensional cones on the right hand side do not contribute to the multiplicity.
Proof of Theorem 2.9. The set theoretic statement follows immediately from (2)
and LemmasT2.6 and 2.8.
k
fi ) be the cone corresponding to E in the incidence variety,
Let σ = i=1 N (E
and τ = π(σ). Using the refinement in [CTY10] of the multiplicity formula from
tropical elimination theory [ST08], the multiplicity of τ in the tropical resultant is
the lattice index [Lτ : π(Lσ )], where Lτ = Rτ ∩ Zm and Lσ = Rσ ∩ Zm+n . The
lattice Lσ is defined by the following equations on (c, x) ∈ Zm+n
c · (eij − eik ) + x · (aij − aik ) = 0 for {aij , aik } = Ei
and is spanned by the integer points in the lineality space of the tropical incidence
variety and the standard basis vectors eij for aij ∈
/ Ei . The rows of the following
matrix span the lattice points in the lineality space of the incidence variety:


0
.
Cay(A)
−In
Hence π(Lσ ) is spanned by the rows of Cay(A) and the eij ’s for aij ∈
/ Ei .



8

ANDERS JENSEN AND JOSEPHINE YU

The first summand in (3) plus the linear span of the first k rows of Cay(A)
is a tropical linear space obtained as a Cartesian product of tropical hyperplanes.
Hence Theorem 2.9 can be rephrased as follows. Let C be the matrix consisting of
the first k rows of Cay(A), so the kernel of C is defined by equations of the form
ci,1 + ci,2 + · · · + ci,mi = 0 for i = 1, 2, . . . , k. Then the tropical resultant is the set
(4)

T R(A) = T (ker(C)) + rowspace [A1 |A2 | · · · |Ak ] .

The tropical linear space here is trivial to compute, as it is described by the first
summand of (3). By contrast the tropical linear space computation required for
tropical discriminants in [DFS07] can be challenging. The state of the art in computing tropical linear spaces is the work of Rincón [Rin].
Example 2.10. Consider the tuple A = (A1 , A2 , A3 ) of the following point configurations in Z2 :
A1 = {(0, 0), (0, 1), (1, 0)},
(5)

A2 = {(0, 0), (1, 0), (2, 1)},
A3 = {(0, 0), (0, 1), (1, 2)}.

The Cayley configuration Cay(A)
which we also denote Cay(A):

1 1
 0 0

Cay(A) = 
 0 0
 0 1
0 0

consist of columns of the following matrix,
1
0
0
0
1

0
1
0
0
0

0
1
0
1
0

0
1
0
2
1

0
0
1
0
0

0
0
1
0
1

The corresponding system of polynomials consist of

0
0
1
1
2








f1 = c11 + c12 y + c13 x,
(6)

f2 = c21 + c22 x + c23 x2 y,
f3 = c31 + c32 y + c33 xy 2 .

The point
(0, 0, 0, 0, 1, 5, 0, 1, 5)
is in the tropical resultant variety because the tropical hypersurfaces of the three
tropical polynomials
F1 = 0 ⊕ X ⊕ Y,
(7)

F2 = 0 ⊕ (1 ⊙ X) ⊕ (5 ⊙ X ⊙2 ⊙ Y )
F3 = 0 ⊕ (1 ⊙ Y ) ⊕ (5 ⊙ X ⊙ Y ⊙2 )

contain the common intersection points (−1, −1) and (−2, −2). See Figure 1.
Consider the incidence variety defined by the ideal
I = hf1 , f2 , f3 i ⊆ C[c±1 , x±1 , y ±1 ].

COMPUTING TROPICAL RESULTANTS

9

(0,0)
(-3,-1)
(-1,-1)
(-2,-2)
(-1,-3)

Figure 1. A tropical hypersurface arrangement and its dual regular mixed subdivision (RMS) of the Minkowski sum of point configurations. The mixed cells are shaded. See Examples 2.10
and 2.18(a).
The resultant variety is obtained by eliminating x and y from the system, i.e. it is
defined by the ideal I ∩ C[c±1 ]. In this case, the resultant variety is a hypersurface
defined by the resultant polynomial
c312 c323 c331 − 2c11 c212 c323 c231 c32 − c212 c13 c22 c223 c31 c232 + c211 c12 c323 c31 c232 −
c12 c213 c21 c223 c332 + c11 c12 c13 c22 c223 c332 + 3c212 c13 c21 c223 c231 c33 + c11 c212 c22 c223 c231 c33 +
2c212 c13 c222 c23 c31 c32 c33 − c11 c12 c13 c21 c223 c31 c32 c33 − c211 c12 c22 c223 c31 c32 c33 +
2c12 c213 c21 c22 c23 c232 c33 − 2c11 c12 c13 c222 c23 c232 c33 − c212 c13 c322 c31 c233 +
3c12 c213 c221 c23 c31 c233 − c11 c12 c13 c21 c22 c23 c31 c233 − c311 c21 c223 c31 c233 −
c12 c213 c21 c222 c32 c233 + c11 c12 c13 c322 c32 c233 + c11 c213 c221 c23 c32 c233 −
c211 c13 c21 c22 c23 c32 c233 + c313 c321 c333 − 2c11 c213 c221 c22 c333 + c211 c13 c21 c222 c333 .
It is homogeneous with respect to the rows of Cay(A). Its Newton polytope is
four-dimensional, has f-vector (15, 40, 38, 13, 1) and lies in an affine space parallel
to the kernel of Cay(A).
The tropical resultant is an eight-dimensional fan in R9 with a five-dimensional
lineality space rowspace(Cay(A)). As a subfan of the secondary fan of Cay(A),
it consists of 89 (out of 338) eight-dimensional secondary cones, which can be
coarsened to get the 40 normal cones dual to edges of the resultant polytope. In
other words, the 40 normal cones can be subdivided to obtain the 89 secondary
cones.
In this example, the point configuration is essential, so T (RA) is equal to the
tropical discriminant of Cay(A), which is described in [DFS07] as
T (ker Cay(A)) + rowspace(Cay(A)).
With the Gröbner fan structure, the tropical linear space T (ker Cay(A)) is a 4dimensional fan with f-vector (1, 15, 66, 84), so in the reconstruction of the Newton
polytope, we have to process 84 maximal cones, compared with 27 cones from
our description in (3) or (4). For larger examples, computing tropical linear spaces
becomes a challenging problem, while our description remains simple. In both cases,
however, the main computational difficulty is the reconstruction of the Newton
polytope from the tropical hypersurface.

10

ANDERS JENSEN AND JOSEPHINE YU

2.2. Secondary fan structure and links in tropical resultants. Let A ∈
Zd×m be an integer matrix with columns a1 , a2 , . . . , am ∈ Zd . We will also denote
by A the point configuration {a1 , a2 , . . . , am }. We allow repeated points in A, as
we consider the points to be labeled by the set {1, 2, . . . , m}, and every column of
A gets a distinct label.
Following [GKZ94, Section 7.2A], a subdivision of A is defined as a family ∆ =
{Ci ⊆ A : i ∈ I} of subsets of A such that
(1) dim(conv(CS
i )) = dim(conv(A)) for each i ∈ I,
(2) conv(A) = i∈I conv(Ci ), and
(3) for every i, j ∈ I, the intersection of conv(Ci ) and conv(Cj ) is a face of
both, and Ci ∩ conv(Cj ) = Cj ∩ conv(Ci ).
This notion is also called a marked subdivision by some authors, as it depends not
only
S on the polyhedra conv(Ci ) but also on the labeled sets Ci . The elements in
i∈I Ci are called marked. If F is a face of conv(Ci ) for some Ci ∈ ∆, then the
labeled set Ci ∩ F is called a cell of the subdivision. The sets Ci ’s are maximal
cells.
For two subdivisions ∆ and ∆′ of A, we say that ∆ refines ∆′ or ∆′ coarsens ∆
if every Ci ∈ ∆ is contained in some Cj′ ∈ ∆′ . A subdivision is a triangulation if no
proper refinement exists, and equivalently, if every maximal cell contains exactly
dim(conv(A)) + 1 elements.
Let ω : A → R be an arbitrary real valued function on A, called a weight vector.
We can define a subdivision of A induced by ω as follows. Consider the unbounded
polyhedron P = conv{(a, ω(a))} + R≥0 {ed+1 } in Rd+1 , and let {Fi : i ∈ I} be its
bounded facets. Then the induced subdivision is {Ci : i ∈ I} where Ci = {a ∈
A : (a, ω(a)) ∈ Fi }. A subdivision A is regular or coherent if it is induced by some
weight vector ω. The partition of the space of weight vectors RA according to
induced subdivisions is a fan, called the secondary fan of A.
Following [GKZ94, Section 7.1D], we can construct the secondary polytope of A
as follows. For a triangulation T of a point configuration A, define the GKZ-vector
φT ∈ RA as
X
φT (a) :=
vol(σ)
σ∈T :a∈σ

where the summation is over all maximal cells σ of T containing a.

Definition 2.11. The secondary polytope Σ(A) is the convex hull in RA of the
vectors φT where T runs over all triangulations of A.
Theorem 2.12. [GKZ94, § 7.1, Theorem 1.7] The vertices of Σ(A) are precisely
the vectors φT for which T is a regular triangulation of A. The normal fan of the
secondary polytope Σ(A) is the secondary fan of A. The normal cone of Σ(A) at
φT is the closure of the set of all weights w ∈ RA which induce the triangulation T .
The link of a cone σ ⊆ Rm at a point v ∈ σ is
linkv (σ) = {u ∈ Rm | ∃δ > 0 : ∀ε between 0 and δ : v + εu ∈ σ}.
The link of a fan F at a point v in the support of F is the fan
linkv (F ) = {linkv (σ) | v ∈ σ ∈ F }.
For any cone τ ∈ F , any two points in the relative interior of τ give the same link
of the fan, denoted linkτ (F ). If a maximal cone τ ∈ F has an assigned multiplicity,
then we let linkv (τ ) ∈ linkv (F ) inherit it.

COMPUTING TROPICAL RESULTANTS

11

We will first show that the link of the secondary fan at a point is a common
refinement of secondary fans, or, more precisely, that a face of a secondary polytope
is a Minkowski sum of secondary polytopes. For a sub-configuration C ⊆ A, we
can consider the secondary polytope of C as embedded in RA by setting φT (a) = 0
for a ∈ A\C for every triangulation T of C. On the other hand, the secondary
fan of C embeds in RA with lineality space containing the coordinate directions
corresponding to a ∈ A\C.
Lemma 2.13. Let A be a point configuration, ω ∈ RA , and ∆ω be the regular
subdivision of A induced by ω. Then the face Fω of the secondary polytope of A
supported by ω is the Minkowski sum of secondary polytopes of maximal cells in
∆ω .
Proof. Let ω ′ ∈ RA be a generic weight vector and p be the vertex of the Minkowski
sum picked out by ω ′ . For all sufficiently small ε > 0, the triangulation ∆ω+εω′
refines the subdivision ∆ω . Let pi be the GKZ-vector of the triangulation of the
i-th maximal cell induced by (the restriction of) the vector ω + εω ′ , which is the
same as the triangulation induced by ω ′ because ω induces the trivial
subdivision
P
on each cell of ∆ω . Then the P
GKZ-vector of ∆ω+εω′ is the sum i pi . Hence the
vertex of Fω in direction ω ′ is i pi . We can then conclude that the two polytopes
are the same since they have the same vertex in each generic direction.

We now define mixed subdivisions as in [DLRS10]. For point configurations
A1 , A2 , . . . , Ak in Rn , with Ai = {ai,j : 1 ≤ j ≤ mi }, the Minkowski sum
k
X

Ai = {a1,j1 + a2,j2 + · · · + ak,jk : 1 ≤ ji ≤ mi }

i=1

is a configuration of m1 m2 · · · mk points labeled by [m1 ] × [m2 ] × · · · × [mk ].
Definition 2.14. A subset of labels is a mixed cell if it is a product of labels
J1 × J2 × · · · × Jk where Ji is a nonempty subset of [mi ], and it is fully mixed if in
addition Ji contains at least two elements for every i = 1, 2, . . . , k. A subdivision
Pk
of the Minkowski sum i=1 Ai is mixed if every maximal cell is labeled by a mixed
cell.
Pk
A mixed subdivision of i=1 Ai is also referred to as a mixed subdivision of the
tuple A = (A1 , A2 , . . . , Ak ). Our definition of fully mixed cell differs from that of
[DFS07, Section 6] where it is required that conv(ai,j : j ∈ Ji ) has affine dimension
at least one, while we only require that Ji contains at least two elements. These
two definitions coincide if none of the Ji ’s contains repeated points.
A mixed subdivision is called regular if it is induced by a weight vector
w:

k
X
i=1

Ai → R, where w :

k
X
i=1

ai,ji 7→

k
X

wi,ji

i=1

for some (w1 , w2 , . . . , wk ) ∈ Rm1 × Rm2 × · · · × Rmk . In [Stu94] a regular mixed
subdivision (RMS) is also called a coherent mixed decomposition.
Theorem 2.15. [Stu94, Theorem 5.1] For a subdivision ∆ of Cay(A), the collection
Sk
Pk
of mixed cells of the form i=1 Ci such that Ci ⊆ Ai and i=1 Ci is a maximal cell
P
of ∆ forms a mixed subdivision of ki=1 Ai . This gives a one-to-one correspondence
Pk
between the regular subdivisions of Cay(A) and RMSs of i=1 Ai . Moreover the

12

ANDERS JENSEN AND JOSEPHINE YU

partition of weight vectors (w1 , w2 , . . . , wk ) ∈ Rm1 × Rm2 × · · · × Rmk according to
the induced RMS coincides with the secondary fan of Cay(A).
From our description of tropical resultants, we get the following result which was
proven for the resultant hypersurfaces in [Stu94, Theorem 5.2] and stated for the
essential configurations with no repeated points in [DFS07, Proposition 6.8]. See
Remark 2.25 for a definition of essential.
Theorem 2.16. The tropical resultant is a subfan of the secondary fan of the Cayley configuration Cay(A1 , A2 , . . . , Ak ), consisting of the cones whose corresponding
mixed subdivision contains a fully mixed cell.
The multiplicities of secondary cones in the tropical resultant will be computed
in Proposition 2.20 below.
Proof. For a tropical polynomial F ∈ RA the tropical solution set T (F ) is dual to
the cells with at least two elements in the subdivision of A induced by the coefficients
of F . More precisely, by the definition of tropical solution sets, w ∈ T (F ) if
and only if (1, w) is an inner-normal vector for the convex hull of lifted points
{(c, a) ∈ Rn+1 : c ⊙ xa is a term in F } supporting at least two points of A. The
two points supported need not have distinct coordinates a.
Let (F1 , F2 , . . . , Fk ) ∈ RA1 × RA2 × · · · × RAk . The union of tropical solution sets
Sk
i=1 T (Fi ) inherits a polyhedral complex structure from the common refinement
of the completions of T (Fi ) to Rm , which is dual to the RMS of A induced by the
coefficients of (F1 , F2 , . . . , Fk ). The tuple (F1 , F2 , . . . , Fk ) is in the tropical resultant
if and only if the tropical solution sets have a common intersection, which holds if
and only if there is a fully mixed cell in the dual RMS.

The tropical resultant is a subfan of the secondary fan. It is pure and connected
in codimension one, so we can compute it by traversing, as in [BJS+ 07]. To traverse
the resultant fan, we need to know how to find the link of the fan at a cone.
Proposition 2.17. Let A = (A1 , A2 , . . . , Ak ). The support of the link at a point
ω of the tropical resultant T R(A) is a union of tropical resultants corresponding to
sub-configurations of fully mixed cells in the RMS ∆ω of A induced by ω.
Proof. By definition, a point u is in the link if and only if ω + εu induces a RMS
with a fully mixed cell for all sufficient small ε > 0. This happens if and only if at
least one of the fully mixed cells in ∆ω is subdivided by u into a RMS with a fully
mixed cell, i.e. u is in the tropical resultant of the sub-configurations of fully mixed
cells.

Example 2.18. Let A be as in Example 2.10.
(a) The link at the point (0, 0, 0, 0, 1, 5, 0, 1, 5) of the tropical resultant is a
union of two hyperplanes whose normal vectors are:
(0, −1, 1, −1, 1, 0, 1, −1, 0) and (0, 0, 0, 0, 1, −1, 0, −1, 1)
respectively. They are the resultant varieties of the sub-configurations of
the two fully mixed cells in Figure 1.
(b) The link at the point (0, 0, 0, 0, −1, −1, 0, 0, 1) consists of four rays modulo
lineality space. Figure 2 shows the induced mixed subdivision, which contains two fully mixed cells. The resultant of one fully mixed cell consists

COMPUTING TROPICAL RESULTANTS

13

(0,0) (1,0)
(-1,0)
(1,-1)

(2,-3)

Figure 2. The tropical solution sets at (0, 0, 0, 0, −1, −1, 0, 0, 1)
and the corresponding dual RMS in Example 2.18(b).
of three rays (modulo lineality), and the resultant of the other fully mixed
cell consists of two rays. They overlap along a common ray.
The following lemma follows immediately from the definition of induced or regular subdivisions and shows that the description of the tropical resultant as a union
of cones in Theorem 2.9 is somewhat compatible with the secondary fan structure.
For any tuple E = (E1 , E2 , . . . , Ek ) of pairs Ei ⊂ Ai , let CE := R≥0 {eij : aij ∈
/
Ei } + rowspace(Cay(A)) be the cone as in Theorem 2.9.
Lemma 2.19. For each tuple E as above, the cone CE is a union of secondary
Pk
cones of Cay(A) corresponding to mixed subdivisions of
i=1 Ai having a mixed
Pk
cell containing i=1 Ei .

Let σ be a secondary cone of Cay(A) which is a maximal cone in the tropical
resultant T R(A), and let ∆σ be the corresponding regular mixed subdivision. Then
P
all the fully mixed cells in ∆σ are of the form ki=1 Ei where each E is a tuple of
pairs as above. Otherwise σ is not maximal in T R(A).

Proposition 2.20. The multiplicity of the tropical resultant T R(A) at a secondary
cone σ of Cay(A) is the sum of multiplicities of cones CE (given in Theorem 2.9)
over all tuples E of pairs forming a mixed cells in ∆σ .
Proof. By Lemma 2.19, for each tuple E of pairs, the cone CE contains σ if and
P
only if ki=1 Ei is a mixed cell in ∆σ . Otherwise CE is disjoint from the interior of
σ. The multiplicity of σ is the sum of multiplicities of CE ’s containing σ.

The edges of the resultant polytope are normal to the maximal cones in the
tropical resultant, and Proposition 2.20 can be used to find the lengths of the edges.
From this description, one can derive Sturmfels’ formula [Stu94, Theorem 2.1] for
the vertices of the resultant polytope.
2.3. Tropical description of secondary polytopes. We will give a tropical
description of secondary polytopes of arbitrary point configurations and show how
tropical resultants fit in.

14

ANDERS JENSEN AND JOSEPHINE YU

22

12

23
11

21
13

Figure 3. A projective drawing of the tropical hypersurface of
the secondary polytope of the Cayley configuration of two 1dimensional configurations in Example 2.22. The tropical resultant is shown in color (or in bold). A vertex labeled ij represents
the vector eij in R6 = RA1 × RA2 , and an edge between ij and kl
represents the cone R≥0 {eij , ekl } + rowspace(Cay(A)). Compare
with dual pictures in [Stu94, Figure 2] and [EFK10, Figure 3].
Proposition 2.21. Let A be a d × m integer matrix whose columns affinely span
an r-dimensional space. The tropical hypersurface of the secondary polytope of the
columns of A is the set
[
R≥0 {ei : i ∈
/ I} + rowspace(A) + R{1}.
I⊂{1,...,m}
|I|=r+2

where

1 denotes the all-ones vector in Rm .

Proof. Let ω ∈ Rm , and let ∆ω be the regular subdivision of the columns of A
induced by ω. The weight vector ω is not in the tropical hypersurface of the
secondary polytope if and only if ∆ω is not a triangulation, which happens if and
only if there exists a maximal cell of ∆ω containing at least r +2 points of A. For an
r + 2-subset I of {1, . . . , m}, the cone R≥0 {ei : i ∈
/ I} + rowspace(A)+ R{1} consists
of all ω such that a cell of ∆ω contains I. Note that rowspace(A) + R{1} consists
precisely of the weight vectors that induce the trivial subdivision of A where there
is a single maximal cell and all points are marked.

Comparing with Theorem 2.9, we see that in the tropical description of the
secondary polytope of Cay(A), the tropical resultant of A is the union of the cones
corresponding to the I’s with two points from each Ai .
Example 2.22. Let A1 = A2 = {0, 1, 2} in Z. For A = (A1 , A2 ), the tropical
hypersurface of the secondary polytope of Cay(A) and the tropical resultant of A are
depicted as graphs in Figure 3. The resultant polytope has f-vector (6, 11, 7, 1). The
secondary polytope in this case is combinatorially equivalent to the 3-dimensional
associahedron and has f-vector (14, 21, 9, 1). The first entry, the number of vertices
of the polytope, is the number of connected components in the complement of the
graph (the tropical hypersurface). The third entry, the number of facets of the
polytope, can be seen as the number of crossings in this case.

COMPUTING TROPICAL RESULTANTS

15

2.4. Codimension of the resultant variety. In this section we discuss how to
determine the codimension of the tropical resultant variety T R(A). By the Bieri–
Groves Theorem [BG84] this is also the codimension of R(A).
Theorem 2.23. The codimension of the tropical resultant equals
k
X
conv(Ei ))
k − MaxE dim(
i=1

where each Ei runs through all cardinality two subsets of Ai .
Proof. The tropical resultant variety is the collection of all lifts of all points in
A which give a fully mixed cell in the subdivision. Therefore it is the closure
of the collection of lifts which give a zonotope in the mixed subdivision being a
sum of convex hull of two points from each Ai . Let P be such a zonotope and
E = (E1 , . . . , Ek ) the k pairs of points. We wish to find the dimension of the
(relatively open) cone CP of lifts which induces P . The height of the first point of
each Ei may be chosen freely. The remaining k points of E must be lifted to the
same subspace of dimension dim(P ), whose lift may be chosen with dim(P ) degrees
of freedom. Finally, the height of the points not in E maybe chosen generically as
long as sufficiently large. The codimension of CP is therefore k − dim(P ). The
theorem follows since there are only finitely many choices for E.

Lemma 2.24. Let Li denote the subspace affinely spanned by Ai . The codimension
of R(A) only depends on the Li ’s and equals
k − Maxv∈Qi Li dim(span(v1 , . . . , vk )).
Proof. Since conv(Ei ) ⊆ Li the quantity of the lemma is smaller
Q than or equal to
that of Theorem 2.23. Conversely, if we have a collection v ∈ i Li we now show
how we can perform a sequence of changes to v to make it only consist of vectors vi
which are each differences between points of Ai without lowering the dimension of
span(v1 , . . . , vk ). Consider a vector vi . It is a linear combination of some uj where
each uj is of the form ais − ait . If all uj belong to W := span(v1 , . . . , vbi , . . . , vk )
then so will vi and it may be substituted by an arbitrary uj without lowering the
dimension. If some uj does not belong to W then substituting uj for vi will not
lower the dimension.

The proof also shows that instead of considering all line segments in Theorem 2.23
it suffices to consider only a basis for the affine span for each Ai . This is useful
while computing the codimension with this formula.
Remark 2.25. We can define a matroid on a set of polytopes as follows. A
set of polytopes is independent if they contain independent line segments. It is
straightforward to check that the base exchange axiom holds. The rank of the
matroid is the maximal dimension of a fully mixed cell (a zonotope) spanned by two
element subsets, one subset from each polytope. The codimension of the tropical
resultant equals the corank of the matroid, i.e. the number of polytopes minus
the largest dimension of such a zonotope. The (tropical) resultant variety is a
hypersurface if and only if the matroid has corank one, which holds if and only if
there is a unique circuit in the matroid. The tuple A is essential [Stu94] if and only
if this matroid of k polytopes is uniform of rank k − 1, that is, the unique circuit
of the matroid consists of the entire ground set.

16

ANDERS JENSEN AND JOSEPHINE YU

Using Theorem 2.23, we get a new proof of Sturmfels’ formula for the codimension of R(A). Recall that Qi is the convex hull of Ai .
Theorem 2.26. [Stu94, Theorem 1.1] The codimension of the resultant variety
P
Qk
R(A) in i=1 (C∗ )mi is the maximum of the numbers |I| − dim( i∈I Qi ) where I
runs over all subsets of {1, . . . , k}.

By the Bieri–Groves Theorem [BG84] and Theorem 2.4, the codimension of
Theorem 2.23 equals that of Theorem 2.26. In the following we explain how the
equality of the two combinatorial quantities of Theorems 2.23 and 2.26 can also be
seen as a consequence of Perfect’s generalization (Theorem 2.27) of Hall’s marriage
theorem and Rado’s theorem on independent transversals.
Let S be the ground set of a matroid with rank function ρ. Let U = {Si : 1 ≤
i ≤ k} be a family of subsets of S. A subset S ′ of S is called an independent
partial transversal of U if S ′ is independent and there exists an injection θ : S ′ →
{1, 2, . . . , k} with s ∈ Sθ(s) for each s ∈ S ′ .
Theorem 2.27. (Perfect’s Theorem [Per69, Theorem 2]) With the notation above,
for every positive integer d, the family U has an independent partial transversal of
cardinality d if and only if
d ≤ ρ(∪i∈I Si ) + k − |I|
for every I ⊆ {1, 2, . . . , k}.
In particular, the maximum cardinality of an independent partial transversal is
equal to the minimum of the numbers on the RHS of the inequality.
S
Proof of Theorem 2.26. Let Si = {a−b : a, b ∈ Ai }, S = ki=1 Si , and U = {Si : 1 ≤
i ≤ k}. Consider the vector matroid on S given by linear independence. Then the
Pk
quantity MaxE dim( i=1 conv(Ei )) is the cardinality of the maximal independent
partial transversal of U. By Perfect’s Theorem,
k
X
X
conv(Ei )) = MinI⊆{1,2,...,k} dim(
Qi ) + k − |I|.
MaxE dim(
i=1

i∈I

Hence the two quantities from Theorems 2.23 and 2.26 are equal.



Straightforward evaluation of the formulas in Theorems 2.23 and 2.26 will require time complexity exponential in the input. Moreover, the maximal bipartite
matching problem is a special case of this codimension problem.
Lemma 2.28. The maximal bipartite matching problem is reducible in polynomial
time to the problem of computing codimension of resultants.
Proof. Let G be a bipartite graph with vertices U ⊔ V and edges E ⊂ U × V . Let
{eu : u ∈ U } be the standard basis for RU . For each v ∈ V , let Av = {eu : (v, u) ∈
E}. Then the maximal cardinality of a bipartite matching in G is equal to the
dimension of the resultant variety of A = ({0} ∪ Av : v ∈ V ), and the size of A is
polynomial in the size of G.

We use Theorem 2.23 to construct an efficient algorithm for computing the codimension of a resultant.
Theorem 2.29. The codimension of the resultant can be computed in polynomial
time in the size of the input.

COMPUTING TROPICAL RESULTANTS

17

Proof. Let A = (A1 , A2 , . . . , Ak ) where each Ai is a point configuration in Zn . By
Lemma 2.24, the codimension of R(A) depends only on the linear spaces L1 , L2 , . . . ,
Lk affinely spanned by A1 , A2 , . . . , Ak respectively. Choose a basis Bi for each linear
Sk
space Li . Let B = {B1 , B2 , . . . , Bk } and S = i=1 Bi . A subset S ′ of S is called a
partial transversal of B if there is an injection θ : S ′ → {1, 2, . . . , k} with s ∈ Bθ(s) .
The collection of partial transversals form an independent system of a matroid M1
on ground set S, called the transversal matroid of B. Let M2 be the vector matroid
on S defined by linear independence. By Theorem 2.23, computing the codimension
of the resultant is equivalent to computing the maximum cardinality of a linearly
independent partial transversal, i.e. the largest subset of S which is independent in
both M1 and M2 .
We can use the cardinality matroid intersection algorithm [Sch03, Section 41.2]
to find the maximum cardinality of a set independent in two matroids on the same
ground set. This algorithm is polynomial in the size of S and the time for testing
independence in the matroids. Testing independence in M1 can be reduced to the
maximal bipartite matching problem and can be solved in polynomial time. Testing
linear independence in M2 can be reduced to finding the rank of a matrix, which
also takes polynomial time.

Alternatively, in the proof above, we can take S to be the disjoint union of
B1 , B2 , . . . , Bk , then the transversal matroid M1 can be replaced by the partition
matroid. This was done in [DGH98] to prove that whether a mixed volume is
zero can be decided in polynomial time. This problem reduces to the codimension
problem by observing that for a tuple A = (A1 , A2 , . . . , An ) of point configurations
in Zn , the mixed volume of the convex hulls of A1 , A2 , . . . , An is non-zero if and
only if the codimension of R(A) is zero, by Bernstein’s Theorem.
The algorithm described in Theorem 2.29 is rather complex, but there is a simpler
probabilistic or numerical algorithm. For generic vectors vi ∈ Li for i = 1, 2, . . . , k,
the codimension of the resultant is equal to k − rank([v1 |v2 | · · · |vk ]). The challenge
of turning this into a deterministic algorithm lies in making sure that the choices for
vi are generic. Our naive attempts at symbolic perturbations resulted in matrices
whose ranks cannot be computed in polynomial time.
The polynomial time algorithm of Theorem 2.29 can be used for finding a generic
point in T R(A) in polynomial time. Simply remove points from A as long as the
dimension does not drop. When we can no longer remove points, we have exactly
two points left from each configuration of A. We then compute a generic point in
T R(A) using Theorem 2.9, possibly using a symbolic ε. It is unclear if a polynomial
time algorithm exists for finding a generic point in specialized tropical resultants
that we will see in Section 3.
2.5. Traversing tropical resultants. Tropical resultants are pure and connected
in codimension 1. This allows the facets (maximal faces) to be enumerated via the
well-known adjacency decomposition approach. By this we mean traversing the
connected bipartite graph encoding the facet-ridge incidences of the fan. Three
operations are essential. We must be able to find some maximal cone in the fan,
find the link at a ridge, and compute an adjacent maximal cone given a ray of
the link at the ridge. In [Jen10] these subcomputations were isolated in an oracle,
and the author discussed a general algorithm for traversing a polyhedral fan (up
to symmetry) represented only through oracle calls. In the following paragraphs

18

ANDERS JENSEN AND JOSEPHINE YU

we will describe how to walk locally in the tropical resultant. More details can
be found in the next section for the more general setting of specialized tropical
resultant.
To find a starting cone for the traversal, we use the description of the tropical
resultant as a union of orthants plus a linear space, as described in Theorem 2.9.
Alternatively, a generic vector in a maximal cone of a resultant fan can be found
in polynomial time using the algorithms for the codimension, as noted at the end
of Section 2.4.
To find ridges, we compute facets of maximal cones. To find the link of the
tropical resultant at a point, we use the fact that the link at a point ω is a union
of smaller tropical resultants associated to the fully mixed cells in the mixed subdivision of A induced by ω, as shown in Proposition 2.17.
In the tropical resultant, as a subfan of the secondary fan of Cay(A), each cone
can be represented by a regular subdivision of Cay(A). The smallest secondary
cone containing a given vector ω can be constructed from the regular subdivision
induced by ω as explained in [DLRS10, Section 5.2].
In our implementation we represent the regular subdivision ∆ induced by ω by ω
and the triangulation induced by a “placing” or “lexicographic” perturbation of ω.
From this triangulation, we can easily recover the subdivision ∆ by comparing the
normal vectors of the maximal cells of the triangulation lifted by ω. For this to work,
it is important to perturb ω in such a way that all the marked points in ∆ remain
marked in the refined triangulation. A full triangulation of Cay(A) is computed
from scratch only once at the beginning. There are standard methods for computing
a placing triangulation of any point configuration; see [DLRS10, Section 8.2.1]. To
obtain a desired triangulation from a known triangulation, we find a path in the
flip graph of regular triangulations and perform flips as in [DLRS10, Section 8.3.1].
This is the analogue of a Gröbner walk in the setting of secondary fans.
To find the secondary cone in the link at u given by a ray v, we compute the
subdivision induced by u + εv for sufficiently small ε > 0. Such a vector u + εv is
represented symbolically in a way similar to a matrix term order in the theory of
Gröbner bases.
3. Resultants with specialized coefficients
For some applications such as implicitization we need to compute resultant varieties while specializing some of the coefficients. This problem was studied in
[EKP07, EFKP11] for the case when the resultant variety is a hypersurface. In
that case, the Newton polytope of the specialized resultant is the projection of the
resultant polytope, and the authors computed the projection of resultant polytopes
using Sturmfels’ formula for vertices of resultant polytopes [Stu94, Theorem 2.1]
and beneath-beyond or gift-wrapping methods for computing convex hulls. In our
language, computing a projection of a polytope is equivalent to computing the
restriction of the normal fan to a subspace.
In tropical geometry, specialization of certain coefficients amounts to taking the
stable intersection of the tropical resultant with certain coordinate hyperplanes.
In this section we first define the specialized tropical resultants and then present
algorithms for computing them.
A polyhedral complex in Rn is called locally balanced if it is pure dimensional
and the link at every codimension one face positively spans a linear subspace of Rn .

COMPUTING TROPICAL RESULTANTS

19

Definition 3.1. Let F1 and F2 be locally balanced fans in Rn . We define the
stable intersection as the fan
F1 ∩st F2 := {C1 ∩ C2 :(C1 , C2 ) ∈ F1 × F2 and
supp(linkC1 (F1 )) − supp(linkC2 (F2 )) = Rn }
with support
supp(F1 ∩st F2 ) = {ω ∈ Rn : supp(linkω (F1 )) − supp(linkω (F2 )) = Rn }.
If in addition F1 and F2 are balanced then the stable intersection inherits multiplicities from linkω (F1 ) and linkω (F2 ) as follows:
multω (F1 ∩st F2 ) :=
X

multC1 (linkω F1 ) · multC2 (linkω F2 ) · [Zn : (Zn ∩ RC1 ) + (Zn ∩ RC2 )]

C1 ,C2

where the sum runs over C1 ∈ linkω (F1 ) and C2 ∈ linkω (F2 ) such that ω ′ ∈ C1 −C2
for a fixed generic vector ω ′ ∈ Rn .
Notice that the support of F1 ∩st F2 depends only on supp(F1 ) and supp(F2 ).
We will therefore extend the definition of stable intersections to intersections of
supports of locally balanced fans and regard them as subsets of Rn .
For proofs of the following six statements, of which some are known to the
community already, we refer to the upcoming paper [JY].
Orthogonally projecting a polytope onto a linear space is equivalent to stably
intersecting the tropical hypersurface of the polytope with the linear space. This
is consistent with the fact that the Newton polytope of the specialized resultant is
a projection of the resultant polytope onto a suitable coordinate subspace.
Theorem 3.2. Let P ⊂ Rn be a polytope, L ⊂ Rn be a linear subspace, and
π : Rn → L be the orthogonal projection. Then
T (π(P )) = (T (P ) ∩st L) + L⊥ .
Lemma 3.3. For any locally balanced fans F1 , F2 , and F3 , we have
(1) (F1 ∩st F2 ) ∩st F3 = F1 ∩st (F2 ∩st F3 )
(2) (supp(F1 ) ∪ supp(F2 )) ∩st supp(F3 ) = supp(F1 ∩st F3 ) ∪ supp(F2 ∩st F3 ).
Lemma 3.4. For locally balanced fans F1 and F2
[
supp(F1 ∩st F2 ) =

C1 ∩ C2 .

C1 ∈F1 ,C2 ∈F2
codim(C1 +C2 )=0

Corollary 3.5. For locally balanced fans F1 and F2
linkω (F1 ) ∩st linkω (F2 ) = linkω (F1 ∩st F2 ).
Proposition 3.6. The stable intersection of two locally balanced fans is either
empty or a locally balanced fan whose codimension is the sum of the codimensions.
Lemma 3.7. Let I be an ideal in k[x1 , x2 , . . . , xn ]. Then
supp(T (I)) ∩st {x : x1 = 0} = supp(T (hIi + hx1 − αi))
where hIi is the ideal in k(α)[x1 , x2 , . . . , xn ] generated by I.

20

ANDERS JENSEN AND JOSEPHINE YU

Definition 3.8. Let S = (S1 , . . . , Sk ) where each Si ⊆ {1, . . . , mi } represent a
choice of points in the configuration A. The coefficients of the monomials indexed
by S are called specialized. Let Ui := {x ∈ Rmi : xj = 0 for all ∀j ∈ Si } and
Qk
US := i=1 Ui . We define the specialized tropical resultant as
T RS (A) := T R(A) ∩st {US }.

We will use the following proposition to justify the word “specialized.” Let I be
the ideal of R(A) and J be a new ideal generated by I together with the binomials
cj − γj for specialized coefficients cj , where γj ’s are parameters. We define the
Qk
specialized resultant variety RS (A) := V (J) ⊆ i=1 (K ∗ )mi as the variety defined
by J where K is the field of rational functions in γj ’s with coefficients in C.
When all the containments Si ⊂ {1, . . . , mi } are strict, i.e. not all coefficients are
specialized in any of the polynomials fi , then the variety RS (A) is irreducible. To
see this, consider the specialized incidence variety WS cut out by the polynomials
f1 , . . . , fk with some, but not all, coefficients specialized in each fi . For a fixed
x ∈ (C∗ )n each fi gives an affine constraint on the the non-specialized coefficients
in fi . Such constraints are solvable since each xj 6= 0 and they are simultaneously
solvable since they concern different sets of coefficients. Hence WS is a vector bundle
over (C∗ )n and is irreducible. Therefore its projection RS (A) is also irreducible.
In general, for a prime ideal I ⊂ k[x1 , . . . , xn ], with k algebraically closed, and
a generic α, specializing a variable x1 to α may not preserve primality, i.e. the
ideal I1 := I + hx1 − αi ⊆ k(α)[x1 , . . . , xn ] need not be prime. However, all
its irreducible components have the same tropical variety. To see this, note that
T (I1 ) = {0}1 × T (I2 ) where I2 := I ⊆ k(x1 )[x2 , . . . , xn ]. The ideal I3 := I ⊆
k(x1 )[x2 , . . . , xn ] is prime because I remains prime under extension from k[x1 ] to
k(x1 ), as primality is preserved under localization. Deciding whether a point is in a
tropical variety can be done with reduced Gröbner bases which are independent of
the field extension, so we have {0}1 × T (I3 ) = {0}1 × T (I2 ) = T (I1 ). Furthermore,
since I1 is prime, by [CP13, Proposition 4], all irreducible components of I2 have
the same tropicalization. Since the tropical varieties of the irreducible components
of I3 are the same as those of the irreducible components of I2 , the conclusion
follows.
Proposition 3.9. The tropicalization of RS (A) is T RS (A).
Proof. The statement follows from Lemmas 3.7 and 3.3(1).



The computation of the tropicalization of RS (A) can be performed using Buchberger’s algorithm as explained in [BJS+ 07] over the field of rational functions in
the γj ’s. During this computation finitely many polynomials in the γj ’s appear
as numerators and denominators of the coefficients. Substituting constant values
for the γj ’s will give the same computation unless one of these polynomials vanish. Hence specializing γj ’s to values outside a hypersurface in (C∗ )S will lead to a
specialized tropical resultant variety. This explains the word “specialized.”
If T RS (A) is nonempty, then its codimension can be computed using Proposition 3.6 and the codimension formulas from Section 2.4. Thus it remains to give
P an
algorithm for checking if the specialized resultant is empty. Recall that m := i mi
is the total number of points in A.
Lemma 3.10. Let A and S be as in Definition 3.8. Define the extended tuple
B = (B1 , . . . , Bk ) where Bi consists of bi,j = (ai,j , vi,j ) ∈ Zn × Zm−|S| , with vi,j ∈

COMPUTING TROPICAL RESULTANTS

21

Zm−|S| being 0 if j ∈ Si and a standard basis vector otherwise. If the standard
vector is chosen differently for every non-specialized coefficient then
T RS (A) 6= ∅ ⇔ T R(B) = Rm .
Proof. According to Lemma 3.4, T RS (A) 6= ∅ if and only if there exists a cone
C ⊆ T R(A) such that US + C = Rm where US is as in Definition 3.8. According
to the simple description of tropical resultants in Theorem 2.9 we may assume that
C has the form R≥0 {eij : aij ∈
/ Ei } + rowspace(Cay(A)). Equivalently, the stable
intersection is nonempty if and only if there exists a choice E such that R≥0 {eij :
aij ∈
/ Ei } + rowspace(Cay(A)) + US has dimension m. Applying Theorem 2.9 to B,
this is equivalent to T R(B) being full dimensional, since rowspace(Cay(A)) + US =
rowspace(Cay(B)).

Combining Lemma 3.10 and the results from Section 2.4 about computation of
codimension, we get a polynomial time algorithm for deciding if a specialized result
is nonempty. Another consequence of the lemma is the following algorithm for
checking membership of a point in a specialized tropical resultant.
Algorithm 3.11. (SpecializedResultantContains(A, S, ω))
Input: A tuple A of point configurations and a choice S of specialized coefficients.
A vector ω ∈ Rm .
Output: “True” if ω ∈ T RS (A), “False” otherwise.
• Compute the mixed subdivision of A induced by ω by computing the regular
subdivision of Cay(A) induced by ω. (See Section 2.5).
• For each fully mixed cell:
– construct a subconfiguration A′ of points involved in the cell.
– Return “True” if the specialized resultant of A′ is nonempty.
• Return “False”.
Proof. By Lemma 3.3(2), Proposition 2.17 and Corollary 3.5, we have that the support of linkω (T RS (A)) is the union of supports of T RS (A′ ), under the appropriate
identification of T RS (A′ ) as a subset of Rm , where A′ runs over all fully mixed
cells of the mixed subdivision of A induced by ω. Hence ω ∈ T RS (A) if and only
if one of T RS (A′ ) is nonempty.

Algorithm 3.12. (NonTrivialVectorInSpecializedResultant(A, S))
Input: A tuple A of configurations, a choice S of specialized coefficients such that
US ∩ rowspace(Cay(A)) ( T RS (A).
Output: A vector ω ∈ T RS (A) \ rowspace(Cay(A))
• For each E = (E1 , E2 , . . . , Ek ) : Ei is a two-element subset of Ai ,
– Let C = R≥0 {ei,j : i ∈
/ Ej } + rowspace(Cay(A)).
– If codim(C + US ) = 0 and US ∩ C 6= US ∩ rowspace(Cay(A)) then
∗ Find among the generators of US ∩ C a vector v outside the
subspace US ∩ rowspace(Cay(A)).
∗ Return v.
The following recursive algorithm finds a perturbed point in a starting cone for
the specialized tropical resultant T RS (A).
Algorithm 3.13. (StartingPoint(A, S))
Input: A tuple A of configurations, a choice S of specialized coefficients such that

22

ANDERS JENSEN AND JOSEPHINE YU

T RS (A) 6= ∅.
Output: A vector ωε ∈ Q(ε)m such that for every fan structure of T RS (A) defined
over Q it holds that for ε > 0 sufficiently small, ωε is in a maximal cone of T RS (A).
• If dim(T RS (A)) = dim(US ∩ rowspace(Cay(A))), then return b1 + εb2 +
· · · + εt−1 bt where b1 , b2 , . . . , bt is some basis of US ∩ rowspace(Cay(A)).
• Compute an ω ∈ T RS (A) \ rowspace(Cay(A)) using Algorithm 3.12.
• Compute the subdivision ∆ω of Cay(A) induced by ω.
• For every fully mixed cell in ∆ω .
– Let A′ be the subconfiguration of the involved points.
– Let S ′ be the restriction of S to A′ .
– If codimension(T RS ′ (A′ )) = codimension(T RS (A)) then
∗ Return ω + ε · StartingPoint(A′ , S ′ ).
Proof. The correctness of the algorithm follows from the facts that the link at ω
of the tropical resultant is the union of tropical resultants corresponding to the
fully mixed cells in ∆ω (Proposition 2.17), that taking links commutes with taking
stable intersections (Corollary 3.5), and that the returned value from the recursive
call (after expansion with zeros) is a generic vector in the link of T RS (A) at ω and
in particular lies outside the secondary cone of ω.

We now turn to the problem of enumerating all maximal cones in T RS (A)
considered as a subfan of the restriction of the secondary fan of Cay(A) to the
subspace US . While connectedness in codimension 1 is not preserved under stable
intersections in general, a specialized tropical resultant T RS (A) is connected in
codimension 1 because it coincides with the tropical variety of a prime ideal, as
shown in the paragraph above Proposition 3.9. The proof in [BJS+ 07] that the
tropical varieties of prime ideals are connected in codimension 1 contained some
mistakes, which were later corrected in [CP13].
The output of Algorithm 3.13 can be converted into a secondary cone in T R(A)
containing ωε in its relative interior, for example by computing a maximal secondary
cone containing ωε and taking the face containing ωε in its relative interior. For
sufficiently small ε > 0, this secondary cone would not change with ε.
Following the approach of [Jen10] discussed in Section 2.5, we are left with the
problem of computing the link at a ridge in T RS (A). If the subspace US is generic
enough such that
codim(US ∩ rowspace(Cay(A)) = codim(US ) + codim(rowspace(Cay(A))),
then the link of T RS (A) is combinatorially equivalent to the link of T R(A) and
the support of the link is a union of resultant fans of subconfigurations (Proposition 2.17) where each fan can be found using Theorem 2.9. If US is not generic,
then computing a stable intersection with US is required for finding the link in
T RS (A) (Corollary 3.5). This is Algorithm 3.14 below. Recall that the dimension
of T RS (A) = T R(A) ∩st {US } can be computed using Proposition 3.6 and the
codimension formulas from Section 2.4.
Algorithm 3.14. StableLink(A, S, ω)
Input: A tuple A of configurations, a choice S of specialized coefficients, a vector
ω ∈ Rn in the relative interior of a ridge R of T RS (A).
Output: A vector in each facet of linkω (T RS (A)).
• Let d be the dimension of T R(A) ∩st {US }.

COMPUTING TROPICAL RESULTANTS

23

• Compute the subdivision ∆ω of Cay(A) induced by ω.
• l := ∅.
• For every fully mixed cell in ∆ω
– Let A′ be the subconfiguration of involved points in the cell.
– For each E = (E1 , E2 , . . . , Ek ) : Ei is a two-element subset of A′i ,
∗ Let C = R≥0 {ei,j : i ∈
/ Ej } + rowspace(Cay(A)).
∗ If dim(US + C) = m and dim(US ∩ C) = d then
· Let V be a set of one or two vectors in US ∩ C such that
(US ∩ C) + span(R) is positively spanned by V ∪ span(R).
· l := l ∪ V
• Return l.
Another approach to computing a link at a point of the stable intersection is to
compute the restriction of the secondary fan of each fully mixed subconfiguration
to US . We then get the resultant fan as certain rays of the secondary fan. This is
Algorithm 3.15.
Algorithm 3.15. StableLink(A, S, ω)
Input: A tuple A of configurations, a choice S of specialized coefficients, a vector
ω ∈ Rn in the relative interior of a ridge R of T RS (A).
Output: A vector in each facet of linkω (T RS (A)).
• Let d be the dimension of T R(A) ∩st {US }.
• Compute the subdivision ∆ω of Cay(A) induced by ω.
• l := ∅.
• For every fully mixed cell in ∆ω
– Let A′ be the subconfiguration of the involved points of the cell.
– If the codimension of the lineality space of the restriction F of the
secondary fan of Cay(A′ ) to US is m − d, then
∗ Choose v such that v extends span(R) ∩ US to a generating set
of the lineality space of F .
∗ If SpecializedResultantContains(A′ , S, v) then l := l ∪ {v, −v}.
– else
∗ Compute all maximal cones in F (by traversal).
∗ For each ray v in F , if SpecializedResultantContains(A′ , S, v)
then l := l ∪ {v}.
• Return l.
The above algorithm is to be read with proper identifications. Namely, when
restricting to A′ the vectors in Rm need to be truncated accordingly, and so does
the set S, and v needs to be expanded when adding it to l. When adding vectors
to l, it is advantageous to choose the vectors as primitive vectors orthogonal to the
span of the ridge so that duplicates can be removed easily.
If US is of high dimension, a typical situation is that each subconfiguration
is a number of edges and a triangle. In this case there are only few choices E
to run through in Algorithm 3.14. For lower dimensional US there can be many
choices of E but with many of the contributions to the stable intersection being
the same. See Example 3.16. In such a case Algorithm 3.15 performs better than
Algorithm 3.14. In general it is difficult to predict which algorithms is better. In
our implementation we use mostly Algorithm 3.15, and Algorithm 3.14 only when
there is no specialization.

24

ANDERS JENSEN AND JOSEPHINE YU

Example 3.16. Let A = (A1 , A2 , A3 ) with
A1 = {(0, 0), (0, 1), (0, 3), (1, 0), (3, 0)}
A2 = {(0, 0), (0, 1), (0, 3), (1, 0), (3, 0)}
A3 = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (3, 1), (3, 3)}.
Choosing the specialization S of every coefficient except the coefficient of the point
(0, 0) in each configuration, we get that T RS (A) is a two-dimensional fan with
f-vector (1, 13, 17) living inside R3 ⊆ R18 . The link at e11 ∈ R18 consists of 4 rays.
The traversal of T RS (A) takes 79 seconds if Algorithm 3.14 is used but only 5
seconds if Algorithm 3.15 is used for computing the links. Algorithm 3.14 needs
to iterate through 2100 vertex pair choices at e11 , but much fewer for many of the
other links.
3.1. Implicitization using specialized resultants. In this section we will show
that the tropicalization of a variety parameterized by polynomials with generic coefficients can be computed using specialized tropical resultants. Let f1 , f2 , . . . , fk ∈
±1
±1
k
C[x±1
1 , x2 , . . . , xn ] be polynomials parameterizing a variety X in C . Let Γ be
the graph of the parameterizing map, defined by hy1 − f1 , y2 − f2 , . . . , yk − fk i in
±1
±1
C[x±1
1 , x2 , . . . , xn , y1 , y2 , . . . , yk ]. When f1 , f2 , . . . , fk have generic coefficients,
the tropical variety of Γ is the stable intersection of the tropical hypersurfaces of
the polynomials y1 − f1 , y2 − f2 , . . . , yk − fk . Since X is the closure of the projection of Γ ⊂ (C∗ )n × Ck onto Ck , by tropical elimination theory, we can compute
the tropical variety T (X) as a projection of T (Γ). This approach was used in
[STY07, SY08].
Another way to compute T (X) is by using specialized resultants. Let A =
(A1 , A2 , . . . , Ak ) where Ai = supp(fi ) ⊔ {0} for each i = 1, 2, . . . , k. Let S =
(supp(f1 ), supp(f2 ), . . . , supp(fk )) be the sets of points to specialize, and let VS be
Qk
the subspace of i=1 RAi × Rn defined by setting the coordinates in S to 0.

Proposition 3.17. With the notation above, T (X) = T RS (A), i.e. the tropicalization of a variety parameterized by polynomials with generic coefficients coincides
with a specialized resultant.
Q
Proof. Let W be the incidence variety in ki=1 (C∗ )Ai × (C∗ )n as in (1), defined by
equations of the form yi − gi where gi is a polynomial with the same support as fi
but with indeterminate coefficients. Then the graph Γ is obtained by specializing
the coefficients of gi to those of fi . Since the coefficients of fi were assumed to be
generic, we get T (Γ) = T (W ) ∩st VS . By tropical elimination, T (X) + ({0} × Rn) =
Qk
T (Γ) + ({0} × Rn ) in Rk × Rn , which is in turn embedded in i=1 RAi × Rn . By
the following lemma, T (Γ) + ({0} × Rn ) = (T (W ) + ({0} × Rn )) ∩st VS . After
quotienting out both sides by {0} × Rn , which is in the lineality space, we obtain
T (X) = T RS (A).

Lemma 3.18. Let F be a locally balanced fan in RN . Let L and L′ be linear
subspaces of RN such that L′ ⊂ L. Then
(F ∩st L) + L′ = (F + L′ ) ∩st L
In other words, stable intersection with a linear space commutes with Minkowski
sum with a smaller linear space.

COMPUTING TROPICAL RESULTANTS

25

Proof. Both (F ∩st L) + L′ and (F + L′ ) ∩st L are empty if F + L has dimension less
than N . Suppose this is not the case. Then both sets contain L′ in their lineality
space and consist of points of the form u + v ∈ RN where u ∈ L′ and v ∈ F ∩ L are
such that dim(linkv (F ) + L) = N .

Since the tropical variety of the graph Γ only depends on the extreme monomials
of the parameterizing polynomials, the next result follows immediately.
Corollary 3.19. When using specialized resultants for implicitization, the extreme
monomials of the input polynomials determine the tropical variety of the parameterized variety, so we can safely disregard the non-extreme terms.
Using specialized resultants for implicitization instead of the approach in [STY07,
SY08] has the advantage that the computation of T (Γ) as a stable intersection can
be avoided. Experiments show that the resultant description may speed up the
reconstruction of the Newton polytope in some cases. See Section 5 for examples.
Moreover, when the variety X is not a hypersurface, our resultant description
gives a fan structure of T (X) derived from the restriction of a secondary fan to a
linear subspace, which is the normal fan of a fiber polytope. Tropical elimination
does not give a fan structure for varieties of codimension more than one.
3.2. Tropical elimination for specialized tropical resultants. As before, let
A be a tuple of point configurations in Zn and S be the tuple of subsets to be
specialized. Let W be the incidence variety and T W be is tropicalization as in
Section 2.1. Let WS be a variety cut out by polynomials fi where the coefficients
of monomials in S have been specialized. Then f1 , f2 , . . . , fk may no longer form a
tropical basis, but the tropicalization of WS can be computed as the stable intersection of tropical hypersurfaces of f1 , f2 , . . . , fk because the coefficients are assumed
to be generic (or indeterminates). The incidence variety W is irreducible because it
is a vector bundle over (C∗ )n , and although specializing coefficients may make WS
reducible, all the irreducible components have the same tropical variety as seen in
the paragraph above Proposition 3.9. Hence any stable intersection of tropical hypersurfaces is connected in codimension 1, and we can use fan traversal to compute
the stable intersection of hypersurfaces.
The specialized resultant is the projection of WS onto the non-specialized coefficient variables, and we can compute this using tropical elimination theory, which
gives the tropical variety as a union of cones. When the specialized tropical resultant is a tropical hypersurface, then we can reconstruct the normal fan of the dual
Newton polytope using the methods in the next section.
The tropical hypersurface of fi only depends on the Newton polytope Pi of fi .
The non-specialized points in Ai always contribute as vertices of Pi , but some
specialized points of Ai may not. From this observation, we obtain the following
result, which is not obvious from the resultant point of view.
Lemma 3.20. If aij ∈ Ai is a specialized point lying in the convex hull of other
specialized points in Ai , then removing aij from Ai does not change the specialized
tropical resultant.
In other words, we may disregard the non-vertices among the specialized points
because the Newton polytope and the tropical hypersurface of fi remain the same.
Using this lemma, we may be able to reduce the amount of work for computing
specialized tropical resultants or specialized resultant polytopes.

26

ANDERS JENSEN AND JOSEPHINE YU

4. Polytope reconstruction
In this section we describe an algorithm for finding a fan structure on a tropical
hypersurface T ⊆ Rn . Recall that the tropical hypersurface of a polytope P ⊂ Rn
is the set of ω ∈ Rn for which there exist distinct p, q ∈ P such that for any r ∈ P ,
ω · p = ω · q ≤ ω · r. In other words, the tropical hypersurface of a polytope is
the union of the normal cones to the polytope at the edges. The multiplicity of
a point in the relative interior of such a normal cone is the (lattice) length of the
edge. The tropical hypersurface of a polynomial is the tropical hypersurface of its
Newton polytope.
The tropical hypersurface T will be presented to us as a finite collection of codimension 1 cones which may overlap badly but whose union is T . What we wish
to compute is a collection of codimension 1 cones such that the collection of all
their faces is a polyhedral fan with support T . This fan is not unique unless we
require it to be the coarsest — that is, that it is the normal fan of the polytope
defining T with its maximal cones removed. If the codimension 1 cones come with
a multiplicity then an advantage of having the fan structure is that it is straightforward to reconstruct the 1-skeleton of the polytope defining T , hence the vertices
of the polytope, up to translation. Therefore we will consider the computations of
the vertices of a polytope, the normal fan, and the tropical hypersurface with the
coarsest fan structure to be equivalent in what follows.
One way to perform the polytope reconstruction is to use the beneath-beyond
method for computing convex hulls. The key observation is that for any generic
ω ∈ Rn the vertex faceω (New(f )) can be computed using “ray shooting.” See
[DFS07] and [CTY10]. The method we present in this paper uses the adjacency
decomposition approach (see Section 2.5) and the following algorithm for computing
normal cones at vertices of the polytope defining T .
Algorithm 4.1 (Region(S,ω)).
Input: A collection S of codimension 1 cones in Rn such that T := ∪C∈S C is the
support of a tropical hypersurface. A vector ω ∈ Rn \ T .
Output: The (open) connected component of R \ T containing ω.
• R := Rn .
• For each C ∈ S:
– While R ∩ C 6= ∅:
∗ Find a point p ∈ R ∩ C.
∗ Introduce the parameter
P ε > 0 and let h be the open half line
from ω through p + ni=1 εi ei .
∗ The set of cones which intersect h is the same for all ε > 0
sufficiently small. Furthermore, the ordering of the intersection
points along h is fixed for ε > 0 sufficiently small. Among the
cones that intersect h, let D be a cone whose intersection point is
closest to ω. (The choice of D is not unique because the cones in
S need not form a fan and may overlap each other arbitrarily).
∗ Let the halfspace H ⊂ Rn be the connected component of Rn \
span(D) containing ω.
∗ R := R ∩ H.
• Return R.

COMPUTING TROPICAL RESULTANTS

27

Proof. The set R stays open and convex throughout the computation. At the
end R ∩ T = ∅. Each added constraint H for R is necessarily satisfied by the
connected component because of its convexity. The symbolic perturbation of p and
the convexity of R ensures that H is independent of the choice of D, as all the
possible choices of cones must be parallel. In fact, the set of constraints gives an
irredundant inequality description of the returned cone.

In computational geometry a standard way of handling the parameter ε > 0 is to
pass to the ordered field R(ε). Since perturbed values are never multiplied together,
there is no exponent growth. Indeed, the implementation is relatively simple.
Proposition 4.2. Let a be the number of facets of the closure of the returned cone
of Algorithm 4.1. The number of checks “R ∩ C 6= ∅” performed in algorithm is
|S| + a while the number of interior point computations “p ∈ R ∩ C” is a.
Proof. The check is done for every cone in C ∈ S. In addition, whenever the
algorithm enters the body of the while loop, a facet constraint H is added to R,
and an additional check “R ∩ C 6= ∅” and a computation of p is performed.

The condition that the generic h intersects a given polyhedral cone C can be
phrased as a condition on the ordering in which h intersects the defining hyperplanes
of C. We can imagine moving a point starting from ω and along the half-line
h, keeping track of which equations and inequalities defining C are satisfied and
updating when a defining hyperplane of C is crossed. Hence the implementation
reduces to a check of the order in which h intersects two given hyperplanes. The
perturbation in such a check is not difficult to handle symbolically. The check can
be used again to actually find a D in the algorithm with intersection point closest
to ω.
To apply the adjacency decomposition approach we must be able to compute a
starting cone and move across ridges to find neighboring cones, while computing
links at ridges is trivial for complete fans. To find a starting cone we guess a vector
outside T and apply Algorithm 4.1. Suppose now that C is a full dimensional cone
in the normal fan and u is a relative interior point on a facet of C with outer
normal vector v. For ε > 0 sufficiently small, calling Algorithm 4.1 with argument
u + εv will give us the desired neighboring cone. In our implementation we again
use comparison of intersection points on line segments to find an ε sufficiently small
to avoid all hyperplanes appearing in the description of T .
If we precompute generators for the cones in S then most of the checks for empty
intersection with R can be done without using linear programming, but rather
for each defining hyperplane of R checking if the cone generators are completely
contained on the wrong side. In our current implementation the time spent on
finding first intersections along the half-lines is comparable to the time spent on
linear programming. We present two examples to illustrate the usability of our
algorithm. These examples appeared earlier in the literature.
Example 4.3. The f-vector of the tropical hypersurface of the 2 × 2 × 2 × 2 hyperdeterminant was computed in [HSYY08]. The support of the hypersurface is the
sum of a tropical linear space and a classical linear space in R16 and is easy to write
as a union of cones. We reconstruct the 25448 normal cones of the Newton polytope of the defining equation in 163 minutes. Exploiting the 384 order symmetry
as explained in [Jen10] we reduce the running time to 7 minutes for computing the

28

ANDERS JENSEN AND JOSEPHINE YU

111 orbits of maximal cones. With suitable input files the following Gfan command
[Jen] will compute the f-vector. See also Section 5 for further details.
anders@gureko:~$ gfan_tropicalhypersurfacereconstruction -i troplinspc.fan
--sum --symmetry <claslinspc_and_symmetry.txt | grep -A1 F_VECTOR
F_VECTOR
1 268 5012 39680 176604 495936 927244 1176976 1005946 555280 178780 25448

Example 4.4. The implicitization challenge solved in [CTY10] is to reconstruct
the Newton polytope of the defining equation of a tropical variety given as a union
of 6865824 cones. This 11-dimensional polytope lives in R16 and has a symmetry
group of order 384. Its vertices come in 44938 orbits. In [CTY10], a modified
version of the ray-shooting method was used to produce coordinates of the vertices
at a rate of a few (2-5) minutes per vertex. Each round took about 45 minutes
found 10-20 vertices typically. However, a lot more computation, with some human
interaction and parallelization, over a period of a few months was required to make
sure that all the vertices were discovered, and this was done by computing the
tangent cone at each found vertex, up to symmetry. During the process most
vertices were re-discovered multiple times.
On this example our new implementation in Gfan spends approximately 1 minute
for each call of Algorithm 4.1. We estimate that the enumeration of the 44938 orbits
would finish after 30 days of computation. With the new method, we do not need to
process a vertex more than once, and we obtain all the facet directions as the rays
in the normal fan and all the tangent cones as duals of the normal cones. Moreover,
there is no post-processing needed to certify that all vertices have been found.
The method we just described does not make use of multiplicities. In fact, it is
not necessary that the fan is polytopal, or even locally balanced. We only require
that each connected component of the complement of T is convex.
Before settling with Algorithm 4.1 we also experimented with storing the codimension one cones in a binary space partitioning tree (BSP tree). See [TN87] for
a definition of BSP trees and an application to a computational geometry problem in arbitrary dimension. The tree would be built at initialization, and the
connected components of the complement could be computed by gathering convex
regions stored in the tree. This method worked as well as Algorithm 4.1 in small
dimensions, but in higher dimensions, like the examples above, Algorithm 4.1 would
always perform better. In Example 4.3 the difference would be a factor of five without exploiting symmetry. But in Example 4.4 the number of required nodes of the
tree would grow too large to have any chance of fitting in memory. The intuition
behind the explosion in complexity is that cones (for example, simplicial cones of
codimension one) in a higher dimensional space have larger chances of intersecting
a fixed hyperplane. Therefore in the process of building the BSP tree, a codimension one cone from the input will meet many other hyperplanes coming from other
cones, causing an explosion in the number of nodes in the BSP tree.
5. Comparison of algorithms
In this section, we consider various algorithms and compare the combinatorial
complexity of the output (e.g. f-vector) and running time (recorded on a laptop
computer with a 2.66 GHz Intel Core i5 processor and 8GB of memory). All implementations are single threaded, done in C++ using cddlib [Fuk05] and SoPlex
[Wun96], and will be part of Gfan in its next release, unless otherwise noted. The

COMPUTING TROPICAL RESULTANTS

29

combinatorial complexity of the output is essential for a fair comparison since different amounts of effort went into making each of the implementations fast. We
mostly concentrated on the implementation of Algorithm 4.1 and the secondary fan
computation because of their broad range of applications, while less optimization
effort has gone into algorithms specific to tropical resultants.
In general, the software Gfan uses the max convention for tropical varieties and
Gröbner fans. However, for the fact that the secondary fan of a point configuration
is a coarsening of the Gröbner fan of the associated binomial (lattice) ideal, we need
the subdivisions to be defined with respect to min if the initial ideals are defined
with respect to max. Therefore Gfan uses min for secondary fans. As tropical
resultants are subfans of secondary fans, we chose to use min in this paper for
tropical addition.
Hypersurfaces. Let us first consider the case where the resultant variety R(A) is
a hypersurface. Following is a list of different methods for computing the resultant
polytope (or its tropical hypersurface or its normal fan).
(1) Enumerating the vertices of the secondary polytope of Cay(A), and then
using Sturmfels’ formula [Stu94, Theorem 2.1] to obtain the vertices of the
resultant polytope. We did not make an implementation but list only the
time spent computing the secondary fan with the Gfan command
gfan_secondaryfan <cayley.txt

(2) Computing the tropical hypersurface of the resultant as a subfan of the
secondary fan by fan traversal using the methods described in Section 2.5.
gfan_resultantfan --vectorinput <tuple.txt

(3) Constructing the normal fan of the resultant polytope from the simple
description of the tropical resultant as a union of cones as in Theorem 2.9.
Our implementation in Gfan uses Algorithm 4.1 for this.
gfan_resultantfan --vectorinput --projection <tuple.txt

(4) Using Sturmfels’ formula [Stu94, Theorem 2.1] for finding the optimal
vertex of the resultant polytope in a generic direction together with the
beneath-beyond convex hull algorithm for recovering the whole polytope.
The software ResPol [EFKP11] is a recent implementation of this method
using the CGAL library.
For the third approach, one can also use other methods for reconstructing a
polytope from its tropical hypersurface, such as ray-shooting/beneath-beyond and
BSP trees, as discussed in Section 4, although we found Algorithm 4.1 to perform
better, especially for polytopes of dimension 5 or more (compared to beneathbeyond in iB4e [Hug06] and BSP).
For Example 2.10 above, each of the first three methods finished in under one
second in Gfan. We present more challenging examples below. In the examples
each matrix represents the point configuration consisting of its columns.
Example (a).


0
A = 0
1

 
1 3
0 0
0 1, 0 2
1 1
3 2

 
1
0 2
1, 2 1
0
3 1

 
2
1
2, 2
1
1


2 2
0 3 
0 2

30

ANDERS JENSEN AND JOSEPHINE YU

Method/fan
(1) secondary fan
(2) traversing tropical resultant
(3) normal fan from simple description
(4) beneath-beyond (ResPol)

Example (b).


0 0
A=
0 1

Method/fan
(1) secondary fan
(2) tropical resultant
(3) normal fan
(4) beneath-beyond (ResPol)

Example (c).

1
1

A=
3
1

2
2
1
2

 
1
2
1
3
, 
2 0
3
2

F-vector of output
1 10432 55277 106216 88509 27140
1 5152 21406 28777 12614
1 78 348 570 391 93
1 - - - - 93

 
1 3
1 2
,
2 0
1 2

3
0

 
3
0
,
1
1

1 2
1 0

Timing
467 s
733 s
1.4 s
2.7 s


3
3

F-vector of output
1 3048 38348 178426 407991 494017 304433 75283
1 2324 26316 106083 197576 173689 58451
1 56 497 1779 3191 3018 1412 249
1 - - - - - - 249

3
2
1
3

Method/fan
(3) normal fan from simple descr.
(4) beneath-beyond (ResPol)

 
0
3
2
2
, 
3 2
1
1

2
0
3
3

 
1
2
2
2
, 
0  0
0
0

1
3
1
3

 
1
3
3
3
, 
0  1
3
2

F-vector of output
1 937 5257 11288 11572 5589 985
1 - - - - - 985

3
2
1
0

Timing
55 s
236 s

Timing
506 s
1238 s
6s
35 s


3

2

2
2

In Example (c) we were not able to compute the secondary fan and the resultant fan
with the secondary fan structure due to integer overflow in intermediate polyhedral
computations. Gfan has been designed to work well for Gröbner fans, where the
degrees of the polynomials are never very large, since that would prevent us from
computing a single Gröbner basis anyway (except for binomial ideals). In Example
(c), a primitive normal vector of a codimension 1 cone of the normal fan of the resultant is (−32, 0, 32, 27, 0, −27, 25, −25, 0, 0, 51, −51, −87, 0, 87), showing that the
resultant has degree at least 32+27+25+51+87=222. On such examples overflows
typically arise when trying to convert an exactly computed rational generator of a
ray to a primitive vector of 32-bit integers. Algorithm 4.1 will show similar behavior
on other examples, for example when converting “p ∈ R ∩ C” to a vector of 32-bit
integers. We intend to fix these implementation problems in the future.
Hypersurfaces with Specialization. If the specialized resultant is a hypersurface, then we can compute its tropical variety using the following methods.
(1) Compute T RS (A) as a subfan of the restriction of the secondary fan to a
subspace US by fan traversal using the algorithms in Section 3.
gfan_resultantfan --vectorinput --special <tuple_and_spcvec.txt

(2) Compute the stable intersection T RS (A) = T R(A) ∩st {US } as a union of
cones, using the simple description from Theorem 2.9 and the characterization of stable intersections from Lemma 3.4. Then reconstruct the normal
fan of the dual polytope using Algorithm 4.1.
gfan_resultantfan --vectorinput --special --projection <tup_and_sv.txt

(3) Compute the specialized tropical resultant as a union of cones using stable intersection of hypersurfaces and tropical elimination theory as in Section 3.2 and reconstruct the normal fan of the dual polytope using Algorithm 4.1. We combine the commands (see also [SY08]):

COMPUTING TROPICAL RESULTANTS

31

gfan_tropicalstartingcone --stable >startingcone.txt
gfan_tropicaltraverse --stable <startingcone.txt >stable.fan
gfan_tropicalhypersurfacereconstruction --sum -i stable.fan <lnspc.txt

(4) For a generic direction, Sturmfels’ formula [Stu94, Theorem 2.1] gives the
optimal vertex of the resultant polytope in that direction, which can then be
projected to get a point in the Newton polytope of the specialized resultant
polynomial. This can be combined with the beneath-beyond convex hull
algorithm for recovering the whole polytope. The software ResPol was used
in the timings below.
In [EKP07], the authors proposed computing a silhouette or a projection of the
secondary polytope. This is dual to computing the restriction of the secondary fan
to a subspace. We provide the results and timings of this dual computation for
comparison.
In the following examples specialized points are shown in non-black color.
Example (d).
 
 


0 1 1 2
0 0 1 1
0 1 1 2
,
,
A=
0 1 0 1
1 0 1 2
0 1 2 1
Method/fan
Restriction of secondary fan
(1) traversing tropical resultant
(2) normal fan from stable intersection
(3) normal fan from tropical elimination
(4) beneath-beyond (ResPol)

Example (e).
A=


0 0
0 1

 
0 1
1 1
,
0 1
1 0

Method/fan
Restriction of secondary fan
(1) traversing tropical resultant
(2) normal fan from stbl. inters.
(3) normal fan from trop. elim.
(4) beneath-beyond (ResPol)

Example (f ).

1 1 2
A = 2 2 3
0 2 1
Method
(2)
(3)

F-vector
1 372 2514 5829 5661 1976
1 126 476 561 212
1 25 127 250 211 65
1 25 127 250 211 65
1 - - - - 65

 
3
0
2, 1
2
0

1
1

 
2
0
,
2
0

1 1
1 2

F-vector
1 709 6955 24354 39464 30226 8870
1 469 3993 11296 12853 5040
1 29 209 597 792 485 110
1 29 209 597 792 485 110
1 - - - - - 110

0 1
2 1
2 1

 
1
1 1
1, 1 3
3
1 1

Timing
26 s
14 s
0.7 s
1.4 s
0.5 s


2
1
Timing
116 s
320 s
1.3 s
3.2 s
2.3 s

 
2 3
1 1
3 2, 0 2
0 1
3 2

F-vector
1 1566 19510 98143 265202 424620 413455 238425 73741 9156
1 1566 19510 98143 265202 424620 413455 238425 73741 9156


3 3
0 1 
1 1

Timing
798 s
974 s

The current version of ResPol could not complete the computation for this example.
Furthermore, we could not apply method (1) because of 32-bit integer overflows as
explained in Example (c).
Implicitization of hypersurfaces. Implicitization is a special case of the specialized resultants, and we compare the three methods as before.
Example (g). (Implicitization of a bicubic surface [EK05, Example 3.4])

 

0 0 0 0 1 2 3
0 0 0 1 2 3
,
A=
,
0 1 2 3 0 0 0
0 1 3 0 0 0

32

ANDERS JENSEN AND JOSEPHINE YU


0
0

0 0
1 2

1 1
0 1

Method/fan
Restriction of secondary fan
(1) traversing tropical resultant
(2) normal fan from stable inters.
(3) normal fan from tropical elim.
(4) beneath-beyond (ResPol)

1 1
2 3

2 2
0 1

F-vector
1 26 66 42
1 13 17
1596
1596
1596

2
2

Timing
5s
16 s
171 s
0.4 s
< 0.1 s

2 3
3 1

3 3
2 3



No interior points
2s
4s
9s
0.4 s
< 0.1 s

As we saw in Corollary 3.19, removing the non-extreme monomials from the parameterizing polynomials does not change the resultant polytope, and in this example,
this also does not change the restriction of the secondary fan. However, doing so
speeds up the computations, as seen on the right most column.
Example (h). (Implicitization of a hypersurface in four dimensions)
 
 
 


0 1 2 3
0 2 3 4
0 0 4 4
0 0 2 4
A = 0 2 4 1, 0 2 2 0, 0 4 0 1, 0 2 2 3
0 2 4 1
0 1 4 1
0 2 4 2
0 4 2 3
Method/fan
(1) traversing tropical resultant
(2) normal fan from stable intersection
(3) normal fan from tropical elimination
(4) beneath-beyond (ResPol)

F-vector
1 10665 24204 13660
1 111 358 368 121
1 111 358 368 121
1 111 358 368 121

Timing
2 h 10 m
9s
2.6 s
1.5 s

For (3), computing the polytope from the tropical hypersurface using ray-shooting
and beneath-beyond took 47 s in the TrIm implementation [SY08] using the library
iB4e [Hug06] on a slightly slower machine.
Example (i). (Implicitization of a hypersurface in five dimensions)


0
0


A = 
0
0

1
1
2
2

3
4
2
4

 
0
4

4
, 0
4 0
0
0

0
0
1
1

1
2
1
2

Method/fan
(2) normal fan from stable inters.
(3) normal fan from tropical elim.
(4) beneath-beyond (ResPol)

 
0
3

3
, 0
3 0
3
0

0
1
1
4

2
4
1
2

 
0
3

2
, 0
1 0
3
0

1
1
0
1

 
0
3

2
, 0
0 0
3
0

2
4
1
3

F-vector
1 5932 23850 35116 22289 5093
1 5932 23850 35116 22289 5093
1 5932 23850 35116 22289 5093

0
4
3
1

2
1
4
3


4

3

3
1

Timing
351 s
184 s
898 s

For (3), timing includes 17 seconds for computing the specialized tropical incidence
variety. The normal fan reconstruction computation in TrIm with iB4e took 3375
seconds on a slightly slower machine.
Non-hypersurfaces. When R(A) is not a hypersurface, the only method we know
for computing T R(A) with a fan structure without knowing the defining ideal is
to traverse the secondary fan of Cay(A) and enumerating just the secondary cones
whose RMS contains a fully mixed cell. There are other descriptions of tropical
resultants as a set, such as Theorem 2.9, but none gives a fan structure.
Example (j).

 
 
 

0 2 4
3 5 5
3 4 5
0 1 2
A=
,
,
,
4 1 1
1 0 4
1 5 2
4 3 5
Method/fan
Secondary fan
Traversing tropical result.

F-vector
1 8876 72744 222108 322303 225040 60977
1 968 4495 6523 3000

Timing
478 s
81 s

COMPUTING TROPICAL RESULTANTS

33

We used, respectively, the commands:
gfan_secondaryfan <cayley.txt
gfan_resultantfan --vectorinput <tuple.txt

Non-hypersurfaces with Specialization. The only method here is to traverse
T RS (A) as a subfan of a restriction of the secondary fan using the algorithms in
Section 3.
Example (k).
 
 
 


0 2 4
3 5 5
3 4 5
0 1 2
,
,
,
A=
4 1 1
1 0 4
1 5 2
4 3 5
Method/fan
Restriction of secondary fan
Traversing spec. tropical result.

F-vector
1 4257 23969 48507 42260 13467
1 310 831 533

Timing
256 s
81 s

We used, respectively, the commands:
gfan_secondaryfan --restrictingfan subspace.fan <cayley.txt
gfan_resultantfan --vectorinput --special <tup_and_sv.txt

5.1. Conclusion. The new method of using adjacency decomposition with Algorithm 4.1 for constructing the normal fan of a polytope from it tropical hypersurface
works very well in practice. Our implementation is much faster than any existing
implementation of the beneath-beyond method with ray-shooting for polytope reconstruction, and we think the gap will widen even more in higher dimension since
this new method scales well — multi-linearly with respect to the number of cones
in input and the number of vertices and edges of the output polytope, as shown in
Proposition 4.2.
The normal fan reconstruction method can be used together with either the
simple description of tropical resultants (Theorem 2.9) or tropical elimination (Section 3.2) for computing resultant polytopes efficiently. Traversing the (specialized)
tropical resultant as a subfan of (a restriction of) the secondary fan of the Cayley
configuration is combinatorially interesting but not computationally competitive.
For implicitization, the beneath-beyond method from [EFKP11] works faster
than any of our “tropical” methods when the output polytope is low dimensional,
while our methods seem to have an advantage in higher dimension (5 or more).
However, the method of [EFKP11] may have an advantage when there are many
specialized points in the input configurations, as the number of cones in the tropical
description increases rapidly. See the last problem in Section 6 below.
For resultant varieties of codimension higher than one, whether specialized or
not, we only know of one method for computing the tropicalization as a fan, without
knowing the defining polynomials, which is to traverse the secondary fan of the
Cayley configuration or a restriction of it to a subspace.
6. Open problems
Combinatorial classification of resultant polytopes: For 1-dimensional
point configurations, the combinatorics of the resultant polytope only depend on the (partial) order of the (not necessarily distinct) points in each Ai
[GKZ94], so a combinatorial classification is easy to obtain. No such classification is known even for point configurations in Z2 . A concrete problem is
to classify 4-dimensional resultant polytopes combinatorially. This
was done for 3-dimensional resultant polytopes by Sturmfels [Stu94], and

34

ANDERS JENSEN AND JOSEPHINE YU

only one-dimensional point configurations were needed for this case. To
understand the 4-dimensional resultant polytopes, we need to work with
the case A = (A1 , A2 , A3 ) where each Ai consists of three points in Z2 that
are not necessarily distinct. How can we stratify the space of tuples A’s
according to the combinatorial type of the resultant polytope?
Using symbolic perturbation: At the end of Section 2.4, we gave a probabilistic algorithm for computing codimension of resultants. Can we turn
this into a polynomial time deterministic algorithm using symbolic perturbation?
Finding a point in the specialized tropical resultant: For non-specialized
tropical resultants, the polynomial time algorithm for computing codimension from Section 2.4 can also be used to find a generic point, by Theorem 2.9. Is there a polynomial time algorithm for finding a generic vector
ω ∈ Q(ε)m in the specialized tropical resultant?
Improved description of specialized tropical resultants: By combining
the descriptions of tropical resultants in Theorem 2.9 and stable intersections in Lemma 3.4, we get a specialized tropical resultant as a union of
Qk
cones. In computations, we need to go through a list of i=1 m2i choices
of tuples of pairs from Ai , many of which do not contribute to a facet of
specialized tropical resultant. Give a combinatorial characterization
for the choices of the tuples of pairs that contribute to a facet.
Corollary 3.19 and Lemma 3.20 are results in this direction.
Acknowledgments
We thank MSRI (Berkeley, USA) and Institut Mittag-Leffler (Djursholm, Sweden) for their support and hospitality. The first author was partially supported
by the German Research Foundation (Deutsche Forschungsgemeinschaft (DFG))
through the Institutional Strategy of the University of Göttingen, partially by the
DFG grant MA 4797/3-1 (SPP 1489) and partially by the Danish Council for Independent Research, Natural Sciences (FNU). The second author was partially
supported by a Postdoctoral Research Fellowship and DMS grant #1101289 from
the National Science Foundation (USA). We would like to express our gratitude to
the anonymous referees, especially Reviewer #1, for exceptionally careful reading
and detailed comments.
References
[BG84]

Robert Bieri and J. R. J. Groves, The geometry of the set of characters induced by
valuations, J. Reine Angew. Math. 347 (1984), 168–195. MR 733052 (86c:14001)
[BJS+ 07] T. Bogart, A. N. Jensen, D. Speyer, B. Sturmfels, and R. R. Thomas, Computing
tropical varieties, J. Symbolic Comput. 42 (2007), no. 1-2, 54–73. MR 2284285
(2007j:14103)
[CP13]
Dustin Cartwright and Sam Payne, Connectivity of tropicalizations, Mathematical
Research Letters 19 (2013), no. 5.
[CTY10] Marı́a Angélica Cueto, Enrique A. Tobis, and Josephine Yu, An implicitization challenge for binary factor analysis, J. Symbolic Comput. 45 (2010), no. 12, 1296–1315.
MR 2733380
[DFS07] Alicia Dickenstein, Eva Maria Feichtner, and Bernd Sturmfels, Tropical discriminants, J. Amer. Math. Soc. 20 (2007), no. 4, 1111–1133 (electronic). MR 2328718
(2008j:14095)

COMPUTING TROPICAL RESULTANTS

[DGH98]

[DLRS10]

[EFK10]

[EFKP11]

[EK05]

[EKP07]
[Fuk05]

[GKZ94]

[HSYY08]

[Hug06]

[Jen]
[Jen10]
[JMM08]

[JY]
[MS]

[Oda08]
[Per69]
[Rin]
[Sch03]
[ST08]
[Stu94]
[STY07]

35

Martin Dyer, Peter Gritzmann, and Alexander Hufnagel, On the complexity of computing mixed volumes, SIAM J. Comput. 27 (1998), no. 2, 356–400. MR 1616544
(99f:68092)
Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms
and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010, Structures
for algorithms and applications. MR 2743368
Ioannis Z. Emiris, Vissarion Fisikopoulos, and Christos Konaxis, Regular triangulations
and resultant polytopes, In Proceedings of European Workshop on Computational Geometry (EuroCG) (Dortmund, Germany), 2010, pp. 137–140.
Ioannis Z. Emiris, Vissarion Fisikopoulos, Christos Konaxis, and Luis Peñaranda, Efficient computation of Newton polytopes of specialized resultants, arXiv:1108.5985v1,
2011.
Ioannis Z. Emiris and Ilias S. Kotsireas, Implicitization exploiting sparseness, Geometric and algorithmic aspects of computer-aided design and manufacturing (Ravi
Janardan, Michiel Smid, and Debasis Dutta, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 67, Amer. Math. Soc., Providence, RI, 2005, pp. 281–297.
MR 2200413 (2006j:65028)
Ioannis Z. Emiris, Christos Konaxis, and Leonidas Palios, Computing the newton polytope of specialized resultants, Proceeding of the MEGA 2007 conference, 2007.
Komei Fukuda, cddlib reference manual, cddlib version 094b, Swiss Federal Institute of Technology, Lausanne and Zürich, Switzerland, 2005,
http://www.inf.ethz.ch/personal/fukudak/cdd_home/.
I. M. Gel′ fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants,
and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser
Boston Inc., Boston, MA, 1994. MR 1264417 (95e:14045)
Peter Huggins, Bernd Sturmfels, Josephine Yu, and Debbie S. Yuster, The hyperdeterminant and triangulations of the 4-cube, Math. Comp. 77 (2008), no. 263, 1653–1679.
MR 2398786 (2009c:52021)
Peter Huggins, ib4e: A software framework for parametrizing specialized lp problems,
Mathematical Software – ICMS 2006, Lecture Notes in Computer Science, vol. 4151,
Springer, 2006, pp. 245–247.
Anders N. Jensen, Gfan, a software system for Gröbner fans and tropical varieties,
Available at http://home.imf.au.dk/jensen/software/gfan/gfan.html.
, Traversing symmetric polyhedral fans, Proceedings of the International Congress on Mathematical Software (Kobe, Japan, 2010), 2010.
Anders Nedergaard Jensen, Hannah Markwig, and Thomas Markwig, An algorithm
for lifting points in a tropical variety, Collect. Math. 59 (2008), no. 2, 129–165.
MR 2414142 (2009a:14077)
Anders N. Jensen and Josephine Yu, Stable intersection of tropical varieties, in preparation.
Diane
Maclagan
and
Bernd
Sturmfels,
Introduction
to
tropical
geometry,
book
draft
available
at
http://homepages.warwick.ac.uk/staff/D.Maclagan/papers/papers.html.
Shinsuke Odagiri, The tropical resultant, Proc. Japan Acad. Ser. A Math. Sci. 84
(2008), no. 7, 93–96. MR 2450058 (2009i:14075)
Hazel Perfect, A generalization of Rado’s theorem on independent transversals, Proc.
Cambridge Philos. Soc. 66 (1969), 513–515. MR 0244065 (39 #5382)
Felipe Rincón, Computing tropical linear spaces, arXiv:1109.4130. To appear in Journal
of Symbolic Computation.
Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. B,
Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003.
Bernd Sturmfels and Jenia Tevelev, Elimination theory for tropical varieties, Math.
Res. Lett. 15 (2008), no. 3, 543–562. MR 2407231 (2009f:14124)
Bernd Sturmfels, On the Newton polytope of the resultant, J. Algebraic Combin. 3
(1994), no. 2, 207–236. MR 1268576 (95j:52024)
Bernd Sturmfels, Jenia Tevelev, and Josephine Yu, The Newton polytope of the implicit
equation, Mosc. Math. J. 7 (2007), no. 2, 327–346, 351. MR 2337885 (2008f:14073)

36

ANDERS JENSEN AND JOSEPHINE YU

[SY08]

[Tab08]
[TN87]
[Wun96]

Bernd Sturmfels and Josephine Yu, Tropical implicitization and mixed fiber polytopes, Software for algebraic geometry (Jan Verschelde, Michael Stillman, and Nobuki
Takayama, eds.), IMA Vol. Math. Appl., vol. 148, Springer, New York, 2008, pp. 111–
131. MR 2410718 (2009m:14089)
Luis Felipe Tabera, Tropical resultants for curves and stable intersection, Rev. Mat.
Iberoam. 24 (2008), no. 3, 941–961. MR 2490204 (2010b:14123)
William C. Thibault and Bruce F. Naylor, Set operations on polyhedra using binary
space partitioning trees, SIGGRAPH Comput. Graph. 21 (1987), no. 4, 153–162.
Roland
Wunderling,
Paralleler
und
objektorientierter
SimplexAlgorithmus,
Ph.D.
thesis,
Technische
Universität
Berlin,
1996,
http://www.zib.de/Publications/abstracts/TR-96-09/.

Institut for Matematik, Aarhus Universitet, Aarhus, Denmark
E-mail address: jensen@imf.au.dk
School of Mathematics, Georgia Institute of Technology, Atlanta GA, USA
E-mail address: jyu@math.gatech.edu

