Gfan version 0.7: A User’s Manual
Anders Nedergaard Jensen ∗August 12, 2024

Abstract
Gfan is a software package for computing Gröbner fans and tropicalvarieties. These are polyhedral fans associated to polynomial ideals. The
maximal cones of a Gröbner fan are in bijection with the marked reducedGröbner bases of its deﬁning ideal. The software computes all marked
reduced Gröbner bases of an ideal. Their union is a universal Gröbner
basis. The tropical variety of a polynomial ideal is a certain subcomplexof the Gröbner fan. Gfan contains algorithms for computing this complex
for general ideals and specialized algorithms for tropical curves, tropical
hypersurfaces and tropical varieties of prime ideals. In addition to theabove core functions the package contains many tools which are useful inthe study of Gröbner bases, initial ideals and tropical geometry. The fulllist of commands can be found in Appendix B. For ordinary Gröbner basis
computations Gfan is not competitive in speed compared to programs suchas CoCoA, Singular and Macaulay2.

Contents
1 Introduction
1.1 The Gröbner fan of an ideal . . . . . . . . . . . . . . . . . . . . .
1.2 Gröbner bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Algorithmic background . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Local computations . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Global computations . . . . . . . . . . . . . . . . . . . . .

5
6
7
8
8
9

∗ Research partially supported by the Faculty of Science, University of Aarhus, Danish Research Training Council (Forskeruddannelsesrådet, FUR) , Institute for Operations Research
ETH, grants DMS 0222452 and DMS 0100141 of the U.S. National Science Foundation and theAmerican Institute of Mathematics.

1

2 Installation
2.1 Installation of the gmp library . . . . . . . . . . . . . . . . . . . .
2.1.1 Installing the gmp library on Mac OS X using ﬁnk . . . .
2.2 Installation of the cddlib library . . . . . . . . . . . . . . . . . . .
2.3 Gfan installation . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 SoPlex (for the advanced user only) . . . . . . . . . . . . . . . . .

11
11
12
13
14
15

3 Using the software
3.1 Computing the Gröbner fan . . . . . . . . . . . . . . . . . . . . .
3.1.1 Exploiting symmetry . . . . . . . . . . . . . . . . . . . . .
3.2 Combining the programs . . . . . . . . . . . . . . . . . . . . . . .
3.3 Interactive mode . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Integers and p-adics . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Toric ideals and secondary fans . . . . . . . . . . . . . . . . . . .

16
16
17
17
18
19
21

4 Doing tropical computations
4.1 Tropical variety by brute force . . . . . . . . . . . . . . . . . . . .
4.2 Traversing tropical varieties of prime ideals . . . . . . . . . . . . .
4.3 Intersecting tropical hypersurfaces (partially deprecated) . . . . .
4.4 Computing tropical bases of curves . . . . . . . . . . . . . . . . .
4.5 Tropical intersection theory . . . . . . . . . . . . . . . . . . . . .
4.6 Non-constant coeﬃcients (partially deprecated) . . . . . . . . . .
4.6.1 Algebraic ﬁeld extensions of Q . . . . . . . . . . . . . . . .
4.7 Tropical prevarieties . . . . . . . . . . . . . . . . . . . . . . . . .

23
23
24
28
28
29
31
34
34

A Data formats
A.1 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Polynomial rings . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.4 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.5 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.6 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.7 Polyhedral fans . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.7.1 Data types . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.7.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.8 Polyhedral cones . . . . . . . . . . . . . . . . . . . . . . . . . . .

37
37
37
37
38
38
39
39
43
43
45

B Application list
B.1 gfan bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 gfan buchberger . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3 gfan combinerays . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.4 gfan doesidealcontain . . . . . . . . . . . . . . . . . . . . . . . . .
B.5 gfan fancommonreﬁnement . . . . . . . . . . . . . . . . . . . . . .

46
46
47
48
48
48

2

B.6 gfan fanhomology . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.7 gfan fanisbalanced . . . . . . . . . . . . . . . . . . . . . . . . . .
B.8 gfan fanlink . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.9 gfan fanproduct . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.10 gfan fansubfan . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.11 gfan genericlinearchange . . . . . . . . . . . . . . . . . . . . . . .
B.12 gfan groebnercone . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.13 gfan groebnerfan . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.14 gfan homogeneityspace . . . . . . . . . . . . . . . . . . . . . . . .
B.15 gfan homogenize . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.16 gfan initialforms . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.17 gfan interactive . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.18 gfan ismarkedgroebnerbasis . . . . . . . . . . . . . . . . . . . . .
B.19 gfan krulldimension . . . . . . . . . . . . . . . . . . . . . . . . . .
B.20 gfan latticeideal . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.21 gfan leadingterms . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.22 gfan list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.23 gfan markpolynomialset . . . . . . . . . . . . . . . . . . . . . . .
B.24 gfan minkowskisum . . . . . . . . . . . . . . . . . . . . . . . . . .
B.25 gfan minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.26 gfan mixedvolume . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.27 gfan overintegers . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.28 gfan padic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.29 gfan polynomialsetunion . . . . . . . . . . . . . . . . . . . . . . .
B.30 gfan render . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.31 gfan renderstaircase . . . . . . . . . . . . . . . . . . . . . . . . . .
B.32 gfan resultantfan . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.33 gfan saturation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.34 gfan secondaryfan . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.35 gfan stats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.36 gfan substitute . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.37 gfan symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.38 gfan tolatex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.39 gfan topolyhedralfan . . . . . . . . . . . . . . . . . . . . . . . . .
B.40 gfan tropicalbasis . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.41 gfan tropicalbruteforce . . . . . . . . . . . . . . . . . . . . . . . .
B.42 gfan tropicalcurve . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.43 gfan tropicalevaluation . . . . . . . . . . . . . . . . . . . . . . . .
B.44 gfan tropicalfunction . . . . . . . . . . . . . . . . . . . . . . . . .
B.45 gfan tropicalhypersurface . . . . . . . . . . . . . . . . . . . . . . .
B.46 gfan tropicalintersection . . . . . . . . . . . . . . . . . . . . . . .
B.47 gfan tropicallifting . . . . . . . . . . . . . . . . . . . . . . . . . .
B.48 gfan tropicallinearspace . . . . . . . . . . . . . . . . . . . . . . . .
3

48
49
49
49
49
50
50
50
51
51
52
52
53
53
54
54
54
54
54
55
55
56
57
57
58
58
58
59
59
60
61
61
61
61
62
62
62
63
63
63
63
64
65

B.49 gfan tropicalmultiplicity . . . . . . . . . . . . . . . . . . . . . . .
B.50 gfan tropicalprevariety . . . . . . . . . . . . . . . . . . . . . . . .
B.51 gfan tropicalrank . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.52 gfan tropicalstartingcone . . . . . . . . . . . . . . . . . . . . . . .
B.53 gfan tropicaltraverse . . . . . . . . . . . . . . . . . . . . . . . . .
B.54 gfan tropicalweildivisor . . . . . . . . . . . . . . . . . . . . . . . .
B.55 gfan version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

65
65
66
66
66
67
67

1

Introduction

Gfan is a software package for computing Gröbner fans [19] and tropical varieties [21] of polynomial ideals. It is an implementation of the algorithms appearing in [9] and [5]. These two papers are joint work with Tristram Bogart,
Komei Fukuda, David Speyer, Bernd Sturmfels and Rekha Thomas. A combinedpresentation can be found in [15]. For toric and lattice ideals, Gröbner fan programs already existed: TiGERS [12] and CaTS [13]. Gfan works on any ideal inQ[x1 , . . . , xn ].
Gfan is based on Buchberger’s algorithm [6] and the local basis change procedure [7]. For traversal of Gröbner fans the simplex method, the reverse searchtechnique [3] and symmetry exploiting algorithms are used. This allows enumeration of fans with millions of cones. For tropical computations these methods
have been developed further.
Gfan has been used for studying the structure of the Gröbner fan. Amongthe new results is an example of a Gröbner fan which is not the normal fan of apolyhedron [16].
The software is intended to be run in a UNIX style environment. In particular,
the software works on GNU/Linux and on Mac OS X (with some eﬀort). Gfan
uses the GNU multi-precision arithmetic library [11] and cddlib [8] for doing
exact arithmetics and solving linear programming problems, respectively. A new
feature of version 0.4 is the possibility to use the SoPlex [24] linear programming
solver which does its computations in ﬂoating point arithmetics. Gfan veriﬁes
LP certiﬁcates in exact arithmetics and falls back on cddlib in case of a rounding
error.
The ﬁrst section of this manual is a very short introduction to Gröbner fans
and algorithms for computing them. The second section describes the installation procedure of the software and the third gives some examples of how to use
it. Section 4 explains how Gfan can be used for computing tropical varieties,
prevarieties and tropical bases. More details on the data formats and programs
are given in Appendix A and B.
Note for the reader: As opposed to scientiﬁc journals the World Wide
Web has the advantage that its contents can be changed after publication. If you
have suggestions for improvements of this manual do not hesitate to let me know.
Suggestions for the installation instructions are of particular interest since I only
have access to / experience with a limited number of computer systems.

Acknowledgments: The ﬁrst version of this software was written in the fall2003 during the authors visit to the Institute for Operations Research, ETH
Zürich. Many features have been added since then. Rekha Thomas and Komei
Fukuda have been involved in the development of the Gröbner fan algorithms, see
the joint paper [9]. The tropical algorithms were developed in the joint paper [5]5with Tristram Bogart, David Speyer, Bernd Sturmfels and Rekha Thomas. The
author is thankful to the following people and institutions for initially supporting
the research: Komei Fukuda and Hans-Jakob Lüthi (Institute for Operations Research, ETH Zürich), Douglas Lind and Rekha Thomas (University of Washington, Seattle) and the American Institute of Mathematics. The research has later
been supported by University of Aarhus, University of Minnesota, TU-Berlin,
the German Research Foundation (DFG) through the institutional strategy ofGeorg-August-Universität Göttingen and The Danish Council for Independent
Research. The author would also like to thank his former advisor Niels Lauritzen
for encouraging the study in the area and the many people who have been testing,been using and helped improving the software.
Other contributors to the Gfan source code include:• Bjarne Knudsen (abstract parallel graph traverser used for mixed volume
computation and tropical prevarieties)• Anton Leykin• Yue Ren
• Josephine Yu

1.1

The Gröbner fan of an ideal

The Gröbner fan of an ideal I ⊆ k[x1 , . . . , xn ] in a polynomial ring over a ﬁeld k
is a polyhedral complex consisting of cones in Rn . We provide a short deﬁnition
and refer the reader to the papers mentioned above for details.
Deﬁnition 1.1 Let ω ∈ Rn and a ∈ Nn . We deﬁne xa := xa11 · · · xann . The ωweight of αxa with α ∈ k \ {0} is ω · a. For f ∈ k[x1 , . . . , xn ] we deﬁne its initial
form inω (f ) to be the sum of all terms in f with maximal ω-weight. For an idealI ⊆ k[x1 , . . . , xn ] we deﬁne the initial ideal to be inω (I) := hinω (f ) : f ∈ Ii.
Notice that initial ideals might not be monomial ideals. If for some ω ∈ Rn>0 wehave inω (I) = I then we say that I is homogeneous in the ω-grading. We now ﬁx
the ideal I ⊆ k[x1 , . . . , xn ] and consider the equivalence relation:u ∼ v ⇔ inu (I) = inv (I)on vectors u, v ∈ Rn . If I is homogeneous then any equivalence class contains
a positive vector. Any equivalence class containing a positive vector is convex.
Moreover, its closure is a polyhedral cone. We use the notationCω (I) := {u ∈ Rn : inu (I) = inω (I)}to denote the closure of the equivalence class containing ω.
6

Deﬁnition 1.2 [9, Deﬁnition 2.8] Let I ⊆ k[x1 , . . . , xn ] be an ideal. The Gröbner
fan of I is the collection of cones Cω (I) where ω ∈ Rn>0 together with all their
non-empty faces.
Any cone in the Gröbner fan is called a Gröbner cone. The relative interiorof any Gröbner cone is an equivalence class. The equivalence class containing
0 is a subspace of Rn called the homogeneity space of I. The Gröbner fan is apolyhedral fan; see [22] or [9]. The support of the Gröbner fan i.e. the unionof its cones is called the Gröbner region of I. If I is homogeneous then theGröbner region is Rn and, moreover, the Gröbner fan is the normal fan of thestate polytope of I; see [22] for a construction of this polytope. The lineality spaceof a polyhedral cone is deﬁned as the largest subspace contained in the cone. The
common lineality space of all cones in the Gröbner fan equals the homogeneity
space of I.
Remark 1.3 Deﬁnition 1.2 was chosen since it gives the nicest Gröbner cones.
In general our Gröbner fan does not coincide with the “restricted” Gröbner fan
nor the “extended” Gröbner fan deﬁned in [19]. The common reﬁnement (i.e.
“intersection”) of Rn≥0 and our Gröbner fan is the restricted Gröbner fan. For homogeneous ideals our deﬁnition coincides with [22, page 13] (which only contains
a deﬁnition for homogeneous ideals).

1.2

Gröbner bases

Given a term order ≺ the initial term in≺ (f ) of a polynomial f is deﬁned and,analogously to the ω-initial ideal above, so is the initial ideal in≺ (I) of an ideal I.
We remind the reader that given generators for and ideal I ⊆ k[x1 , . . . , xn ] and aterm order ≺ Buchberger’s Algorithm produces a reduced Gröbner basis G≺ (I).
This basis is unique. It is useful to introduce the notion of a marked polynomial
and a marked reduced Gröbner basis. A polynomial is marked if one of its terms
has been distinguished. When writing such a polynomial we may either underline
the distinguished term or we may by convention write the distinguished term as
the ﬁrst one listed. Gfan uses this second convention. A Gröbner basis G≺ (I) is
marked if the initial term in≺ (f ) of every polynomial f ∈ G≺ (I) has been marked
i.e. distinguished.
Example 1.4 The polynomial ideal I = hx + yi ⊆ Q[x, y] has two marked
reduced Gröbner bases: {x + y} and {x + y}. Gfan would write these Gröbner
bases as {x + y} and {y + x}.
By deﬁnition of Gröbner bases the initial ideal in≺ (I) is easily read oﬀ from themarked (reduced) Gröbner basis G≺ (I), namely, it is generated by the marked
terms. In fact, for I ⊆ k[x1 , . . . , xn ] ﬁxed the follow three ﬁnite sets are in
bijection:
7• The set of marked reduced Gröbner bases for I.
• The set of monomial initial ideals in≺ (I) with respect to term orders.
• The set of n-dimensional Gröbner cones in the Gröbner fan of I.

The map from the ﬁrst set to the second set has already been described. A monomial ideal in≺ (I) in the second set is mapped to {v ∈ Rn : inv (I) = in≺ (I)} in thethird set. Going from the ﬁrst set to the third is easy, namely the inequalities
can be read oﬀ from the exponents of the marked reduced Gröbner basis. Thus
a useful way to represent the Gröbner fan of an ideal is by the set of its marked
reduced Gröbner bases.

1.3

Algorithmic backgroundWe brieﬂy describe the algorithms implemented in Gfan for computing Gröbner
fans. The algorithms are divided into two parts, the local algorithms and theglobal algorithms. For more details we refer to [9] and [14].
1.3.1Local computations

There are two local computations that need to be done:• Given a full-dimensional Gröbner cone by its reduced Gröbner basis, weneed to ﬁnd its facets. To be precise we need to ﬁnd a normal for eachfacet.
• Given a full-dimensional Gröbner cone represented by its reduced Gröbner
basis and a normal for one of its facets we need to compute the other fulldimensional cone having this facet as a facet (if one exists). Again, thecomputed cone should be represented by a reduced Gröbner basis.

To do the ﬁrst computation we need the following theorem telling us how to readof the cone inequalities from the reduced Gröbner basis:
Theorem 1.5 Let G≺ (I) be a reduced Gröbner basis. For any vector u ∈ Rn
inu (I) = in≺ (I) ⇔ ∀g ∈ G≺ (I) : inu (g) = in≺ (g)Each g introduces a set of strict linear inequalities on u. By making these inequalities non-strict we get a description of the closed Gröbner cone of G≺ (I).
This gives us a list of possible facet normals of the cone. Linear programming
techniques are now applied to ﬁnd the true set of normals among these.
Suppose we know a reduced Gröbner basis G≺ (I) and a normal of one of its
facets. If ω is a vector in the relative interior of the facet we can compute aGröbner basis of inω (I) with respect to ≺ by picking out a certain subset of the8terms in G≺ (I), see [22, Corollary 1.9]. The initial ideal inω (I) has at most two
reduced Gröbner bases since it is homogeneous with respect to any grading given
by vectors in the n − 1 dimensional subspace spanned by the facet. The otherGröbner basis of inω (I) can be computed using a term order represented by theouter normal of the facet. A lifting step will take the Gröbner basis for inω (I)to a Gröbner basis for I representing the neighbouring cone. See [22, Subroutine3.7]. The method described above is the local change procedure due to [7]. The
procedure simpliﬁes in our case since:• We only walk through facets. Thus, the ideal inω (I) has at most two reducedGröbner bases.
• We know the facet normal. Thus, there is no reason for computing ω.

1.3.2

Global computations

We deﬁne the graph G whose set of vertices consists of all reduced Gröbner
bases of I with two bases being connected if their cones share a common facet
containing a strictly positive vector. With the two subroutines in the previous
section it is easy to do a traditional vertex enumeration of G starting from some
reduced Gröbner basis. However, for such algorithm to work it would need tostore the boundary of the already enumerated vertices to guarantee that we do
not enumerate the same vertex more than ones. For a planar graph this might
not seem too bad but as the dimension grows the boundary can contain a huge
number of elements. Storing these elements would require a lot of memory andsometimes more memory than the size of the computers RAM which would cause
the computation to slow down.
A better way to do the enumeration is by the reverse search strategy [3]. If
there is an easy rule for orienting the edges of a graph so that it has a unique sinkand no cycles it is also easy to ﬁnd a spanning tree for the graph. The reverse
search will traverse this spanning tree. The method works well for enumerating
vertices of polytopes since an orientation of the edges with respect to a genericvector will have a unique sink and no cycles. A proof in [9] shows that a similar
orientation orienting G with respect to a term order will also give an acyclicorientation with a unique sink and thus allow enumeration by reverse search.
Reverse search is the default enumeration method in Gfan .
If the ideal is symmetric we may want to do the Gröbner basis enumeration
up to symmetry. For example the ideal I = ha−bi ⊆ k[a, b] is invariant under theexchange of a and b. The ideal has two marked Gröbner bases {a−b} and {b−a},each deﬁning a full dimensional Gröbner cone in R2 . Up to symmetry they are
equal. We only want to compute one of them. In general I ⊆ k[x1 , . . . , xn ] isinvariant under all permutations of some subgroup G ⊆ Sn . Applying a permutation in G to a marked reduced Gröbner basis of I we get another marked
reduced Gröbner basis of I. Hence, G acts on the set of marked reduced Gröbner
9

bases of I. We wish to compute only one representative for each orbit. We apply
techniques similar to the ones used in [20] for computing regular triangulationsof point conﬁgurations up to symmetry. Often the number of orbits is muchsmaller than the number of reduced Gröbner bases and we save a lot of time by
not computing them all.

10

2Installation

In some situations installation of Gfan is easy while in other situations it can bevery complicated. If you are satisﬁed with an old version of Gfan, then you mightjust use the package manager on the system.
If you are using Linux and have root-access then the following might work
sudo apt-get install gfanorsudo emerge gfan
depending on your distribution and package manager. If you succeed, it is good
to know which version was installed. Run
gfan _version
Should this command fail, then you are using an old version of gfan.
As an alternative to using package managers as above you can try to locate
an executable ﬁle named “gfan” in the installation of other math software. SageMath, for example, contains a gfan executable. You also have the possibility of
installing a precompiled executables: go to the Gfan webpage, go to the binaries.html subpage, and follow the instructions there. There is however only very
few executables available.
The rest of this section eplains how to install Gfan by compiling it fromsource on a Linux/Unix-like system with a modern version of gcc. You mustalready have this compiler installed on your system to follow the instructions.
Gfan has been compiled successfully with gcc version 11.2.0. Two libraries areneeded in order to compile Gfan : cddlib and gmp. Users of Microsoft
Windows may be able to use these installation instructions if they ﬁrst install
Cygwin. A new feature in Gfan version 0.4 is the possibility to link to the
SoPlex [24] library. This does not add to the functionality of Gfan but improves
speed of the polyhedral computations. In an attempt to keep the installation
instructions simple, instructions for how to use SoPlex are given in a separate
section, Subsection 2.4. If you are a lucky Linux user it will suﬃce to follow thered part of these instructions.

2.1

Installation of the gmp library

GMP stands for GNU Multi Precision arithmetic library. This library must
be installed on your system before you can install cddlib and gfan. On some
GNU/Linux systems the library is already installed. If your system does
not already have gmp installed (which is the case if you have a usual Mac OS X
installation) follow the directions in this section.
11

IF YOU ARE USING Mac OS X AND YOU ARE NOT AN EXPERT FOLLOW THE INSTRUCTIONS IN SECTION 2.1.1 INSTEAD.
Make a new directory and download gmp-4.2.2.tar.gz fromhttp://gmplib.org/
for example by typing
cd ~mkdir tempdir
cd tempdir
wget http://ftp.sunet.se/pub/gnu/gmp/gmp-4.2.2.tar.gz
Extract the ﬁle and go to the thereby created directory:
tar -xzvf gmp-4.2.2.tar.gz
cd gmp-4.2.2
Run the conﬁgure script and specify the installation directory:./configure --prefix=$HOME/gfan/gmp
The above line speciﬁes the installation directory which in this case will be thefolder gfan/gmp in your home directory. If you already have a directory by thatname its content may be destroyed by the subsequent commands.
Compile the gmp library and install it:
makemake install
Finally, a very important step when working with gmp: Let the program perform
a self-test:
make check
The gmp installation is now complete. The gmp ﬁles can be found in your home
directory under gfan/gmp.
2.1.1

Installing the gmp library on Mac OS X using ﬁnk

This subsubsection might very well be outdated.
Current versions of Mac OS X and the gmp library have a compatibility problem
causing gmp to be compiled with errors if compiled without modiﬁcations. Thereexist packages of gmp for Mac OS X on the internet which have been compiled
incorrectly. We recommend that Mac OS users use the packages provided by ﬁnk.
Install ﬁnk by following the instructions given on the page
http://www.finkproject.org/download/index.php?phpLang=en
Having installed ﬁnk now simply typefink install gmp
The gmp library is now installed in the directory /sw.
12

2.2

Installation of the cddlib library

Cddlib [8] is a library for doing exact polyhedral computations, including solving
linear programming problems. Gfan can be compiled with cddlib version 094.
Older versions of cddlib will not work with Gfan version 0.2 or later. Notice that
cddlib itself needs gmp to compile. We give instructions on how to install cddlib.
Make a directory for the compilation process if you did not do that already:cd ~mkdir tempdir
cd tempdir
Download the ﬁle cddlib-094i.tar.gz fromhttps://people.inf.ethz.ch/fukudak/cdd_home/Cddtarfiles_pub/
into that directory. Decompress the ﬁle and change directory to the directory
being created:tar -xzvf cddlib-094i.tar.gz
cd cddlib-094i
Run the conﬁgure script. Here you have the chance of telling cddlib where toﬁnd gmp and where to install itself.
./configure --prefix="$HOME/gfan/cddlib"
CFLAGS="-I$HOME/gfan/gmp/include -L$HOME/gfan/gmp/lib"(On a single line). The above options say that cddlib should be installed inyour home directory under gfan/cddlib and where to look for gmp. If gmp was
installed by ﬁnk (see Section 2.1.1) you should run./configure --prefix="$HOME/gfan/cddlib"
CFLAGS="-I/sw/include -L/sw/lib"
instead. If gmp was already installed on your system in its default
location run./configure --prefix="$HOME/gfan/cddlib"
The content of gfan/cddlib might be destroyed by the subsequent commands.
Compile and install cddlib:
makemake install
You can now ﬁnd the installed cddlib library ﬁles in your home directory under
gfan/cddlib.
If you had super user access you could also just have run./configure
when you conﬁgured cddlib. This would cause cddlib to be installed in its default
place.
13

2.3

Gfan installation

Download the ﬁle gfan0.7.tar.gz from the Gfan homepage located at:
http://home.math.au.dk/jensen/software/gfan/gfan.html
to your folder tempdir. Extract the ﬁle and enter the new directory by typing
cd ~cd tempdir
tar -xzvf gfan0.7.tar.gz
cd gfan0.7
Gfan does not have a conﬁgure script, so you tell Gfan where to ﬁnd gmp and
cdd when you compile the program. For example you should typemakeor
make cddpath=$HOME/gfan/cddlib
ormake cddpath=$HOME/gfan/cddlib gmppath=$HOME/gfan/gmp
ormake cddpath=$HOME/gfan/cddlib gmppath=/sw
depending on where you installed the libraries to compile the program.
If the compiler complains about not being able to ﬁnd include ﬁles whencompiling, doing
make cddnoprefix=true
might help.
If you managed to compile and produce the ﬁle “gfan” you may wish to test
the compiled Gfan before installing:./gfan _test
The ﬁnal step is to install the compiled program. Typemake PREFIX=$HOME/gfan installor
make install14

depending on where you want Gfan installed. (The second line attempts to installit in /usr/local by default). If you chose to install in the directory gfan in yourhome folder you will now ﬁnd the ﬁle gfan in the subdirectory gfan/bin of yourhome folder together with a set of symbolic links, for example gfan buchberger.
You can go to the subdirectory and type ./gfan --help and ./gfan buchberger--help in the shell to test them. Or you can ask Gfan to compute the reducedGröbner bases of an ideal by typing./gfan bases
followed by, for example,
Q[a,b,c]{a^3+b^2c-a,c^2-2/3b}
Remark 2.1 If for some reason you did get gfan compiled but did not get thesymbolic links made like gfan buchberger you can still run that program by
typing gfan buchberger instead of gfan buchberger.

2.4

SoPlex (for the advanced user only)

These instructions do not work for linking with new versions of SoPlex.
Linking Gfan to SoPlex can lead to huge performance improvements. Notice
however, that the strict license of SoPlex propagates through the software toyour paper, requiring that you cite SoPlex appropriately if you choose to publish
results based on SoPlex. Furthermore, with the standard SoPlex license you are
only allowed to use SoPlex for non-commercial, academic work.
Download SoPlex here (version 1.3.2 has been used successfully):
http://soplex.zib.de/download.shtml
After download, follow the installation instructions
http://www.zib.de/Optimization/Software/Soplex/html/INST.html
After having installed SoPlex, you must tell Gfan where SoPlex is located. Do
this by editing the lines
SOPLEX_PATH = $(HOME)/math/software/soplex-1.3.2
SOPLEX_LINKOPTIONS = -lz $(SOPLEX_PATH)/lib/libsoplex.darwin.x86.gnu.opt.aof the ﬁle Makefile in your Gfan directory. Most likely you need to change
darwin to linux in the last line. Finally you need to recompile Gfan . First run
make clean and then make with the options from Subsection 2.3 together with theoption soplex=true. Then do a make install as described in Subsection 2.3.

15

3

Using the software

In this section we will explain by examples how to use the software for the mostcommon computations. Gfan consist of a set of subprograms with names likegfan bases and gfan buchberger each with a diﬀerent purpose. See Appendix
A for an explanation of the data formats and Appendix B for a full list of thevarious functions and their help ﬁles.

3.1

Computing the Gröbner fan

The program gfan bases computes the set of reduced Gröbner bases of an ideal.
To use it type in the name in the UNIX shell 1
gfan_bases
and type in a polynomial ring followed by a set of generators for the ideal
Q[a,b,c]{aab-c,bbc-a,cca-b}
For compatibility reasons the polynomial ring can be left out in which case thering is assumed to be the polynomial ring over the rationals with variable names
a, b, c, . . .. The program will output the polynomial ring and the list of reducedGröbner bases of the input ideal. In this example there are 33 such bases.
Often it is convenient to store your generators in a text ﬁle instead of typing
them in every time you use the program. You can redirect the standard input
for the program to read from a ﬁle instead of the keyboard. For example, if yourring and generators are stored in the ﬁle myinputfile.txt you would type:gfan_bases <myinputfile.txt
If you want to store the output in the ﬁle myoutputfile.txt you can redirect
the standard output as well:gfan_bases <myinputfile.txt >myoutputfile.txt
The list of reduced Gröbner bases can be transformed into a polyhedral representation of the Gröbner fan by using the program gfan topolyhedralfan as
explained in Section 3.2.
Here is another example of a polynomial ring and an ideal:
Z/3Z[x_1,x_2,x_3]{x_1^2x_2-x_3,x_2^2x_3-x_1,x_3^2x_1-x_2}
1

It is actually much more convenient to use the Emacs shell. In Emacs press Meta-x and typeshell. When you are in the Emacs shell Ctrl-up will allow you to easily reinput old polynomial
data to Gfan .

16

3.1.1

Exploiting symmetry

As explained in Subsection 1.3.2 the program can do its computations up to symmetry. In the example above we may cycle the three variables without changing
the ideal. Hence the subgroup G ⊆ Sn in Subsection 1.3.2 is the group generated by a three cycle. A way to write down the subgroup is by writing a list of
permutations that generate the subgroup:{(0,1,2),(1,2,0)}The ﬁrst permutation is the identity (which can be left out). The second permutation is three-cycle. Together they generate G. See Appendix A for more
information on how to specify the permutations.
The option --symmetry tells gfan to do its computations up to symmetry.
For example,
gfan_bases --symmetry <anotherinputfile.txt
will read the generators for the ideal and the generators for the group and performthe computation up to symmetry. The input ﬁle would have to look like this:Q[a,b,c]{aab-c,bbc-a,cca-b}{(0,1,2),(1,2,0)}The output will be a list of reduced Gröbner basis - one for each orbit.

3.2

Combining the programs

The various Gfan programs can be combined. For example, if we are interested
in the combinatorics of the Gröbner fan rather than the Gröbner bases, we canrun the command:
gfan_bases <myinputfile.txt | gfan_topolyhedralfan
The output is a polyhedral fan in the format explained in Appendix A.7.
Similarly, the command line
gfan_buchberger <myinputfile.txt | gfan_groebnercone
produces the polyhedral cone (Appendix A.8) of the computed reduced Gröbner
basis, andgfan_buchberger <myinputfile.txt | gfan_groebnercone --asfan
computes the cone as a polyhedral fan (Appendix A.7) with all faces of the cone
listed.
As another example, if we are interested in the list of monomial initial ideals
rather than the complete list of reduced Gröbner bases of an ideal we will pipe
the output of gfan bases through the program gfan leadingterms:
17Figure 1: Staircase diagrams of the monomial initial ideals in the example - up
to symmetry.
gfan_bases <myinputfile.txt | gfan_leadingterms -m
We need to use the option -m to tell gfan leadingterms that it should expect alist of Gröbner bases rather than a single Gröbner basis on its input.
If we want the union of the Gröbner bases instead we should type:gfan_bases <myinputfile.txt | gfan_polynomialsetunion >myoutputfile.txt
This will compute a universal Gröbner basis.
In three variables, if we want to draw staircase diagrams of the initial ideals
we may use the program gfan renderstaircase:
gfan_bases --symmetry <anotherinputfile.txt |gfan_renderstaircase -m -w6 -d16 >out.fig
The output ﬁle is the xﬁg ﬁle in Figure 1. To save paper we used the --symmetry
option and gave the program the ﬁle also containing the group generators as
input.
In three variables, if we want to draw the Gröbner fan - or rather draw theintersection of the 2-dimensional standard simplex with the Gröbner fan we may
use the program gfan render:
gfan_bases <myinputfile.txt | gfan_render >myoutputfile.fig
The output is shown in Figure 2. If there are more than three variables in
the polynomial ring this program can still be used but it is more diﬃcult. See
Appendix B.30.

3.3

Interactive mode

To study the local structure of the Gröbner fan the program gfan interactive
is useful. It allows the user to walk along an arbitrary path of full dimensional18

Figure 2: The Gröbner fan of the ideal intersected with the standard simplex.
Gröbner cones in the Gröbner fan of the ideal. At each step the user will specify
which facet to walk through. The input must be a marked Gröbner basis. The
program will minimise and autoreduce if necessary to get the reduced Gröbner
basis. For example running the program
gfan_interactivewith input
Q[a,b,c]{c^15-c,b-c^11,a-c^9}
will give us a list of facets to walk through. (One way to get a starting Gröbner
basis is by using the program gfan buchberger.) In this case only two ﬂips are
possible, since the third wall does not lead to a new Gröbner cone. – The wall ison the boundary of the Gröbner region. We may choose any of the two remaining
facets by typing in an index (a number) followed by < enter >. See Appendix
B.17 for more options.

3.4

Integers and p-adics

Gfan handles two settings in which the usual division and Buchberger algorithms
do not suﬃce. These are ideals in Z[x1 , . . . , xn ] and Q[x1 , . . . , xn ], where, in thelatter setting, the p-adic valuation is taken into account when deﬁning initial
ideals.
19

At the moment these two settings are handled by the commands gfan overintegers
and gfan padic. They allow the computation of Gröbner bases, initial ideals,
Gröbner cones (or polyhedra) and Gröbner fans (or complexes). In this section
we give two examples. Use the --help option to get the full documentation.
Example 3.1 To compute the Gröbner fan of [22, Example 3.9], with the ideal
considered in the ring Z[a, b, c] we run the command
gfan_overintegers --groebnerFan -g --log1
onQ[a,b,c]{a^5+b^3+c^2-1, b^2+a^2+c-1, c^3+a^6+b^5-1}
Since the type-system of Gfan does not understand Z[a,b,c] we need to trick Gfanby specifying the ring Q[a, b, c] when running gfan overintegers. From the output
we conclude that the ideal has 1659 reduced Gröbner bases over the integers (asopposed to 360 over a ﬁeld of characteristic 0).
Example 3.2 To compute the reduced Gröbner basis of I = hx1 +2x2 −3x3 , 3x2 −
4x3 + 5x4 i ⊆ Q[x1 , . . . , x4 ] with respect to the vector (1, 0, 0, 1) (tie-broken lexicographically) and with Q having the 2-adic valuation, we run
gfan_padic --groebnerBasis -p2
on the input
Q[x1,x2,x3,x4]{
x1+2x2-3x3,
3x2-4x3+5x4}(1,1,0,0,1)
The ﬁrst coordinate of the input vector is a 1, since padic requires “homogenized” weight vectors. This is Example 2.4.3 in [17]. The division algorithm
implemented in Gfan used for this computation was proposed by Maclagan. To
ﬁnd all initial ideals, we can use a combination of gfan padic --groebnerBasis,
gfan combinerays --section CONES -i filename and gfan padic --initialIdeals-m.
Notice that the Gröbner complex of I, where valuation is taken into account(see Maclagan-Sturmfels), is not a fan. The output of gfan padic --groebnerComplex,
however, will be a fan. To get the Gröbner complex we need to intersect the fanwith the hyperplane ω0 = 1.
NOTICE THAT padic USES THE MINIMUM CONVENTION AT THE
MOMENT - in order to be consistent with Maclagan and Sturmfels.
20

3.5

Toric ideals and secondary fans

Gfan is a replacement of the software CaTS [13] which computes Gröbner fans oftoric and lattice ideals. For convenience a program for computing lattice ideals
has been added to Gfan. To compute the lattice ideal of the lattice generated by(2, −1, 0) and (3, 0, −1) we run:
gfan_latticeideal{(2,-1,0),(3,0,-1)}
Gfan will transform the generators into binomials and compute the saturationof the ideal they generate by the product of all variables. The computation is
independent of the characteristic of the ﬁeld.
If on the other hand we wish to compute the toric ideal of a vector conﬁguration given by the columns of the 1 × 3-matrix (1, 2, 3) we run
gfan_latticeideal -t{(1,2,3)}More rows can be added to the matrix if we want.
The choice of the term “vector conﬁguration” is intentional and nonstandard.
The reason for this will become clear later in this section. In Gfan terminology apoint conﬁguration is reserved for the collection of points we have before we add
a row of ones to construct a projective toric variety. By adding the row of ones
the point conﬁguration is turned into a vector conﬁguration. Notice that scalinga vector of a vector conﬁguration may change its toric ideal.
Computing toric ideals Gfan is not optimal. If one needs to do big examples
the software 4ti2 [1] is recommended.
For a toric ideal the radical of a monomial initial ideal is the Stanley-Reisner
ideal of a regular triangulation of the point conﬁguration, see [22]. Hence thetoric Groebner fan is a reﬁnement of the secondary fan, indexing all regulartriangulation of the point conﬁguration.
The secondary fan of the vector conﬁguration {(1, 0), (1, 1), (1, 2), (1, 3)} canbe computed by typing
gfan_secondaryfan{(1,0),(1,1),(1,2),(1,3)}
Comparing this to the ﬁner Gröbner fan of the corresponding toric ideal which
you get by doing
gfan_transposematrix | gfan_latticeideal -t | gfan_bases | gfan_topolyhedralfan{(1,0),(1,1),(1,2),(1,3)}

you realise that three monomial initial ideals of the toric ideal have the sameradical, while four monomial initial ideals pairwise have the same radical.
21

The secondary fan computation was added for convenience. An alternative
is to use TOPCOM [20]. Notice however, that the vector conﬁgurations forgfan secondaryfan do not have to be pointed. This means that all combinatorial
types of polytopes with a ﬁxed set of normals can be easily enumerated. This is
not possible with TOPCOM.

22

4

Doing tropical computations

This section follows the max convention for tropical arithmetic. For the nonconstant coeﬃcient case tropical varieties are deﬁned as in [18] and [15].
In this section we explain how to use Gfan to do tropical computations. Fora ﬁxed ideal I ⊆ k[x1 , . . . , xn ] the set of all faces of all full-dimensional Gröbner
cones is a polyhedral complex which we call the Gröbner fan of I. For tropicalcomputations the lower dimensional cones of the complex will be of our interest.
In general every Gröbner cone is of the form:Cω (I) := {ω ′ ∈ Rn : inω′ (I) = inω (I)}.
We deﬁne the tropical variety T (I) of an ideal I to be the the set of all ωsuch that inω (I) does not contain a monomial. If the ideal I is homogeneous withrespect to a positive grading, then the Gröbner cones cover all of Rn and T (I)is a union of Gröbner cones. Thus for a homogeneous ideal the tropical variety
gets the structure of a polyhedral fan which it inherits from the Gröbner fan. We
therefore also deﬁne the tropical variety T (I) to be the collection of all Gröbner
cones Cω (I) such that inω (I) is monomial-free.
We start by noticing that for computational purposes it is no restriction to
only consider the case of a homogeneous ideal:
Lemma 4.1 [15, Lemma 6.2.5] Let I ⊆ k[x1 , . . . , xn ] be an ideal generated byhf1 , . . . , fm ∈ k[x1 , . . . , xn ]. Let J = hf1h , . . . , fm
i ⊆ k[x0 , . . . , xn ]. Then inω (I)is monomial-free if and only if in(0,ω) (J) is monomial-free where ω ∈ Rn . In
particular we have the following identity of sets in Rn+1 :{0} × T (I) = T (J) ∩ ({0} × Rn ).
Here f h denotes the homogenization of the polynomial f . The homogenizationof a list of polynomials can be computed by the program gfan homogenize.
Notice that the lemma only requires the generators to be homogenized as a setof polynomials and not in the sense of a polynomial ideal.
The tropical algorithms implemented in Gfan are explained in [5]. Noticethat Gfan follows the usual conventions for signs of weight vectors deﬁning initial
forms while [5] uses opposite signs. This means that Gfan is compatible with themax-plus convention whereas [5] is compatible with the min-plus convention.

4.1

Tropical variety by brute force

The command gfan tropicalbruteforce will compute all Gröbner cones of ahomogeneous ideal and for each check if its initial ideal contains a monomial. The
output is the tropical variety of the ideal. Since the tropical variety is usually23

much smaller than the Gröbner fan this is a rather slow method for computing
the tropical variety. The line
gfan_buchberger | gfan_tropicalbruteforce
run on the input
Q[a,b,c,d,e,f,g,h,i,j]{bf-ah-ce,bg-ai-de,cg-aj-df,
ci-bj-dh,fi-ej-gh}
produces a tropical variety of the input ideal in a few minutes as a polyhedralfan, see Section A.7. We use gfan buchberger since gfan tropicalbruteforce
requires its input to be a marked reduced Gröbner basis.
Remark 4.2 Notice that if k ′ ⊇ k is a ﬁeld extension and I ⊆ k[x1 , . . . , xn ] an
ideal then T (I) = T (hIik′ [x1 ,...,xn ] ) as a polyhedral fan. This identity follows sinceboth objects can be computed by Gröbner basis methods and Gröbner bases are
independent of such ﬁeld extensions. The same argument of course also applies
to the Gröbner fans of the two ideals.

4.2

Traversing tropical varieties of prime ideals

Let I ⊆ C[x1 , . . . , xn ] be a homogeneous monomial-free prime ideal of dimension d. By the Bieri Groves Theorem [4] the tropical variety of I is a pure ddimensional polyhedral fan. It is connected in codimension one ([5, Theorem 14])and can be traversed by Gfan. Let ω be a relative interior point of a d-dimensionalGröbner cone in the tropical variety of I. Fix some term order ≺. Gfan represents Cω (I) by the pair of marked reduced Gröbner bases (G≺ω (inω (I)), G≺ω (I)).
To compute the tropical variety of an ideal we must begin by ﬁnding a starting ddimensional Gröbner cone. For this gfan tropicalstartingcone is used. After
having computed a starting cone we use the program gfan tropicaltraverse
to traverse the tropical variety. We illustrate the procedure with an example.
Remark 4.3 Gfan does its computations over Q and thus the input should be
an ideal generated by polynomials in Q[x1 , . . . , xn ]. The assumption that I is
an ideal in C[x1 , . . . , xn ] is needed since by “prime ideal” in the above we mean
“prime ideal in the polynomial ring over the algebraically closed ﬁeld C”. If I is aprime ideal in Q[x1 , . . . , xn ] we do not know that its tropical variety is connected.
In Section 4.6 we address the problem of specifying non-rational coeﬃcients.
24

Example 4.4 Let I ⊆ Q[a, . . . , o] be the ideal generated by the relations on the
2 by 2 minors of a 2 by 6 generic matrix. In C[x1 , . . . , xn ] the ideal I generates aprime ideal. To get a starting cone for the traversal of T (I) we run the command
gfan_tropicalstartingconeon the input
Q[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]{bg-aj-cf, bh-ak-df, bi-al-ef, ck-bm-dj,
cl-ej-bn, ci-eg-an, dn-co-em, dl-bo-ek,
gk-fm-jh, gl-fn-ij, hl-fo-ik, kn-jo-lm,}

ch-am-dg,
di-ao-eh,hn-im-goand get a pair of marked reduced Gröbner bases
Q[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]{l*m+j*o, i*m+g*o, i*k-h*l, i*j-g*l, h*j-g*k,
e*m+c*o, e*k+b*o, e*j-c*l, e*h+a*o, e*g-c*i,
c*k-b*m, c*h-a*m, b*i-a*l, b*h-a*k, b*g-a*j}{
l*m-k*n+j*o, i*m-h*n+g*o, i*k-h*l+f*o, i*j-g*l+f*n, h*j-g*k+f*m,e*m-d*n+c*o, e*k-d*l+b*o, e*j-c*l+b*n, e*h-d*i+a*o, e*g-c*i+a*n,
c*k-d*j-b*m, c*h-d*g-a*m, b*i-e*f-a*l, b*h-d*f-a*k, b*g-c*f-a*j}
This takes about a second. We store the output in the ﬁle grassmann2 6.cone
for later use. Since I has many symmetries we add the following lines describing
the symmetry group to the end of the ﬁle:{(0,8,7,6,5,4,3,2,1,14,13,11,12,10,9),(5,6,7,8,0,9,10,11,1,12,13,2,14,3,4)}
We are ready to traverse T (I). We run the following command
gfan_tropicaltraverse --symmetry <grassmann2_6.cone
The computation takes a few (two - three) minutes. The output looks like this:_application PolyhedralFan_version 2.2_type PolyhedralFan
AMBIENT_DIM
25

15
DIM
9
LINEALITY_DIM
6
RAYS
0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 # 0
0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 # 1
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 # 2
0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 # 3
0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 # 4
0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 # 5
0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 # 6
0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 # 7
0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 # 8
0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 # 9
0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 # 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 # 11
0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 # 12
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 # 13
0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 # 14
0 0 0 -1 -1 -1 -1 0 0 -1 0 0 0 0 -1 # 15
-1 -1 0 0 0 -1 0 0 0 0 0 0 -1 -1 -1 # 16
-1 0 0 0 -1 0 0 0 -1 -1 -1 0 -1 0 0 # 17
1 1 0 0 0 1 2 2 0 2 2 0 1 1 1 # 18
1 0 2 2 1 0 0 0 1 1 1 0 1 2 2 # 19
0 0 0 1 1 1 1 0 0 1 2 2 2 2 1 # 20
1 1 0 2 2 1 0 2 2 0 0 0 1 1 1 # 21
1 2 2 0 1 2 2 0 1 1 1 0 1 0 0 # 22
2 2 0 1 1 1 1 0 2 1 0 2 0 0 1 # 23
0 -1 0 -1 0 0 -1 0 -1 0 -1 0 0 -1 0 # 24
N_RAYS
25
LINEALITY_SPACE
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 1 0 0 1 0 1 1
0 0 0 1 0 0 0 1 0 0 1 0 1 0 1
0 0 1 0 0 0 1 0 0 1 0 0 1 1 026

0 1 0 0 0 0 -1 -1 -1 0 0 0 -1 -1 -1
1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1
ORTH_LINEALITY_SPACE
0 0 0 0 0 0 0 0 0 0 1 -1 -1 1 0
0 0 0 0 0 0 0 0 0 1 0 -1 -1 0 1
0 0 0 0 0 0 0 1 -1 0 0 0 -1 1 0
0 0 0 0 0 0 1 0 -1 0 0 0 -1 0 1
0 0 0 0 0 1 0 0 -1 0 0 -1 -1 1 1
0 0 0 1 -1 0 0 0 0 0 0 0 -1 1 0
0 0 1 0 -1 0 0 0 0 0 0 0 -1 0 1
0 1 0 0 -1 0 0 0 0 0 0 -1 -1 1 1
1 0 0 0 -1 0 0 0 -1 0 0 0 -1 1 1
F_VECTOR
1 25 105 105
After this follows a list of cones and maximal cones. Every maximal cone has an
associated multiplicity which is also listed.
The output says that the tropical variety has dimension 9. Modulo the 6dimensional homogeneity space this is reduced to a 3-dimensional complex in
R9 and thus we may think of the tropical variety as a 2-dimensional polyhedral
complex on the 8-sphere in R9 . This complex is simplicial and has 105 maximal
cones.
The extreme rays (modulo the homogeneity space) are labeled 0, . . . , 24. In
the cone lists the cones are grouped together according to dimension and orbit
with respect to the speciﬁed symmetries. See Section A.7 for more information
on how to read the polyhedral fan format.
While traversing the variety the program gfan tropicaltraverse only computes d and (d − 1)-dimensional cones. The other cones are extracted after
traversing. Also the symmetries are expanded. Sometimes extracting all cones
is time consuming and one is only interested in the high dimensional cones up
to symmetry. These can be output using the option --noincidence. In thatcase the output would be a list of orbits for maximal cones and a list of orbits
for codimension one cones. It is also listed how these cones are connected taking
symmetry into account. In general that format is rather diﬃcult to read.
A ﬁnal remark about gfan tropicaltraverse is that the polyhedral structure of the complex comes from the Gröbner fan. For some ideals it is possible
to ﬁnd polyhedral fans covering the tropical variety with fewer cones.

27

4.3

Intersecting tropical hypersurfaces (partially deprecated)

Note: While the content of this subsection is still correct, the command
gfan tropicalprevariety, new in gfan0.7 and presented in Section 4.7,
is generally much faster than gfan tropicalintersection. The old functionality is kept for compatability - in particular regarding groupingof its output and handling of symmetry and stable intersections.
The tropical variety of a principal ideal is called a tropical hypersurface. A
tropical prevariety is a ﬁnite intersection of tropical hypersurfaces or, to be precise, the intersection of the support set of these hypersurfaces. In Gfan the intersection is represented by the common reﬁnement of the tropical hypersurfaces.
The program gfan tropicalintersection can compute such intersections.
Example 4.5 To compute the intersection of the tropical hypersurfaces T (ha +b + c + 1i) and T (ha + b + 2ci) we run
gfan_tropicalintersectionon
Q[a,b,c]{a+b+c+1,a+b+2c}
The output is a polyhedral fan whose support is the intersection. The balancing
condition for this fan is not satisﬁed which implies that it is not a tropical variety.

4.4

Computing tropical bases of curves

In Gfan an ideal I is said to deﬁne a tropical curve if k[x1 , . . . , xn ]/I has Krull
dimension equal to or one larger than the dimension of the homogeneity space of
I. A tropical basis of I is a ﬁnite generating set for the ideal such that the tropicalvariety deﬁned by I (as a set) is the intersection of the tropical hypersurfaces of
the generators. A tropical basis always exists [5]. The program gfan tropicalbasis
computes a tropical basis for an ideal deﬁning a tropical curve.
Example 4.6 Again we consider the ideal ha + b + c + 1, a + b + 2ci. We noticethat this ideal deﬁnes a curve since the Krull dimension is 1 and the dimensionof the homogeneity space is 0. In the example above we saw that the listed set
is not a tropical basis. We run
gfan_tropicalbasis -hon
Q[a,b,c]{a+b+c+1,a+b+2c}
28

to get some tropical basis
Q[a,b,c]{-1+c,2+b+a}
We needed the option -h here since the ideal was not homogeneous. If we run
gfan tropicalintersection on the output we see that the tropical variety consists of three rays and the origin.

4.5

Tropical intersection theory

Gfan contains a few experimental programs for doing computations in tropicalintersection theory. In [2, Deﬁnition 3.4] the tropical Weil divisor of a tropicalrational function on a (tropical) k-cycle in Rn is deﬁned. This divisor can becomputed in Gfan. However, Gfan and [2] do not agree on the basic deﬁnitions
in tropical geometry. For example the deﬁnition of a fan is diﬀerent. Here wewill adjust the necessary deﬁnitions to the Gfan conventions. A tropical k-cycle
will be a pure (rational) polyhedral fan F of dimension k in Rn with weights
which is balanced in the following sense: To every k-dimensional facet C weassign a weight (or multiplicity) mC ∈ Z. The vector space Rn comes with
its standard lattice Zn . For a k − 1-dimensional ridge R ∈ F and a facet C
in its star2 in F corresponding to a cone L in the link3 of R in F , the semigroup L ∩ Zn /spanR (R) ∩ Zn ⊆ Zn /spanR (R) ∩ Zn is isomorphic to N. DeﬁneuC/R ∈ Zn /span(R) ∩ Zn as the element identiﬁed with 1 ∈ N. The balancing
condition at R is thatX
mC uC/R = 0.
C∈F :R⊂C

For a (weighted) fan to be a tropical cycle this must hold at every ridge R.
It remains to deﬁne what a tropical rational function is. Take a polyhedral
fan F ′ and associate to each of its maximal cones a linear form. When evaluatinga point x in the support of F ′ simply evaluate the linear form of cone containing
x. If this gives a well-deﬁned function we call this function a tropical rational
function. When computing Weil divisors we will require that the supports satisfy
supp(F ) ⊆ supp(F ′ ). There will be no further restriction on the polyhedral
structure.
For a deﬁnition of the Weil divisor itself we refer to [2, Deﬁnition 3.4]. Here
we just mention that it again is a cycle of dimension one lower.
2

the smallest polyhedral subcomplex of F containing all faces of F containing R.
take an ǫ-ball around a relative interior ω ∈ R and intersect it with F . Translating the ballto the origin and scaling the intersection to inﬁnity we get the link of R in F .
329

To demonstrate the Gfan features we recompute [2, Example 3.10]. An easy
way to generate the k-cycle of that example is to compute it as a hypersurface.
Since the paper is using min and Gfan is using max we need to change thepolynomial from the paper such that the Newton polytope is ﬂipped:
gfan_tropicalhypersurface > tmpfile1.poly
Q[x_1,x_2,x_3]{x_2x_3+x_1x_3+x_1x_2+x_1x_2x_3}
The weights/multiplicities are stored in the MULTIPLICITIES section of thePolymake ﬁle.
It is harder specifying the rational function. We make the following ﬁle andcall in func.poly.
_application PolyhedralFan_version 2.2_type PolyhedralFan
AMBIENT_DIM
3
DIM
2
LINEALITY_DIM
0
RAYS
1 0 0 # 0
0 1 0 # 1
0 0 1 # 2
-1 -1 -1 # 3
1 1 0 # 4
-1 -1 0 # 5
N_RAYS
6
LINEALITY_SPACEORTH_LINEALITY_SPACE
1 0 0
0 1 0
0 0 1
MAXIMAL_CONES{3 5} # Dimension 2
{5 2}
{0 2}
{1 2}
{1 3}

30

{0 3}{1 4}{0 4}
MULTIPLICITIES
1
1
1
1
1
1
1
1
RAY_VALUES
0
0
0
1
-1
0
LINEALITY_VALUES

Instead of specifying the linear function on each maximal cone we have to specify
its values on each of the rays in the fan and each of the generators of the lineality
space. Then Gfan will automatically interpolate the function. Since the lineality
space of the fan is empty we leave the LINEALITY VALUES section empty.
We now compute the Weil divisor:
gfan_tropicalweildivisor -i1 tmpfile1.poly -i2 func.poly >tmpfile2.poly...and compute the Weil divisor again as in [2]...
gfan_tropicalweildivisor -i1 tmpfile2.poly -i2 func.poly >tmpfile3.poly

We get a fan with the origin being the only cone. It has multiplicity −1:
MULTIPLICITIES-1# Dimension 0
There is another useful command for computing polyhedral fans for rational
functions. The command gfan tropicalfunction takes a polynomial and turns
it into a fan representing its tropicalization which is a tropical rational function.

4.6

Non-constant coeﬃcients (partially deprecated)

The easiest way to compute tropical prevarieties is by using the command gfan tropicalprevariety introduced in gfan0.7. See Section 4.7.
The current section is kept for compatibility reasons.
31In tropical geometry it is common to take the valuation of C{{t}} into accountwhen deﬁning the tropical variety of an ideal in C{{t}}[x1 , . . . , xn ]. Here C{{t}}denotes the ﬁeld of Puiseux series. The valuation val(p) of a non-zero Puiseux
series p is the degree of its lowest order term.
Deﬁnition 4.7 For ω ∈ Rn the t-ω-degree of a term cta xv with c ∈ C∗ , a ∈ Q
and v ∈ Zn is deﬁned as −val(cta ) + ω · v = −a + ω · v. The t-initial formt-inω (f ) ∈ C[x1 , . . . , xn ] of a polynomial f ∈ C{{t}}[x1 , . . . , xn ] is the sum of allterms in f of maximal t-ω-weight but with 1 substituted for t.
Remark 4.8 Notice that since t has t-ω-degree −1, the maximal t-ω-weight isattained by a term if the polynomial is non-zero. Furthermore, only a ﬁnite
number of terms attain the maximum. Therefore, it makes sense to substitutet = 1 and consider the ﬁnite sum of terms as a polynomial in C[x1 , . . . , xn ].
Example 4.9 Consider f = (1 + t) + t2 x + tx2 ∈ C{{t}}[x1 , . . . , xn ]. Let ω =( 21 ) ∈ R1 . Then t-inω (f ) = 1 + x2 . For any other choice of ω the t-initial form isa monomial.
Deﬁnition 4.10 Let I ⊆ C{{t}}[x1 , . . . , xn ] and ω ∈ Rn . The t-initial ideal of
I with respect to ω is deﬁned as:
t-inω (I) := ht-inω (f ) : f ∈ Ii ⊆ C[x1 , . . . , xn ].
Deﬁnition 4.11 Let I ⊆ C{{t}}[x1 , . . . , xn ] be an ideal. The tropical variety of
I is the set
T ′ (I) := {ω ∈ Rn : t-inω (I) is monomial-free}.
We use the notation T ′ (I) to avoid contradicting our original deﬁnition of thetropical variety of an ideal in the polynomial ring over a ﬁeld.
Proposition 4.12 [18, Proposition 7.3] Let I ⊆ C[t, x1 , . . . , xn ] be an ideal, J =hIiC{{t}}[x1 ,...,xn ] and ω ∈ Rn . Then t-inω (I) = t-inω (J).
Remark 4.13 For f ∈ C[t, x1 , . . . , xn ] we have t-inω (f ) = (in(−1,ω) (f ))|t=1 . Consequently, for I ⊆ C[t, x1 , . . . , xn ] we have t-inω (I) = (in(−1,ω) (I))|t=1 . In order todecide if t-inω (I) contains a monomial we may simply decide if the initial idealin(−1,ω) (I) contains a monomial. As a corollary we get
T (I) ∩ ({−1} × Rn ) = {−1} × T ′ (J).
In fact this gives a method for computing the tropical variety as a set of any
ideal J ⊆ C{{t}}[x1 , . . . , xn ] generated by elements in the polynomial ring overthe ﬁeld of rational functions Q(t)[x1 , . . . , xn ] in Gfan by clearing denominatorsand intersecting the result with the t = −1 plane. (We remind the reader that
Lemma 4.1 shows that for computational purposes it is no restriction if I is nothomogeneous.)
32

Intersecting the tropical variety with the t = −1 plane can with some difﬁculty be done by hand. If the tropical (pre)-variety has been computed withgfan tropicalintersection then it is also possible to let Gfan do the intersection. What Gfan does is to compute the common reﬁnement of the fan with the
fan consisting of the halfspace t ≤ 0 and its proper face. Of course this does notremove the cones in the t = 0 plane, but they are easily removed by hand. We
illustrate the procedure by an example.
Example 4.14 Exercise 2 in Chapter 9 of [23] asks us to draw the variety deﬁned
by the tropical polynomial f = 1x2 + 2xy + 1y 2 + 3x + 3y + 1. If we tropicallydivide this polynomial by 3 we get f ′ := f /3 = −2x2 − 1xy − 2y 2 + 0x + 0y + −2
which deﬁnes the same tropical variety. This variety equals the variety deﬁned
by the polynomial g = t2 x2 + txy + t2 y 2 + x + y + t2 ∈ C{{t}}[x, y]. Notice thatf ′ is the tropicalisation of g.
According to Remark 4.13 above the we may compute T ′ (hgi) by computing
the variety of ht2 x2 + txy + t2 y 2 + x + y + t2 i ⊆ C[t, x, y] and intersecting it withthe hyperplane t = −1. Running
gfan_tropicalintersection --tplaneonQ[t,x,y]{t^2x^2+txy+t^2y^2+x+y+t^2}
we getRAYS
0 -1 0 # 0-1 2 1 # 1
0 1 1 # 2
-1 1 1 # 3-1 -2 -2 # 4
0 0 -1 # 5-1 1 2 # 6
MAXIMAL_CONES{3 4} # Dimension 2
{2 6}
{1 3}
{1 2}
{3 6}
{4 5}
{0 4}
{0 6}
{1 5}
33

2
6
3

1

0

4

5

Figure 3: The tropical variety deﬁned by the tropical polynomial in Example 4.14.
among other information. We can now draw the two-dimensional picture asked
for in the exercise. The rays with non-zero ﬁrst coordinate become points in the
picture. (If the ﬁrst coordinate is not −1 scaling is required to get the rationalx, y-coordinates.) The rays with zero ﬁrst coordinate become directions. The
maximal cones show how to connect the rays; see Figure 3. Notice that some of
the connections could have been “at inﬁnity”.
4.6.1

Algebraic ﬁeld extensions of Q

Ignoring time, memory usage and overﬂows Gfan can compute the tropical variety
T ′ (I) of any ideal I ⊆ C{{t}}[x1 , . . . , xn ] generated by elements of Q(t)[x1 , . . . , xn ].
This is a consequence of the following lemma:
Lemma 4.15 [18, Lemma 3.12] Let k be a ﬁeld and M = hmi ⊆ k[a] a maximal
ideal where m is not a monomial. Let I ⊆ (k[a]/M )[x1 , . . . , xn ] be an ideal. For
ω ∈ Rn we haveinω (I) contains a monomial ⇐⇒ in(0,ω) (ϕ−1 (I)) contains a monomial
where ϕ : k[a, x1 , . . . , xn ] → (k[a]/M )[x1 , . . . , xn ] is the homomorphism taking
elements to their cosets.

4.7

Tropical prevarieties

As explained earlier, a tropical prevariety is deﬁned to be an intersection of ﬁnitely
many tropical hypersurfaces. Such intersection can be computed by either the oldcommand gfan tropicalintersection or the new command gfan tropicalprevariety
introduced in Gfan version 0.7.

34

There are several choices to be made when deﬁning the tropical prevariety
of a list of polynomials in C{{t}}[x1 , . . . , xn ], for example whether t should havevaluation +1 or −1, whether the value group should be ordered in the positive or
negativ direction (and whether gfan should “cone over” the complex at x0 = −1
or x0 = 1 to get the fan-like output).
However, the most sensible choices are just to have the equation
T (I) ∩ Qn = val(V (I))
satisﬁed, where val is cooridinate-wise valuation. This leaves the choice of thinking of C{{t}} as having increasing exponents in t (min) or decreasing exponents
in t (max) and taking valuation to be t-exponent of the leading term of a series.
In addition to these choices, part of the literature mixes max and min conventions to have increasing Puiseux series while following conventions of the (global)Gröbner fan theory (using outer normals). This is consistent with Deﬁnition 4.7.
For these choices the following equation holds:
T (I) ∩ Qn = −val(V (I)).
In the following we illustrate these choices on some examples. Note that the
Gfan parser only understands ordinary polynomials at the moment. So although
we can specify the coeﬃcient ﬁeld to be rational functions in t, only polynomialof C(t)[x1 , . . . , xn ] ⊂ C{{t}}[x1 , . . . , xn ] that are actually in C[t, x1 , . . . , xn ] canbe parsed at the moment, leading to some inconvenience. Moreover, specifying
for example p-adic valuations for ideals in Q[x1 , . . . , xn ] is not possible at the
moment.
The command gfan tropicalprevariety has two options to set max/min conventions:--mint--minxExample 4.16 (Default: Max, max) The Puiseux series are decreasing in texponent and T (I) ∩ Qn = val(V (I)) is satisﬁed. This convention is compatible
with most of Gfan , but seems to not be used much in the literature. One place
it is used is in the introduction of [5]. In the following note that it would not be
possible for Gfan to parse (t4+1)x while t4x+1x can be parsed.
gfan _tropicalprevariety --usevaluation
Q(t)[x]{t+t4x+1x+tx3}
gives as part of the output
RAYS
1 -3 # 0
2 3 # 1
35

The tropical prevariety is {−3, 32 }.
Example 4.17 (Max convention, increasing t-exponents) We now change
to the deﬁnition that is compatible both with the Gröbner basis convention (outernormals) and increasing t-exponents. This convention was used in [23], [18]and [15] and satisﬁes T (I) ∩ Qn = −val(V (I)).
gfan _tropicalprevariety --usevaluation --mint
Q(t)[x]{t+t4x+1x+tx3}
gives as part of the output
RAYS
1 -1 # 0
2 1 # 1
The tropical prevariety is {−1, 12 }.
Example 4.18 (Min convention, increasing t-exponents) Our ﬁnal example illustrates the most common convention, since this is the one used in thetropical book by Maclagan and Sturmfels [17]. It was also used in [21]. The convention has the advantage that Puiseux series are increasing in t and the equation
T (I) ∩ Qn = val(V (I)) is satisﬁed.
gfan _tropicalprevariety --usevaluation --mint --minx
Q(t)[x]{t+t4x+1x+tx3}
gives as part of the output
RAYS
1 1 # 02 -1 # 1
The tropical prevariety is {1, − 21 }.
More interesting examples are obtained by introducing more variables and polynomials, but here we only wished to demonstrate various conventions.
To speed up computation the arithmetic can be changed to machine-integer
using for example option --bits64. Note that in that case overﬂow checking is
not completely implemented.
If --usevaluation is not speciﬁed, then the output lives in a space of dimension one lower. If a coeﬃcient ﬁeld without a default valuation is speciﬁed in the
input, then the trivial valuation is used.

36

A

Data formats

In this section we describe how polynomials, lists, marked Gröbner bases etc.
are represented as ASCII character strings. These strings will be input to theprograms by typing or by redirecting the standard input and be output by the
program on the standard output which may be the screen, a pipe or a ﬁle. Usuallyﬁles are used for input. For example,
gfan_bases < inputfile.txt > outputfile.txt
will read its input from inputfile.txt and write its output to outputfile.txt.
The following is an example of how to use pipes for computing a universal Gröbner
basis of the input:
gfan_bases < inputfile.txt | gfan_polynomialsetunion > outputfile.txt
In general spaces and newlines in the input are ignored, but for the polyhedral
formats described in Section A.7 and Section A.8 the rules are diﬀerent.

A.1

FieldsTwo kinds of ﬁelds are supported:• The ﬁeld Q of rationals which is represented by the string “Q”.
• Fields of the form Z/pZ where p is a prime number. These ﬁelds are represented by text strings “Z/pZ” where p is the prime number. For example“Z/3Z” or “Z/17Z”. In Gfan the prime number p must be less than 32749.

A.2

Variables

A variable is denoted by its name which is an string of characters. The exact
rules for which names are allowed have not been decided on in this version of
Gfan and therefore Gfan accepts most names. However, white spaces, commas
and “]” are not allowed as characters in the name. Furthermore one should notchoose variable names such that one name is a starting substring of an other –don’t choose names such as “x1” and “x” in the same polynomial ring.

A.3

Polynomial rings

A polynomial ring is represented ﬁrst by a ﬁeld and then by a list of variablenames. The list begins with “[” and ends with “]”. Names are separated
by commas. The ordering of the variables matters as this is also the ordering used for the entries of for example weight vectors. Examples: “Z/2Z[a,b]”
and “Q[x 1,x 2,y1,y2]”.
37

A.4

Polynomials

Coeﬃcients in the ﬁeld are given as fractions. A coeﬃcient equals its numerator
multiplied by the inverse of the denominator. The numerator and denominatorthemselves are given by an integer in Z which is mapped to the ﬁeld by the homomorphism sending 1 ∈ Z to 1 in the ﬁeld. The ’/’ character and the denominatorcan be left out if the denominator is 1. If a ﬁeld with non-zero characteristic waschosen one should be careful that the denominator is not 0.
Monomials are written in the following formats:• a^4dc• a4dc• aaadac

The monomial 1 cannot be written without writing it as a term in the usual
way “1”. Any other term is either a monomial or a coeﬃcient and a monomial.
A polynomial is a list of terms separated by +. The + may be left out if thenumerator of the next monomial is negative.
That description did not cover every detail. Here is an example:
hello world - 3/8 a2+23abcge^4 +1
In our usual notation we would write it like this: dehl3 o2 rw + 1 + 23abce4 g − 38 a2 .
It is important to note that the ﬁrst term written in a polynomial isdistinguished from the other terms in the polynomial. This is usefulwhen specifying marked Gröbner bases.

A.5

Lists

A list begins with a ’{’ or a ’(’, contains elements separated by ’,’ and is ended
by a ’}’ or a ’)’. Diﬀerent types of lists may be needed when specifying input for
the various programs:
An integer vector is a list of integers.
A list of integer vectors is a list of integer vectors. Such lists are used forexample when specifying generators for subgroups of Sn .
A polynomial list (or a polynomial set) is a list of polynomials.
A Gröbner basis is the list of polynomials in a Gröbner basis with the leading
term of each listed polynomial being the initial term with respect to a termorder for which this a Gröbner basis.
A list of polynomial sets is a list of polynomial sets. Often the polynomial
sets are required to be Gröbner bases.
38

An ideal is written as a list of polynomials generating it.
For all other lists than integer vectors the characters ’{’ and ’}’ are used to startand end the list.

A.6

Permutations

When exploiting the symmetry of an ideal one needs to input permutations to
the program. Each permutation is speciﬁed by a vector. The length of the vector
should equal the number of elements being permuted - for example the numberof variables in the polynomial ring. The ﬁrst element in the vector describes
where the ﬁrst element goes and so on. Of course we start indexing from 0. The
following vectors specify the identity, a transposition and a 3-cycle, respectively,on an ordered set of four elements:• (0,1,2,3)• (1,0,2,3)• (0,3,1,2)

A.7

Polyhedral fans

The output format for polyhedral fans is intended to be Polymake [10] compatible.
Polymake recently switched to an XML based format. Gfan will keep outputting
data in the old text style by default as it is more convienient for the command line
Gfan user. The option --xml switches output to being XML. In the Polymake
world, the output objects will have type SymmetricFan. The new XML ﬁlescannot be read by Gfan at the moment, while the old non-XML format cannot beread by any version of Polymake. In the following we describe only the text (nonXML) format. For the XML format we refer to the Polymake documentation.
The text representation of a fan begins with the lines_application fan_version 2.2_type SymmetricFan
After this follows a list of properties. For example
LINEALITY_SPACE
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 1 0 0 1 0 1 1
0 0 0 1 0 0 0 1 0 0 1 0 1 0 1
0 0 1 0 0 0 1 0 0 1 0 0 1 1 0
0 1 0 0 0 0 -1 -1 -1 0 0 0 -1 -1 -1
1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1
39

Each property has a name and must be assigned a value of a certain type. You canread more about the philosophy of the format in the Polymake documentation.
Example A.1 The ideal I = hab − c, bc − a, ca − bi has a cyclic symmetry. If we
run the commands
gfan --symmetry -e | gfan_topolyhedralfan --symmetryon the input
Q[a,b,c]{ab-c,bc-a,ca-b}{(1,2,0)}we get a polyhedral representation of the Gröbner fan of I:_application PolyhedralFan_version 2.2_type PolyhedralFan
AMBIENT_DIM
3
DIM
3LINEALITY_DIM
0
RAYS
1 1 0 # 01 0 1 # 1
0 1 1 # 2
0 1 0 # 3
1 0 0 # 4
0 0 1 # 5
2 1 1 # 6
1 1 2 # 7
1 2 1 # 8
1 1 1 # 9
N_RAYS
10
LINEALITY_SPACE
40

ORTH_LINEALITY_SPACE
0 0 1
0 1 0
1 0 0
F_VECTOR
1 10 18 9
CONES{} # New orbit # Dimension 0{0} # New orbit # Dimension 1{1}{2}{3} # New orbit{4}{5}{6} # New orbit{7}{8}{9} # New orbit{0 3} # New orbit # Dimension 2
{1 4}
{2 5}
{0 4} # New orbit
{1 5}
{2 3}
{6 9} # New orbit
{7 9}
{8 9}
{0 6} # New orbit
{1 7}
{2 8}
{0 8} # New orbit
{1 6}
{2 7}
{3 8} # New orbit
{4 6}
{5 7}
{0 3 8} # New orbit # Dimension 3{1 4 6}{2 5 7}{0 4 6} # New orbit
41

Figure 4: The Gröbner fan in Example A.1 intersected with the standard simplex
in R3 .
{1 5 7}{2 3 8}{0 6 8 9} # New orbit{1 6 7 9}{2 7 8 9}MAXIMAL_CONES{0 3 8} # New orbit # Dimension 3{1 4 6}{2 5 7}{0 4 6} # New orbit{1 5 7}{2 3 8}{0 6 8 9} # New orbit{1 6 7 9}{2 7 8 9}
PURE
1
The most important properties are “RAYS” and “CONES”. A ray is given bya relative interior point and a cone is given by a list of indices of rays that will
generate the cone. We may compare this combinatorial data to the drawing of
the Gröbner fan given in Figure 4. Notice that this example is particularly simple
as the dimension of the homogeneity space of I is 0.
The symbol “#” is used for writing comments in the ﬁle. The comments
42

should not be considered a part of the ﬁle. The comments are used by Gfan tolet the user know about dimensions, orbits and indices.
A detailed description of the properties follows in the following.
A.7.1

Data types

In Gfan’s Polymake format the following data types are supported:
Cardinal: One non-negative integer.
Boolean: 0 or 1.
Matrix: An array of integer vectors.
IncidenceMatrix: An array of sets of integers.
Vector: An integer vector.
A.7.2

Properties

Before we describe the properties we need to make a few deﬁnitions.
We do not consider the empty set to be a cone nor a face of a cone.
Deﬁnition A.2 The lineality space of a polyhedral cone is the largest subspacecontained in the cone.
The lineality space is the smallest face of the cone and if two cones are in thesame polyhedral fan then they must have the same lineality space. We deﬁne
the lineality space of a fan to be the common lineality space of its cones. In thespecial case of a (non-restricted) Gröbner fan or a tropical variety the lineality
space of the fan coincides with the homogeneity space of the deﬁning ideal.
Deﬁnition A.3 A cone (in a fan) is called a ray if its dimension is one larger
than the dimension of its lineality space.
A ray can be represented by a vector in its relative interior. This vector is contained in the cone but not contained in any of its proper faces. The representation
is not unique since the cone is invariant under translation by vectors in its lineality
space.
A Polyhedral fan in Gfan can have a subset of the following properties:
AMBIENT DIM is a Cardinal whose value is the dimension of the vector spacein which the fan lives. If the fan is a Gröbner fan or a tropical variety thenthis number equals the number of variables in the polynomial ring of thedeﬁning ideal.

43

DIM is a Cardinal whose value is the dimension of the highest dimensional conein the fan.
LINEALITY DIM is a Cardinal whose value is the dimension of the lineality
space of the fan.
RAYS is a Matrix. The rows of the matrix are vectors representing the rays ofthe fan — one for each ray. The rows are ordered and Gfan writes an index
as a comment to make the ﬁle human readable.
N RAYS is a Cardinal which equals the number of rays in the fan.
LINEALITY SPACE is a Matrix whose rows form a basis for the lineality spaceof the fan.
ORTH LINEALITY SPACE is a Matrix whose rows form a basis for the orthogonal complement of the lineality space of the fan.
F VECTOR is a Vector. The number of entries is DIM−LINEALITY DIM+1.
The ith entry is the number of cones in the fan of dimension
i+LINEALITY DIM−1.
CONES is an IncidenceMatrix. The section contains a line for each cone in thefan. Each line is the set of indices of the rays contained in the corresponding
cone.
MAXIMAL CONES is an IncidenceMatrix and similar to CONES except that
only cones which are maximal with respect to inclusion are listed.
PURE is a Boolean. The value is 1 if the polyhedral fan is pure and 0 otherwise.
MULTIPLICITIES is a Matrix with one column. An entry is the multiplicity ofa maximal cone. Usually cones in polyhedral fans do not have multiplicities.
Thus this property only makes sense for weighted polyhedral fans of which
tropical varieties is a special case. The ordering of the rows in this property
is consistent with the ordering in MAXIMAL CONES.
RAY VALUES is a Matrix with just one column. It is used when the fan ismeant to specify a piece-wise linear (or tropical rational) function. The
function value on the ith ray of the fan is listed in the ith row of thematrix.
LINEALITY VALUES is a Matrix with just one column. It is used when the
fan is meant to specify a piece-wise linear (or tropical rational) function.
The function value on the ith generator of the lineality space (stored in
LINEALITY SPACE) is listed in the ith row of the matrix.
44Besides sections listed above, the sections MAXIMAL CONES ORBITS, CONES ORBITS
and MULTIPLICITIES ORBITS are introduced when doing symmetric computations with the --symmetry option. These sections are analogous to MAXIMAL CONES, CONES and MULTIPLICITIES except that they operate on thelevel of orbits of cones with respect to the symmetry rather than cones.

A.8

Polyhedral cones

The string representation of a polyhedral cone starts with_application PolyhedralCone_version 2.2_type PolyhedralCone
After this follows the properties. For polyhedral cones they are as follows.
AMBIENT DIM — see previous section.
DIM is a Cardinal whose value is the dimension of the cone.
IMPLIED EQUATIONS is a Matrix whose rows form a basis of the space of
linear forms vanishing on the cone.
LINEALITY DIM — see previous section.
LINEALITY SPACE — see previous section.
FACETS is a Matrix which contains an outer normal vector for each facet ofthe cone.
RELATIVE INTERIOR POINT is a Vector in the relative interior of the cone.

45

B

Application list

This section contains the full list of programs in Gfan. For each program its
help ﬁle is listed. The help ﬁle of a program can also be displayed by specifying
the --help option when running the program. Besides the options listed in thissection all programs have options --log1, --log2,... which tell Gfan how muchinformation to write to “standard error” while a computation is running. These
options are VERY USEFUL when you wish to know if Gfan is making
any progress in its computation.
Additional options which can be used for all programs, but which are notlisted in the following subsections are:--stdin value Specify a ﬁle to use as input instead of reading from the standard
input.
--stdout value Specify a ﬁle to write output to instead of writing to the standard output.
--xml To let polyhedral fans be output in an XML format instead of in the text
format. (The XML ﬁles are not readable by Gfan.)

B.1

gfan bases

This is a program for computing all reduced Gröbner bases of a polynomial ideal.
It takes the ring and a generating set for the ideal as input. By default theenumeration is done by an almost memoryless reverse search. If the ideal issymmetric the symmetry option is useful and enumeration will be done up to
symmetry using a breadth ﬁrst search. The program needs a starting Gröbner
basis to do its computations. If the -g option is not speciﬁed it will compute one
using Buchberger’s algorithm.
Options:-g Tells the program that the input is already a Gröbner basis (with the initial term of each polynomial being the ﬁrst ones listed). Use this option
if it takes too much time to compute the starting (standard degree lexicographic) Gröbner basis and the input is already a Gröbner basis.
--symmetry Tells the program to read in generators for a group of symmetries(subgroup of S n) after having read in the ideal. The program checks thatthe ideal stays ﬁxed when permuting the variables with respect to elementsin the group. The program uses breadth ﬁrst search to compute the setof reduced Gröbner bases up to symmetry with respect to the speciﬁed
subgroup.
-e Echo. Output the generators for the symmetry group.
46

--disableSymmetryTest When using --symmetry this option will disable thecheck that the group read oﬀ from the input actually is a symmetry groupwith respect to the input ideal.
--parameters value With this option you can specify how many variables totreat as parameters instead of variables. This makes it possible to do computations where the coeﬃcient ﬁeld is the ﬁeld of rational functions in theparameters.
--interrupt value Interrupt the enumeration after a speciﬁed number of facets
have been computed (works for usual symmetric traversals, but may notwork in general for non-symmetric traversals or for traversals restricted tofans).

B.2

gfan buchberger

This program computes a reduced lexicographic Gröbner basis of the polynomial
ideal given as input. The default behavior is to use Buchberger’s algorithm. The
ordering of the variables is a > b > c... (assuming that the ring is Q[a,b,c,...]).
Options:-w Compute a Gröbner basis with respect to a degree lexicographic order witha > b > c... instead. The degrees are given by a weight vector which is readfrom the input after the generating set has been read.
-r Use the reverse lexicographic order (or the reverse lexicographic order as a tie
breaker if -w is used). The input must be homogeneous if the pure reverse
lexicographic order is chosen. Ignored if -W is used.
-W Do a Gröbner walk. The input must be a minimal Gröbner basis. If -W isused -w is ignored.
-g Do a generic Gröbner walk. The input must be homogeneous and must bea minimal Gröbner basis with respect to the reverse lexicographic termorder. The target term order is always lexicographic. The -W option must
be used.
--parameters value With this option you can specify how many variables totreat as parameters instead of variables. This makes it possible to do computations where the coeﬃcient ﬁeld is the ﬁeld of rational functions in theparameters.

47

B.3

gfan combinerays

This program combines rays from the speciﬁed polymake ﬁle by adding according
to a list of vectors of indices given on the standard input.
Options:-i value Specify the name of the input ﬁle.
--section value Specify a section of the polymake ﬁle to use as input, rather
than standard input.

B.4

gfan doesidealcontain

This program takes a marked Gröbner basis of an ideal I and a set of polynomials
on its input and tests if the polynomial set is contained in I by applying thedivision algorithm for each element. The output is 1 for true and 0 for false.
Options:--remainder Tell the program to output the remainders of the divisions rather
than outputting 0 or 1.
--multiplier Reads in a polynomial that will be multiplied to the polynomial to
be divided before doing the division.

B.5

gfan fancommonreﬁnement

This program takes two polyhedral fans and computes their common reﬁnement.
Options:-i1 value Specify the name of the ﬁrst input ﬁle.
-i2 value Specify the name of the second input ﬁle.
--stable Compute the stable intersection.

B.6

gfan fanhomology

This program takes a polyhedral fan and computes its reduced homology groups.
Of course the support of a fan is contractible, so what is really computed is the
reduced homology groups of the support of the fan after quotienting out with thelineality space and intersecting with a sphere. Notice that taking the quotientwith the lineality space results in an inverted suspension which just results in ashift of the reduced homology groups.
Options:-i value Specify the name of the input ﬁle.
--no-optimize Disable preprocessing of boundary maps before doing latticecomputations.
48

B.7

gfan fanisbalanced

This program checks if a fan is balanced
Options:-i value Specify the name of the input ﬁle.
--makeBalanced Assign positive multiplicities to cones to make the fan balanced instead. Fan is assumed to be pure.
--facetComplex When making the fan balanced, ﬁrst take facet complex--cone Output cone of all balanced weight functions.

B.8

gfan fanlink

This program takes a polyhedral fan and a vector and computes the link of thepolyhedral fan around that vertex. The link will have lineality space dimension
equal to the dimension of the relative open polyhedral cone of the original fan
containing the vector.
Options:-i value Specify the name of the input ﬁle.
--symmetry Reads in a fan stored with symmetry. The generators of the symmetry group must be given on the standard input.
--star Computes the star instead. The star is deﬁned as the smallest polyhedral
fan containing all cones of the original fan containing the vector.

B.9

gfan fanproductThis program takes two polyhedral fans and computes their product.
Options:-i1 value Specify the name of the ﬁrst input ﬁle.
-i2 value Specify the name of the second input ﬁle.

B.10

gfan fansubfan

This program takes a polyhedral fan and a list of vectors and computes thesmallest subfan of the fan having the list of vectors in its support.
Options:-i value Specify the name of the input ﬁle.
--symmetry Reads in the cone stored with symmetry. The generators of thesymmetry group must be given on the standard input.
49

B.11

gfan genericlinearchangeThis program takes a list of polynomials and performs a generic linear change of
coordinates by introducing nxn new variables.

B.12

gfan groebnercone

This program computes a Gröbner cone. Three diﬀerent cases are handled. The
input may be a marked reduced Gröbner basis in which case its Gröbner cone iscomputed. The input may be just a marked minimal basis in which case the cone
computed is not a Gröbner cone in the usual sense but smaller. (These cones
are described in [Fukuda, Jensen, Lauritzen, Thomas]). The third possible caseis that the Gröbner cone is possibly lower dimensional and given by a pair ofGröbner bases as it is useful to do for tropical varieties, see option --pair. The
facets of the cone can be read oﬀ in section FACETS and the equations in section
IMPLIED EQUATIONS.
Options:--restrict Add an inequality for each coordinate, so that the the cone is restricted
to the non-negative orthant.
--pair The Gröbner cone is given by a pair of compatible Gröbner bases. The
ﬁrst basis is for the initial ideal and the second for the ideal itself. See thetropical section of the manual.
--asfan Writes the cone as a polyhedral fan with all its faces instead. In thisway the extreme rays of the cone are also computed.
--vectorinput Compute a cone given list of inequalities rather than a Gröbnercone. The input is an integer which speciﬁes the dimension of the ambient
space, a list of inequalities given as vectors and a list of equations.

B.13

gfan groebnerfan

This is a program for computing the Gröbner fan of a polynomial ideal as apolyhedral complex. It takes a generating set for the ideal as input. If the ideal
is symmetric the symmetry option is useful and enumeration will be done up to
symmetry. The program needs a starting Gröbner basis to do its computations.
If the -g option is not speciﬁed it will compute one using Buchberger’s algorithm.
Options:-g Tells the program that the input is already a Gröbner basis (with the initial term of each polynomial being the ﬁrst ones listed). Use this option
if it takes too much time to compute the starting (standard degree lexicographic) Gröbner basis and the input is already a Gröbner basis.
50

--symmetry Tells the program to read in generators for a group of symmetries(subgroup of S n) after having read in the ideal. The program checks thatthe ideal stays ﬁxed when permuting the variables with respect to elementsin the group. The program uses breadth ﬁrst search to compute the setof reduced Gröbner bases up to symmetry with respect to the speciﬁed
subgroup.
--disableSymmetryTest When using --symmetry this option will disable thecheck that the group read oﬀ from the input actually is a symmetry groupwith respect to the input ideal.
--restrictingfan value Specify the name of a ﬁle containing a polyhedral fan in
Polymake format. The computation of the Gröbner fan will be restricted
to this fan. If the --symmetry option is used then this restricting fan must
be invariant under the symmetry and the orbits in the ﬁle must be withrespect to the speciﬁed group of symmetries. The orbits of maximal conesof the ﬁle are then read in rather than the maximal cones.
--parameters value With this option you can specify how many variables totreat as parameters instead of variables. This makes it possible to do computations where the coeﬃcient ﬁeld is the ﬁeld of rational functions in theparameters.
--nocones Tells the program not to output the CONES and MAXIMAL CONES
sections, but still output CONES COMPRESSED and MAXIMAL CONES COMPRESSEDif --symmetry is used.
--interrupt value Interrupt the enumeration after a speciﬁed number of facets
have been computed (works for usual symmetric traversals, but may notwork in general for non-symmetric traversals or for traversals restricted tofans).

B.14

gfan homogeneityspace

This program computes the homogeneity space of a list of polynomials - as acone. Thus generators for the homogeneity space are found in the section LINEALITY SPACE. If you wish the homogeneity space of an ideal you should ﬁrst
compute a set of homogeneous generators and call the program on these. A
reduced Gröbner basis will always suﬃce for this purpose.

B.15

gfan homogenize

This program homogenises a list of polynomials by introducing an extra variable.
The name of the variable to be introduced is read from the input after the list of51

polynomials. Without the -w option the homogenisation is done with respect tototal degree. Example: Input: Q[x,y]{y-1} z Output: Q[x,y,z]{y-z}Options:-i Treat input as an ideal. This will make the program compute the homogenisation of the input ideal. This is done by computing a degree Gröbner basisand homogenising it.
-w Specify a homogenisation vector. The length of the vector must be the sameas the number of variables in the ring. The vector is read from the input
after the list of polynomials.
-H Let the name of the new variable be H rather than reading in a name fromthe input.

B.16

gfan initialforms

This program converts a list of polynomials to a list of their initial forms withrespect to the vector given after the list.
Options:--ideal Treat input as an ideal. This will make the program compute the initial
ideal of the ideal generated by the input polynomials. The computation isdone by computing a Gröbner basis with respect to the given vector. The
vector must be positive or the input polynomials must be homogeneous ina positive grading. None of these conditions are checked by the program.
--pair Produce a pair of polynomial lists. Used together with --ideal this option
will also write a compatible reduced Gröbner basis for the input ideal tothe output. This is useful for ﬁnding the Gröbner cone of a non-monomial
initial ideal.
--mark If the --pair option is and the --ideal option is not used this option will
still make sure that the second output basis is marked consistently with thevector.
--list Read in a list of vectors instead of a single vector and produce a list ofpolynomial sets as output.

B.17

gfan interactive

This is a program for doing interactive walks in the Gröbner fan of an ideal. The
input is a Gröbner basis deﬁning the starting Gröbner cone of the walk. The
program will list all ﬂippable facets of the Gröbner cone and ask the user tochoose one. The user types in the index (number) of the facet in the list. The
52

program will walk through the selected facet and display the new Gröbner basis
and a list of new facet normals for the user to choose from. Since the program
reads the user’s choices through the the standard input it is recommended not toredirect the standard input for this program.
Options:-L Latex mode. The program will try to show the current Gröbner basis in areadable form by invoking LaTeX and xdvi.
-x Exit immediately.
-f Tell the program to list the ﬂipped reduced Gröbner basis of the initial ideal
for each ﬂippable wall in the current Gröbner cone.
-w Tell the program to list (a Gröbner basis with respect to the current termorder for) the initial ideal for each ﬂippable wall in the current Gröbner
cone.
-i Tell the program to list the deﬁning set of inequalities of the non-restrictedGröbner cone as a set of vectors after having listed the current Gröbner
basis.
-W Print weight vector. This will make the program print an interior vectorof the current Gröbner cone and a relative interior point for each ﬂippable
facet of the current Gröbner cone.
--tropical Traverse a tropical variety interactively.

B.18

gfan ismarkedgroebnerbasis

This program checks if a set of marked polynomials is a Gröbner basis with respect
to its marking. First it is checked if the markings are consistent with respect to a
positive vector. Then Buchberger’s S-criterion is checked. The output is boolean
value.

B.19

gfan krulldimension

Takes an ideal I and computes the Krull dimension of R/I where R is the polynomial ring. This is done by ﬁrst computing a Gröbner basis.
Options:-g Tell the program that the input is already a reduced Gröbner basis.

53

B.20

gfan latticeideal

This program computes the lattice ideal of a lattice. The input is a list of generators for the lattice.
Options:-t Compute the toric ideal of the matrix whose rows are given on the input
instead.
--convert Does not do any computation, but just converts the vectors to binomials.

B.21

gfan leadingterms

This program converts a list of polynomials to a list of their leading terms.
Options:-m Do the same thing for a list of polynomial sets. That is, output the set ofsets of leading terms.

B.22

gfan list

This program lists all subcommands of the Gfan installation.
Options:--hidden Show hidden commands which are not oﬃcially supported.

B.23

gfan markpolynomialset

This program marks a set of polynomials with respect to the vector given at theend of the input, meaning that the largest terms are moved to the front. In caseof a tie the lexicographic term order with a > b > c... is used to break it.

B.24

gfan minkowskisumThis is a program for computing the normal fan of the Minkowski sum of the
Newton polytopes of a list of polynomials.
Options:--symmetry Tells the program to read in generators for a group of symmetries(subgroup of S n) after having read in the ideal. The program checks thatthe ideal stays ﬁxed when permuting the variables with respect to elementsin the group. The program uses breadth ﬁrst search to compute the setof reduced Gröbner bases up to symmetry with respect to the speciﬁed
subgroup.
54

--disableSymmetryTest When using --symmetry this option will disable thecheck that the group read oﬀ from the input actually is a symmetry groupwith respect to the input ideal.
--nocones Tell the program to not list cones in the output.

B.25

gfan minors

This program will generate the r*r minors of a d*n matrix of indeterminates.
Options:-r value Specify r.
-d value Specify d.
-n value Specify n.
-M2 Use Macaulay2 conventions for order of variables.
--names Assign names to the minors.
--dressian Produce tropical deﬁning the Dressian(3,n) instead. (The signs may
not be correct, that is the equations may not be Pluecker relations.)--pluckersymmetries Do nothing but produce symmetry generators for the
Pluecker ideal.
--symmetry Produces a list of generators for the group of symmetries keeping
the set of minors ﬁxed. (Only without --names).
--parametrize Parametrize the set of d times n matrices of Barvinok rank lessthan or equal to r-1 by a list of tropical polynomials.
--ultrametric Produce tropical equations cutting out the ultrametrics.

B.26

gfan mixedvolume

This program computes the mixed volume of the Newton polytopes of a list ofpolynomials. The ring is speciﬁed on the input. After this follows the list ofpolynomials.
Options:--vectorinput Read in a list of point conﬁgurations instead of a polynomial ring
and a list of polynomials.
--cyclic value Use cyclic-n example instead of reading input.
--noon value Use Noonburg-n example instead of reading input.
55

--chandra value Use Chandrasekhar-n example instead of reading input.
--katsura value Use Katsura-n example instead of reading input.
--gaukwa value Use Gaukwa-n example instead of reading input.
--eco value Use Eco-n example instead of reading input.
-j value Number of threads

B.27

gfan overintegers

This program is an experimental implementation of Gröbner bases for ideals inZ[x 1,...,x n]. Several operations are supported by specifying the appropriate option: (1) computation of the reduced Gröbner basis with respect to a given vector(tiebroken lexicographically), (2) computation of an initial ideal, (3) computation of the Gröbner fan, (4) computation of a single Gröbner cone. Since Gfan
only knows polynomial rings with coeﬃcients being elements of a ﬁeld, the idealis speciﬁed by giving a set of polynomials in the polynomial ring Q[x 1,...,x n].
That is, by using Q instead of Z when specifying the ring. The ideal MUST BE
HOMOGENEOUS (in a positive grading) for computation of the Gröbner fan.
Non-homogeneous ideals are allowed for the other computations if the speciﬁed
weight vectors are positive. NOTE: This program is experimental and expected
to change behaviour in future releases, so don’t write your SAGE and M2 interfaces just yet.
Options:--groebnerBasis Asks the program to compute a marked Gröbner basis withrespect to a weight vector tie-broken lexicographically. The input order is:
Ring ideal vector.
--initialIdeal Asks the program to compute an initial ideal with respect to avector. The input order is: Ring ideal vector.
--groebnerFan Asks the program to compute the Gröbner fan. The input order
is: Ring ideal.
--groebnerCone Asks the program to compute a single Gröbner cone containing the speciﬁed vector in its relative interior. The output is stored as afan. The input order is: Ring ideal vector.
-m For the operations taking a vector as input, read in a list of vectors instead,and perform the operation for each vector in the list.
-g Tells the program that the input is already a Gröbner basis (with the initial
term of each polynomial being the ﬁrst ones listed). Use this option if theusual --groebnerFan is too slow.
56

B.28

gfan padic

This program is an experimental implementation of p-adic Gröbner bases as proposed by Diane Maclagan. Several operations are supported by specifying theappropriate option: (1) computation of Gröbner basis with respect to a given vector (tiebroken lexicographically), (2) computation of the p-adic initial ideal, (3)computation of the p-adic Gröbner complex as deﬁned by Maclagan and Sturmfels, (4) computation of a single polyhedron of the p-adic Gröbner complex. The
input ideal should be an ideal of the polynomial ring with coeﬃcient ﬁeld Q. The
valuation is speciﬁed with the option -p. The ideal MUST BE HOMOGENEOUS(in a positive grading). Since gfan can only handle fans and not polyhedral complexes in general, what is computed as the Gröbner complex is actually the ”fanover” the complex - in other words, the ﬁrst coordinate is supposed to be 1 in the
output fan. Similarly, the weight vectors must be speciﬁed in an homogeneousway, for example by adding an additional 1 entry as ﬁrst coordinate. (If fractions
are needed, use the entry as a common denominator.) NOTE: This program isexperimental and expected to change behaviour in future releases, so don’t write
your SAGE and M2 interfaces just yet. In particular this program uses the tropical minimum-convention!!
Options:-p value Deﬁnes the prime used for the valuation.
--groebnerBasis Asks the program to compute a marked Gröbner basis withrespect to a weight vector (tie-broken lexicographically). The input order
is: Ring ideal vector.
--initialIdeal Asks the program to compute an initial ideal with respect to avector. The input order is: Ring ideal vector.
--groebnerComplex Asks the program to compute the p-adic Gröbner complex. The input order is: Ring ideal.
--groebnerPolyhedron Asks the program to compute a single polyhedron of
the Gröbner complex containing the speciﬁed vector in its relative interior.
The output is stored as a fan. The input order is: Ring ideal vector.
-m For the operations taking a vector as input, read in a list of vectors instead,and perform the operation for each vector in the list.

B.29

gfan polynomialsetunion

This program computes the union of a list of polynomial sets given as input. The
polynomials must all belong to the same ring. The ring is speciﬁed on the input.
After this follows the list of polynomial sets.
Options:57

-s Sort output by degree.

B.30

gfan renderThis program renders a Gröbner fan as an xﬁg ﬁle. To be more precise, the input
is the list of all reduced Gröbner bases of an ideal. The output is a drawing of theGröbner fan intersected with a triangle. The corners of the triangle are (1,0,0) to
the right, (0,1,0) to the left and (0,0,1) at the top. If there are more than threevariables in the ring these coordinates are extended with zeros. It is possible toshift the 1 entry cyclic with the option --shiftVariables.
Options:-L Make the triangle larger so that the shape of the Gröbner region appears.
--shiftVariables value Shift the positions of the variables in the drawing. For
example with the value equal to 1 the corners will be right: (0,1,0,0,...), left:(0,0,1,0,...) and top: (0,0,0,1,...). The shifting is done modulo the numberof variables in the polynomial ring. The default value is 0.

B.31

gfan renderstaircase

This program renders a staircase diagram of a monomial initial ideal to an xﬁgﬁle. The input is a Gröbner basis of a (not necessarily monomial) polynomial
ideal. The initial ideal is given by the leading terms in the Gröbner basis. Using
the -m option it is possible to render more than one staircase diagram. The
program only works for ideals in a polynomial ring with three variables.
Options:-m Read multiple ideals from the input. The ideals are given as a list of listsof polynomials. For each polynomial list in the list a staircase diagram isdrawn.
-d value Speciﬁes the number of boxes being shown along each axis. Be surethat this number is large enough to give a correct picture of the standard
monomials. The default value is 8.
-w value Width. Speciﬁes the number of staircase diagrams per row in the xﬁgﬁle. The default value is 5.

B.32

gfan resultantfan

This program computes the resultant fan as deﬁned in ”Computing TropicalResultants” by Jensen and Yu. The input is a polynomial ring followed by polynomials, whose coeﬃcients are ignored. The output is the fan of coeﬃcients such58

that the input system has a tropical solution.
Options:--codimension Compute only the codimension of the resultant fan and return.
--symmetry Tells the program to read in generators for a group of symmetries(subgroup of S n) after having read in the vector conﬁguration. The program DOES NOT checks that the conﬁguration stays ﬁxed when permuting
the variables with respect to elements in the group. The output is grouped
according to the symmetry.
--nocones Tells the program not to output the CONES and MAXIMAL CONES
sections, but still output CONES COMPRESSED and MAXIMAL CONES COMPRESSEDif --symmetry is used.
--special Read in a zero-one vector from the standard input and specialize all
variables with a one. That is, compute the stable intersection of the resultant fan with the subspace where the variables with a one in the vector
are forced to zero. AT THE MOMENT ALSO A RELATIVE INTERIOR
POINT OF A STARTING CONE IS READ.
--vectorinput Read in a list of point conﬁgurations instead of a polynomial ring
and a list of polynomials.
--projection Use the projection method to compute the resultant fan. This
works only if the resultant fan is a hypersurface. If this option is combined with --special, then the output fan lives in the subspace of the nonspecialized coordinates.

B.33

gfan saturation

This program computes the saturation of the input ideal with the product of thevariables x 1,...,x n. The ideal does not have to be homogeneous.
Options:-h Tell the program that the input is a homogeneous ideal (with homogeneous
generators).
--noideal Do not treat input as an ideal but just factor out common monomial
factors of the input polynomials.

B.34

gfan secondaryfan

This program computes the secondary fan of a vector conﬁguration. The conﬁguration is given as an ordered list of vectors. In order to compute the secondary59

fan of a point conﬁguration an additional coordinate of ones must be added. For
example {(1,0),(1,1),(1,2),(1,3)}.
Options:--unimodular Use heuristics to search for unimodular triangulation rather thancomputing the complete secondary fan--scale value Assuming that the ﬁrst coordinate of each vector is 1, this option
will take the polytope in the 1 plane and scale it. The point conﬁguration
will be all lattice points in that scaled polytope. The polytope must havemaximal dimension. When this option is used the vector conﬁguration musthave full rank. This option may be removed in the future.
--restrictingfan value Specify the name of a ﬁle containing a polyhedral fan in
Polymake format. The computation of the Secondary fan will be restricted
to this fan. If the --symmetry option is used then this restricting fan must
be invariant under the symmetry and the orbits in the ﬁle must be withrespect to the speciﬁed group of symmetries. The orbits of maximal conesof the ﬁle are then read in rather than the maximal cones.
--symmetry Tells the program to read in generators for a group of symmetries(subgroup of S n) after having read in the vector conﬁguration. The program checks that the conﬁguration stays ﬁxed when permuting the variables
with respect to elements in the group. The output is grouped according to
the symmetry.
--nocones Tells the program not to output the CONES and MAXIMAL CONES
sections, but still output CONES COMPRESSED and MAXIMAL CONES COMPRESSEDif --symmetry is used.
--interrupt value Interrupt the enumeration after a speciﬁed number of facets
have been computed (works for usual symmetric traversals, but may notwork in general for non-symmetric traversals or for traversals restricted tofans).

B.35

gfan stats

This program takes a list of reduced Gröbner bases for the same ideal and computes various statistics. The following information is listed: the number of basesin the input, the number of variables, the dimension of the homogeneity space,
the maximal total degree of any polynomial in the input and the minimal total
degree of any basis in the input, the maximal number of polynomials and terms
in a basis in the input.

60

B.36

gfan substituteThis program changes the variable names of a polynomial ring. The input is apolynomial ring, a polynomial set in the ring and a new polynomial ring with thesame coeﬃcient ﬁeld but diﬀerent variable names. The output is the polynomial
set written with the variable names of the second polynomial ring. Example:
Input: Q[a,b,c,d]{2a-3b,c+d}Q[b,a,c,x] Output: Q[b,a,c,x]{2*b-3*a,c+x}

B.37

gfan symmetries

This program computes the symmetries of a polynomial ideal. The program isslow, so think before using it. Use --symmetry to give hints about which subgroupof the symmetry group could be useful. The program checks each element of thespeciﬁed subgroup to see if it preserves the ideal.
Options:--symmetry Specify subgroup to be searched for permutations keeping the ideal
ﬁxed.
--symsigns Specify for each generator of the group speciﬁed wiht --symmetry anelement of {−1, +1}n which by its multiplication on the variables together
with the permutation is expected to keep the ideal ﬁxed.

B.38

gfan tolatex

This program converts ASCII math to TeX math. The data-type is speciﬁed by
the options.
Options:-h Add a header to the output. Using this option the output will be LaTeXable
right away.
--polynomialset The data to be converted is a list of polynomials.
--polynomialsetlist The data to be converted is a list of lists of polynomials.

B.39

gfan topolyhedralfanThis program takes a list of reduced Gröbner bases and produces the fan of all
faces of these. In this way by giving the complete list of reduced Gröbner bases,
the Gröbner fan can be computed as a polyhedral complex. The option --restrict
lets the user choose between computing the Gröbner fan or the restricted Gröbner
fan.
Options:61

--restrict Add an inequality for each coordinate, so that the the cones are restricted to the non-negative orthant.
--symmetry Tell the program to read in generators for a group of symmetries(subgroup of S n) after having read in the ring. The output is grouped
according to these symmetries. Only one representative for each orbit isneeded on the input.

B.40

gfan tropicalbasis

This program computes a tropical basis for an ideal deﬁning a tropical curve.
Deﬁning a tropical curve means that the Krull dimension of R/I is at most 1 +the dimension of the homogeneity space of I where R is the polynomial ring. The
input is a generating set for the ideal. If the input is not homogeneous option -hmust be used.
Options:-h Homogenise the input before computing a tropical basis and dehomogenise theoutput. This is needed if the input generators are not already homogeneous.

B.41

gfan tropicalbruteforce

This program takes a marked reduced Gröbner basis for a homogeneous ideal andcomputes the tropical variety of the ideal as a subfan of the Gröbner fan. The
program is slow but works for any homogeneous ideal. If you know that your ideal
is prime over the complex numbers or you simply know that its tropical variety
is pure and connected in codimension one then use gfan tropicalstartingcone andgfan tropicaltraverse instead.

B.42

gfan tropicalcurveThis program computes a tropical basis for an ideal deﬁning a tropical curve.
Deﬁning a tropical curve means that the Krull dimension of R/I is at most 1 +the dimension of the homogeneity space of I where R is the polynomial ring. The
input is a generating set for the ideal. If the input is not homogeneous option -hmust be used.
Options:--singleray Only compute a single ray of the curve.
--parameters value With this option you can specify how many variables totreat as parameters instead of variables. This makes it possible to do computations where the coeﬃcient ﬁeld is the ﬁeld of rational functions in theparameters.
62

B.43

gfan tropicalevaluation

This program evaluates a tropical polynomial function in a given set of points.

B.44

gfan tropicalfunction

This program takes a polynomial and tropicalizes it. The output is piecewise
linear function represented by a fan whose cones are the linear regions. Eachray of the fan gets the value of the tropical function assigned to it. In otherwords this program computes the normal fan of the Newton polytope of the
input polynomial with additional information.
Options:--exponents Tell program to read a list of exponent vectors instead.

B.45

gfan tropicalhypersurface

This program computes the tropical hypersurface deﬁned by a principal ideal.
The input is the polynomial ring followed by a set containing just a generator of
the ideal.

B.46

gfan tropicalintersection

This program computes the set theoretical intersection of a set of tropical hypersurfaces (or to be precise, their common reﬁnement as a fan). The input isa list of polynomials with each polynomial deﬁning a hypersurface. Considering
tropical hypersurfaces as fans, the intersection can be computed as the common
reﬁnement of these. Thus the output is a fan whose support is the intersectionof the tropical hypersurfaces.
Options:--tropicalbasistest This option will test that the input polynomials for a tropical basis of the ideal they generate by computing the tropical prevariety of
the input polynomials and then reﬁne each cone with the Gröbner fan andtesting whether each cone in the reﬁnement has an associated monomial
free initial ideal. If so, then we have a tropical basis and 1 is written as
output. If not, then a zero is written to the output together with a vector
in the tropical prevariety but not in the variety. The actual check is doneon a homogenization of the input ideal, but this does not aﬀect the result.
(This option replaces the -t option from earlier gfan versions.)--tplane This option intersects the resulting fan with the plane x 0=-1, wherex 0 is the ﬁrst variable. To simplify the implementation the output isactually the common reﬁnement with the non-negative half space. Thismeans that ”stuﬀ at inﬁnity” (where x 0=0) is not removed.
63

--symmetryPrinting Parse a group of symmetries after the input has beenread. Used when printing with --incidence.
--symmetryExploit Restrict computation to the closed lexicographic fundamental domain of the speciﬁed symmetry group. This overwrites --restrict.
--nocones Tells the program not to output the CONES and MAXIMAL CONES
sections, but still output CONES COMPRESSED and MAXIMAL CONES COMPRESSEDif --symmetry is used.
--restrict Restrict the computation to a full-dimensional cone given by a list of
marked polynomials. The cone is the closure of all weight vectors choosing
these marked terms.
--stable Find the stable intersection of the input polynomials using tropicalintersection theory. This can be slow. Most other options are ignored.
--parameters value With this option you can specify how many variables totreat as parameters instead of variables. This makes it possible to do computations where the coeﬃcient ﬁeld is the ﬁeld of rational functions in theparameters.

B.47

gfan tropicalliftingThis program is part of the Puiseux lifting algorithm implemented in Gfan andSingular. The Singular part of the implementation can be found in:Anders Nedergaard Jensen, Hannah Markwig, Thomas Markwig: tropical.lib.
A SINGULAR 3.0 library for computations in tropical geometry, 2007
See also
http://www.mathematik.uni-kl.de/˜keilen/de/tropical.html
and the paper
Jensen, Markwig, Markwig: ”An algorithm for lifting points in a tropicalvariety”.
Example:Run Singular from the directory where tropical.lib is located. Give the following sequence of commands to Singular:
LIB ”tropical.lib”; ring R=0,(t,x,y,z),dp; ideal i=-y2t4+x2,yt3+xz+y; intvec
w=1,-2,0,2; list L=tropicallifting(i,w,3); displaytropicallifting(L,”subst”); This
produces a Puiseux series solution to i with valuation (2,0,-2)
Options:--noMult Disable the multiplicity computation.
-n value Number of variables that should have negative weight.
-c Only output a list of vectors being the possible choices.
64

B.48

gfan tropicallinearspace

This program generates tropical equations for a tropical linear space in the Speyer
sense given the tropical Pluecker coordinates as input.
Options:-d value Specify d.
-n value Specify n.
--trees list the boundary trees (assumes d=3)

B.49

gfan tropicalmultiplicity

This program computes the multiplicity of a tropical cone given a marked reducedGröbner basis for its initial ideal.

B.50

gfan tropicalprevariety

This program computes the tropical prevariety of a set of polynomials. The
program works in two diﬀerent modes. By default the coeﬃcient ﬁeld is regarded
as having trivial valuation and the output is a polyhedral fan. With the option--usevaluation the program uses the valuation of the given coeﬃcient ﬁeld when
deﬁning the tropical prevariety. As a consequence the output in this case is apolyhedral complex represented by the half-open polyhedral fan over it. It is
often useful to use the ﬁeld Q(t). However, because of the limitations of thecurrent parser, the way to specify elements of for example Q(t)[x1,x2] is to write
them as polynomials in Q[t,x1,x2].
When --usevaluation is used the options --mint and --minx can switch theprogram from max to min convention. In particular, using both --mint and -minx switches conventions to the [Speyer,Sturmfels]/[Maclagan,Sturmfels] convention. Example: ./gfan tropicalprevariety -j32 --usevaluation --bits64 with
input: Q(t)[x,y]{1+t*x+x+y} produces a polyhedral complex.
Options:--saveas value Specify ﬁlename for saving intermediate result.
--loadfrom value Specify ﬁlename for loading intermediate result.
-j value Number of threads--bits value Number of bits used in intermediate integer type. Allowed values
are 64, 32 and 0 for arbitrary precision. In the postprocessing step thecomputed prevariety is converted in arbitrary precission.

65

--usevaluation Use valuations in the deﬁntion of the tropical hypersurfaces.
The used valuation comes from the ring speciﬁed. For example Q(t) will
come with its usual valuation. In order to represent the output an additional
0th coordinate is introduced.
--mint In a ﬁeld with parameter t this option decides if maximal or minimal
degrees of t determine the valuation.
--minx Switch the programme to min convention for the variables.

B.51

gfan tropicalrankThis program will compute the tropical rank of matrix given as input. Tropical
addition is MAXIMUM.
Options:--kapranov Compute Kapranov rank instead of tropical rank.
--determinant Compute the tropical determinant instead.

B.52

gfan tropicalstartingcone

This program computes a starting pair of marked reduced Gröbner bases to be
used as input for gfan tropicaltraverse. The input is a homogeneous ideal whose
tropical variety is a pure d-dimensional polyhedral complex.
Options:-g Tell the program that the input is already a reduced Gröbner basis.
-d Output dimension information to standard error.
--stable Find starting cone in the stable intersection or, equivalently, pretendthat the coeﬃcients are genereric.

B.53

gfan tropicaltraverse

This program computes a polyhedral fan representation of the tropical variety ofa homogeneous prime ideal I. Let d be the Krull dimension of I and let ω bea relative interior point of d-dimensional Gröbner cone contained in the tropicalvariety. The input for this program is a pair of marked reduced Gröbner baseswith respect to the term order represented by ω, tie-broken in some way. The
ﬁrst one is for the initial ideal in ω(I) the second one for I itself. The pair is thestarting point for a traversal of the d-dimensional Gröbner cones contained in thetropical variety. If the ideal is not prime but with the tropical variety still being
pure d-dimensional the program will only compute a codimension 1 connected66

component of the tropical variety.
Options:--symmetry Do computations up to symmetry and group the output accordingly. If this option is used the program will read in a list of generators
for a symmetry group after the pair of Gröbner bases have been read. Twoadvantages of using this option is that the output is nicely grouped andthat the computation can be done faster.
--symsigns Specify for each generator of the symmetry group an element of{−1, +1}n which by its multiplication on the variables together with the
permutation will keep the ideal ﬁxed. The vectors are given as the rows ofa matrix.
--nocones Tells the program not to output the CONES and MAXIMAL CONES
sections, but still output CONES ORBITS and MAXIMAL CONES ORBITS
if --symmetry is used.
--disableSymmetryTest When using --symmetry this option will disable thecheck that the group read oﬀ from the input actually is a symmetry groupwith respect to the input ideal.
--stable Traverse the stable intersection or, equivalently, pretend that the coefﬁcients are genereric.
--interrupt value Interrupt the enumeration after a speciﬁed number of facets
have been computed (works for usual symmetric traversals, but may notwork in general for non-symmetric traversals or for traversals restricted tofans).

B.54

gfan tropicalweildivisor

This program computes the tropical Weil divisor of piecewise linear (or tropicalrational) function on a tropical k-cycle. See the Gfan manual for more information.
Options:-i1 value Specify the name of the Polymake input ﬁle containing the k-cycle.
-i2 value Specify the name of the Polymake input ﬁle containing the piecewise
linear function.

B.55

gfan version

This program writes out version information of the Gfan installation.
67

References[1] 4ti2 team. 4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at www.4ti2.de.
[2] Lars Allermann and Johannes Rau. First steps in tropical intersection theory.
Mathematische Zeitschrift, 2009.
[3] David Avis and Komei Fukuda. A basis enumeration algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete
Computational Geometry, 8:295–313, 1992.
[4] Robert Bieri and J. R. J. Groves. The geometry of the set of characters
induced by valuations. J. Reine Angew. Math., 347:168–195, 1984.
[5] T. Bogart, A. N. Jensen, D. Speyer, B. Sturmfels, and R. R. Thomas.
Computing tropical varieties. J. Symbolic Comput., 42(1-2):54–73, 2007,
math.AG/0507563.
[6] Bruno Buchberger. An algorithm for ﬁnding a basis for the residue class ringof a zero-dimensional polynomial ideal, 1965. PhD-thesis (German).
[7] S. Collart, M. Kalkbrener, and D. Mall. Converting bases with the Gröbner
walk. J. Symbolic Comput., 24(3-4):465–469, 1997. Computational algebra
and number theory (London, 1993).
[8] Komei Fukuda. cddlib reference manual, cddlib Version 094b.
Swiss
Federal Institute of Technology, Lausanne and Zürich, Switzerland, 2005.
http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html.
[9] Komei Fukuda, Anders Jensen, and Rekha Thomas. Computing Gröbner
fans. Mathematics of Computation, to appear, 2007, math.AC/0509544.
[10] Ewgenij Gawrilow and Michael Joswig. polymake: a framework for analyzing
convex polytopes. In Gil Kalai and Günter M. Ziegler, editors, Polytopes —Combinatorics and Computation, pages 43–74. Birkhäuser, 2000.
[11] Torbjörn Granlund et al. GNU multiple precision arithmetic library 4.1.2,
December 2002. http://swox.com/gmp/.
[12] Birkett Huber and Rekha R. Thomas. Computing Gröbner fans of toricideals. Experimental Mathematics, 9(3/4):321–331, 2000.
[13] Anders Jensen. CaTS, a software system for toric state polytopes. Available
at http://www.soopadoopa.dk/anders/cats/cats.html.
[14] Anders N. Jensen. Traversing symmetric polyhedral fans. to appear in“Mathematical Software - ICMS 2010”, 2010.
68

[15] Anders Nedergaard Jensen.
Algorithmic aspects of Gröbner fans
and tropical varieties.
PhD thesis, University of Aarhus, 2007.
http://www.imf.au.dk/publs?id=655.
[16] Anders Nedergaard Jensen. A non-regular Gröbner fan. Discrete Comput.
Geom., 37(3):443–453, 2007, math.CO/0501352.
[17] D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry:. Graduate Studies in Mathematics. American Mathematical Society, 2015.
[18] Hannah Markwig, Thomas Markwig, and Anders Jensen. An algorithm forlifting points in a tropical variety. 2007, math.AG/0705.2441.
[19] Teo Mora and Lorenzo Robbiano. The Gröbner fan of an ideal. J. Symbolic
Comput., 6(2-3):183–208, 1988. Computational aspects of commutative algebra.
[20] Jörg Rambau. TOPCOM: Triangulations of point conﬁgurations and oriented matroids. ZIB report, 02-17, 2002.
[21] David Speyer and Bernd Sturmfels. The tropical Grassmannian. Adv. Geom.,
4(3):389–411, 2004, math.AG/0304218.
[22] Bernd Sturmfels. Gröbner bases and convex polytopes, volume 8 of University
Lecture Series. American Mathematical Society, Providence, RI, 1996.
[23] Bernd Sturmfels. Solving systems of polynomial equations, volume 97 of
CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2002.
[24] Roland Wunderling.
Paralleler und objektorientierter SimplexAlgorithmus.
PhD thesis, Technische Universität Berlin, 1996.
http://www.zib.de/Publications/abstracts/TR-96-09/.

69