Tropical combinatorial Nullstellensatz and sparse polynomials

DOI10.1007/S10208-019-09431-1MaRDI QIDQ2194772zbMATH OpenOpenAlexWikidataFDO

Authors Vladimir V. Podolskii, Dima Grigoriev

Publication date 7 September 2020

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.00080

zbMATH Keywords

combinatorial Nullstellensatztropical circuitstropical polynomial

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Foundations of tropical geometry and relations with algebra (14T10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Symbolic computation and algebraic computation (68W30)

Abstract: 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: 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. 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? 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? 4. 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 $au$-conjecture due to M. Shub - S. Smale. In this paper we provide results on these four questions for tropical polynomials.

Recommendations

• Tropical combinatorial Nullstellensatz and fewnomials testing
• Tropical effective primary and dual Nullstellensätze
• Tropical effective primary and dual Nullstellensätze
• TROPICAL ALGEBRAIC SETS, IDEALS AND AN ALGEBRAIC NULLSTELLENSATZ
• A tropical nullstellensatz

Cites work

• A \(\tau \)-conjecture for Newton polygons
• A Polyhedral Method for Solving Sparse Polynomial Systems
• A tropical nullstellensatz
• A Wronskian approach to the real \(\tau\)-conjecture
• Algorithms in real algebraic geometry
• An algebra for piecewise-linear minimax problems
• Bounds on the number of connected components for tropical prevarieties
• Combinatorial Nullstellensatz
• Combinatorics and genus of tropical intersections and Ehrhart theory
• Complexity of solving tropical linear systems
• Complexity of tropical and MIN-plus linear prevarieties
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 2149438 (Why is no real title available?)
• scientific article; zbMATH DE number 1827070 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• scientific article; zbMATH DE number 5019906 (Why is no real title available?)
• scientific article; zbMATH DE number 2221693 (Why is no real title available?)
• Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems
• Linear independence over tropical semirings and beyond
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Matching is as easy as matrix inversion
• Mathematical problems for the next century
• Max-min representation of piecewise linear functions
• On a partition into convex polygons
• On the frontiers of polynomial computations in tropical geometry
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Partitioning point sets in space into disjoint convex polytopes
• Randomness efficient identity testing of multivariate polynomials
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Research Problems in Discrete Geometry
• Sets in \(\mathbb{R}^ d\) with no large empty convex subsets
• Testing polynomials
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
• The Tropical Rank of a Tropical Matrix
• Tropical algebraic geometry
• Tropical combinatorial Nullstellensatz and fewnomials testing
• Tropical effective primary and dual Nullstellensätze
• Tropical Nevanlinna Theory and Ultradiscrete Equations
• Tropical polyhedra are equivalent to mean payoff games

Cited in

(7)

• Tropical combinatorial Nullstellensatz and fewnomials testing
• Tropicalization, symmetric polynomials, and complexity
• Tropical Newton-Puiseux polynomials. II
• On a tropical dual Nullstellensatz
• Notes on Boolean read-k and multilinear circuits
• The Nullstellensatz and Positivstellensatz for sparse tropical polynomial systems
• Universal dynamical system for brain modeling

This page was built for publication: Tropical combinatorial Nullstellensatz and sparse polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2194772)