key: cord-0047200-b165dvns
authors: Joswig, Michael; Vater, Paul
title: Real Tropical Hyperfaces by Patchworking in polymake
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_20
sha: d4f1dad35075ade081e53ec85f66508965116164
doc_id: 47200
cord_uid: b165dvns

An implementation of Viro’s patchworking in polymake is presented, and a census of Betti numbers of real tropical surfaces serves as a showcase. The latter is relevant in the context of Hilbert’s 16th Problem.

Hilbert's 16th problem asks about topological constraints for real algebraic hypersurfaces in projective space. In the 1980s Viro developed patchworking as a combinatorial method to construct real algebraic hypersurfaces with unusually large Z 2 -Betti numbers [14] [15] [16] [17] . A major breakthrough of this idea was Itenberg's refutation of Ragsdale's Conjecture [9] . Today patchworking is most naturally interpreted within the larger framework of tropical geometry [12] . In this way patchworking is a combinatorial avenue to real tropical hypersurfaces.

Here we report on a recent implementation of patchworking and real tropical hypersurfaces in polymake [1] , version 4.1 of June 2020. The first software for patchworking that we are aware of is the "Combinatorial Patchworking Tool" [4] , which works web-based and is restricted to the planar case. A second implementation is Viro.sage [18] which is capable of patchworking in arbitrary dimension and degree. Our implementation has the same scope as Viro.sage but it is superior in two ways. First, it naturally ties in with a comprehensive hierarchy of polyhedral objects in polymake; e.g., this allows for a rich choice of constructions of real tropical hypersurfaces. Second, our implementation is more efficient. This is demonstrated by several experiments with curves and surfaces of various degrees. As a new mathematical contribution we provide a census of Betti numbers of real tropical surfaces.

Let f = v∈V c v x v ∈ T[x 1 , . . . , x n ] be a tropical polynomial where V is a finite subset of Z n . We use the multi-index notation x v = x v1 1 · · · x vn n , and T = R ∪ {∞}, ⊕= min and =+. The tropical hypersurface T (f ) is the tropical vanishing locus of f , i.e., the set of points in R n , where the minimum of the evaluation function x → f (x) is attained at least twice. Throughout we will assume that f is homogeneous of degree d, i.e., for each v ∈ V we have v 1 + · · · + v n = d. In that case T (f ) descends to the tropical projective torus R n /R1, where 1 = (1, . . . , 1). The Newton polytope of f is N (f ) = conv V , and the coefficients of f induce a regular subdivision, S(f ). The latter is dual to T (f ). We refer to [12] and [3] for further details.

The tropical projective space TP n−1 = (T n −{∞1})/R1 compactifies R n /R1. It is naturally stratified into lower dimensional tropical projective tori, marked by those coordinates which are finite. In this way the pair (TP n−1 , R n /R1) is naturally homeomorphic with an (n−1)-simplex and its interior. Often we will identify the tropical hypersurface T (f ) with its compactification in TP n−1 .

The following is essentially a condensed version of [13, §3.1] , with minor variations. A sign distribution ∈ Z V 2 can be symmetrized to the function

As in [6] we choose our signs in Z 2 = {0, 1}, which corresponds to ±1 via z → (−1) z . Further, the elements z ∈ Z n 2 are in bijection with the 2 n orthants of R n via z → pos{(−1) z1 e 1 , . . . , (−1) zn e n }, where e 1 , . . . , e n are the standard basis vectors of R n , and pos(·) denotes the nonnegative hull. We will use this identification throughout and, consequently, we call z itself an orthant.

The tropical hypersurface T (f ) is a polyhedral complex in TP n−1 , and its k-dimensional cells are dual to the (n−1−k)-cells of S(f ). In particular, each maximal cell F of T (f ) corresponds to an edge, V (F ) ⊂ V , of S(f ). We write T n−2 for the set of maximal cells (which are (n−2)-dimensional polyhedra) and denote powersets as P(·).

Note that there are no (n−2)-cells of T (f ) in the boundary TP n−1 − R n /R1. The real phase structure on T (f ) induced by is the map

That is, for each maximal cell Let z, defined by z i = 1 − z i , be the antipode of z ∈ Z n 2 . We define an equivalence relation ∼ on Z n 2 × TP n−1 , which identifies copies of TP n−1 along common strata, by letting

This identifies {z} × TP n−1 and {z} × TP n−1 one to one for each z. It follows that the quotient (Z n 2 × TP n−1 )/∼ is homeomorphic to the real projective space RP n−1 . Combinatorially that construction can be seen as follows: the union of ) × TP n−1 . To avoid cumbersome notation and language we call the quotient of RT (f ) by ∼ also the real part of T (f ) and use the same symbol, RT (f ). In this way RT (f ) becomes a piecewise linear hypersurface in RP n−1 ≈ Z n 2 × TP n−1 /∼. The above construction is relevant for its connection with real algebraic geometry. To simplify the exposition we now consider a special case: Setting Δ n−1 = conv{e 1 , . . . , e n }, we assume that the set V = d · Δ n−1 ∩ Z n is the set of lattice points in the dilated unit simplex. This entails that the projective toric variety generated from V is the (complex) projective space CP n−1 . The following result comes in various guises; this version occurs in [15] and [8, Proposition 2.6].

Then, for each sign distribution ∈ Z n 2 , there exists a nonsingular real algebraic hypersurface X in CP n−1 , also with Newton polytope

If additionally S(f ) is unimodular, i.e., each simplex has normalized volume one, this is "primitive patchworking". In the primitive case stronger conclusions hold [13, 16] . The notion "combinatorial patchworking" refers to the condition N (f ) = d·Δ n−1 . This is what our implementation supports, for arbitrary degrees and dimensions. More general results require to carefully take into account the toric geometry of N (f ).

With n = d = 3 we consider the tropical polynomial Fig. 1 (left) . The sign distribution = (0, 1, 0, 1, 1, 1, 1, 0, 1, 1) yields a real tropical curve with real part in Z 3 2 × TP 2 /∼ which has two components; cf. Fig. 1 (right) . This primitive patchwork corresponds to a classical Harnack curve of degree 3; cf. [9, Sec. 5].

Our goal is to exhibit a census of Betti numbers of real tropical surfaces in Z 4 2 × TP 3 /∼. Throughout the following let f be a tropical polynomial of degree d in n = 4 homogeneous variables; we will assume that S(f ) is a regular and full triangulation of V = d · Δ 3 ∩ Z 4 . That is, we focus on combinatorial patchworks. A triangulation of V is full if it uses all points in V ; a unimodular triangulation is necessarily full. While the converse holds in the plane, there are many more full triangulations of d · Δ 3 than unimodular ones if d ≥ 3. Further, with

which is the cardinality of V , we pick a sign vector ∈ Z k 2 . This gives rise to a real algebraic surface X in CP 3 whose real part RX is "near the tropical limit" RT (f ) in the sense of [13] . Itenberg [6, Theorems 3.2/3.3] showed that the Euler characteristic satisfies

with equality attained in the primitive/unimodular case. Moreover, by [6, The-

where b q (·) are Z 2 -Betti numbers; see also [7] for bounds without the fullness assumption. However, if S(f ) is even unimodular then, by [6, Theorem 4 

See Table 1 for explicit numbers in the range which is relevant for our experiments. The main result of [13] furnishes a vast generalization of (4) to arbitrary dimensions. The values k, χ , b 0 and b 1 are the right hand sides of (1), (2) , (4) and (3), respectively. 

is a full triangulation of 3 · Δ 3 which is not unimodular. Its f -vector reads (20, 60, 64, 23), and its automorphism group is of order 6. The sign distribution = (0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0) yields a real tropical surface RT (f ) whose real part has Betti vector (2, 1, 2) (Fig. 2) . 

The polyhedral description of RT (f ) directly gives a combinatorial description of the homology; see also [13, Proposition 3.17] . The cellular chain modules read

and ∂(σ ×{z}) = ∂(σ)×{z} defines the boundary maps. In fact this construction is a special case of a cellular (co-)sheaf [11] . Algorithmically it is beneficial that this does not require the geometric construction of RT (f ).

We used mptopcom [10] to compute regular and full triangulations of d · Δ 3 for 3 ≤ d ≤ 6, which are not necessarily unimodular. For d = 3 the total number of such triangulations is known to be 21 125 102 [10, Table 3 ], up to the natural action of the symmetric group S 4 . For higher degrees the corresponding numbers are unknown and probably out of reach for current hard-and software. Still we can compute some of those triangulations, for each degree. Our experiments suggest that, in order to see many different Betti vectors (b 0 , b 1 , b 0 ) , it is preferable to look at many different triangulations. This is feasible for degrees 3 and 4, where we created 1 000 000 and 100 000 orbits of triangulations, respectively. Each of them was equipped with 20 sign distributions which were picked uniformly at random; cf. share the same f -vector (20, 60, 64, 23). For d = 4 all the possible Betti vectors occur; cf. (2) and (3). The case of d = 5 turned out to be surprisingly difficult. In our standard setup mptopcom quickly produced about a hundred full and regular triangulations before it stalled. mptopcom's algorithm employs a very special search through the flip graph of the point configuration, and it finds all regular triangulations plus some non-regular ones connected by a sequence of flips. Apparently, most neighbors to our first 100 triangulations of 5 · Δ 3 are not regular or not full. As we were interested in exploring many different Betti vectors, we created a second sample of triangulations; to this end we employed a random walk on the flip graph of 5 · Δ 3 . After eliminating multiples, this gave an additional 13 000 regular and full triangulations. On each of the resulting 13 100 triangulations we tried 500 random sign distributions; cf. Fig. 4 (left) for the combined statistic. For d = 6 we checked 1 500 triangulations with 500 sign distributions each; cf. Fig. 4 (right) .

No matter how hard we try we will only see a tiny fraction of all possible real tropical surfaces of higher degrees. So the distributions for d = 5 and d = 6 may not even be close to the "truth". Yet for d = 5 we observed b 1 = 43, whereas b 1 = 45; cf. Table 1 . We found 61 triangulations of 5 · Δ 3 with five components, none of which were unimodular. The maximal number of components in the unimodular case was four. For d = 6 our census is way off the theoretical bounds.

polymake is a comprehensive software system for polyhedral geometry and related areas of mathematics [1] . Mathematical objects like tropical hypersurfaces are determined by their properties. Upon a user query the system directly returns a property (e.g., a tropical polynomial or the dual polyhedral subdivision) if it is known, or it computes it by applying a sequence of rules. Subsequently, the property asked for becomes known, along with any intermediate results. Throughout the life of such a big object the number of properties grows; objects, with their properties, can be saved and loaded again. The latter is useful, e.g., for processing data on a cluster and examining them on a laptop later.

The computation which is relevant here takes a tropical polynomial f (such that the Newton polytope N (f ) is a dilated simplex) and a sign distribution as input and computes the Z 2 -Betti numbers of the real part RT (f ) of the real tropical hypersurface T (f ). The individual steps are: (i) find the maximal cells of T (f ) via a dual convex hull computation; (ii) compute the Hasse diagram of the entire face lattice of T (f ); (iii) construct the chain complex (5) from that Hasse diagram; (iv) compute ranks of the boundary matrices mod 2. Each step is implemented as a separate rule, which makes the code highly modular and reusable. In particular, the only nontrivial implementation which is really new is step (iii).

We wish to give some details about the first two steps. Often the dual convex hull computation is the most expensive part. For this polymake has interfaces to several algorithms and implementations, the default being PPL [2] which is also used here. In general, it is difficult to predict which algorithm performs best; see [1] for extensive convex hull experiments. The computation of the Hasse diagram uses a combinatorial procedure whose complexity is linear in the size of the output, i.e., the total number of cells of the tropical hypersurface; cf. [5] .

To compare the running times of Viro.sage and polymake for computing the Betti numbers of patchworked hypersurfaces we conducted two experiments, one for Harnack curves and one for surfaces. All computations were carried out on an AMD Phenom II X6 1090T (3.2 GHz, 38528 bmips).

For the Harnack curves, where we have just one curve per degree (the cubic case is Example 2), we repeated the same computation ten times each. Figure 5 (left) shows the mean running time depending on the degree. The Viro.sage code showed a rather wide variety, while the polymake computations gave almost identical running times for each test.

The experiment for the surfaces is slightly different in that both the tropical polynomials (and triangulations) and the sign distributions were varied. For degrees 3, 4, 5, and 6 we took the first 2000, 1000, 100, and 75 triangulations (as enumerated by mptopcom), respectively, and measured the running time for 10 random sign distributions each. Figure 5 (right) shows a box plot for each degree. The boxes indicate the 2nd and 3rd quartiles, the whiskers mark the minimum and maximum time measurements, excluding outliers (i.e., measurements whose ratio to the median is either bigger than 4, or smaller than 0.25), which are marked separately. Again Viro.sage exhibits a much greater variety of running times than polymake. 

We have shown that our new implementation is capable of determining the Z 2 -Betti numbers of a patchworked surface of moderate degree within a few seconds. This allows for providing a rich census. One major reason for polymake being faster than Viro.sage [18] is that we avoid the explicit construction of a simplicial complex model of RT (f ). Moreover, polymake computes Z 2 Betti numbers directly, while Viro.sage goes through a standard homology computation with integer coefficients. polymake provides geometric realizations (and integral homology), too, but this is unnecessary here.

Computing convex hulls and counting integer points with polymake

The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems

Triangulations, Algorithms and Computation in Mathematics

Combinatorial patchworking tool

Algorithms for tight spans and tropical linear spaces

Topology of real algebraic T -surfaces

Critical points of real polynomials and topology of real algebraic T -surfaces

Viro theorem and topology of real and complex combinatorial hypersurfaces

Patchworking algebraic curves disproves the Ragsdale conjecture

Parallel enumeration of triangulations. Electron

Cellular sheaf cohomology of polymake

Introduction to Tropical Geometry

Bounding the Betti numbers of real hypersurfaces near the tropical limit

Curves of degree 7, curves of degree 8 and the Ragsdale conjecture

Gluing algebraic hypersurfaces, removing of singularities and constructions of curves. Topology conference

Gluing of plane real algebraic curves and constructions of curves of degrees 6 and 7

From the sixteenth Hilbert problem to tropical geometry

We are indebted to Ilia Itenberg, Johannes Rau and Kristin Shaw for valuable comments on a previous version of this text. Moreover, we are grateful to Lars Kastner and Benjamin Lorenz for helping with the experiments. M. Joswig has been supported by DFG (EXC 2046: "MATH + ", SFB-TRR 195: "Symbolic Tools in Mathematics and their Application", and GRK 2434: "Facets of Complexity").