arXiv:1612.01762v1 [math.AG] 6 Dec 2016

COMPUTING TROPICAL VARIETIES
OVER FIELDS WITH VALUATION
THOMAS MARKWIG AND YUE REN
Abstract. We show how tropical varieties of ideals I E K[x] over a field K
with non-trivial valuation can always be traced back to tropical varieties of ideals
π −1 I E RJtK[x] over some dense subring R in its ring of integers. Moreover, for
homogeneous ideals, we present algorithms on how the latter can be computed in
finite time, provided that π −1 I is generated by elements in R[t, x]. While doing
so, we also comment on the computation of the Gröbner polytope structure and
p-adic Gröbner bases using our framework.

1. Introduction
Tropical varieties are commonly described as combinatorial shadows of their algebraic counterparts, and computing tropical varieties is an algorithmically highly
challenging task, requiring sophisticated techniques from computer algebra and convex geometry.
The first techniques were developed by Bogart, Jensen, Speyer, Surmfels and Thomas
[BJS+ 07], who focused on homogeneous ideals over C with the trivial valuation,
which allowed them to rely on classical Gröbner basis methods. Furthermore, the
authors showed that, under sensible conditions, their techniques can be used over the
field of Puiseux series C{{t}} with its natural valuation, by regarding t as a variable
in the polynomial ring instead of a uniformizing parameter in the coefficient ring.
The inhomogeneity of the resulting ideal in C[t, x] can be worked around through
homogenization and dehomogenization. In order to adapt these techniques to the
field of p-adic numbers and the p-adic valuation, Chan and Maclagan adapted the
classical theory of Gröbner bases [ChM13] to take the valuation on the ground field
into account, instead of solely relying on monomial orderings.
In this article, in Section 2, we discuss another approach to compute tropical varieties
over an arbitrary field with valuation, which can be regarded as a generalisation of
Date: December, 2016.
1991 Mathematics Subject Classification. Primary 14T05, 13P10, 13F25, 16W60; Secondary
12J25, 16W60.
Key words and phrases. Tropical varieties, valued fields.
The author was supported by ...
1

2

THOMAS MARKWIG AND YUE REN

the trick used for C{{t}}. For that, we combine the existing notions of tropical varieties over power series [Tou05, BaT07, PPS13] with the concept of tropical varieties
over coefficient rings [MaS15, Section 1.6]. Compared to [ChM13], the approach relies on existing standard basis theory, which not only allows us to exploit the highly
optimized implementations that exist in many established computer algebra systems
such as Singular [DGPS16] or Macaulay2 [GrS16], it also gives us access to a
highly active field of research.
Moreover, in Section 3, we improve on the techniques in [BJS+ 07] by avoiding homogenization and dehomogenization. We also touch upon the topic on how to
compute p-adic Gröbner bases in our framework. In Section 4 we present the algorithms for computing tropical varieties and in Section 5 we touch upon possible
optimizations that are exclusive to non-trivial valuations.
All algorithms in this article are implemented in the Singular library tropical.lib
[JMMR16], relying on the gfanlib interface gfan.lib [Jen11, JRS16] for computations in convex geometry. They are publicly available as part of the official
Singular distribution.
2. Tracing tropical varieties to a trivial valuation
The aim of this section is to show how tropical varieties over valued fields can be
traced back to tropical varieties over integral power series. The linchpin of the
section is to show that initial ideals over valued fields can be described through
initial ideals over integral power series, the remaining results then follow naturally
from this. To fix the notation, we will begin by recalling some very basic notions in
tropical geometry that are of immediate relevance to us.
Convention 2.1
For the remainder of the article, fix a complete field K with non-trivial discrete
valuation ν : K → R ∪ {∞} and a uniformizing parameter p ∈ K. Let OK be its
ring of integers and let K denote its residue field. Let R ≤ OK be a dense, noetherian
subring. By Cohen’s Structure Theorem, we have two exact sequences
0

hp − ti · RJtKhp−ti

RJtKhp−ti

0

hp − ti · RJtK

RJtK

π
t 7−→ p

K

0,

OK

0.

Moreover, fix a multivariate polynomial ring K[x] = K[x1 , . . . , xn ]. By abuse of
notation, we will also use π to refer to both the map RJtK[x] → OK [x] as well as the
composition RJtK[x] → OK [x] ֒→ K[x].

COMPUTING TROPICAL VARIETIES

3

Example 2.2 (p-adic numbers)
The most important example is the field K := Qp of p-adic numbers with OK := Zp
the ring of p-adic integers. Then R := Z ≤ Zp is a natural dense subring, which is
computationally easy to work over. The exact sequences in Convention 2.1 merely
reflect the presentation of p-adic integers as power series in p:
0

hp − ti · ZJtKhp−ti [x]

ZJtKhp−ti [x]

0

hp − ti · ZJtK[x]

ZJtK[x]

π
t 7−→ p

Qp [x]

0,

Zp [x]

0.

Example 2.3
Given the choice of R ≤ OK in Convention 2.1, choosing R := OK is always possible.
However, in many examples there are natural choices for R, which are computationally much easier to handle than OK itself:

(1) K = k((t)) the field of Laurent series over a field k with OK = kJtK the ring of
power series over k, R = k[t] and p = t; e.g. k = Fq with q a prime power, as
used in [SpS04, Section 7] or [Kal13], or k = Q as considered in [BJS+ 07], see
Example 2.14.
(2) Finite extensions K of Qp and Fq ((t)), i.e. all local fields with non-trivial valuation, and also all higher dimensional local fields.
(3) OK any completion of a localization of a Dedekind domain R at a prime ideal
P E R, p ∈ P a suitable element. Note that p does not need to generate P and
hence OK need
with respect to the ideal generated by p,
√
√ not be the completion
e.g. R = Z[ −5], P = h2, 1 + −5i and p = 2.
(4) For an odd choice of R, consider K := Q(s)((t)) so that OK = Q(s)JtK. Set
R := S −1 Q[s, t], where S := Q[s, t] \ (ht − 1, si ∪ hxi) is multiplicatively closed as
the complement of two prime ideals. Then R is a non-catenarian, dense subring
of OK .
Definition 2.4 (initial forms, initial ideals, tropical varieties over valued fields)
P
For a polynomial f = α∈Nn cα · xα ∈ K[x] and a weight vector w ∈ Rn , we define
the initial form of f with respect to w to be:
X
inν,w (f ) :=
cα · p−ν(cα ) · xα ∈ K[x].
w·α−ν(cα )
maximal

For any subset I ⊆ K[x] and a weight vector w ∈ Rn , we define the initial ideal of
I with respect to w to be:
inν,w (I) := hinν,w (f ) | f ∈ Ii E K[x].

4

THOMAS MARKWIG AND YUE REN

We refer to the set of weight vectors for which the initial ideal contains no monomial
as the tropical variety of I,
Tν (I) := {w ∈ Rn | inν,w (I) monomial free} .
Theorem 2.5 ([MaS15, Theorem 3.3.5])
Let I E K[x] define an irreducible subvariety in (K ∗ )n of dimension d. Then Tν (I)
is the support of a pure polyhedral complex of same dimension that is connected in
codimension 1.
Next, we will introduce tropical varieties in RJtK[x], and show how a certain class
of them relates to tropical varieties in K[x]. In particular, we will note that those
tropical varieties in RJtK[x] are pure and connected in codimension 1. We begin by
introducing initial forms and initial ideals in RJtK[x] and show how they can be used
to describe their pendants in K[x].
Definition 2.6 (initial forms, initial ideals)
P
Given an element f = β,α cα,β · tβ xα E RJtK[x] and a weight vector w ∈ R<0 × Rn ,
we define the initial form of f with respect to w to be
X
inw (f ) :=
cα tβ xα ∈ R[t, x].
w·(β,α) maximal

Given an ideal I E RJtK[x] and a weight vector w ∈ R<0 × Rn , we define the initial
ideal of I with respect to w to be:
inw (J) := hinw (f ) | f ∈ Ji E R[t, x].
This can be thought of as a natural extension of Definition 2.4 with trivial valuation
on the coefficients. Note that we only allow weight vectors with negative weight in
t, so that our result lies in a polynomial ring.
Example 2.7 (p-adic numbers)
Let us consider the example in [Cha13, Chapter 3.6], the ideal
I = h2x21 + 3x1 x2 + 24x3 x4 , 8x31 + x2 x3 x4 + 18x23 x4 i E Q3 [x1 , . . . , x4 ]
over the 3-adic number Q3 , so that
π −1 I = h3 − t, 2x21 + 3x1 x2 + 24x3 x4 , 8x31 + x2 x3 x4 + 18x23 x4 i E ZJtK[x],
and the weight vector (−1, w) ∈ R<0 × R4 , w := (1, 11, 3, 19). A short computation
yields
in(−1,w) (π −1 I) = h3, x21 , tx1 x3 x4 , t3 x1 x22 x3 , t4 x1 x42 , t3 x43 x24 i,

COMPUTING TROPICAL VARIETIES

5

and the similarity to the initial ideal of I under the 3-adic valuation is no coincidence:
inν3 ,w (I) = hx21 , x1 x3 x4 , x1 x22 x3 , x1 x42 , x43 x24 i E F3 [x].
Proposition 2.8
For any ideal I E OK [x] and any weight vector w ∈ Rn , we have:
in(−1,w) (π −1 I)|t=1 = inν,w (I),
where (·) denotes the canonical projection (·) : R[x] → K[x].
P
Proof. ⊇: Any term s ∈ OK [x] is of the form s = ( β cβ pβ ) · xα with p ∤ cβ for all
P
β ∈ N. Then the element s′ := ( β cβ tβ ) · xα ∈ RJtK[x] is a natural preimage of it
under π for which we have
inν,w (s) = cβ0 · xα = in(−1,w) (s′ )|t=1 , where β0 = min{β ∈ N | cβ 6= 0}.
And because the valued weighted degree in OK [x] and the weighted degree in
RJtK[x] coincide,
P
P
degw (xα ) − val( β cβ pβ ) = deg(−1,w) ( β cβ · tβ xα ),
this implies any f ∈ OK [x] has a preimage f ′ ∈ RJtK[x] under π such that
inν,w (f ) = in(−1,w) (f ′)|t=1 ,
simply by applying the above argument to each of its terms.
P
⊆: Once again consider a term s = β cβ pβ · xα ∈ OK [x] with p ∤ cβ for all β ∈ N.
P
β α
Then any preimage of it under π is of the form s′ =
β cβ t x + r for some
r ∈ ht − pi.
P
If deg(−1,w) (r) > deg(−1,w) ( β cβ tβ xα ), we would have
in(−1,w) (s′ )|t=1 = in(−1,w) (r)|t=1 = 0,

since in(−1,w) (r) ∈ in(−1,w) hp − ti = hpi.
P
And if deg(−1,w) (r) < deg(−1,w) ( β cβ tβ xα ), we would have

P
in(−1,w) (s′ )|t=1 = in(−1,w) ( β cβ tβ xα )|t=1 = cβ0 · xα
P
= inν,w ( β cβ pβ · xα ) = inν,w (s),

where β0 := min{β ∈ N | cβ 6= 0}.
P
Now suppose deg(−1,w) (r) = deg(−1,w) ( β cβ tβ xα ). First observe that because t
is weighted negatively, there can be no cancellation amongst the highest weighted

6

THOMAS MARKWIG AND YUE REN

P
P
terms of r and the terms of β cβ tβ xα , as the terms of β cβ tβ xα are not divisible
by p, unlike the terms of the highest weighted terms of r. Therefore, we have
P
in(−1,w) (s′ )|t=1 = in(−1,w) ( β cβ tβ xα )|t=1 + in(−1,w) (r)|t=1 = inν,w (s).
|
{z
}
|
P {z β α }
=0
=inν,w (
β cβ p · x )

Either way, we always have in(−1,w) (s′ )|t=1 ∈ hinν,w (s)i for any arbitrary preimage
s′ ∈ π −1 (s), and, as before, the same hence holds true for any arbitrary element
f ∈ OK [x].


Corollary 2.9
For any ideal I E K[x] and any weight vector w ∈ Rn , we have:
in(−1,w) (π −1 I)|t=1 = inν,w (I).
Proof. Follows from inν,w (I) = inν,w (I ∩ OK [x]).



With our previous considerations, we can define tropical varieties of ideals in RJtK[x]
and show how some of them relate to tropical varieties of ideals in K[x].
Definition 2.10 (tropical variety)
For an ideal I E RJtK[x] we define its tropical variety to be
T (I) = {w ∈ R<0 × Rn | inw (I) monomial free} ⊆ R≤0 × Rn ,
where (·) denotes the closure in the euclidean topology.
Example 2.11
Unlike over coefficient fields, initial ideals over coefficient rings may be devoid of
monomials tβ xα , β ∈ N and α ∈ Nn while containing terms c · tβ xα , c ∈
/ R∗ .
Consequently, tropical varieties over rings need not be pure.
Consider the principal ideal generated by g := x + y + 2z ∈ ZJtK[x, y, z]. Figure 1
shows the intersection of its tropical variety with an affine subspace of codimension 2.
Because g is homogeneous in x, y, z, its tropical variety is invariant under translation
by (0, 1, 1, 1), and since t does not occur in g, it is also closed under translation
by (−1, 0, 0, 0). Hence, the remaining points are then uniquely determined up to
symmetry.
Since in(−1,−1,−1,0) (g) = 2z is no monomial, the entire lower left quadrant is included
in our tropical variety, while the two other maximal cones are not. However, because
in(−1,1,1,0) (g) = x + y is no monomial either, the edge containing it is also part of
our tropical variety. Therefore, the tropical variety cannot be the support of a pure

COMPUTING TROPICAL VARIETIES

7

inw (I) = hyi
contains monomial
(−1, 1, 1, 0)
(−1, 0, 0, 0)

inw (I) = h2zi
monomial free

inw (I) = hxi
contains monomial

Figure 1. T (hx + y + z2i) ∩ {wt = −1, wz = 0}
polyhedral complex. Note, however, that I is not the type of ideal we are interested
in, i.e. the type of ideal occurring in the following theorem.
Theorem 2.12
Let I E K[x] be an ideal. The projection R≤0 × Rn → Rn induces a natural bijection
∼

T (π −1 I) ∩ ({−1} × Rn ) −→ Tν (I)

(−1, w1 , . . . , wn ) 7−→ (w1 , . . . , wn ).

Proof. For the bijection, we show that
inν,w (I) monomial free

⇐⇒

in(−1,w) (π −1 I) monomial free.

⇒: Assume that in(−1,w) (π −1 I)ERJtK[x] contains a monomial tβ xα . Then, by Corollary 2.9, we have inν,w (I) = in(−1,w) (π −1 I)|t=1 , which means inν,w (I) must contain
the monomial xα ∈ K[x].
⇐: Assume that inν,w (I) E K[x] contains a monomial xα . Then, by Corollary 2.9,
in(−1,w) (π −1 I) must contain an element of of the form xα + (t − 1) · r + p · s, for
some r, s ∈ R[t, x]. Recall that p lies in in(−1,w) (π −1 I), therefore so does p · s, and
hence we have xα + (t − 1) · r ∈ in(−1,w) (π −1 I).
Let r = rl + . . . + r1 be a decomposition of r into its (−1, w)-homogeneous layers
with deg(−1,w) (r1 ) < . . . < deg(−1,w) (rl ). For sake of simplicity, we now distinguish
between three cases:
1. deg(−1,w) (xα ) ≥ deg(−1,w) (rl ): Set g1 := r − r1 = rl + . . . + r2 . Then
xα + (t − 1) · r = xα + (t − 1) · (g1 + r1 ) = xα + (t − 1) · g1 − r1 + t · r1 .
{z
}
|
higher weighted degree

Hence xα + (t − 1) · g1 − r1 , t · r1 ∈ in(−1,w) (π −1 I) and, more importantly,

t · (xα + (t − 1) · g1 − r1 ) + t · r1 = txα + (t − 1)t · g1 ∈ in(−1,w) (π −1 I),

8

THOMAS MARKWIG AND YUE REN

effectively shaving off the r1 layer. We can continue this process by setting g2 :=
g1 − r2 = rl + . . . + r3 . Then
txα + (t − 1)t · g1 = txα + (t − 1)t · (g2 + r2 )

= txα + (t − 1)t · g2 − t · r2 +t2 · r2 .
{z
}
|
higher weighted degree

Hence txα + (t − 1)t · g2 − t · r2 , t2 · r2 ∈ in(−1,w) (π −1 I) and, as above,
t · (txα + (t − 1)t · g2 − t · r2 ) + t2 · r2

= t2 xα + (t − 1)t2 · g2 ∈ in(−1,w) (π −1 I)

removing the r2 layer. Eventually, we obtain tl xα ∈ in(−1,w) (π −1 I).
2. deg(−1,w) (xα ) ≤ deg(−1,w) (r1 ): Set g1 := r − rl = rl−1 + . . . + r1 . Then
xα + (t − 1) · r = xα + (t − 1) · (g1 + rl ) = xα + (t − 1) · g1 + t · rl −rl .
|
{z
}
lower weighted degree

Thus rl , xα + (t − 1) · g1 + t · rl ∈ in(−1,w) (π −1 I) and, more importantly,

xα + (t − 1) · r1 + t · g1 − t · g1 = xα + (t − 1) · r1 ∈ in(−1,w) (π −1 I),
shaving off the the rl layer this time. Continuing this pattern eventually yields
xα ∈ in(−1,w) (π −1 I).
3. deg(−1,w) (r1 ) < deg(−1,w) (xα ) < deg(−1,w) (rl ): In this case we can use a combination of the steps in the previous cases to see ti ·xα ∈ in(−1,w) (π −1 I) for the 1 ≤ i ≤ k
such that deg(−1,w) (ri−1 ) < deg(−1,w) (xα ) ≤ deg(−1,w) (ri ).
In either case, we see that in(−1,w) (π −1 I) contains a monomial.

Corollary 2.13
If I E K[x] defines an irreducible subvariety of (K ∗ )n of dimension d, then T (π −1 I)
is the support of a pure polyhedral fan of dimension d + 1 connected in codimension
one.
Example 2.14
Let K := Q((u)) be the field of Laurent series, equipped with is natural valuation
νu , and let I E K[x, y] be the principal ideal generated by (x + y + 1) · (u2x + y + u).
Then Tνu (I) is the union of two tropical lines, one with vertex at (0, 0) and one with
vertex at (1, −1). Setting R := Q[t] ⊆ QJtK = OK , Proposition 2.8 implies that for
any weight vector w = (wt , wx , wy ) ∈ R<0 × R2 in the lower open halfspace we have


wx wy
−1
w ∈ T (π I) ⇐⇒
∈ Tνu (I).
,
|wt | |wt |

COMPUTING TROPICAL VARIETIES

9

Hence T (π −1 I) is as shown in Figure 2, the cone over Tνu (I). The polyhedral
complex consists of 6 rays and 8 two-dimensional cones in a way that the intersection
with the affine hyperplane yields a highlighted polyhedral complex, Tνu (I).
(0, 0, 0)

{−1} × R2

Figure 2. T (π −1 I) as cone over Tνu (I)
Example 2.15
Consider I = hx1 − 2x2 + 3x3 , 3x2 − 4x3 + 5x4 i E Q2 [x1 , . . . , x4 ], whose preimage is
given by
π −1 I = hx1 − 2x2 + 3x3 , 3x2 − 4x3 + 5x4 , 2 − ti E ZJtK[x1 , . . . , x4 ].
The tropical variety of the preimage is combinatorially of the form shown in Figure 3 and is invariant under the one-dimensional subspace generated by (0, 1, 1, 1, 1).
Hence each of the six vertices represents a two-dimensional cone and each of the five
edges represents a three-dimensional cone.
(0, −3, 1, 1, 1)

(0, 1, −3, 1, 1)

(−1, 1, −1, 1, −1)

(−2, −1, 1, −1, 1)

(0, 1, 1, −3, 1)

(0, 1, 1, 1, −3)

Figure 3. T (hx1 − 2x2 + 3x3 , 3x2 − 4x3 + 5x4 , 2 − ti)
Intersected with the affine hyperplane {−1} × R4 , we obtain a polyhedral complex
as shown in Figure 4, any vertex of Figure 3 in {0}×R4 becoming a point at infinity.
(−3, 1, 1, 1)

<

(1, 1, −3, 1)

<

(1, −1, 1, −1)

1
(−1, 1, −1, 1)
2

>

(1, −3, 1, 1)

>

(1, 1, 1, −3)

Figure 4. Tν2 (hx1 − 2x2 + 3x3 , 3x2 − 4x3 + 5x4 i)

10

THOMAS MARKWIG AND YUE REN

3. Tracing Gröbner complexes to a trivial valuation
In this section, we show how the Gröbner complexes of ideals in K[x] can be traced
back to the Gröbner fans of ideals in RJtK[x]. We will show how the Gröbner fan
induces a refinement of the Gröbner complex and how to determine whether two
integral Gröbner cones map to the same valued Gröbner polytope. For the latter,
we will need to delve into some basics in Gröbner bases. We close this section with
a remark on p-adic Gröbner bases as introduced by Chan and Maclagan [ChM13].
Definition 3.1 (Gröbner polyhedra, Gröbner complexes over valued fields)
For a homogeneous ideal I E K[x] and a weight vector w ∈ Rn we define its Gröbner
polytope to be
Cν,w (I) := {v ∈ Rn | inν,v (I) = inν,w (I)} ⊆ Rn ,
where (·) denotes the closure in the euclidean topology. We will refer to the collection
Σν (I) := {Cν,w (I) | w ∈ Rn } as the Gröbner complex of I.
Theorem 3.2 (Gröbner complex, [MaS15, Theorem 2.5.3])
Let I E K[x] be a homogeneous ideal. Then all Cν,w (I) are convex polytopes and
Σν (I) is a finite polyhedral complex.
Definition 3.3
For an x-homogenous ideal I E RJtK[x], i.e. an ideal generated by elements which
are homogeneous if considered as polynomials in x with coefficients in RJtK, and a
weight vector w ∈ R<0 × Rn we define its Gröbner cone to be
Cw (I) := {v ∈ R<0 × Rn | inv (I) = inw (I)},
where (·) denotes the closure in the euclidean topology. We will refer to the collection
Σ(I) := {Cw (I), Cw (I) ∩ {0} × Rn | w ∈ R<0 × Rn } as the Gröbner fan of I.
Proposition 3.4 ([MaR17], Theorem 3.19)
Let I E RJtK[x] be an x-homogeneous ideal. Then all Cw (I) are polyhedral cones and
Σ(I) is a finite polyehdral fan.
Corollary 3.5
∼
The map {−1} × Rn −→ Rn , (−1, w) 7−→ w is compatible with the Gröbner fan
Σ(π −1 I) and the Gröbner complex Σν (I), i.e. it maps the restriction of a Gröbner
cone C(−1,w) (π −1 I) ∩ {−1} × Rn into a Gröbner polytope Cν,w (I).
Proof. Follows directly from Proposition 2.8.



COMPUTING TROPICAL VARIETIES

11

Note that it may very well happen that several cones are mapped into the same
Gröbner polytope, i.e. that the image of the restricted Gröbner fan is a refinement
of the Gröbner complex (see Example 3.10).
We will now recall the notion of initially reduced standard bases of ideals in RJtK[x]
from [MRW17] and how they determine the inequalities and equations of Gröbner
cones as shown in [MaR17]. We will then use them to decide whether two Gröbner
cones are mapped to the same Gröbner polytope and, by doing so, show that no
separate standard basis computation is required for it.
Definition 3.6 (initially reduced standard bases)
Fix the t-local lexicographical ordering > such that x1 > . . . > xn > 1 > t.
Given a weight vector w ∈ R<0 × Rn we define the weighted ordering >w to be
tβ xα >w tδ xγ

:⇐⇒ w · (β, α) > w · (δ, γ) or

w · (β, α) = w · (δ, γ) and tβ xα > tδ xγ .

For g ∈ RJtK[x], the leading term LT>w (g) is the unique term of g with maximal
monomial under >w and for I E RJtK[x], the leading ideal LT>w (I) is the ideal
generated by the leading terms of all its elements. A finite subset G ⊆ I is called a
standard basis of I with respect to >w , if the leading terms of its elements generate
LT>w (I).
P
Suppose G = {g1, . . . , gk } with gi = α∈Nn gi,α · xα , gi,α ∈ RJtK. We call G initially
reduced, if the set
o
nX
α
′
LT> (gi,α ) · x
i = 1, . . . , k ⊆ R[t, x],
G :=
α∈N

is reduced in the classical sense.
Proposition 3.7 ([MaR17, Algorithm 4.6])
Let I E RJtK[x] be an x-homogeneous ideal and w ∈ R<0 × Rn a weight vector. Then
an initially reduced standard basis G of I with respect to >w exists.
Moreover, if I can be generated by elements in R[t, x], then G can be computed in
finite time.
Proposition 3.8 ([MaR17, Proposition 3.8, 3.11])
Let I E RJtK[x] be an x-homogeneous ideal, let w ∈ R<0 × Rn be a weight vector and
let G an initially reduced standard basis of I with respect to >w . Then the set of its
initial forms {inw (g) | g ∈ G} is an initially reduced standard basis of inw (I) with
respect to >w , and the Gröbner cone of I around w is given by
Cw (I) = {v ∈ R<0 × Rn | inv (g) = inw (g) for all g ∈ G}.

12

THOMAS MARKWIG AND YUE REN

We now show that our standard bases of π −1 I ERJtK[x] yield Gröbner bases of initial
ideals of I E K[x], allowing us to immediately decide whether two Gröbner cones of
the former are mapped to the same Gröbner polytope of the latter.
Corollary 3.9
Let I E K[x] be a homogeneous ideal, let w ∈ Rn be a weight vector and let G be an
initially reduced standard basis of π −1 I with respect to the weighted ordering >(−1,w) .
Then
o
n
in(−1,w) (g)|t=1 g ∈ G
is a standard basis of inν,w (I) with respect to the fixed lexicographical ordering >
restricted to monomials in x.

Proof. By Proposition 3.8, the set in(−1,w) (G) := {in(−1,w) (g) | g ∈ G} is an initially
reduced standard basis of in(−1,w) (π −1 I) with respect to >(−1,w) . And because it is
homogeneous with respect to weight vector (−1, w), it is also an initially reduced
standard basis with respect to >. By choice of >, the set in(−1,w) (G)|t=1 remains
a standard basis of in(−1,w) (π −1 I)|t=1 with respect to the restriction of > to monomials in x. And since p ∈ in(−1,w) (G)|t=1 , in(−1,w) (G)|t=1 is a standard basis of
in(−1,w) (π −1 I)|t=1 with respect to the restriction of >.

Example 3.10
Consider the preimage π −1 I EZJtK[x, y, z] of the ideal I = h2y+x, z 2 +y 2 iEQ2 [x, y, z]
and the two weight vectors w = (1, 3, 7), v = (1, 10, 5) ∈ R3 . Fix a lexicographical
tiebreaker > with x > y > z > 1 > t.
The initially reduced standard basis of π −1 I under >(−1,w) and >(−1,v) are the following two sets respectively (initial forms underlined):
G(−1,w) = {2 − t, ty + x, z 2 + y 2 }, G(−1,v) = {2 − t, ty + x, xy − tz 2 , t2 z 2 + x2 , y 2 + z 2 },
yielding the following Gröbner basis of inν,w (I) and inν,v (I) under >:
Gw = {y, z 2 },

Gv = {y, xy, z 2, y 2 }.

One immediately sees that both initial ideals coincide, meaning that the two Gröbner
cones C(−1,w) (π −1 I) and C(−1,v) (π −1 I) are mapped to the same Gröbner polytope
Cν2 ,w (I) = Cν2 ,v (I).
Remark 3.11 (homogenization and dehomogenization)
A lot of effort has been put into developing algorithms for computing Gröbner cones
Cw (I) for x-homogeneous ideals I E RJtK[x] and weight vectors w ∈ R<0 × Rn in
[MaR17] which terminate in finite time in case I can be generated by elements in

COMPUTING TROPICAL VARIETIES

13

R[t, x], avoiding the necessity to use homogenization and dehomogenization techniques as described in [BJS+ 07, Lemma 1.1], which are known to refine the Gröbner
fan structure in general.
The most prominent phenomenon showing the refinement is the non-regular Gröbner
fan in [Jen07, Theorem 1]. Note that Gröbner fans of homogeneous ideals are known
to be regular, as they are the normal fans of the state polytopes [Stu96, Theorem
2.5]. The non-regular Gröbner fan Σ(I) arises from the inhomogeneous ideal
I := hx1 x3 x4 + x21 x3 − x1 x2 , x1 x24 − x3 , x1 x44 + x1 x3 i E Q[x1 , . . . , x4 ]
and hence is restricted to the positive orthant R4≥0 . However, once homogenized
it yields a regular Gröbner fan Σ(I h ) living in R5 , whose restriction to {0} × R4≥0
refines Σ(I).
Remark 3.12 (p-adic Gröbner bases)
A Gröbner basis of an ideal I E K[x] over valued fields with respect to a weight
vector w ∈ Rn is by [MaS15, Section 2.4] a finite generating set whose initial forms
generate the initial ideal inν,w (I). Observe that Corollary 3.9 implies that such a
Gröbner basis can be computed by projecting an initially reduced standard basis of
π −1 I E RJtK[x] under the monomial ordering >w via π to K[x].
Figure 5 shows timings of the Macaulay2 Package GroebnerValuations from
Andrew Chan [GrS16, ChM13], a toy-implementation of a p-adic Matrix-F5 algorithm by Tristan Vaccon in Sage [Sag16, Vac14] and the standard basis engine of
Singular over integers under mixed orderings [DGPS16]. The examples are:
Cyclic(n): In Q2 [x0 , . . . , xn ], the cyclic ideal in the variables x1 , . . . , xn , homogenized using the variable x0 , and weight vector (1, . . . , 1).
Katsura(n): In Q2 [x0 , . . . , xn ], the Katsura ideal in the variables x1 , . . . , xn , homogenized using the variable x0 , and weight vector (1, . . . , 1).
Chan: In Q3 [x0 , . . . , xn ], the ideal h2x21 + 3x1 x2 + 24x3 x4 , 8x31 + x2 x3 x4 + 18x23 x4 i
and weight vector (−1, −11, −3, −19) taken from [Cha13, Chapter 3.6].

All computations were aborted after exceeding either 1 CPU day or 16 GB memory.
Note that the computations in Sage were done up to a finite precision of p50 and
that the correctness of the result could only be verified for the examples for which
either Macaulay2 or Singular finished.
4. Computation of tropical varieties
In this section, we present an algorithm for computing the tropical variety of an xhomogeneous ideal I ERJtK[x], provided it is pure and connected in codimension one,
as is the case for all preimages of ideals in K[x] under π. All algorithms in this section

14

THOMAS MARKWIG AND YUE REN

Examples Macaulay2 Sage Singular
Cyclic(4)
1
10
1
Cyclic(5)
1
Cyclic(6)
Katsura(3)
1
1
1
10
1
Katsura(4)
Katsura(5)
190
1
2900
Katsura(6)
Chan
1
4
Figure 5. Timings in seconds unless aborted
are straight-forward modification of the techniques developed by Bogart, Jensen,
Speyer, Sturmfels and Thomas for tropical varieties of homogeneous polynomial
ideals over ground fields with trivial valuation, which is why proofs are omitted and
instead references to [BJS+ 07] are added.
Before we begin, we quickly note that the computation of tropical hypersurfaces is
simple:
Algorithm 4.1 (TropHypersurface, [BJS+ 07, Algorithm 4.3])
P
Input: g = β,α cα,β · tβ xα , g 6= 0.
Output: ∆, collection of maximal dimensional cones in R≤0 × Rn such that
S
T (g) := T (hgi) = σ∈∆ σ.
1:

2:

Construct the finite set of exponent vectors with minimal entry in t,


α ∈ Nn with cα,β ′ 6= 0 for some β ′ ∈ N
n
.
Λ := (β, α) ∈ N × N
β = min{β ′ ∈ N | cα,β ′ 6= 0}
Construct the normal fan of its convex hull

∆ := NormalFan(Conv(Λ)).
3:

return {σ ∈ ∆ | σ ∩ R<0 × Rn 6= ∅ and dim(σ) = n}.

The computation of general tropical varieties on the other hand works in three steps:
(1) Finding a first maximal Gröbner cone Cw (I) ⊆ T (I), Alg. 4.7.
(2) Given Cu (I) ⊆ T (I) of codimension one, describe T (I) around Cu (I), Alg. 4.13.
(3) Given Cw (I) ⊆ T (I) maximal, compute an adjacent Cv (I) ⊆ T (I), Alg. 4.2.
of which (3) is a generalisation of the well-known flip of Gröbner bases, which we
will simply cite from [MaR17] without going into any algorithmic details:

COMPUTING TROPICAL VARIETIES

15

Algorithm 4.2 (Flip, [MaR17, Algorithm 5.5])
Input: (G, H, v, >w ), where
• >w a weighted monomial ordering with weight vector w ∈ R<0 × Rn ,
• v an outer normal vector of Cw (I),
• G = {g1 , . . . , gk } ⊆ I an initially reduced standard basis of an x-homogeneous
ideal I w.r.t. >w ,
• H = {h1 , . . . , hk } with hi = inw (gi ).

Output: (G′ , >w′ ), where

• Cw′ (I) adjacent to Cw (I) in direction v, i.e. Cw′ (I) = Cw+ε·v (I) for ε > 0
sufficiently small,
• G′ ⊆ I an initially reduced standard basis w.r.t. >w′ .

To show how to find a first maximal dimensional Gröbner cone on T (I), we need to
introduce the homogeneity space, since the starting cone algorithm works inductively
over the codimension of it, and we have to recall the lift of standard bases, which
we will again cite from [MaR17] without going into any algorithmic details. The
latter allows us to lift a standard basis of an initial ideal into a standard basis of
the original ideal, useful for avoiding unnecessary standard basis computations.
Definition 4.3 (homogeneity space)
Given an x-homogeneous ideal I E RJtK[x], we define the homogeneity space of I (or
of T (I)) to be the intersection of all its lower Gröbner cones, i.e. Gröbner cones of
the form Cw (I) for some w ∈ R<0 × Rn ,
\
Cw (I).
C0 (I) :=
w∈R<0 ×Rn

Example 4.4
Note that our definition of homogeneity space C0 (I) differs from the natural lineality
space C0 (I) of tropical varieties over fields with trivial valuation. In general, our
C0 (I) is neither a linear subspace nor is it the set of all vectors with respect to whom
the ideal is weighted homogeneous. Consider the principal ideal
I = h(1 + t) · x + (1 + t) · yi E ZJtK[x, y],
whose Gröbner Fan splits the weight space R≤0 × R2 into two maximal cones, see
Figure 6, and whose homogeneity space is given by
C0 (I) = {(wt , wx , wy ) ∈ R≤0 × Rn | wx = wy }.
Clearly, C0 (I) is no subspace and we have (−1, 0, 0) ∈ C0 (I) despite the ideal not
being weighted homogeneous with respect to it. This effect is caused by the terms

16

THOMAS MARKWIG AND YUE REN

tx and ty in the generator, which do not appear in any initial form and hence
have no influence on C0 (I), yet still exist and thus prevent I from being weighted
homogeneous with respect to any weight vector in the interior of C0 (I).
R · (0, 1, 1)

{0} × R2
C0 (I) = {wx = wy }

Figure 6. C0 (h(1 + t) · x + (1 + t) · yi)
We follow up our observation in Example 4.4 with the following Lemma, which
shows that the homogeneity space behaves properly in the case which is of interest
to us:
Lemma 4.5
Let I E RJtK[x] be an x-homogeneous ideal and w ∈ R<0 × Rn a weight vector. Then
C0 (inw (I)) = {v ∈ R<0 × Rn | inv inw (I) = inw (I)} = Lin(Cw (I)) ∩ (R≤0 × Rn ).
Proof. The second equality follows directly from the perturbation of initial ideals,
i.e. it follows from the fact that for any v ∈ R<0 ×Rn we have inv inw (I) = inw+ε·v (I)
for ε > 0 sufficiently small [MaR17, Proposition 5.4]. It remains to show the first
equality.
The ⊇ inclusion can be shown in a similar fashion: Suppose v ∈ R<0 × Rn such that
inv (inw (I)) = inw (I). Then for any u ∈ R<0 × Rn we have
inv+ε·u (inw (I)) = inu (inv (inw (I))) = inu (inw (I)),
showing that v + ε · u ∈ Cu (inw (I)) for any ε > 0 sufficiently small. As Cu (inw (I)) is
closed by definition, this implies v ∈ Cu (inw (I)). This shows that v is contained in
every lower Gröbner cone of inw (I), and hence also in their intersection C0 (inw (I)).
For the ⊆ inclusion, consider v ∈ C0 (inw (I)) ∩ (R<0 × Rn ), so that v ∈ Cu (inw (I))
for all u ∈ R<0 × Rn . In particular, v ∈ Cw (inw (I)) which is the middle set by
definition.


COMPUTING TROPICAL VARIETIES

17

Algorithm 4.6 (Lift, [MaR17, Algorithm 5.2])
Input: (H ′, >′ , H, G, >), where
• > a weighted t-local monomial ordering on Mon(t, x) with weight vector in
R<0 × Rn ,
• G = {g1 , . . . , gk } ⊆ I an initially reduced standard basis of an x-homogeneous
ideal I w.r.t. >,
• H = {h1 , . . . , hk } with hi = inw (gi ) for some w ∈ C> (I) with w0 < 0,
• >′ a t-local monomial ordering such that w ∈ C> (I) ∩ C>′ (I),
• H ′ ⊆ inw (I) a weighted homogeneous standard basis w.r.t. >′ .

Output: G′ ⊆ I, an initially reduced standard basis of I w.r.t. >′ .

Algorithm 4.7 (TropStartingCone, [BJS+ 07, Algorithm 4.12])
Input: (G, >w ), where G is an initially reduced standard basis of an x-homogeneous
ideal I with respect a weighted ordering >w , w ∈ R<0 × Rn .
Output: (Cw′ (I), G′ , >w′ ), where Cw′ (I) ⊆ T (I) maximal dimensional and G′ an
initially reduced standard basis of I with respect to the weighted ordering >w′ .
1: if dim(I) = dim(C0 (I)) then return (C0 (I), G, >)
2: Find a weight vector w ∈ (T (I) \ C0 (I)) ∩ (R<0 × Rn ).
3: Compute an initially reduced standard basis G′′ of I with respect to >w .
4: Set H ′′ := {inw (g) | g ∈ G′′ }.
5: Rerun
(Cw0′ (I), G′0 , >′0 ) = TropStartingCone(H ′′ , >w ).
Let >′ be the weighted ordering with weight vector w and tiebreaker >′0 .
7: Lift G′0 to an initially reduced standard basis G′ of I:

6:

G′ = Lift(G′0 , >′ , H ′′ , G′′ , >w ).
Construct the corresponding Gröbner cone Cw′ (I) := C(H ′ , G′ , >′ ).
9: return (Cw′ (I), G′ , >′ )

8:

Example 4.8
Let I E ZJtK[x1 , . . . , x4 ] be the preimage from Example 2.7,
I = h3 − t, 2x21 + 3x1 x2 + 24x3 x4 , 8x31 + x2 x3 x4 + 18x23 x4 i.
A short calculation reveals that dim(T (I)) = dim(I) = 3 > 1 = dim(C0 (I)) with
C0 (I) = R · (0, 1, 1, 1, 1).
Picking w := (−2, −1, 1, 5, −5) ∈ T (I), the initial ideal inw (I) is generated by
{3,

tx3 x4 − tx1 x2 + x21 ,

tx1 x22 − x21 x2 − t3 x1 x2 x3 + t2 x21 x3 }.

18

THOMAS MARKWIG AND YUE REN

Another short calculation reveals dim(inw (I)) = 3 > 2 = dim(C0 (inw (I))) with
C0 (inw (I)) = R≥0 · w + R · (0, 1, 1, 1, 1).
Picking v := (6, −11, 11, −1, 1) ∈ T (I), the initial ideal inv inw (I) is generated by
{3,

tx3 x4 − tx1 x2 ,

x2 x3 x4 − t2 x1 x2 x3 }.

And since dim(inv inw (I)) = 3 = dim(C0 (inv inw (I))) with
C0 (inv inw (I)) = R≥0 · (−1, 1, −1, 1, −1) + R · (0, 1, 0, 0, 1) + R · (0, 0, 1, 1, 0),
the recursions end.

v
C0 (inw (I))

C0 (inv inw (I))

w

C0 (I)
1 = dim(C0 (I)) < dim(C0 (inw (I))) < dim(C0 (inv inw (I))) = dim T (I) = 3

Figure 7. computing a tropical starting cone recursively
This shows that w + ε · v ∈ T (I) for ε > 0 sufficiently small. Together with the
one-dimensional C0 (I), this determines a maximal, three-dimensional Gröbner cone
in our tropical variety, see Figure 7.
Two centrals tools necessary to describe the tropical variety around one of its codimension one cells are generic weight vectors and tropical witnesses.
Definition 4.9 (multiweights and generic weights)
Given weight vectors w ∈ R<0 × Rn and v1 , . . . , vd ∈ R × Rn , we define the initial
form of an element g ∈ RJtK[x] with respect to the multidegree (w, v1 , . . . , vd ) to be
in(w,v1 ,...,vd ) (g) = invd . . . inv1 inw (g),
and we define the initial ideal of I E RJtK[x] with respect to (w, v1, . . . , vd ) to be
in(w,v1 ,...,vd ) (I) = invd · · · inv1 inw (I) = hin(w,v1 ,...,vd ) (g) | g ∈ Ii.

COMPUTING TROPICAL VARIETIES

19

Also, still fixing the lexicographical ordering > with x1 > . . . > xn > 1 > t from
Definition 3.6, we define the multiweighted ordering >(w,v1 ,...,vk ) to be
tβ · xα >(w,v1 ,...,vk ) tδ · xγ

⇐⇒

either :

• w · (β, α) > w · (δ, γ) or

• w · (β, α) = w · (δ, γ) and there exists an 1 ≤ l ≤ d with

vi · (β, α) = vi · (δ, γ) for all 1 ≤ i < l and vl · (β, α) > vl · (δ, γ) or

• w · (β, α) = w · (δ, γ) and vi · (β, α) = vi · (δ, γ) for all 1 ≤ i ≤ d
and tβ · xα > tδ · xγ .

Moreover, given a polyhedral cone σ ⊆ R≤0 × Rn of dimension d with σ * {0} × Rn
and a point w ∈ relint(σ) (note that w ∈ R<0 × Rn necessarily), we call a weight
vector u ∈ σ generic around w, if for all open neighbourhoods U around w there
exists a weight vector u′ ∈ U ∩ σ not lying on any Gröbner cone of dimension lower
than d such that inu′ (π −1 I) = inu (π −1 I).
Algorithm 4.10 (inσ,w (G), generic initial ideal around a weight)
Input: (σ, w, G), where
(1) σ ⊆ R≤0 × Rn , a polyhedral cone with σ * {0} × Rn ,
(2) w ∈ relint(σ) a relative interior point,
(3) G ⊆ I a generating set of an x-homogeneous ideal I E RJtK[x].

Output: (H ′, G′ , >′ ) = in(σ,w) (G), where

1:
2:
3:
4:
5:

(1) >′ :=>u for a weight vector u ∈ σ generic around w,
(2) G′ an initially reduced standard basis of I with respect to >′ ,
(3) H ′ = {inu (g) | g ∈ G′ }.

Choose a basis v1 , . . . , vd of the linear span of σ.
Pick a t-local monomial ordering > on Mon(t, x).
Compute an initially reduced standard basis G′ of I = hGi w.r.t. >(w,v1 ,...,vd ) .
Set H ′ := {in(w,v1 ,...,vd ) (g) | g ∈ G′ }
return (H ′ , G′ , >(w,v1 ,...,vd ) ).

Definition 4.11
Let I E RJtK[x] and let u ∈ R<0 × Rn be such that Cu (I) * T (I). We call an element
f ∈ I a tropical witness of Cu (I) if inv (f ) is a monomial for all v ∈ Relint(Cu (I)).
Algorithm 4.12 (TropWitness, [BJS+ 07, Algorithm 4.7])
Input: (m, H, G, >), where
(1) >w a weighted monomial ordering for some w ∈ R<0 × Rn ,

20

THOMAS MARKWIG AND YUE REN

(2) G = {g1 , . . . , gk } an initially reduced standard basis of an x-homogeneous
ideal I E RJtK[x] with respect to >w ,
(3) H = {h1 , . . . , hk } with hi = inw (gi ),
(4) m ∈ inw (I) a monomial.

Output: f ∈ I, a tropical witness of Cw (I).
1: Compute a standard representation m = q1 · h1 + . . . + qk · hk , i.e. no term of
qi · hi lies in hLM> (hj ) | j < ii for all 1 ≤ i ≤ k.
2: return q1 · g1 + . . . + qk · gk .
Algorithm 4.13 (TropStar, [BJS+ 07, Algorithm 4.8])
Input: G, the generating set of an x-homogeneous ideal I ERJtK[x] with dim T (I) =
dim C0 (I) + 1.
Output: ∆, a collection of maximal dimensional polyhedral cones in R≤0 × Rn
covering T (I).
1: Compute the common refinement of all tropical hypersurfaces, throwing away
cones in {0} × Rn ,
V
∆ := {σ ∈ g∈G TropHypersurface(g) | σ ∩ R<0 × Rn 6= ∅}.
Set L := ∆.
3: while L 6= ∅ do
4:
Pick σ ∈ L maximal and w ∈ relint(σ).
5:
Compute an initial ideal with respect to a weight w ∈ σ generic around w:
2:

(H ′, G′ , >′ ) = in(σ,w) (G).

6:
7:
8:

if inu (I) = hH ′ i contains a monomial s 6= 0 then
Compute a tropical witness g := TropicalWitness(s, H ′, G′ , >′ ).
Set
G := G ∪ {g},

9:
10:
11:
12:
13:
14:

∆ := ∆ ∧ T (g),

L := L ∧ T (g).

continue
Suppose w = (wt , wx ) ∈ R<0 × Rn , set wneg := (wt , −wx ) ∈ R<0 × Rn .
if wneg ∈ σ then
Redo Steps 5 to 9 with w := wneg .
Set L := L \ {σ}.
return ∆

Example 4.14
Consider the ideal I E ZJtK[x1 , . . . , x4 ] generated by
g0 := 3,

g1 := tx3 x4 − tx1 x2 + x21 ,

g2 := tx1 x22 − x21 x2 − t3 x1 x2 x3 + t2 x21 x3 ,

COMPUTING TROPICAL VARIETIES

21

which is 3-dimensional with C0 (I) = Cone((−2, −1, 1, 5, −5)) + R · (0, 1, 1, 1, 1).
Figure 8 illustrates the combinatorial structure of T (g0 ) ∩ T (g1 ) ∩ T (g2 ).
(0, 1, 1, 1, −3)

σ

(0, 0, 0, −1, 1)

(0, 0, 0, 1, −1)

(−2, −1, 1, 5, −5)

(0, −1, 1, 1, −1)

(0, 1, −3, −3, 5)

Figure 8. combinatorial structure of T rop(g0) ∩ T (g1 ) ∩ T (g2 )
One cone σ that can be seen to be contained in the intersection is
σ := Cone((0, 0, 0, −1, 1), (0, 1, 1, 1, −3)) + C0 (I),
|
{z
} |
{z
}
=:w1

because we have

inw (g1 )

2
}|
{
z
g1 = tx3 x4 −tx1 x2 + x21 ,
|
{z
}

inw1 (g1 )

=:w2

inw (g2 )

1
}|
{
z
2
g2 = tx1 x2 − x21 x2 −t3 x1 x2 x3 + t2 x21 x3 ,
|
{z
}

inw2 (g2 )

so that for any weight w ∈ σ, inw (g1 ) contains at least the binomial −tx1 x2 + x21
and inw (g2 ) contains at least the binomial tx1 x2 − x21 x2 . In particular, neither are
monomials. However, it can be shown that, for
g3 := tx2 x3 x4 + t2 x21 x3 − t3 x1 x2 x3 ∈ I

and w := (−1, 1, 2, 2, 0) ∈ σ,

inw (g3 ) = tx2 x3 x4 is a monomial, which implies that σ * T (I) (not that we would
have expected otherwise considering dim(σ) = 4 > 3 = dim(T (I))). Figure 9
T
illustrates the combinatorial structure of 3i=0 T (gi ), red highlighting all weights
that have been eliminated through the intersection with T (g3 ).
Continuing, the following cone can be seen to be contained in the intersection of the
tropical varieties of g0 , . . . , g3 ,
σ ′ := Cone((0, 1, 1, −3, 1), (0, 1, 1, 1, −3)) + C0 (I),
{z
} |
{z
}
|
=:w1

=:w2

22

THOMAS MARKWIG AND YUE REN
(0, 1, 1, 1, −3)

σ

(0, 0, 0, −1, 1)

′

(0, 1, 1, −3, 1)
(0, 0, 0, 1, −1)

(−2, −1, 1, 5, −5)

(0, −1, 1, 1, −1)

(0, 1, −3, −3, 5)

Figure 9. combinatorial structure of

T3

i=0

T (gi )

since
inw1 (g1 ), inw2 (g1 )

z
}|
{
g1 = tx3 x4 −tx1 x2 + x21 ,
inw (g3 )

inw (g2 )

1
z
}|
{
2
g2 = tx1 x2 − x21 x2 −t3 x1 x2 x3 + t2 x21 x3 ,
|
{z
}

inw2 (g2 )

3
z
}|
{
2 2
g3 = tx2 x3 x4 +t x1 x3 − t3 x1 x2 x3 .
|
{z
}

inw1 (g3 )

However, setting

g4 := tx2 x3 x4 − t3 x23 x4 ∈ I

and w ′ := (−1, 3, 4, 5, 0) ∈ σ ′ ,

inw′ (g4 ) = tx2 x3 x4 is a monomial. Hence, we have again σ ′ * T (I) and Figure 10
T
illustrates the combinatorial structure of 4i=0 T (gi ). Further calculations will yield
T
that indeed T (I) = 4i=0 T (gi ).
(0, 1, 1, 1, −3)
(0, 0, 0, −1, 1)
(−2, −1, 1, 5, −5)

(0, −1, 1, 1, −1)

(0, 1, −3, −3, 5)

Figure 10. combinatorial structure of

T4

i=0

T (gi )

Tropical varieties with one-codimensional homogeneity space are important as they
describe general tropical varieties locally around a codimension one cone.

COMPUTING TROPICAL VARIETIES

23

Example 4.15
Consider again the ideal I E ZJtK[x1 , . . . , x4 ] from Example 2.7 and 4.8 generated by
3 − t,

8tx3 x4 + tx1 x2 + 2x21 ,

tx1 x22 + 2x21 x2 + 2t3 x1 x2 x3 + 4t2 x21 x3 − 64tx31 .

For any weight vector inside T (I), say w = (−2, −1, 1, 5, −5), T (inw (I)) describes
T (I) locally around w, see Figure 11. In particular, if w lies on a Gröbner cone of
codimension 1, we have
Lem.

dim C0 (inw (I)) = dim Cw (I) = dim T (I) − 1 = dim T (inw (I)) − 1,
4.5

which allows us to compute T (inw (I)) using Algorithm 4.13.
(0, −1, 1, 1, −1)
(0, 1, 1, 5, −7)

(−1, 0, −1, 1, 0)

(0, 1, −3, 1, 1)

w

(0, 1, 1, 1, −3)

(−1, 0, 1, 3, −4)
w
(0, −1, 1, 1, −1)

(0, 1, −3, −3, 5)

(0, 0, 0, −1, 1)

Figure 11. T (I) and T (inw (I))
Combining Algorithms 4.7, 4.13 and 4.2, we obtain an algorithm to compute the
tropical variety of a general ideal, provided it is pure and connected in codimension
one.
Algorithm 4.16 (Trop, [BJS+ 07, Algorithm 4.11])
Input: (Ginput , >input ), where for an x-homogeneous ideal I E RJtK[x] with T (I)
pure and connected in codimension one:
• >input is a weighted monomial ordering,
• Ginput an initially reduced standard basis of I with respect to >input .

Output: ∆ = {Cw (I) | Cw (I) ∈ T (I) maximal}, so that
S
T (I) = Cw (I)∈∆ Cw (I).
1:

Compute a starting cone

(Cw (I), G, >) = TropStartingCone(Ginput , >input ).

24

2:
3:
4:
5:
6:
7:
8:
9:

THOMAS MARKWIG AND YUE REN

Initialize ∆ := {Cw (I)}.
Initialize a working list L := {(G, >, Cw (I))}.
while L 6= ∅ do
Pick (G, >, Cw (I)) ∈ L.
for all facets τ ≤ Cw (I), τ * {0} × Rn do
Compute a relative interior point u ∈ τ .
Set H := {inu (g) | g ∈ G}.
Compute the tropical star
∆star = TropStar(H).

10:
11:
12:
13:

for θ ∈ ∆star do
Compute a relative interior point v ∈ θ.
if Cu+ε·v (I) ∈
/ ∆ for ε > 0 sufficiently small then
Flip the standard basis to the adjacent ordering
(G′ , >′ ) := Flip(G, H, v, >).

14:
15:

Set H ′ := {in(u,v) (g) | g ∈ G′ }.
Construct the adjacent Gröbner cone
Cw′ (I) := C(H ′ , G′ , >′).

16:

Set
∆ := ∆ ∪ {Cw′ (I)} and L := L ∪ {(G′ , >′ , Cw′ (I))}.

Set L := L \ {(G, >, Cw (I))}.
18: return ∆.
17:

Example 4.17 (tropical traversal)
For a visual example of Algorithm 4.16 at work, consider the 3-dimensional ideal
I = h4x2 + xy + 16y 2 + xz + 8z 2 , 2 − ti

= ht2 x2 + xy + t4 y 2 + xz + t3 z 2 , 2 − ti ∈ ZJtK[x, y, z].
|
{z
}
=:g

As inw (2 − t) = 2 for all w ∈ R<0 × R3 , it suffices to solely focus on g. For the
starting cone, we begin with weight vector w = (−3, −10, 1, 0) ∈ R<0 × R3 , since
inw (g) = xy + t3 z 2 is no monomial. In fact, its initial form is binomial, hence
the only weight vectors v such that inw+εv (g) is no monomial are the v such that
inw+εv (g) = inw (g), or in other words v ∈ Cw (I). This shows that Cw (I) is a
maximal cone in the tropical variety.
Note that all Gröbner cones are invariant under transv1
v2
lation by (0, 1, 1, 1). Hence the 3-dimensional Gröbner
cone Cw (I) is spanned by two rays, which are generated

COMPUTING TROPICAL VARIETIES

25

by v1 = (−2, −7, 1, 0) and v2 = (−1, −3, 0, 0) respectively. This can be seen from
their respective initial forms, which gain one additional term compared to inw (g),
inv1 (g) = xy + t4 y 2 + t3 z 2 and inv2 (g) = xy + xz + t3 z 2 . We have thus finished
computing a starting cone and identified its two facets, which we need to traverse.
If we pick one of the facets, say the one generated by v1 ,
v1,1
we see that its tropical star consists of three rays. One
v1,3
ray points in the direction v1,3 = (0, 0, −2, −1) so that
v1,2
inv1 +ε·v1,3 (g) = xy + t3 z 2 = inw (g), which undoubtedly
points into our starting cone. Another ray points in the
direction v1,2 = (0, 0, 1, 1) so that inv1 +ε·v1,2 (g) = t4 y 2 + t3 z 2 . The last ray points in
the direction v1,1 = (0, 0, 0, −1) so that inv1 +ε·v1,1 (g) = xy + t4 y 2.
Continuing with direction v1,2 = (0, 0, 1, 1), to whose side
v3
lies the closure of equivalence class such that inw′ (g) =
t4 y 2 + t3 z 2 , we see that the other ray of the maxiv1
v2
mal Gröbner cone is generated by v3 = (0, 0, 1, 1) with
inv3 (g) = t4 y 2 + t3 z 2 . The ray lies on the boundary of the
v4
maximal Gröbner cone because it lies on the boundary
of the lower halfspace.
Continuing with the direction v1,1 = (0, 0, 0, −1), which is the closure of the equivalence class such that inw′ (g) = xy + t4 y 2, we get that the other ray of the maximal
Gröbner cone is v4 = (0, 0, 0, −1) with inv4 (g) = t2 x2 + xy + t4 y 2 .
Because both v3 and v4 lie on the boundary of
the lower halfspace, the only facet left to trav2,2
v2,3
verse is the one generated by v2 . The tropical
star around v2 consists of three rays. One ray
v2,1
points in the direction of v2,1 = (0, 1, 0, 0) so that
inv2 +ε·v2,1 (g) = xy + xz. Another ray points in
the direction of v2,2 = (0, 0, −1, 0) so that inv2 +ε·v2,2 (g) = xz + t3 z 2 . The final ray
points in the direction of v2,3 = (0, 0, 2, 1) so that inv2 +ε·v2,3 (g) = xy + t3 z 2 = inw (g),
this is the vector pointing into our starting cone.
Continuing in the direction of v2,1 , the other ray
v6
v3
of the maximal Gröbner cone is generated by
v5 = (−1, 2, 0, 0) as inv5 (g) = t2 x2 + xy + xz.
v1
v2
And continuing in the direction of v2,2 , the other
ray is generated by v6 := (0, 0, −1, 0) as inv6 (g) =
v5
v4
t2 x2 + xz + t3 z 2 .
Because v6 lies on the boundary of the lower halfspace, v5 generates the only facet left to traverse. A quick glance at the initial forms

26

THOMAS MARKWIG AND YUE REN

imply that it is connected to the facets generated by v4 and v6 , as it has two terms
in common with each of them.
We obtain that T (I) is covered by a polyhev6
v3
dral fans which, modulo the homogeneity space
R · (0, 1, 1, 1), has 6 rays, of which the ones genv1
v2
erated by v1 , v2 , v5 lie in the interior of the lower
halfspace R≤0 × Rn , while the ones generated by
v5
v4
v3 , v4 , v6 lie on its boundary.
The 6 rays are pairwise connected via 7 edges.
The edges connecting (v1 , v3 ), (v1 , v4 ), (v2 , v6 ) and (v4 , v5 ) intersect the boundary
in codimension one, while the cones connecting (v1 , v2 ) and (v2 , v5 ) intersect the
boundary in codimension 2, which has to be the homogeneity space.
Example 4.18 (dependency on the valuation)
Consider the ideal from Example 2.15, I := hx1 − 2x2 + 3x3 , 3x2 − 4x3 + 5x4 i E Q[x].
Figure 12 shows its tropical varieties for all possible valuations on Q. Regardless of
the valuation, all tropical varieties share the same recession fan, as was proven by
Gubler [Gub13]. The latter is also necessarily the tropical variety under the trivial
valuation. Note that for p sufficiently large, the tropical varieties under νp coincides
with the tropical variety under the trivial valuation. This is because p is simply
too large for p − t to matter in any of our standard basis calculations. These p are
referred to as good primes while other p are referred to as bad primes in the theory
of modular techniques [BDF+ 16].
(−3, 1, 1, 1)

<

(1, 1, −3, 1)

<

(1, −1, 1, −1)

1
(−1, 1, −1, 1)
2

>

(1, −3, 1, 1)

>

(1, 1, 1, −3)

(−3, 1, 1, 1)
(1, −3, 1, 1)

<

>

(1, 1, −3, 1)

<

>

(1, 1, 1, −3)

1
(−1, −1, −1, 3)
4

Tν2 (I)
(−3, 1, 1, 1)

<

(1, −3, 1, 1)

<

1
(−1, −1, 1, 1)
2

1
(1, 1, −1, −1)
2

Tν3 (I)

Tν5 (I)
>

(1, 1, −3, 1)

(−3, 1, 1, 1)

<

>

(1, 1, −3, 1)

>

(1, 1, 1, −3)

(1, −3, 1, 1)

<

>

(1, 1, 1, −3)

(0, 0, 0, 0)

Tνp (I) = T (I) for p > 7

Figure 12. Tν (I) for various p-adic and the trivial valuations.

COMPUTING TROPICAL VARIETIES

27

Example 4.19 (independency of the valuation, Singular output)
Consider the following ideal of Grassmann-Plücker relations for Grass(2, 5),
I := hx1 x5 − x0 x7 − x2 x4 , x1 x6 − x0 x8 − x3 x4 , x2 x6 − x0 x9 − x3 x5 ,
x2 x8 − x1 x9 − x3 x7 , x5 x8 − x4 x9 − x6 x7 i E Q[x0 , . . . , x9 ].

Unlike Example 4.18, its tropical variety does not seem to dependent on the choice
of valuation, which is not surprising as Speyer and Sturmfels showed that it is
characteristic-free [SpS04, Theorem 7.1]. In this case, the computations under the
p-adic valuation are mathematically equivalent to the computations under the trivial
valuation, though the practical timings under the p-adic valuation are slightly slower
due to a constant overhead of a more general framework.
Figure 13 shows a shortened output of Singular when computing its tropical variety with respect to the 2-adic valuation. It describes a polyhedral fan whose
intersection with the affine hyperplane {−1} × R10 yields again a polyhedral fan:
The ray #0 represents the 5-dimensional lineality space of Tν2 (I), while the maximal
cones {0 i j} represent polyhedral cones in Tν2 (I) spanned by the lineality space
and rays #i, #j. Note that, from a perspective of Rn = {−1} × Rn , all data is given
in homogenized coordinates, which is why the f-Vector shown is slightly distorted
by lower-dimensional cones at infinity.
Figure 14 illustrates the combinatorial structure of ∆. Each vertex represents a ray
of ∆, while each edge represents a maximal cone of ∆. The graph shown should be
thought of as lying on a sphere S 2 , on which the colored edges connect with their
counterpart on the other side.
5. Optimizations for non-trivial valuations
Up till now, all algorithms for computing Tν (I) via T (π −1 I) appear to be strictly
worse than computing T (I), as we are working with an inhomogeneous ideal π −1 I
over a coefficient ring R instead of a homogeneous ideal I over a coefficient field K.
In this section, however, we consider simple optimizations for the traversal, which
suggest that working under a nontrivial valuation need not necessarily be slower
than working under a trivial valuation.
The main algebraic bottlenecks in the computation of tropical varieties are:
(1) computing generic initial ideals, Algorithm 4.10 ,
(2) checking generic initial ideals for monomials in Algorithm 4.13,
(3) the flip of standard bases, Algorithm 4.2,
all of which require at least one standard basis computation, which is the reason for
the bottleneck. However, from Algorithm 4.16, they are never called on the actual

28

THOMAS MARKWIG AND YUE REN
SINGULAR
A Computer Algebra System for Polynomial Computations

/
/ Version 4.1.0
0<
by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann \ Dec 2016
FB Mathematik der Universitaet, D-67653 Kaiserslautern \
> LIB "gfanlib.so";
> printlevel = 1;
> ring r=0,(a,b,c,d,e,f,g,h,i,j),dp;
> ideal I = bf-ah-ce, bg-ai-de, cg-aj-df, ci-bj-dh, fi-ej-gh;
> tropicalVariety(I,number(2));
cones finished: 1 cones in working list: 4
[...] information on the state of the traversal because printlevel=1 was set
cones finished: 14 cones in working list: 1
cones finished: 15 cones in working list: 0
_application PolyhedralFan
_version 2.2
_type PolyhedralFan
AMBIENT_DIM
11

LINEALITY_SPACE
0 -1 0 0 0 0 0 0 1 1 1 # 0
0 0 -1 0 0 0 1 1 0 0 1 # 1
0 0 0 1 0 0 1 0 1 0 1
# 2
0 0 0 0 1 0 0 1 0 1 1
# 3
0 0 0 0 0 -1 -1 -1 -1 -1 -1# 4

DIM
8

F_VECTOR
1 11 25 15

LINEALITY_DIM
5

MAXIMAL_CONES
{0 1 2}# Dimension 8
{0 1 3}
{0 1 4}
{0 2 5}
{0 2 9}
{0 3 7}
{0 4 6}
{0 3 8}
{0 4 10}
{0 5 6}
{0 5 7}
{0 6 8}
{0 7 10}
{0 8 9}
{0 9 10}

RAYS
-1 0 0 0 0 0 0 0 0 0 0 # 0
0 -3 1 1 1 1 1 1 -1 -1 -1#
0 -1 -1 1 1 -1 1 1 1 1 -3#
0 -1 1 -1 1 1 -1 1 1 -3 1#
0 -1 1 1 -1 1 1 -1 -3 1 1#
0 1 -3 1 1 1 -1 -1 1 1 -1#
0 1 -1 -1 1 1 1 -3 -1 1 1#
0 1 -1 1 -1 1 -3 1 1 -1 1#
0 1 1 -3 1 -1 1 -1 1 -1 1#
0 1 1 -1 -1 -3 1 1 1 1 -1#
0 1 1 1 -3 -1 -1 1 -1 1 1#

1
2
3
4
5
6
7
8
9
10

Figure 13. Singular output for the Grassmann-Plücker ideal

COMPUTING TROPICAL VARIETIES

29

9
2

5

6

1

4

3

7

10

8

Figure 14. tropical variety of the Grassmann-Plücker ideal
input ideal, they are exclusively called on its initial ideals instead. This can be
exploited, should the input ideal of Algorithm 4.16 be of the form π −1 I for some
I E K[x]. Lemma 5.4 then shows that many computations can actally be done over
the residue field K.
Convention 5.1
Let I E K[x] be a homogeneous ideal and fix an initial ideal J := in(−1,w) (π −1 I) E
R[t, x] of its preimage as well as the corresponding monomial ordering >(−1,w) . Note
that necessarily p ∈ J.
Lemma 5.2 (quasi-homogeneity of J)
There exists a positive weight vector u ∈ (R>0 )n+1 such that J is weighted homogeneous with respect to it.
Proof. Because J is weighted homogeneous with respect to w ∈ R<0 × Rn and xhomogeneous, it is, picking k ∈ N sufficiently high, also weighted homogeneous with
respect to k · (0, 1, . . . , 1) + w ∈ (R>0 )n+1 .

Definition 5.3
P
We call an element g = β,α cβ,α · tβ xα ∈ R[t, x] a canonical representative of its
residue class g ∈ K[t, x], if
cβ,α = 0 ⇐⇒ cβ,α = 0

and

cβ,α = 1 ⇐⇒ cβ,α = 1.

Lemma 5.4 (standard bases of J)
Let {g 1 , . . . , g k } be a monic standard basis of J with respect to >(−1,w) . Then

30

THOMAS MARKWIG AND YUE REN

{g0 , g1, . . . , gk } is a standard basis of J with respect to >(−1,w) , where g0 = p and
g1 , . . . , gk are canonical representatives of their residue classes.
Proof. Let G = {g0 , . . . , gk }. Since p ∈ J, it is clear that hGi ⊆ J and therefore
hLT> (g) | g ∈ Gi ⊆ LT> (J). For the converse, consider a term s = c·tβ xα ∈ LT> (J).
Now if p | c, then s ∈ hLT> (g) | g ∈ Gi, since p ∈ G and LT> (p) = p. And if p ∤ c, we
may use p ∈ LT> (J) to normalize s, and get tβ xα ∈ LT> (J). Thus tβ xα ∈ LT> (J),
and hence there is a gi such that LM> (g i ) | tβ xα . Since all g i were chosen to be
monic, this implies LT> (g i ) | tβ xα , and because all gi were chosen to be canonical
representatives, this implies LT> (gi ) | s.

This article was dedicated to show how Tν (I) can be computed via T (π −1 I), however
until now we have not addressed how to compute the preimage π −1 I in the first place.
We will therefore end the article with two results: The first will show that π −1 I can
be obtained by a saturation. The second will allow us get around computing the
saturation.
Lemma 5.5
Let I E K[x] be an ideal, and let G = {g1 , . . . , gk } ⊆ I ∩ OK [x] be a generating
set over the valuation ring. Since π : RJtK[x] → OK [x] is surjective, there exist
g1′ , . . . , gk′ ∈ RJtK[x] such that π(gi′ ) = gi ∈ R[x]. Then


π −1 I = hg1′ , . . . , gk′ i + hp − ti : p∞ E RJtK[x].

Proof. π −1 I ⊇ (hg1′ , . . . , gk′ i + hp − ti) : p∞ is obvious, as p − t is mapped to 0 and p
is invertible in K.
For the converse inclusion, let f ∈ π −1 I. Then there are q1 , . . . , qk ∈ K[x] such that
π(f ) = q1 · g1 + . . . + qk · gk ∈ K[x],
which means that for a sufficiently high power l ∈ N we have

pl · π(f ) = pl q1 ·g1 + . . . + pl qk ·gk ∈ OK [x].
|{z}
|{z}
∈OK [x]

∈OK [x]

Since the map π : RJtK[x] → OK [x] is surjective, there exist q1′ , . . . , qk′ ∈ RJtK[x]
such that
pl · π(f ) = π(q1′ · g1′ + . . . + qk′ · gk′ ),
or rather

pl · f − q1′ · g1′ + . . . + qk′ · gk′ ∈ ker(π) = hp − ti.

Thus pl · f ∈ hg1′ , . . . , gk′ i + hp − ti, and hence

f ∈ (hg1′ , . . . , gk′ i + hp − ti) : p∞ .



COMPUTING TROPICAL VARIETIES

31

Proposition 5.6
Let IEK[x] be an ideal, and let G = {g1′ , . . . , gk′ } ⊆ π −1 I such that I = hπ(g1′ ), . . . , π(gk′ )i.
Then
T (π −1 I) = T (hg1′ , . . . , gk′ i + hp − ti).
Proof. By Lemma 5.5, we have


π −1 I = hg1′ , . . . , gk′ i + hp − ti : p∞ E RJtK[x].
{z
}
|
=:I ′

Consider a weight vector w ∈ R<0 × Rn and suppose inw (I ′ ) contains a monomial
tβ xα . By Algorithm 4.12, there exists a witness f ∈ I ′ with inw (f ) = tβ xα . However
since I ′ ⊆ π −1 I, inw (π −1 I) then contains the monomial tβ xα as well.
Now suppose inw (π −1 I) contains a monomial tβ xα . By Algorithm 4.12, there exists
a witness f ∈ π −1 I with inw (f ) = tβ xα . Let l ∈ N be sufficiently high such that
pl · f ∈ I ′ . Now since p − t ∈ I ′ , this implies tl · f ∈ I ′ and inw (I ′ ) then contains the
monomial inw (tl · f ) = tβ+l xα .

References
[BaT07] Rouchdi Bahloul and Nobuki Takayama, Local Gröbner fans, C. R. Math. Acad. Sci.
Paris 344 (2007), no. 3, 147–152.
[BDF+ 16] Janko Böhm, Wolfram Decker, Claus Fieker, Santiago Laplagne, and Gerhard Pfister, Bad primes in computational algebraic geometry, pp. 93–101, Springer International
Publishing, 2016.
[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.
[Cha13] Andrew Chan, Gröbner bases over fields with valuation and tropical curves by coordinate
projections, Ph.D. thesis, University of Warwick, 2013.
[ChM13] Andrew J. Chan and Diane Maclagan, Groebner bases over fields with valuations, 2013.
[DGPS16] Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann,
Singular 4-1-0 — A computer algebra system for polynomial computations,
https://www.singular.uni-kl.de, 2016.
[GrS16] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research
in algebraic geometry, https://www.math.uiuc.edu/Macaulay2/, 2016.
[Gub13] Walter Gubler, A guide to tropicalizations, Algebraic and combinatorial aspects of tropical geometry, Contemp. Math., vol. 589, Amer. Math. Soc., Providence, RI, 2013,
pp. 125–189.
[Jen07] Anders Nedergaard Jensen, A non-regular Gröbner fan, Discrete Comput. Geom. 37
(2007), no. 3, 443–453.
[Jen11] Anders N. Jensen, Gfan 0.5, a software system for Gröbner fans and tropical varieties,
http://home.math.au.dk/jensen/software/gfan/gfan.html, 2011.
[JMMR16] Anders N. Jensen, Hannah Markwig, Thomas Markwig, and Yue Ren, tropical.lib.
a Singular 4-1-0 library for computations in tropical goemetry, 2016.

32

THOMAS MARKWIG AND YUE REN

[JRS16] Anders N. Jensen, Yue Ren, and Frank Seelisch, gfan.lib. a Singular 4-1-0 interface
to gfanlib for basic computations in convex geometry, 2016.
[Kal13] Nikita Kalinin, Tropical approach to nagata’s conjecture in positive characteristic, 2013.
[MaS15] Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015.
[MaR17] Thomas Markwig and Yue Ren, Gröbner fans of x-homogeneous ideals in R[[t]][x], J.
Symb. Comput. (2017), to appear, also available as arXiv:1512.02662.
[MRW17] Thomas Markwig, Yue Ren, and Oliver Wienand, Standard bases in mixed power series
and polynomial rings over rings, J. Symb. Comput. 79 (2017), 119–139.
[PPS13] Patrick Popescu-Pampu and Dmitry Stepanov, Local tropicalization, Algebraic and combinatorial aspects of tropical geometry, Contemp. Math., vol. 589, Amer. Math. Soc.,
Providence, RI, 2013, pp. 253–316.
[Sag16] Sage, Sagemath, the Sage Mathematics Software System (Version 7.4), 2016,
https://www.sagemath.org.
[SpS04] David Speyer and Bernd Sturmfels, The tropical Grassmannian, Adv. Geom. 4 (2004),
no. 3, 389–411.
[Stu96] Bernd Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, vol. 8,
American Mathematical Society, Providence, RI, 1996.
[Tou05] Naoyuki Touda, Local tropical variety, 2005.
[Vac14] Tristan Vaccon, Matrix-f5 algorithms over finite-precision complete discrete valuation
fields, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, 2014, pp. 397–404.
Eberhard Karls Universität Tübingen, Fachbereich Mathematik, Auf der Morgenstelle 10, 72076 Tübingen, Germany
E-mail address: keilen@math.uni-tuebingen.de
URL: https://www.math.uni-tuebingen.de/~keilen
Ben-Gurion University of the Negev, Department of Mathematics, P.O.B. 653,
8410501 Be’er Sheva, Israel
E-mail address: reny@post.bgu.ac.il
URL: https://www.math.bgu.ac.il/~reny

