This tutorial is probably also available as a Jupyter notebook in the demo folder in the polymake source and on github.

Different versions of this tutorial: latest release, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, nightly master

Tutorial: Patchworking real tropical hypersurfaces

Viro's combinatorial patchworking method takes as its input a regular subdivision $\tau$ of a dilated standard simplex $d\cdot\Delta_n$ (where $\Delta_n = \mathrm{conv}{e_1,\ldots,e_n}$), and a sign distribution on its vertices $s:\tau_0\rightarrow\mathbb Z/2\mathbb Z$, and builds a polyhedral hypersurface (a pure codimension 1 polyhedral complex), that is of the same topological type as some real algebraic hypersurface of degree $d$ (i.e., a real algebraic variety $\mathbb RV(F)$ for some real polynomial $F$ with $\mathrm{deg}F=d$).

We present an implementation of this method using real tropical hypersurfaces, with the induced regular subdivision of its Newton polytope taking the place of the above mentioned triangulation, as well as an efficient algorithm to compute the $\mathbb Z/2\mathbb Z$ homology of the resulting hypersurface, which also works for non-regular subdivisions (see below).

For the math, see for example Viro or, for the case of tropical hypersurfaces, Mikhalkin. This polymake implementation is discussed in

  • Joswig & Vater: Real tropical hyperfaces by patchworking in polymake, in: Mathematical software – ICMS 2020 (Bigatti et al, eds.), Springer, LNCS 12097, doi:10.1007/978-3-030-52200-1_20.

In the case of a real tropical hypersurface $T_s(f)$ (i.e., a tropical hypersurface $T(f)$ together with a sign distribution $s$ on its support), patchworking works by symmetrically gluing together $2^n$ copies of $H$ (one for each orthant of the ambient space $\mathbb R^n$), and then forgetting certain facets of these copies (this depends on $s$).

The quantity encoding which facets are remembered in which orthant is called its real phase structure. We call the resulting polyhedral hypersurface the corresponding patchworked hypersurfaces, or simply a realization of $T_s(f)$.

Naturally, we'll want to load Polymake's tropical application first:

> application "tropical";

The simplest non-trivial example builds a polyhedral line from a tropical line. So let's first create a tropical line:

> $h1 = new Hypersurface<Min>(POLYNOMIAL=>toTropicalPolynomial("min(x,y,z)"));
> print $h1->MONOMIALS;
(3) (2 1)
(3) (1 1)
(3) (0 1)

The line consists of 3 rays eminating from the point (0,0,0). This gives us one vertex. The points where the rays intersect the plane at infinity are also considered vertices.

0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
> print $h1->MAXIMAL_POLYTOPES; # the facets of the (original) tropical hypersurface
{0 3}
{1 3}
{2 3}

The property MAXIMAL_POLYTOPES is an IncidenceMatrix. An entry $k$ in the $i$-th row of MAXIMAL_POLYTOPES indicates the vertex (represented by the $k$-th row in PROJECTIVE_VERTICES) contained in the $i$-th facet of the tropical line.

We can now add a sign distribution on its monomials in the following way:

> $h1_pw1 = $h1->PATCHWORK(SIGNS=>[0,0,1]); # a real structure on $h1
> $h1_pw2 = $h1->PATCHWORK(SIGNS=>[1,0,1]); # another one, why not?

The property PATCHWORK represents a multiple subobject to a Hypersurface object (whether we deal with a Min or Max tropical hypersurface is irrelevant for the patchworking), parametrized by the property SIGNS with type Array<Bool>, which represents the sign distribution on its support. This subobject carries the information about the real tropical hypersurface.

Note that this allows us to create multiple “real structures” on the same tropical hypersurface object (as we did in the above example).

> print dense($h1_pw1->REAL_PHASE);
0 1 1 0
1 1 0 0
1 0 1 0

The property REAL_PHASE is an IncidenceMatrix, representing the real phase structure of the real tropical hypersurface, with the following semantics:

Each orthant $o\subset\mathbb R^n$ corresponds to a subset $o\cap{-e_1,\ldots,-e_n}\subset{-e_1,\ldots,-e_n}$, whose characteristic vector is the binary representation of a unique natural number $0\leq N_o< 2^n$. E.g. in the plane, the positive orthant has binary representation $(00)_2 = 0$, and the negative $(11)_2 = 3$.

The $j$-th entry in the $i$-th row of REAL_PHASE is now $1$ iff the $i$-th facet of the tropical hypersurface (represented by the $i$-th row of MAXIMAL_POLYTOPES; see above) is remembered in the orthant with binary representation $j$.

We can produce a realization of the patchworked hypersurface as a PolyhedralComplex with the user method ...->realize():

> $h1_pw_r = $h1_pw1->realize();
> print $h1_pw_r->COMBINATORIAL_DIM;
> svg($h1_pw_r->VISUAL);
Undefined subroutine &Polymake::User::svg called

Note that the realization is only unique up to combinatorial equivalence.

There are convenience functions to produce some classic algebraic curves:

> $harnack = harnack_curve(6); # harnack curve of degree 6
> $ragsdale = ragsdale_counterexample(); # a counterexample to the ragsdale conjecture
> $gudkov = gudkov_curve(); # gudkov curve (degree 6)

These return a Hypersurface object with a unique PATCHWORK property attached, to access it simply use ...->PATCHWORK.

> print $ragsdale->PATCHWORK->SIGNS;
> svg($ragsdale->PATCHWORK->realize("uniform")->VISUAL);
1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1
Undefined subroutine &Polymake::User::svg called

Naive computation of the homology of a patchworked hypersurface is computationally expensive, since its size depends exponentially on the dimension (we glue together $2^n$ copies of the tropical hypersurface).

Shaw & Renaudineau describe a way to exploit the symmetry of a patchworked hypersurface to compute its $\mathbb Z/2\mathbb Z$ homology directly from the triangulation + sign distribution, without needing to construct a polyhedral complex realization; cf. arXiv:1805.02030 or the published version here.

This leads to a straight forward algorithm, which is implemented in Polymake, and accessible in the following way:

> print $h1_pw1->CHAIN_COMPLEX_Z2;
<0 1 1
1 1 0
1 0 1
> print $h1_pw1->BETTI_NUMBERS_Z2;
1 1

It is possible to use this implementation starting with a (possibly non-regular) subdivision $\tau$ (i.e., without the data of a tropical hypersurface).

The usage is similar, you just have to define the hypersurface via the DUAL_SUBDIVISION property (even if mathematically no such hypersurface exists, i.e. in the non-regular case), instead the tropical POLYNOMIAL.

Here is such a non-regular subdivision of $4\Delta_2$, the “mother of all examples”:

> $moae = new fan::SubdivisionOfPoints(POINTS=>[[1,4,0,0],[1,0,4,0],[1,0,0,4],[1,2,1,1],[1,1,2,1],[1,1,1,2]],
>                                      MAXIMAL_CELLS=>[[0,1,3],[0,2,5],[0,3,5],[1,2,4],[1,3,4],[2,4,5],[3,4,5]]);
> $moae->VISUAL;
Automatic explosion
Exploding speed
Rotation speed
New tab
> $h2 = new Hypersurface<Min>(DUAL_SUBDIVISION=>$moae);
> $h2_pw = $h2->PATCHWORK(SIGNS=>[0,0,0,1,1,0]);
> print $h2_pw->BETTI_NUMBERS_Z2;
3 3
  • user_guide/tutorials/patchwork.txt
  • Last modified: 2020/06/15 12:50
  • by