Overview

This summer I participate in Google Summer of Code (GSoC) project: Implementation of Tropical Polynomials and its Corresponding Tropical Hypersurfaces.

My primary task was to implement tropical polynomials in SageMath, where I focused on creating new classes that extend polynomial implementation to support coefficient from tropical semirings, along with several methods to manage various functionality. Additionally, I implemented a class for tropical varieties, which facilitates the visualization of tropical hypersurfaces for multivariate tropical polynomials.

Activity Report

List of relevant issues and pull requests:

New classes for Tropical Polynomials ⭐

Developed new element classes specifically designed to handle tropical polynomials, building on the existing tropical semiring implementation in SageMath. We’ve created a separate class for univariate and multivariate cases, along with a parent class that encapsulates the semiring structure. These classes support operations like (tropical) addition, multiplication, and exponentiation (with scalar).

Univariate Tropical Polynomials 📈

We developed and implemented an algorithm to find the tropical roots of univariate tropical polynomials. These roots allow us to determine the tropical polynomial function, which is essentially a piecewise linear function. Using these result, we can then plot the graph of the tropical polynomial. A few examples of the graph:

Figure 1. Graph of $0x^2 + -1x + 1$ (max-plus algebra)Figure 2. Graph of $0x^2 + -1x + 1$ (min-plus algebra)
Figure 3. Graph of $-1x^5 + \frac{1}{3}x^4 + 1x^2 + \frac{1}{3}x$ (max-plus algebra)Figure 4. Graph of $-1x^5 + \frac{1}{3}x^4 + 1x^2 + \frac{1}{3}x$ (min-plus algebra)

The classes for univariate case can also handle interpolation of points, finding the split form, and determining the tropical factorization.

Tropical Variety

A tropical variety is defined as the corner locus of a tropical polynomial function, consisting of all points in $\mathbb{R}^n$ where the minimum (or maximum) of the function is attained at least twice. We developed and implemented an algorithm to compute the tropical variety for any multivariate tropical polynomial, with the ability to visualize these varieties in the cases of two and three variables. For dimensions greater than three, the result is also referred to as tropical hypersurface.

Tropical Curve 2️⃣

A tropical curve is a piecewise linear structure in $\mathbb{R}^2$ which can be seen as tropical roots of tropical polynomials in two variables. For these polynomials, we can also plot their graph, which consist of multiple surfaces in three dimensions. Some examples of these are:

Figure 5. Tropical Curve of $-2x^2 + -1x + \frac{1}{2}y$Figure 6. Graph of $-2x^2 + -1x + \frac{1}{2}y$
Figure 7. Tropical Curve of $2x^2 + 0xy + 2y^2 + 0x + -1y + 3$Figure 8. Graph of $2x^2 + 0xy + 2y^2 + 0x + -1y + 3$

The class for tropical curves also provides methods to check whether a tropical curve is simple or smooth, calculate the genus, and determine the contribution.

Tropical Surface 3️⃣

A tropical surface is a piecewise linear structure in $\mathbb{R}^3$ which can be seen as tropical roots of tropical polynomials in three variables. The tropical surface consists of planar regions and facets, referred to as cells. Some examples of these are:

Figure 9. Tropical Surface of $0x + 0y + 0z$Figure 10. Tropical Surface of $0x^2 + 0xyz + 0x + 0y + 0z + 1$

Dual Subdivision 🔗

Dual subdivision is a subdivision of the Newton polygon of tropical polynomials. This subdivision is dual in the sense that each face of the subdivision corresponds to a vertex of the tropical curve, and each edge of the subdivision corresponds to an edge of the tropical curve. This analogy extends to tropical varieties in higher dimensions, where the dual subdivision similarly reflects the structure of the variety. Some examples of these are:

Figure 11. Dual Subdivision of $2x^2 + 0xy + 2y^2 + 0x + -1y + 3$Figure 12. Dual Subdivion of $0x^2 + 0xyz + 0x + 0y + 0z + 1$

Weight Vectors ↗

As seen before, a tropical curve consists of line segments and half-lines, referred to as edges. These edges meet at a vertices, where the balancing condition is satisfied. This balancing condition ensures that the sum of the outgoing slopes at each vertex equals zero. We have also successfully extended the similar concept to tropical surfaces, where the sum of the outgoing normal vectors with respect to a line equals zero.

1sage: T = TropicalSemiring(QQ)
2sage: R.<x,y> = PolynomialRing(T)
3sage: p = R(2)*x^2 + x*y + R(2)*y^2 + R(3)
4sage: tv = p.tropical_variety()
5sage: tv.weight_vectors()
6{(1/2, 5/2): [(-1, -1), (0, 2), (1, -1)],
7 (5/2, 1/2): [(-1, -1), (-1, 1), (2, 0)]}

The above code shows there are $2$ vertices of tropical curve of $2x^2 + 0xy + 2y^2 + 3$. For each of these vertices, it can be seen that the associated list of vectors sums to $(0,0)$.

 1sage: T = TropicalSemiring(QQ)
 2sage: R.<x,y,z> = PolynomialRing(T)
 3sage: p = x^2 + R(-1)*y + z + R(1)
 4sage: tv = p.tropical_variety()
 5sage: tv.weight_vectors()
 6({0: ((1/2*u2, u2 + 1, u2), {u2 <= 1}),
 7  1: ((1/2, 2, u2), {1 <= u2}),
 8  2: ((1/2, u2, 1), {2 <= u2}),
 9  3: ((u1, 2, 1), {(1/2) <= u1})},
10 {0: [(1, 2, -5/2), (1, -5/2, 2), (-2, 1/2, 1/2)],
11  1: [(-1, -2, 0), (0, 2, 0), (1, 0, 0)],
12  2: [(1, 0, 2), (0, 0, -2), (-1, 0, 0)],
13  3: [(0, 1, 1), (0, 0, -1), (0, -1, 0)]})

The above code shows there are $4$ unique line of intersection of tropical surface of $0x^2 + -1y + 0z + 1$. For each of these lines, it can be seen that the associated list of vectors sums to $(0,0,0)$.

This balancing property applies to all tropical varieties, indicating that these geometric structures are balanced graphs.

Potential Future Improvements

  • Extending the tropical polynomial semiring to Laurent polynomial ring
  • Implement division of tropical polynomials in Laurent polynomial ring

Afterword

Implementing new classes and developing complex algorithms for various methods was quite challenging. However, the satisfaction of achieving the expected results and producing fascinating plots made the effort worthwhile.

I would like to express my deepest gratitude to my mentor, Travis Scrimshaw for helpful meetings and email exchanges. His support and guidance were important during my time on the project. I’m also thankful to Google for organizing this incredible event. Moving forward, I hope to continue contributing to SageMath. Until next time!

References

  1. Diane Maclagan and Bernd Sturmfels, Introduction to Tropical Geometry, American Mathematical Society, 2015.
  2. Erwan Brugalle and Kristin Shaw, A bit of tropical geometry, The American Mathematical Monthly, 121(7): 563-589, 2014.
  3. Ivana Filipan, An Invitation to Combinatorial Tropical Geometry, Conference: 1st Croatian Combinatorial Days, 2017.