The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems

Grigoriev and Podolskii (2018) have established a tropical analog of the effective Nullstellensatz, showing that a system of tropical polynomial equations is solvable if and only if a linearized system obtained from a truncated Macaulay matrix is solvable. They provided an upper bound of the minimal admissible truncation degree, as a function of the degrees of the tropical polynomials. We establish a tropical nullstellensatz adapted to sparse tropical polynomial systems. Our approach is inspired by a construction of Canny-Emiris (1993), refined by Sturmfels (1994). This leads to an improved bound of the truncation degree, which coincides with the classical Macaulay degree in the case of n + 1 equations in n unknowns. We also establish a tropical positivstellensatz, allowing one to decide the inclusion of tropical basic semialgebraic sets. This allows one to reduce decision problems for tropical semi-algebraic sets to the solution of systems of tropical linear equalities and inequalities. The later systems are known to be reducible to mean payoff games, which can be solved in practice, in a scalable way, by value iteration methods. We illustrate this approach by examples.