The Nullstellensatz and Positivstellensatz for Sparse Tropical Polynomial Systems

Grigoriev and Podolskii (Discrete Comput Geom 59:507–552, 2018) have established a tropical analogue 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 and Emiris (in: Applied algebra, algebraic algorithms and error-correcting codes. Proceedings of 10th international symposium, AAECC-10, San Juan de Puerto Rico, Springer, Berlin, 1993), refined by Sturmfels (J Algebr Combin 3(2):207–236, 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.