A sparse effective Nullstellensatz

Abstract: We present bounds for the sparseness and for the degrees of the polynomials in the Nullstellensatz. Our bounds depend mainly on the unmixed volume of the input polynomial system. The degree bounds can substantially improve the known ones when this polynomial system is sparse, and they are, in the worst case, simply exponential in terms of the number of variables and the maximum degree of the input polynomials.

Review text

Let \(k\) be a field, \(\overline k\) its algebraic closure, \(\mathbb{A}^n\) the affine \(n\)-space over \(\overline k\). Let \(f_1,\dots, f_s\in k[X_1, \dots, X_n,X_1^{-1}, \dots,X_n^{-1}]\) be Laurent polynomials. The support of the set \(f_1, \dots, f_s\) is the set of exponents of all non-zero monomials of all the \(f_i\). The Newton polytope \(N(f_1, \dots, f_s)\) is the convex hull of the support and the unmixed volume \(U(f_1, \dots, f_s)\) is \(\rho\)! times the volume of \(N(f_1,\dots,f_s)\), where \(\rho\) is the dimension of the polytope. The main result of the paper shows that if \(f_1, \dots, f_s\in k[X_1, \dots, X_n]\) without common zeroes in \(\mathbb{A}^n\), there are \(g_1, \dots, g_s\in k[X_1, \dots, X_n]\) such that \(\sum^s_{i=1} g_if_i=1\) and \(N(g_if_i) \subseteq (n^{n+3} U)N\), \(i=1, \dots,s\). An analogous result is obtained for the case of Laurent polynomials. Several applications are given.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: A sparse effective Nullstellensatz

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