Combinatorial Nullstellensatz, fewnomials and Shub-Smale's conjecture: tropical versions

Combinatorial Nullstellensatz (due to N. Alon) provides conditions in terms of the support of a polynomial when it can't vanish on a subset of an integer grid. We prove its tropical version. Moreover, we establish a sharp bound on the number of points in a grid at which a tropical polynomial can vanish (for classical polynomials it is called Schwartz-Zippel lemma). We estimate the size of universal sets at which no tropical fewnomial (with a fixed number of monomials) can vanish. This relates to Erdos problem from convex combinatorial geometry. Finally, we produce two tropical versions of Shub-Smale's conjecture and show that one of them is true and another is false.

(jointly with V. Podolskii)