Foundations of Computational Mathematics. The Journal of the Society for the Foundations of Computational Mathematics, 2020, том 20, страницы 753–781 DOI: https://doi.org/10.1007/s10208-019-09431-1(Mi fcm1)
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
[Tropical Combinatorial Nullstellensatz and sparse polynomials]
Аннотация:
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 a fundamental 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 four basic questions on tropical
polynomials closely related to their computational properties:
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?
A more precise question, given a polynomial with a certain support and a (finite)
set of inputs, how many roots can this polynomial have on this set of inputs?
Given an integer k, for which s there is a set of s inputs such that any nonzero
polynomial with at most k monomials has a non-root among these inputs?
How many integer roots can have a one variable polynomial given by a tropical
algebraic circuit?
In the classical algebra well-known results in the direction of these questions are
Combinatorial Nullstellensatz due to N. Alon, J. Schwartz–R. Zippel Lemma and
Universal Testing Set for sparse polynomials, respectively. The classical analog of the
last question is known as τ-conjecture due to M. Shub–S. Smale. In this paper, we
provide results on these four questions for tropical polynomials.
The results of Sects. 4 and 6 were obtained by the first author at MCCME and supported by the Russian Science Foundation (Project 16-11-10075). The results of Sects. 3 and 5 were obtained by the second author and were supported by
grant MK-5379.2018.1, by the Russian Academic Excellence Project ‘5-100’ and by RFBR Grant 17-51-10005-KO_a.
Поступила в редакцию: 25.01.2018 Исправленный вариант: 10.01.2019 Принята в печать: 05.06.2019
Обратная связь: