Tropical Combinatorial Nullstellensatz and Fewnomials Testing

Lecture Notes in Computer Science. 2017. Vol. 10472. P. 284–297.

Podolskii V. V., Grigoriev D.

Tropical algebra emerges in many fields of mathematics such as algebraic geometry, mathematical physics and combinatorial optimization. In part, its importance is related to the fact that it makes various parameters of mathematical objects computationally accessible. Tropical polynomials play an important role in this, especially for the case of algebraic geometry. On the other hand, many algebraic questions behind tropical polynomials remain open. In this paper we address three basic questions on tropical polynomials closely related to their computational properties:

1. 1.

   Given a polynomial with a certain support (set of monomials) and a (finite) set of inputs, when is it possible for the polynomial to vanish on all these inputs?

    

2. 2.

   A more precise question, given a polynomial with a certain support and a (finite) set of inputs, how many roots can polynomial have on this set of inputs?

    

3. 3.

   Given an integer k, for which s there is a set of s inputs such that any non-zero polynomial with at most k monomials has a non-root among these inputs?

    

In the classical algebra well-known results in the direction of these questions are Combinatorial Nullstellensatz, Schwartz-Zippel Lemma and Universal Testing Set for sparse polynomials respectively. In this paper we extensively study these three questions for tropical polynomials and provide results analogous to the classical results mentioned above.

Keywords: tropical algebras, max-plus algebra, combinatorial nullstellensatz, tropical polynomial

Publication based on the results of: Теоретическая информатика (2017)