Abstract
In classical algebraic complexity, theorems such as the Combinatorial Nullstellensatz and the Schwartz-Zippel Lemma provide the foundation for understanding polynomial behavior and identity testing. This paper extends these foundational results into the domain of tropical algebra, where polynomials are defined as "max-plus" expressions and roots correspond to the non-differentiable "kinks" of piecewise linear functions. The authors establish a tropical version of the Combinatorial Nullstellensatz and investigate the complexity of identity testing for sparse polynomials. A significant discovery is the divergence in the size of universal testing sets depending on whether the scalar field is real or rational. Finally, the paper explores the expressive power of tropical circuits, ultimately disproving the tropical analogue of the $\tau$-conjecture by demonstrating that small circuits can generate an exponential number of roots.
Introduction
Tropical geometry serves as a powerful bridge, translating complex algebraic varieties into simpler combinatorial structures like graphs and polyhedra. In the tropical (or max-plus) semiring, standard addition is replaced by the maximum function ($x \oplus y = \max(x, y)$) and multiplication is replaced by standard addition ($x \odot y = x + y$). Within this framework, a tropical polynomial is a piecewise linear convex function. A "root" in this context is not a point where the function evaluates to zero, but rather a point where the maximum is attained by at least two distinct monomials, creating a "kink" or a break in the function's linearity.
Despite the utility of tropical geometry, many computational questions regarding these polynomials remained open. This research addresses four primary areas: the conditions for polynomial vanishing, root counting on finite grids, the complexity of identity testing for sparse polynomials (fewnomials), and the validity of the $\tau$-conjecture in a tropical setting.
The Tropical Combinatorial Nullstellensatz
The authors establish a tropical version of the Combinatorial Nullstellensatz by examining the relationship between sets of points and sets of allowed monomials. They demonstrate that the existence of a vanishing polynomial—one that has a root at every point in a given set—is determined by the "singularity" of the associated tropical matrix.
Specifically, they prove that if the number of available monomials strictly exceeds the number of points, a vanishing tropical polynomial is guaranteed to exist. This result parallels the classical theorem but relies on the combinatorial properties of bijections between monomials and points that maximize the sum of their inner products.
Identity Testing and the Influence of the Field
A central problem in computational algebra is Polynomial Identity Testing (PIT): determining if a given polynomial is identically zero. For "sparse" polynomials (those with at most $k$ monomials), this involves finding a "universal testing set" of points such that any non-zero polynomial must evaluate to a non-root on at least one point in the set.
One of the paper's most surprising findings is that the size of these testing sets depends heavily on the underlying field, a departure from classical algebra.
- Over Real Numbers ($\mathbb{R}$): The authors use bipartite graph modeling to show that a $k$-sparse polynomial requires only $k$ points for testing.
- Over Rational Numbers ($\mathbb{Q}$): The problem becomes more complex, requiring $\Theta(kn)$ points for $n$ variables. For the specific case of two variables ($n=2$), the authors determine the exact size of the testing set to be $2k-1$.
This discrepancy is explored through discrete geometry, where the authors link identity testing over $\mathbb{Q}$ to the problem of "double coverings" of points by the boundaries of disjoint convex polyhedra.
Circuits vs. Formulas: Disproving the $\tau$-Conjecture
The paper highlights a massive disparity in expressive power between tropical formulas and tropical circuits. In a formula, each intermediate calculation is used only once, whereas in a circuit, results can be reused as inputs for multiple subsequent operations.
In classical complexity, the $\tau$-conjecture suggests that the number of roots of a polynomial should be polynomially bounded by the size of the circuit that computes it. The authors show that while this holds for tropical formulas (where a formula of size $s$ has at most $s$ roots), it fails for circuits. By adapting constructions from neural network theory, they demonstrate that a tropical circuit of size $O(n)$ can produce $2^n$ roots. This exponential growth effectively disproves the tropical version of the $\tau$-conjecture.
Conclusion and Future Directions
This work provides a comprehensive mapping of the tropical algebraic landscape, establishing bounds for root counting and identity testing that are distinct from their classical counterparts. However, several open questions remain, particularly regarding the exact size of universal testing sets for more than two variables over $\mathbb{Q}$. Additionally, the deep connection between tropical identity testing and the geometric problem of covering points with polytope boundaries suggests that further breakthroughs in discrete geometry will be required to fully resolve the complexity of tropical fewnomials.
Summary updated