A Sparse Effective Nullstellensatz ^{1}

Martín Sombra ^{2}

Departamento de Matemática, Universidad Nacional de La Plata, Calle 50 y 115, 1900 La Plata, Argentina.

E-mail:  sombra@mate.unlp.edu.ar

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.

Keywords. Cohen–Macaulay ring, Effective Nullstellensatz, Newton polytope, Degree of a polynomial system of equations.

AMS Subject Classification. 13P10.

Introduction

We consider the problem of bounding the sparseness of the polynomials in the Nullstellensatz in the case when the input is a sparse polynomial system.

Let us denote by k a field and by \overline{k} its algebraic closure. As usual we denote by IA^{n} the affine space of n dimensions over \overline{k}. Let be given polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] without common zeros in IA^{n}. Classical Hilbert’s Nullstellensatz states then that there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] satisfying the Bézout equation

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s}. (1)

Let d denote the maximum degree of the polynomials f_{1}, …, f_{s} and assume that n ≥ 2. In the previous situation we have indeed that there exist polynomials g_{1}, …, g_{s} verifying the degree bound

deg g_{i}f_{i} ≤ max{3, d}^{n}.

This result is due to Kollár, and it is optimal provided that d ≥ 3 [19]. In the case when d = 2 and the characteristic of k is different from two, Sabia and Solernó proved that the sharper bound deg g_{i}f_{i} ≤ n 2^{n+2} holds true [27]. In fact more precise estimations are valid, we refer to the original papers for the exact statements.

1Date of this version: 6.8.97

2Partially supported by CONICET PID 3949/92, UBA CyT EX. 001 and Fundación Antorchas.

We note that such a degree bound allows us, given polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}], to determine whether the equation (1) is solvable or not, and in the case it is, to actually find a solution, as it reduces the original problem to the solving of a k–linear system of equations.

The study of this Bézout identity is the object of much research, due to both its theoretical and practical importance, mainly in the context of computational algebraic geometry and diophantine approximation. Thus it has been approached from many points of view and with different objectives. In this respect we refer to the research papers [2], [4], [5], [7], [11], [13], [15], [20], [24], [27], [28], [29]. We also refer to the surveys [3], [23], [34] for a broad introduction to the history of this problem, main results and open questions.

Let be given a Laurent polynomial f = ∑_{i∈ZZ^{n}} a_{i} x^{i} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}]. The support of f is defined as the set {i : a_{i} ≠ 0}, that is, the set of exponents of the nonzero monomials of f. More generally, the support of a family of Laurent polynomials f_{1}, …, f_{s} is defined as the set of exponents of the nonzero monomials of any of the f_{i} for i = 1, …, s.

The Newton polytope N (f_{1}, …, f_{s}) is defined as the convex hull of the support of f_{1}, …, f_{s}. Let ρ denote the dimension of this polytope. Then the unmixed volume U(f_{1}, …, f_{s}) of the family of Laurent polynomials f_{1}, …, f_{s} is defined as ρ! times the volume of the polytope N (f_{1}, …, f_{s}).

The degree of a polynomial is bounded by a nonnegative integer d if and only if its Newton polytope is contained in d times the standard simplex of IR^{n}. Thus the notion of Newton polytope gives a sharper characterization of the monomial structure of a polynomial system than just degree. This concept is in the basis of sparse elimination theory. Within this theory, algorithms for elimination problems are designed trying to exploit the sparseness of the involved polynomials, and sparseness is then usually measured in terms of the Newton polytope of these polynomials. This is the point of view introduced by Sturmfels in his foundational work [31] and followed, for instance, in [8], [18], [25], [26], [35].

The sparse aspect in the Nullstellensatz has also been considered by Canny and Emiris, who obtained a sparse effective Nullstellensatz but only for the case of n + 1 generic n–variate Laurent polynomials [8, Theorem 7.2].

We obtain the following result, which in this context can be seen as a bound for the sparseness of the output polynomials in terms of the sparseness of the input system.

Theorem 1. Let be given polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] without common zeros in IA^{n}. Let N denote the Newton polytope of the polynomials x_{1}, …, x_{n}, f_{1}, …, f_{s}, and let U denote the unmixed volume of this polytope. Then there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] satisfying

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s},

with N (g_{i}f_{i}) ⊆ n^{n+3} U N for i = 1, …, s.

Let us keep the notations of Theorem 1 and let d denote the maximum degree of f_{i} for i = 1, …, s. We readily derive from the previous result the degree bound

deg g_{i}f_{i} ≤ n^{n+3} d U.

We obtain from this the worst–case bound deg g_{i}f_{i} ≤ n^{n+2} d^{n+1}, as the unmixed volume of the polynomials x_{1}, …, x_{n}, f_{1}, …, f_{n} is bounded by d^{n}. We show however that our degree bound can considerably improve the usual one in the case when the input polynomial system is sparse and d ≥ n (Example 2.14).

We note that the naive notion of sparseness, based just on the counting of the number of nonzero monomials in each polynomial, does not yield better bounds for the degrees than the usual ones, in view of the well known example of Mora, Lazard, Masser and Philippon [5].

We obtain an analogous result for the case of Laurent polynomials.

Theorem 2. Let be given Laurent polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] without common zeros in (\overline{k}^{∗})^{n}. Let N denote the Newton polytope of f_{1}, …, f_{s}, and let U denote the unmixed volume of this polytope. Then there exist a ∈ ZZ^{n} and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] satisfying

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s},

with a ∈ n^{2n+3} U^{2} N and N (g_{i}f_{i}) ⊆ n^{2n+3} U^{2} N − a for i = 1, …, s.

The proof of both results is similar. It takes as its first step the translation of the original system of equations over the affine space or the torus into a system of linear equations over an appropriate toric variety. The resulting system is then solved by appealing to an effective Nullstellensatz for linear forms in a Cohen–Macaulay graded ring. This key lemma is proved following for the most part the lines of a previous paper [30] which in turn is based on previous work of Dubé [9] and Almeida [1], although we introduce at this time some simplifications into the arguments. In particular we eliminate the use of estimations for the Hilbert function.

As a by–product, we obtain an effective Nullstellensatz which holds not only for linear forms, but for arbitrary homogeneous elements in a Cohen–Macaulay graded ring (Theorem 1.9).

Besides we apply these arguments in two other situations. First we consider the usual effective Nullstellensatz and we obtain the following degree bound.

Theorem 3. Let be given polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] without common zeros in IA^{n}. Let d_{i} denote the degree of f_{i} for i = 1, …, s and assume that d_{1} ≥ ⋯ ≥ d_{s} holds. Then there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] satisfying

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s},

with deg g_{i}f_{i} ≤ 2 d_{s} ∏_{j=1}^{min{n,s}−1} d_{j} for i = 1, …, s.

In the case when the polynomials f_{1}, …, f_{s} are quadratic this estimation improves the bound deg g_{i}f_{i} ≤ n 2^{n+2} to the bound deg g_{i}f_{i} ≤ 2^{n+1}, which is very close to the expected 2^{n}.

Finally we obtain another bound for the degrees in the Nullstellensatz. This bound depends on the number of variables and the maximum degree of the input polynomials and also on an additional parameter, called the algebraic degree of the input polynomial system, which we are going to introduce.

Let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Let λ = (λ_{ij})_{ij} ∈ \overline{k}^{s×s} be an arbitrary s × s matrix with entries in \overline{k}. We note by h_{i}(λ) the linear combinations ∑_{j} λ_{ij} f_{j} induced by the matrix λ for i = 1, …, s.

Consider the set Γ of s × s matrices such that for any λ in Γ the polynomials h_{1}(λ), …, h_{t−1}(λ) form a regular sequence in \overline{k}[x_{1}, …, x_{n}] and 1 ∈ (h_{1}(λ), …, h_{t}(λ)) for some t = t(λ) ≤ min{n, s}. This set is nonempty, and indeed it contains a nonempty open set of \overline{k}^{s×s}.

For each λ ∈ Γ and i = 1, …, t − 1 we denote by J_{i}(λ) ⊆ k[x_{0}, …, x_{n}] the homogenization of the ideal (h_{1}(λ), …, h_{i}(λ)). Then let δ(λ) denote the maximum degree of the homogeneous ideal J_{i}(λ) for i = 1, …, t − 1.

The algebraic degree of the polynomial system f_{1}, …, f_{s} is defined as

δ(f_{1}, …, f_{s}) := min {δ(λ) : λ ∈ Γ}.

This is the algebraic analogue of the notion of geometric degree of a system of equations of Giusti et al. [14], Krick, Sabia and Solernó [21] and Sombra [30]. We refer to Section 3 for a comparison between both notions.

There have been obtained degree bounds for the polynomials in the Nullstellensatz which mainly depend on the geometric degree [13], [21], [30]. We show that a similar bound holds by replacing the geometric degree of the input polynomial system by the algebraic degree.

Theorem 4. Let be given polynomials f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] without common zeros in IA^{n}. Let d denote the maximum degree of f_{i} for i = 1, …, s and let δ denote the algebraic degree of this polynomial system. Then there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] satisfying

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s},

with deg g_{i}f_{i} ≤ min{n, s}^{2} d δ for i = 1, …, s.

Let us denote by d_{i} the degree of f_{i} for i = 1, …, s and assume that d_{1} ≥ ⋯ ≥ d_{s} holds. Then the Bézout bound δ(f_{1}, …, f_{s}) ≤ d_{s} ∏_{i=1}^{min{n,s}−2} d_{i} holds true, and therefore we essentially recover from the previous result the known bounds for the degrees in the Nullstellensatz. The algebraic degree is bounded by the geometric degree, and so we also recover the known degree bounds in the Nullstellensatz which depend on the geometric degree. We show however that the algebraic degree is much smaller than the geometric degree in some particular instances, and by force, than the Bézout bound d^{n−1} (Example 3.22). We conclude that the obtained degree bound is much sharper in these cases than the known ones.

The outline of the paper is as follows. In Section 1 we obtain the effective Nullstellensatz for homogenous elements in a Cohen–Macaulay graded ring. In Section 2 we prove both Theorems 1 and 2 and we derive some of their consequences. In Section 3 we devote to the degree bounds in the usual Nullstellensatz.

0. Notations and Conventions

We denote by k an infinite field with an algebraic closure denoted by \overline{k}. All the rings to be considered in the sequel are Noetherian commutative, and more precisely finitely generated k–algebras. The polynomial ring k[x_{0}, …, x_{n}] is alternatively denoted by S.

As usual IP^{n} and IA^{n} denote the projective and the affine spaces of n dimensions over \overline{k}, respectively. A variety is not necessarily irreducible.

Let J be a homogeneous ideal in the ring S/I. The dimension of J is defined as the Krull dimension of the quotient ring (S/I)/J and it is denoted by dim J. The degree of J is defined as (dim J − 1)! times the principal coefficient of the Hilbert polynomial of the graded k–algebra (S/I)/J.

Let φ : A → B be a morphism between two rings, and let I and J be ideals of A and B respectively. Then I^{e} denotes the extension of the ideal I to B and J^{c} denotes the contraction of the ideal J to A. Given an element α ∈ A, we denote by \overline{α} the element φ(α) ∈ B. We shall make use of this notation when it is clear from the context the morphism to which we refer.

1. An Effective Nullstellensatz over Cohen–Macaulay Graded Rings

Let be given a Cohen–Macaulay homogeneous ideal I in the ring k[x_{0}, …, x_{n}]. By this we mean that the quotient ring k[x_{0}, …, x_{n}]/I is a Cohen–Macaulay ring. Let r denote the dimension of I. We also suppose that there is given a homogeneous element p in S/I which is not a zero–divisor. Let η_{1}, …, η_{s} ∈ S/I be homogeneous elements of degree one —or for short, linear forms— which define the empty variety in the open set {p ≠ 0} of V (I). In this situation, Hilbert’s Nullstellensatz implies that p belongs to the radical of the ideal (η_{1}, …, η_{s}), that is, p ∈ \sqrt{(η_{1}, …, η_{s})}. Equivalently we have that 1 lies in the ideal (\overline{η}_{1}, …, \overline{η}_{s}) spanned by \overline{η}_{1}, …, \overline{η}_{s} in the ring (S/I)_{p}.

We are going to give a bound for the minimal D ∈ IN such that p^{D} falls into the ideal (η_{1}, …, η_{s}) (Main Lemma 1.7). This bound depends on the number of linear forms, and on the dimension and the degree of the ideal I. As a consequence of this result we derive an effective Nullstellensatz for Cohen–Macaulay graded rings (Theorem 1.9 and Corollary 1.10).

Let A be a ring and let α_{1}, …, α_{t} be elements of A. Then α_{1}, …, α_{t} is called a weak regular sequence if \overline{α}_{i} is not a zero–divisor in the ring A/(α_{1}, …, α_{i−1}) for i = 1, …, t. We note that this definition differs from usual notion of regular sequence only in one point, namely that it allows \overline{α}_{t} to be a unit in A/(α_{1}, …, α_{t−1}).

Lemma 1.1 Let notations be as before. Then there exist linear forms ζ_{1}, …, ζ_{t} ∈ (η_{1}, …, η_{s}) for some t ≤ min\{r, s\} such that \overline{ζ}_{1}, …, \overline{ζ}_{t} is a weak regular sequence in (S/I)_{p} and 1 ∈ (\overline{ζ}_{1}, …, \overline{ζ}_{t})

Proof. Let z_{i} := ∑_{j=1}^{s} λ_{ij} \overline{η}_{j} be a generic k–linear combination of \overline{η}_{1}, …, \overline{η}_{s} for i = 1, …, s. We obtain a maximal secant sequence z_{1}, …, z_{t} for some t ≤ s, as the field k is infinite. By this we mean that dim(z_{1}, …, z_{i}) = r −i−1 for i = 1, …, t−1 and that 1 ∈ (z_{1}, …, z_{t}). In particular t ≤ min{r, s} holds true.

The ring (S/I)_{p} is Cohen–Macaulay as it is a localization of a Cohen–Macaulay ring. Then z_{1}, …, z_{t} is a regular sequence in (S/I)_{p}.

We take ζ_{i} := ∑_{j=1}^{s} λ_{ij} η_{j} for i = 1, …, t. Thus ζ_{i} ∈ (η_{1}, …, η_{s}) and \overline{ζ}_{i} = z_{i} for i = 1, …, s as required. □

Thus we can suppose without loss of generality that \overline{η}_{1}, …, \overline{η}_{s} is a weak regular sequence in (S/I)_{p} and that s ≤ r holds. We assume this from now on. Next we are going to show that η_{1}, …, η_{s} can be replaced by polynomials of controlled degree which form a regular sequence in S/I (Corollary 1.3).

The following lemma is a generalization of [17, Remark 4].

Lemma 1.2 Let be given a homogeneous unmixed ideal K ⊆ k[x_{0}, …, x_{n}] and points ξ_{1}, …, ξ_{m} ∈ IP^{n} not lying in V (K). Then there exists a homogeneous polynomial g in K such that deg g ≤ deg K and that g(ξ_{i}) ≠ 0 hold.

Proof. The case when K is a homogeneous prime ideal follows easily from [17, Remark 4].

Let us consider the general case. For each associated prime ideal P of K we take a homogeneous polynomial g_{P} such that deg g_{P} ≤ deg P and g_{P} (ξ_{i}) ≠ 0 for i = 1, …, m. Let Q_{P} be the corresponding P –primary ideal in the decomposition of K. Let l(Q_{P}) denote the length of Q_{P}, that is, the length of (S/Q_{P})_{P} as a S/P –module. Then let

g := ∏_{P} g_{P}^{l(Q_{P})},

where the product is taken over all the associated prime ideals of K. Then g(ξ_{i}) ≠ 0 for i = 1, …, m, and we have also that the polynomial g lies in the ideal K by [6, Lemma 1] and the degree bound deg g ≤ ∑_{P} l(Q_{P}) deg P = deg K holds true by [36, Proposition 1.49]. It follows that g satisfies the stated conditions. □

In the sequel we shall denote by J_{i} the contraction to the ring S/I of the ideal (\overline{η}_{1}, …, \overline{η}_{i}) ⊆ (S/I)_{p} and by δ_{i} the degree of the homogeneous ideal J_{i} for i = 1, …, s.

Corollary 1.3 Let notations be as before. Then there exist homogeneous elements h_{1}, …, h_{s} ∈ S/I satisfying the following conditions: i) h_{i} ≡ p^{c_{i}}η_{i} mod J_{i−1} for some c_{i} ≥ 0,

ii) h_{1}, …, h_{s} is a regular sequence,

iii) deg h_{i} ≤ deg J_{i−1} + deg p − 1,

for i = 1, …, s.

Proof. We proceed by induction on i. By assumption p is not a zero–divisor in S/I so that the canonical morphism S/I → (S/I)_{p} is injective. The fact that \overline{η}_{1} is not a zero–divisor in (S/I)_{p} implies then that η_{1} is not a zero–divisor in S/I.

Now let i ≥ 2 and assume that the elements h_{1}, …, h_{i−1} are already constructed. Let H_{i−1} denote the ideal spanned by h_{1}, …, h_{i−1} in S/I. Let H_{i−1} = (∩_{j} Q_{j}) ∩ (∩_{l} R_{l}) be the primary decomposition of H_{i−1}, with p ∉ \sqrt{Q_{j}} and p ∈ \sqrt{R_{l}}. Our objective is to find a homogeneous element h_{i} in S/I not lying in any of the associated primary ideals of H_{i−1}.

We recall that the ideal H_{i−1} has no imbedded component as it is spanned by a regular sequence in a Cohen–Macaulay ring. On the other hand the ideal J_{i−1} has the primary decomposition ∩_{j} Q_{j} and so it follows that V (R_{l}) ⊆ / V (J_{i−1}) holds for each l. We choose a point ξ_{l} lying in V (R_{l}) − V (J_{i−1}) and a homogeneous element g ∈ J_{i−1} such that deg g ≤ deg J_{i−1} and g(ξ_{l}) ≠ 0 for each l. The existence of g is guaranteed by the previous lemma. By eventually multiplying g with linear forms we can suppose without loss of generality that deg g = c_{i} deg p + 1 holds for some c_{i} ≥ 0. In particular we can assume that deg g ≤ deg J_{i−1} +deg p−1 holds. Finally we set

h_{i} := ag + p^{c_{i}}η_{i}

for some indeterminate scalar a ∈ k. Then h_{i} is homogeneous and h_{i} ≡ p^{c_{i}}η_{i} mod J_{i−1} holds true. Therefore h_{i} does not belong to \sqrt{Q_{j}}, as both p and η_{i} are not zero–divisors modulo J_{i−1}. We have also that h_{i}(ξ_{l}) = a g(ξ_{l}) + (p^{c_{i}}η_{i})(ξ_{l}) ≠ 0 for a generic choice of a, which forces h_{i} ∉ \sqrt{R_{l}}. □

We fix the following notation. Let h_{1}, …, h_{s} ∈ S/I be the homogeneous polynomials introduced in Corollary 1.3, and let H_{i} := (h_{1}, …, h_{i}) and L_{i} := (η_{1}, …, η_{i}) denote the homogeneous ideals successively generated by h_{1}, …, h_{s} and η_{1}, …, η_{s} respectively.

Let us write h_{i} = l_{i}+p^{c_{i}} η_{i} for some l_{i} ∈ J_{i−1} and c_{i} ≥ 0. Then set γ_{i} := δ_{i−1}−δ_{i} , and let λ_{i} := ∑_{j=1}^{i}(γ_{j} +c_{j}) and μ_{i} := ∑_{j=1}^{i}((i−j +1)γ_{j} +(i−j)c_{j}) for i = 1, …, s.

Given an ideal K in S/I we denote by K^{u} the unmixed part of K, that is, the unmixed ideal given as the intersection of the primary components of K of maximal dimension.

Lemma 1.4 Let be given an element q ∈ J_{i} for some 1 ≤ i ≤ s. Then p^{γ_{i}}q ∈ (J_{i−1}, η_{i})^{u}.

Proof. Let (∩_{j} Q_{j}) ∩ (∩_{l} R_{l}) be the primary decomposition of the ideal (J_{i−1}, η_{i})^{u}, with p ∉ \sqrt{Q_{j}} and p ∈ \sqrt{R_{l}}. Then the ideal J_{i} has the primary decomposition ∩_{j} Q_{j}. Let K_{i} := ∩_{l} R_{l} be the intersection of the other primary components. Then K_{i} is an unmixed ideal which lies in the hypersurface {p = 0}.

The ideals (J_{i−1}, η_{i})^{u} and (J_{i−1}, η_{i}) have the same degree because they only differ in an ideal of codimension at least i + 1. The degree of (J_{i−1}, η_{i}) is δ_{i−1}, as η_{i} is not a zero–divisor mod J_{i−1}, and so the degree of K_{i} equals γ_{i} = δ_{i−1} −δ_{i}. Therefore p^{γ_{i}} lies in the ideal K_{i} [6, Lemma 1] and we conclude that p^{γ_{i}}q ∈ (∩_{j} Q_{j}) ∩ (∩_{l} R_{l}) = (J_{i−1}, η_{i})^{u} as stated. □

The following two statements (Lemmas 1.5 and 1.6) are plain extensions of [9, Lemmas 6.1 and 6.2].

Lemma 1.5 Let be given an element q ∈ J_{i} for some 1 ≤ i ≤ s. Then p^{λ_{i}}q ∈ H_{i}.

Proof. We proceed by induction on i. First p^{γ_{1}}q ∈ (η_{1})^{u} by Lemma 1.4. We have also that (η_{1})^{u} = (η_{1}) and so the assertion is true for i = 1.

Let i ≥ 2 and assume that the statement holds for i − 1. By Lemma 1.4, p^{γ_{i}}q ∈ (J_{i−1}, η_{i})^{u}, that is, p^{γ_{i}} q belongs to the intersection of the primary components of dimension r − i of the ideal (J_{i−1}, η_{i}). The intersection of the other primary components is an ideal of codimension at least i + 1. Then there exists a regular sequence w_{1}, …, w_{i+1} in this ideal, as S/I is a Cohen–Macaulay ring. We have that w_{j} p^{γ_{i}} q ∈ (J_{i−1}, η_{i}) and so there exist u_{j} ∈ J_{i−1} and v_{j} ∈ S/I such that w_{j} p^{γ_{i}} q = u_{j} + v_{j}η_{i} for j = 1, …, i + 1. Then

w_{j} p^{γ_{i}+c_{i}} q = p^{c_{i}} u_{j} + p^{c_{i}} v_{j} η_{i} = p^{c_{i}}u_{j} + v_{j}(h_{i} − l_{i}) = (p^{c_{i}}u_{j} − v_{j}l_{i}) + v_{j}h_{i}.

Therefore p^{γ_{i}+c_{i}}u_{j} − v_{j}l_{i} ∈ J_{i−1} and by the inductive hypothesis p^{λ_{i−1}}(p^{γ_{i}+c_{i}}u_{j} − v_{j}l_{i}) lies in the ideal H_{i−1}. Then w_{j} p^{λ_{i}} q ∈ H_{i} holds for j = 1, …, i + 1, as λ_{i} = λ_{i−1} + γ_{i} − c_{i}.

The ideal H_{i} is spanned by a regular sequence h_{1}, …, h_{i} and so it is an unmixed ideal of dimension r − i. Thus for each associated prime ideal P of H_{i} there exists some j such that w_{j} ∉ P. We conclude that p^{λ_{i}}q ∈ H_{i}. □

Lemma 1.6 Let be given an element q ∈ J_{i} for some 1 ≤ i ≤ s. Then p^{μ_{i}}q ∈ L_{i}.

Proof. We shall proceed by induction on i. The case i = 1 follows in the same way as in the preceding lemma because L_{1} = H_{1} and μ_{1} = λ_{1}.

Let i ≥ 2. Then p^{λ_{i}}q lies in H_{i} by Lemma 1.5. Let us write p^{λ_{i}}q = u + v h_{i} for some u ∈ H_{i−1} and v ∈ S/I. Therefore p^{λ_{i}}q − v h_{i} ∈ H_{i−1} and thus p^{λ_{i}}q − p^{c_{i}} v η_{i} lies in the ideal J_{i−1} because H_{i−1} ⊆ J_{i−1} and h_{i} ≡ p^{c_{i}} η_{i} mod J_{i−1}. This implies in turn that p^{λ_{i}−c_{i}}q − v η_{i} ∈ J_{i−1}.

¿From the inductive hypothesis we get that p^{μ_{i−1}}(p^{λ_{i}−c_{i}} q −v η_{i} lies in L_{i−1} and so p^{μ_{i−1}+λ_{i}−c_{i}}q ∈ L_{i}. The statement follows from the observation that μ_{i} = μ_{i−1}+λ_{i}−c_{i}. □ Main Lemma 1.7 Let I ⊆ k[x_{0}, …, x_{n}] be a homogeneous Cohen–Macaulay ideal of dimension r. Let be given in addition a homogeneous element p ∈ k[x_{0}, …, x_{n}]/I which is not a zero–divisor and linear forms η_{1}, …, η_{s} ∈ k[x_{0}, …, x_{n}]/I such that p lies in the radical of the ideal (η_{1}, …, η_{s}). Then

p^{D} ∈ (η_{1}, …, η_{s})

holds, with D := min{r, s}^{2} deg I.

Proof. By Lemma 1.1 we can suppose without loss of generality that \overline{η}_{1}…. , \overline{η}_{s} is a weak regular sequence in (S/I)_{p} and that s ≤ r. After Lemma 1.6 it only remains to bound μ_{s}. We make use of the estimations γ_{i}, c_{i} ≤ δ_{i−1} and we get the bound

\begin{aligned}μ_{s} & = & ∑_{j=1}^{s}((s − j + 1)γ_{j} + (s − j)c_{j}) \\ & ≤ & ∑_{j=1}^{s}((s − j + 1)δ_{j−1} + (s − j)δ_{j−1}) ≤ s^{2} deg I. \end{aligned}

□

Compare with Caniglia, Galligo and Heintz [7, Proposition 10], Smietanski [29, Lemma 1.44], and Sturmfels, Trung and Vogel [33, Theorems 2.1 and 5.3]

The rest of the section is devoted to the extension of the previous result to the case when we are given homogeneous elements of arbitrary degree instead of linear forms. First we establish some generalities about the Veronese imbedding.

Let us denote by N the integer (_{d}^{n+d})−1 and let a_{0}, …, a_{N} denote the exponents of the different monomials of degree d in S. Let

v_{d} : IP^{n} → IP^{N}, x := (x_{0} : ⋯: x_{n}) ↦ (x^{a_{0}} : ⋯: x^{a_{N}})

be the Veronese map. This is a regular morphism of projective varieties and so its image is a closed subvariety of IP^{N}. This variety is called the Veronese variety and it is denoted by v_{n,d}. Let I(v_{n,d}) be its defining ideal and let us denote by S(d) := k[y_{0}, …, y_{N}]/I(v_{n,d}) its homogeneous coordinate ring. The Veronese map induces then an inclusion of k–algebras i_{d} : S(d) ↪ S defined by y_{j} ↦ x^{a_{j}} for j = 0, …, N.

Let be given an ideal J in S and let J(d) denote its contraction to the ring S(d). Identifying the quotient ring S(d)/J(d) with its image in S/J through the inclusion i_{d} : S(d)/J(d) ↪ S/J we obtain the decomposition in graded parts

S(d)/J(d) = ⊕_{j} (S/J)_{d j}.

Let h_{J(d)} and h_{J} denote the Hilbert functions of J(d) and J respectively. Then h_{J(d)}(m) = h_{J}(d m) for m ∈ IN. It follows that the ideals J(d) and J have the same dimension and that their degrees are related by the formula deg J(d) = d ^{dim J−1} deg J.

Lemma 1.8 Let J be a homogeneous Cohen–Macaulay ideal in S and let J(d) denote its contraction to the ring S(d). Then J(d) is a Cohen–Macaulay ideal.

Proof. Let us denote by A and B the quotient rings S(d)/J(d) and S/J respectively. We identify A with its image in B through the inclusion i_{d}.

We are going to prove that A is a Cohen–Macaulay ring. As A is a graded ring it suffices to exhibit a regular sequence of homogeneous elements of length equal to the dimension of A.

Let e denote the dimension of the ring B, which is also the dimension of A. Let β_{1}, …, β_{e} be a regular sequence in B of homogeneous elements. Let α_{i} := β_{i}^{d} for i = 1, …, e. Then α_{1}, …, α_{e} are elements of A which form a regular sequence in B, by [22, Theorem. 16.1]. We affirm that they also form a maximal regular sequence in A. We only have to prove that α_{i} is not a zero–divisor in A/(α_{1}, …, α_{i−1}) for i = 1, …, e. Let ζ ∈ A be an element such that ζ α_{i} ∈ (α_{1}, …, α_{i−1}). Then there exist homogeneous elements ζ_{1}, …, ζ_{i−1} ∈ B such that ζ = ζ_{1}α_{1} + ⋯ + ζ_{i−1}α_{i−1} because α_{1}, …, α_{i−1} is a regular sequence in B. An easy verification shows that ζ_{1}, …, ζ_{i−1} can be chosen to lie in A, from where it follows that ζ ∈ (α_{1}, …, α_{i−1}). □

Theorem 1.9 Let I ⊆ k[x_{0}, …, x_{n}] be a homogeneous Cohen–Macaulay ideal. Let be given in addition an homogeneous element p ∈ k[x_{1}, …, x_{n}]/I which is not a zero–divisor and homogeneous elements f_{1}, …, f_{s} ∈ k[x_{0}, …, x_{n}]/I such that p lies in the radical of the ideal (f_{1}, …, f_{s}). Let r denote the dimension of I and let d the maximum degree of f_{i} for i = 1, …, s. Then

p^{D} ∈ (f_{1}, …, f_{s})

holds, with D := r^{2} d^{r} deg I.

Proof. First we note that the zero locus in V (I) of the polynomials {f_{i}}_{i} equals the zero locus in V (I) of the polynomials {x_{j}^{d−deg f_{i}}f_{i}}_{ij}. We have also that x_{j}^{d−deg f_{i}}f_{i} lies in the ideal (f_{1}, …, f_{s}) for all i and j. Therefore we can suppose without loss of generality that f_{i} is a homogeneous polynomial of degree d for i = 1, …, s. We note however that the number of input polynomials have been enlarged in this preparative step.

Let i_{d} : S(d) ↪ S be the inclusion of k–algebras induced by the Veronese map and let I(d) denote the contraction of the ideal I to the ring S(d). Then we have the inclusion i_{d} : S(d)/I(d) ↪ S/I and the decomposition in graded parts i_{d}(S(d)/I(d)) = ⊕_{j}(S/I)_{dj}. We take a linear form η_{i} ∈ S(d)/I(d) such that i_{d}(η_{i}) = f_{i} for i = 1, …, s, which exists as the inclusion i_{d} is a bijection in degree one. We take also a homogeneous element q ∈ S(d)/I(d) such that i_{d}(q) = p^{d}.

The map v_{d} : V (I) → V (I(d)) is a dominant regular map of projective varieties and so it is surjective. Therefore the zero locus of the linear forms η_{1}, …, η_{s} lies in the image of the zero locus of the polynomials f_{1}, …, f_{s}. The common zeros of f_{1}, …, f_{s} lie in the hypersurface {p^{d} = 0} of V (I) and we have in addition that v_{d}({p^{d} = 0}) = {q = 0}. Then the subvariety of V (I(d)) defined by η_{1}, …, η_{s} lies in the hypersurface {q = 0}.

By Lemma 1.8 the ideal I(d) is Cohen–Macaulay, and we have also that q is not a zero–divisor modulo I(d). Then we are in the hypothesis of the Main Lemma 1.7.

As a consequence we obtain that

q^{r^{2} deg I(d)} ∈ (η_{1}, …, η_{s})

holds. Finally we apply the morphism i_{d} to the previous expression and we get that

p^{d r^{2} (d^{r−1} deg I)} ∈ (f_{1}, …, f_{s})

holds, as deg I(d) = d^{r−1} deg I. □

Corollary 1.10 Let be given an ideal I ⊆ k[x_{1}, …, x_{n}]. Assume furthermore that the homogenization I^{h} of the ideal I in the ring k[x_{0}, …, x_{n}] is a Cohen-Macaulay ideal. Let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in the affine variety V (I). Then there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] such that

1 ≡ g_{1}f_{1} + ⋯ + g_{s}f_{s} (mod I)

holds, with deg g_{i}f_{i} ≤ (r + 1)^{2} d^{r+1} deg I^{h} for i = 1, …, s.

Proof. By assumption the ideal I^{h} is a Cohen–Macaulay homogeneous ideal of dimension r + 1. We have also that x_{0} is not a zero–divisor modulo I^{h}.

Let f_{i}^{h} denote the homogenization of f_{i} for i = 1, …, s. The homogeneous polynomials f_{1}^{h}, …, f̃_{s}^{h} have no common zero in V (Ĩ) outside the hyperplane {x_{0} = 0}. By Theorem 1.9 there exist homogeneous polynomials v_{1}, …, v_{s} ∈ S such that

x_{0}^{(r+1)^{2} d^{r+1}} = v_{1}f_{1}^{h} + … + v_{s}f_{s}^{h} (mod I^{h})

holds, with deg v_{i}f_{i}^{h} = (r + 1)^{2} d^{r+1} . The corollary then follows by evaluating x_{0} := 1. □

Let notations be as in Corollary 1.10. In the case when I is the zero ideal, that is, in the setting of the classic effective Nullstellensatz, we get the degree bound

deg g_{i}f_{i} ≤ (r + 1)^{2} d^{r+1}.

2. The Sparse Effective Nullstellensatz

In this section we shall devote to the sparse effective Nullstellensätze (Theorems 1 and 2) and to the derivation of some of their consequences.

First we introduce notation and state some basic facts from polyhedral geometry and toric varieties. We refer to the books [12] and [32] for the proofs of these facts and for a more general background on these topics.

Let us be given a finite set of integer vectors A ⊆ ZZ^{n}. The convex hull of A as a subset of IR^{n} is denoted by conv(A). The cone over conv(A) is denoted by pos(A).

The set A is graded if there exists an integer vector ω ∈ ZZ^{n} such that < a, ω >= 1 holds for every a ∈ A, that is, when the set A lies in an affine hyperplane which does not contain the origin.

Let ZZA denote the ZZ–module generated by A. Let IRA denote the linear space spanned by A, so that ZZA is a lattice in IRA. Let ρ denote the dimension of this linear space. Then we consider the euclidian volume form in IRA, normalized in such a way that the lattice ZZA has covolume ρ! or equivalently, such that each primitive lattice simplex has unit volume. The normalized volume Vol(A) of the set A is defined as the volume of its convex hull with respect to this volume form.

We get readily from the definition the bound

Vol(A) ≤ ρ! vol (conv(A)),

where vol (conv(A)) denotes the volume of the convex hull of A with respect to the usual non–normalized volume form of IR^{n}.

Let INA denote the semigroup spanned by A. This semigroup is always contained in the semigroup pos(A) ∩ ZZA. The set A is said to be normal or saturated if the equality INA = pos(A) ∩ ZZA holds.

A polytope P is said to be integral if it is the convex hull of a finite set of integer vectors.

Let S be an integral simplex. Then S is said to be unimodular if its interior contains no integral vector. Let {s_{1}, …, s_{k}} be the set of vertices of S. Then we have that S is unimodular if and only if the set of integer vectors {s_{2}−s_{1}, …, s_{k}−s_{1}} is normal.

Let P be an integral polytope. A subdivision of P is said to be unimodular if it is formed by unimodular integral simplices.

Given integral polytope P in IR^{n}, we denote by A(P) the set {1} × (P ∩ ZZ^{n}), which is a graded set of integral vectors in ZZ^{n+1}. We note that the set A(P) is normal in the case when P admits a unimodular subdivision.

With respect to toric geometry, we shall follow the lines of [32]. This point of view differs from the usual one in algebraic geometry. It is more combinatorial and suits better for our purposes.

Let us be given again a finite set of integer vectors A = {a_{1}, …, a_{N}} in ZZ^{n}. We associate to the set A the morphism

φ_{A} : k[y_{1}, …, y_{N}] → k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}], y_{i} → x^{a_{i}}.

The kernel of this map is a prime ideal I_{A} of k[y_{1}, …, y_{N}], called the toric ideal associated to the set A. This ideal defines an affine toric variety X_{A} as its zero locus in IA^{N}. This variety is irreducible and its dimension equals the rank of the ZZ–module ZZA.

The k–algebra k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] is the coordinate ring of the torus (\overline{k}^{∗})^{n}. Thus the map φ_{A} induces a dominant map (\overline{k}^{∗})^{n} → X_{A}. The image of this map is called the torus T_{A} of the affine toric variety X_{A}. This torus equals the open set {y_{1} ⋯ y_{N} ≠ 0} of X_{A}.

The ideal I_{A} is homogeneous if and only if the set A is graded. In this case the set A defines a projective toric variety Y_{A} as the zero locus of the ideal I_{A} in the projective space IP^{N−1}. The dimension of Y_{A} equals then the rank of ZZA minus one, and its degree equals the normalized volume of the set A.

Let A = {a_{1}, …, a_{N}} ⊆ ZZ^{n} be a graded set. The intersection of the projective variety Y_{A} with the affine chart {y_{i} ≠ 0} ≅ IA^{N−1} equals the affine toric variety associated to the set

A − a_{i} := {a_{1} − a_{i}, …, a_{i−1} − a_{i}, a_{i+1} − a_{i}, …, a_{N} − a_{i}}.

In fact Y_{A} is irredundantly covered by the affine varieties X_{A−a_{i}}, where a_{i} runs over the vertices of the polytope conv(A).

The k–algebra k[y_{1}, …, y_{N}]/I_{A} is canonically isomorphic to the semigroup algebra k[INA]. This algebra is normal if and only if the set A is normal. We recall Hochster’s theorem that the k–algebra k[INA] is a Cohen–Macaulay domain in the case when the set A is normal.

Let be given an integral polytope P in IR^{n}. This polytope determines a fan Δ_{P} and an abstract complete toric variety X_{P} = X(Δ_{P}). This variety comes equipped with an ample Cartier divisor D_{P}. This Cartier divisor defines then a map φ_{P} : X_{P} → IP^{N−1}, where N denotes the cardinality of the set {P ∩ ZZ^{n}}. The image of this map is the projective variety Y_{A(P)}, where the set A(P) is defined as before as {1} × (P ∩ ZZ^{n}) [12, Section 3.4]. The divisor (n − 1)D_{P} is very ample [10], and so the graded set A((n − 1) P) is normal.

Theorem 2.11 Let be given polynomials p, f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] such that p lies in the radical of the ideal (f_{1}, …, f_{s}). Let P be an integral polytope which contains the Newton polytope of the polynomials 1, x_{1}, …, x_{n}, f_{1}, …, f_{s}. Assume furthermore that A(P) is a normal set of integer vectors in ZZ^{n+1}. Then there exist D ∈ IN and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] such that

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with D ≤ n! min{n + 1, s}^{2} vol (P) and N (g_{i}f_{i}) ⊆ (1 + deg p) n! min{n + 1, s}^{2} vol (P) P for i = 1, …, s.

Proof. Let B = {b_{0}, …, b_{N}} denote the set of integer vectors P ∩ZZ^{n}, so that A(P) = {1} × B. Assume that b_{0} = (0, …, 0). We consider the morphism of k–algebras

ψ : k[y_{1}, …, y_{N}] → k[x_{1}, …, x_{n}], y_{i} ↦ x^{b_{i}}.

The kernel of this morphism is the defining ideal I_{B−b_{0}} of the affine toric variety X_{B−b_{0}}. This affine variety is the intersection of the projective toric variety Y_{A(P)} with the affine cart {y_{0} ≠ 0} of IP^{N}. In addition the map ψ induces an isomorphism IA^{n} → X_{B−b_{0}}.

Let ζ_{i} be a polynomial of degree one in k[y_{1}, …, y_{N}] such that ψ(ζ_{i}) = f_{i} for i = 1, …, s. We take also a polynomial q in k[y_{1}, …, y_{N}] of degree less or equal to the degree of p such that ψ(q) = p. Then ζ_{1}, …, ζ_{s} have no common zero in X_{B−b_{0}} outside the hypersurface {q = 0}.

Let η_{1}, …, η_{s}, u denote the homogenization of ζ_{1}, …, ζ_{s}, q in k[y_{0}, …, y_{N}] respectively. Then the linear forms η_{1}, …, η_{s} have no common zero in Y_{A(P)} outside the hypersurface {y_{0} u = 0}.

By assumption the set A(P) is normal, and so I_{A(P)} is a Cohen–Macaulay prime homogeneous ideal of k[y_{0}, …, y_{N}] of dimension less or equal that n + 1. We have also that y_{0} u is not a zero–divisor modulo I_{A(P)}. Then we are in the hypothesis of the Main Lemma 1.7. Let D denote the integer min{n + 1, s}^{2} deg Y_{A(P)}. We obtain that there exist homogeneous elements α_{1}, …, α_{s} ∈ k[y_{0}, …, y_{N}]/I_{A(P)} of degree (1 + deg u) D − 1 satisfying

(y_{0} u)^{D} = α_{1}η_{1} + ⋯ + α_{s}η_{s}.

Finally we evaluate y_{0} := 1 and we apply the map ψ to the preceding identity. We get

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s},

where we have set g_{i}(x) := α_{i}(1, x^{b_{1}}, …, x^{b_{N}}) for i = 1, …, s. We have the estimations deg u ≤ deg p and deg Y_{A(P)} ≤ n! vol (P). We conclude that D ≤ n! min{n + 1, s} vol (P) and that the polytope N (f_{i}g_{i}) is contained in ((1 + deg p) n! min{n + 1, s}^{2} vol (P)) P for i = 1, …, s. □

We derive from the previous theorem the following degree bound.

Corollary 2.12 Let notations be as in Theorem 2.11. Let d denote the maximum degree of the polynomials f_{i} for i = 1, …, s. Then there exist D ∈ IN and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] such that

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with D ≤ n! min{n+1, s}^{2} vol (P) and deg g_{i}f_{i} ≤ d (1+deg p) n! min{n+ 1, s, }^{2} vol (P) for i = 1, …, s.

□

We are going to show with an example that this degree bound can be much more precise than the usual one in the case when the input system is sparse. First we need the following auxiliary result.

Lemma 2.13 Let P_{d} denote the integral polytope {x = (x_{1}, …, x_{n}) ∈ IR^{n} : x_{1}, …, x_{n} ≥ 0, x_{1} + ⋯ + x_{n−1} ≤ 1, x_{n} ≤ d} for some d ∈ IN. Then P_{d} admits a unimodular subdivision.

Proof. Let us denote by e_{1}, …, e_{n−1} the standard unit vectors of IR^{n−1}. Let S denote the simplex of IR^{n−1} with vertices (0, …, 0), e_{1}, …, e_{n−1}, so that P_{d} = S × [0, d]. We have the subdivision P_{d} = ∪_{i=0}^{d−1}(P_{1} + i e) , where e ∈ IR^{n} denotes the vector (0, …, 0, 1). Thus it suffices to show that P_{1} admits a unimodular subdivision.

Let α_{i}, β_{i} ∈ IR^{n} denote the vectors e_{i} × {0}, e_{i} × {1} respectively, for i = 1, …, n − 1, and (0, …, 0, 0), (0, …, 0, 1) for i = n. Let S_{i} be the integral simplex determined by the vectors α_{1}, …, α_{i}, β_{i}, …, β_{n} for i = 1, …, n.

It is easily checked that the simplices S_{i} and S_{j} intersect in a proper face for i ≠ j, so that S_{1}, …, S_{n} are essentially disjoint. We have also that vol (S) = 1/(n − 1)! and that vol (S_{i}) = 1/n! for i = 1, …, n, and so S_{1}, …, S_{n} form a unimodular subdivision of P_{1} as desired. □

Example 2.14 Let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Assume in addition that deg_{x_{1},...,x_{n−1}} f_{i} ≤ 1 and that deg_{x_{n}} f_{i} ≤ d holds for i = 1, …, s. Let P_{d} denote as before the polytope {x ∈ IR^{n} : x_{1}, …, x_{n} ≥ 0, x_{1} + ⋯ + x_{n−1} ≤ 1, x_{n} ≤ d}. Then P_{d} contains the Newton polytope of the polynomials 1, x_{1}, …, x_{n}, f_{1}, …, f_{s} and the set A(P) is normal by the preceding lemma. Thus we are in the hypothesis of Corollary 2.12 and we can conclude that there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] such that

1 = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with N (g_{i}f_{i}) ⊆ d n min{n + 1, s}^{2} P_{d} for i = 1, …, s, as the volume of P_{d} equals d/(n−1)!. In particular we get the degree bound deg g_{i}f_{i} ≤ (n+1)^{3} (d+1)^{2}, which is much sharper than the estimation deg g_{i}f_{i} ≤ (d + 1)^{n} which follows from direct application of the usual degree bound.

Let notations be again as in Theorem 2.11. Let N denote the Newton polytope of the polynomials 1, x_{1}, …, x_{n}, f_{1}, …, f_{s} and let U denote the unmixed volume of this polytope. Assume that n ≥ 2. In this situation we can then take the polytope P to be (n − 1) N. Then we get the bounds

D ≤ n^{n+2} U, N (g_{i}f_{i}) ⊆ ((1 + deg p) n^{n+3} U) N .

It is easy to check that these bounds hold also when n = 1. Thus Theorem 1 follows from this observation in the particular case p = 1. We observe that in this case the condition 0 ∈ P is redundant.

We obtain a similar result in the case of Laurent polynomials.

Theorem 2.15 Let be given Laurent polynomials p, f_{1}, …, f_{s} ∈ k[x_{1}^{−1}, …, x_{n}^{−1}, x_{1}, …, x_{n}] such that p lies in the radical of the ideal (f_{1}, …, f_{s}). Let P be an integral polytope which contains the Newton polytope of p, f_{1}, …, f_{s}. Let ρ denote its dimension. Assume furthermore that A(P) is a normal set of integer vectors in ZZ^{n+1}. Then there exist D ∈ IN, a ∈ ZZ^{n} and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] such that

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with D ≤ ρ! min{n + 1, s}^{2} vol (P) , a ∈ (ρ! min{n + 1, s} vol (P))^{2}P and N (g_{i}f_{i}) ⊆ (ρ! min{n + 1, s} vol (P))^{2} P − a for i = 1, …, s.

Proof. As before, we denote by B = {b_{0}, …, b_{N}} the set of integer vectors P ∩ ZZ^{n}. Assume for the moment that b_{0} = (0, …, 0). We consider the morphism

ψ : k[y_{1}, …, y_{N}] → k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}], y_{i} ↦ x^{b_{i}}.

The kernel of this morphism is the defining ideal I_{B−b_{0}} of the affine toric variety X_{B−b_{0}}. Let T denote the torus of this toric variety. Then we have that X_{B−b_{0}} equals the intersection of the projective variety Y_{A(P)} with the affine cart {y_{0} ≠ 0} of IP^{N}, and that T is also the torus of Y_{A(P)}. We recall that this torus equals the open set {y_{0} ⋯ y_{N} = 0} of Y_{A(P)}.

The map ψ induces a surjection (\overline{k}^{∗})^{n} → T. Let ζ_{1}, …, ζ_{s}, q be elements of degree one in k[y_{1}, …, y_{N}] such that ψ(ζ_{i}) = f_{i} for i = 1, …, s and ψ(q) = p. Then ζ_{1}, …, ζ_{s} have no common zero in T outside the hyperplane {q = 0}.

Let η_{1}, …, η_{s}, u denote the homogenization of ζ_{1}, …, ζ_{s}, q in k[y_{0}, …, y_{N}] respectively. Then the linear forms η_{1}, …, η_{s} have no common zero in Y_{A(P)} outside the hypersurface {y_{0} ⋯ y_{N} u = 0}.

Let V (η_{1}, …, η_{s}) denote the subvariety of Y_{A(P)} defined by the linear forms η_{1}, …, η_{s}. By Bézout inequality, the number of irreducible components of V (η_{1}, …, η_{s}) does not exceed the degree of Y_{A(P)}. Let us denote by δ the degree of Y_{A(P)}, so that δ ≤ ρ! vol (P) holds. In our situation this implies that V (η_{1}, …, η_{s}) lies in the union of at most δ hyperplanes. These hyperplanes are defined by variables y_{i_{1}}, …, y_{i_{l}}, and eventually also by the linear form u, depending on whether η_{1}, …, η_{s} have a common zero in T in the hyperplane {u = 0} or not. Let Π denote the product of these equations, which is a polynomial of degree less or equal that δ.

By assumption the set A(P) is normal and so I_{A(P)} is a Cohen–Macaulay prime homogeneous ideal of k[y_{0}, …, y_{N}] . We have also that Π is not a zero–divisor modulo this ideal. Thus we are again in the hypothesis of the Main Lemma 1.7. Let E denote the integer min{n + 1, s}^{2} deg Y_{A(P)}. Then there exist homogeneous elements α_{1}, …, α_{s} ∈ k[y_{0}, …, y_{N}]/I_{A(P)} of degree deg Π E − 1 such that

Π^{E} = α_{1}η_{1} + ⋯ + α_{s}η_{s}

holds. We evaluate y_{0} := 1 and we apply the map ψ to the preceding identity. We get

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s},

where we have set g_{i}(x) := (x^{b_{i_{1}}} ⋯ x^{b_{i_{l}}})^{−1} α_{i}(1, x^{b_{1}}, …, x^{b_{N}}) for i = 1, …, s and D := E in the case when u appears as a factor of Π and D := 1 in the other case. Then D ≤ ρ! min{n + 1, s}^{2} vol (P) holds and the polytope N (g_{i}f_{i}) is contained in (ρ! vol (P) E − 1) P − (b_{i_{1}} + ⋯ + b_{i_{l}}) for i = 1, …, s. We have that deg Π ≤ deg Y_{A(P)} ≤ ρ! vol (P) and that i_{1} + … + i_{k} ∈ deg Y_{A(P)} P.

Now we consider the general case. Let b_{0} be any integer vector in P, and let Q denote the polytope P − b_{0}. By the previous considerations there exist D ∈ IN, a_{0} ∈ ZZ^{n} and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] such that

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with D ≤ ρ! min{n + 1, s}^{2} vol (Q) , a_{0} ∈ ρ! vol (Q) Q and N (g_{i}f_{i}) ⊆ (ρ! min{n + 1, s} vol (Q))^{2} Q − a_{0} for i = 1, …, s.

Let a be the integer vector a_{0} + (ρ! min{n + 1, s} vol (P))^{2} b_{0}. Then a lies in the polytope (ρ! min{n + 1, s} vol (P))^{2} P and we have also that N (g_{i}f_{i}) ⊆ (ρ! min{n + 1, s} vol (P))^{2} P − a holds for i = 1, …, s as stated. □

Let notations be as in Theorem 2.15. Let N denote the Newton polytope of p, f_{1}, …, f_{s} and let U denote the unmixed volume of this polytope. Assume in addition that n ≥ 2. In this situation we can then take the polytope P to be (n − 1) N. We get the bounds

D ≤ n^{n+2} U, N (g_{i}f_{i}) ⊆ (n^{2n+3} U) N − a.

for some a ∈ (n^{2n+3} U) N. As before, it is easy to verify that the same bounds hold also when n = 1. Thus Theorem 2 follows from this observation in the particular case h = 1.

Let be given a rational function q ∈ k(x_{1}, …, x_{n}) and let q = f/g be a representation of q as the quotient of two polynomials without common factors. Then the degree of q is defined as deg q := max{deg f, deg g}.

We derive from Theorem 2.15 the following degree bound.

Corollary 2.16 Let notations be as in Theorem 2.15. Let d denote the maximum degree of the Laurent polynomials f_{i} for i = 1, …, s. Then there exist D ∈ IN and g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}] such that

p^{D} = g_{1}f_{1} + ⋯ + g_{s}f_{s}

holds, with D ≤ ρ! min{n + 1, s}^{2} vol (P) , a ∈ (ρ! min{n + 1, s} vol (P))^{2}P and deg(g_{i}f_{i}) ≤ d ((1 + deg p)ρ! min{n + 1, s} vol (P))^{2} for i = 1, …, s.

□

3. Improved Bounds for the Degrees in the Nullstellensatz

In this section we consider the degree bounds in the Nullstellensatz. We shall apply the methods used in Section 1 in a direct way —without any reference to the Veronese map— in the setting of the classic effective Nullstellensatz. The proof follows closely the same lines and so we shall skip some verifications in order to avoid unnecessary repetitions.

Assume that we are given homogeneous polynomials f_{1}, …, f_{s} in k[x_{0}, …, x_{n}] without common zeros at finite distance. In this situation we are going to give a bound for the minimal D ∈ IN such that x_{0}^{D} ∈ (f_{1}, …, f_{s}).

We shall assume without loss of generality that s ≤ n + 1 and that \overline{f}_{1}, …, \overline{f}_{s} is a weak regular sequence in k[x_{0}, …, x_{n}]_{x_{0}}. Let d_{i} denote the degree of f_{i} for i = 1, …, s. We shall also suppose that d_{2} ≥ ⋯ ≥ d_{s} and that d_{s} ≥ d_{1} hold. As before these polynomials can be obtained as linear combinations of the original polynomials, eventually multiplied by powers of x_{0}.

Let us denote by J_{i} the contraction to the ring S of the ideal (\overline{f}_{1}, …, \overline{f}_{i}) ⊆ S_{x_{0}} for i = 1, …, s. We make the convention J_{0} := (0).

Lemma 3.17 Let notations be as before. Then there exist homogeneous polynomials h_{1}, …, h_{s} ∈ k[x_{0}, …, x_{n}] satisfying the following conditions:

i) h_{i} ≡ x_{0}^{c_{i}}f_{i} mod J_{i−1} for some c_{i} ∈ IN,

ii) h_{1}, …, h_{s} is a regular sequence,

iii) deg h_{i} ≤ max {deg J_{i−1}, deg f_{i}},

for i = 1, …, s.

□

We introduce the following notation. Let δ_{i} denote the degree of the homogeneous ideal J_{i} for i = 0, …, s. We recall the Bézout bound δ_{i} ≤ ∏_{j=1}^{i} d_{j}. Then we denote by γ_{i} the integer d_{i} δ_{i−1} − δ_{i} for i = 1, …, min{n, s} and γ_{n+1} := δ_{n} + d_{n+1} − 1. We also let δ := max{δ_{i} : i = 1, …, s − 1} and d := max{d_{i} : i = 1, …, s − 1}.

We recall that given an ideal I in S we denote by I^{u} its unmixed part.

Lemma 3.18 Let be given a polynomial q ∈ J_{i} for some 1 ≤ i ≤ s. Then x_{0}^{γ_{i}} q ∈ (J_{i−1}, η_{i})^{u}.

Proof. The case i ≤ n is exactly as in Lemma 1.4. Thus we only consider the case i = n + 1.

The ideal J_{n} is has dimension one and its degree is δ_{n}. Then (J_{n}, f_{n+1})_{m} = S_{m} for m ≥ δ_{n} + d_{n+1} − 1 as f_{n+1} is not a zero–divisor modulo J_{n} [30, Theorem. 2.23]. It follows that x_{0}^{γ_{n+1}} ∈ (J_{n}, f_{n+1}) and in particular x_{0}^{γ_{n+1}} q ∈ (J_{n}, f_{n+1})^{u}. □

Now let h_{1}, …, h_{s} be the homogeneous polynomials introduced in Lemma 3.17. We set μ_{i} := ∑_{j=2}^{i}((i − j + 1) γ_{j} + (i − j) c_{j}) for i = 1, …, min{n, s} and μ_{n+1} := μ_{n} + γ_{n+1}, where c_{i} denotes the integer deg h_{i} − deg f_{i}.

We denote by L_{i} the homogeneous ideal (f_{1}, …, f_{i}) for i = 1, …, s.

Lemma 3.19 Let be given a polynomial q ∈ J_{i} for some 1 ≤ i ≤ s. Then x_{0}^{μ_{i}}q ∈ L_{i}.

Proof. The case i ≤ n is exactly as in Lemma 1.6. Thus we only consider the case i = n + 1.

By the previous lemma x_{0}^{γ_{n+1}} q ∈ (J_{n}, f_{n+1})^{u} = (J_{n}, f_{n+1}) and so x_{0}^{γ_{n+1}} q−u f_{n+1} ∈ J_{n} for some polynomial u ∈ S. We apply then the inductive hypothesis and we obtain that x_{0}^{μ_{n}} (x_{0}^{γ_{n+1}} q − u f_{n+1}) ∈ L_{n} from where it follows that x_{0}^{μ_{n+1}} q ∈ L_{n+1}. □

Thus it only remains to bound μ_{s}. We shall be concerned with two different types of bounds. One depends as usual on the number of variables and on the degrees of the input polynomials, and the other depends also on the degree of some ideals associated to these polynomials.

Lemma 3.20 Let notations be as before. Then μ_{s} ≤ min{n, s}^{2} d δ. In the case when deg f_{i} ≥ 2 for i = 1, …, s we have that μ_{s} ≤ 2 ∏_{j=1}^{min{n,s}} d_{j}.

Proof. We decompose the integer μ_{s} in two terms and we estimate them separately. First we consider the term ∑_{j=2}^{s} (s − j) c_{j}. We have that c_{i} ≤ max{δ_{i−1} − d_{i}, 0}. In particular c_{2} = 0 as δ_{1} = d_{1} and d_{1} ≤ d_{2}. Then

∑_{j=2}^{s} (s − j) c_{j} ≤ ∑_{j=3}^{s−1} (s − j) (d_{1} ⋯ d_{j−1} − d_{j})
≤ (∑_{j=3}^{s−1}(s − j)/d_{j} ⋯ d_{s−2}) d_{1} ⋯ d_{s−2} − ∑_{j=2}^{s−1} (s − j) d_{j}
≤ 4 d_{1} ⋯ d_{s−2} − d_{s−1},

under the assumption d_{i} ≥ 2 for i = 1, …, s. We have also ∑_{j=2}^{s−1} (s − j) c_{j} ≤ ∑_{j=2}^{s−1} (s − j) δ = \frac{1}{2} (s − 2)(s − 1) δ.

Now we estimate the other term. We consider first the case s ≤ n. Then

∑_{j=2}^{s} (s − j + 1) γ_{j} = ∑_{j=2}^{s} (s − j + 1) (d_{j} δ_{j−1} − δ_{j})
= (s − 1) d_{2} δ_{1} + ∑_{j=3}^{s} ((s − j + 1) d_{j} − (s − j)) δ_{j−1} − δ_{n}
≤ d_{1} ⋯ d_{s} − δ_{s},

from where we obtain the bound μ_{s} = ∑_{j=2}^{s} (s − j + 1) γ_{j} + ∑_{j=2}^{s−1} (s − j) c_{j} ≤ (d_{1} ⋯ d_{s} − δ_{s}) + (4 d_{1} ⋯ d_{s−2} − d_{s−1}) ≤ 2 d_{1} ⋯ d_{s}.

In the case s = n + 1 we have that μ_{n+1} = μ_{n} + γ_{n+1} from where it follows that μ_{n+1} ≤ (2 d_{1} ⋯ d_{n} − δ_{n} − d_{n−1}) + (δ_{n} + d_{n+1} − 1) ≤ 2 d_{1} ⋯ d_{n}.

On the other hand we have also the estimation ∑_{j=2}^{s} (s−j +1) γ_{j} ≤ \frac{1}{2} (s−1) s d δ from where we conclude that μ_{s} ≤ \frac{1}{2} (s − 1) s d δ + \frac{1}{2} (s − 2) (s − 1) δ ≤ (s − 1)^{2} d δ holds, as stated. □

Theorem 3.21 Let be given homogeneous polynomials f_{1}, …, f_{s} ∈ k[x_{0}, …, x_{n}] such that x_{0} lies in the radical of the ideal (f_{1}, …, f_{s}). Let d_{i} denote the degree of f_{i} for i = 1, …, s and assume that d_{1} ≥ ⋯ ≥ d_{s} holds. Then

x_{0}^{D} ∈ (f_{1}, …, f_{s})

holds, with D := 2 d_{s} ∏_{i=1}^{min{n,s}−1} d_{i}.

Proof. After Lemmas 3.19 and 3.20 it only remains to consider the case when some f_{i} has degree one.

By assumption f_{1}, …, f_{s} are ordered in such a way that d_{1} ≥ ⋯ ≥ d_{s} holds. Let r be maximum such that d_{r} ≥ 2, so that the polynomials f_{r+1}, …, f_{s} have all degree one. We can assume without loss of generality that they are k–linearly independent. We can also suppose that neither 1 nor x_{0} lie in the k–linear space spanned by f_{r+1}, …, f_{s} as if this is the case the statement is trivial.

Let y_{0}, …, y_{n+r−s−1} ∈ S be polynomials of degree one which complete f_{r+1}, …, f_{s} to a linear change of variables. We suppose in addition that y_{0} = x_{0}. Then the natural inclusion k[y_{0}, …, y_{n+r−s−1}] ↪ k[x_{0}, …, x_{n}]/(f_{r+1}, …, f_{s}) is an isomorphism. Let v_{i} be an homogeneous polynomial in k[y_{0}, …, y_{n+r−s−1}] such that v_{i} ≡ f_{i} mod (f_{r+1}, …, f_{s}) for i = 1, …, r. Then x_{0} lies in the radical of the ideal (v_{1}, …, v_{r}) of k[y_{0}, …, y_{n+r−s−1}] and deg v_{i} ≤ d_{i} holds for i = 1, …, r.

Let E denote the integer 2 ∏_{i=1}^{r} deg v_{i} so that E ≤ D := 2 d_{s} ∏_{i=1}^{min{n,s}−1} d_{i}. Then x_{0}^{D} ∈ (v_{1}, …, v_{r}) from where it follows that x_{0}^{D} ∈ (f_{1}, …, f_{s}) as stated. □

Then Theorem 3 follows from this result by homogenizating the input polynomials and by considering the degree of the polynomials in a representation of x_{0}^{D}.

Now we are going to prove Theorem 4. First we recall the definition of algebraic degree of a polynomial system.

Let g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Given a s×s matrix λ = (λ_{ij})_{ij} with entries in \overline{k} we denote by h_{i}(λ) the linear combinations ∑_{j} λ_{ij} g_{j} induced by λ for i = 1, …, s. We consider the set of s × s matrices Γ such that for any λ in Γ the polynomials h_{1}(λ), …, h_{t−1}(λ) form a regular sequence in \overline{k}[x_{1}, …, x_{n}] and 1 ∈ (h_{1}(λ), …, h_{t}(λ)) for some t = t(λ) ≤ min\{n, s\}.

For each λ ∈ Γ and i = 1, …, t − 1 we denote by J_{i}(λ) ⊆ k[x_{0}, …, x_{n}] the homogenization of the ideal (h_{1}(λ), …, h_{i}(λ)). Then let δ(λ) denote the maximum degree of the homogeneous ideals J_{i}(λ) for i = 1, …, t − 1.

The algebraic degree of the polynomial system g_{1}, …, g_{s} is defined as the minimum of δ(λ) over all matrices λ ∈ Γ.

The notion of geometric degree of [21] and [30] is defined in an analogous way as the minimum of δ(λ) for λ ∈ Γ, with the additional hypothesis that the ideals J_{i}(λ) are radical for i = 1, …, t − 1. Another difference is that in the case when the characteristic of k is positive the polynomials h_{j}(λ) are taken as linear combinations of the polynomials {x_{j} f_{i}}_{ij}.

The notion of geometric degree of [14] is similar to that of [21], [30], the only difference is that it is not defined as a minimum but as the value of δ(λ) for a generic choice of λ.

Thus the algebraic degree is bounded by the geometric degree, whichever version of the later one we consider. The following example shows that in fact it can be much smaller. It is a variant of [21, Example].

Example 3.22 Let us consider the polynomial system

f_{1} := 1 − x_{1}x_{2}^{d}, f_{2} := x_{2} − x_{3}^{d}, …, f_{n−1} := x_{n−1} − x_{n}^{d}, f_{n} := x_{n}^{2}

for some d ≥ 3. It is easy to check that these polynomials have no common zero in IA^{n}. Let us denote by δ_{g} and by δ_{a} the geometric degree —in the sense of [21], [30]— and the algebraic degree of this polynomial system, respectively. We are going to compute both integers for this particular example.

Let λ be a l × n matrix with entries in \overline{k} for some l ≤ n, and let h_{i} := ∑_{j} λ_{ij} f_{j} be the induced linear combinations for i = 1, …, n.

We apply to this matrix the Gauss elimination method by rows, by using as pivots the columns of λ by ascending order. Invertible elementary operations by rows produces polynomials q_{1}, …, q_{l} which generate the same ideal than h_{1}, …, h_{l}. For our particular polynomial system this corresponds to the successive elimination of the variables x_{1}, …, x_{n} in the equations h_{1}, …, h_{l}. Thus in the case when l ≤ n−1 the affine variety defined by h_{1}, …, h_{l} can be parametrized by expressing the pivot variables as rational functions of the free ones. It follows that in this case the ideal (h_{1}, …, h_{l}) has dimension at least n − l.

First we consider the geometric degree of this system. The polynomials f_{1}, …, f_{n} form a weak regular sequence, 1 ∈ (f_{1}, …, f_{n}) and the ideal (f_{1}, …, f_{i}) is radical for i = 1, …, n − 1. We have that deg V (f_{1}, …, f_{i}) = d^{i} for i = 1, …, n − 1 from where it follows that δ_{g} ≤ d^{n−1}.

On the other hand, let λ be a l × n matrix with entries in \overline{k} and let h_{1}, …, h_{l} be the corresponding linear combinations. Assume that h_{1}, …, h_{l} is a weak regular sequence, 1 ∈ (h_{1}, …, h_{l}) and that (h_{1}, …, h_{i}) is a radical ideal for i = 1, …, l. In particular we get that l equals n and that (h_{1}, …, h_{n−1}) is a one dimensional radical ideal.

We apply the elimination method described above to the matrix formed by the first n − 1 rows of λ and we denote by q_{1}, …, q_{n−1} the obtained polynomials. We affirm that no columns i fails to be a pivot for i = 1, …, n − 1. Suppose that this is not the case. Then q_{1}, …, q_{n−2} are polynomials which do not depend on x_{n} and which span a one dimensional ideal in \overline{k}[x_{1}, …, x_{n−1}]. In addition q_{n−1} = x_{n}^{2} and so the ideal (q_{1}, …, q_{n−1}) ⊆ \overline{k}[x_{1}, …, x_{n}] is not radical, contradicting our assumption.

Thus there exist scalars a_{1}, …, a_{n−1} ∈ \overline{k} such that q_{i} = f_{i} + a_{i} f_{n} for i = 1, …, n − 1. We deduce that the variety V (h_{1}, …, h_{n−1}) can be parametrized by a map φ : IA^{1} → IA^{n} defined by t ↦ φ(t) = (φ_{1}(t), …, φ_{n}(t)), where φ_{i} ∈ \overline{k}(t) is a rational function of degree d^{n−i} for i = 1, …, n. We get that deg V (h_{1}, …, h_{n−1}) = d^{n−1} from where it follows the lower bound δ_{g} ≥ d^{n−1}. Combining this with the previous estimation we conclude that δ_{g} = d^{n−1}.

Now we consider the algebraic degree of the system. The polynomials f_{n}, …, f_{1} form a weak regular sequence and 1 ∈ (f_{n}, …, f_{1}). We have that (f_{n}, …, f_{n−i+1}) = (x_{n}^{2}, x_{n−1}, …, x_{n−i+1}) for i = 1, …, n from where it follows that δ_{a} ≤ 2. In addition, any nontrivial linear combination of f_{1}, …, f_{n} has degree at least two and so δ_{a} ≥ 2. We conclude that δ_{a} = 2.

We obtain the following degree bound by direct application of Lemmas 3.19 and 3.20.

Theorem 3.23 Let be given homogeneous polynomials f_{1}, …, f_{s} ∈ k[x_{0}, …, x_{n}] such that x_{0} lies in the radical of the ideal (f_{1}, …, f_{s}). Let f_{i}^{a} denote the affinization of f_{i} for i = 1, …, s. Let d denote the maximum degree of f_{i} for i = 1, …, s and let δ denote the degree of the polynomial system f_{1}^{a}, …, f_{s}^{a}. Then

x_{0}^{D} ∈ (f_{1}, …, f_{s})

holds, with D := min{n, s}^{2} d δ.

□

Then Theorem 4 follows from this result in the same way that Theorem 3 was derived from Theorem 3.21.

If we apply this degree bound to the previous example we obtain that there exist g_{1}, …, g_{n} ∈ k[x_{1}, …, x_{n}] satisfying

1 = g_{1}f_{1} + ⋯ + g_{n}f_{n},

with deg g_{i}f_{i} ≤ 2 n^{2} d for i = 1, …, s. In fact we have the identity

1 = f_{1} + x_{1} x_{2}^{d−1} f_{2} + x_{1} x_{2}^{d−1} x_{3}^{d−1} f_{3} + ⋯ + x_{1} x_{2}^{d−1} ⋯ x_{n−1}^{d−1} x_{n}^{d−2} f_{n}

Acknowledgements. This work originated in several conversations with Bernd Sturmfels. He motivated me to think about the sparse Nullstellensatz and suggested me several lines to approach it. Special thanks are due to him. I am also grateful to Alicia Dickenstein and Joos Heintz for helpful discussions and suggestions, and to Pablo Solernó for providing me a counterexample to a conjecture in an early version of this paper.

I also thank the Departments of Mathematics of the Universities of Alcalá and of Cantabria, Spain, where part of this paper was written during a stay in the spring of 1997.

References

[1] M. S. Almeida, Función de Hilbert de álgebras graduadas y Nullstellensatz afín efectivo, Tesis de Licenciatura, Univ. Buenos Aires, 1995.

[2] F. Amoroso, On a conjecture of C. Berenstein and A. Yger, in L. González–Vega and T. Recio, eds., Algorithms in algebraic geometry and applications, Proceedings MEGA’94, Birkäuser Progress in Math. 143, Bikhäuser, Basel, 1996, pp. 17–28.

[3] C. A. Berenstein, D. C. Struppa, Recent improvements in the complexity of the effective Nullstellensatz, Linear Alg. Appl. 157 (1991), pp. 203–215.

[4] C. A. Berenstein, A. Yger, Effective Bézout identities in Q[x_{1}, …, x_{n}], Acta Math. 166 (1991), pp. 69–120.

[5] W. D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. 126 (1987), pp. 577–591.

[6] W. D. Brownawell, D. W. Masser, Multiplicity estimates for analytic functions II, Duke J. Math. 47 (1980), pp. 273–295.

[7] L. Caniglia, A. Galligo, J. Heintz, Some new effectivity bounds in computational geometry, in T. Mora, ed, Proceedings AAECC–6, Lect. Notes in Comput. Sci. 357, Springer, Berlin, 1989, pp. 131–151.

[8] J. Canny, I. Emiris, A subdivision–based algorithm for the sparse resultant, Preprint, 1996.

[9] T. W. Dubé, A combinatorial proof of the effective Nullestellensatz, J. Symb. Comp. 15 (1993), pp. 277–296.

[10] G. Ewald, U. Wessels, On the ampleness of invertible sheaves in complete toric varieties, Results Math. 25 (1991), pp. 275–278.

[11] N. Fitchas, A. Galligo, Nullstellensatz effectif et conjecture de Sèrre (théorème de Quillen–Suslin) pour le Calcul Formel, Math. Nachr. 149 (1990), pp. 231–253.

[12] W. Fulton, Introduction to toric varieties, Ann. Math. Studies 131, Princeton Univ. Press, 1993.

[13] M. Giusti, K. Hägele, J. Heintz, J. L. Montaña, J. E. Morais, L. M. Pardo, Lower bounds for diophantine approximation, J. Pure Appl. Algebra 117 & 118 (1997), pp. 277–317.

[14] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, L. M. Pardo, Straight–line programs in geometric elimination theory, to appear in J. Pure Appl. Algebra.

[15] K. Hägele, J. E. Morais, L. M. Pardo, M. Sombra, On the intrinsic complexity of the arithmetic Nullstellensatz, Preprint, 1997.

[16] J. Harris, Algebraic geometry: a first course, Graduate Texts in Math. 133, Springer, Berlin, 1992.

[17] J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), pp. 239-277.

[18] B. Huber, B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), pp. 1541–1555.

[19] J. Kollár, Sharp effective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), pp. 963–975.

[20] T. Krick, L. M. Pardo, A computational method for diophantine approximation, in L. González–Vega and T. Recio, eds., Algorithms in algebraic geometry and applications, Proceedings MEGA’94, Birkäuser Progress in Math. 143, Bikhäuser, Basel, 1996, pp. 193–253.

[21] T. Krick, J. Sabia, P. Solernó, On intrinsic bounds in the Nullstellensatz, to appear in AAECC Journal.

[22] H. Matsumura, Commutative ring theory, Cambridge Univ. Press, 1986.

[23] L. M. Pardo, How upper and lower bounds meet in elimination theory, in G. Cohen, M. Giusti and T. Mora, eds., Proceedings AAECC–11, Lect. Notes. Comput. Sci. 948, pp. 33–69, Springer, Berlin, 1995.

[24] P. Philippon, Dénominateurs dans le théorème des zeros de Hilbert, Acta Arith. 58 (1990), pp. 1–25.

[25] J. M. Rojas, Toric generalized characteristic polynomials, Preprint, 1997.

[26] J. M. Rojas, Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert’s tenth problem, Preprint, 1997.

[27] J. Sabia, P. Solernó, Bounds for traces in complete intersections and degrees in the Nullstellensatz, AAECC Journal 6 (1995), pp. 353–376.

[28] B. Shiffman, Degree bounds for the division problem in polynomial ideals, Michigan Math. J. 36 (1989), pp. 163–171.

[29] F. Smietanski, Quelques bornes effectives pour le théoreme des zeros avec parametres, These, Univ. Nice–Sophia Antipolis, 1994.

[30] M. Sombra, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, J. Pure Appl. Algebra 117 & 118 (1997), pp. 565–599.

[31] B. Sturmfels, Sparse elimination theory, in D. Eisenbud and L. Robbiano, eds., Proceedings of the Cortona conference on computational algebraic geometry and commutative algebra, Symposia Matematica XXXIV, Ist. Naz. di Alta Matematica, Cambridge Univ. Press, 1993, pp. 377–396.

[32] B. Sturmfels, Gröbner bases and convex polytopes, Univ. Lect. Series 8, Amer. Math. Soc., 1996.

[33] B. Sturmfels, N. V. Trung, W. Vogel, Bounds on degrees of projective schemes, Math. Ann. 302 (1995), pp. 417–432.

[34] B. Teissier, Résultats récents d’algèbre commutative effective, Sém. Bourbaki 718, Astérisque 189–190, pp. 107–131, Soc. Math. France, 1991.

[35] J. Verschelde, P. Verlinden, R. Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), pp. 915–930.

[36] W. Vogel, Lectures on results on Bézout theorem, Tata Lect. Notes 74, Springer, Berlin, 1984.

[37] O. Zariski, P. Samuel, Commutative algebra, 2 vols., Van Nostrand, New York, 1958, 1960.