  RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  Главная страница О проекте Программное обеспечение Классификаторы Полезные ссылки Пользовательскоесоглашение Поиск публикаций Поиск ссылок RSS Текущие выпуски Архивные выпуски Что такое RSS

 Персональный вход: Логин: Пароль: Запомнить пароль Войти Забыли пароль? Регистрация

 Found. Comput. Math., статья опубликована online (Mi fcm1)

[Tropical Combinatorial Nullstellensatz and sparse polynomials]

D. Yu. Grigor'eva, V. V. Podolskiibc

a CNRS, Mathématiques, Université de Lille, 59655 Villeneuve d'Ascq, France
b National Research University Higher School of Economics, Moscow, Russia
c Steklov Mathematical Institute, 8 Gubkina St., Moscow, Russia 119991

Аннотация: 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 $\tau$-conjecture due to M. Shub–S. Smale. In this paper, we provide results on these four questions for tropical polynomials.

 Финансовая поддержка Номер гранта Российский научный фонд 16-11-10075 Министерство образования и науки Российской Федерации MK-5379.2018.1 Российский фонд фундаментальных исследований 17-51-10005-KO_a 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.

DOI: https://doi.org/10.1007/s10208-019-09431-1 Реферативные базы данных:  Тип публикации: Статья
MSC: 68R05, 68W30, 14T05
Поступила в редакцию: 25.01.2018
Исправленный вариант: 10.01.2019
Принята в печать:05.06.2019
Язык публикации: английский

Образцы ссылок на эту страницу:
• http://mi.mathnet.ru/fcm1

 ОТПРАВИТЬ:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Просмотров: Эта страница: 6 Обратная связь: math-net2020_04 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020