Tropicalization via Valuation over Puiseux Series

19 concepts12 papers1 proposal

Many problems in continuous mathematics—such as non-linear optimization, algebraic geometry, and statistical estimation—are difficult because of the intricate, smooth geometry of their underlying spaces. Conversely, purely combinatorial problems can be difficult because they lack the continuous structure needed to apply calculus or linear algebra.

Tropical geometry bridges this gap. By replacing the classical operations of addition and multiplication with minimization (or maximization) and addition, it transforms smooth algebraic varieties and convex sets into sharp, skeletal polyhedral complexes.

The core mechanism that makes this transformation rigorous is tropicalization via valuation maps over fields of Puiseux series. This framework acts as a two-way mirror: it allows researchers to either project complex continuous structures down to tractable combinatorial skeletons, or lift discrete problems up into the continuous realm where classical calculus and linear programming theorems hold.

The Mathematical Bridge: Puiseux Series and Valuation

To understand why this framework works, we must look at the algebraic object that mediates between the classical and tropical worlds: the field of Puiseux series (and its generalizations).

A Puiseux series is a formal power series in a parameter $t$ that allows for fractional exponents, taking the form:

$$f(t) = c_1 t^{a_1} + c_2 t^{a_2} + c_3 t^{a_3} + \dots$$

where the exponents $a_i$ are rational numbers sorted in increasing order ($a_1 < a_2 < a_3 < \dots$), and the coefficients $c_i$ belong to a field like the real or complex numbers.

The critical tool used to interact with these series is the nonarchimedean valuation map, denoted as $\text{val}(\cdot)$. The valuation map extracts the dominant asymptotic behavior of the series by looking at its leading exponent:

$$\text{val}(f) = a_1$$

As explained by Michael Joswig et al., this map serves as the fundamental bridge to tropical geometry. When you perform classical arithmetic on these series and look only at the leading exponents, addition and multiplication naturally morph into tropical operations:

$$\text{val}(f \times g) = \text{val}(f) + \text{val}(g)$$ $$\text{val}(f + g) \ge \min(\text{val}(f), \text{val}(g))$$

By applying this valuation map element-wise to classical geometric objects defined over Puiseux series—such as vectors, matrices, or solutions to polynomial equations—we obtain their tropical counterparts. As noted in a comprehensive overview by Stephane Gaubert et al., this mapping preserves essential structural properties while stripping away algebraic complexity, making it a recurring theme for understanding computational complexity.

Classical Realm (Puiseux Series)          Tropical Realm (Real Numbers)
   f(t) = 3t² + 2t³ - t⁴                     val(f) = 2
         ×                                      +
   g(t) = 5t³ - t⁵                           val(g) = 3
         =                                      =
 f×g  = 15t⁵ + ...                         val(f×g) = 5

Lifting: Solving Combinatorial Problems via Continuous Machinery

One of the most powerful applications of this bridge is lifting. If a purely combinatorial or game-theoretic problem is too difficult to analyze directly, we can lift it into a classical geometric problem over a field of Puiseux fractions. Once in the continuous realm, we can deploy powerful classical theorems before projecting the solution back down.

A prime example of this is found in the study of Mean Payoff Games (MPGs). Xavier Allamigeon et al. demonstrated that these discrete, combinatorial games can be lifted into classical linear programs over generalized Puiseux series. By doing so, the authors were able to apply standard continuous linear programming theorems—specifically a variant of the shadow-vertex simplex algorithm—to prove that mean payoff games can be solved in polynomial time on average.

Similarly, Georg Loho et al. utilized this lifting strategy to establish the foundations of signed tropical convexity, which extends tropical geometry to include both positive and negative values. To validate signed tropical operations (like Fourier-Motzkin elimination or Farkas' Lemma), the authors lifted the tropical objects to classical polytopes over Puiseux series, ensuring that the combinatorial properties remained consistent with classical geometric intuition.

Projecting: Uncovering the Combinatorial Skeleton

The reverse direction—projecting a classical problem down to its tropical counterpart—is equally fruitful. This is particularly useful when trying to understand the fundamental limits or structural properties of continuous algorithms.

Consider the long-standing question of whether interior point methods for linear programming are strongly polynomial (meaning their runtime depends only on the number of constraints and variables, not the bit length of the inputs). To answer this, Xavier Allamigeon et al. applied the valuation map to the continuous "central paths" and polyhedra of classical linear programs.

By analyzing the tropicalized representations, the authors developed metric estimates (such as Hausdorff distance) to tightly couple the continuous behavior with the combinatorial structure. This tropical abstraction allowed them to construct an explicit counterexample, proving that log-barrier interior point methods are not strongly polynomial because the continuous path can be forced to mirror a highly twisted tropical path.

Classical Central Path (Continuous curve) 
       │
       ▼  [Valuation Map]
Tropical Central Path (Piecewise-linear skeletal path on a polyhedral complex)

Generalizing Beyond Polyhedra: Spectrahedra and Semialgebraic Sets

While early tropical geometry focused primarily on linear systems and polyhedra, recent research has extended the valuation-based mapping to more complex algebraic structures, such as spectrahedra (shapes defined by linear matrix inequalities) and semialgebraic sets.

Xavier Allamigeon et al. introduced the concept of tropical spectrahedra by applying nonarchimedean valuations to classical spectrahedra. A key theoretical insight established by the authors is that the valuation map transforms continuous semialgebraic sets into closed semilinear sets. This insight was subsequently leveraged by Xavier Allamigeon et al. to solve complex nonarchimedean semidefinite programs (SDPs) by mapping them to tropical spectrahedra, which can then be solved using combinatorial stochastic game algorithms.

This boundary-pushing work also resolved theoretical conjectures. For instance, Xavier Allamigeon et al. proved that the tropical analogue of the Helton-Nie conjecture holds true. By characterizing the tropicalization of convex semialgebraic sets over Puiseux series, the authors demonstrated that tropicalized convex semialgebraic sets and projected tropical spectrahedra are completely equivalent in the tropical realm, bridging convex algebraic geometry and game theory.

Broad Applications Across Mathematics

The utility of valuation-based tropicalization extends far beyond optimization, serving as a unifying language across diverse mathematical disciplines:

  • Algebraic Statistics: Emma Boniface et al. applied valuation maps to classical algebraic varieties and affine spaces defined over Puiseux series to solve the "tropical toric maximum likelihood estimation" problem, mapping statistical critical points directly to the geometric properties of underlying polytopes.
  • Combinatorics and Economics: Edin Husic et al. established deep connections between valuated matroids (which model gross substitute valuations in economics) and Lorentzian polynomials by showing how algebraic operations on these polynomials correspond directly to combinatorial operations on matroids under tropicalization.
  • Algebraic Geometry: Alex Abreu et al. used the metric structures and Jacobians of tropical curves to resolve complex Abel maps for singular, nodal algebraic curves, turning a daunting geometric degeneration problem into a tractable combinatorial one.
  • Representation Theory: Anton Alekseev et al. employed tropicalization to transform abstract geometric objects from Lie theory into polyhedral structures in Euclidean space, enabling direct algebraic comparisons that explain deep dualities (like Langlands and Poisson-Lie duality).

Ultimately, tropicalization via valuation works because it strips away the "meat" of continuous curves while perfectly preserving their topological and algebraic "bones." Whether lifting a game to solve it with a simplex algorithm or flattening a semidefinite program into a polyhedral complex, the valuation map over Puiseux series provides a rigorous, predictable translator between the continuous and the discrete.

Key Foundational Work

Linear Programs and Convex Hulls Over Fields of Puiseux Fractions (2015) — contributed 2 concept elements to this direction.
The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tropicalization_0119a2f7,
  title = {tropicalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tropicalization/rdr_0119a2f73d84436a8c2eb3af268186eb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tropicalization_0119a2f7_v1,
  title = {tropicalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tropicalization/rdr_0119a2f73d84436a8c2eb3af268186eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake