arXiv:1208.4248v1 [math.AG] 21 Aug 2012
Contents
1. 5 6 5 6 FIGURE 3 An example for converting a spanning tree on Ke into a Pr fer sequence and back The tree can also be considered as a 4 marked rational curve with additional labels at the interior vertices As one can see from the picture tropical rational n marked curves with d bounded edges can also be considered as graphs on n d 1 vertices We convert the un bounded leaves into terminal vertices labelled 1 n and arbitrarily attach labels n 1 2 d 1 to the other vertices This will allow us to establish a bijec tion between combinatorial types of rational curves and a certain kind of Priifer sequence Definition 6 3 A moduli Priifer sequence of order n and length d is a sequence a1 n a 1 for some d gt 0 n gt 3 with a n 1 n d 1 such that each entry occurs at least twice We call such a sequence ordered if after removing all occurrences of an entry but the first the sequence is sorted ascendingly We denote the set of all sequences of order n and length d by Pn a and the corre sponding ordered sequences by P 4 Example 6 4 The sequences 6 7 8 7 8 6 and 6 7 6 7 8 8 are ordered moduli sequences of order 5 and length 2 but the sequence 6 8 8 7 7 6 is not ordered Definition 6 5 For fixed n and d we call two sequences p q Pn a equivalent if there exists a permutation o S n 1 2 d 1 such that qi o p for all i Remark 6 6 It is easy to see that for fi2. 1 times By the Theorem above the valence of a vertex is dictated by the leaves adjacent to it Furthermore the leaves adjacent to a vertex Ua can be read off of the first n entries of the sequence Leaf i is adjacent to va if and only if P a So given a curve in the Psi class product vertex vg must have valence 3 K Iy so it occurs 2 K Iy 2 XY j p q ki times Conversely given a sequence fulfilling the above condition we obviously obtain a curve with the required valences We now want to give an algorithm that computes all of these Priifer sequences As it turns out this is easier if we require the k to be in decreasing order i e k gt kg gt gt k In the general case we will then have to apply a permutation to the k before computation and to the result afterwards The general idea is that we recursively compute all possible placements of each vertex that fulfill the conditions imposed by the k if we place vertex a at leaf i with k gt 0 then it has to occur more often Due to its length the algorithm has been split into several parts ITERATEPLACEMENTS goes through all possible entries of the Pr fer sequence re cursively It uses PLACEMENTS to compute all possible valid distributions of an entry given a certain configuration of free spaces in the Priifer sequence Algorithm 7 pSIPRODUCTSEQUENCESORDERED kj kn 1 Input Nonnegative integers k gt k2 gt gt kn 2 Output Al
3. atint gt w new WeightedComplex RAYS gt 1 0 1 1 0 1 1 0 1 1 0 1 MAXIMAL_CONES gt 0 1 2 3 4 5 TROPICAL_WEIGHTS gt 1 1 1 1 1 1 atint gt print is_irreducible w FALSE is displayed as an empty result atint gt print cycle_weight_space w 1 11000 001001 100100 010010 This finally allows us to give an algorithm that computes Vx Remark 3 18 One is often interested in the positive weights one can assign to a complex X to make it balanced This is now very easy using polymake Simply intersect Vx with the positive orthant Rs and you will obtain the weight cone of X 4 INTERSECTION PRODUCTS IN R There are two main equivalent definitions for an intersection product in R the fan displacement rule Theorem 3 2 and via rational functions AR At first sight the computationally most feasible one seems to be the latter since we can already compute it with the means available to us so far Let X Y be tropical cycles in R and y max z y R x R gt R Denote by am IR xR gt R the projection onto the first n coordinates Then we define XV te Pr pn Xx Y Here applying m just means forgetting the last n coordinates However comput ing this directly turns out to be rather inefficient The main reason is that since we compute on the product X x Y we multiply the number of their maximal cones by each other and double the ambien
4. G Ziegler Lectures on polytopes Springer Verlag 1994 Graduate Texts in Mathematics 152 SIMON HAMPE FACHBEREICH MATHEMATIK TECHNISCHE UNIVERSITAT KAISERSLAUTERN POST FACH 3049 67653 KAISERSLAUTERN GERMANY E mail address hampe mathematik uni kl de
5. The polymake extension a tint All of what has been discussed in the previous sections has been implemented by the author in an extension for polymake www polymake org It can be obtained under https bitbucket org hampe atint Installation instructions and a user manual can be found under the Wiki tab We include here a list of most of the features of the software e Creating weighted polyhedral fans complexes e Basic operations on weighted polyhedral complexes Cartesian product k skeleton affine transformations computing lattice normals checking bal ancing condition e Visualization Display varieties in R or R including optional weight labels and coordinate labels e Compute degree and recession fan experimental 28 SIMON HAMPE e Rational functions Arbitrary rational functions given as complexes with function values and tropical polynomials min and max e Basic linear arithmetic on rational functions Compute linear combinations of functions e Divisor computation Compute k fold divisor of a rational function on a tropical variety e Intersection products Compute cycle intersections in R e Intersection products on matroid fans via rational functions defined by chains of flats this is very slow e Local computations Compute divisors intersections locally around a given face a given point e Functions to create tropical linear spaces e Functions to create matroid fans using a modified v
6. The set theoretic union of all cells in X is denoted by the support of X We call X pure dimensional or pure if all inclusion maximal cells are of the same dimension We call rational if all polyhedral cells are defined by inequalities Ax gt b with rational coefficients A If not explicitly stated otherwise all complexes and fans in this paper will be pure and rational Note that a polyhedral complex is uniquely defined by giving all its top dimensional cells This is the way in which complexes are also usually handled in polymake You specify the vertices and rays of the complex and then define the top dimensional cells in terms of these rays Hence we will often identify a polyhedral complex with its set of maximal cells The last definition we need is the normal fan of a polytope i e a bounded polyhe dron Let be a polytope T any face of o The normal cone of T in is Nz o w R w t max w x x2 o for all ter i e the closure of the set of all linear forms which take their maximum on 7 These sets are in fact cones and the collection of these cones is called the normal fan No of a 2 2 Tropical geometry Let X be a pure d dimensional rational polyhedral com plex in R Let o X and assume 7 lt is a face of dimension d 1 The primitive normal vector of T with respect to is defined as follows By definition there is a linear form g Z such that its minimal locus on is r
7. Then there is a unique generator of A A Z denoted by u such that g u gt 0 One can also define this for a polyhedral complex in a vector space A R for a prescribed lattice A see for example GKM If not stated otherwise we will however always consider the standard lattice Z A tropical cycle X w is a pure rational d dimensional complex X together with a weight function w X gt Z such that for all codimension one faces r X 4 SIMON HAMPE it fulfills the balancing condition 5 w o uojr 0 V V O gt T We call X a tropical variety if furthermore all weights are positive Two tropical cycles are considered equivalent if they have the same support and there is a finer polyhedral structure on this support that respects both weight functions Hence we will sometimes distinguish between a tropical cycle X and a specific polyhedral structure We also want to define the local picture of around a given cell Let 7 be any polyhedral cell Let Il V gt V V be the residue morphism We define Starx T Rso HW o 7 7 lt ce X u 0 which is a fan in V V on the lattice A A If we furthermore equip Starx rT with the weight function wgtar Rso II o 7 wx o for all maximal o then Stary T wstar is a tropical fan cycle 3 BASIC COMPUTATIONS IN TROPICAL GEOMETRY 3 1 Computing the primitive normal vector The primitive normal vector Uoj defined in the previous section
8. 12 Now create edges 13 for i n 1 n d 1 do 15 li n Ay 16 if length P gt 0 then 17 We denote by P 0 the first element of the sequence P 18 Apio Apio U A 19 V V i 20 P Disi DN 21 endif 22 end for 23 Create final edge 24 Ig Aminv to the first vertex in P which is 13 Hence A13 A 3UAg 1 2 We remove 9 from V and set P to be 13 14 14 Now v min V P 10 We obtain the second split Ip Ajo 3 4 The we connect vertex 10 to 13 so A13 A13 U A10 1 2 3 4 We set V 11 12 13 14 and P 14 14 In the next two iterations we obtain splits Iz Ai 5 6 I4 Aig 7 8 and we connect both 11 and 12 to 14 setting A14 5 6 7 8 Now P and V 13 14 so we leave the for loop and set the final split to be I5 Ai3 1 2 3 4 3 45 6 2 9 13 14 12758 FIGURE 4 The curve corresponding to the moduli sequence P including labels for the interior vertices 6 3 Enumerating maximal cones of Mnp We now want to apply the results of the previous section to compute Mp For this it is of course sufficient to compute all maximal cones More precisely we will only need to compute all combinatorial types corresponding to maximal cones i e rational n marked tropical curves whose vertices are all three valent Using Algorithm 6 we can then compute its rays Ur UI _3 These can easily be converted into matroid coordinates with the construction given in Exa
9. 3260v1 K Fukuda cdd cddplus and cddlib homepage 2002 available at http www ifor math E Feichtner and B Sturmfels Matroid polytopes nested sets and Bergman fans Port Math N S 62 2005 437 468 available at arxiv math 0411260 W Fulton and B Sturmfels Intersection theory on toric varieties Topology 36 1997 no 2 available at arxiv 9403002 A Gathmann M Kerber and H Markwig Tropical fans and the moduli spaces of tropical curves Compos Math 145 2009 no 1 173 195 available at arxiv 0708 2268 E Gawrilow and M Joswig polymake a Framework for Analyzing Convex Polytopes Polytopes Combinatorics and Computation 2000 pp 43 74 polymake is available at B Griinbaum Convex polytopes 2nd ed Springer Verlag 2003 G Havas B S Majewski and K R Matthews Extended gcd and Hermite normal form algorithms via lattice basis reduction Experimental Mathematics 7 1998 125 136 A N Jensen and J Yu Stable intersections of tropical varieties work in progress M Kerber and H Markwig Intersecting Psi classes on tropical Mo n Int Math Res Notices 2009 2009 no 2 221 240 available at jarxiv 0709 3953v2 Z A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 31 L Khachiyan E Boros K Elbassioni V Gurvich and K Makino On the complexity of some enumeration problems for matroids SIAM J Discrete Math 19 2006 no 4 966 984 A Nabutovsky Einstein structures Existence
10. 66 TABLE 2 Comparing successive divisors to intersection products 7 3 3 Matroid fan computation Here we compare the computation of matroid fans with different algorithms In Table 3 we compare computation of the moduli space Mn first as the Bergman fan B Kn 1 of the complete graph on n 1 vertices using the TropLi algorithms then combinatorially as described in Corollary 6 10 Table 4 shows some more examples of Bergman fans We compare the performance of the TropLi algorithms to the normal fan Algorithm 3 First we compute the Bergman fan of the uniform matroid Un x Note that we compute it as a Bergman fan of a matroid without making use of the matrix structure behind it the uniform matroid is actually realizable Then we compute two linear matroids i e we let TropLi make use of linear algebra to compute fundamental circuits C has as column vectors the vertices of the i dimensional unit cube lWe did not use the original TropLi program but an implementation of the algorithms in polymake C In the case of linear matroids the original program is actually much faster This is probably due to the fact that the data types in polymake are larger and that the linear algebra library used by TropLi is more efficient 30 FS1 FS2 GKM GJ HMM JY SIMON HAMPE n 6 7 8 TropLi 0 3 921 a tint 0 0 0 TABLE 3 Computation of M TropLi a tint U9 6
11. 8 8 9 7 7 9 but this sequence would never occur in the algorithm After having placed the first two 7 s in PLACEMENTS we would already have 6 0 so the last two 7 s are never tried out For completeness we also give the algorithm for the general case Algorithm 8 PSIPRODUCTSEQUENCES k1 kn 1 Input A list of nonnegative integers k ky kn 2 Output All Priifer sequences corresponding to maximal cones in pe tenes kn Mn 3 Let Sn such that o k is ordered descendingly 4 PSIPRODUCTSEQUENCESORDERED o k 5 return oa l applied elementwise to the first n entries of each sequence polymake example Computing psi classes This computes Y Y2 v6 Mo 9 which is a point and displays its multiplicity atint gt p psi_product 9 new Vector lt Int gt 3 2 0 0 0 1 0 0 0 atint gt print p gt TROPICAL_WEIGHTS 60 6 5 Computing rational curves from a given metric In previous sections we computed rational curves as elements of the moduli space given by their cor responding bounded edges i e the vy that span the cone containing the curve Usually we will be given the curves either in the matroid coordinates of the moduli space or as a vector in RC i e a metric on the leaves It is relatively easy to convert the matroid coordinates to a metric but it is not trivial to convert the metric to a combinatorial description of the curve i e a list of the splits induced by the bounded edge
12. Hence P C has only entries in n 1 n d 1 In addition it is easy to see that each interior vertex v occurs exactly val v 1 times since we remove val v 1 adjacent edges before the vertex becomes itself a leaf i e at least twice Injectivity follows from the fact that if two curves induce the same ordered sequence they can only differ by a relabelling of the interior vertices so the combinatorial types are in fact the same Surjectivity is also clear since the graph constructed from any P P 4 is obviously a labelling of a rational n marked curve We now present algorithm 6 which given a moduli sequence computes the cor responding combinatorial type in terms of its edge splits it is more or less just a slight modification of Algorithm 5 Theorem 6 8 In the notation of Algorithm 6 the procedure generates the set of splits I q of the combinatorial type corresponding to P More precisely If u t is the element chosen from V in iteration i e nt 1 n d 1 then In is the split on the leaves 1 n induced by the edge v i pi Proof Let v i be the element chosen in iteration i corresponding to vertex w in the curve In particular i P This means that i has already occurred val w 1 times in the sequence P as P 0 Hence the node v i is already val w 1 valent i e connected to nodes q j 1 val w 1 If q is a leaf i e lt n then qj Avy Otherwise qj must ha
13. Hence we would like a method to compute M or parts thereof in some combinatorial manner The main instrument for this task is presented in the following subsection 6 2 Priifer sequences Cayley s Theorem states that the number of spanning trees in the complete graph Kn on n vertices is n One possible proof uses so called Pr fer sequences A Pr fer sequence of length n 2 is a sequence 1 an 2 with a 1 n Repetitions allowed One can now give two very simple algo rithms for converting a spanning tree in Kn into such a Pr fer sequence Algorithm and vice versa Algorithm 5 Algorithm 4 PRUEFERSEQUENCEFROMGRAPH T 1 Input A spanning tree T in Kn 2 Output A sequence P aj n 2 a n 3 Pis Q 4 while No of nodes of T gt 2 do 5 Find the smallest node 7 that is a leaf and let v be the adjacent node 6 Remove i from T 7 P P v 8 end while It is easy to see that this induces a bijection see for example Chapter 30 An example for this is given in Figure 8 A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 15 Algorithm 5 GRAPHFROMPRUEFERSEQUENCE P Input A sequence P a1 n 2 a n Output A spanning tree T in Kn T graph on n nodes with no edges V n while V gt 2 do Let i min V N P Let j be the first element of P Connect nodes 7 and j in T Remove i from V and the first element from P end while Connect the two nodes left in V aon
14. INPUT_STRING gt 2 3 2 3 4 1 12 1 2 3 4 12 9 10 8 9 10 11 13 8 9 10 11 13 atint gt m local_mOn c atint gt print m gt MAXIMAL_CONES gt rows 15 atint gt print m gt IS_BALANCED 1 7 APPENDIX 7 1 Open questions and further research 7 1 1 More efficient polyhedral computations As we already discussed in previous sections most polyhedral operations occurring in tropical computations can in gen eral be arbitrarily bad in terms of performance However it remains to be seen how different convex hull algorithms compare in the case of tropical varieties So far a tint only makes use of the double description method F Also measure ments indicate that many computations are much faster when all cones involved are simplicial see the discussion in Section raul Since we are not bound to a fixed polyhedral structure in tropical geometry it would be interesting to see if we gain anything by subdividing all complexes involved before we do any actual computations 7 1 2 A computable intersection product on matroid fans A very interesting ques tion is whether one can find another description of intersection products in matroid fans that is suitable for computation One should be able to compute this from the bases of the matroid alone since that is what is usually given It would also be interesting to see if there is some local purely geometric criterion similar to Theorem 7 2
15. M if and only if M has no loops i e the union of its bases is the complete ground set Remark 5 2 The convex hull of the incidence vectors of the bases of a matroid is a polytope in R the so called matroid polytope Pm So the vectors w maximizing a certain basis are exactly the vectors in the normal cone of the vertex corresponding to that basis Hence the Bergman fan is a subfan of the normal fan of Pm In addi tion we know that it has dimension rank M this follows immediately from other possible definitions of B M see for example AK This gives us an algorithm to compute B M Algorithm 3 BERGMANFANFROMNORMALFAN 1 Input A matroid M on n elements given in terms of its bases 2 Output Its Bergman fan in R 3 Compute the normal fan F of the matroid polytope Pm 4 S the rank M skeleton of F 5 for a maximal cone in S do 6 Let p be the corresponding face of Py maximized by 7 Let o1 0q be the bases corresponding to the vertices of p 8 if Uo n then 9 Remove from S 10 end if 11 end for 12 return S w 1 While this algorithm is fairly simple to implement it is highly inefficient for two reasons Computing the skeleton of a fan from its maximal cones can be fairly expensive especially if we want to compute a low dimensional skeleton But mainly the problem is that from the potentially many cones of S we often only retain a small fraction Hence we compute a lot of s
16. algorithm based on these ideas Algorithm 2 MINKOWSKIINTERSECTION 1 Input Two tropical cycles X Y in R of codimension k and l respectively such that k 1 lt n 2 Output Their intersection product X Y 3 Compute the n k l skeleton Z of X NY 4 for o a maximal cell in Z do 5 Compute an interior point p rel into 6 Compute the local fans Starx p Stary p 7 if for any p Starx p p2 Stary p the cell p1 p2 is n dimensional then 8 Compute weight wx y of as described above 9 else 10 Remove o 11 end if 12 end for 13 return Z wx y polymake example Computing an intersection product This computes the self intersection of the standard tropical line in R atint gt 1 tropical_Ink 2 1 atint gt i intersect 1 1 atint gt print i gt TROPICAL_WEIGHTS 1 12 SIMON HAMPE 5 MATROID FANS Matroid fans are an important object of study in tropical geometry since they are the basic building blocks of what we would consider as smooth varieties There are several different but equivalent ways of associating a tropical fan to a matroid see for example AK FRI FS1 S3 S One possibility which immediately implies a method to compute the fan is given in Proposition 2 5 Definition 5 1 Let M be a matroid on n elements For w R let Mu be the matroid whose bases are the bases of M of maximal w cost Xico Wi Then w lies in the Bergman fan B
17. cycle with a fixed polyhedral structure Let N be the number of maximal cells o1 0n of We identify an integer vector w Z with the weight function g wi We define 8 SIMON HAMPE e Ax we ZN X w is balanced which is a lattice e Ve Ax 9R Now fix a codimension one cell 7 in X Let S be the induced polyhedral structure of Stary 7 For an integer vector w Z we denote by ws the induced weight function on S Then e AY we ZN S ws is balanced e Ve A 8R Remark 3 12 We obviously have Ay N extaimx 1 A and similarly for Vx Clearly if X is irreducible then dim Vx should be 1 and vice versa assuming that gcd w wy 1 where the w are the weights on However so far this definition is tied to the explicit choice of the polyhedral structure We would like to get rid of this restriction which we can do using Lemma 8 15 Hence we will also write Vx and Ax We call Vx the weight space and Ax the weight lattice of X Definition 3 13 Let X w be a d dimensional tropical cycle and a polyhedral structure on X We define an equivalence relation on the maximal cells of in the following way Two maximal cells 0 0 are equivalent if and only if there exists a sequence of maximal cells o 00 07 0 oi X such that for all i 0 r 1 the intersection g N 0 41 is a codimension one cell of 1 whose only adjacent maximal cells are g and oj41 Lemma 3 14 Leto and o be e
18. example GKM Definition 6 1 An n marked rational tropical curve is a metric graph with n unbounded edges labelled with numbers 1 n such that all vertices of the graph are at least three valent We can associate to each such curve C its metric vector d C ij i lt j R 2 where d C j is the distance between the unbounded edges called leaves marked i and j determined by the metric on C Define R gt RG a gt ai a icj Then Mn d C C n marked curve R 6 R is the moduli space of n marked rational tropical curves Remark 6 2 It is shown e g in GKM that Mn is a pure n 3 dimensional fan and if we assign weight 1 to each maximal cone it is balanced though they do not use the standard lattice as we will see below Points in the interior of the same cone correspond to curves with the same combinatorial type i e forgetting their metric they are equal In particular maximal cones correspond to curves where 14 SIMON HAMPE each vertex is exactly three valent We call this particular polyhedral structure on Mn the combinatorial subdivision The lattice for Mp under the embedding defined above is generated by the rays of the fan These correspond to curves with exactly one bounded edge Hence each such curve defines a partition or split I I on 1 n and we denote the resulting ray by vy note that vr vre Given any rational n marked curve each bounded edge EF of length a induce
19. is an essential part of most formulas and cal culations in tropical geometry Hence we will need an algorithm to compute it An important tool in this computation is the Hermite normal form of an integer matrix Definition 3 1 Let M Z be a matrix with n gt m We say that M is in Hermite normal form HNF if it is of the form M Omx n m T where T t j is an upper triangular matrix with t gt 0 and for j gt i we have tii gt tij gt 0 Remark 3 2 We are actually only interested in the fact that T is an upper tri angular invertible matrix Furthermore it is known that for any A Z there exists a U GL Z such that B AU is in HNF see for example 2 4 Proposition 3 3 Let X c R be a d dimensional tropical cycle T X 1 Let Ae Zin such that V ker A and Vs ker A where A denotes A without its first row Let U e GL Z such that AU O n a 1 x d 1 T is in HNF Denote by U the i th column of U Then 1 Usi Usa 1 is a Z basis for ker A V 2 Uy1 Ung is a Z basis for ker A V In particular U aq Ug mod Vz Proof It is clear that Uy1 Usa 1 form an R basis for ker A and the fact that det U 1 ensures that it is a Z basis Removing the first row of A corresponds to removing the first row of AU so we obtain an additional column of zeros Hence U 1 Uq is a basis of ker A and Uyg is a generator of A A A TINT ALGORITHMIC TROPICAL INT
20. m gt MAXIMAL_CONES gt rows 10395 6 4 Computing products of Psi classes A factor that often occurs in inter section products on moduli spaces are Psi classes In KM the authors describe tropical Psi classes as multiples of certain divisors of rational functions but also in combinatorial terms For nonnegative integers ky k and I n they define K 1 Dicer ki Then one of their main results is the following Theorem Theorem 6 12 KM Theorem 4 1 The intersection product wt kn Mzy is the subfan of Mn consisting of the closure of the cones of dimension n 3 K n corresponding to the abstract tropical curves C such that for each vertex V of C we have val V K Iv 3 where Iy i n leaf i is adjacent to V n The weight of the corresponding cone o C is Ivevo KUv Ii ki w o C In combination with Proposition 6 7 this allows us to compute these products in terms of Priifer sequences A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 19 Corollary 6 13 The maximal cones in we tees En Mn are in bijection to the ordered moduli sequences P P n 3 K n that fulfill the following condition Let d n 3 K n and ki 0 fori n 1 n d 1 For any a n 1 n d 1 let j jia 1 n d 1 be the indices such that P a Then l a lI a 2 gt ky i 1 Proof Recall that any entry a corresponding to a vertex vg in the curve C P occurs exactly val v
21. 0 3 U10 6 0 19 U11 6 0 87 C3 0 1 C4 1 29388 TABLE 4 Computation of several matroid fans REFERENCES M Aigner and G M Ziegler Proofs from THE BOOK Springer 1998 L Allermann and J Rau First steps in tropical intersection theory Math Z 264 2010 no 3 633 670 available at arxiv 0709 3705v3 F Ardila and C J Klivans The Bergman complex of a matroid and phylogenetic trees J Comb Theory Ser B 96 2006 38 49 available at arxiv math 0311370v2 D Avis D Bremner and R Seidel How good are convex hull algorithms Computational Geometry Theory and Applications 7 1997 265 302 D Avis and K Fukuda A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra Discrete and Computational Geometry 8 1992 295 313 J P Barth lemy and A Gu noche Trees and Proximity Representations Wiley Interscience Chichester 1991 E Brugall and K Shaw Obstructions to approximating tropical curves in surfaces via intersection theory 2001 available at arxiv 1110 0533v2 P Buneman A note on the metric properties of trees Journal of combinatorial theory 17 1974 48 50 H Cohen A course in computational algebraic number theory 4th ed Springer Verlag Berlin 2000 H Edelsbrunner Algorithms in combinatorial geometry Springer Verlag 1987 G Francois and J Rau The diagonal of tropical matroid varieties and cycle intersec tions available at arxiv 1012
22. 10 ITERATEPLACEMENTS current_vertex 1 v 11 end for 12 end if PLACEMENTS kj km 1 Input Positive integers k gt gt km 2 Output All subsets J m such that J 2 Djez kj 3 Let J i 1 4 while i gt 0 do 5 if J lt 2 Dj k then 6 Let le m J be minimal such that l gt max J and we haven t used it yet as i th element of J 7 if There is no such l then 8 STEPDOWN 9 else 10 Add l to the indices we have used as i th element of J 11 i i 1 12 J Ju i 13 end if 14 else 15 Add J to solution 16 STEPDOWN 17 end if 18 end while STEP DOWN 1 Forget all indices we used as i th element of J 2 J JN max J Se ae el decrease if we have tried all valid placements including a So assume 6 0 Then a as is a valid placement i e s 2 gt 77_ ka If we subtract this from the equation for J we obtain N 0 lt N s 5 ka i s 1 In particular since the k are ordered we must have ka 2 1 and hence also ka 2 1 for all j lt s This implies s 8224 ka gt 2 s i 1 A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 21 which is obviously a contradiction With this it is now easy to see that PSIPRODUCTSEQUENCESORDERED computes indeed all the required sequences Example 6 14 We do indeed need that k gt gt kn to be able to compute all sequences Assume n 7 and k1 k7 0 0 0 0 0 1 1 A valid sequence would be 7 7
23. 1208 4248vl1 math AG 21 Aug 2012 e arXiv A TINT A POLYMAKE EXTENSION FOR ALGORITHMIC TROPICAL INTERSECTION THEORY SIMON HAMPE ABSTRACT In this paper we study algorithmic aspects of tropical intersection theory We analyse how divisors and intersection products on tropical cycles can actually be computed using polyhedral geometry The main focus of this paper is the study of moduli spaces where the underlying combinatorics of the varieties involved allow a much more efficient way of computing certain tropical cycles The algorithms discussed here have been implemented in an extension for polymake a software for polyhedral computations 1 INTRODUCTION Tropical intersection theory has proved to be a powerful tool in tropical geome try The basic ideas for an intersection theory in R based on divisors of rational functions were first laid out in and were then further developed in AR Even earlier had proved the fan displacement rule in the context of toric geome try It describes how cohomology classes of a toric variety X A can be multiplied using a generic translation of A This was later translated to the concept of stable intersections of tropical varieties One can force two tropical varieties to intersect in the correct dimension by translating one of them locally by a generic vector The intersection multiplicities are then computed using the formula from the fan displacement rule An intersection product in matroi
24. 7 th entry is 1 for all other rays vyruzr it is 0 Hence ang 2 mos 2 m 2 m Zen i jzk leI Finally if k I say k I ko I then vr yr 1 There are m 1 choices for a ray vz z with j i Since n Xier e1 7 1 we get z enon m 1 m 2 42e 1 T leI TF i jzk Hence equation 6 1 holds Theorem 6 17 Let vz vn be the rays of T Then the set Be U Baw omy 0E pec val p gt 3 is a basis for V r In particular the dimension of V r can be calculated as dimV r dimr gt Ce val p pec val p gt 3 Proof By Lemma 6 16 these rays generate V We can write each vy in some o gt T in terms of W and the bounded edges at the vertex associated to it The first part of the Lemma then yields that we can replace any occurrence of v u7 to get a representation in B and the bounded edges To see that the set is linearly independent we do an induction on n For n 4 the statement is trivial For n gt 4 assume T is the vertex of Mn Then B actually agrees with the set Vk vg for some S and we are done So let p be a vertex of C that has only one bounded edge attached and denote by i one of the leaves 26 SIMON HAMPE attached to it It is easy to see that applying the forgetful map ft to B we get the set By 7 If p is three valent then the ray corresponding to the bounded edge at p is mapped to 0 and all other elements of B are mapped bijec
25. ELIMINARIES POLYHEDRAL AND TROPICAL GEOMETRY In this section we establish the basic terms and definitions of polyhedral and tropical geometry needed in this paper For a more thorough introduction to polytopes and polyhedra see for example z 2 1 Polyhedra and polyhedral complexes A polyhedron or polyhedral cell in V R is a set of the form o x Ax gt b where A e R b e R i e it is an intersection of finitely many halfspaces We call a cone if b 0 Equivalently any polyhedron can be described as o conv pi pe Rsori Ror L where p1 Pk T1 r1 R and L is a linear subspace of R The first de scription is often called an H description of o and the second is a V description of o It is a well known algorithmic problem in convex geometry to compute one of these descriptions from the other In fact both directions are computationally equivalent and there are several well known convegz hull algorithms Most notable are the double description method MRTT the reverse search method and the beneath and beyond algorithm e g E Generally speaking each of these algorithms behaves very well in terms of complexity for a certain class of polyhedra but very badly for some other types see for a more in depth discussion of this In general it is very difficult to say beforehand which algorithm would be optimal for a given polyhedron It is also an open problem whether there exists a conv
26. ERSECTION THEORY 5 Remark 3 4 In 2 4 3 Cohen suggests an algorithm for computing the HNF of a matrix using integer Gaussian elimination However he already states that this algorithm is useless for practical applications since the coefficients in intermediate steps of the computation explode too quickly A more practical solution is an LLL based normal form algorithm that reduces the coefficients in between elimination steps a tint uses an implementation based on the algorithm designed by Havas Majevski and Matthews in EMM Note that knowing the primitive normal vector up to sign it is easy to determine its final form since we know that the linear form defined by us must be positive on a So we only have to compute the scalar product of Ug with any ray in o that is not in 7 and check if it is positive What remains is to compute the matrix A such that A V There is an obvious notion of an irredundant H description of r Assume T Hin N Sj i 1 j 1 where H x R x zi a and S x R x w gt 8j for some zi wj Z Qi Bj R This is considered an irredundant H description if we cannot remove any of these without changing the intersection and we cannot change any of the inequalities into an equality Note that most convex hull algorithms return such an irredundant description Now it is basic linear algebra to see the following Lemma 3 5 Let 7 R be a polyhedron given by an irredun
27. I Proof 1 We define a a R via a 1 if i I and a s 3 otherwise Furthermore we define b b R via 0 if is a leaf attached to p bi 41 if i is not a leaf at p and lies in J s 3 ifiis not a leaf at p and does not lie in J 24 SIMON HAMPE We now prove the following equation to be considered as an equation in RC where each ray is represented by its metric vector gt v s 3 D UI ur bn b on a Me re We index RC by all sets T k1 k2 k ko We have 0 if k k2 Ij j 1 58 z s 2 if k h ka Ij j gt 1 Wo Ir 2 s 3 if ki Ii ko 1j3i j gt l i j We now study the right hand side in four different cases a If ky k2 J4 then both are not leaves at p Hence the right hand side yields 0 0 2 2 0 b If ki k2 I 7 gt 1 again both are not leaves at p The right hand side now yields 0 0 2 s 3 2 s 3 0 c Assume ky Ij k2 Ij i 7 gt 1 and i j If both are not leaves at p we get 2 s 3 0 2 s 3 2 s 3 If only one is a leaf we get s 3 0 s 3 2 s 3 Finally if both are leaves we get 0 0 0 2 s 3 So in any of these cases the right hand side agrees with the left hand side d Assume k k2 Ij j gt 1 If both are not leaves we get s 3 1 s 3 1 s 2 The other cases are similar 2 We know that J must be a union of some of the J and we assume without rest
28. S 1 ji such that I Ujes Ij Again this choice is unique Now map vy to vg in Myajp It is easy to see that this map must be bijective First let us see that the map is linear By Theorem we only have to check that the map respects the relations given in Lemma But this is clear since analogous equations hold in Mp again see KM Lemmas 2 4 and 2 7 for details For any set of rays vj Uj associated to the same vertex of C it is easy to see that they span a cone in Mn if and only if their images do Now if gt 7 is any cone we can partition its rays into subsets S 7 1 m that are associated to the same vertex pj Each of these sets of rays span a cone j which is mapped to a cone in Myai p Since o 01 X X Om it is mapped to a cone in Myai p X x Mval pm Hence Y is an isomorphism Finally if M is any polyhedral structure let 7 be the minimal cone of the combi natorial subdivision containing T Then l dimr and we have Star m T R4 x Star m 7 A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 27 polymake example Local computations in Mn This computes a local version of Mo 13 around a codimension 2 curve C with a single five valent vertex i e it computes all maximal cones containing the cone corresponding to C a tint keeps track of the local aspect of this complex so it will actually consider it as balanced atint gt c new RationalCurve N_LEAVES gt 13
29. compute intersection products in R and to create matroid fans 2 SIMON HAMPE Section 6 is the main focus of this paper Here we discuss how the combinatorial structure of the moduli spaces M of rational n marked tropical curves can be used to efficiently compute these spaces or certain subcycles thereof We introduce Pr fer sequences and show how they are in bijection to combinatorial types of rational curves Since Pr fer sequences are relatively easy to enumerate we can make use of this to compute parts of Mn We also show how the combinatorics of a rational curve can be retrieved from its metric vector and we study the local structure of Mn More precisely we show that locally around each point Mp is the Cartesian product of some R and several M with i lt n In Section 7 we list some open questions and the main features of a tint an extension for polymake that implements all of the algorithms discussed in this paper We also include some benchmarking tables that show how some algorithms compare to one another or react to a change in certain parameters Acknowledgement The author is supported by the Deutsche Forschungsgemein schaft grants GA 636 4 1 MA 4797 3 1 The software project a tint is part of the DFG priority project SPP 1489 www computeralgebra de I would like to thank Andreas Gathmann Anders Jensen Hannah Markwig Thomas Markwig and Kirsten Schmitz for their support and many helpful discussions 2 PR
30. d fans was introduced in S2 FR In particular this made it now possible to do intersection theory on moduli spaces Tropical intersection theory has many applications For example one can use to see that certain intersection products in toric varieties can be computed as trop ical intersection products It has also been used in to study the relative re alizability of tropical curves A prominent example of the usefulness of tropical intersection theory is enumerative geometry see for example GKM Rij KM One can formulate many combinatorially complex enumerative problems in terms of much simpler intersection products on moduli spaces However in concrete cases these products are still tedious to compute by hand especially in higher dimensions For the purpose of testing new conjectures or studying examples of a new and unfamiliar object one is often interested in such explicit computations This paper aims to analyse how one can efficiently compute divisors products of tropical cycles and other constructions frequently occurring in tropical intersection theory After briefly discussing the basic notions of polyhedral and tropical geometry we study some basic operations in tropical geometry in Section 3 We describe how a lattice normal vector and the divisor of a rational function are computed and we give an algorithm that can check whether a given tropical cycle is irreducible In Section 4 and 5 we discuss algorithms to
31. dant H representation T HAinN S with H x R x zi ai Denote by H x R x zi O Then r Zi V N H ker i 1 Zp Furthermore if T is a codimension one face of a polyhedral complex and T lt o then there is an le 1 r such that Vs N H ial Remark 3 6 There is an additional trick that can make lattice normal computa tions speed up by a factor of up to several hundred Assume you want to compute normal vectors of a 10 dimensional variety in R In this case we would have to compute the HNF of 11 x 20 matrices However for computing Uoj we can project c onto Vs Now the matrix of the codimension one face 7 is only a 1 x 10 matrix The normal form of this matrix can of course be computed much faster Note that we have to take care that the projection induces a lattice isomorphism on o For this we have to compute a lattice basis of which still requires computation of an HNF of the matrix associated to but only once instead of once for each codimension one face 3 2 Divisors of rational functions The most basic operation in tropical inter section theory is the computation of the divisor of a rational function Let us first discuss how we define a rational function and its divisor Our definition is the same as in AR Definition 3 7 Let X be a tropical variety A rational function on X is a function yp X gt R that is affine linear with integer slope on each cell of some arbit
32. e idea for constructing a basis is the following In addition to the rays of 7 we choose a basis for the M ayp at each higher valent vertex p This choice is similar to the one in KM Lemma 2 3 There the authors show that Vk vg S 2 k S is a generating set of the ambient space of Mp for any k n and it is easy to see that by removing any element it becomes a basis Now fix a vertex p of C such that s val p gt 3 Denote by the splits on n induced by the edges and leaves adjacent to p in particular some of the J might only contain one element We now define Wp vru 34 9 1 14 7 This corresponds to the set V described above and Bp Wp X VIguIs Clearly all the following results also hold if we choose i j k for some k gt 1 or remove a different element in the definition of B in particular because the numbering of the I is completely arbitrary To make the proofs more concise we will however stick to this particular choice We introduce one final notation For Z 1 we set vz 0 Lemma 6 16 see also Lemmas 2 4 and 2 7 1 Let p be a vertex of the generic curve C and define I1 Is W p as above Then 5 v 8 3 on ton 0 moa V veWp gel 2 Let vy be a ray in some o gt T and assume it separates some vertex p of C7 Define I1 1s Wp as above Assume without restriction that I T Then UL gt vs m 2 v Ur 5 vs mod Vz vseWp jl useWp Sel SS
33. epresentatives j1 jn from each partitioning set S and let p Vx gt R be the projection on these coor dinates jg By the previous considerations the map does not depend on the choice of representatives We claim that Im p Vx Let 7 be a codimension one cell of and 7 any codimension one cell of X contained in 7 Then Starz 7 Starx 7 so if w ZN makes balanced around 7 then p w makes balanced around T Bijectivity of p is obvious so Vx 2 Vx Theorem 3 16 Let X w be ad dimensional tropical cycle Then X is irreducible if and only if g gcd w a 0 X 1 and dimVx 1 Proof Let X be irreducible Clearly g must be 1 since otherwise a rational multiple of X would provide a full dimensional cycle in X not equal to k X for an integer k Now assume dim Vy rank Ax gt 1 Then we have an element w Z that is not a multiple of w and such that X w is balanced which is a contradiction to our assumption that X is irreducible Now let g 1 dimVx Assume X is not irreducible Then we can find a poly hedral structure of X and two weight functions w w on this polyhedral structure such that X w X w are both balanced and w k w for any integer k In particular dim Vx gt 2 which is a contradiction After having laid out these basics we want to see how we can actually compute this weight space Proposition 3 17 Let r be a codimensi
34. ersion of TropLi by Felipe Rinc n R3 e Creation functions for the moduli spaces of rational n marked curves Glob ally and locally around a given combinatorial type e Computing with rational curves Convert metric vectors moduli space elements back and forth to rational curves do linear arithmetic on rational curves e Morphisms Arbitrary morphisms given as complexes with values and linear maps e Pull backs Compute the pull back of any rational function along any mor phism e Evaluation maps Compute the evaluation map ev on the labelled version of the moduli spaces Mn 7 3 Benchmarks All measurements were taken on a standard office PC with 8 GB RAM and 8x2 8 GHz though no parallelization took place Time is given in seconds 7 3 1 Divisor computation Here we see how the performance of the computation of the divisor of a tropical polynomial on a cycle changes if we change different parameters In Table 1 we take a random tropical polynomial f with l terms where l e 5 10 15 We compute the divisor of this polynomial on X where X is Lx R in R L the standard tropical line i e X has 3 cones We do this ten times and take the average Note that the normal fan of the Newton polytope of f usually has around 15 maximal cones but is highly non simplicial It can have several hundred rays If instead of f we take a polynomial whose Newton polytope is the hypercube in R here the normal fan is simplicial the
35. ex hull algorithm with polynomial complexity in both input and output All of the above mentioned algorithms are implemented in polymake GJ At the moment all algorithms in a tint use the built in double description algorithm that was implemented by Fukuda F A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 3 For any polyhedron o we denote by V the vector space associated to the affine space spanned by g i e Vs a b a b o We denote by A Vs n Z its associated lattice The dimension of o is the dimension of V A face of o is any subset 7 that can be written as on H where H x x a A is an affine hyperplane such that is contained in one of the halfspaces x x a gt A or x x a lt A i e we change one or more of the inequalities defining o to an equality If 7 is a face of we write this 7 lt or 7 lt if the inclusion is proper By convention we will also say that is a face of itself Finally the relative interior of a polyhedron is the set rel int o a0 Ur TKO A polyhedral complex is a set of polyhedra that fulfills the following properties e For each o X and each face T lt 0 TEX e For each two o o X the intersection is a face of both If all of the polyhedra in are cones we call a fan We will denote by the set of all k dimensional polyhedra in and set the dimension of X to be the largest dimension of any polyhedron in X
36. l Priifer sequences corresponding to maximal cones in pe ee kn Mn K D ki current_vertex n 1 current_sequence 0 0 72n 4 K exponents k1 4n 0 0 Z ITERATEPLACEMENTS current_vertex current sequence Proof of Algorithm First of all we prove that PLACEMENTS computes indeed all possible subsets J m such that J 2 jez kj So let J a1 a be such a set with a lt lt ay It is easy to see that in each iteration of the while loop we have J i 1 Let 6 2 jeg kj J One can see by induction on 6 that starting in any iteration of the while loop the algorithm will eventually reach an iteration where 7 is one smaller This proves termination of PLACEMENTS But we can only reach the iteration where i 0 if in the previous iteration we have tried all indices 1 m as first element of J In particular there was a previous iteration where we chose l a as first element of J Now assume we are in the first iteration where J a1 a 1 lt s lt N Assuming 6 gt 0 we can again only 20 SIMON HAMPE ITERATEPLACEMENTS current_vertex current_sequence 1 if current_vertex gt 2n 2 K then 2 if current_sequence contains no 0 s then 3 append current_sequence to result 4 end if 5 else 6 f current_sequence 7 0 7 for P PLACEMENTS exp i 7 f do 8 v current_sequence 9 Place current_vertex in v at positions indicated by P
37. l gt 1 1 0 0 0 0 1 1 atint gt bm Bergman_fan_linear m atint gt u matroid uniform_matroid 3 4 atint gt bm2 Bergman fan matroid m 5 2 Intersection products on matroid fans Intersection products on matroid fans have been studied in S2 FR Both approaches however are not suitable for computation While the approach in is more theoretical except for surfaces where its approach might lead to a feasible algorithm the description in might seem applicable at first The authors define rational functions which applied to B M x B M cut out the diagonal Hence they can define an intersection product similar to AR However these rational functions are defined on a very fine polyhedral structure of B M induced by its chains of flats These are very hard to compute gives an incremental polynomial time algorithm but states that already the number of hyperplanes can be exponential and the subdivision computed by the algorithm of Rinc n is in general much coarser Also recall that this approach to computing an intersection product already proved to be inefficient in R It remains to be seen whether there might be a more suitable criterion for compu tation of matroid intersection products maybe similar to Theorem 4 1 6 MODULI SPACES OF RATIONAL CURVES 6 1 Basic notions We only present the basic notations and definitions related to tropical moduli spaces For more detailed information see for
38. l of cells is actually relevant However the ambient dimension of M is 3 n oe O n Convex hull computations and operations in linear algebra thus quickly become expensive We will show however that locally at any point 0 pe Mn the span of Star y p has a much lower dimension Hence we can do all our computations locally where we embed parts of Mn in a lower dimensional space Let us make this precise Definition 6 15 Let 7 be a d dimensional cone of M We define V r o 2730 Mn p U T p where U r U s rel int a It is easy to see that for any 0 pe Mn and T the minimal cone containing p the span of Star m p is exactly V r A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 23 We are now interested in finding a basis for this space V r preferably without having to do any computations in linear algebra The idea for this is the following Let C be the combinatorial type of an abstract curve represented by an interior point of r We want to find a set of rays vr all contained in some o gt 7 that generate V r Each such ray corresponds to separating edges and leaves at a vertex p of C along a new bounded edge whose split is of course I I We will see that for a fixed vertex p with valence greater than 3 all the rays separating that vertex span a space that has the same ambient dimension as M aj p In fact it is easy to see that they must be in bijection to the rays of that moduli space Hence th
39. mple 7 2 18 SIMON HAMPE Proposition 6 7 directly implies the following Corollary 6 10 The maximal cones of Mp are in bijection to all ordered Pr fer sequences of order n and length n 3 i e sequences a1 2n 4 with a in n 1 2n 2 such that each entry occurs exactly twice This also gives us an easy way to compute the number of maximal cones of Mn thus reproving the formula of Theorem 3 4 Lemma 6 11 The number of maximal cones in the coarse subdivision of Mn is n 4 UGG Proof We prove this by constructing ordered Priifer sequences of order n and length n 3 The sequence has 2n 4 entries Since it is ordered the first entry must always be n 1 This entry must occur once more so we have 2n 5 possibilities to place it in the sequence Assume we have placed all entries n 1 n k each of them twice Then the first free entry must be n k 1 since the sequence is ordered and we have 2 n k 5 possibilities to place the remaining one This implies the formula As one can see the complexity of this number is in O n so there is no hope for a fast algorithm to compute all of Mnp for larger n except using symmetries As we will see later however we are sometimes only interested in certain subsets or local parts of Mn polymake example Computing Mn This computes tropical Mo g and displays the number of its maximal cones atint gt m tropical _m0n 8 atint gt print
40. n all these computations take less then a second This is probably due to the fact that convex hull algorithms are very fast on nice polyhedra 7 3 2 Intersection products We want to see how computation of an intersection product compares to divisor computation If we apply several rational functions fi fk to R we can compute fi fk R in two ways Either as successive divisors f f2 R or as an intersection product f1 R fk R Since successive divisors of rational functions appear in many formulas and constructions it is interesting to see which method is faster Table 2 compares this for k 2 We take f and g to be random tropical polynomials with 5 terms and average over 50 runs As we can see the intersection product is significantly faster in low A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 29 n 2 4 6 8 10 k 1 0 3 0 3 0 3 0 3 0 3 0 2 0 3 0 5 0 4 0 5 0 3 0 5 36 8 1242 6 2327 3 3 0 2 0 3 0 3 0 3 0 4 0 6 0 5 0 5 0 7 38 4 1031 7 1860 6 5 0 3 0 3 0 3 1 9 1 8 2 2 43 9 1519 7 2313 5 0 4 0 4 6 1 12 2010 9 3149 2 9 0 4 2 4 22931 TABLE 1 Divisor of a random tropical polynomial dimensions but its computation time grows much more quickly For n 8 the intersection product takes seven times as long as the divisors n f g R f R GR 3 0 62 0 14 4 0 68 0 24 5 1 04 0 38 6 1 42 0 84 7 1 5 27 8 1 6 11
41. nt condition 2 Output A metric tree T with leaf vertices L labelled 1 n such that the induced metric on L equals d 3 Let V 1 n 4 while V gt 3 do 5 Find ordered triple of distinct elements p q r from V such that d p r d q r d p q is maximal 6 Let t be a new vertex and define its distance to the other vertices by d t p 5 d p 4 d p r aCa r d t x d x p d t p for x p If d t x 0 for any x identify t and x otherwise add t to V Attach p and q to t Then remove p and q from V 9 end while 10 Compute the tree on the remaining vertices using linear algebra g0 polymake example Converting curve descriptions This takes a ray from Mo in its moduli coordinates and displays it in different representations atint gt m tropical _m0n 6 atint gt r m gt RAYS gt row 0 atint gt print r 1 1 1 0 1 1 0 1 0 atint gt c rational_curve_from_moduli r atint gt print c 1 2 3 4 This means that this ray represents V 1 2 3 4 atint gt print c gt metric_vector 000110011011110 Read as d 1 2 d 1 3 d 5 6 6 6 Local bases of M When computing divisors or intersection products on moduli spaces Mn a major problem is the sheer size of the fans in the number of cones and in the dimension of the ambient space The number of cones can usually be reduced to an acceptable amount since one often knows that only a handfu
42. on one cell of a d dimensional tropical cycle X in R Let u1 up Z be representatives of the normal vectors usj for alla gt 7 Also choose a lattice basis l la 1 of Ar We define the following matrix M u1 up hy cdg ZED Then A n ker M nZ 41 x ZN where m is the projection onto the first k coordinates and N is again the number of maximal cells in X Proof Fix an order on the maximal cells of X and let J j N 7 is not a face of oj Then clearly ZY 2 e j J AX and it is easy to see that AX must be iso morphic to Z x Agtary r Hence it suffices to show that Agtary 7 is isomorphic to m ker M nZ 1 Let a1 01 01 ker M n Z Then Xau E b l Az so Starx T is balanced if we assign weights a In particular a1 a Agtarx 7 Since l lg 1 are a lattice basis any choice of the a such that Staryx 7 is balanced fixes the b uniquely so m is injective on ker M and surjective onto Asters tr 10 SIMON HAMPE Algorithm 1 WEIGHTSPACE X 1 Input A pure dimensional polyhedral complex X Output Its weight space Vx Vx RN for 7 a codimension one face of X do Compute M as above Vy 1 ker M e 7 is not a face of oj Vx Vx n V end for return Vx b polymake example Checking irreducibility This creates the six valent curve from example 2 and computes its weight space as row vectors
43. quivalent Then 1 Vo Vy 2 w o w o Proof We can assume that ono 7 X dimX 1 1 Choose any representatives Ug U9 7 of the lattice normal vectors Then w a Ug 7 w Wor Vr Let g1 gr AY such that g Vs ker Gr Since V V we have for all i 0 gi w o vo w vorr w 3 g Berfnr Hence v Vz and since Vy V x voj we have Vz Vs The other inclusion follows analogously 2 X is balanced at r if and only if Stary r is balanced which is a one dimensional fan with exactly two rays Such a fan can only be balanced if the weights of the two rays are equal Lemma 3 15 Let X and X be two polyhedral structures of a tropical cycle X Then Vx Vx and similarly for Ax Vx n Z A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 9 Proof We can assume without loss of generality that X is a refinement of X De note by N and N the number of maximal cells of and 4 respectively and fix an order on the maximal cells of both structures First of all assume two maximal cones of X are contained in the same maximal cone of 4 Since subdividing a polyhedral cell produces equivalent cells in terms of definition 3 13 they must have the same weight by Lemma 3 14 Thus the following map is well defined We par tition 1 N into sets S Siy such that j S lt gt of Co where o and gi are maximal cells of 4 and 4 respectively Pick r
44. rary polyhedral structure of X 6 SIMON HAMPE polymake example Computing a tropical variety This creates the weighted complex consisting of the four orthants of R with weight 1 and checks if it is balanced The maximal cones are represented in terms of indices of the rays starting the count with 0 atint gt w new WeightedComplex RAYS gt 1 0 1 0 0 1 0 1 MAXIMAL _CONES gt 0 2 0 3 1 2 1 31 TROPICAL WEIGHTS gt 1 1 1 1 atint gt print w gt IS_BALANCED 1 The divisor of y on X denoted by y X is defined as follows Choose a polyhedral structure of X such that y is affine linear on each cell Let X X 4 D pe the codimension one skeleton For each r 4 we define its weight via Wins 7 gt a ee uat pr 0 aj O gt T O gt T where Yo and p denote the linear part of the restriction of y to the respective cell Then P X X wox Remark 3 8 While the computation of the weights on the divisor is relatively easy to implement the main problem is computing the appropriate polyhedral structure The most general form of a rational function y on some cycle X would be given by its domain a polyhedral complex Y with X Y together with the values and slopes of y on the vertices and rays of Y To make sure that is affine linear on each cell of X we then have to compute the intersection of the complexes which boils down to computing the pairwise inter
45. riction that I Uj 1 for some k gt 1 Furthermore we define m i TC D s k 1 We now prove the following formula again in R 2 A similar formula for the representation of a ray vr in V and a similar proof can be found in KM Lemma 2 7 vr gt gt vnu M 22dodn gt a i jzk lel z 1 D vrur mod Vz 6 1 i jzk To see that the equation holds let us first compute w We index RC by all sets T k1 k2 k kg Then we have 0 if k1 k2 CI for some i 2 k 41 if k I k2 I or vice versa ki k2 Se Izk 2 if ki lika Lj i jii j gt k A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 25 Hence 0 if k1 k2 I for some i gt k Zesto 42 if k I k2 I or vice versa jzk kiko 2 if k l ka j i j i j 2k 0 if k1 k2 I for some i gt k 2 otherwise Finally we get w iki ka Thus it remains to prove that _ 2 m 2 if ki k2 I for some i gt k vr Z ha 7 0 otherwise For this let k k2 n If T k k2 I for some i gt k then vr r vru r 0 for all i j gt k and n Yiere1 7 2 Thus the formula holds Now if k j k2 Ij for i j and i j gt k we still have vr r 0 Furthermore there are m 2 choices for a ray vur with Fj 2 if k1 k2 I for some i gt k 0 otherwise and m 2 choices for a ray urur with i i For these rays the
46. s and their lengths The paper describes an algorithm to obtain a tree from a metric d on a given set S that fulfills the four point condition i e for all x y z t n we have d x y d z t lt max d x z d y t d x t d y z and Theorem 2 1 shows that the metrics induced by semi labelled trees es sentially rational n marked curves are exactly those which fulfill this condition Note that we can always assume d x y gt 0 for x y by adding an appropriate element from Im More precisely if we have an element d R that is equivalent to the metric of a curve modulo Im there is a k N such that d k e is a positive vector fulfilling the four point condition In fact if m d ain e is the equivalent metric then d a a e still fulfills the four point condition since adding positive multiples of e preserves it Algorithm 9 gives a short sketch of the algorithm described in Theorem 2 As input we provide a metric d We then obtain a metric tree with leaves L labelled 1 n such that the metric induced on L is equal to d This tree corresponds 22 SIMON HAMPE to a rational n marked curve Just replace the bounded edges attached to the leaf vertices by unbounded edges It is very easy to modify the algorithm such that it also computes the splits of all edges Algorithm 9 TREEFROMMETRIC d B Theorem 2 1 Input A metric d on the set n fulfilling the four poi
47. s some split J i 1 d on the leaves In the moduli space this curve is then contained in the cone spanned by the vz and can be written as a vy While this description of Mn is very useful to understand the moduli space in terms of combinatorics it is not very suitable for computational purposes By dividing out Im we have to make some choice of projection which would force us to do a lot of tedious and unnecessary calculations Also the special choice of a lattice would make normal vector computations difficult However there is a different representation of Mp It was proven in and FR that Mn B Kn 1 G ey 1 p as a tropical variety where Kn 1 is the matroid of the complete graph on n 1 vertices In paricular matroid fans are always defined with respect to the standard lattice Dividing out the lineality space 1 1 of a matroid fan can be done without much difficulty so we will usually want to represent M internally in ma troid fan coordinates while the user should still be able to access the combinatorial information hidden within The remaining parts of this section will be dedicated to this purpose While the description of Mp as a matroid fan automatically gives us a way to compute it it turns out that this is rather inefficient Furthermore as soon as we want to compute certain subsets of Mn e g Psi classes the computations quickly become infeasible due to the sheer size of the moduli spaces
48. section of all maximal cones of X and Y Here lies the main problem of computing divisors One usually computes the intersection of two cones by converting them to an H description and converting the joint description back to a V description via some convex hull algorithm But as we discussed earlier so far no convex hull algorithm is known that has polynomial runtime for all polyhedra Also shows that computing the intersection of two V polyhedra is NP complete Hence we already see a crucial factor for computing divisors besides the obvious ones dimension and ambient dimension The number of maximal cones of the tropical cycle and the domain of the rational function Table 1 in the appendix shows how divisor computation is affected by these parameters Example 3 9 The easiest example of a rational function is a tropical polynomial p x max vi x aii 1 r with v Z a R To this function we can associate its Newton polytope P conv v i ai i 1 r eR Denote by N its normal fan and define No N N 2 n41 1 Then N can be considered as a complete polyhedral complex in R and it is easy to see that is affine linear on each cone of this complex In fact each cone in the normal fan consists of those vectors maximizing a certain subset of the linear functions vi 1 n Qi En 1 at the same time So for any tropical polynomial y and any tropical variety X we can compute an appropriate pol
49. t dimension As we have discussed earlier both are factors to which the computation of divisors reacts very sensitively A different definition of the intersection product is given by Jensen and Yu in JY A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 11 Theorem 4 1 Let X Y be tropical cycles in R of dimension k and l respectively Let o be a k l n dimensional cone in the complezr X nY and p any point in rel int o Then o is a cell in X Y if and only if the Minkowski sum Starx p Stary p is complete i e its support is R This definition is very close to the fan displacement rule and it is in fact not difficult to see that they are equivalent So at first glance it would seem to be an unlikely candidate for an efficient intersection algorithm In particular it is in general algorithmically undecidable whether a given fan is complete see for example the appendix of N However one can also show that Starx p Stary p can be made into a tropical fan see for more details Since R is irreducible a tropical fan is complete if and only if it is n dimensional In this case it is a multiple of R The weight of the cone in the above Theorem is then computed in the following manner Lemma 4 2 JY Let o be a polyhedral cell in X Y Let p rel int o Then wx y o 5 wx p wy p2 i Ag Ap Mii p EStar x p p2 eStary p s t perel int p1 p2 This now allows us to write down an
50. tively onto the elements of By Since the latter is independent by induction so is B If p is higher valent only rays from B might be mapped to 0 or to the same element Hence if we have a linear relation on the rays in B we can assume by induction that only the elements in B have non trivial coefficients But these are linearly independent as well Let q be any other vertex with only one bounded edge and j any leaf at q Bp is now preserved under the forgetful map ft and hence linearly independent by induction At the beginning of this section we introduced the notion that the rays resolving a certain vertex of a combinatorial type C look like M ap The results above allow us to make this notion precise Corollary 6 18 Let M be any polyhedral structure of Mn and hence a refinement of the combinatorial subdivision Lettre M be a d dimensional cell Let C be the combinatorial type of a curve represented by a point in the relative interior of T Denote by pj px its vertices and by l the number of bounded edges of the curve Then Stary T Rat x M val p XxX M valp Proof First assume M is the combinatorial subdivision of Mp There is an obvious map Wr Star T md Mval p MER Meals defined in the following way For each vertex p of C fix a numbering of the adjacent edges and leaves J Now for each vy in some gt 7 there is a unique i 1 k such that vr separates p Let
51. uperfluous information 5 1 Computing matroid fans via circuits A different definition of a matroid fan can be given in terms of its circuits Definition 5 3 Let M be a matroid on n elements Then B M is the set of all elements w R such that for all circuits C of M the minimum min w i C is attained at least twice This definition actually produces the inversion in 0 of the fan in the first definition but that is obviously not a problem It is used by Felipe Rinc n in to compute the Bergman fans of linear matroids i e matroids associated to matrices His algo rithm requires the computation of a fundamental circuit C e I for an independent set I and some element e J such that Tu e is dependent C e I e u ie T J 2 u e is independent A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 13 It is an advantage of linear matroids that fundamental circuits can be computed very efficiently purely in terms of linear algebra For general matroids it can still be computed using brute force With this modified computation of fundamental circuits the algorithm of Rinc n can be used to compute Bergman fans of general matroids It turns out that this is still much faster than the normal fan algorithm above Table 4 in the appendix demonstrates this polymake example Computing matroid fans This computes the Bergman fan of a matrix matroid and of the uniform matroid U34 atint gt m new Matrix lt Rationa
52. ve been chosen as v k in a previous iteration k lt i Hence it must already be val w valent Inductively we see that each node behind qj is either a leaf or has already full valence In particular no further edges will be attached to any of these nodes By induction on i the edge v 7 q assuming q is not a leaf corresponds to the split A In particular A has been added to A Hence A is the split induced by the edge v i pi Example 6 9 Let us apply algorithm 6 to the following sequence P P see figure 4 for a picture of the corresponding curve P 9 9 10 10 11 11 12 12 13 13 14 14 The algorithm begins by attaching the leaves 1 8 to the appropriate vertices i e after the first for loop we have Ag 1 2 A10 3 4 A11 5 6 A12 7 8 and P 13 13 14 14 V 9 14 Now the minimal element of V P is v 9 We set J Ag 1 2 to be the split of the first edge Then we connect the vertex 9 A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY 17 Algorithm 6 COMBINATORIALTYPEFROMPRUEFERSEQUENCE P n 1 Input A moduli sequence P p1 PN Pra 2 Output The rational tropical n marked curve associated to P in terms of the splits J4 Ia induced by its bounded edges 3 d N n 1 4 V 1 n d 1 5 An i Antd 1 6 First Connect leaves 7 for i 1 n do 8 Ap Ap u i 9 V V i 10 P pisi Ppn 11 end for
53. versus uniqueness Geometric and Func tional Analysis 5 1995 no x 76 91 Grigory Mikhalkin Tropical geometry and its applications Proceedings of the ICM Madrid Spain 2006 827 852 available at arxiv math 0601041v2 T S Motzkin H Raiffa G L Thompson and R M Thrall The double description method Contributions to theory of games Vol 2 1953 J Rau Intersections on tropical moduli spaces 2008 available at arxiv 0812 3678v1 F Rinc n Computing Tropical Linear Spaces Journal of Symbolic Computation to appear available at arxiv 1109 4130 TropLi a software tool for computing tropical linear spaces berkeley edu felipe tropli P D Seymour A note on hyperplane generation Journal of Combinatorial Theory Series B 1 1994 no 1 88 91 K Shaw A tropical intersection product in matroidal fans 2010 available at D Speyer Tropical linear spaces SIAM J Discrete Math 22 2008 1527 1558 avail able at arsiv math 0410855 D Speyer and B Sturmfels The Tropical Grassmannian Advances in Geometry 4 2004 no 3 389 411 available at math 0304218 B Sturmfels Solving systems of polynomial equations CBMS Regional Conferences Series in Mathematics vol 97 Published for the Conference Board of the Mathematical Sciences Washington DC 2002 H R Tiwary On the Hardness of Computing Intersection Union and Minkowski Sum of Polytopes Discrete amp Computational Geometry 40 2008 no 3 469 479
54. xed n and d the set P 4 forms a system of representatives of P q modulo equivalence i e each sequence of order n and length d is equivalent to a unique ordered sequence We will need this equivalence relation to solve the following problem As stated above we want to associate Pr fer sequences to rational tropical curves by assigning vertex labels n 1 n2 d 1 to all interior vertices There is no canonical way to 16 SIMON HAMPE do this so we can associate different sequences to the same curve But two different choices of labellings will then yield two equivalent sequences Proposition 6 7 The set of combinatorial types of n marked rational tropical curves is in bijection to UR lt More precisely the set of all combinatorial types of curves with d bounded edges is in bijection to P 4 Proof The bijection is constructed as follows Given an n marked rational curve C with d bounded edges consider the unbounded leaves as vertices labelled 1 n Assign vertex labels n 1 n d 1 to the inner vertices Then compute the Pr fer sequence P C of this graph using Algorithm 4 and take the unique equivalent ordered sequence as image of C First of all we want to see that P C Pn a Since C has n d 1 vertices if consid ered as above the associated Pr fer sequence has indeed length n d 1 Further more the n smallest vertex numbers are assigned to the leaves so they will never occur in the Pr fer sequence
55. yhedral structure on X by intersecting it with N3 An example is given in Figure I A TINT ALGORITHMIC TROPICAL INTERSECTION THEORY T FIGURE 1 The surface is X max 1 y z y z R with weights all equal to 1 The curve is max 3xz 4 x y 2 y z 3 X the weights are given by the labels polymake example Computing a divisor This computes the divisors displayed in figure I atint gt f new MinMaxFunction INPUT_STRING gt max 1 x y z x y z x divisor linear_nspace 3 f g new MinMaxFunction INPUT_STRING gt max 3x 4 x y z y z 3 atint gt c divisor x g atint Vv atint Vv 3 3 Irreducibility of tropical cycles A property of classical varieties that one is often interested in is irreducibility and a decomposition into irreducible components While one can easily define a concept of irreducible tropical cycles there is in general no unique decomposition see Figure 2 We can however still ask whether a cycle is irreducible and what the possible decompositions are Definition 3 10 We call a d dimensional tropical cycle X irreducible if any other d dimensional cycle Y with Y X is an integer multiple of X FIGURE 2 The curve on the left is irreducible The curve on the right is reducible and there are several different ways to decompose it To compute whether a cycle is irreducible we have to introduce a few notations Definition 3 11 Let X be a tropical
Download Pdf Manuals
Related Search