The Nullstellensatz and Positivstellensatz for Sparse Tropical Polynomial Systems

Abstract

Grigoriev and Podolskii (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 {\em 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.

arXiv comment32 pages + 3 pages of references, 11 figures, uses frenchineq.sty

References in corpus (8)

• Enumerative tropical algebraic geometry in R2
• The number of extreme points of tropical polyhedra
• The Fundamental Theorem of Tropical Differential Algebraic Geometry
• Computing mixed volume and all mixed cells in quermassintegral time
• Performance evaluation of an emergency call center: tropical polynomial systems applied to timed Petri nets
• Tropical Homotopy Continuation
• Computing Tropical Prevarieties with Satisfiability Modulo Theories (SMT) Solvers
• Geometry of higher rank valuations