On Intrinsic Bounds in the Nullstellensatz

Teresa Krick^{∗} Juan Sabia^{∗}

Departamento de Matemática. Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires. -1428- Buenos Aires. ARGENTINA.

                       krick@dm.uba.ar     jsabia@dm.uba.ar

Pablo Solernó^{∗}

Departamento de Economía y Matemática. Universidad de San Andrés. Vito Dumas 284. -1644- Victoria, Buenos Aires. ARGENTINA.

                              psolerno@udesa.edu.ar
                     This paper is published in
   Applicable Algebra in Engineering Communications and Computing
                    Vol.  8, pages 125-134, 1997

April 23, 1997

Abstract. Let k be a field and f_{1}, …, f_{s} be non constant polynomials in k[X_{1}, …, X_{n}] which generate the trivial ideal. In this paper we define an invariant associated to the sequence f_{1}, …, f_{s} : the geometric degree of the system. With this notion we can show the following effective Nullstellensatz : if δ denotes the geometric degree of the trivial system f_{1}, …, f_{s} and d := max_{j} deg(f_{j}) , then there exist polynomials p_{1}, …, p_{s} ∈ k[X_{1}, …, X_{n}] such that 1 = ∑_{j} p_{j}f_{j} and deg p_{j}f_{j} ≤ 3n^{2}δd. Since the number δ is always bounded by (d + 1)^{n−1} , one deduces a classical single exponential upper bound in terms of d and n, but in some cases our new bound improves the known ones.

Keywords. complete intersection polynomial ideals, trace theory, effective Nullstellensatz, geometric degree.

1 Introduction

Let k be a field, \overline{k} its algebraic closure and let X_{1}, …, X_{n} be indeterminates over k; for any finite polynomial sequence f_{1}, …, f_{s} in k[X_{1}, …, X_{n}] such that 1 belongs to the ideal (f_{1}, …, f_{s}) we define D(f_{1}, …, f_{s}) in the following way :

D(f_{1}, …, f_{s}) := min { max{deg p_{j}f_{j} ; 1 = ∑ p_{j}f_{j}}}.

∗Partially supported by UBACYT and CONICET.

An effective Hilbert Nullstellensatz means to provide an explicit function which is an upper bound for D.

During the last years, many efforts have been made in order to improve the effective double exponential version of Hilbert Nullstellensatz due to G. Hermann [14]. The first single exponential bound for D was obtained by D. Brownawell [5] for k = C in 1986. Later, L. Caniglia, A. Galligo and J. Heintz [6] extended this result for any field and finally, J. Kollár [15] showed that D ≤ (max{d, 3})^{n}, where d is the maximum of the total degrees of the polynomials f_{1}, …, f_{s} (see also [9]). This is the best bound known up to now for d ≥ 3 (for d = 2 the more precise bound n2^{n+2} can be obtained; see [19, 21]) and, in fact, a well known example shows that it is asymptotically optimal (see Example 1 below). Related results can be found also in the research papers [20, 3, 18, 11, 10, 1, 16, 12] and in the surveys [4, 22].

In this paper we exhibit a new effective Nullstellensatz which doesn’t depend so much on the degree of the involved polynomials as the ones mentioned above, but on a more intrinsic invariant: the geometric degree of a trivial polynomial system.

First, following [13] we define the geometric (or set-theoretical) degree of an algebraic affine variety V ⊂ IA\overline{k}^{n} as the sum of the degrees of its irreducible components (where, as usual, the degree of an irreducible variety is the cardinal of its intersection with a generic linear variety of complementary dimension). If V, W ⊂ IA\overline{k}^{n} are affine varieties, Bezout Inequality states the inequality deg(V ∩ W) ≤ deg(V) deg(W) (see for instance [13, Theorem 1] for an elementary proof).

Let f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] be non constant polynomials such that 1 ∈ (f_{1}, …, f_{s}) . First let us suppose that the characteristic of k is zero; from Bertini’s Theorem and suitable arguments of genericity (cf. [11, Section 3.2], [19, Section 5.2] and [16, Section 6.1]), it is possible to show that there exist an integer t, 2 ≤ t ≤ n + 1 , and t \overline{k} -linear combinations g_{1}, …, g_{t} of the polynomials f_{j} such that :

- 1 ∈ (g_{1}, …, g_{t}) ,

- g_{1}, …, g_{t−1} is a regular sequence,

- (g_{1}, …, g_{j}) is a radical ideal, for all j = 1, …, t.

If the characteristic of k is positive, a similar result holds for \overline{k} -linear combinations of the polynomials f_{j} and X_{i}f_{j}, j = 1, …, s, i = 1, …, n (see [11, Section 3.2] or [19, Section 5.2]). In both cases denote by G the set of all sequences g_{1}, …, g_{t} for all possible t, 2 ≤ t ≤ n+1 , which verify the three conditions.

Definition 1 Under these assumptions we define the geometric degree of the trivial system f_{1}, …, f_{s} as the quantity

min_{G} { max_{1≤j≤min{t−1, n−1}}{deg V (g_{1}, …, g_{j}) }} ,

where V (g_{1}, …, g_{j}) ⊂ IA\overline{k}^{n} denotes the variety of common zeros of the polynomials g_{1}, …, g_{j}.

With this notion our main result is the following (see Theorem 7 below) :

Theorem Let f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] be polynomials which generate the trivial ideal, d := max_{j} deg f_{j} and δ be the associated geometric degree. Then D(f_{1}, …, f_{s}) ≤ 3n^{2}δd.

Let us observe that the geometric degree of a system is always bounded by its algebraiccombinatoric “Bezout number” which is given by the Hilbert function of a suitable homogeneous ideal. Moreover, from Bezout inequality, this number is bounded by d^{n−1} (in characteristic zero) or by (d + 1)^{n−1} (in any characteristic), and then, from our result a single exponential bound for D(f_{1}, …, f_{s}) can be reobtained. However, in many cases, the value of the geometric degree of the system is much smaller than its Bezout number since this geometric degree does not take into account multiplicities or degrees of certain components at infinity. In this sense, our effective Nullstellensatz can be considered more intrinsic and improves the known ones (see Example 3 of Section 4).

As an intermediate step in the proof of the Nullstellensatz, we also obtain similar bounds for the membership problem in a complete intersection case (see Lemma 5 below).

The techniques used here are exactly the same ones that in [19] which rely on elementary duality theory for Gorenstein algebras. In fact, this paper may be considered as another way (more intrinsic) of applying the trace inequalities of [19] to effective Nullstellensätze.

Similar results can be obtained by means of algorithmic tools (see [12]) or combinatoric methods (see [21]).

We thank Joos Heintz and Marc Giusti for pointing out this problem to us.

2 Preliminaries

We denote by k an arbitrary field; since our statements of effective Nullstellensätze don’t depend on algebraic extensions of k, we may suppose in the sequel that k is algebraically closed. Let X_{1}, …, X_{n} be indeterminates over k and k[X_{1}, …, X_{n}] be the polynomial ring with coefficients from k. For each polynomial f ∈ k[X_{1}, …, X_{n}] we write deg f for its total degree (by convention deg 0 := −1 ). Let 0 ≤ r < n be a non-negative integer, f_{1}, …, f_{n−r} ∈ k[X_{1}, …, X_{n}] a regular sequence, A := k[X_{1}, …, X_{r}] , B := k[X_{1}, …, X_{n}]/(f_{1}, …, f_{n−r}) and suppose that the canonical morphism A → B is an integral monomorphism (Noether position). In this case, it is well known that B is a free A -module. For any polynomial f ∈ k[X_{1}, …, X_{n}] we denote

by \overline{f} its class in B. Δ denotes the determinant of the Jacobian matrix (\frac{∂f_{j}}{∂X_{r+j}})_{1≤j≤n−r}

and we assume that \overline{Δ} is not a zero divisor in B (therefore the Jacobian criterion implies that B is reduced). The set of common zeros of the regular sequence f_{1}, …, f_{n−r} in IA_{k}^{n} is denoted by V .

The following definitions and statements of basic trace theory for Gorenstein algebras can be found in [17, Appendix F] (see also [19, Section 4.2]). This is a useful tool in Effective Algebra and several applications of duality theory in this field can be found for instance in [4, 8, 23, 10, 7, 2, 16]. Consider the ring B as an A -algebra and denote by B^{∗} its dual space Hom_{A}(B, A) . Our assumptions guarantee that B^{∗} admits a natural structure of cyclic B -module (any generator of B^{∗} is called a trace of B over A). Let μ : B ⊗_{A} B → B be the multiplication morphism μ(b⊗b′) := bb′ and denote by K its kernel. The annihilator Ann_{B⊗_{A}B}(K) is a cyclic B -module. Moreover, for each generator ∑_{m} b_{m} ⊗ b′_{m}, there exists a uniquely determinate trace σ ∈ B^{∗} such that for all b ∈ B the so-called trace formula holds:

b = ∑_{1≤m≤M} σ(b b′_{m}) b_{m}.  (1)

In particular we observe that b_{1}, …, b_{M} is a system of generators of the A -module B.

Let Y_{r+1}, …, Y_{n} be new indeterminates over k; for each polynomial f ∈ k[X_{1}, …, X_{n}] we denote by f^{(Y)} the element of the polynomial ring k[X_{1}, …, X_{r}, Y_{r+1}, …, Y_{n}] defined by f^{(Y)} := f(X_{1}, …, X_{r}, Y_{r+1}, …, Y_{n}) . Hence we have the canonical isomorphism of A -algebras :

B ⊗_{A} B ≅ A[X_{r+1}, …, X_{n}, Y_{r+1}, …, Y_{n}]/(f_{1}, …, f_{n−r}, f_{1}^{(Y)}, …, f_{n−r}^{(Y)}).  (2)

If one considers each polynomial f_{i}^{(Y)} − f_{i} as a polynomial in the variables Y_{r+1}, …, Y_{n} with coefficients in k[X_{1}, …, X_{n}] ( 1 ≤ i ≤ n − r), its Taylor expansion around the point (X_{r+1}, …, X_{n}) gives the relation :

f_{i}^{(Y)} − f_{i} = ∑_{1≤j≤n−r} a_{ij}(Y_{r+j} − X_{r+j})

where a_{ij} ∈ k[X_{1}, …, X_{n}, Y_{r+1}, …, Y_{n}] = A[X_{r+1}, …, X_{n}, Y_{r+1}, …, Y_{n}] are polynomials of total degree bounded by d − 1 . Following [17, Corollary E.19 and Example F.19] the class of det(a_{ij}) modulo the ideal (f_{1}, …, f_{n−r}, f_{1}^{(Y)}, …, f_{n−r}^{(Y)}) gives a generator of Ann_{B⊗_{A}B}(K) by means of the identification (2). Developing this determinant we obtain:

Proposition 2 There exist polynomials a_{m}, c_{m} in k[X_{1}, …, X_{n}] satisfying deg(a_{m}) + deg(c_{m}) ≤ (n − r)(d − 1) ( 1 ≤ m ≤ M ) such that ∑_{m} \overline{a}_{m} ⊗ \overline{c}_{m} is a generator of Ann_{B⊗_{A}B}(K) .

Definition 3 The trace associated to the generator of Ann_{B⊗_{A}B}(K) introduced in Proposition 2 will be called the trace associated to the regular sequence f_{1}, …, f_{n−r} and we will denote it by σ_{Δ} . In particular we have \overline{f} = ∑_{m} σ_{Δ}(\overline{f} \overline{c}_{m}) \overline{a}_{m}, for all f ∈ k[X_{1}, …, X_{n}] .

For any polynomial g ∈ k[X_{1}, …, X_{n}] such that its class \overline{g} ∈ B is not a zero divisor let X_{g} = T^{s}+α_{s−1}T^{s−1}+…+α_{0} ∈ A[T] be the characteristic polynomial of the endomorphism of B consisting in multiplication by \overline{g}. We define a new polynomial g^{∗} ∈ k[X_{1}, …, X_{n}] which depends on g in the following way:

g^{∗} := g^{s−1} + α_{s−1}g^{s−2} + … + α_{2}g + α_{1}.  (3)

Observe that gg^{∗}+α_{0} = X_{g}(g) is an element of the ideal (f_{1}, …, f_{n−r}) (Hamilton-Cayley) and α_{0} ≠ 0 since multiplication by \overline{g} is injective.

Under these hypothesis we have :

Theorem 4 ([19, Theorem 10]) Let σ_{Δ} ∈ B^{∗} be the trace associated to f_{1}, …, f_{n−r}; let g and f be polynomials in k[X_{1}, …, X_{n}] such that \overline{g} ∈ B is not a zero divisor. Then the following inequality holds :

deg σ_{Δ}(\overline{g^{∗}} \overline{f}) ≤ deg(V) (1 + max\{deg f, deg g + (n − r)d \}).

3 A division lemma for complete intersections and Nullstellensatz

Let r be an integer, 0 ≤ r ≤ n − 1 . We assume that f_{1}, …, f_{n−r} is a regular sequence contained in k[X_{1}, …, X_{n}] . Let d be an upper bound for the degrees of all polynomials f_{j}, 1 ≤ j ≤ n − r. For each j, r ≤ j ≤ n − 1 , let ℑ_{j} be the ideal generated by f_{1}, …, f_{n−j}, and set A_{j} := k[X_{1}, …, X_{j}] , B_{j} := k[X_{1}, …, X_{n}]/ℑ_{j}. Suppose that the canonical morphism A_{j} → B_{j} is an integral monomorphism and that the corresponding Jacobian Δ_{j} is not a zero divisor in B_{j}. We write K_{j} for the kernel of the application μ_{j} : B_{j} ⊗_{A_{j}} B_{j} → B_{j} introduced in Section 2 and a_{m}^{(j)}, c_{m}^{(j)} ∈ k[X_{1}, …, X_{n}] are such that ∑_{m} \overline{a}_{m}^{(j)} ⊗ \overline{c}_{m}^{(j)} is the generator of Ann_{B_{j}⊗B_{j}}(K_{j}) defined in Proposition 2. Its associated trace will be denoted by σ_{j}. Let V_{j} ⊂ IA_{k}^{n} be the algebraic variety defined by the ideal ℑ_{j} and let

ρ := max{deg(V_{j}); r + 1 ≤ j ≤ n − 1}.

Under the previous assumptions we have the following division lemma (see, for instance, [15, 4, 19, 16, 1] for similar results) :

Lemma 5 Let f be a polynomial in the ideal ℑ_{r}. Then there exist polynomials p_{1}, …, p_{n−r} in k[X_{1}, …, X_{n}] such that :

• f = ∑_{i=1}^{n−r} p_{i} f_{i}

• deg p_{i}f_{i} ≤ 2(n − r)^{2}ρd + ρ max{deg f, d} ( 1 ≤ i ≤ n − r).

Proof.- We shall construct recursively polynomials p_{n−r}, p_{n−r−1}, …, p_{1} ∈ k[X_{1}, …, X_{n}] such that for any index j, r ≤ j ≤ n − 1 , the following properties are verified :

(I) the polynomial f − p_{n−r}f_{n−r} − … − p_{n−j}f_{n−j} belongs to the ideal ℑ_{j+1} (where ℑ_{n} denotes the zero ideal)

(II) the polynomial p_{n−j} can be written in the form

p_{n−j} = ∑_{m} α_{m}^{(j+1)}a_{m}^{(j+1)}

where a_{m}^{(j+1)} are the polynomials which appear in Proposition 2 and α_{m}^{(j+1)} are polynomials in the ring A_{j+1} which degrees are uniformly bounded by a constant D_{j} defined recursively by :

D_{r} := ρ (1 + d(n − r − 1) + max{deg f, d})
D_{j+1} := D_{j} + ρ (1 + 2d(n − j − 1))  (4)

for r ≤ j ≤ n − 2 . (Let us observe that, from these bounds, we have deg p_{n−j} < D_{j} + (n − j − 1)d for all j, r ≤ j ≤ n − 1 .)

In order to show the fulfilment of statements (I) and (II) we start the recursive procedure at j = r. Since the polynomial f belongs to the ideal ℑ_{r}, there exists a polynomial h ∈ k[X_{1}, …, X_{n}] such that :

f ≡ hf_{n−r}  mod ℑ_{r+1}.  (5)

We define p_{n−r} := ∑_{m} σ_{r+1}(\overline{h} \overline{c}_{m}^{(r+1)})a_{m}^{(r+1)} .

First we observe that the trace formula (1) for the element ∑_{m} \overline{a}_{m}^{(j+1)} ⊗ \overline{c}_{m}^{(j+1)} implies that p_{n−r} − h belongs to ℑ_{r+1} . So p_{n−r} satisfies condition (I). Since the element \overline{f}_{n−r} is not a zero divisor in the ring B_{r+1} we can define, following (3), the polynomials f_{n−r}^{∗} ∈ k[X_{1}, …, X_{n}] and α ∈ A_{r+1} (α ≠ 0) in such a way that f_{n−r}^{∗}f_{n−r} − α is an element of the ideal ℑ_{r+1} . Multiplying the equality (5) by f_{n−r}^{∗} we obtain :

f_{n−r}^{∗} f ≡ α h mod ℑ_{r+1}.

Thus the polynomial identity

α p_{n−r} = ∑_{m} σ_{r+1}(\overline{f^{∗}}_{n−r} \overline{f} \overline{c}_{m}^{(r+1)}) a_{m}^{(r+1)}

holds. Since α ∈ A_{r+1} and σ_{r+1} is A_{r+1} -linear, α divides the polynomials σ_{r+1}(\overline{f^{∗}}_{n−r} \overline{f} \overline{c}_{m}^{(r+1)}) , whose degrees are uniformly bounded by ρ (1 + d(n − r − 1) + max{deg f, d}) = D_{r} (see Theorem 4). Therefore defining

α_{m}^{(r+1)} := \frac{1}{α} σ_{r+1}(\overline{f^{∗}}_{n−r} \overline{f} \overline{c}_{m}^{(r+1)})

property (II) holds.

Let now j, r ≤ j ≤ n − 2 and suppose that there exist polynomials p_{n−r}, …, p_{n−j} satisfying conditions (I) and (II). We are going to repeat mutatis mutandis the same procedure used in the case j = r in order to prove conditions (I) and (II) for j + 1 . Since the polynomial g := f − p_{n−r}f_{n−r} − … − p_{n−j}f_{n−j} belongs to the ideal ℑ_{j+1} (condition (I) for j) there exists a polynomial h ∈ k[X_{1}, …, X_{n}] such that :

g ≡ h f_{n−j−1}  mod ℑ_{j+2}.  (6)

The polynomial p_{n−j−1} is defined by :

p_{n−j−1} := ∑_{m} σ_{j+2}(\overline{h} \overline{c}_{m}^{(j+2)})a_{m}^{(j+2)}.

The trace formula (1) implies that p_{n−j−1} −h belongs to ℑ_{j+2} . So condition (I) is verified for j + 1 . Following (3) let us consider the polynomials f_{n−j−1}^{∗} ∈ k[X_{1}, …, X_{n}] and α ∈ A_{j+2} such that f_{n−j−1}^{∗}f_{n−j−1} − α ∈ ℑ_{j+2} . From (6) we obtain :

f_{n−j−1}^{∗} g ≡ α h mod ℑ_{j+2}.

Therefore

α p_{n−j−1} = ∑_{m} σ_{j+2}(\overline{f^{∗}}_{n−j−1} \overline{g} \overline{c}_{m}^{(j+2)})a_{m}^{(j+2)}

holds in the polynomial ring k[X_{1}, …, X_{n}] . Taking into account that α divides the polynomials σ_{j+2}(\overline{f^{∗}}_{n−j−1} \overline{g} \overline{c}_{m}^{(j+2)}) we define :

α_{m}^{(j+2)} := \frac{1}{α} σ_{j+2}(\overline{f^{∗}}_{n−j−1} \overline{g} \overline{c}_{m}^{(j+2)}).

In order to show that p_{n−j−1} satisfies condition (II) it suffices to prove that the degrees of the polynomials α_{m}^{(j+2)} are bounded by D_{j+1} . First we observe that deg α_{m}^{(j+2)} is bounded by deg σ_{j+2}(\overline{f^{∗}}_{n−j−1} \overline{g} \overline{c}_{m}^{(j+2)}) for each index m. From the definition of the polynomial g we have :

deg σ_{j+2}(\overline{f^{∗}}_{n−j−1} \overline{g} \overline{c}_{m}^{(j+2)}) = deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}\overline{f} \overline{c}_{m}^{(j+2)} − ∑_{l=r}^{j} \overline{f^{∗}}_{n−j−1}\overline{p}_{n−l}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)}) ≤

≤ max \{ deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}\overline{f} \overline{c}_{m}^{(j+2)}) , deg σ_{j+2}(∑_{l=r}^{j} \overline{f^{∗}}_{n−j−1}\overline{p}_{n−l}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)}) \} (7)

Theorem 4 implies :

deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}\overline{f} \overline{c}_{m}^{(j+2)}) ≤
≤ ρ(1 + max{deg f + deg c_{m}^{(j+2)} , deg f_{n−j−1} + (n − j − 2)d}) ≤
≤ ρ(1 + (n − j − 2)d + max{d, deg f}).

In order to bound the remainder part of (7), we use condition (II) to replace each polynomial p_{n−l}, r ≤ l ≤ j :

deg σ_{j+2}( ∑_{l=r}^{j} \overline{f^{∗}}_{n−j−1}(∑_{m′} α_{m′}^{(l+1)}\overline{a}_{m′}^{(l+1)})\overline{f}_{n−l}\overline{c}_{m}^{(j+2)}) ≤

≤ max_{l,m′} \{ deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}α_{m′}^{(l+1)}\overline{a}_{m′}^{(l+1)}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)})\}.

Taking into account that the polynomials α_{m′}^{(l+1)} are elements of the ring A_{l+1} and therefore are in A_{j+2} we obtain :

max_{l,m′} \{deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}α_{m′}^{(l+1)}\overline{a}_{m′}^{(l+1)}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)})\} =

= max_{l,m′} \{deg α_{m′}^{(l+1)} + deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}\overline{a}_{m′}^{(l+1)}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)})\} .

From Theorem 4 and condition (II) for l we deduce :

deg α_{m′}^{(l+1)} + deg σ_{j+2}(\overline{f^{∗}}_{n−j−1}\overline{a}_{m′}^{(l+1)}\overline{f}_{n−l}\overline{c}_{m}^{(j+2)}) ≤ D_{l} + ρ(1 + (2n − l − j − 2)d).

Summarizing the inequalities above we have that deg α_{m}^{(j+2)} is bounded by the expression :

max {ρ(1 + (n − j − 2)d + max{d, deg f}) , max_{r≤l≤j}{D_{l} + ρ(1 + (2n − l − j − 2)d)}}.

Since D_{j+1} ≥ D_{j} for all index j one infers that D_{l} ≥ ρ max{d, deg f} for all l and then

deg α_{m}^{(j+2)} ≤ max_{r≤l≤j} {D_{l} + ρ(1 + (2n − l − j − 2)d)} .

From the fact that D_{j+1} ≥ D_{j} + ρd a simple computation shows that :

max_{r≤l≤j} {D_{l} + ρ(1 + (2n − l − j − 2)d)} = D_{j} + ρ(1 + 2d(n − j − 1)) = D_{j+1} .

Then we have :

deg α_{m}^{(j+2)} ≤ D_{j+1}

and so, condition (II) is verified for j + 1 .

From the recursive definition of the integers D_{j} it is easy to prove the formula:

D_{j} = ρ( max{deg f, d} + 1 + d(n − r − 1) + (j − r)(1 + d(2n − r − j − 1))) . (8)

Summarizing, this recursive method produces polynomials p_{1}, …, p_{n−r} in k[X_{1}, …, X_{n}]

such that f = ∑_{1≤i≤n−r} p_{i} f_{i} and deg p_{i} ≤ D_{n−i} + (i − 1)d, 1 ≤ i ≤ n − r. From the

definition of D_{j} and from (8) we have

D_{n−i} + (i − 1)d ≤ D_{n−1} = ρd((n − r)^{2} − 1) + ρ(max{deg f, d} + n − r − 1). (9)

Therefore, deg p_{i}f_{i} ≤ D_{n−1} + d and, from (9), this quantity is obviously bounded by 2ρd(n − r)^{2} + ρ max{deg f, d} and the lemma follows.

Corollary 6 Let s ∈ IN, 2 ≤ s ≤ n + 1 , f_{1}, …, f_{s} be polynomials in k[X_{1}, …, X_{n}] such that f_{1}, …, f_{s−1} is a regular sequence verifying the previous assumptions for r := n−s+1 and such that 1 ∈ (f_{1}, …, f_{s}) . Let d be an upper bound for the degrees of the polynomials f_{j}, 1 ≤ j ≤ s. Then D(f_{1}, …, f_{s}) ≤ 2n^{2}ρd. In particular, if δ is the geometric degree of the system f_{1}, …, f_{s}, the inequality D(f_{1}, …, f_{s}) ≤ 2n^{2}δd holds.

Proof.- First suppose s < n + 1 . Taking into account that in the first step of the proof of Lemma 4 we didn’t use the fact that the ideal is generated by a regular sequence (in fact, we only use that f_{n−r} is not a zero divisor modulo ℑ_{r+1} ) we obtain 1 = ∑_{j} p_{j}f_{j} where deg p_{j}f_{j} ≤ 2n^{2}ρd (1 ≤ j ≤ s) . Now assume s = n + 1 . As f_{1}, …, f_{n} is a regular sequence these polynomials generate a 0–dimensional ideal ℑ_{0} and the class of f_{n+1} is a unit in the factor ring k[X_{1}, …, X_{n}]/ℑ_{0} . In other words, there exists a polynomial p_{n+1} ∈ k[X_{1}, …, X_{n}] such that 1 − p_{n+1}f_{n+1} ∈ ℑ_{0} . Formula (1) and Proposition 2 in the case A = k and B = k[X_{1}, …, X_{n}]/ℑ_{0} imply that there exists a k -system of generators of B consisting of polynomials a_{m} ∈ k[X_{1}, …, X_{n}] ( 1 ≤ m ≤ M ) with degrees bounded by n(d − 1) . Therefore, without loss of generality we can suppose that deg p_{n+1} ≤ n(d − 1) . Now, applying inequality (9) of Lemma 4 for r = 0 to the polynomial f := 1 − p_{n+1}f_{n+1} which belongs to the ideal ℑ_{0} and has degree bounded by n(d − 1) + d, we obtain polynomials p_{1}, …, p_{n} such that :

– ∑_{i=1}^{n+1} p_{i} f_{i} = 1

– deg p_{i}f_{i} ≤ ρd(n^{2} − 1) + ρ(n(d − 1) + d + n − 1) + d ≤ 2n^{2}ρd.

The stated last inequality is a direct consequence of the definition of the geometric degree of a trivial polynomial system (see Definition 1).

The general case can be deduced from this corollary by means of Bertini’s Theorem :

Theorem 7 Let f_{1}, …, f_{s} ∈ k[X_{1}, …, X_{n}] be polynomials which generate the trivial ideal, d := max_{j} deg f_{j} and δ be the associated geometric degree (cf. Definition 1). Then D(f_{1}, …, f_{s}) ≤ 3n^{2}δd.

Proof.- Without loss of generality we may suppose d > 1 . Then the proof is an immediate consequence of [11, Section 3.2.] or [19, Section 5.2.] (see also [16]) which state the following : there exists a suitable number of generic linear combinations of the polynomials f_{j} (if char(k) = 0 ) and eventually of the polynomials X_{i}f_{j} (if char(k) > 0 ), j = 1, …, s and i = 1, … n, say g_{1}, …, g_{s}, which verify the conditions :

1. 1 ∈ (g_{1}, …, g_{s}) ,

2. g_{1}, …, g_{s−1} is a regular sequence,

3. the ideal (g_{1}, …, g_{j}) is radical for all j = 1, …, s.

Therefore the result follows from Corollary 6 applied to the polynomials g_{1}, …, g_{s}, after a suitable linear change of coordinates to put the variables into Noether position and taking into account that max_{j} deg(g_{j}) ≤ d + 1 .

4 Examples

Example 1 The following example shows that in the definition of the geometric degree of a trivial polynomial system, the radical condition is unavoidable in order to obtain the stated bounds. Let us consider the classic example :

f_{1} := X_{1}^{d}, f_{2} := X_{1} − X_{2}^{d}, …, f_{n−1} := X_{n−2} − X_{n−1}^{d}, f_{n} = 1 − X_{n−1}X_{n}^{d−1}.

Clearly f_{1}, …, f_{n−1} is a regular sequence which is not reduced step-by-step, and 1 ∈ (f_{1}, …, f_{n}) . Specializing any equality 1 = p_{1}f_{1} +⋯+p_{n}f_{n} on the curve parametrized by (t^{(d−1)d^{n−2}}, …, t^{(d−1)d}, t^{d−1}, t^{−1}) one deduces that deg_{X_{n}} p_{1} ≥ (d − 1)d^{n−1} and therefore from Corollary 6 or Theorem 7 one has:

δ ≥ \frac{(d − 1)d^{n−2}}{2n^{2}} .

However in this case deg V (f_{1}, …, f_{j}) = 1 , for all 1 ≤ j ≤ n − 1 .

Example 2 In this simple example one easily sees that the maximum of the degrees of the involved polynomials must occur in the stated upper bounds :

f_{1} := X_{1}, f_{2} := X_{2} − X_{1}, …, f_{n} := X_{n} − X_{1}, f_{n+1} = 1 − X_{1}^{d}.

Here f_{1}, …, f_{n} is a step-by-step reduced regular sequence and 1 ∈ (f_{1}, …, f_{n+1}) . Specializing again any representation 1 = p_{1}f_{1} + ⋯ + p_{n+1}f_{n+1} on (t, …, t) it immediately follows that deg p_{1}f_{1} ≥ d. On the other hand δ = 1 and our bound is 2n^{2}d (Corollary 6).

Example 3 The last example shows that our upper bound improves in some cases Kollár’s :

f_{1} := X_{1}, f_{2} := X_{2} − X_{1}^{d}, …, f_{n} := X_{n} − X_{n−1}^{d}, f_{n+1} = 1 − X_{n}^{d}.

In this case Kollár’s bound is d^{n−1} while ours is 2n^{2}d since δ = 1 . Effectively we have the following representation:

1 = (X_{1}^{d−1} … X_{n}^{d−1})f_{1} + (X_{2}^{d−1} … X_{n}^{d−1})f_{2} + … + (X_{n}^{d−1})f_{n} + f_{n+1}.

References

[1] Amoroso F.: On a conjecture of C.Berenstein and A.Yger.- To appear in Proc. MEGA’94, Birkhäuser Progress in Math.

[2] Alonso M., Becker E., Roy M.-F. and Wörmann T.: Zeros, Multiplicities and Idempotents for Zerodimensional Systems.- To appear in Proc. MEGA’94, Birkhäuser Progress in Math.

[3] Berenstein C. and Struppa D.: Recent improvements in the Complexity of the Effective Nullstellensatz.- Linear Algebra and its Appl. 157 (1991) 203-215.

[4] Berenstein C. and Yger A.: Bounds for the degrees in the division problem.- Mich. Math. J. 37 (1990) 25-43.

[5] Brownawell D.: Bounds for the degrees in the Nullstellensatz.- Ann. of Math. Second Series 126 No.3 (1987) 577-591.

[6] Caniglia L., Galligo A. and Heintz J.: Some new effectivity bounds in computational geometry.- Proc. 6th Int. Conf. Applied Algebra, Algebraic Algorithms and Error Correcting Codes AAECC–6, Roma 1988, Springer Lect. Notes Comput.Sci. 357 (1989) 131-151.

[7] Cardinal J.-P.: Dualité et algorithmes itératifs pour la résolution de systèmes polynomiaux.- Thesis Université de Rennes (1993).

[8] Dickenstein A. and Sessa C.: An effective residual criterion for the membership problem in C[z_{1}, …, z_{n}] .- J.Pure and Appl.Algebra 74, North-Holland (1991) 149-158.

[9] Fitchas N. and Galligo A.: Nullstellensatz effectif et conjecture de Serre (théorème de Quillen– Suslin) pour le Calcul Formel.- Math. Nachr. 149 (1990) 231-253.

[10] Fitchas N., Giusti M. and Smietanski F.: Sur la complexité du théorème des zéros.- Approximation & Optimization 8, Verlag Peter Lang (1995) 274-329.

[11] Giusti M., Heintz J. and Sabia J.: On the efficiency of effective Nullstellensätze.- Comput. Complexity 3, Birkhaüser (1993) 56-95.

[12] Giusti M., Heintz J., Morais J., Morgenstern J. and Pardo L.: Straight-line Programs in Geometric Elimination Theory.- To appear in J. Pure and Appl. Algebra (1995).

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

[14] Hermann G.: Die Frage der endlich vielen Schritte in der Theorie der Polynomideale.- Math. Ann. 95 (1926) 736-788.

[15] Kollár J.: Sharp effective Nullstellensatz.- J. AMS 1 (1988) 963–975.

[16] Krick T. and Pardo L.: A computational Method for Diophantine Approximation.- To appear in Proc. MEGA’94, Birkhäuser Progress in Math.

[17] Kunz E.: Kälher Differentials.- Adv. Lect. in Math., Vieweg Verlag (1986).

[18] Philippon P.: Dénominateurs dans le théorème des zéros de Hilbert.- Acta. Arith. 58 (1991) 1-25.

[19] Sabia J. and Solernó P.: Bounds for Traces in Complete Intersections and Degrees in the Nullstellensatz.- AAECC Journal 6, No.6, Springer-Verlag (1995).

[20] Shiffman B.: Degree bounds for the division problem in polynomial ideals.- Michigan Math. J. 36 (1989) 163-171.

[21] Sombra M.: Bounds for the Hilbert function of polynomial ideals. Preprint Universidad de Buenos Aires (1996).

[22] Teissier B.: Résultats récents d’algèbre commutative effective.- Séminaire Bourbaki 1989-1990, Astérisque vol 189-190 (1991) 107-131.

[23] Vasconcelos W.: Jacobian Matrices and Constructions in Algebra.- Proc. 9th Int. Conf. Applied Algebra, Algebraic Algorithms and Error Correcting Codes AAECC–9, New Orleans, 1991, Springer Lect. Notes Comput.Sci.539 (1992) 48-64.