Keywords

Subject Classifications

1 Introduction

In recent years availability of computational classifications of mathematical objects has proven to be an important and valuable tool to obtain new results, to check new ideas and to experiment with the objects to obtain insight into their structure and directions for further research.

We know the full list of smooth Fano polytopes (up to lattice equivalence) up to dimension 9 by an algorithm of Øbro [33], whose availability within the software package polymake has been the foundation e.g. for counter-examples to a conjecture of Batyrev and Selivanova [32] or the classification of simplicial, terminal, and reflexive polytopes with many vertices by Assarf et al. [5]. Availability of the same data in Magma [37] lead to the study of the poset of blowups by Higashitani [16] or the study of reflexive polytopes of higher index by Kasprzyk and Nill [24]. The classification of 0/1-polytopes up to dimension 6 by Aichholzer [2] was used in the study of permutation polytopes by Baumeister et al. [6].

We also know classifications of small oriented matroids by Miyata et al. [12], polytropes [21, 39], and reflexive polytopes up to dimension 4 by Kreuzer and Skarke [3, 26]. The symbolic data project by Gräbe et al. [13] aims to collect data from computer algebra and make it accessible in a structured and searchable form on their web page. The library MIPLIB by Koch et al. [25] collects discrete optimization problems for benchmarking of algorithms.

Most of these collections, however, cannot easily be used in a software package. Sometimes the data is only available in text format or, if searchable via a database, is connected to a specific software package or lacks a proper interface at all. For example, the small oriented matroids [12], polytropes [27, 39], or 0/1-polytopes [2] are available as text files, while access to the small groups library [7] is linked to GAP [36]. Altman et al. [3] have created a database for the reflexive polytopes up to dimension 4 computed by Kreuzer and Skarke [26], but it is currently not accessible at the link given in the paper.

On the other hand, the Graded Rings Database [8] project has a more general approach and provides data in a format both searchable via a web interface and accessible via a programmatic interface that can be used in software packages. It currently has a focus on data from combinatorial commutative algebra and toric geometry.

The new database polyDB aims to provide searchable data from a wide range of areas at a permanent location in an application independent format. It allows download in text format and access from any software package that provides an interface to the data. It is also searchable via a web interface at db.polymake.org. Currently, one interface to a software package is implemented, in the software package polymake [4, 22]. The current collection of data is thus still inspired by the range of applications of polymake with data from combinatorial geometry, matroid theory, toric geometry and combinatorial topology.

In the following two sections we explain the concept of the database and introduce the interface implemented in polymake to access the data. The last section shows one application of the database and the interface. We will show that in dimensions up to 8 more than 80% of the smooth Fano polytopes arise from lower dimensional ones as a free sum of two lower dimensional smooth Fano polytopes or a certain skew sum construction of a smooth Fano polytope and a simplex. We give the count of polytopes decomposable in this way in Table 1. With a simple extension of the scripts one can also obtain the list of possible decompositions for each polytope.

Table 1 Free sums, skew bipyramids and generalized smooth simplex sums among the smooth Fano polytopes
Full size table

2 polyDB

In this section we briefly introduce the structure of the database polyDB and the data sets already contained in it.

The database polyDB for discrete geometric objects is based on the open source NoSQL database MongoDB [31]. It has been set up at db.polymake.org. The database stores its data as plain JSON documents grouped into collections and databases (To avoid confusion with this and the abstract database polyDB we will refer to this technical term introduced by MongoDB as a collection group). We use this to group collections from the same area of discrete geometry into a common collection group. E.g., the collection group Objects in Tropical Geometry currently contains two collections of such objects, the small tropical oriented matroids classified by Horn [17] and the polytropes classified by Kulas [27] and Tran [39]. polyDB stores data in a plain JSON format independent of any particular software package. See Fig. 1 for an example of an entry in the collection of smooth reflexive polytopes.

Fig. 1
figure 1

An entry in the collection of smooth Fano polytopes. Naming of the fields is in this example taken from standard properties of objects in polymake. However, there are no restrictions on field names

Full size image

Each document contains one special entry polyDB (besides its _id, which is required by MongoDB). Apart form this all other entries and their tags can be chosen freely depending on the data. The entry polyDB may specify format restrictions for the data and import or export specifications for various software packages, separated by subfields naming the software. This section may contain, e.g., information on the required version, authors of the data, and the method to load the data into the particular software package. Each collection group also has a separate collection type_information that specifies the format of an entry in a collection and allows to store information applicable to all data sets in this collection, e.g., methods for import and export of the data. The web interface at db.polymake.org allows independent and searchable access to all data sets in polyDB.

There are currently five collections, grouped into four collection groups contained in polyDB. We give a brief introduction to each of the collections.

  • The collection group Lattice Polytopes has the collection Smooth Reflexive Polytopes that contains low dimensional smooth reflexive polytopes based on the algorithm of Øbro [33]. Øbro used his algorithm to compute the data up to dimension 8. Later, dimension 9 was computed with an improved implementation of the algorithm by Lorenz and the author. There are 9, 060, 505 such polytopes.

  • The collection group Objects in Tropical Geometry has two collections. The collection Tropical Oriented Matroids contains a list of 71 known non-realizable tropical oriented matroids. This data was provided by Horn [17]. The collection Full-dimensional Polytropes in TP3 contains all 1013 polytropes in 3-dimensional tropical projective space. The collection was generated by Constantin Fischer from data of Joswig and Kulas [21] and Tran [39]. See [20] for a description.

  • The collection group Special Polytopes has the collection Faces of Birkhoff Polytopes which contains all 5371 combinatorial types of faces up to dimension 8 of the Birkhoff polytope in any dimension [34].

  • The collection group Matroids has the collection Matroids on at most 12 elements. This collection contains all 32, 401, 446 small matroids as computed by Miyata et al. [11, 12, 30].

Further collections are in preparation.

3 The polymake Interface to polyDB

The initiative for polyDB was started in 2013 by Silke Horn and the author as an extension for the software package polymake [19] with associated database. With the latest version 3.1 of polymake [38], released in March 2017, the interface to the database has been turned into a bundled extension for polymake that is directly delivered with the software and the database has been set up as an independent project.

However, the software package polymake currently provides the only interface for import of data into the database and methods to access and use it for computations. Given a search query, i.e. a list of restrictions on the properties of an object, MongoDB allows the retrieval of a single object satisfying the query, an array with all objects satisfying the query or a cursor that returns objects from the result set one after another. All three methods are also implemented in polymake. The implementation is based on the perl MongoDB driver [1]. With

   polytope >  db_info ( ) ;  DATABASE:  LatticePolytopes  This database contains  various  c l a s s e s  of  l a t t i c e  polytopes .  Collection :  SmoothReflexive  A  complete c o l l e c t i o n  of  smooth r e f l e x i v e  l a t t i c e  polytopes in dimensions up to 9 , up to l a t t i c e  equivalence .  [ . . . ]

we can query which collection groups are available. The collection group and collection we want to use for our search are then specified with the keywords db and collection in any access function. The query itself is given as a perl hash. The query is not processed by polymake but directly handed over to MongoDB, so it allows all queries specified in the MongoDB query language. A specification of the full query language and its use from within perl can be found in the documentation of MongoDB [31] and the perl driver for it [1].

Here is an example returning an array of results.

 polytope >  $parray= db_query ({”DIM ”=>3, ” N_FACETS ”=>5},  polytope (2)  >                 db =>”LatticePolytopes ” ,  polytope (3)  >                 c o l l e c t i o n=>”SmoothReflexive ”);  polytope >  print  $parray −> s i z e ;  4

This shows that there are four polytopes in the collection SmoothReflexive that have dimension 3 and 5 facets. Using a loop over this array or a database cursor we can check properties of each object returned. For example

 polytope >  $cursor=db_cursor ({”DIM ”=>3, ” N_FACETS ”=>5},  polytope (2)  >  db =>”LatticePolytopes ” ,  polytope (3)  >  c o l l e c t i o n=>”SmoothReflexive ”);  polytope >  while ( ! $cursor −> at_end ()  )  {  polytope (2)  >  $p =$cursor −> next ( ) ;  polytope (3)  >  print  $p −> N_LATTICE_POINTS ,  ”  ”;  polytope (4)  >  }  34 30 31 30

defines a cursor over the collection SmoothReflexive successively returning all polytopes that satisfy the restrictions given in the query, i.e., that have five facets in dimension 3. Here it tells us that among the four polytopes found above, two have 30, one has 31 and one has 34 lattice points.

4 Decomposing Smooth Fano Polytopes

We illustrate the use of polyDB and its interface to polymake with a computation that uses the collection SmoothReflexive in the collection group LatticePolytopes to compute decompositions of smooth Fano polytopes in dimensions 1 to 8. With our computations we start a new statistics that counts how many of the smooth Fano polytopes can be generated from lower dimensional smooth Fano polytopes with some simple known polytope construction method that preserves both smoothness and reflexiveness of the polytope. We consider three methods in this paper and determine how many of the smooth Fano polytopes in these dimensions are

  • free sums of two smooth Fano polytopes

  • a smooth skew bipyramid over a smooth Fano polytope as defined in [5], or

  • a generalized simplex sum of a smooth Fano polytope with a smooth simplex. This new construction method will be defined below.

All smooth skew bipyramids and many of the free sums are also generalized smooth simplex sums. We will also provide the total number of smooth Fano polytopes that can be decomposed with at least one of these constructions. The results are collected in Table 1.

We briefly explain the relevant notions. More background can, e.g., be found in the book of Ewald [10]. Let be a polytope with vertices , i.e.,

$$\displaystyle \begin{aligned} P\ := \ \mathsf{conv}(v_1, \ldots, v_r){} \end{aligned} $$
(1)

is the convex hull of these points and none of the v i can be omitted in the definition. We assume that P is full dimensional, i.e., the affine hull of P is (otherwise we can pass to a subspace). A polytope can equally be given as the intersection of a finite number of half-spaces in the form

$$\displaystyle \begin{aligned} P\ = \ \{ x\mid Ax\; \le\; b\}{} \end{aligned} $$
(2)

for some and . We can again assume that no inequality is redundant in this definition. In this case the rows of A are the facet normals of P. A facet F of P is the set of all x ∈ P that satisfy one of the inequalities in (2) with equality. A face of P is the common intersection in P of a subset of the facets (this may be empty). The vertices, which are the faces of dimension 0, are in the common intersection of at least d facets.

If 0 is strictly contained in the interior of P, then the polar or dual polytope is defined as

$$\displaystyle \begin{aligned} P^\vee\ :=\ \{ v\mid \langle v, x\rangle\le 1\ \text{ for all }\ x\in P\}\,. \end{aligned}$$

In fact, a finite subset of the inequalities in this definition suffice to define P ∨ (those corresponding to the vertices of P), so that P ∨ is again a polytope. Further, we have (P ∨)∨ = P.

A lattice Λ is the integral span of a linearly independent set of vectors in . Up to a linear transformation we can assume that Λ is the integer lattice , and by passing to a subspace we can assume that n = d. With these assumptions a polytope P is a lattice polytope if all its vertices are in .

In this case we can assume that both A and b are integral in (2), and that the greatest common divisor of the entries of each row of A (i.e., of the entries of each facet normal) is 1. A lattice polytope P is reflexive if P ∨ is again a lattice polytope. In this case b = 1 in (2), and for both P and P ∨ the origin is the unique interior lattice point. P is smooth if the vertices of any facet of P are a lattice basis of . In this case 0 is a strictly interior point of P and each facet has exactly d vertices, so P is simplicial. Moreover, the polar polytope is again a lattice polytope (in the dual lattice) whose vertices are the facet normals (the rows of A), so P is also reflexive. Note that in the literature sometimes the polytopes polar to the ones defined here are called smooth.

It follows from a result of Hensley [15] and Lagarias and Ziegler [28] that there are only finitely many smooth reflexive polytopes in each dimension up to lattice equivalence (affine transformations preserving ), as reflexive polytopes have exactly one interior lattice point. See Fig. 2 for the list of such polytopes in dimension 2. The complete list is contained in polyDB for d ≤ 9 in the collection SmoothReflexive of the database LatticePolytopes. Note however, that in the database we follow the above mentioned alternative definition and list the duals of the ones defined here. Yet, for the purpose of the following constructions it is easier to work with the definition given above, so we will use that one in the following. This requires that in the scripts we use for our computations below we polarize the polytopes obtained from the database. Sometimes this is, however, only done implicitly. This is saves computation time, as it follows from the design of polymake that for reflexive polytopes the facets of the polytope are the vertices of its dual. Also, as we will see below, most constructions can also be given for the duals of the polytopes.

Fig. 2
figure 2

The five 2-dimensional smooth Fano polytopes. (a) P 6. (b) P 5. (c) P 4a. (d) P 4b. (e) P 3

Full size image

We introduce several methods to construct a smooth Fano polytope from smaller ones. The most well known construction is the free sum of two polytopes and that both contain the origin in their interior. This is the polytope

We can also define this on the dual side. The product of polytopes P and Q is the polytope

$$\displaystyle \begin{aligned} P\times Q\ := \ \{(x,y)\mid x\in P,\; y\in Q\}\;. \end{aligned}$$

Then, if P and Q contain the origin in their interior,

$$\displaystyle \begin{aligned} P\oplus Q\,=\,(P^\vee \times Q^\vee)^\vee\, .{} \end{aligned} $$
(3)

We will use this dual definition for the detection of free sums among the smooth Fano polytopes. See Fig. 3a for an example.

Fig. 3
figure 3

Polytope constructions. (a) The free sum of a hexagon and a segment. This is at the same time also a proper bipyramid over the hexagon. (b) A skew bipyramid of a hexagon. The top apex has been shifted to e 1 + e 3. (c) A generalized simplex sum of a segment and a triangle. (d) Another generalized simplex sum of a segment with a triangle

Full size image

A bipyramid over a polytope P is the free sum of P with a segment S containing the origin in the interior. More generally, we say that Q is a skew bipyramid over P if Q has the same combinatorial type (the same face lattice) as a bipyramid over P. The two vertices coming from vertices of S are the two apices of Q.

If P is a smooth d-dimensional Fano polytope then we call the free sum with the segment [−1, 1] the smooth bipyramid over P. Let v be a vertex of P and \(\bar v\) its embedding into by adding a 0 at the end. Then the smooth skew bipyramid for vertex v as defined by Assarf et al. [5] is the polytope

$$\displaystyle \begin{aligned} \operatorname{\mathrm{SBipyr}}(P,v)\ :=\ \mathsf{conv}\left( P\times \{0\} \cup \left\{-e_{d+1}, \bar v+e_{d+1}\right\}\right)\,. \end{aligned}$$

Figure 3b shows an example of this definition. More generally, we say that Q is a smooth generalized skew bipyramid over P if Q is a skew bipyramid over P such that the two apices have lattice distance 1 from P. This class contains all smooth bipyramids and smooth skew bipyramids. The following proposition is an extension of Lemmas 1, 2 and 3 of [5]. The proof easily carries over into this more general setting.

Proposition 4.1

Let P and Q be smooth Fano polytopes. Then the free sum P ⊕ Q, the smooth bipyramid and any smooth (generalized) skew bipyramid over P are again smooth Fano polytopes. □

We further generalize this construction. Let be a smooth Fano polytope and a smooth Fano simplex (this is unique up to lattice equivalence). Let v be a vertex of Q. Then R := P ⊕ Q is a smooth Fano polytope and also any polytope R ′ obtained from R by replacing v with a lattice point v′ in the hyperplane , as long as R and R ′ have the same combinatorial type. This is again a simple extension of the proposition above. We call those polytopes smooth generalized simplex sums. Figure 3c, d shows two examples. Observe that any smooth (generalized skew) bipyramid is a simplex sum.

We can use polymake and polyDB to detect all free sums and smooth generalized simplex sums among the smooth Fano polytopes. Clearly, these two constructions overlap in various ways. Any proper bipyramid over all polytope P is also the free sum of a P with a segment, and polytopes may have more than one possible decomposition into a free sum. Many of the various possibilities to place the vertex v′ for a generalized smooth simplex sum are lattice equivalent. Our approach to detect all different instances is as follows: For a fixed dimension d we consider all possible splits of d as a sum of dimensions a and b and compute all free sums of smooth Fano polytopes in these two dimensions and all simplex sums of an a-dimensional smooth Fano polytope with a b-dimensional simplex. For each such polytope we run through the list of d-dimensional smooth Fano polytopes, check for lattice equivalence and store the name of the polytope we have found. We could also store the way we obtained it alongside, so that in the end we have a list of all possible splits for a given d-dimensional smooth Fano polytope.

We did the computation up to dimension 8. The results are given in Table 1. The free sums can be obtained with the small scripts given in Fig. 4. The first script identify_smooth_polytope takes a smooth Fano polytope, identifies it in the database and returns its name. The identification is based on the polymake function lattice_isomorphic_smooth_polytopes, that reduces the check whether two lattice polytopes are lattice isomorphic to a colored graph isomorphism problem (which is solved using bliss [23] or nauty [29]). Note that there is also the extension LatticeNormalization [18] to polymake that computes the lattice normal form of a lattice polytope (see [14] for a definition), but the reduction to colored graph isomorphism is more efficient for smooth polytopes. The simpler problem of checking combinatorial isomorphisms (i.e., graph isomorphism) can also be done with the polymake-function canonical_hash (also based on bliss or nauty). The second function all_free_sums_in_dim computes all possible free sums that lead to a d-dimensional smooth Fano polytope. As the database contains the polytopes dual to the ones we consider we use (3) and compute products instead of sums to avoid explicit dualization. For each product the function calls identify_smooth_polytope to identify it in the database. The function returns a list of all names (_ids) found in this way. If splitinfo is set to 1 it also returns all pairs of summands.

Fig. 4
figure 4

A function to detect all free sums among the smooth Fano polytopes. This is a shortened version of the script given at [35]

Full size image

For the computation of the smooth generalized simplex sums we used the function all_skew_simplex_sums_in_dim available at [35]. For each combination of an a-dimensional smooth Fano polytope and a b-dimensional simplex with d = a + b we compute all possible lattice points for the shifted vertex v′, construct the polytope and again use identify_smooth_polytope to identify it in the database. Computation of all possible v′ requires the computation of all lattice points in the hyperplane that lead to a lattice polytope with the same combinatorial type as the proper free sum. This can be reduced to enumerating lattice points in the interior of a polytope, which is done in polymake via the interface to Normaliz [9]. As above the function returns a list of ids, and also all possible decompositions into a simplex sum if splitinfo is set to 1. You can save the scripts to a file in the current folder and load this into polymake via

   polytope>  script (<filename >);

Then the classification, e.g. in dimension 4, is obtained with

   polytope >  $fs  =  all_free_sums_in_dim ( 4 ) ;    polytope >  print  $fs −> s i z e ;    28    polytope >  $sb =  all_skew_bipyramids_in_dim ( 4 ) ;    polytope >  print  $fs −> s i z e ;    57    polytope >  $s =  new Set<String >;    polytope >  foreach  ( 1 . . 4 )  {    polytope (2)  >  $st =  skew_simplex_sums_in_dim (4 , ${∖mmlnull}_ ) ;    polytope (3)  >  print  $st −> size ,  ”  ”;    polytope (4)  >  $s +=  $st ;    polytope (5)  >  }    66 31 4 1    polytope >  print  $s −> s i z e ;    93    polytope >  print  (( $fs+$s )−> s i z e ) ;    96

The scripts containing the functions all_skew_bipyramids_in_dim for skew bipyramids and skew_simplex_sums_in_dim for generalized smooth simplex sums are available from [35] and allow to store the possible decompositions. Note that the computation time for the decompositions grows quickly in the dimension. While dimension 4 runs in a few minutes on an Intel Xeon E5-4650, computations in dimension 8 took over a month.

From these computations we can, e.g., see that we have three different decompositions of the dual of the 5-dimensional polytope with index F.5.0116. Its vertices are the rows of the matrix in Table 2a. We can decompose this into three different simplex sums. One is over dual of the 3-dimensional polytope P 3 with index F.3D.0112. This is shown in Table 2b, where the shaded part corresponds to the vertices of P 3. The shifted vertex of the triangle is [0, 0, −2, 1, 1]. Note that the vertices are given as obtained by dualization from the database. Hence, the equality is not directly visible from the vertices, as the two polytopes differ by a lattice isomorphism. We can check this with polymake.

Table 2 Simplex sums leading to the dual of F.5D.0116
Full size table

   polytope >  $p3_ext =  new Polytope (VERTICES =>  polytope (2)  >  [[1,0,1,1,0,0],[1,−1,0,0,0,0],[1,0,0,1,0,0],  polytope (3)  >  [1,0,−1,0,0,0],[1,0,0,−1,0,0],[1,1,0,−1,0,0],  polytope (4)  >  [1,0,0,0,−1,0],[1,0,0,0,0,−1],  polytope (5)  >  [1,0,0,−2,1,1]]);  polytope >  $p5 =  new Polytope (VERTICES =>  polytope (2)  >  [[1,0,0,0,0,1],[1,0,0,1,0,−1],[1,0,0,−1,0,0],  polytope (3)  >  [1,0,0,0,−1,0],[1,0,0,0,0,−1],[1,−1,0,0,0,0],  polytope (4)  >  [1,0,−1,0,0,0],[1,0,1,0,0,1],[1,1,0,0,1,2]]);  polytope >  print  lattice_isomorphic_smooth_polytope (  polytope (2)  >  polarize ( $p3_ext ) , polarize ( $p5 ) ) ;  1

Here, the variable $p3_ext contains the polytope P 3 and $p5 is P 5. As above we need to dualize for the isomorphism check. The check returns 1, which is the true-value for polymake.

The other two decompositions are over the 4-dimensional polytopes \(P_4^1\) and \(P_4^2\) with index F.4D.0008 and F.4D.0019. Those are shown in Table 2c and d. Again, the vertices of \(P_4^1\) and \(P_4^2\) are shaded. The shifted vertices of the 1-dimensional simplex are in the last line.

With this simple computation we have seen that over 80% of the smooth Fano polytopes can be obtained from at least one of the constructions considered here. Hence, for a structural description of all smooth Fano polytopes it suffices to look at the remaining less than 20%.