Sharp estimates for the Arithmetic Nullstellensatz

Teresa Krick^{1}, Luis Miguel Pardo^{2}, and Martín Sombra^{1}

Abstract. We present sharp estimates for the degree and the height of the polynomials in the Nullstellensatz over ZZ . The result improves previous work of Philippon, Berenstein-Yger and Krick-Pardo. We also present degree and height estimates of intrinsic type, which depend mainly on the degree and the height of the input polynomial system. As an application, we derive an effective arithmetic Nullstellensatz for sparse polynomial systems. The proof of these results relies heavily on the notion of local height of an affine variety defined over a number field. We introduce this notion and study its basic properties.

Keywords. Height of varieties, Chow forms, arithmetic Nullstellensatz, intrinsic parameters, sparse elimination theory.

AMS Subject Classification. Primary: 11G35, Secondary: 13P10.

1T. Krick and M. Sombra were partially supported by CONICET, UBACyT and ANPCyT (Argentina), and by the Mathematical Sciences Research Institute at Berkeley (USA).

M. Sombra was also partially supported by grant NSF-DMS 97-29992 to the Institute for Advanced Study at Princeton (USA).

2L. M. Pardo was partially supported by PB 96-0671-C02-02 (Spain), and by CNRS 1026 MEDICIS (France).

2

Contents

Introduction 5

1 Height of polynomials and varieties 10

1.1 Height of polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.1 Height of polynomials over C_{v} . . . . . . . . . . . . . . . . . . . . . 10 1.1.2 Height of polynomials over a number field . . . . . . . . . . . . . . 13

1.2 Height of varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1 Degree of varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.2 Normalization of Chow forms . . . . . . . . . . . . . . . . . . . . . . 17 1.2.3 Height of varieties over C_{v} . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.4 Height of varieties over a number field . . . . . . . . . . . . . . . . . 18 1.2.5 Height of affine toric varieties . . . . . . . . . . . . . . . . . . . . . . 19

2 Estimates for local and global heights 21

2.1 Estimates for Chow forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Generalized Chow forms . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 An estimate for generalized Chow forms . . . . . . . . . . . . . . . . 23

2.2 Basic properties of the height . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Height of varieties under affine maps . . . . . . . . . . . . . . . . . 25 2.2.2 Local height of the intersection of varieties . . . . . . . . . . . . . . 28 2.2.3 An arithmetic Bernstein-Kushnirenko theorem . . . . . . . . . . . . 31

2.3 Local height of norms and traces . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.1 Characteristic polynomials . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.2 Estimates for norms and traces . . . . . . . . . . . . . . . . . . . . . 35

3 An effective arithmetic Nullstellensatz 36

3.1 Division modulo complete intersection ideals . . . . . . . . . . . . . . . . . 36 3.1.1 Tate trace formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.2 A division lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 An effective arithmetic Nullstellensatz . . . . . . . . . . . . . . . . . . . . . 42 3.2.1 Estimates for the complete intersection case . . . . . . . . . . . . . . 42 3.2.2 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Intrinsic type estimates 51

4.1 Equations in general position . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.1.1 An effective Bertini theorem . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.2 Effective Noether normal position . . . . . . . . . . . . . . . . . . . 57

4.2 An intrinsic arithmetic Nullstellensatz . . . . . . . . . . . . . . . . . . . . . 58 4.2.1 Intrinsic parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.2 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.3 Estimates for the sparse case . . . . . . . . . . . . . . . . . . . . . . 63

References 64 4

Introduction

Hilbert Nullstellensatz is a cornerstone of algebraic geometry. Under a simplified form, its statement is the following:

Let f_{1}, …, f_{s} ∈ ZZ[x_{1}, …, x_{n}] be polynomials such that the equation system
f_{1}(x) = 0, …, f_{s}(x) = 0  (1)
has no solution in C^{n}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈
ZZ[x_{1}, …, x_{n}] satisfying the Bézout identity
a = g_{1} f_{1} + ⋯ + g_{s} f_{s}.  (2)

As for many central results in commutative algebra and algebraic geometry, it is an existential non-effective statement. The estimation of both the degree and the height of polynomials satisfying Identity (2) became an important and widely considered question. Effective versions of Hilbert Nullstellensatz apply to a wide range of situations in number theory and theoretical computer science. In particular, they decide the consistency of a given polynomial system. In their arithmetic presentation, they apply to Lojasiewicz inequalities [48], [23] and to the consistency problem over finite fields [25], [19]. We recall that the height h(f) of a polynomial f ∈ ZZ[x_{1}, …, x_{n}] is defined as the logarithm of the maximum modulus of its coefficients. The main result of this paper is the following effective arithmetic Nullstellensatz:

Theorem 1 Let f_{1}, …, f_{s} ∈ ZZ[x_{1}, …, x_{n}] be polynomials without common zeros in C^{n}. Set d := max_{i} deg f_{i} and h := max_{i} h(f_{i}) . Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ ZZ[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 4 n d^{n},

• h(a), h(g_{i}) ≤ 4 n (n + 1) d^{n} (h + log s + (n + 7) log(n + 1) d) .

As we will see below, this result substantially improves all previously known estimates for the arithmetic Nullstellensatz. The following variant of a well-known example due to Masser and Philippon [6] yields a lower bound for any general degree and height estimate. Set

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

for any n , d , H ∈ IN . These are polynomials of degree d and height bounded by h := log H without common zeros in C^{n}. Let a ∈ ZZ \ {0} and g_{1}, …, g_{n} ∈ ZZ[x_{1}, …, x_{n}] such that

a = g_{1} f_{1} + ⋯ + g_{n} f_{n}.

Specializing this identity at x_{1} := H^{d^{n−2}} t^{d^{n−1}−1}, …, x_{n−1} := H t^{d−1}, x_{n} := 1/t we obtain

a = g_{1}(H^{d^{n−2}} t^{d^{n−1}−1}, …, H t^{d−1}, 1/t) H^{d^{n−1}} t^{d^{n}−d}.

We conclude that deg g_{1} ≥ d^{n} − d and h(a) ≥ d^{n−1} h. In fact, a modified version of this example gives the improved lower bound h(a) ≥ d^{n} h (Example 3.10). This shows that our estimate is essentially optimal.

The earlier work on the effective Nullstellensatz dealt with the degree bounds. Let k be a field and let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials of degree bounded by d without common zeros in \overline{k}^{n}. In 1926, Hermann [22] (see also [20], [40]) proved that there exist g_{1}, …, g_{s} ∈ k[x_{1}, …, x_{n}] such that

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

with deg g_{i} f_{i} ≤ 2 (2d)^{2^{n−1}} . After a conjecture of Keller and Gröbner, this estimate was dramatically improved by Brownawell [6] to deg g_{i}f_{i} ≤ n^{2}d^{n} + n d in case char (k) = 0 , while Caniglia, Galligo and Heintz [7] showed that deg g_{i}f_{i} ≤ d^{n^{2}} holds in the general case. These results were then independently refined by Kollár [26] and by Fitchas and Galligo [11] to

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

which is optimal in case d ≥ 3 . For d = 2 , Sombra [50] recently showed that the bound deg g_{i}f_{i} ≤ 2^{n+1} holds.

Now, let us consider the height aspect: assume f_{1}, …, f_{s} ∈ ZZ[x_{1}, …, x_{n}] are polynomials of degree and height bounded by d and h, respectively. The previous degree bound reduces Bézout identity (2) to a system of Q− linear equations, which can be solved by Cramer rule. The obtained estimate for the height of the integer a and the polynomials g_{i} is of type s d^{n^{2}} (h + log s + d) . However, it was soon conjectured that the true height bound should be much smaller. Philippon [45] obtained the following sharper estimate for the denominator a in the Bézout equation:

deg g_{i} ≤ (n + 2) d^{n}  ,  h(a) ≤ κ(n) d^{n}(h + d),

where κ(n) depends exponentially on n. The first essential progress on height estimates for all the polynomials g_{i} was achieved by Berenstein and Yger [2], who obtained

deg g_{i} ≤ n (2 n + 1) d^{n} , h(a), h(g_{i}) ≤ λ(n) d^{8 n+3} (h + log s + d log d),

where λ(n) is a (non-explicit) constant which depends exponentially on n. Their proof relies on the previous work of Philippon and on techniques from complex analysis. Later on, Krick and Pardo [28], [29] obtained

deg g_{i} ≤ (n d)^{c n}  ,  h(a), h(g_{i}) ≤ (n d)^{c n}(h + log s + d),

where c is a universal constant ( c ≤ 35 ). Their proof, based on duality theory for Gorenstein algebras, is completely algebraic. Finally, Berenstein and Yger [3] improved their height bound to λ(n) d^{4 n+2} (h+log s+d) , and extended it to the case when ZZ is replaced by an arbitrary diophantine ring. It should be said, however, that the possibility of such an extension was already clear from the arguments of [29]. We refer the reader to the surveys [55], [1], [42] for a broad introduction to the history of the effective Nullstellensatz, main results and open questions. Aside from degree and height estimates, there is a strong current area of research on computational issues [17], [12], [29], [16], [15], [19]. There are other results in the recent research papers [47], [27], [9].

With respect to previous work, in this paper we improve in an almost optimal way the dependence of the height estimate on d^{n} and we eliminate the extraneous exponential constants depending on n. We remark that the polynomials arising in Theorem 1 are a slight variant of the polynomials which appear in [29] and can thus be effectively computed by their algorithm.

Although the exponential behavior of the degree and height estimates is — in the worstcase — unavoidable, it has been observed that there are many particular instances in which these estimates can be essentially improved. This has motivated the introduction of parameters associated to the input system which identify special families whose behavior with respect to our problem is polynomial instead of exponential. In this spirit, Giusti et al. [16] introduced the notion of degree of a polynomial system f_{1}, …, f_{s}. Roughly speaking, this parameter measures the degree of the varieties cut out by f_{1}, …, f_{i} for i = 1, …, s − 1 . It was soon realized that the degrees in the Nullstellensatz can be controlled in terms of this parameter, giving rise to the so-called “intrinsic Nullstellensätze” [16], [30], [15], [49]. Recently Hägele, Morais, Pardo and Sombra [19] (see also [18]) obtained an arithmetic analogue of these intrinsic Nullstellensätze. To this aim, they introduced the notion of height of a polynomial system, the arithmetic analogue of the degree of the system. They obtained degree and height estimates which depend polynomially on the number of variables and on the degree, height and complexity of the input system. This result followed from their study of the computational complexity of the Nullstellensatz. In this paper we obtain a dramatical improvement over this result, bringing it to an (apparently) almost optimal form. In particular, we show that the dependence on the degree and the height of the system is linear, and we eliminate the influence of the complexity of the input.

Theorem 2 Let f_{1}, …, f_{s} ∈ ZZ[x_{1}, …, x_{n}] be polynomials without common zeros in C^{n}. Set d := max_{i} deg f_{i} and h := max_{i} h(f_{i}) . Let δ and η denote the degree and the height of the polynomial system f_{1}, …, f_{s}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ ZZ[x_{1}, …, x_{n}] such that

• a = g_{1} f_{1} + ⋯ + g_{s} f_{s}, • deg g_{i} ≤ 2 n^{2} d δ,

• h(a), h(g_{i}) ≤ (n + 1)^{2} d (2 η + (h + log s) δ + 21 (n + 1)^{2} d log(d + 1) δ).

Since δ ≤ d^{n−1} and η ≤ n d^{n−1} (h + log s + 3 n (n + 1) d) (Lemma 4.8) one recovers from this statement essentially the same estimates of Theorem 1. However, we remark that Theorem 2 is a more flexible result, as there are many situations in which the degree and the height of the input system are smaller than the Bézout bounds. When this is the case, it yields a much more accurate estimate (Subsection 4.2.2).

As an application of Theorem 2 we derive an arithmetic effective Nullstellensatz for sparse polynomial systems. To state this result, we first need to introduce some standard notation. The support Supp(f_{1}, …, f_{s}) of a polynomial system f_{1}, …, f_{s} ⊂ C[x_{1}, …, x_{n}] is defined as the set of exponents of all the non-zero monomials of all f_{i} ’s, and the Newton polytope N (f_{1}, …, f_{s}) is the convex hull of this support. The (normalized) volume of f_{1}, …, f_{s} equals n! times the volume of the corresponding Newton polytope. The notions of Newton polytope and volume of a polynomial system give a sharper characterization of its monomial structure than the degree alone. These concepts were introduced in the context of root counting by Bernstein [4] and Kushnirenko [32], and are now in the basis of sparse elimination theory (see e.g. [53]). We obtain the following result:

Corollary 3 Let f_{1}, …, f_{s} ∈ ZZ[x_{1}, …, x_{n}] be polynomials without common zeros in C^{n}. Set d := max_{i} deg f_{i} and h := max_{i} h(f_{i}) . Let V denote the volume of the polynomial system 1, x_{1}, …, x_{n}, f_{1}, …, f_{s}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ ZZ[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 2 n^{2} d V,

• h(a), h(g_{i}) ≤ 2 (n + 1)^{3} d V ( h + log s + 2^{2n+4}d log(d + 1)).

The crucial observation here is that both the degree and the height of a polynomial system are essentially controlled by the normalized volume. This follows from an adequate arithmetic version of the Bernstein-Kushnirenko theorem (Proposition 2.11). Our result follows then from Theorem 2 in a straightforward way. As before, we can apply the worst-case bound V ≤ d^{n} to recover from this result an estimate similar to the one presented in Theorem 1. However, this result gives sharper estimates for both the degree and the height when the input system is sparse (Example 4.13). The sparse aspect in the Nullstellensatz was previously considered by Canny and Emiris [8] for the case of n + 1 n -variate Laurent polynomials without common roots at toric infinity. Their result is the sparse analogue of Macaulay effective Nullstellensatz (see e.g. [34]). The first general sparse Nullstellensatz was obtained by Sombra [50]. In both cases the authors give bounds for the Newton polytopes of the output polynomials in terms of the Newton polytopes of the input ones. We refer to the original papers for the exact statements. It is quite difficult to make a definite comparison between these results and ours. The latter does not give sharp bounds for Newton polytopes. But on the other hand, our degree estimate for the general case is better, while the height estimate is completely new.

The key ingredient in our treatment of the arithmetic Nullstellensatz is the notion of local height of a variety defined over a number field K. Let V ⊂ IA^{n}(\overline{Q}) be an equidimensional affine variety defined over K. For each absolute value v over K, we introduce the local height h_{v}(V) of V at v as a Mahler measure of a suitable normalized Chow form of V . This definition is consistent with the Faltings height h(V) of V , namely:

h(V) = \frac{1}{[K : Q]} ∑_{v∈M_{K}} N_{v} h_{v}(V),

where M_{K} denotes the set of canonical absolute values of K, and N_{v} the multiplicity of v. We study the basic properties of this notion. In particular we are able to estimate the local height of the trace and the norm of a polynomial f ∈ K[x_{1}, …, x_{n}] with respect to an integral extension K[IA^{r}] ↪ K[V] . We also obtain local analogues of many of the global results of Bost, Gillet and Soulé [5] and Philippon [46]. Our proof of the arithmetic Nullstellensatz is based on duality theory for Gorenstein algebras (Tate trace formula). This technique was introduced in the context of the effective Nullstellensatz in [17], [12]. Here, we follow mostly the lines of Sabia-Solernó [47] and Krick–Pardo [29]. The trace formula allows to perform division modulo complete intersection ideals, with good control of the degree and height of the involved polynomials. The local arithmetic intersection theory plays, with respect to the height estimates, the role of the classical intersection theory with respect to the degree bounds.

Finally, we remark that all of our results are valid not just for Q but for arbitrary number fields. Moreover, it is quite evident from our arguments that they can be extended to any product formula field. In fact, the general analysis over number fields is necessary to obtain the sharpest estimates for the case K := Q. We also remark that the estimates in the general version of Theorem 1 do not depend on the involved number field.

The outline of the paper is the following: In Chapter 1, we recall the basic definitions and properties of the height of polynomials, and we introduce the notion of local height of a variety defined over a number field. In Chapter 2, we derive useful estimates for the local heights of the trace and the norm of a polynomial in K[V] , and we study the behavior of the local heights of the intersection of a variety with a hypersurface. In Chapter 3, we recall the basic facts of duality theory which will be useful in our context, and we prove Theorem 1.

In Chapter 4, we focus on the intrinsic and sparse versions of the arithmetic Nullstellensatz.

1 Height of polynomials and varieties

Throughout this paper Q denotes the field of rational numbers, ZZ the ring of rational integers, K a number field, and O_{K} its ring of integers. We also denote by IR the field of real numbers, C the field of complex numbers, k an arbitrary field, and \overline{k} an algebraic closure of k. As usual, IA^{n} and IP^{n} will denote the affine and the projective space of n dimensions over \overline{k}, respectively. For every rational prime p we denote by | · |_{p} the corresponding p -adic absolute value over Q . We also denote the ordinary absolute value by | · |_{∞} or simply by | · |. These form a complete set of independent absolute values over Q : we identify the set M_{Q} of these absolute values with the set {∞, p; p prime}. For v ∈ M_{Q} we denote by Q_{v} the completion of Q with respect to the absolute value v. In case v = ∞ we have Q_{∞} = IR , while in case p is prime, we have that Q_{p} is the p -adic field. There exists a unique extension of v to an absolute value over the algebraic closure C_{v} of Q_{v}, which we denote by v. In case v = ∞ we have C_{∞} = C .

1.1 Height of polynomials

In this section we introduce the different measures for the size of a multivariate polynomial, both over C_{v} and over a number field. We establish the link between the different notions and study their basic properties.

1.1.1 Height of polynomials over C_{v}

We fix an absolute value v ∈ {∞, p; p prime} for the rest of this chapter. Let A ⊂ C_{v} be a finite set. The absolute value of A is defined as

|A|_{v} := max{ |a|_{v} , a ∈ A},

and the (logarithmic) height of A as

h_{v}(A) := max{ 0, log |A|_{v} }.

For a polynomial f = ∑_{α} a_{α} x^{α} ∈ C_{v}[x_{1}, …, x_{n}] , we define the absolute value of f (denoted by |f|_{v}) as the absolute value of its set of coefficients, and the height of f (denoted by h_{v}(f) ) as the height of its set of coefficients. That is

|f|_{v} := max_{α}{ |a_{α}|_{v} },
h_{v}(f) := max{ 0, log |f|_{v} }.

When v = ∞, i.e. when f has complex coefficients, we shall make use of the (logarithmic) Mahler measure of f defined as

m(f) := ∫_{0}^{1} ⋯ ∫_{0}^{1} log |f(e^{2π it_{1}}, …, e^{2π it_{n}})| dt_{1} … dt_{n}.

This integral is well-defined, as log |f| is a plurisubharmonic function on C^{n} [37, Appendix I]. The Mahler measure was introduced by Lehmer [35] for the case of a univariate polynomial f := a_{d} ∏_{i=1}^{d}(x − α_{i}) ∈ C[x] as

m(f) = log |a_{d}| + ∑_{i=1}^{d} max{0, log |α_{i}| }.

The link between both expressions of m(f) is given by Jensen formula. The general case was introduced and studied by Mahler [38]. The key property of the Mahler measure is its additivity:

m(f g) = m(f) + m(g).

We have the following relation between log |f| and m(f) :

− log(n + 1) deg f ≤ m(f) − log |f| ≤ log(n + 1) deg f.  (1.1)

The right inequality follows from the definition of m and the fact that the number of monomials of f is bounded by \binom{n+deg f}{n} ≤ (n + 1)^{deg f} . For the left inequality, we refer to [44, Lemme 1.13] and its proof. When f has total degree bounded by 1 , the inequality is refined to log |f| ≤ m(f) . Also, for any degree, m(f(x_{1}, …, x_{n−1}, 0)) ≤ m(f) . We shall make frequent use of the following more precise relation:

Lemma 1.1 Let f ∈ C[X_{1}, …, X_{r}] be a polynomial in r groups of n_{i} variables each. Let d_{i} denote the degree of f in the group of variables X_{i}. Then

− ∑_{i=1}^{r} log(n_{i} + 1) d_{i} ≤ m(f) − log |f| ≤ ∑_{i=1}^{r} log(n_{i} + 1) d_{i}.

Proof.– The right inequality follows directly from the definition of m(f) and the fact that we can bound by ∏_{i}(n_{i} + 1)^{d_{i}} the number of monomials of f . Thus we only consider the left inequality. Let f_{α_{1}···α_{i}} ∈ C[X_{i+1}, …, X_{r}] denote the coefficient of f with respect to the monomial X_{1}^{α_{1}} ⋯ X_{i}^{α_{i}}. Applying Inequality (1.1) we obtain for all (ξ_{i+1}, …, ξ_{r}) in C^{n_{i+1}+···+n_{r}} :

log |f_{α_{1}···α_{i−1}}(X_{i}, ξ_{i+1}, …, ξ_{r})| ≤ m(f_{α_{1}···α_{i−1}}(X_{i}, ξ_{i+1}, …, ξ_{r})) + log(n_{i} + 1) d_{i}

We have |f_{α_{1}···α_{i−1}}(X_{i}, ξ_{i+1}, …, ξ_{r})| = max_{α_{i}} |f_{α_{1}···α_{i}}(ξ_{i+1}, …, ξ_{r})|. We integrate both sides of the last inequality on S_{1}^{n_{i+1}+···+n_{r}} and we deduce

max_{α_{i}} m(f_{α_{1}···α_{i}}) ≤ m(f_{α_{1}···α_{i−1}}) + log(n_{i} + 1) d_{i}

The statement follows then by induction and the fact that

log |f|_{v} = max{m(f_{α_{1}···α_{r}}); α_{i} ∈ ZZ^{n_{i}}}.
□

Let f ∈ C[X_{1}, …, X_{r}] be a multihomogeneous polynomial in r groups of n_{i} + 1 each, and set f^{a} for a deshomogenization of f with respect to these groups of variables. Then m(f^{a}) = m(f) , log |f^{a}| = log |f|. Thus the estimates of the preceding lemma also hold for f . Next we introduce the (logarithmic) S_{n} -Mahler measure of a complex polynomial f in C[x_{1}, …, x_{n}] as

m(f; S_{n}) := ∫_{S_{n}} log |f| μ_{n},

where S_{n} := {(z_{1}, …, z_{n}) ∈ C^{n} : |z_{1}|^{2} + ⋯ + |z_{n}|^{2} = 1} is the unit sphere in C^{n}, and μ_{n} is the measure of total mass 1 , invariant with respect to the unitary group U(n) . More generally, let f ∈ C[X_{1}, …, X_{r}] be a polynomial in r groups of n variables each. Its S_{n}^{r} -Mahler measure is then defined as

m(f; S_{n}^{r}) := ∫_{S_{n}^{r}} log |f| μ_{n}^{r},

with S_{n}^{r} := S_{n} × ⋯ × S_{n}. This alternative Mahler measure was introduced by Philippon [46, I]. With this notation, the ordinary Mahler measure m(f) of f ∈ C[x_{1}, …, x_{n}] coincides with m(f; S_{1}^{n}) . The S_{n}^{r} -Mahler measure is related to the ordinary Mahler measure by the following inequalities [36]:

0 ≤ m(f) − m(f; S_{n}^{r}) ≤ r d ∑_{i=1}^{n−1} \frac{1}{2 i},  (1.2)

where d is a bound for the degree of f in each group of variables.

Finally, we summarize in the following lemma the basic properties of the notion of height of polynomials in C_{v}[x_{1}, …, x_{n}] .

Lemma 1.2 Let v ∈ M_{Q} and f_{1}, …, f_{s} ∈ C_{v}[x_{1}, …, x_{n}] .

1. If v = ∞ then

(a) h_{∞}(∑_{i} f_{i}) ≤ max_{i}{h_{∞}(f_{i})} + log s .

(b) h_{∞}(∏_{i=1}^{s} f_{i}) ≤ ∑_{i=1}^{s} h_{∞}(f_{i}) + log(n + 1) ∑_{i=1}^{s−1} deg f_{i} .

h_{∞}(f_{1} f_{2}) ≤ h_{∞}(f_{1}) + h_{∞}(f_{2}) + log(n + 1) min{deg f_{1}, deg f_{2}}

(c) Let g ∈ C[y_{1}, …, y_{s}] . Set d := max_{i}{deg f_{i}} and h_{∞} := max_{i}{h_{∞}(f_{i})}. Then

h_{∞}(g(f_{1}, …, f_{s})) ≤ h_{∞}(g) + deg g (h_{∞} + log(s + 1) + log(n + 1) d).

(d) log | ∏_{i} f_{i}|_{∞} ≥ ∑_{i} log |f_{i}|_{∞} − 2 log(n + 1) ∑_{i} deg f_{i}.

2. If v = p for some prime p then

(a) h_{p}(∑_{i} f_{i}) ≤ max_{i}{h_{p}(f_{i})} .

(b) h_{p}(∏_{i} f_{i}) ≤ ∑_{i} h_{p}(f_{i}) .

(c) Let g ∈ C_{p}[y_{1}, …, y_{s}] . Set d := max_{i}{deg f_{i}} and h_{p} := max_{i}{h_{p}(f_{i})}. Then

h_{p}(g(f_{1}, …, f_{s})) ≤ h_{p}(g) + deg g h_{p}.
(d) log | ∏_{i} f_{i}|_{p} = ∑_{i} log |f_{i}|_{p}.

Proof of Lemma 1.2.– (1.a), (1.b), (2.a) and (2.b) are immediate from the definition of h_{v}. (1.c) and (2.c): Let us consider the case v = ∞. Set c(n) := log(n + 1) . First we compute h_{v}(f_{1}^{α_{1}} ⋯ f_{s}^{α_{s}}) for the exponent (α_{1}, …, α_{s}) of a monomial of g. Applying (1.b) we obtain

h_{∞}(f_{1}^{α_{1}} ⋯ f_{s}^{α_{s}}) ≤ (c(n) d + h_{∞}) ∑_{i} α_{i} ≤ (c(n) d + h_{∞}) deg g.

The polynomial g has at most (s + 1)^{deg g} monomials and so

h_{∞}(g(f_{1}, …, f_{s})) ≤ h_{∞}(g) + (c(n) d + h_{∞}) deg g + c(s) deg g

The case v ≠ ∞ follows in a similar way. (1.d) and (2.d): In case v = ∞, we apply directly Inequality (1.1):

∑_{i} log |f_{i}|_{∞} ≤ ∑_{i}(m(f_{i}) + c(n) deg f_{i})
= m(∏_{i} f_{i}) + c(n) ∑_{i} deg f_{i}
≤ log | ∏_{i} f_{i}|_{∞} + 2 c(n) ∑_{i} deg f_{i}.

In case v = p, Gauss Lemma implies that ∑_{i} log |f_{i}|_{p} = log | ∏_{i} f_{i}|_{p}. □

We shall make frequent use of the following particular case of the previous lemma: Let (f_{ij})_{ij} be a s × s -matrix of polynomials in C_{v}[x_{1}, …, x_{n}] of degrees and heights bounded by d and h_{v} respectively. From Lemma 1.2(a,b) we obtain:

• h_{∞}(det(f_{ij})_{ij}) ≤ s (h_{∞} + log s + d log(n + 1)) ,

• h_{p}(det(f_{ij})_{ij}) ≤ s h_{p} .

1.1.2 Height of polynomials over a number field

The set M_{K} of absolute values over K which extend the absolute values in M_{Q} is called the canonical set. We denote by M_{K}^{∞} the set of archimedean absolute values in M_{K}. If v ∈ M_{K} extends an absolute value v_{0} ∈ M_{Q} (which is denoted by v | v_{0} ) there exists a (non necessarily unique) immersion σ_{v} : K ↪ C_{v_{0}} corresponding to v, i.e. such that |ξ|_{v} = |σ_{v}(ξ)|_{v_{0}} for every ξ ∈ K.

In the p -adic case, there is a one-to-one correspondence P ↦ v(P) between the prime ideals of O_{K} which divide p, and absolute values extending p, defined by

|ξ|_{v(P)} := p^{−ord_{P}(ξ)/e_{P}} = N(P)^{−ord_{P}(ξ)/e_{P} f_{P}}

for ξ ∈ K^{∗}. Here e_{P} denotes the ramification index of P, ord_{P}(ξ) the order of P in the factorization of ξ, and N(P) the norm of the ideal P. Thus ξ lies in O_{K} if and only if log |ξ|_{v} ≤ 0 for every non-archimedean absolute value v. We denote by K_{v} the completion of K in C_{v_{0}} . The local degree of K at v is defined as:

N_{v} := [K_{v} : Q_{v_{0}}],

and it coincides with the number of different immersions σ : K ↪ C_{v_{0}} which correspond to v. When v is archimedean, K_{v} is either IR or C , and N_{v} equals 1 or 2 accordingly. In the non-archimedean case we have

N_{v} = e_{P}f_{P}

where f_{P} := [O_{K}/P : ZZ/(p)] denotes the residual degree of the prime ideal P which corresponds to v. We have

[K : Q] = ∑_{v | v_{0}} N_{v}

for v_{0} ∈ M_{Q}. The canonical set M_{K} satisfies the product formula with multiplicities N_{v}:

∏_{v∈M_{K}} | x |_{v}^{N_{v}} = 1,  ∀x ∈ K^{∗}.  (1.3)

Let A ⊂ K be a finite set. Let v ∈ M_{K} be an absolute value which extends v_{0} ∈ M_{Q}, and let σ_{v} be an immersion corresponding to v. The local absolute value and the local height of A at v are defined as

|A|_{v} := |σ_{v}(A)|_{v_{0}},
h_{v}(A) := h_{v_{0}}(σ_{v}(A)),

respectively. For a polynomial f = ∑_{α} a_{α} x^{α} ∈ K[x_{1}, …, x_{n}] , we define the local absolute value of f at v (denoted by |f|_{v}) as the absolute value at v of its set of coefficients, and the local height of f at v (denoted by h_{v}(f) ) as the logarithmic height at v of its set of coefficients.

Finally the (global) height of a finite set A ⊂ K is defined as

h(A) := \frac{1}{[K : Q]} ∑_{v∈M_{K}} N_{v} h_{v}(A).

In the same way, the (global) height of f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] is defined as the global height of its set of coefficients, that is

h(f_{1}, …, f_{s}) := \frac{1}{[K : Q]} ∑_{v∈M_{K}} N_{v} max_{i} h_{v}(f_{i}).  (1.4)

These quantities do not depend on the field K in which we consider the set A or the polynomials f_{1}, …, f_{s}. This allows us to extend the definition of h to the polynomial ring \overline{Q}[x_{1}, …, x_{n}] . We have h(A) ≥ 0 and max_{a∈A} h(a) ≤ h(A) . In case A ⊂ O_{K}, h_{v}(a) = 0 for every a ∈ A and v ∉ M_{K}^{∞}, and so h(A) ≤ [K : Q] max_{a∈A} h(a) .

Let q = m/n ∈ Q^{∗} be a rational number, where m ∈ ZZ and n ∈ IN are coprime. Then h(q) = max{|m|, n}, that is, the height of q controls both the size of the minimal numerator and denominator of q. More generally, let A ⊂ Q be a finite set, and let a ∈ IN be a minimal common denominator for all the elements of A. Then h(A) = log max{ |a A|, a }. The following is the analogous statement for the general case:

Lemma 1.3 Let A ⊂ K be a finite set. Then there exist b ∈ ZZ \ {0} and B ⊂ O_{K} such that

b A = B  ,  h(A) ≤ h({b} ∪ B) ≤ [K : Q] h(A).

Proof.– Let v be a non-archimedean absolute value, and set P for the corresponding prime ideal of O_{K}. Then h_{v}(A) = c(P) log N(P)/e(P) f(P) for some c(P) ≥ 0 . We set

b := ∏_{P} N(P)^{c(P)} B := {b a : a ∈ A}.

Clearly b ∈ ZZ , and log |b a|_{v} ≤ h_{v}(A) − c(P) log N(P) ≤ 0 for every v ∉ M_{K}^{∞}, that is B ⊂ O_{K}. We have

h_{v}(b) = ∑_{P} c(P) log N(P) = ∑_{v∉M_{K}^{∞}} N_{v}h_{v}(A)

for v ∈ M_{K}^{∞}, and also h_{v}(A) + log |b|_{v} ≤ h_{v}({b} ∪ B) ≤ h_{v}(A) + h_{v}(b) for all v ∈ M_{K}. Thus

h(\{b\} ∪ B) ≤ \frac{1}{[K : Q]} ∑_{v∈M_{K}^{∞}} N_{v} (h_{v}(A) + h_{v}(b))

−1mm] + \frac{1}{[K : Q]} ∑_{v∈M_{K}^{∞}} N_{v} h_{v}(A) + ∑_{v∉M_{K}^{∞}} N_{v}h_{v}(A)
1mm] ≤ [K : Q] h(A).

On the other hand

h(A) = \frac{1}{[K : Q]} ∑_{v} N_{v}(h_{v}(A) + log |b|_{v}) ≤ \frac{1}{[K : Q]} ∑_{v} N_{v}h_{v}(\{b\} ∪ B) = h(\{b\} ∪ B).

□

Finally, let α ∈ \overline{Q}^{∗} be a non-zero algebraic number, and set p_{α} ∈ ZZ[t] for its primitive minimal polynomial. We have h(α) = m(p_{α})/ deg α. More generally, the height of a finite set can be seen as the height of the minimal polynomial of a generic linear combination of its elements. This gives a partial motivation for the notion of global height of a finite set.

Lemma 1.4 Let A := {a_{1}, …, a_{N}} ⊂ K be a finite set and set

p_{A} := ∏_{σ}(u_{0} + σ(a_{1}) u_{1} + ⋯ + σ(a_{N}) u_{N}) ∈ Q[u_{0}, …, u_{N}],

where the product is taken over all Q -immersions σ : K ↪ \overline{Q} . Then

− log(N + 1) ≤ h(A) − h(p_{A})/[K : Q] ≤ log(N + 1).

Proof.– Set L(u) := u_{0} + a_{1}u_{1} + ⋯ + a_{N}u_{N} ∈ K[u] . We have log |L|_{v} = h_{v}(A) and so

h(p_{A}) ≤ [K : Q] (h(A) + log(N + 1))

by Lemma 1.2(b). On the other hand we have log |L|_{v} ≤ m(σ_{v}(L)) for v ∈ M_{K}^{∞} and thus

[K : Q] h(A) = ∑_{v∈M_{K}^{∞}} N_{v} h_{v}(A) + ∑_{v∉M_{K}^{∞}} N_{v} h_{v}(A)
≤ m(p_{A}) + ∑_{v∉M_{K}^{∞}} N_{v} h_{v}(A)
≤ h(p_{A}) + [K : Q] log(N + 1).

by application of Lemma 1.2(d) and Inequality (1.1). □

1.2 Height of varieties

In this section we introduce the notions of local and global height of an affine variety defined over a number field. For this aim, we recall the basic facts of the degree and Chow form of varieties. As an important particular case, we study the height of an affine toric variety.

1.2.1 Degree of varieties

Let k be an arbitrary field and V ⊂ IA^{n} be an affine equidimensional variety of dimension r. We recall that the degree of V is defined as the number of points in the intersection of V with a generic linear space of dimension n − r. This coincides with the sum of the degrees of its irreducible components. For an arbitrary variety V ⊂ IA^{n} we set V = ∪_{i} V_{i} for its decomposition into equidimensional varieties. Following Heintz [20], we define the degree of V as

deg V := ∑_{i} deg V_{i}.

For V = ∅ we agree deg V := 1 . This is a positive integer, and we have deg V = 1 if and only V is a linear variety. The degree of a hypersurface equals the degree of any generator of its defining ideal. The degree of a finite variety equals its cardinal. For a linear morphism φ : IA^{n} → IA^{m} and a variety V ⊂ IA^{n} we have deg \overline{φ(V)} ≤ deg V . The basic aspect of this notion of degree is its behavior with respect to intersections. It verifies the Bézout inequality:

deg(V ∩ W) ≤ deg V deg W

for V, W ⊂ IA^{n}, without any restriction on the intersection type of V and W [20], [13].

1.2.2 Normalization of Chow forms

Let V ⊂ IA^{n} be an affine equidimensional variety of dimension r defined over a field k. Let f_{V} be a Chow form of V , that is a Chow form of its projective closure \overline{V} ⊂ IP^{n}. This is a squarefree polynomial over k in r + 1 groups U_{0}, …, U_{r} of n + 1 variables each. It is multihomogeneous of degree D := deg V in each group of variables, and is uniquely determined up to a scalar factor. In case V is irreducible, f_{V} is an irreducible polynomial, and in the general case of an equidimensional variety, the product of Chow forms of its irreducible components is a Chow form of V . In order to avoid this indeterminacy of f_{V} , we are going to fix one of its coefficients under some assumption on the variety V . For purpose of reference, we resume it in the following:

Assumption 1.5 We assume that the projection π_{V} : V → IA^{r} defined by x ↦ (x_{1}, …, x_{r}) verifies #π_{V}^{−1}(0) = deg V .

This assumption implies that π_{V} : V → IA^{r} is a dominant map of degree deg V , by the theorem of dimension of fibers. Later on, we will prove that in fact the projection π_{V} is finite, that is, the variables x_{1}, …, x_{r} are in Noether normal position with respect to V (Lemma 2.13). We remark that the previous condition is satisfied by any variety under a generic linear change of variables. Each group of variables U_{i} is associated to the coefficients of a generic linear form L_{i}(U_{i}) := U_{i 0} + U_{i 1} x_{1} + ⋯ + U_{i n}x_{n}. The main feature of a Chow form is that

f_{V} (ν_{0}, …, ν_{r}) = 0 ⇔ \overline{V} ∩ \{L^{h}(ν_{0}) = 0\} ∩ … ∩ \{L^{h}(ν_{r}) = 0\} ≠ ∅

holds for ν_{i} ∈ \overline{k}^{n+1} . Here L_{i}^{h} := U_{i 0} x_{0} + ⋯ + U_{i n}x_{n} stands for the homogenization of L_{i}. Assumption 1.5 implies that \overline{V} ∩ \{x_{1} = 0\} ∩ … ∩ \{x_{r} = 0\} is a zero-dimensional variety of IP^{n} lying in the affine space {x_{0} ≠ 0}. Set e_{i} for the the (i + 1) -vector of the canonical basis of k^{n+1} . Then f_{V} (e_{0}, …, e_{r}) — that is, the coefficient of the monomial U_{0 0}^{D} ⋯ U_{r r}^{D} — is non-zero. We then define the (normalized) Chow form Ch_{V} of V by fixing the election of f_{V} through the condition

Ch_{V} (e_{0}, …, e_{r}) = 1.

Under this normalization, Ch_{V} equals the product of the normalized Chow forms of the irreducible components of V .

1.2.3 Height of varieties over C_{v}

Let v be an absolute value over Q , and V ⊂ IA^{n}(C_{v}) an equidimensional variety of dimension r which satisfies Assumption 1.5. We introduce the height of V as a Mahler measure of its normalized Chow form. This notion is closely related to Philippon local height of a projective variety [46, II].

Definition 1.6 The height of the affine variety V ⊂ IA^{n}(C_{v}) is defined as

h_{∞}(V) := m(Ch_{V}; S_{n+1}^{r+1}) + (r + 1) (∑_{i=1}^{n} 1/2 i) deg V

in case v = ∞ is archimedean, and as

h_{p}(V) := h_{p}(Ch_{V})

in case v is non-archimedean, that is v = p for some prime p.

Let us consider some examples:

• We have that h_{∞}(IA^{n}) equals the Stoll number ∑_{i=1}^{n} ∑_{j=1}^{i} 1/2 j, while h_{p}(IA^{n}) = 0 . This follows from [5, Lem.3.3.1] and the fact that Ch_{IA^{n}} = det(U_{0}, …, U_{n}) .

• Let V ⊂ IA^{n}(C_{v}) be a hypersurface verifying Assumption 1.5, defined by a squarefree polynomial f ∈ C_{v}[x_{1}, …, x_{n}] . Then the coefficient of the monomial x_{n}^{deg V} is nonzero, and we can suppose without loss of generality that it equals 1. Then

h_{∞}(V) = m(f^{h}; S_{n+1}) + (∑_{i=1}^{n−1} ∑_{j=1}^{i} 1/2 j) deg V,
h_{p}(V) = h_{p}(f),

where f^{h} denotes the homogenization of f [46, I, Cor. 4].

• In case V = {ξ} for some ξ ∈ IA^{n}, we have (see e.g. [46, I, Prop. 4])

h_{∞}(V) = \frac{1}{2} log(1 + |ξ_{1}|^{2} + ⋯ + |ξ_{n}|^{2}),
h_{p}(V) = h_{p}(ξ).

1.2.4 Height of varieties over a number field

Let V ⊂ IA^{n}(\overline{Q}) be an equidimensional variety of dimension r defined over a number field K. We define the (global) height h(V) of V as the Faltings height [10] of its projective closure \overline{V} ⊂ IP^{n}. Following Philippon [46, III], we introduce h — without appealing to Arakelov theory — through the identity

h(V) = \frac{1}{[K : Q]}( ∑_{v∈M_{K}^{∞}} N_{v} m(σ_{v}(f_{V}); S_{n+1}^{r+1}) + ∑_{v∉M_{K}^{∞}} N_{v} log |f_{V} |_{v}) + (r+1) (∑_{i=1}^{n} 1/2 i) deg V,

where f_{V} denotes any Chow form of V [52], [46, I]. This coincides with the sum of the heights of the irreducible components of V . For an arbitrary affine variety, we define its (global) height as the sum of the heights of its equidimensional components. We agree that h(∅) := 0 .

We introduce the local counterpart of this notion. Let v ∈ M_{K} be absolute value over K, and suppose that V satisfies Assumption 1.5. Let v_{0} ∈ M_{Q} such that v|v_{0} , and let σ_{v} : K_{v} → C_{v_{0}} be an immersion corresponding to v. We define the local height of V at v as

h_{v}(V) := h_{v_{0}}(σ_{v}(V)).

This definition is consistent with the global height, namely

h(V) = \frac{1}{[K : Q]} ∑_{v∈M_{K}} N_{v} h_{v}(V).

This notion is related to the height ĥ of Bost, Gillet and Soulé, by the formula [5, Prop. 4.1.2 (i)]:

h(V) = ĥ(V) + (∑_{i=1}^{r} ∑_{j=1}^{i} 1/2 j) deg V.

It is also related to the height h̃ introduced by Giusti et al. [15] in terms of the so-called geometric solution of a variety. They are polynomially equivalent [51, 1.3.4], namely

h(V) ≤ (n deg V h̃(V))^{c}  ,  h̃(V) ≤ (n deg V h(V))^{c},

for some constant c > 0 . We have h(V) ≥ 0 . Moreover h(V) ≥ (∑_{i=1}^{r} ∑_{j=1}^{i} 1/2 j) deg V , with equality only in case V is defined by the vanishing of n − r standard coordinates. [5, Th. 5.2.3]. For instance h(IA^{n}) = ∑_{i=1}^{n} ∑_{j=1}^{i} 1/2 j.

This notion of height satisfies the arithmetic Bezout inequality [5, Th. 5.5.1 (iii)], [46, III, Th. 3]:

h(V ∩ W) ≤ h(V) deg W + deg V h(W) + c deg V deg W,

for V, W ⊂ IA^{n}(\overline{Q}) , with

c := ( ∑_{i=0}^{dim V} ∑_{j=0}^{dim W} 1/2(i + j + 1) ) + ( n − (dim V + dim W)/2 ) log 2.

1.2.5 Height of affine toric varieties

Now we consider the case of affine toric varieties. The obtained height estimate is crucial in our treatment of the sparse arithmetic Nullstellensatz (Corollary 4.12). Let A = {α_{1}, …, α_{N}} ⊂ ZZ^{n} be a finite set of integer vectors such that 0 ∈ A. Let r := dim A denote the dimension of A, that is, the dimension of the free ZZ− module ZZA. We normalize the volume form of IRA in order that any elementary simplex of the lattice ZZA has volume 1. The (normalized) volume Vol(A) of A is defined as the volume of the convex hull Conv(A) with respect to this volume form. In case ZZA = ZZ^{n}, then Vol(A) equals n! times the volume of Conv(A) with respect to the Euclidean volume form of IR^{n}.

We associate to the set A a map (\overline{Q}^{∗})^{n} → \overline{Q}^{N} defined by ξ ↦ (ξ^{α_{1}}, …, ξ^{α_{N}}) . The Zariski closure of the image of this map is the affine toric variety X_{A} ⊂ IA^{N} . This is an irreducible variety of dimension r and degree Vol(A) . For i = 0, …, r, let U_{i} denote a group of variables indexed by the elements of A and set

F_{i} := ∑_{α∈A} U_{iα} x^{α}

for the generic Laurent polynomial with support contained in A. Let W ⊂ (IP^{N−1})^{r+1} × (\overline{Q}^{∗})^{n} be the incidence variety of F_{0}, …, F_{r} in (\overline{Q}^{∗})^{n}, that is

W = {(ν_{0}, …, ν_{r}; ξ); F_{i}(ν_{i})(ξ) = 0 ∀i},

and let π : (IP^{N−1})^{r+1} × (\overline{Q}^{∗})^{n} → (IP^{N−1})^{r+1} be the canonical projection. Then \overline{π(W)} is an irreducible variety of codimension 1. Its defining polynomial R_{A} ⊂ Q[U_{0}, …, U_{r}] is called the A -resultant or sparse resultant, and it coincides with the Chow form of the affine toric variety X_{A} [24]. It is a multihomogeneous polynomial of degree Vol(A) in each group of variables, and it is uniquely defined up to its sign, if we assume it to be a primitive polynomial with integer coefficients. Basic references for affine toric varieties and sparse resultants are [14], [54]. We obtain the following bound for the height of X_{A}. Our argument relies on the Canny-Emiris determinantal formula for the sparse resultant [8].

Proposition 1.7 Let A ⊂ ZZ^{n} be a finite set of dimension r and cardinality #A ≥ 2 . Then h(X_{A}) ≤ 2^{2 r+2} log(#A) Vol(A) .

Proof.– Let M be the Canny-Emiris matrix associated to the generic polynomial system F_{0}, …, F_{r}. This is a non-singular square matrix of order M , where M denotes the cardinality of the set

E := ((r + 1) Q + ε) ∩ ZZ^{n}.

Here Q := Conv(A) , and ε ∈ IR^{n} is a vector such that each point in E is contained in the interior of a cell in a given triangulation of the polytope (r + 1) Q. Every non-zero entry of M is a variable U_{iα}. In fact, each row has exactly N non-zero entries, which consist of the variables in some group U_{i}. We refer to [8] for the precise construction. Thus det M ∈ ZZ[U_{0}, …, U_{r}] is a multihomogeneous polynomial of total degree M and height bounded by M log N . This polynomial is a non-zero multiple of the sparse resultant R_{A} [8]. The assumption that R_{A} is primitive implies that det M/R_{A} lies in ZZ[U_{0}, …, U_{r}] , and so m(R_{A}) ≤ m(det M) . Let {T_{j}}_{j∈I} be a unimodular triangulation of Q, so that {(r +1) T_{j}}_{j∈I} is a triangulation of (r+1) Q. For every ε ∈ IR^{n}, the set of integer points in (r+1) T_{j}+ε is in correspondence with a subset of those of (r + 1) T_{j}. Moreover, for a generic choice of ε we loose — at least — the set of integer points in a facet of codimension 1. Thus

#((r + 1) T_{j} + ε) ∩ ZZ^{n} = \binom{2 r}{r} ≤ 2^{2 r}

and so M ≤ 2^{2 r} Vol(A) . Applying Lemma 1.1 we obtain

m(R_{A}) ≤ log | det M| + deg(det M) log N
≤ 2 M log N
≤ 2^{2 r+1} log N Vol(A).

We conclude

h(X_{A}) = m(R_{A}; S_{N+1}^{r+1}) + (r + 1) (∑_{i=1}^{N} 1/2 i) Vol(A)
≤ m(R_{A}) + 2 (r + 1) log N Vol(A)
≤ 2^{2 r+2} log N Vol(A),

as N = #A ≥ 2 . □

In case A ⊂ (ZZ_{≥0})^{n} — that is, when F_{0}, …, F_{r} are polynomials — we set d := max{|α| : α ∈ A} = deg F_{0} . We have then N ≤ (n + 1)^{d} and so

h(X_{A}) ≤ 2^{2 r+2} log(n + 1) d Vol(A).

2 Estimates for local and global heights

In this chapter we study the basic properties of local and global heights that we will need for our purposes. The key result is a precise estimate for the local height of the trace and the norm of a polynomial f ∈ K[x_{1}, …, x_{n}] with respect to an integral extension K[IA^{r}] ↪ K[V] . We also study some of the basic properties of the height of a variety, in particular its behavior under intersection with hypersurfaces and under affine maps.

2.1 Estimates for Chow forms

In this section we recall the notion of generalized Chow form of a variety in the sense of Philippon [44], and we prove a technical estimate for its local height.

2.1.1 Generalized Chow forms

Let V ⊂ IA^{n} be an affine equidimensional variety of dimension r and degree D defined over a field k. For d ∈ IN we denote by U(d)_{0} a group of \binom{d+n}{n} variables. Also, for 1 ≤ i ≤ r we denote by U_{i} a group of n + 1 variables, and we set U(d) := {U(d)_{0}, U_{1}, …, U_{r}}. Set

F := ∑_{|α|≤d} U(d)_{0α} x^{α}  ,  L_{i} := U_{i 0} + U_{i 1} x_{1} + ⋯ + U_{i n} x_{n}

for the generic polynomial in n variables of degree d and 1 associated to U(d)_{0} and U_{i} respectively. Set N := \binom{d+n}{n} + r (n + 1) and let W ⊂ IA^{N} × V be the incidence variety of F, L_{1}, …, L_{r} with respect to V , that is

W := {(ν(d)_{0}, ν_{1}, …, ν_{r}; ξ) ; ξ ∈ V, F (ν(d)_{0})(ξ) = 0, L_{i}(ν_{i})(ξ) = 0, 1 ≤ i ≤ r}.

Let π : IA^{N} × IA^{n} → IA^{N} denote the canonical projection. Then \overline{π(W)} ⊂ IA^{N} is a hypersurface [44, Prop. 1.5] and any of its defining equations f_{d,V} ∈ k[U(d)] is called a generalized Chow form or a d -Chow form of V . A d -Chow form is uniquely defined up to a scalar factor. It shares many properties with the usual Chow form, which corresponds to the case d = 1 . We have

f_{d,V} (ν(d)_{0}, ν_{1}, …, ν_{r}) = 0 ⇔
⇔ \overline{V} ∩ \{F^{h}(ν(d)_{0}) = 0\} ∩ \{L_{1}^{h}(ν_{1}) = 0\} ∩ ⋯ ∩ \{L_{r}^{h}(ν_{r}) = 0\} ≠ ∅

for ν(d)_{0} ∈ \overline{k}^{\binom{d+n}{n}} and ν_{i} ∈ \overline{k}^{n+1} . Here \overline{V} ⊂ IP^{n} denotes the projective closure of V , while F^{h} and L_{i}^{h} stand for the homogenization of F and L_{i} respectively. A d -Chow form f_{d,V} ∈ k[U(d)] is a multihomogeneous polynomial of degree D in the group of variables U(d)_{0} and of degree d D in each group U_{i} [44, Lem. 1.8]. When V is an irreducible variety, f_{d,V} is an irreducible polynomial of k[U(d)] . When V is equidimensional, it coincides with the product of d -Chow forms of its irreducible components.

We will appeal to the following relation between a d -Chow form f_{d,V} and the usual one: Let U_{0} be another group of n + 1 variables, and consider the morphism

ϱ_{d} : k[U(d)] → k[U_{0}, U_{1}, …, U_{r}]

defined by ϱ_{d}(F) = L_{0}^{d} and ϱ_{d}(L_{i}) = L_{i} for i = 1, …, r, where L_{0} stands for the generic linear form associated to U_{0} . In other terms

ϱ_{d}(U(d)_{0α}) = \binom{d}{α}U_{00}^{d−|α|} U_{01}^{α_{1}} ⋯ U_{0n}^{α_{n}}

where

\binom{d}{α} := \frac{d!}{(d − |α|)! α_{1}! ⋯ α_{n}!}

for |α| ≤ d, and ϱ_{d}(U_{i j}) = U_{i j} for i = 1, …, r and j = 0, …, n. Then ϱ_{d}(f_{d,V}) = λ f_{V}^{d} for some λ ∈ k^{∗} [44, Prop. 1.4].

Now assume that V satisfies Assumption 1.5. Then \overline{V} ∩ \{x_{0}^{d} = 0\} ∩ \{x_{1} = 0\} ∩ … ∩ \{x_{r} = 0} = ∅. Setting e(d)_{α} and e_{i} for the α -vector and the (i + 1) -vector of the canonical bases of k^{\binom{d+n}{n}} and k^{n+1} respectively, we infer that f_{d,V} (e(d)_{0}, e_{1}, …, e_{r}) — that is, the coefficient of the monomial U(d)_{00}^{D} U_{11}^{d D} ⋯ U_{rr}^{d D} — is non-zero.

We define the (normalized) d -Chow form Ch_{d,V} of V by fixing the election of f_{d,V} with the condition Ch_{V} (e(d)_{0}, e_{1}, …, e_{r}) = 1 . In the previous construction, U(d)_{00}^{D} U_{11}^{d D} … U_{rr}^{d D} is the only monomial of k[U(d)] which maps through ϱ_{d} to U_{00}^{d D} ⋯ U_{rr}^{d D}. The imposed normalizations imply then

ϱ_{d}(Ch_{d,V}) = Ch_{V}^{d} .

2.1.2 An estimate for generalized Chow forms

The following technical result is crucial to our local height estimates for the trace and the norm of a polynomial (Subsection 2.3.2), as well as for the intersection of a variety with an hypersurface (Subsection 2.2.2). The proof follows the lines of [44, Prop. 2.8]. We adopt the following convention: Let f ∈ k[x_{1}, …, x_{n}] be a polynomial of degree d. We denote by f_{d,V} (f) and Ch_{d,V} (f) the specialization of U(d)_{0} into the coefficients of f in f_{d,V} and Ch_{d,V} respectively.

Lemma 2.1 Let V ⊂ IA^{n}(C_{v}) be an equidimensional variety of dimension r which satisfies Assumption 1.5. Let f ∈ C_{v}[x_{1}, …, x_{n}] . Then

• m(Ch_{deg f,V} (f); S_{n+1}^{r}) + r (∑_{i=1}^{n} 1/2 i) deg f deg V

≤ deg f h_{∞}(V) + h_{∞}(f) deg V + log(n + 1) deg f deg V

if v = ∞,

• h_{p}(Ch_{deg f,V} (f)) ≤ deg f h_{p}(V) + h_{p}(f) deg V if v = p for some prime p.

We will need the following lemma in order to treat the non-archimedean case:

Lemma 2.2 Let f ∈ C_{p}[x_{1}, …, x_{n}] , and let Ω ⊂ IA^{n}(C_{p}) be a Zariski open set. Then

|f|_{p} = max {|f(z)|_{p}; z ∈ Ω, |z|_{p} = 1}.

Proof.– For q ∈ IN we denote by G_{q} the set of q -roots of 1 in \overline{Q} ⊂ C_{p}. Let α = (α_{1}, …, α_{n}) ∈ ZZ^{n} such that |α_{i}| < q. Then

∑_{ω∈G_{q}^{n}} ω^{α} = \{ \begin{matrix}0 & if & α ≠ 0, \\ q^{n} & if & α = 0. \end{matrix}

Set f = ∑_{α} a_{α} x^{α}. Let q > deg f such that |q|_{p} = 1 , that is p |̸ q. Then for any ν = (ν_{1}, …, ν_{n}) ∈ (C_{p}^{∗})^{n} we have

a_{α} = \frac{1}{ν^{α} q^{n}} ∑_{ω∈G_{q}^{n}} f(ν ω) ω^{−α}.

Let α ∈ (ZZ_{≥0})^{n} such that |f|_{p} = |a_{α}|_{p}. From the previous expression we derive that for each ν ∈ S_{n} := {ν; |ν_{i}|_{p} = 1} there exists ω_{0} ∈ G_{q}^{n} such that |f|_{p} = |f(ν ω_{0})|_{p}. The set S_{n} is Zariski dense in IA^{n}(C_{p}) , and so S_{n} ∩ Ω is also dense. Thus we can take ν such that ν G_{q} ⊂ Ω , and therefore

|f|_{p} ≤ max{|f(z)|_{p}; z ∈ Ω, |z|_{p} = 1}.

The other inequality is straightforward. □

Proof of Lemma 2.1.– First we consider the case when V is a 0–dimensional variety. We may assume without loss of generality that V is irreducible, that is V = {ξ} for some ξ = (ξ_{1}, …, ξ_{n}) ∈ C_{v}^{n}. Set d := deg f . Then

Ch_{V} = L(ξ) := U_{0} + U_{1}ξ_{1} + ⋯ + U_{n}ξ_{n}  ,  Ch_{d,V} = F (ξ) := ∑_{α} U_{α} ξ^{α},

where L and F denote generic polynomials in n variables of degree 1 and d respectively. Then

h_{∞}(F (ξ)) = log max_{|α|≤d}{|ξ^{α}|}
= log max_{i}{1, |ξ_{i}|^{d}}
= d h_{∞}(L(ξ))
≤ d m(L(ξ); S_{n+1}) + (∑_{i=1}^{n} 1/2 i) d

and so h_{∞}(Ch_{d,V} (f)) ≤ d h_{∞}(F (ξ))+h_{∞}(f)+log(n+1) d ≤ d h_{∞}(V)+h_{∞}(f)+log(n+1) d. Analogously, h_{p}(F (ξ)) ≤ d h_{p}(L(ξ)) and so h_{p}(Ch_{d,V} (f)) ≤ d h_{p}(V) + h_{p}(f) .

Now we consider the general case. Set ν = (ν_{1}, …, ν_{r}) ∈ C_{v}^{r (n+1)} , L(ν_{i}) := ν_{i 0} + ν_{i 1} x_{1} + ⋯ + ν_{i n} x_{n} and

V (ν) := V ∩ V (L(ν_{1}), …, L(ν_{r})) ⊂ IA^{n}(C_{v}).

Then V (ν) is a 0-dimensional variety of degree deg V for ν in a Zariski open set Ω of IA^{r (n+1)}(C_{v}) . Let ν ∈ Ω . By [44, Prop. 2.4] there exist λ(ν), θ(ν) ∈ k^{∗} such that

Ch_{V (ν)} = λ(ν) Ch_{V} (ν)  ,  Ch_{d,V (ν)} = θ(ν) Ch_{d,V} (ν),

where Ch_{V} (ν), Ch_{d,V} (ν) stand for the specialization of U_{1}, …, U_{r} into ν_{1}, …, ν_{r}. Applying the morphism ϱ_{d} linking the d -Chow form with the usual one we obtain

Ch_{V (ν)}^{d} = ϱ_{d}(Ch_{d,V (ν)}) = θ(ν) ϱ_{d}(Ch_{d,V} (ν)) = θ(ν) Ch_{V}^{d} (ν)

and so θ(ν) = λ(ν)^{d}. We consider the case v = ∞. Any Zariski closed set of IA^{r (n+1)}(C) intersects S_{n+1}^{r} in a set of μ_{n+1}^{r} -measure 0, and so the previous relation holds for almost every ν ∈ S_{n+1}^{r}. Therefore

m(Ch_{d,V} (f); S_{n+1}^{r}) = ∫_{S_{n+1}^{r}}(log |Ch_{d,V (ν)}(f)| − d log |λ(ν)|) μ_{n+1}^{r} ≤

≤ ∫_{S_{n+1}^{r}}(d h_{∞}(V (ν)) + h_{∞}(f) deg V (ν) + log(n + 1) d deg V (ν) − d log |λ(ν)|) μ_{n+1}^{r} =

= d ∫_{S_{n+1}^{r}} m(Ch_{V} (ν); S_{n+1}) μ_{n+1}^{r} + (∑_{i=1}^{n} 1/2 i) d deg V + h_{∞}(f) deg V +

+ log(n + 1) d deg V =

= d h_{∞}(V) + h_{∞}(f) deg V + log(n + 1) d deg V − r (∑_{i=1}^{n} 1/2 i) d deg V.

The case v = p follows analogously from the 0-dimensional case and the previous lemma. □

Remark 2.3 The only role played by Assumption 1.5 in the proof of the previous result is in the normalization of the involved Chow forms. This is essential in order to properly define local heights of varieties. If we disregard normalization, we get altogether the following global result: Let V ⊂ IA^{n} be an equidimensional variety of dimension r defined over a number field K, and let f_{d,V} be a d -Chow form of V . Let f ∈ K[x_{1}, …, x_{n}] be a polynomial of degree d. Then, we have

\frac{1}{[K : Q]}( ∑_{v∈M_{K}^{∞}} N_{v} m(σ_{v}(f_{d,V} (f)); S_{n+1}^{r}) + ∑_{v∉M_{K}^{∞}}N_{v} log |f_{d,V} (f)|_{v}) + r (∑_{i=1}^{n} 1/2 i) d deg V ≤

≤ d h(V) + h(f) deg V + log(n + 1) d deg V.

2.2 Basic properties of the height

We derive some of the basic properties of the notion of height of a variety. In particular, we study the behavior of the height of a variety under intersection with a hypersurface and under an affine map. We also obtain an arithmetic version of the Bernstein-Kushnirenko theorem.

2.2.1 Height of varieties under affine maps

Let φ : IA^{n} → IA^{m} be a regular map defined by polynomials φ_{1}, …, φ_{m} ∈ K[x_{1}, …, x_{n}] . We recall that the height of φ is defined as h(φ) := h(φ_{1}, …, φ_{m}) . We obtain the following estimate for the height of the image of a variety under an affine map:

Proposition 2.4 Let V ⊂ IA^{n} be a variety of dimension r, and let φ : IA^{n} → IA^{N} be an affine map. Then

h(φ(V)) ≤ h(V) + (r + 1) (h(φ) + 8 log(n + N + 1)) deg V.

The proof of this result follows from the study of the particular cases of a linear projection and an injective affine map. The following estimate for the height of a linear projection of a variety generalizes [10, Prop. 2.10] and [5, 3.3.2]. Its proof is essentially based on the description of the Chow form of such projection variety, due to Pedersen and Sturmfels [43, Prop. 4.1].

Lemma 2.5 Let V ⊂ IA^{n} ×IA^{m} be a variety of dimension r, and let π : IA^{n} ×IA^{m} → IA^{n} denote the projection (x, y) ↦ x. Then

h(\overline{π(V)}) ≤ h(V) + 3 (r + 1) log(n + m + 1) deg V.

Proof. We assume without loss of generality that V is irreducible. Set W := \overline{π(V)} ⊂ IA^{n} and s := dim W . The case s = r follows directly from [43, Prop. 4.1]: in this case, there exists a partial monomial order ≺ such that

f_{W} | initf_{V} ,

where initf_{V} denotes the initial polynomial of f_{V} with respect to ≺. In particular initf_{V} is the sum of some of the terms in the monomial expansion of f_{V} . The general case s ≤ r reduces to the previous one: we choose standard coordinates z_{s+1}, …, z_{r} of IA^{m} such that the projection

ϖ : IA^{n} × IA^{m} → IA^{n} × IA^{r−s}  ,  (x, y) ↦ (x, z)

verifies dim Z = r for Z := \overline{ϖ(V)} . Let ϱ : IA^{n} × IA^{r−s} → IA^{n} denote the canonical projection. Then f_{Z} | initf_{V} , π = ϱ ∘ ϖ and W = \overline{ϱ(Z)} . We have that ϱ^{−1}(ξ) = \{ξ\} × IA^{r−s} for ξ ∈ ϱ(Z) by the theorem of dimension of fibers. Thus Z = W × IA^{r−s}, and in particular

i(W) = Z ∩ V (z_{s+1}, …, z_{r}) ⊂ IA^{n} × IA^{r−s},

where i denotes the canonical inclusion IA^{n} ↪ IA^{n} × IA^{r−s}. We have deg W = deg Z and so f_{W} := f_{Z}(z_{s+1}, …, z_{r}) is a Chow form of W [44, Prop. 2.4].

Now we estimate the height of f_{W} . Let K be a number field of definition of V , and set

initf_{V} = Q f_{Z}

for some polynomial Q. From the proof of [44, Lem. 1.12(v)], there is a non-zero coefficient λ of Q such that log |λ|_{v} ≤ m(σ_{v}(Q)) for all v ∈ M_{K}^{∞}. Clearly log |λ|_{v} ≤ log |Q|_{v} also holds for all v ∉ M_{K}^{∞}. Thus

m(σ_{v}(f_{Z})) ≤ m(σ_{v}(initf_{V})) − log |λ|_{v}

for v ∈ M_{K}^{∞}, while log |f_{Z}|_{v} ≤ log |initf_{V} |_{v} − log |λ|_{v} for v ∉ M_{K}^{∞}.

Let v ∈ M_{K}^{∞}. From [44, Lem. 1.13] we obtain m(σ_{v}(f_{W})) ≤ m(σ_{v}(f_{Z})) . Hence

m(σ_{v}(f_{W}); S_{n+1}^{s+1}) ≤ m(σ_{v}(f_{W}))
≤ m(σ_{v}(initf_{V})) − log |λ|_{v}
≤ log |initf_{V} |_{v} + (r + 1) log(n + m + 1) deg V − log |λ|_{v}
≤ log |f_{V} |_{v} + (r + 1) log(n + m + 1) deg V − log |λ|_{v}
≤ m(σ_{v}(f_{V}); S_{n+m+1}^{r+1}) + (r + 1) ( ∑_{i=1}^{n+m} 1/2 i) deg V
+ 2 (r + 1) log(n + m + 1) deg V − log |λ|_{v}

by application of Lemma 1.1 and Inequality (1.2). In case v ∉ M_{K}^{∞} we have analogously log |f_{W} |_{v} ≤ log |f_{V} |_{v} − log |λ|_{v}, and so

h(W) ≤ h(V) + (s + 1) (∑_{i=1}^{n} 1/2 i) deg V + 2 (r + 1) log(n + m + 1) deg V
≤ h(V) + 3 (r + 1) log(n + m + 1) deg V.
□

The following is a variant of [46, I, Prop. 7]:

Lemma 2.6 Let V ⊂ IA^{m} be a variety of dimension r, and let ψ : IA^{m} → IA^{n} be an injective affine map. Then

h(ψ(V)) ≤ h(V) + (r + 1) (h(ψ) + 5 log(n + 1)) deg V.

Proof.– We assume again without loss of generality that V is irreducible. Let K be a number field of definition of both V and ψ, and set ψ(x) = a+A x for some m×n− matrix A of maximal rank and a ∈ K^{n}. Then let ψ^{∗} : IA^{n+1} → IA^{m+1} be the linear map y ↦ (a, A)^{t} y defined by the transpose of the matrix associated to ψ. Set W := ψ(V) , and let \overline{V} ⊂ IP^{m}, \overline{W} ⊂ IP^{n} denote the projective closures of V and W respectively. For i = 0, …, r we let ν_{i} ∈ \overline{Q}^{n+1} , and we set L^{h}(ν_{i}) := ν_{i 0} x_{0} + … + ν_{i n} x_{n} for the homogenization of the associated linear form. Then f_{W} (ν_{0}, …, ν_{r}) = 0 if and only if there exists ξ ∈ \overline{V} such that ψ(ξ) lies in the linear space determined by ν_{0}, …, ν_{r}. Equivalently ξ lies in the linear space determined by ψ^{∗}(ν_{0}), …, ψ^{∗}(ν_{r}) . We conclude that

f_{W} = f_{V} ∘ (ψ^{∗})^{r+1}.

Let v ∈ M_{K}^{∞}. Then

m(σ_{v}(f_{W}), S_{n+1}^{r+1}) ≤ log |f_{W} |_{v} + (r + 1) log(n + 1) deg V
≤ log |f_{V} |_{v} + (r + 1) (h_{v}(ψ) + 2 log(n + 1)) deg V +
+(r + 1) log(n + 1) deg V ≤

≤ m(σ_{v}(f_{V})) + (r + 1) log(m + 1) deg V +
+ (r + 1) (h_{v}(ψ)3 log(n + 1)) deg V ≤
≤ m(σ(f_{V}), S_{m+1}^{r+1}) + (∑_{i=1}^{m} 1/2 i) (r + 1) deg V
+ (r + 1) (h_{v}(ψ) + 4 log(n + 1)) deg V.

Here we have applied Lemma 1.1, Inequality (1.2) and the proof of Lemma 1.2(c), using the fact that the number of monomials of f_{V} is bounded by (n + 1)^{(r+1) deg V} . In case v ∉ M_{K}^{∞} we obtain analogously log |f_{W} |_{v} ≤ log |f_{V} |_{v} + (r + 1) h_{v}(ψ) deg V , and hence

h(ψ(V)) ≤ h(V) + (r + 1) (h(ψ) + 5 log(n + 1)) deg V.
□

Proof of Proposition 2.4.– Let ψ : IA^{n} → IA^{N} × IA^{n} be the injective map x ↦ (φ(x), x) . Then φ decomposes as

φ = π ∘ ψ,

where π : IA^{N} × IA^{n} → IA^{N} denotes the canonical projection. Thus

h(φ(V)) ≤ h(ψ(V)) + 3 (r + 1) log(n + N + 1) deg ψ(V)
≤ h(V) + (r + 1) (h(ψ) + 5 log(n + N + 1)) deg V +
3 (r + 1) log(n + N + 1) deg V =
= h(V) + (r + 1) (h(φ) + 8 log(n + N + 1)) deg V.
□

2.2.2 Local height of the intersection of varieties

We obtain the following estimate for the local height of the intersection of a variety with an hypersurface. This is a consequence of our previous estimate for generalized Chow forms. This result can be seen as the local analogue of [44, Prop. 2.8], and its proof closely follows it.

Proposition 2.7 Let V ⊂ IA^{n} be an equidimensional variety of dimension r defined over a number field K. Let f ∈ K[x_{1}, …, x_{n}] be a polynomial which is not a zero-divisor in K[V] . We assume that both V and V ∩ V (f) satisfy Assumption 1.5. Then there exists λ ∈ K^{∗} such that

• h_{v}(V ∩ V (f)) ≤ deg f h_{v}(V) + h_{v}(f) deg V + log(n + 1) deg f deg V − log |λ|_{v} for v ∈ M_{K}^{∞},

• h_{v}(V ∩ V (f)) ≤ deg f h_{v}(V) + h_{v}(f) deg V − log |λ|_{v} for v ∉ M_{K}^{∞}.

Proof.– Set d := deg f and W := V ∩ V (f) ⊂ IA^{n}. By [44, Prop. 2.4] there exists Q ∈ K[U_{1}, …, U_{r}] \ {0} such that Ch_{d,V} (f) = Q Ch_{W} . Then — as in the proof of Lemma 2.5 — there exists a non-zero coefficient λ of Q such that log |λ|_{v} ≤ m(σ_{v}(Q)) for all v ∈ M_{K}^{∞} and log |λ|_{v} ≤ log |Q|_{v} for all v ∉ M_{K}^{∞}. Now let v ∈ M_{K}^{∞}. From Inequality (1.2) we obtain

log |λ|_{v} ≤ m(σ_{v}(Q)) ≤ m(σ_{v}(Q); S_{n+1}^{r}) + r (∑_{i=1}^{n} 1/2 i) (d deg V − deg W)

since Q has degree d deg V − deg W in each group of variables. Then

h_{v}(W) = m(σ_{v}(Ch_{W}); S_{n+1}^{r}) + r (∑_{i=1}^{n} 1/2 i) deg W

= m(σ_{v}(Ch_{d,V} (f)); S_{n+1}^{r}) + r (∑_{i=1}^{n} 1/2 i) d deg V

− m(σ_{v}(Q); S_{n+1}^{r}) − r (∑_{i=1}^{n} 1/2 i) (d deg V − deg W)

≤ d h_{v}(V) + h_{v}(f) deg V + log(n + 1) d deg V − log |λ|_{v}.

by straightforward application of Lemma 2.1. The case v ∉ M_{K}^{∞} follows in an analogous way. □

This result can be immediately generalized to families of polynomials:

Corollary 2.8 Let V ⊂ IA^{n} be an equidimensional variety of dimension r defined over K. Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials which form a complete intersection in V . We assume that V ∩ V (f_{1}, …, f_{i}) satisfies Assumption 1.5 for i = 0, …, s. Set d_{i} := deg f_{i}. Then there exists λ ∈ K^{∗} such that

• h_{v}(V ∩ V (f_{1}, …, f_{s})) ≤ ∏_{i} d_{i} (h_{v}(V) + (∑_{i} h_{v}(f_{i})/d_{i}) deg V + s log(n + 1) deg V) − log |λ|_{v}

for v ∈ M_{K}^{∞},

• h_{v}(V ∩V (f_{1}, …, f_{s})) ≤ ∏_{i} d_{i} (h_{v}(V)+(∑_{i} h_{v}(f_{i})/d_{i}) deg V)−log |λ|_{v} for v ∉ M_{K}^{∞}.

Proof.– We just consider the case when v is archimedean, as the other one follows similarly. From the preceding result we obtain

h_{v}(V ∩ V (f_{1}, …, f_{i})) ≤ d_{i} h_{v}(V ∩ V (f_{1}, …, f_{i−1})) + h_{v}(f_{i}) deg(V ∩ V (f_{1}, …, f_{i−1}))
+ log(n + 1) d_{i} deg(V ∩ V (f_{1}, …, f_{i−1})) − log |λ_{i}|_{v}

for some λ_{i} ∈ K^{∗}. For the final estimate we apply iteratively this inequality and we set λ := ∏_{i=1}^{s} λ_{i}^{d_{i+1}···d_{s}}. □

Corollary 2.9 Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials which form a complete intersection in IA^{n}. We assume that V (f_{1}, …, f_{i}) satisfies Assumption 1.5 for i = 1, …, s. Set d_{i} := deg f_{i}. Then there exists λ ∈ K^{∗} such that:

• h_{v}(V (f_{1}, …, f_{s})) ≤ ∏_{i} d_{i} (∑_{i} h_{v}(f_{i})/d_{i} +(n+s) log(n+1))−log |λ|_{v} for v ∈ M_{K}^{∞},

• h_{v}(V (f_{1}, …, f_{s})) ≤ ∏_{i} d_{i} (∑_{i} h_{v}(f_{i})/d_{i}) − log |λ|_{v} for v ∉ M_{K}^{∞}.

Proof.– We apply the previous result to V := IA^{n}, using the fact that

h_{∞}(IA^{n}) = ∑_{i=1}^{n} ∑_{j=1}^{i} 1/2 j ≤ n log(n + 1)  ,  h_{p}(IA^{n}) = 0.
□

The following global result is the arithmetic analogue of [21, Prop. 2.3]:

Corollary 2.10 Let V ⊂ IA^{n} be a variety of dimension r, and let f_{1}, …, f_{s} ∈ \overline{Q}[x_{1}, …, x_{n}] . Set d_{i} := deg f_{i}, h := h(f_{1}, …, f_{s}) and n_{0} := min{r, s}. We assume that d_{1} ≥ … ≥ d_{s} holds. Then:

h(V ∩ V (f_{1}, …, f_{s})) ≤ ∏_{i=1}^{n_{0}} d_{i} (h(V) + (∑_{i=1}^{n_{0}} 1/d_{i}) h deg V + n_{0} log(n + 1) deg V).

Proof.– We proceed by induction on (r, s) with respect to the product order of IN × IN . The cases r = 0 or s = 0 are both trivial. Thus we assume r, s ≥ 1 . Let V = ∪_{C} C be the decomposition of V into irreducible components. In case C ⊂ V (f_{s}) we have that C ∩ V (f_{1}, …, f_{s}) = C ∩ V (f_{1}, …, f_{s−1}) and so

h(C ∩ V (f_{1}, …, f_{s})) ≤ ∏_{i=1}^{m_{0}} d_{i} (h(C) + (∑_{i=1}^{m_{0}} 1/d_{i}) h deg C + m_{0} log(n + 1) deg C)

with m_{0} := min{r, s − 1}. In case C ⊄ V (f_{s}) we have either C ∩ V (f_{s}) = ∅ or dim C ∩ V (f_{s}) ≤ r − 1 . The first case is trivial. In the second case we have

h(C ∩ V (f_{s})) ≤ d_{s} h(C) + h deg C + log(n + 1) d deg C.

To obtain this, we proceed as in the proof of Proposition 2.7, applying Remark 2.3 instead of Lemma 2.1. Then we apply the inductive hypothesis and we obtain

h(C ∩ V (f_{1}, …, f_{s})) ≤ ∏_{i=1}^{n_{0}−1} d_{i} (h(C ∩ V (f_{s})) + ( ∑_{i=1}^{n_{0}−1} 1/d_{i}) h deg(C ∩ V (f_{s}))
+(n_{0} − 1) log(n + 1) deg(C ∩ V (f_{s})))
≤ ∏_{i=1}^{n_{0}} d_{i} (h(C) + (∑_{i=1}^{n_{0}} 1/d_{i}) h deg C + n_{0} log(n + 1) deg C).
□

With the same notations than Corollary 2.10, for V := IA^{n} we obtain

h(V (f_{1}, …, f_{s})) ≤ ∏_{i=1}^{n_{0}} d_{i} ((∑_{i=1}^{n_{0}} 1/d_{i}) h + (n + n_{0}) log(n + 1)).

2.2.3 An arithmetic Bernstein-Kushnirenko theorem

From our estimate for the height of an affine toric variety (Proposition 1.7) and the previous results of this section we derive the following arithmetic version of the Bernstein-Kushnirenko theorem. We refer to Subsection 1.2.5 for the notation.

Proposition 2.11 Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] , and let A ⊂ (ZZ_{≥0})^{n} be a finite set such that Supp(1, x_{1}, …, x_{n}, f_{1}, …, f_{s}) ⊂ A. Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Then

• deg V (f_{1}, …, f_{s}) ≤ Vol(A) ,

• h(V (f_{1}, …, f_{s})) ≤ (n h + 2^{2 n+3} log(n + 1) d) Vol(A) .

Proof.– Set A := {α_{1}, …, α_{N}}. The case N = 1 is trivial, and so we assume N ≥ 2 . We also assume that α_{1}, …, α_{n} are the vectors of the canonical basis of IR^{n}. The map φ_{A} : IA^{n} → IA^{N} induces an isomorphism between IA^{n} and the affine toric variety X_{A} ⊂ IA^{N} . The projection map π_{A} : IA^{N} → IA^{n} defined by y ↦ (y_{1}, …, y_{n}) restricted to X_{A} is the inverse map of φ_{A}. For i = 1, …, s we set f_{i} = ∑_{j=1}^{N} a_{i j} x^{α_{j}} and we let

ℓ_{i} := ∑_{j=1}^{N} a_{i j} y_{j} ∈ K[y_{1}, …, y_{N}]

be the associated linear form. Set V := V (f_{1}, …, f_{s}) ⊂ IA^{n} and W := X_{A}∩V (ℓ_{1}, …, ℓ_{s}) ⊂ IA^{N} . We have φ_{A}(V) = W and so V = π_{A}(W) . Then

deg V ≤ deg W ≤ deg X_{A} = Vol(A)

and

h(V) ≤ h(W) + 3 (n + 1) log(N + 1) deg W
≤ h(X_{A}) + n h deg(X_{A}) + 4 (n + 1) log(N + 1) deg(X_{A})
≤ (n h + (2^{2 n+2} log N + 4 (n + 1) log(N + 1)) Vol(A).

by successive application of Lemma 2.5, Corollary 2.10 and Proposition 1.7. Finally N ≤ \binom{d+n}{n} and so h(V) ≤ (n h + 2^{2 n+3} log(n + 1) d) Vol(A) . □

It seems that the factor 2^{2 n} in the estimate of h(X_{A}) is superfluous. If this is the case, the above estimate can be considerably improved. We remark that Maillot has recently obtained a much more precise estimate for the height of the isolated points of V (f_{1}, …, f_{s}) [39, Th. 8.48] .

2.3 Local height of norms and traces

Let V ⊂ IA^{n} be an equidimensional variety of dimension r and degree D defined over a field k which satisfies Assumption 1.5. As we will see below, this implies that the projection π_{V} : V → IA^{r} defined by x ↦ (x_{1}, …, x_{r}) is finite (Lemma 2.13). Set L := k(IA^{r}) and M := L ⊗_{k[IA^{r}]} k[V] , so that M is a finite L -algebra of dimension D.

Let f ∈ k[x_{1}, …, x_{n}] . We identify \overline{f} ∈ k[V] with the multiplication map M → M defined by q ↦ f q. The characteristic polynomial X_{f} ∈ L[t] of f is then defined as the characteristic polynomial of this L -linear map. The fact that the inclusion π_{V}^{∗} : k[IA^{r}] ↪ k[V] is integral implies that this polynomial lies in k[IA^{r}][t] , and we have X_{f}(\overline{f}) = 0 in k[V] . Set X_{f} = t^{D} + b_{D−1} t^{D−1} + ⋯ + b_{0} ∈ k[IA^{r}][t] . Then the norm N_{V} (f) and the trace Tr_{V} (f) of f are defined as

N_{V} (f) := (−1)^{D} b_{0} ∈ k[IA^{r}]  ,  Tr_{V} (f) := −b_{D−1} ∈ k[IA^{r}].

They equal the determinant and the trace of the L -linear map \overline{f} : M → M respectively. We also define the adjoint polynomial f^{∗} of f as

f^{∗} := (−1)^{D−1} (f^{D−1} + b_{D−1} f^{D−2} + ⋯ + b_{1}) ∈ k[x_{1}, …, x_{n}].

We have \overline{f^{∗}}\overline{f} = N_{V} (f) in k[V] .

The key result of this subsection is a precise bound for the height of the norm and the trace of a polynomial in case k is a number field.

2.3.1 Characteristic polynomials

Let V ⊂ IA^{n} be an equidimensional variety of dimension r and degree D defined over k. We keep notations as in Subsection 2.1.1: for d ∈ IN we denote by F := ∑_{|α|≤d} U(d)_{0 α} x^{α} and L_{i} := U_{i 0} +U_{i 1} x_{1} +⋯+U_{i n} x_{n} the generic polynomial of degree d and 1 associated to the group of variables U(d)_{0} and U_{i} respectively. As before, we set U(d) := \{U(d)_{0}, U_{1}, …, U_{r}\} and N := \binom{d+n}{n} + r (n + 1) . Also we introduce an additional group T := {T_{0}, …, T_{r}} of r + 1 variables which correspond to the coordinate functions of IA^{r+1} . We consider the map

ψ : IA^{N} × IA^{n} → IA^{N} × IA^{r+1}

given by

(U(d), x) ↦ (ν(d), F (ν(d)_{0})(ξ), L_{1}(ν_{1})(ξ), …, L_{r}(ν_{r})(ξ)).

where ν(d) := (ν(d)_{0}, ν_{1}, …, ν_{r}) ∈ IA^{N} and ξ ∈ IA^{n}. Then the Zariski closure \overline{ψ(IA^{N} × V)} ⊂ IA^{N} × IA^{r+1} is a hypersurface, and any of its defining equations P_{d,V} ∈ k[U(d)][T] is called a d -characteristic polynomial of V . Also we define the characteristic polynomial of V by P_{V} := P_{1,V} . A d -characteristic polynomial is uniquely defined up to a scalar factor. In case V is an irreducible variety, P_{d,V} is an irreducible polynomial. When V is equidimensional, it coincides with the product of d -characteristic polynomials of its irreducible components.

The following construction links the characteristic polynomial of a variety with its generalized Chow form. Set

ζ(d)_{0α} := \{ \begin{matrix}U(d)_{00} − T_{0} & for α = 0 \\ U(d)_{0α} & for α ≠ 0. \end{matrix}

Analogously, for i = 1, …, r we set ζ_{i 0} := U_{i 0} − T_{i} and ζ_{i j} := U_{i j} for j ≠ 0 . Finally we set ζ(d) := (ζ(d)_{0}, ζ_{1}, …, ζ_{r}) .

Lemma 2.12 Let V ⊂ IA^{n} be an equidimensional variety of dimension r and degree D. Let f_{d,V} be a d -Chow form of V . Then f_{d,V} ∘ ζ(d) is a d -characteristic polynomial of V .

Proof.– It is enough to consider the case when V is irreducible. Let P_{d,V} be a d -characteristic polynomial of V . For (ν(d), ξ) ∈ IA^{N} × V we set

ϑ := (F (ν(d)_{0})(ξ), L_{1}(ν_{1})(ξ), …, L_{r}(ν_{r})(ξ)) ∈ IA^{r+1},

so that P_{d,V} (ν(d))(ϑ) = 0 . We observe that

ξ ∈ V ∩ {F (ν(d)_{0})(x) = ϑ_{0}} ∩ {L_{1}(ν_{1})(x) = ϑ_{1}} ∩ ⋯ ∩ {L_{r}(ν_{r})(x) = ϑ_{r})} ⊂ IA^{n}.

In particular, this variety is non-empty, and so we infer that f_{d,V} ∘ ζ(d)(ν(d), ϑ) = 0 . This implies that P_{d,V} |f_{d,V} ∘ ζ(d) as P_{d,V} is an irreducible polynomial. On the other hand f_{d,V} ∘ ζ(d) is also irreducible, as it is multihomogeneous and f_{d,V} ∘ ζ(d)(U(d), 0) = f_{d,V} (U(d)) . We conclude that P_{d,V} and f_{d,V} ∘ζ(d) coincide up to a factor in k^{∗}. □

The previous construction shows that a d -characteristic polynomial of V is multihomogeneous of degree D in the group of variables U(d)_{0} ∪ {T_{0}} and of degree d D in each group U_{i} ∪ {T_{i}}.

Set k_{d} := \overline{k(U(d))} , and set

ϕ : IA^{n}(k_{d}) → IA^{r+1}(k_{d})  ,  x ↦ (F (x), L_{1}(x), …, L_{r}(x)).

Then P_{d,V} ∈ k_{d}[T] is also a minimal equation for the hypersurface \overline{ϕ(V)} , and by Bézout inequality we have also deg_{T} P_{d,V} ≤ d D (see e.g. [47]).

We assume from now on that V satisfies Assumption 1.5, that is #π_{V}^{−1}(0) = deg V . In order to avoid the indeterminacy of the d -characteristic polynomial, we fix it as

P_{d,V} := (−1)^{D} Ch_{d,V} ∘ ζ(d).

In particular, we set P_{V} := (−1)^{D} Ch_{V} ∘ ζ(1) for the characteristic polynomial of V . Set P_{V} := a_{D} T_{0}^{D} + ⋯ + a_{0} for the expansion of P_{V} with respect to T_{0} . We have that P_{V} is multihomogeneous of degree D in each group U_{i} ∪ {T_{i}}. This implies that a_{D} lies in fact in k[U_{1}, …, U_{r}] and is multihomogeneous of degree D in each U_{i} for i = 1, …, r.

Moreover, a_{D} coincides with the coefficient of U_{00}^{D} in Ch_{V} , and the imposed normalization on Ch_{V} implies that

a_{D}(e_{1}, …, e_{r}) = Ch_{V} (e_{0}, e_{1}, …, e_{r}) = 1.

We extend the morphism ϱ_{d} of Subsection 2.1.1 to a morphism k[U(d)][T] → k[U_{0}, …, U_{r}][T] defining ϱ_{d}(U(d)_{00} − T_{0}) := (U_{00} − T_{0})^{d} and ϱ_{d}(T_{i}) := T_{i}. In other terms

ϱ_{d}(T_{0}) = ∑_{j=1}^{d}(−1)^{j−1} \binom{d}{j} U_{0 0}^{d−j} T_{0}^{j}.

From the previous lemma we obtain

ϱ_{d}(P_{d,V}) = ϱ_{d}((−1)^{D}Ch_{d,V} ∘ ζ(d)) = (−1)^{D}(Ch_{V} ∘ ζ(1))^{d} = (−1)^{(d+1)D}P_{V}^{d} .

Now set

P_{d,V} = a_{d,D} T_{0}^{D} + ⋯ + a_{d,0}

for the expansion of P_{d,V} with respect to T_{0} . The previous remark implies that a_{d,D} = ϱ_{d}(a_{d,D}) = a_{D}^{d}. In particular a_{d,D} ∈ k[U_{1}, …, U_{r}] and a_{d,D}(e_{1}, …, e_{r}) = 1 .

The following lemma allows us to obtain a characteristic polynomial of f ∈ k[x_{1}, …, x_{n}] from the d -characteristic polynomial of the variety V . We introduce the following convention: Given a polynomial f ∈ k[x_{1}, …, x_{n}] of degree d and linear forms ℓ_{1}, …, ℓ_{r} ∈ k[x_{1}, …, x_{n}] , we denote by P_{d,V} (f, ℓ_{1}, …, ℓ_{r}) the specialization of the variables in U(d) into the coefficients of f, ℓ_{1}, …, ℓ_{r}.

Lemma 2.13 Let V ⊂ IA^{n} be an equidimensional variety of dimension r and degree D which satisfies Assumption 1.5. Then the projection π_{V} : V → IA^{r} is finite. Moreover, for a polynomial f ∈ k[x_{1}, …, x_{n}] of degree d, the characteristic polynomial of f is given by

X_{f} = P_{d,V} (f, e_{1}, …, e_{r})(t, x_{1}, …, x_{r}) ∈ k[IA^{r}][t].

Proof.– We have that P_{V} (U_{0}, …, U_{r})(L_{0}, …, L_{r}) = 0 in k[U] ⊗ k[V] and so

P_{V} (e_{j}, e_{1}, …, e_{r})(t, x_{1}, …, x_{r}) ∈ k[IA^{r}][t]

is a monic equation for x_{j} in k[V] , for j = r + 1, …, n. Thus the projection π_{V} is finite. For the second assertion, set

P_{F} (t) := P_{d,V} (U(d)_{0}, e_{1}, …, e_{r})(t, x_{1}, …, x_{r}) ∈ k[U(d)_{0}][IA^{r}][t].

This is a polynomial of degree D. It is monic with respect to t, as a_{d,D} ∈ k[U_{1}, …, U_{r}] and a_{d,D}(e_{1}, …, e_{r}) = 1 . We have P_{F} (F) = 0 in k[U(d)_{0}] ⊗ k[V] .

Now let m_{F} be the monic minimal polynomial of F . Let U′(d)_{0} be a group of \binom{d+n−r}{n−r} variables and set F_{0} for the generic polynomial of degree d in the variables x_{r+1}, …, x_{n}.

Then

m_{F} (U′(d)_{0}, 0) ∈ k[U′(d)_{0}][t]

is an equation for F_{0} over π_{V}^{−1}(0) . Since π_{V}^{−1}(0) is a 0-dimensional variety of degree D and F_{0} separates its points, we infer that deg_{T_{0}} m_{F} = D, and so P_{F} = m_{F} . Finally we obtain

X_{f} = X_{F} (f) = P_{F} (f) = P_{d,V} (f, e_{1}, …, e_{r})(t, x_{1}, …, x_{r}).
□

2.3.2 Estimates for norms and traces

Finally we prove the announced estimates for the height of the norm and the trace of a polynomial.

Lemma 2.14 Let V ⊂ IA^{n} be an equidimensional variety of dimension r defined over K which satisfies Assumption 1.5. Let f ∈ K[x_{1}, …, x_{n}] . Then

• deg N_{V} (f) ≤ deg f deg V ,

• h_{v}(N_{V} (f)) ≤ deg f h_{v}(V) + h_{v}(f) deg V + (r + 1) log(n + 1) deg f deg V for v ∈ M_{K}^{∞},

• h_{v}(N_{V} (f)) ≤ deg f h_{v}(V) + h_{v}(f) deg V for v ∉ M_{K}^{∞}.

Proof.– We keep notations as in Subsection 2.3.1. Set d := deg f and D := deg V . We have then

N(f) = (−1)^{D} P_{d,V} (f, e_{1}, …, e_{r})(0, x_{1}, …, x_{r}) = Ch_{d,V} (f, e_{1} − e_{0} x_{1}, …, e_{r} − e_{0} x_{r})

by Lemmas 2.13 and 2.12. Then

deg N(f) ≤ deg_{T} P_{d,V} ≤ d D.

From the previous expression we also obtain that the coefficients of N(f) are some of the coefficients of Ch_{d,V} (f) , and so |N(f)|_{v} ≤ |Ch_{d,V} (f)|_{v} for every absolute value v of K. Let v ∈ M_{K}^{∞}. Then

log |N(f)|_{v} ≤ log |Ch_{d,V} (f))|_{v}
≤ m(σ_{v}(Ch_{d,V} (f)); S_{n+1}^{r}) + r (∑_{i=1}^{n} 1/2 i) d D + r log(n + 1) d D
≤ d h_{v}(V) + h_{v}(f) D + (r + 1) log(n + 1)d D

by Inequalities (1.1) and (1.2), and Lemma 2.1. In a similar way we obtain

h_{v}(N(f)) ≤ d h_{v}(V) + h_{v}(f) D

for v ∉ M_{K}^{∞}. □

The proof of the following lemma follows closely that of [47, Lem. 9]. We slightly improve the degree estimate obtained therein, and we get the corresponding height estimate.

Lemma 2.15 Let V ∈ IA^{n} be an equidimensional variety of dimension r defined over K which satisfies Assumption 1.5. Let f, g ∈ K[x_{1}, …, x_{n}] such that \overline{f} is not a zero-divisor in K[V] . Set d := max{deg f, deg g} and h_{v} := max{h_{v}(f), h_{v}(g)} for v ∈ M_{K}. Then

• deg Tr_{V} (f^{∗}g) ≤ d deg V ,

• h_{v}(Tr_{V} (f^{∗}g)) ≤ d h_{v}(V) + (h_{v} + log 2) deg V + (r + 1) log(n + 1) d deg V for v ∈ M_{K}^{∞},

• h_{v}(Tr_{V} (f^{∗}g)) ≤ d h_{v}(V) + h_{v} deg V for v ∉ M_{K}^{∞}.

Proof.– Let D := deg V , and let t be a new variable. Then K[x_{1}, …, x_{r}, t] ↪ K[V ×IA^{1}] is again an integral inclusion. Set Q(t) := N_{V ×IA^{1}}(t f − g) ∈ K[x_{1}, …, x_{r}, t] . We have then N(t − f^{∗}g) = X_{f^{∗}g}(t) and so

N_{V} (f)^{D−1} Q = N_{V} (f^{∗}) Q = X_{f^{∗}g}(N_{V} (f)t).

Set Q = c_{D} t^{D} + ⋯ + c_{0} with c_{i} ∈ K[IA^{r}] . The last identity implies then Tr(f^{∗}g) = −c_{D−1} . Set q > D, and let G_{q} denote the group of q -roots of 1. Then Q(ω) = N_{V} (ω f − g) for ω ∈ G_{q}, and so

Tr(f^{∗}g) = −\frac{1}{q} ∑_{ω∈G_{q}} N_{V} (ω f − g) ω^{1−D}.

From Lemma 2.14 we get deg Tr(f^{∗}g) ≤ d D. For v ∈ M_{K}^{∞}, we then obtain

h_{v}(Tr(f^{∗}g)) ≤ max_{ω∈G_{q}} h_{v}(N_{V} (ω f − g)) ≤ d h_{v}(V) + (h_{v} + log 2) D + (r + 1) log(n + 1) d D.

Analogously, for v ∉ M_{K}^{∞} we take q > D such that |q|_{v} = 1 , and we obtain h_{v}(Tr(f^{∗}g)) ≤ d h_{v}(V) + h_{v} D. □

3 An effective arithmetic Nullstellensatz

In this chapter we obtain the announced estimates for the arithmetic Nullstellensatz over the ring of integers of a number field K. Theorem 1 of Introduction corresponds to the case K := Q . These estimates depend on the number of variables and on the degree and height of the input polynomials.

3.1 Division modulo complete intersection ideals

The tool we will use here is Tate trace formula, which has already been used in several papers on elimination theory. One of its outstanding features is that it performs effective division modulo complete intersection ideals [17], [12], [29], [47], [15], [19]. In this section we apply trace formula to obtain sharp height estimates in the division procedure.

3.1.1 Tate trace formula

We describe in what follows the basic aspects of duality theory for complete intersection algebras that we will need in the sequel. We refer to Kunz [31, Appendix F] for a complete presentation of this theory. Let k be a perfect field, and set A := k[t_{1}, …, t_{r}] and A[x] := A[x_{1}, …, x_{n}] . Let F := {F_{1}, …, F_{n}} ⊂ A[x] be a reduced complete intersection which defines a radical ideal (F) of dimension r. We consider the A -algebra

B := A[x]/(F) = A[x_{1}, …, x_{n}]/(F_{1}, …, F_{n}).

We assume that the inclusion A ↪ B is finite, that is the variables t_{1}, …, t_{r} are in Noether normal position with respect to the variety V := V (F) ⊂ IA^{r+n}. This is the case, for instance, if V satisfies Assumption 1.5. Thus B is a projective A -module, which turns to be free of rank bounded by deg V by Quillen-Suslin theorem. The dual A -module B^{∗} := Hom_{A}(B, A) can be seen as a B -module with scalar multiplication defined by f · τ(g) := τ(f g) for f, g ∈ B and τ ∈ B^{∗}. It is a free B -module of rank 1 and any of its generators is called a trace of B. The following construction yields a trace σ canonically associated to the complete intersection F . We take new variables y := {y_{1}, …, y_{n}}, and we set F_{i}^{(x)} := F_{i}(x) ∈ A[x] and F_{i}^{(y)} := F_{i}(y) ∈ A[y] . Then F_{i}^{(y)} − F_{i}^{(x)} belongs to the ideal (y_{1} − x_{1}, …, y_{n} − x_{n}) and so there exist (not unique) l_{ij} ∈ A[x, y] such that

F_{i}^{(y)} − F_{i}^{(x)} = ∑_{j=1}^{n} l_{ij}(y_{j} − x_{j}),

for i = 1, …, n. We consider the determinant Δ ∈ A[x, y] of the square matrix (l_{ij})_{ij}, and we write it as

Δ = ∑_{m} a_{m} b_{m}

with a_{m} ∈ A[x] and b_{m} ∈ A[y] . Again, the polynomials a_{m}, b_{m} are not uniquely defined. The polynomial Δ ∈ A[x, y] is called a pseudo-Jacobian determinant of the complete intersection F . Set c_{m} := b_{m}(x) ∈ A[x] . Then there exists a unique trace σ ∈ B^{∗} such that for g ∈ A[x]

\overline{g} = ∑_{m} σ(\overline{g} \overline{a}_{m}) \overline{c}_{m}

where the bar denotes class modulo (F) . This is what is known as Tate trace formula. Let J := det(∂F_{i}/∂x_{j})_{i j} be the Jacobian determinant of the complete intersection F with respect to the variables x_{1}, …, x_{n}. Then the following identity —which justifies the name of pseudo-Jacobian for Δ — holds

\overline{J} = ∑_{m} \overline{a}_{m} \overline{c}_{m}.

The standard trace Tr_{V} is related to σ by the equality

Tr_{V} (\overline{g}) = σ(\overline{J} \overline{g})

for all g ∈ A[x] .

3.1.2 A division lemma

Throughout this subsection we keep notations and assumptions as in the previous one. In addition we replace k by a number field K. We will choose concrete polynomials a_{m}, c_{m} which satisfy trace formula and we will estimate their degree and local height. Set d := max_{i} deg F_{i} and h_{v} := max_{i} h_{v}(F_{i}) for v ∈ M_{K}. First we choose the polynomials l_{ij}. Remarking that

F_{i}^{(y)} − F_{i}^{(x)} = ∑_{j=1}^{n} F_{i}(x_{1}, …, x_{j−1}, y_{j}, …, y_{n}) − F_{i}(x_{1}, …, x_{j}, y_{j+1}, …, y_{n}),

we set

l_{ij} := (F_{i}(x_{1}, …, x_{j−1}, y_{j}, …, y_{n}) − F_{i}(x_{1}, …, x_{j}, y_{j+1}, …, y_{n}))/(y_{j} − x_{j})

Here we perform the division through the formula

(y_{j}^{k} − x_{j}^{k})/(y_{j} − x_{j}) = y_{j}^{k−1} + y_{j}^{k−2} x_{j} + ⋯ + y_{j} x_{j}^{k−2} + x_{j}^{k−1}.

We set Δ := det(l_{ij})_{ij}. Finally we choose b_{m} ∈ A[y] as the monomials in the expansion of Δ with respect to y, a_{m} ∈ A[x] as the corresponding coefficient, and we set c_{m} := b_{m}(x) . Set F_{i} = ∑_{α} a_{i α} x^{α} with a_{i α} ∈ A. Then

l_{ij} = ∑_{α} a_{i α} x_{1}^{α_{1}} ⋯ x_{j−1}^{α_{j−1}}y_{j+1}^{α_{j+1}} ⋯ y_{n}^{α_{n}}(y_{j}^{α_{j}−1} + ⋯ + x_{j}^{α_{j}−1}) ∈ A[x, y].

We deduce that deg l_{ij} ≤ d − 1 and h_{v}(l_{ij}) ≤ h_{v} for every v ∈ M_{K}. Then deg Δ ≤ n (d − 1) and so

deg a_{m} + deg c_{m} ≤ n (d − 1).

We have also h_{v}(c_{m}) = 0 and h_{v}(a_{m}) ≤ h_{v}(Δ) . Finally we can write

l_{ij} = C_{0} + ⋯ + C_{d−1} y_{j}^{d−1},

where each C_{k} ∈ A[x_{1}, …, x_{j}, y_{j+1}, …, y_{n}] is a polynomial in n + r variables of degree bounded by d − 1 . This implies that the number of monomials of l_{ij} is bounded by d \binom{n+r+d−1}{n+r} ≤ d (n + r + 1)^{d−1} . Therefore, for v ∈ M_{K}^{∞} we have

h_{v}(a_{m}) ≤ h_{v}(Δ)
≤ n h_{v} + (n − 1) (log d + (d − 1) log(n + r + 1)) + n log n
≤ n (h_{v} + d log(n + r + 1) + log d).  (3.1)

Analogously we have h_{v}(a_{m}) ≤ n h_{v} for v ∉ M_{K}^{∞}.

The following is a sharp estimate for the degree and the local height of the polynomials in the division procedure. It is a substantial improvement over [29, Thm. 29]. We introduce the notation deg_{t} f and deg_{x} f for the degree of a polynomial f ∈ A[x] with respect to the group of variables t and x, respectively.

Main Lemma 3.1 (Division Lemma) Set A := K[t_{1}, …, t_{r}] and A[x] := A[x_{1}, …, x_{n}] . Let F := {F_{1}, …, F_{n}} ⊂ A[x] be a reduced complete intersection defining a variety V := V (F) ⊂ IA^{r+n} which satisfies Assumption 1.5. Set B := K[V] = A[x]/(F) . Let f, g ∈ A[x] be polynomials such that \overline{f} ∈ B is a non-zero divisor and \overline{f} | \overline{g} in B. Set d := max{deg f, deg F_{1}, …, deg F_{n}} and h_{v} := max{h_{v}(f), h_{v}(F_{1}), …, h_{v}(F_{n})} for v ∈ M_{K}. Then there exist q ∈ A[x] and ξ ∈ K^{∗} such that

• \overline{q} \overline{f} = \overline{g},

• deg_{x} q ≤ n d,

• deg q ≤ deg_{t} g + (n d + max{(n + 1) d, deg_{x} g}) deg V ,

• h_{v}(q) ≤ h_{v}(g) + (n d + max{d, deg_{x} g}) h_{v}(V)

+ ((n + 1) h_{v} + (r + 6) log(n + r + 1) (n d + max{(n + 1) d, deg_{x} g})) deg V

+ 2 log(r + 1) deg_{t} g − log |ξ|_{v}

for v ∈ M_{K}^{∞},

• h_{v}(q) ≤ h_{v}(g) + (n d + max{d, deg_{x} g}) h_{v}(V) + (n + 1) h_{v} deg V − log |ξ|_{v}

for v ∉ M_{K}^{∞}.

Proof.– Set L := K(t_{1}, …, t_{r}) for the quotient field of A and M := L ⊗_{A} B. Then M is a finite L -algebra of dimension deg V and σ can be uniquely extended to a L -linear map σ : M → M . The fact that B is a torsion-free A -algebra implies that the canonical map B → M is an inclusion. We will only consider the case n ≥ 1 . For the case n = 0 we refer to Remark 3.2. Whenever it is clear from the context, we will avoid explicit reference to the ring in which we are considering a given element of A[x] . Let q_{0} ∈ A[x] be any polynomial such that q_{0} f = g in B. We have that f is a nonzero divisor in B, and so it is invertible in M . Then q_{0} = f^{−1} g in M and therefore σ(f^{−1} g p) = σ(q_{0} p) ∈ A for all p ∈ A[x] . Then we set

q := ∑_{m} σ(f^{−1} g a_{m}) c_{m} ∈ A[x].

Tate trace formula implies that q ≡ q_{0} (mod (F)) , and so q f = g in B.

Let J ∈ A[x] denote the Jacobian determinant of the complete intersection F with respect to the group of variables x. This is a non-zero divisor because of the Jacobian criterion, and so it is also invertible in M . Let (J f)^{∗} be the adjoint polynomial of J f and set

Λ_{m} := Tr_{V} ((J f)^{∗}g a_{m}) ∈ A.

We have J f (J f)^{∗} = N(J f) ∈ A \ {0}, and so

Λ_{m}/N(J f) = Tr((J f)^{−1} g a_{m}) = σ(f^{−1} g a_{m}) ∈ A.

In particular N(J f) | Λ_{m} in A, and we have the expression

q = \frac{1}{N(J f)} ∑_{m} Λ_{m} c_{m}.

Clearly

deg_{x} q ≤ max_{m} deg c_{m} ≤ n(d − 1) ≤ n d.

Next we analyze the total degree of q. Let g := ∑_{α} p_{α} x^{α} be the monomial expansion of g with respect to x. Then

Λ_{m} = ∑_{α} p_{α} Tr((Jf)^{∗}x^{α} a_{m}),  (3.2)

as Tr is a A -linear map. We have the estimates deg(J f) ≤ n (d − 1) + d ≤ (n + 1) d and deg(x^{α} a_{m}) ≤ deg_{x} g + deg a_{m}, from where we get

deg Tr((Jf)^{∗}x^{α} a_{m}) ≤ max{(n + 1) d, deg_{x} g + deg a_{m}} deg V

by Lemma 2.15. Thus

deg q ≤ deg_{t} g + max_{m}{max{(n + 1) d, deg_{x} g + deg a_{m}} deg V + deg c_{m}}
≤ deg_{t} g + max_{m}{max{(n + 1) d + deg c_{m}, deg_{x} g + deg a_{m} + deg c_{m}}} deg V
≤ deg_{t} g + max{(n + 1) d + n d, deg_{x} g + n d} deg V
≤ deg_{t} g + (n d + max{(n + 1) d, deg_{x} g}) deg V.

For the rest of the proof, we will use several times the following basic estimates:

max{deg(J f), deg(x^{α} a_{m})} ≤ n d + max{d, deg_{x} g},
deg Tr((Jf)^{∗}x^{α} a_{m}) ≤ (n d + max{d, deg_{x} g}) deg V.

Finally we estimate the local height of q. Let v ∈ M_{K}^{∞}. We have h_{v}(∂F_{i}/∂x_{j}) ≤ h_{v} +log d and so

h_{v}(J) ≤ n (h_{v}+log d)+(n−1) log(n+r+1) (d−1)+n log n ≤ n (h_{v}+log(n+r+1) d+log d).

Therefore

h_{v}(J f) ≤ n(h_{v} + log(n + r + 1) d + log d) + h_{v} + log(n + r + 1) d
≤ (n + 1) h_{v} + (n + 1) log(n + r + 1) d + n log d  (3.3)

by Lemma 1.2(b). We recall that h_{v}(x^{α} a_{m}) ≤ n (h_{v}+log(n+r+1) d+log d) by Inequality (3.1) and so

max{h_{v}(J f), h_{v}(x^{α} a_{m})} ≤ (n + 1) h_{v} + (n + 1) log(n + r + 1) d + n log d.

Then

h_{v}(Tr((J f)^{∗}x^{α}a_{m})) ≤ (n d + max{d, deg_{x} g}) h_{v}(V)
+ ((n + 1)h_{v} + (n + 1) log(n + r + 1) d + n log d + log 2) deg V
+ (r + 1) log(n + r + 1) (n d + max{d, deg_{x} g}) deg V
≤ (n d + max{d, deg_{x} g}) h_{v}(V)
+((n + 1) h_{v} + ((2 n + 1) log(n + r + 1) d) deg V
+ (r + 1) log(n + r + 1) (n d + max{d, deg_{x} g}) deg V
≤ (n d + max{d, deg_{x} g}) h_{v}(V) + ((n + 1) h_{v} +
+(r + 2) log(n + r + 1) (n d + max{(n + 1) d, deg_{x} g})) deg V

by Lemma 2.15. Hence

h_{v}(Λ_{m}) ≤ max_{α}{h_{v}(p_{α} Tr((J f)^{∗}x^{α}a_{m})} + log(n + 1) deg_{x} g
≤ h_{v}(g) + max_{α}{h_{v}(Tr((J f)^{∗}x^{α}a_{m}))}
+ log(r + 1) (n d + max{d, deg_{x} g}) deg V + log(n + 1) deg_{x} g
≤ h_{v}(g) + (n d + max{d, deg_{x} g})h_{v}(V)

+ ((n + 1) h_{v} + (r + 2) log(n + r + 1) (n d + max{(n + 1) d, deg_{x} g})) deg V

+ log(r + 1) (n d + max{d, deg_{x} g}) deg V + log(n + 1) deg_{x} g
≤ h_{v}(g) + (n d + max{d, deg_{x} g}) h_{v}(V)

+ ((n + 1) h_{v} + (r + 4) log(n + r + 1) (n d + max{(n + 1)d, deg_{x} g})) deg V

by application of Identity (3.2) and Lemma 1.2(b). We have

h_{v}(q) ≤ max_{m} {h_{v}(Λ_{m}/N(J f))}

as each c_{m} is a different monomial in x. Thus it only remains to estimate the local height of each Λ_{m}/N(J f) . Let ξ ∈ K^{∗} be any non-zero coefficient of N(J f) . Then

log |Λ_{m}/N(J f)|_{v} ≤ h_{v}(Λ_{m}) +

2 log(r + 1) (deg_{t} g + (n d + max{d, deg_{x} g}) deg V) − log |N(J f)|_{v}

≤ h_{v}(g) + (n d + max{d, deg_{x} g}) h_{v}(V) + (n + 1) h_{v} deg V
+ (r + 6) log(n + r + 1) (n d + max{(n + 1)d, deg_{x} g}) deg V
+ 2 log(r + 1) deg_{t} g − log |ξ|_{v}  (3.4)

by Lemma 1.2(d) and the fact that log |ξ|_{v} ≤ log |N(J f)|_{v}. From Lemma 2.14 and Inequality (3.3) we obtain

log |ξ|_{v} ≤ h_{v}(N(J f))
≤ (n + 1) d h_{v}(V) + ((n + 1) h_{v} + (n + 1) log(n + r + 1) d + n log d) deg V
+ (r + 1) (n + 1) log(n + r + 1) d deg V
≤ (n + 1) d h_{v}(V)
+((n + 1) h_{v} + (r + 3) (n + 1) log(n + r + 1) d) deg V  (3.5)

This implies that the right hand side of Inequality (3.4) is non-negative. So the inequality also holds for h_{v}(Λ_{m}/N(J f)) , and thus for h_{v}(q) . The case v ∉ M_{K}^{∞} is treated analogously. We remark that the election of ξ is independent of v, and so it can be done uniformly.

□

Remark 3.2 Let notations be as in the previous lemma. In case n = 0 we have the sharper estimates

• deg q ≤ deg g,

• h_{v}(q) ≤ h_{v}(g) + h_{v} + 2 log(r + 1) deg g − log |ξ|_{v} for v ∈ M_{K}^{∞},

• h_{v}(q) ≤ h_{v}(g) + h_{v} − log |ξ|_{v} for v ∉ M_{K}^{∞}.

Here ξ ∈ K^{∗} denotes any non-zero coefficient of f . The local height estimates follow from Lemma 1.2(d) and the fact that h_{v} − log |ξ|_{v} ≥ 0 .

3.2 An effective arithmetic Nullstellensatz

3.2.1 Estimates for the complete intersection case

The following result gives estimates for the degree and local height of polynomials arising in the Nullstellensatz over a number field K in case the input is a reduced weak regular sequence, i.e. when the input is a reduced regular sequence which eventually may have no common zeros in IA^{n}. It is a direct consequence of the division lemma above. These estimates depend mainly on the degree and height of the varieties successively cut out by the input polynomials. They are quite flexible apply to other situations as we will see in Chapter 4.

Lemma 3.3 Let n ≥ 2 and let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n} which form a reduced weak regular sequence. Furthermore assume that for j = 1, …, s − 1 , V_{j} := V (f_{1}, …, f_{j}) satisfies Assumption 1.5. Set d := max_{i}{ deg f_{i}, 2 } and h_{v} := max_{i} h_{v}(f_{i}) for v ∈ M_{K}. Then there exist p_{1}, …, p_{s} ∈ K[x_{1}, …, x_{n}] and ξ ∈ K^{∗} such that

• 1 = p_{1} f_{1} + ⋯ + p_{s} f_{s},

• deg p_{i} ≤ 2 n d (1 + ∑_{j=1}^{min{n,s}−1} deg V_{j}) ,

• h_{v}(p_{i}) ≤ 2 n d ∑_{j=1}^{s−1} h_{v}(V_{j}) + ((n+1) h_{v}+2 n (2 n+5) log(n+1) d) (1+∑_{j=1}^{s−1} deg V_{j})− log |ξ|_{v}

for v ∈ M_{K}^{∞},

• h_{v}(p_{i}) ≤ 2 n d ∑_{j=1}^{s−1} h_{v}(V_{j}) + (n + 1) h_{v} (1 + ∑_{j=1}^{s−1} deg V_{j}) − log |ξ|_{v} for v ∉ M_{K}^{∞}.

Proof.– Set I_{i} := I(V_{i}) = (f_{1}, …, f_{i}) for i = 0, …, s − 1 . Also set A_{i} := K[x_{1}, …, x_{n−i}] and B_{i} := K[V_{i}] = K[x_{1}, …, x_{n}]/I_{i}. The fact that V_{i} satisfies Assumption 1.5 implies that the inclusion A_{i} ↪ B_{i} is integral. We note that the sets of free and dependent variables of B_{i} have cardinality n − i and i respectively. Also the set of dependent variables of B_{j} is contained in that of B_{i} for i ≤ j. For f ∈ K[x_{1}, …, x_{n}] we denote by deg_{x(i)} f the degree of f in the dependent variables x_{n−i+1}, …, x_{n} of B_{i} with respect to the integral inclusion A_{i} ↪ B_{i}. For i ≤ j, the previous observation implies that deg_{x(j)} f ≤ deg_{x(i)} f .

Applying the Division Lemma 3.1, we will construct inductively polynomials p_{1}, …, p_{s}: first we take p_{s} such that

p_{s} f_{s} ≡ 1 (mod I_{s−1}).

For 0 ≤ i ≤ s − 2 we assume that p_{i+2}, …, p_{s} are already constructed and we set

b_{i+1} := 1 − (p_{i+2} f_{i+2} + ⋯ + p_{s} f_{s}).

Then f_{i+1} is a non-zero divisor and f_{i+1} | b_{i+1} in B_{i}. We apply again Division Lemma to obtain p_{i+1} such that

p_{i+1} f_{i+1} ≡ b_{i+1} (mod I_{i}),

Continuing this procedure until i = 0 , we get 1 = p_{1} f_{1} + ⋯ + p_{s} f_{s} in K[x_{1}, …, x_{n}] .

Let us analyze degrees. First we consider the case s ≤ n. Again we proceed by induction. First we have deg_{x(s−1)} p_{s} ≤ (s − 1) d ≤ (n − 1) d and deg p_{s} ≤ (2 s − 1) d deg V_{s−1}. Now let 1 ≤ i ≤ s − 2 . Then deg_{x(i)} p_{i+1} ≤ i d and

deg p_{i+1} ≤ deg b_{i+1} + (i d + max{(i + 1) d, deg_{x(i)} b_{i+1}}) deg V_{i}.

where

deg_{x(i)} b_{i+1} ≤ max_{j≥i+2}{deg_{x(i)} p_{j} + deg f_{j}} ≤ max_{j≥i+2} deg_{x(j−1)} p_{j} + d ≤ s d.

Hence

deg p_{i+1} ≤ max_{j≥i+2} deg p_{j} + d + (s + i) d deg V_{i}
≤ (2 s − 1) d deg V_{s−1} + ∑_{j=i}^{s−2}(d + (s + j) d deg V_{j})
= (s − i − 1) d + ∑_{j=i}^{s−1}(s + j) d deg V_{j}.

For i = 0 we have p_{1} | b_{1} and therefore deg p_{1} ≤ deg b_{1} ≤ max_{j≥2} deg p_{j} + d. Then for all i:

deg p_{i} ≤ (s − 1) d + ∑_{j=1}^{s−1}(s + j) d deg V_{j} ≤ 2 n d (1 + ∑_{j=1}^{s−1} deg V_{j}).

Next we consider the case s = n + 1 . In this case V_{s} is a 0-dimensional variety and so

deg p_{n+1} = deg_{x(n)} p_{n+1} ≤ n d.

Let 1 ≤ i ≤ n − 1 . Then deg_{x(i)} p_{i+1} ≤ i d and

deg p_{i+1} ≤ max_{j≥i+2} deg p_{j} + d + (n + 1 + i) d deg V_{i}
≤ n d + ∑_{j=i}^{n−1}(d + (n + 1 + j) d deg V_{j})
= (2 n − i) d + ∑_{j=i}^{n−1}(n + 1 + j) d deg V_{j}.

We have also deg p_{1} ≤ deg b_{1} ≤ max deg_{j≥2} deg p_{j} + d. We conclude for all i:

deg p_{i} ≤ 2 n d + ∑_{j=1}^{n−1}(n + 1 + j) d deg V_{j} ≤ 2 n d (1 + ∑_{j=1}^{n−1} deg V_{j}).

Finally we estimate the local height of these polynomials. In the rest of the proof we will make repeated use of the following degree bounds:

deg_{x(i−1)} p_{i} ≤ n d,
deg p_{i} ≤ 2 n d (1 + ∑_{j=i−1}^{min{n,s}−1} deg V_{j}).

As usual, we consider only the case v ∈ M_{K}^{∞}, the case v ∉ M_{K}^{∞} can be treated analogously. From Division Lemma we obtain

h_{v}(p_{s}) ≤ s d h_{v}(V_{s−1}) +

+(s h_{v} + (n − (s − 1) + 6) (s + (s − 1)) log(n + 1) d) deg V_{s−1} − log |ξ_{s−1}|_{v} for some ξ_{s−1} ∈ K^{∗}. Let 1 ≤ i ≤ s − 2 and set n_{0} := min{n, s}. Then there exists ξ_{i} ∈ K^{∗} such that

h_{v}(p_{i+1}) ≤ h_{v}(b_{i+1}) + (i d + max{d, deg_{x(i)} b_{i+1}}) h_{v}(V_{i}) + (i + 1) h_{v} deg V_{i}

+ (n − i + 6) log(n + 1) (i d + max{(i + 1) d, deg_{x(i)} b_{i+1}}) deg V_{i}

+ 2 log(n − i + 1) deg b_{i+1} − log |ξ_{i}|_{v}

≤ max_{j≥i+2} h_{v}(p_{j}) + h_{v} + log(n + 1) d + log(s − i)

+(s + i) d h_{v}(V_{i}) + (i + 1) h_{v} deg V_{i} + (n − i + 6) (s + i) log(n + 1) d deg V_{i} +

+2 log(n + 1) (2 n d (1 + ∑_{j=i+1}^{n_{0}−1} deg V_{j}) + d) − log |ξ_{i}|_{v}.

Applying the inductive hypothesis we obtain

h_{v}(p_{i+1}) ≤ s d h_{v}(V_{s−1}) + d ∑_{j=i}^{s−2}(s + j) h_{v}(V_{j}) + (s − i − 1) h_{v} + h_{v} ∑_{j=i}^{s−1}(j + 1) deg V_{j}

+ 4 (s − i − 1) (n + 1) log(n + 1) d + log(n + 1) d ∑_{j=i}^{s−1}(n − j + 6) (s + j) deg V_{j}

+ 4 n log(n + 1) d ∑_{j=i+1}^{n_{0}−1}(j − i) deg V_{j} − ∑_{j=i}^{s−1} log |ξ_{j}|_{v}.

For i = 0 we apply Remark 3.2: there exists ξ_{0} ∈ K^{∗} such that

h_{v}(p_{1}) ≤ h_{v}(b_{1}) + h_{v} + 2 log(n + 1) deg b_{1} − log |ξ_{0}|_{v}
≤ max_{j≥2} h_{v}(p_{j}) + 2 h_{v} + log(n + 1) d + log s + 2 log(n + 1) (2 n d (1 + ∑_{j=1}^{n_{0}−1} deg V_{j}) + d)
− log |ξ_{0}|_{v}.

We set ξ := ∏_{j=0}^{s−1} ξ_{j}. Then

h_{v}(p_{1}) ≤ 2 n d ∑_{j=1}^{s−1} h_{v}(V_{j}) + (n + 1) h_{v} (1 + ∑_{j=1}^{s−1} deg V_{j}) + 4 n (n + 1) log(n + 1) d

+ log(n + 1) d ∑_{j=1}^{s−1}(n − j + 6) (n + 1 + j) deg V_{j} + 4 n log(n + 1) d ∑_{j=1}^{n_{0}−1} j deg V_{j} − log |ξ|_{v}

≤ 2 n d ∑_{j=1}^{s−1} h(V_{j}) + ((n + 1) h_{v} + 2 n (2 n + 5) log(n + 1) d) (1 + ∑_{j=1}^{s−1} deg V_{j}) − log |ξ|_{v}.

This last inequality follows from the facts that 4 n j + (n − j + 6) (j + s) ≤ 2 n (2 n + 5) for j ≤ n − 1, and 6 (2 n + 1) ≤ 2 n (2 n + 5) as n ≥ 2 . To conclude the proof, observe that for i = 1, dots, s − 1 , Inequality 3.5 guarantees that the obtained estimate for p_{i} differs from the one for p_{i+1} by a positive term. Thus, the same estimate holds for h_{v}(p_{i}) , 1 ≤ i ≤ s. □

By means of Bézout inequality, we can now estimate the degree and height of the varieties V_{j}. In this way we obtain an estimate which only depends on the degree and height of the input polynomials.

Corollary 3.4 Let notations and assumptions be as in Lemma 3.3. Then there exist p_{1}, …, p_{s} ∈ K[x_{1}, …, x_{n}] and γ ∈ K^{∗} such that

• 1 = p_{1} f_{1} + ⋯ + p_{s} f_{s},

• deg p_{i} ≤ 4 n d^{n},

• h_{v}(p_{i}) ≤ 4 n (n + 1) d^{n} h_{v} + 4 n (4 n + 5) log(n + 1) d^{n+1} − log |γ|_{v} for v ∈ M_{K}^{∞},

• h_{v}(p_{i}) ≤ 4 n (n + 1) d^{n} h_{v} − log |γ|_{v} for v ∉ M_{K}^{∞}.

Proof.– Let us first consider degrees. We assume without loss of generality d ≥ 2 . From the preceding result we obtain

deg(p_{i}) ≤ 2 n d (1 + ∑_{j=1}^{min{n,s}−1} deg V_{j}) ≤ 2 n d (1 + ⋯ + d^{n−1}) ≤ 4 n d^{n}.

Next we consider the local height estimates. Let v ∈ M_{K}^{∞}. We have

h_{v}(p_{i}) ≤ 2 n d ∑_{j=1}^{s−1} h_{v}(V_{j}) + ((n + 1) h_{v} + 2 n (2 n + 5) log(n + 1)d) (1 + ∑_{j=1}^{s−1} deg V_{j}) − log |ξ|_{v}

for some ξ ∈ K^{∗}. Applying Corollary 2.9, h_{v}(V_{j}) ≤ j d^{j−1} h_{v} + (n + j) log(n + 1) d^{j} − log |λ_{j}|_{v} for some λ_{j} ∈ K^{∗}. Therefore

h_{v}(p_{i}) ≤ 2 n d ∑_{j=1}^{s−1}(j d^{j−1} h_{v} + (n + j) log(n + 1) d^{j} − log |λ_{j}|_{v})

+ ((n + 1) h_{v} + 2 n (2 n + 5) log(n + 1) d) ∑_{j=0}^{n} d^{i} − log |ξ|_{v}

≤ 4 n^{2} d^{n} h_{v} + 8 n^{2} log(n + 1) d^{n+1}

+ 2 (n + 1) d^{n} h_{v} + 4 n (2 n + 5) log(n + 1) d^{n+1} − 2 n d ∑_{j=1}^{s−1} log |λ_{j}|_{v} − log |ξ|_{v}

≤ 4 n (n + 1) d^{n} h_{v} + 4 n (4 n + 5) log(n + 1) d^{n+1} − log |γ|_{v},

where γ ∈ K^{∗} is defined as γ := ξ ∏_{j=1}^{s−1} λ_{j}^{2 n d}. The case v ∉ M_{K}^{∞} follows anagolously. □

3.2.2 Proof of Theorem 1

In order to prove Theorem 1, it only remains to put the case of a general input into the hypothesis of Corollary 3.4. This is accomplished by replacing the input polynomials and variables by generic linear combinations. The coefficients of the linear combinations will be chosen to be roots of 1. Amazingly enough, we will see using next lemma that we don’t need to control the degree of the involved number field extension.

Let L be a finite extension of K, and let B := {e_{1}, …, e_{N}} be a basis of L as a K -linear space. We recall that B^{∗} := {e_{1}^{∗}, …, e_{N}^{∗}} is the dual basis of B if Tr_{K}^{L}(e_{i} e_{j}^{∗}) = 1 for i = j and 0 otherwise.

Lemma 3.5 Let ω ∈ \overline{Q} be a primitive p -root of 1 for some prime p. Then the basis B^{∗} := { (ω^{−j} −ω) / p : j = 0, …, p−2 } of Q(ω) is dual to B := { ω^{i} : i = 0, …, p−2 }.

Proof.– A direct computation shows that for i, j = 0, …, p − 2

Tr(ω^{i} (ω^{−j} − ω)) = ∑_{l=1}^{p−1} ω^{l i} (ω^{−l j} − ω^{l}) = \{ \begin{matrix}p, & for & i = j, \\ 0, & for & i ≠ j. \end{matrix}

□

We will use this result in the following way: let ω be a primitive p -root of 1 and set L := K(ω) . Let us assume that Q(ω) and K are linearly independent and that p does not divide the discriminant of K. Both conditions are satisfied by all but a finite number of p. Then [L : K] = p − 1 and O_{L} = O_{K}[ω] [33, Ch. III, Prop. 17]. Now, let ν ∈ L \ {0}. Then

ν = \frac{1}{p} Tr(ν (1 − ω)) + ⋯ + \frac{1}{p} Tr(ν (ω^{2−p} − ω)) ω^{2−p} ∈ K[ω] \ \{0\}

and so there exists 0 ≤ j ≤ p − 2 such that Tr(ν (ω^{−j} − ω)) / p ∈ K \ {0}. Moreover, if ν ∈ O_{L} \ {0}, as every coefficient belongs to O_{K}, there exists 0 ≤ j ≤ p − 2 such that Tr(ν (ω^{−j} − ω)) / p ∈ O_{K} \ {0}.

Theorem 3.6 (Effective arithmetic Nullstellensatz) Let K be a number field and let f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Then there exist a ∈ O_{K} \ {0} and g_{1}, …, g_{s} ∈ O_{K}[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 4 n d^{n},

• h(a, g_{1}, …, g_{s}) ≤ 4 n (n + 1) d^{n} (h + log s + (n + 7) log(n + 1) d).

The extremal cases n = 1 and d = 1 are treated directly in the following results.

Lemma 3.7 Let ℓ_{1}, …, ℓ_{s} ∈ O_{K}[x_{1}, …, x_{n}] be polynomials of degree bounded by 1 without common zeros in IA^{n}. Set h := h(ℓ_{1}, …, ℓ_{s}) . Then there exist a ∈ O_{K} \ {0} and a_{1}, …, a_{s} ∈ O_{K} such that

• a = a_{1} ℓ_{1} + ⋯ + a_{s} ℓ_{s},

• h(a, a_{1}, …, a_{s}) ≤ (n + 1) (h + log(n + 1)) .

Proof.– Equation a = a_{1} ℓ_{1} + ⋯ + a_{s} ℓ_{s} is equivalent to a O_{K} -linear system of n + 1 equations in s unknowns, which can be solved applying Cramer rule. The integer a is the determinant of a non-singular submatrix of the system. □

Lemma 3.8 Let f_{1}, …, f_{s} ∈ O_{K}[x] be polynomials without common zeros in IA^{1} . Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s})) . Then there exist a ∈ O_{K} \ {0} and g_{1}, …, g_{s} ∈ O_{K}[x] such that

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

• deg g_{i} ≤ d − 1 ,

• h(a, g_{1}, …, g_{s}) ≤ 2 d (h + d) .

Proof.– Let f := ∑_{i} a_{i} f_{i}, g := ∑_{i} b_{i} f_{i} ∈ K[x] be generic linear combinations of f_{1}, …, f_{s}. Then f and g are coprime polynomials, and so there exist p, q ∈ K[x] with deg p < deg g and deg q < deg f such that 1 = p f + q g. Expanding this identity there exists p_{1}, …, p_{s} ∈ K[x] with deg p_{i} ≤ d − 1 such that

1 = p_{1} f_{1} + ⋯ + p_{s} f_{s}.

Thus the above Bézout identity translates to a consistent system of K -linear equations. The number of equations and variables equal 2 d and s d respectively. This system can be solved by Cramer rule. The integer a is the determinant of a non-singular 2 d × 2 d− submatrix of the matrix of the linear system. □

Proof of Theorem 1.– We assume n > 1 and d > 1 . Let G_{p} ⊂ \overline{Q} denote the group of p -roots of 1, for a prime p. For a_{ij} ∈ G_{p} and i = 1, …, min{n + 1, s} we set

q_{i} := a_{i 1} f_{1} + … + a_{i s} f_{s}.

Also, for b_{kl} ∈ G_{p} and k = 1, …, n we set

y_{k} := b_{k 0} + b_{k 1} x_{1} + ⋯ + b_{k n} x_{n}.

We will assume that for a specific choice of p, a_{ij} and b_{kl} there exists t ≤ min{n + 1, s} such that (q_{1}, …, q_{i}) ⊂ K[x_{1}, …, x_{n}] is a radical ideal of dimension n−i for i = 1, …, t−1 and 1 ∈ (q_{1}, …, q_{t}) . We also assume that y_{1}, …, y_{n} is a linear change of variables, and that V_{i} := V (q_{1}, …, q_{i}) ⊂ IA^{n} satisfies Assumption 1.5 for i = 1, …, t − 1 with respect to y_{1}, …, y_{n−i}.

This is guaranteed by the fact that these conditions are generically satisfied: there exists a hypersurface H of the coefficient space such that (a_{i j}, b_{k l}) ∉ H implies that q_{1}, …, q_{s} satisfy the stated conditions with respect to the variables y_{1}, …, y_{n} [17], [47]. As ∪_{p}G_{p} is Zariski dense in IA^{1} , it follows that these coefficients can be chosen to lie in G_{p} for some p. Moreover, p can be chosen such that for ω a primitive p -root of 1 and L := K(ω) , Q(ω) and K are linearly independent and p does not divide the discriminant of K. We refer the reader to Section 4.1, where we give a self-contained treatment of this topic.

Set b := (b_{k 0})_{k} ∈ G_{p}^{n} and B := (b_{k l})_{k,l≥1} ∈ GL_{n}(\overline{Q}) . For j = 1, …, t set

F_{j}(y) := q_{j}(x) = q_{j}(B^{−1}(y − b)) ∈ L[y_{1}, …, y_{n}].

Then F_{1}, …, F_{t} satisfy the hypothesis of Corollary 3.4. Let γ ∈ L^{∗} and P_{1}, …, P_{t} ∈ L[y_{1}, …, y_{n}] be the non-zero element and the polynomials satisfying Bézout identity we obtain there. Now, for i = 1, …, s, set

p_{i} := ∑_{j=1}^{t} a_{i j} P_{j}(B x + b) ∈ L[x_{1}, …, x_{n}]

so that 1 = p_{1} f_{1} + ⋯ + p_{s} f_{s} holds. Finally set μ := (det B)^{4 n (n+1) d^{n+1}} γ ∈ L^{∗} . By Lemma 3.5 there exists 0 ≤ ℓ ≤ p − 2 such that Tr(μ (ω^{−ℓ} − ω)) ≠ 0 . We define

a := Tr(μ (ω^{−ℓ} − ω))/p ∈ K^{∗}  ,  g_{i} := Tr(μ p_{i} (ω^{−ℓ} − ω))/p ∈ K[x_{1}, …, x_{n}]

for i = 1, …, s. Then

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

as f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] and Tr is a K -linear map. Aside from the degree and height bounds, we will show that since f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] , a ∈ O_{K} and g_{i} ∈ O_{K}[x_{1}, …, x_{n}] .

Let us first analyze degrees and local heights. As deg F_{j} ≤ d, deg g_{i} ≤ deg p_{i} ≤ max_{j} deg P_{j} ≤ 4 n d^{n}. Now let v ∈ M_{K}^{∞} and let w ∈ M_{L} such that w | v. We have h_{w}(B^{−1} (y − b)) ≤ n log n − log | det B|_{w} and so

h_{w}(F_{j}) ≤ h_{w}(q_{j}) + (n log n − log | det B|_{w} + 2 log(n + 1)) d
≤ h_{v} + log s + (n + 2) log(n + 1) d − log | det B|_{w} d

by Lemma 1.2(c). From Corollary 3.4

h_{w}(P_{j}) ≤ 4 n (n + 1) d^{n} max_{k} h_{w}(F_{k}) + 4 n (4 n + 5) log(n + 1) d^{n+1} − log |γ|_{w}
≤ 4 n (n + 1) d^{n}(h_{v} + log s + (n + 2) log(n + 1) d − log | det B|_{w} d)
+ 4 n (4 n + 5) log(n + 1) d^{n+1} − log |γ|_{w}
= 4 n (n + 1) d^{n} (h_{v} + log s) + 4 n (n^{2} + 7 n + 7) log(n + 1) d^{n+1} − log |μ|_{w}.

Therefore

h_{w}(μ p_{i}) ≤ max_{j} h_{w}(P_{j}) + 2 log(n + 1) max_{j} deg P_{j} + log t + log |μ|_{w}
≤ 4 n (n + 1) d^{n} (h_{v} + log s) + 4 n (n^{2} + 7 n + 7) log(n + 1) d^{n+1}
+ 8 n log(n + 1) d^{n} + log(n + 1)
≤ 4 n (n + 1) d^{n} (h_{v} + log s + (n + 7) log(n + 1) d) − log 2  (3.6)

again by Lemma 1.2(c) and the fact d, n ≥ 2 . We have

g_{i} = \frac{1}{p} Tr(μ p_{i} (ω^{−ℓ} − ω)) = \frac{1}{p} ∑_{σ∈Gal_{L/K}} σ(μ p_{i} (ω^{−ℓ} − ω))

and so

h_{v}(g_{i}) ≤ max_{w | v} h_{w}(μ p_{i}) + log 2
≤ 4 n (n + 1) d^{n} (h_{v} + log s + (n + 7) log(n + 1) d).

We have h_{w}(μ) ≤ 4 n (n + 1) d^{n} (h_{v} + log s) + 4 n (n^{2} + 7 n + 7) log(n + 1) d^{n+1} and so the previous estimate also holds for h_{v}(a) . Now let v ∉ M_{K}^{∞} and w | v. Analogously we have

h_{w}(μ), h_{v}(μ p_{i}) ≤ 4 n (n + 1) d^{n} h_{v} = 0

as f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] . Then μ ∈ O_{L} \ {0} and μ p_{i} ∈ O_{L}[x_{1}, …, x_{n}] , which in term implies that a ∈ O_{K} \ {0} and g_{i} ∈ O_{K}[x_{1}, …, x_{n}] as desired. The global height estimate follows then from the expression

h(a, g_{1}, …, g_{s}) = \frac{1}{[K : Q]} ∑_{v∈M_{K}^{∞}} N_{v} max\{h_{v}(a), h_{v}(g_{1}), …, h_{v}(g_{s})\}.

□

Remark 3.9 The fact that the bound 3.6 is uniform on w for w | v is the key that allows us to get rid of the roots of 1. This will no longer be the case in our treatment of the more refined arithmetic Nullstellensätze in Chapter 4.

The following example, although not verifying the worst case bound for the degrees, improves the lower bound stated in the introduction for a general height estimate and shows that the term d^{n}h is unavoidable.

Example 3.10 Set

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

for any d, H ∈ IN . These are polynomials without common zeros in IA^{n} of degree and height bounded by d and h := log H respectively. Let a ∈ ZZ \ {0} and g_{1}, …, g_{n+1} ∈ ZZ[x_{1}, …, x_{n}] such that a = g_{1} f_{1} + ⋯ + g_{n+1} f_{n+1} . We evaluate this identity in (H, H^{d}, ⋯, H^{d^{n−1}}) and we obtain

a = g_{n+1}(H, H^{d}, ⋯, H^{d^{n−1}}) H^{d^{n}}

from where we deduce h(a) ≥ d^{n} h.

4 Intrinsic type estimates

Theorem 1 is essentially optimal in the general case. There are however many particular instances in which these estimates can be improved. Consider the following example:

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

for any d, H ∈ IN . These are polynomials without common zeros in IA^{n} of degree and height bounded by d and h := log H respectively. Theorem 1 says there exist a ∈ ZZ \ {0} and g_{1}, …, g_{n+1} ∈ ZZ[x_{1}, …, x_{n}] such that

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

with deg g_{i} ≤ 4 n d^{n} and h(a), h(g_{i}) ≤ 4 n (n + 1) d^{n} (h + (n + 7) log(n + 1) d) . However the following Bézout identity holds:

H − 1 = \frac{x_{1}^{d} − 1}{x_{1} − 1} ⋯ \frac{x_{n}^{d} − 1}{x_{n} − 1} f_{1} + ⋯ + \frac{x_{n}^{d} − 1}{x_{n} − 1} f_{n} + f_{n+1}.

Note that the polynomials arising in this identity have degree and height bounded by n (d − 1) and h respectively. There is in this case an exponential gap between the a priori general estimates and the actual ones. The explanation is somewhat simple: for i = 1, …, n, the varieties

V_{i} := V (f_{1}, …, f_{i}) = V (x_{1} − 1, x_{2} − 1, …, x_{i} − 1) ⊂ IA^{n},

verify deg(V_{i}) = 1 and h(V_{i}) ≤ 2 n log(n + 1) . Namely, both the degree and the height of the varieties successively cut out by the input polynomials are much smaller than the corresponding Bézout estimate. As the varieties V_{i} verify the assumptions of Lemma 3.3, a direct application together with Lemma 1.3 produces the more realistic estimates:

deg g_{i} ≤ 2 n^{2} d , h(a), h(g_{i}) ≤ (n + 1)^{2}(h + 8 n log(n + 1) d).

Based on this idea, we devote this chapter to the study of more refined arithmetic Nullstellensätze which can deal with such situations.

4.1 Equations in general position

This section deals with the preparation of the input data. To apply Lemma 3.3, we need to prepare the polynomials and the variables of the ambient space. Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. For i = 1, …, s and a_{i j} ∈ ZZ we set

q_{i} := a_{i 1} f_{1} + ⋯ + a_{i s} f_{s}.

We will estimate the height of rational integers a_{ij} in order that there exists t ≤ min{n + 1, s} such that (q_{1}, …, q_{i}) ⊂ K[x_{1}, …, x_{n}] is a radical ideal of dimension n − i for i = 1, …, t − 1 and 1 ∈ (q_{1}, …, q_{t}) .

Also we set

y_{k} := b_{k 0} + b_{k 1} x_{1} + ⋯ + b_{k n} x_{n}

for k = 1, …, n and b_{k l} ∈ ZZ . Again we want to estimate the height of rational integers b_{kl} such that V_{i} := V (q_{1}, …, q_{i}) ⊂ IA^{n} satisfies Assumption 1.5 with respect to this set of variables for i = 1, …, t − 1 . Namely, the projection

π_{i} : V_{i} → IA^{n−i}  ,  x ↦ (y_{1}, …, y_{n−i})

must verify #π_{i}^{−1}(0) = deg V_{i}, that is # V_{i} ∩V (y_{1}, ⋯, y_{n−i}) = deg V_{i} for i = 1, …, t−1 . Lemma 2.13 implies that the variables y_{1}, …, y_{n−i} are in Noether normal position with respect to V_{i}. It is well-known that these conditions are satisfied by a generic election of a_{ij} and b_{kl}, see for instance [17], [47]. We have already applied such a preparation to obtain the classic style version of the effective arithmetic Nullstellensatz presented in Theorem 3.6. There, we chose roots of 1 as coefficients of the linear combinations since their existence was sufficient in our proof. However, technical reasons (see Remark 3.9) prevent us to apply the same principle in this chapter, and we need to carry out a more careful analysis. We note that all aspects of this preparation were previously covered in the research papers [2], [17], [29], [19]. However the bounds presented therein are either non-explicit or not precise enough for our purposes. Here we chose to give a self-contained presentation, which yields another proof of the existence of such linear combinations, with good control of the integers height.

4.1.1 An effective Bertini theorem

This subsection concerns the preparation of the polynomials. We will first show some auxiliary results. The following is a version of the so-called shape lemma representation of a 0-dimensional radical ideal. The main difference here is that we choose a generic linear form — instead of a particular one — as a primitive element. For a polynomial f = c_{D} t^{D} + ⋯ + c_{0} ∈ k[t] we denote its discriminant by discr(f) ∈ k. We recall that discr (f) ≠ 0 if and only if c_{D} ≠ 0 and f is squarefree, that is when f has exactly D distinct roots.

Lemma 4.1 (Shape Lemma) Let V ⊂ IA^{n} be a 0-dimensional variety defined over k. Let U := (U_{0}, …, U_{n}) be a group of n + 1 variables, and set L := U_{0} + U_{1} x_{1} + ⋯ + U_{n} x_{n} for the associated generic linear form. Let P := P_{V} ∈ k[U][T] be a characteristic polynomial of V . Set P′ := ∂P/∂T ∈ k[U][T] and ρ := discr_{T} P ∈ k[U] \ {0}. Also set I for the extension of I(V) to k[U][x] . Then there exist v_{1}, …, v_{n} ∈ k[U][T] with deg v_{i} ≤ deg V − 1 such that

I_{ρ} = (P (L), P′(L) x_{1} − v_{1}(L), …, P′(L) x_{n} − v_{n}(L))_{ρ} ⊂ k[U]_{ρ}[x].

Proof.– We note first that I(V) is a radical ideal, and so I = k[U] ⊗_{k} I(V) is also radical. We readily obtain from the definition of P := P_{V} that I ∩ k[U][L] = (P (L)) , and so P (L) ∈ I. We can write P (L) = ∑_{α} a_{α}(x) U^{α} with a_{α}(x) ∈ I(V) . Therefore ∂P (L)/∂U_{i} also lies in I for all i. A direct computation shows that for i = 1, …, n

∂P (L)/∂U_{i} = P′(L) x_{i} − v_{i}(L)

for some v_{i} ∈ k[U][T] with deg v_{i} ≤ deg P − 1 = deg V − 1 . Set

J := (P (L), P′(L) x_{1} − v_{1}(L), …, P′(L) x_{n} − v_{n}(L)) ⊂ k[U][x].

The previous argument shows the inclusion I ⊃ J.

On the other hand, ρ = A P + B P′ for some A, B ∈ k[U][T] . Set w_{i} := B v_{i}. Then x_{i} ≡ w_{i}(L)/ρ (mod J_{ρ}) and so for every f ∈ k[U][x] we have that f ≡ f(U, w_{1}(L)/ρ, …, w_{n}(L)/ρ) modulo J_{ρ}, and hence modulo I_{ρ}. For f ∈ I,

ρ^{deg f} f(U, w_{1}(L)/ρ, …, w_{n}(L)/ρ) ∈ I ∩ k[U][L] = (P (L))

which implies I_{ρ} ⊂ J_{ρ} as desired. □

Let ν ∈ k^{n+1} such that ρ(ν) ≠ 0 . It follows that I(V) can be represented as

I(V) = (P (L), P′(L) x_{1} − v_{1}(L), …, P′(L) x_{n} − v_{n}(L))(ν) ⊂ k[x].

Now let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. For i = 1, …, s we let Z_{i} := (Z_{i1}, …, Z_{is}) denote a group of s variables, and we set

Q_{i} := Z_{i1} f_{1} + ⋯ + Z_{is} f_{s} ∈ k[Z][x]

for the associated generic linear combination of f_{1}, …, f_{s}.

Lemma 4.2 For ℓ = 1, …, s, the ideal (Q_{1}, …, Q_{ℓ}) is a complete intersection prime ideal of k[Z][x] .

Proof.– Set I := (Q_{1}, …, Q_{ℓ}) and V := V (I) ⊂ IA^{sℓ} × IA^{n}. First we observe that V is a linear bundle over IA^{n}: the projection

π : V → IA^{n}  ,  (z, x) ↦ x

is surjective, and the fibers are affine spaces of dimension (s − 1) ℓ. This follows from the assumption that the f_{j} have no common zeros. This implies that

dim V = (s − 1) ℓ + n

because of the theorem of dimension of fibers. Namely Q_{1}, …, Q_{ℓ} is a complete intersection, and in particular the ideal I is unmixed.

Set I = I_{1} ∩ … ∩ I_{m} for the primary decomposition of this ideal. We will show that I_{j} is prime for all j, and then that m = 1 . First we have that I_{f_{j}} = (Q_{1}/f_{j}, …, Q_{ℓ}/f_{j}) = (Z_{1j} + H_{1j}, …, Z_{ℓj} + H_{ℓj}) where H_{ij} ∈ k[Z_{i}][x]_{f_{j}} does not depend on Z_{ij}. Therefore

(k[IA^{sℓ} × IA^{n}]/I)_{f_{j}} ≅ k[IA^{(s−1)ℓ} × IA^{n}]_{f_{j}}

is a domain, that is I_{f_{j}} is prime. We have I_{f_{j}} = (I_{1})_{f_{j}} ∩ … ∩ (I_{m})_{f_{j}} , and so there exists 1 ≤ n(j) ≤ m such that

I_{f_{j}} = (I_{n(j)})_{f_{j}}  ,  V (I_{i}) ⊂ {f_{j} = 0} for i ≠ n(j).

In particular I_{n(j)} = I_{f_{j}} ∩ k[IA^{sℓ} × IA^{n}] is prime. The fact that ∩_{j}{f_{j} = 0} = ∅ ensures that n(j) runs over all 1 ≤ i ≤ m, and so I is radical. The expression I_{f_{j}} = (Z_{1j} +H_{1j}, …, Z_{ℓj} +H_{ℓj}) implies that π(V (I_{f_{j}})) ⊂ IA^{n} contains the dense open set {f_{j} ≠ 0}. In particular V (I_{f_{j}}) is not contained in any of the hypersurfaces {f_{i} = 0} and so n(j) = n(1) for all j. This implies that m = 1 , and so I = I_{1} is prime. □

The following proposition shows that (Q_{1}(a_{1}), …, Q_{ℓ}(a_{ℓ})) is a radical ideal for a generic election of a_{i} := (a_{i1}, …, a_{is}) . Unlike Lemmas 4.1 and 4.2, this result does note hold for arbitrary characteristic. For instance, let x^{p}, 1 − x^{p} ∈ IF_{p}[x] for some prime p. Then Q_{1}(a_{1}) = b + c x^{p} for some b, c ∈ \overline{IF_{p}} and so

Q_{1}(a_{1}) = (b^{1/p} + c^{1/p} x)^{p}

is not squarefree.

Proposition 4.3 Let char (k) = 0 and set I := (Q_{1}, …, Q_{ℓ}) ⊂ k[Z][x] .

• In case I ∩ k[Z] ≠ {0} there exists F ∈ k[Z] \ {0} with deg F ≤ (d + 1)^{ℓ} such that F (a_{1}, …, a_{ℓ}) ≠ 0 for a_{1}, …, a_{ℓ} ∈ k^{s} implies that 1 ∈ (Q_{1}(a_{1}), …, Q_{ℓ}(a_{ℓ})) .

• In case I ∩ k[Z] = {0} there exists F ∈ k[Z] \ {0} with deg F ≤ 2 (d + 1)^{2 ℓ} such that F (a_{1}, …, a_{ℓ}) ≠ 0 for a_{1}, …, a_{ℓ} ∈ k^{s} implies that (Q_{1}(a_{1}), …, Q_{ℓ}(a_{ℓ})) ⊂ k[x] is a radical ideal of dimension n − ℓ.

Proof.– Set V := V (I) ⊂ IA^{sℓ} ×IA^{n}. We have dim V = (s−1) ℓ+n and deg V ≤ (d+1)^{ℓ}.

First we consider the case I ∩ k[Z] ≠ {0}. This occurs, for instance, when ℓ ≥ n + 1 , since then dim I = s ℓ + n − ℓ < dim k[Z] = s ℓ. Let π : IA^{sℓ} × IA^{n} → IA^{sℓ} be the canonical projection. Then \overline{π(V)} is a proper subvariety of IA^{sℓ}, and thus it is contained in a hypersurface of degree bounded by deg V . This can be seen by taking a generic projection of this variety into an affine space of dimension s ℓ + n − ℓ + 1 [20, Remark 4]. Let F ∈ k[Z] be a defining equation of this hypersurface. Then F ∈ I as I is prime, and we have deg F ≤ (d + 1)^{ℓ}. Thus

1 ∈ I_{F} ⊂ k[Z]_{F} [x],

and therefore 1 ∈ I(a) := (Q_{1}(a_{1}), …, Q_{ℓ}(a_{ℓ})) for a ∈ k^{sℓ} such that F (a) ≠ 0 .

Next we consider the case I ∩ k[Z] = {0}. We adopt the following convention: for an ideal J ⊂ k[x] and for ζ any new group of variables, we denote by J^{[ζ]} and J^{(ζ)} the extension of J to the polynomial rings k[ζ][x] and k(ζ)[x] respectively. We assume for the moment ℓ = n. Then dim I = s ℓ and so the extended ideal I^{(Z)} ⊂ k(Z)[x] is a 0-dimensional prime ideal. We have then that \overline{k(Z)} ⊗_{k} I^{(Z)} ⊂ \overline{k(Z)}[x] is a radical ideal, as char (k) = 0 [41, Thm. 26.3]. Our approach to this case is based on Shape Lemma 4.1. We will determine a polynomial F ∈ k[Z] such that F (a) ≠ 0 implies that the shape lemma representation of I^{(Z)} can be transferred to a shape lemma representation of I(a) . Let U be a group of n + 1 variables and set L := U_{0} + U_{1} x_{1} + ⋯ + U_{n} x_{n} for the associated generic linear form. Consider the morphism

Ψ : IA^{n+1} × IA^{sℓ} × IA^{n} → IA^{n+1} × IA^{sℓ} × IA^{1}  ,  (u, z, x) ↦ (u, z, L(x)).

and let W be the variety defined by I in IA^{n+1} × IA^{sℓ} × IA^{n}, that is W = IA^{n+1} × V . The Zariski closure \overline{Ψ(W)} is then an irreducible hypersurface. We set P ∈ k[U, Z][T] for one of its defining equations. If I^{[U](Z)} is the extension of I^{(Z)} to k[U](Z)[x] , the polynomial P can be equivalently defined through the condition that P (L) is a generator of the principal ideal I^{[U](Z)} ∩ k[U, Z][L] . Namely, P is a characteristic polynomial of the 0− dimensional variety W_{0} defined by I^{(Z)} in IA^{n}(\overline{k(Z)}) . Let v_{1}, …, v_{n} ∈ k[U](Z)[T] denote the polynomials arising in Shape Lemma applied to W_{0} . From the proof of this lemma we have that

∂P (L)/∂U_{i} = P′(L) x_{i} − v_{i}(L) ∈ k[U, Z][L]

and so v_{i} ∈ k[U, Z][T] . Set J := (P (L), P′(L) x_{1}−v_{1}(L), …, P′(L) x_{n}−v_{n}(L)) ⊂ k[U, Z][x] and ρ := discr_{T} P ∈ k[U, Z] \ {0}. Then

(I^{[U](Z)})_{ρ} = (J^{[U](Z)})_{ρ} ⊂ k[U](Z)_{ρ}[x].

We have that both I_{ρ}^{[U,Z]} and J_{ρ}^{[U,Z]} are prime ideals of k[U, Z]_{ρ}[x] with trivial intersection with the ring k[U, Z] . Thus they coincide with the contraction of I_{ρ}^{[U](Z)} and J_{ρ}^{[U](Z)} to k[U, Z]_{ρ}[x] respectively, and so

I_{ρ}^{[U,Z]} = J_{ρ}^{[U,Z]} ⊂ k[U, Z]_{ρ}[x].

Define F ∈ k[Z] \ {0} as any of the non-zero coefficients of the monomial expansion of ρ with respect to U . Let a ∈ k^{sℓ} such that F (a) ≠ 0 . Then ρ(U, a) ≠ 0 and so P (U, a)[T] is squarefree. Then

(I(a)^{[U]})_{ρ(U,a)} = (P (L), P′(L) x_{1} − v_{1}(L), …, P′(L) x_{n} − v_{n}(L))(a) ⊂ k[U][x]

is radical, which implies in turn that I(a) = (I(a)^{[U]})_{ρ(U,a)} ∩ k[x] is a radical ideal of k[x] as desired. It remains to estimate the degree of F . To this end, it suffices to bound the degree of ρ with respect to the group of variables Z. We recall that P was defined as a defining equation of the hypersurface \overline{Ψ(W)} . The map Ψ is linear in the variables Z and x, and so

deg_{Z} P ≤ deg W = deg V ≤ (d + 1)^{n}.

This implies that deg F ≤ deg_{Z} ρ ≤ deg_{Z} P (2 deg_{Z} P − 1) ≤ 2 (d + 1)^{2n}.

Finally we consider the case ℓ < n for I ∩ k[Z] = {0}. Let U_{1}, …, U_{n−ℓ} be groups of n + 1 variables each, and set

L_{i} := U_{i 0} + U_{i 1} x_{1} + ⋯ + U_{i n} x_{n}.

for i = 1, …, n − ℓ. Set U := (U_{1}, …, U_{n−ℓ}) , L := (L_{1}, …, L_{n−ℓ}) and k_{0} := k(U, L) . The extended ideal I_{0} ⊂ k_{0}[Z][x_{1}, …, x_{ℓ}] verifies I_{0} ∩ k_{0}[Z] = {0} and thus falls into the previously considered case. Thus there exists F_{0} ∈ k_{0}[Z] \ {0} with deg F_{0} ≤ 2 (d + 1)^{2ℓ} such that F_{0}(a) ≠ 0 for a ∈ k^{sℓ} implies that I_{0}(a) is a radical ideal of k_{0}[Z][x_{1}, …, x_{ℓ}] . This implies in turn that I(a) is a radical ideal of k[x] , as

I(a) = I_{0}(a) ∩ k[x].

We can assume without loss of generality that F_{0} lies in k[U, L][Z] . We conclude by taking F as any non-zero coefficient of the monomial expansion of F_{0} with respect to the variables U and L. □

Corollary 4.4 Let char (k) = 0 , and let f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d := max_{i} deg f_{i}. Then there exist t ≤ min{n + 1, s} and a_{1}, …, a_{t} ∈ ZZ^{s} such that

• (Q_{1}(a_{1}), …, Q_{i}(a_{i})) is a radical ideal of dimension n − i for 1 ≤ i ≤ t − 1 ,

• 1 ∈ (Q_{1}(a_{1}), …, Q_{t}(a_{t})) ,

• h(a_{i}) ≤ 2 (n + 1) log(d + 1) .

Proof.– Set t for the minimal i such that I_{i} := (Q_{1}, …, Q_{i})∩k[Z] ≠ {0}. Then t ≤ n+1 , and by the previous result there exists F_{t} ∈ k[Z] with deg F_{t} ≤ (d+1)^{t} such that F_{t}(a) ≠ 0 implies that 1 ∈ (Q_{1}(a_{1}), …, Q_{t}(a_{t})) . On the other hand, for i < t we take a polynomial F_{i} ∈ k[Z] of degree bounded by 2 (d + 1)^{2 i} such that F_{i}(a) ≠ 0 implies that (Q_{1}(a_{1}), …, Q_{i}(a_{i})) is a radical ideal of dimension n − i. Then we take F := F_{1} ⋯ F_{t} and so

deg F ≤ 2 (d + 1)^{2} + ⋯ + 2 (d + 1)^{2(t−1)} + (d + 1)^{t}
≤ (d + 1)^{2n} + 2 (d + 1)^{2n} + (d + 1)^{n+1}
≤ 4 (d + 1)^{2n}.

Finally, F ≠ 0 implies there exist a_{1}, …, a_{t} ∈ ZZ^{s} such that h(a_{i}) ≤ log(deg F) and F (a) ≠ 0 .

□

4.1.2 Effective Noether normal position

Now we devote to the preparation of the variables. For k = 0, …, n we let U_{k} := (U_{k0}, …, U_{kn}) be a group of n + 1 variables and we set

Y_{k} := U_{k 0} + U_{k 1} x_{1} + ⋯ + U_{k n} x_{n}.

Proposition 4.5 Let V ⊂ IA^{n} be an equidimensional variety of dimension r defined over k. Then there exists G ∈ k[U_{1}, …, U_{r}]\{0} with deg_{U_{k}} G ≤ 2 (deg V)^{2} such that G(b_{1}, …, b_{r}) ≠ 0 for b_{1}, …, b_{r} ∈ k^{n+1} implies that

# V ∩ V (Y_{1}(b_{1}), …, Y_{r}(b_{r})) = deg V.

Proof.– Let f_{V} be a Chow form of V and P_{V} ∈ k[U, T] be the characteristic polynomial of V associated to f_{V} given by Lemma 2.12. Set D := deg V and let P_{V} = c_{D} T_{0}^{D} + ⋯ + c_{0} be its expansion with respect to T_{0} . Also set

ρ := discr_{T_{0}}P_{V} ∈ k[U_{0}, …, U_{r}][T_{1}, …, T_{r}] \ {0}

for the discriminant of P_{V} with respect to T_{0} . Observe that as P_{V} is multihomogeneous of degree D in each group of variables U_{i} ∪{T_{i}}, the degree of ρ in each of these group of variables is bounded by D (2D − 1) . Now let ν_{1}, …, ν_{r} ∈ \overline{k}^{n+1} such that V (ν) := V ∩ V (Y_{1}(ν_{1}), …, Y_{r}(ν_{r})) is a 0 -dimensional variety of cardinality D, and f_{V (ν)} be a Chow forms of V (ν) . Set ζ_{0} := (T_{0} − U_{00}, U_{01}…. , U_{0n}) . Then applying [44, Prop. 2.4], there exists λ ∈ k^{∗} such that:

P_{V} (U_{0}, ν_{1}, …, ν_{r})(T_{0}, 0, …, 0) = f_{V} (ζ_{0}(U_{0}, T_{0}), ν_{1}, …, ν_{r}) = λ f_{V (ν)}(ζ_{0}(U_{0}, T_{0})) = λ P_{V (ν)}(U_{0})(T_{0})

where P_{V (ν)} is a characteristic polynomial of V (ν) . This implies P_{V} (U)(T_{0}, 0, …, 0) ∈ k[U][T_{0}] is a squarefree polynomial and so ρ(U)(0) ≠ 0 . We take G ∈ k[U_{1}, …, U_{r}] as any non-zero coefficient of the expansion of ρ(U)(0) with respect to U_{0} . Therefore

deg G ≤ deg_{U_{i}} ρ(U)(0) ≤ D (2 D − 1).

The condition G(b) ≠ 0 implies that ρ(U_{0}, b_{1}, …, b_{r})(0) ≠ 0 , and so #V (b) = D. □

As we noted before, this implies that the variables Y_{1}(b_{1}), …, Y_{r}(b_{r}) are in Noether normal position with respect to the variety V .

Corollary 4.6 Let char (k) = 0 and let q_{1}, …, q_{t} ∈ k[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n} which form a reduced weak regular sequence. Set d := max_{i} deg f_{i}. Then there exist b_{1}, …, b_{n} ∈ ZZ^{n+1} such that for i = 1, …, t, V (q_{1}, …, q_{i}) satisfies Assumption 1.5 with respect to the variables Y_{1}(b_{1}), …, Y_{n−i}(b_{n−i}) and

h(b_{k}) ≤ 2 (n + 1) log(d + 1).

Proof.– This follows readily from the previous result. We take G_{i} as the polynomial corresponding to the variety V (q_{1}, …, q_{i}) and we set G := G_{1} ⋯ G_{t−1} ∈ k[U_{1}, …, U_{n}] . We have deg_{U_{j}} G_{i} ≤ 2 d^{2 i} and so

deg_{U_{j}} G ≤ 2 d^{2} + ⋯ + 2 d^{2 (t−1)} ≤ 4 d^{2 (t−1)} ≤ 4 d^{2 n}.

We conclude by taking b_{1}, …, b_{n} ∈ ZZ^{n+1} such that h(b_{i}) ≤ log(deg G) and G(b) ≠ 0 . □

4.2 An intrinsic arithmetic Nullstellensatz

In this section we introduce the notions of degree and height of a polynomial system defined over a number field K. Modulo setting the input equations in general position, these parameters measure the degree and height of the varieties successively cut out. The resulting estimates for the arithmetic Nullstellensatz are linear in these parameters. As an important particular case, we derive a sparse arithmetic Nullstellensatz.

4.2.1 Intrinsic parameters

Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials of degree bounded by d without common zeros in IA^{n}. For i = 1, …, s we let Z_{i} denote a group of s variables and we set

Q_{i}(Z) := Z_{i1} f_{1} + ⋯ + Z_{is} f_{s} ∈ K[Z][x]

for the associated generic linear combination of f_{1}, …, f_{s}. Let Γ be the set of integer s × s− matrices a = (a_{ij})_{ij} ∈ ZZ^{s×s} of height bounded by 2 (n + 1) log(d + 1) such that

I_{i}(a) := (Q_{1}(a_{1}), …, Q_{i}(a_{i})) ⊂ K[x_{1}, …, x_{n}]

is a radical ideal of dimension n − i for i = 1, …, t − 1 and 1 ∈ I_{t}(a) for some t ≤ min{n + 1, s}. Corollary 4.4 implies that Γ ≠ ∅. For a ∈ Γ we set

δ(a) := max { deg V (I_{i}(a)) ; 1 ≤ i ≤ min{t, n} − 1 },
η(a) := max { h(V (I_{i}(a))) ; 1 ≤ i ≤ t − 1 }.

We set Γ_{min} ⊂ ZZ^{s×s} for the subset of matrices a ∈ Γ such that η(a)+d δ(a) is minimum. Finally let a_{min} ∈ Γ_{min} be a matrix which attains the minimum of δ(a) for a ∈ Γ_{min} .

Definition 4.7 Let notations be as in the previous paragraph. Then we define the degree and the height of the polynomial system f_{1}, …, f_{s} respectively as

δ(f_{1}, …, f_{s}) := δ(a_{min})  ,  η(f_{1}, …, f_{s}) := η(a_{min}).

We restrict ourselves to integer matrices of bounded height in order to keep control of the height of Q_{1}(a_{1}), …, Q_{t}(a_{t}) . The election of η(a) + d δ(a) as the defining invariant comes from the need of estimating the degree and height simultaneously. We note that in case f_{1}, …, f_{s} is already a reduced weak regular sequence we have

η(f_{1}, …, f_{s}) + d δ(f_{1}, …, f_{s}) ≤ η(Id) + d δ(Id).

We can estimate this parameters through the arithmetic Bézout inequality:

Lemma 4.8 Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d_{i} := deg f_{i} and assume that d_{1} ≥ ⋯ ≥ d_{s} holds. Set d := d_{1} = max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Also set n_{0} := min{n, s} and n_{1} := min{n + 1, s}. Then

• δ(f_{1}, …, f_{s}) ≤ ∏_{j=1}^{n_{0}−1} d_{j},

• η(f_{1}, …, f_{s}) ≤ n ∏_{j=1}^{n_{1}−2} d_{j} (h + log s + 3 n (n + 1) d) .

Proof.– Let a := a_{min} = (a_{ij})_{ij} ∈ ZZ^{s×s} be the coefficient matrix which realizes the degree and height of f_{1}, …, f_{s} and set

q_{i} := a_{i1} f_{1} + ⋯ + a_{is} f_{s} , 1 ≤ i ≤ s.

Let t ≤ n_{1} = min{n + 1, s} be minimum such that 1 ∈ (q_{1}, …, q_{t}) . Let ã ∈ ZZ^{(t−1)×s} be the matrix formed by the first t − 1 rows of a and let c ∈ ZZ^{(t−1)×s} be a staircase matrix equivalent to ã. The polynomial system

q̃_{i} := c_{i1} f_{1} + ⋯ + c_{is} f_{s}

is then equivalent to q_{1}, …, q_{t−1} , that is (q̃_{1}, …, q̃_{i}) = (q_{1}, …, q_{i}) for i = 1, …, t − 1 . Also we have deg q̃_{i} ≤ d_{i}, and so

δ := max {deg V_{i}; 1 ≤ i ≤ min{n, t} − 1} ≤ ∏_{j=1}^{n_{0}−1} d_{j}.

We have also that each coefficient of c is a subdeterminant of ã. Thus

h̃ := h(q̃_{1}, …, q̃_{t−1}) ≤ h + log s + h(c)
≤ h + log s + (t − 1) (2 (n + 1) log(d + 1) + log(t − 1))
≤ h + log s + n (3 n + 1) d

and so, applying Corollary 2.10,

η ≤ max {h(V_{i}) : 1 ≤ i ≤ min{n + 1, t} − 1}
≤ ( ∏_{j=1}^{n_{1}−1} d_{j}) ( ∑_{j=1}^{n_{1}−1} h̃)/d_{j} + (n + n_{1} − 1) log(n + 1))
≤ ( ∏_{j=1}^{n_{1}−2} d_{j}) (n (h + log s + n (3 n + 1) d) + 2 n log(n + 1))
≤ n ( ∏_{j=1}^{n_{1}−2} d_{j}) (h + log s + 3 n (n + 1) d).
□

We can also estimate these parameters through the arithmetic Bernstein-Kushnirenko inequality:

Lemma 4.9 Let f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Also let V denote the volume of 1, x_{1}, …, x_{n}, f_{1}, …, f_{s}. Then

• δ(f_{1}, …, f_{s}) ≤ V,

• η(f_{1}, …, f_{s}) ≤ n V (h + log s + 2^{2 n+4} d) .

Proof.– Let a := a_{min} = (a_{i j})_{i j} ∈ ZZ^{s×s} and set q_{i} := a_{i 1} f_{1}+⋯+a_{i s} f_{s} for i = 1, …, s. Then Supp(q_{i}) ⊂ Supp(f_{1}, …, f_{s}) and so V(1, x_{1}, … x_{n}, q_{1}, …, q_{s}) ≤ V. Applying Proposition 2.11 we obtain δ ≤ V and

η ≤ (n max_{i} h(q_{i}) + 2^{2 n+3} log(n + 1) d) V
≤ (n (h + log s + 2 (n + 1) log(d + 1)) + 2^{2 n+3} log(n + 1) d) V
≤ n V (h + log s + 2^{2 n+4} d).
□

4.2.2 Proof of Theorem 2

Modulo the preparation of the input data, the proof of Theorem 2 follows the lines of the example introduced at the beginning of Chapter 4.

Theorem 4.10 (Intrinsic arithmetic Nullstellensatz) Let K be a number field and let f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Also let δ and η denote the degree and the height of the polynomial system f_{1}, …, f_{s}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ O_{K}[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 2 n^{2} d δ ,

• h(a, g_{1}, …, g_{s}) ≤ (n + 1)^{2} [K : Q] d (2 η + (h + log s) δ + 21 (n + 1)^{2} d log(d + 1) δ).

Proof.– Let a_{min} = (a_{ij})_{ij} ∈ ZZ^{s×s} be a coefficient matrix which realizes the degree and height of f_{1}, …, f_{s}. We have then δ = δ(a_{min}) , η = η(a_{min}) and h(a_{min}) ≤ 2 (n + 1) log(d + 1) . We set

q_{i} := a_{i 1} f_{1} + ⋯ + a_{i s} f_{s}

for i = 1, …, s. Then (q_{1}, …, q_{i}) is a radical ideal of dimension n − i for i = 1, …, t − 1 and 1 ∈ (q_{1}, …, q_{t}) for some t ≤ min{n + 1, s}. Also let b_{kl} ∈ ZZ be integers with h(b_{k l}) ≤ 2 (n+1) log(d+1) such that V_{i} := V (q_{1}, …, q_{i}) satisfies Assumption 1.5 with respect to the variables

y_{k} := b_{k 0} + b_{k 1} x_{1} + ⋯ + b_{k n} x_{n}

for i = 1, …, t − 1 . Set b := (b_{k 0})_{k} ∈ ZZ^{n} and B := (b_{k l})_{k,l≥1} ∈ GL_{n}(Q ) , and set φ : IA^{n} → IA^{n} for the affine map φ(x) := B x + b. For j = 1, …, t we then set

F_{j}(y) := q_{j}(x) = q_{j}(φ^{−1}(y)) ∈ K[y_{1}, …, y_{n}]

Thus F_{1}, …, F_{t} are in the hypothesis of Lemma 3.3 with respect to y_{1}, …, y_{n} and we let P_{1}, …, P_{t} ∈ K[x_{1}, …, x_{n}] be the polynomials satisfying Bészout identity we obtain there. Finally, for i = 1, …, s, we set

p_{i} := ∑_{j=1}^{t} a_{i j}P_{j}(φ(x)) ∈ K[x_{1}, …, x_{n}].

We have 1 = p_{1} f_{1} + ⋯ + p_{s} f_{s}.

Now we analyze the degree and the height of these polynomials. We will assume n, d ≥ 2 as the remaining cases have already been considered in Lemmas 3.7 and 3.8. Set W_{l} := V (F_{1}, …, F_{l}) ⊂ IA^{n} for l = 1, …, t − 1 . We have W_{l} = φ(V_{l}) and so deg W_{l} = deg V_{l}. We have also deg F_{j} = deg q_{j} ≤ d and so

deg p_{i} ≤ max_{j} deg P_{j} ≤ 2 n d (1 + ∑_{l=1}^{min{n,s}−1} deg W_{l}) ≤ 2 n^{2} d δ

as deg W_{l} ≤ δ for l ≤ n − 1 . Now let v ∈ M_{K}^{∞} and set h_{v} := max_{i} h_{v}(f_{i}) . We have

h_{∞}(φ^{−1}) ≤ n (h_{∞}(φ) + log n) − log | det B|_{∞}
≤ n (2 (n + 1) log(d + 1) + log n) − log | det B|_{∞}
≤ 3 n (n + 1) log(d + 1) − log | det B|_{∞}

Then

h_{v}(F_{i}) ≤ h_{v}(q_{i}) + (h_{∞}(φ^{−1}) + 2 log(n + 1)) deg q_{i}
≤ h_{v} + 2 (n + 1) log(d + 1) + log s + (3 n (n + 1) log(d + 1) − log | det B|_{∞} + 2 log(n + 1)) d
≤ h_{v} + log s + (n + 1 + 3 n (n + 1) + 2 n) d log(d + 1) − log | det B|_{∞} d
≤ h_{v} + log s + 3 (n + 1)^{2} d log(d + 1) − log | det B|_{∞} d.

by Lemma 1.2(c) and the facts that log(n + 1) ≤ n and log(d + 1) ≥ 1 for d ≥ 2 . Next, applying Lemma 2.6, we obtain

h(W_{l}) ≤ h(V_{l}) + (n − l + 1)(h(φ) + 5 log(n + 1)) deg V_{l}
≤ h(V_{l}) + n (2 (n + 1) log(d + 1) + 5 log(n + 1)) deg V_{l}
≤ η + n (7 n + 2) d log(d + 1) δ

as deg W_{l} = deg V_{l} ≤ d δ and h(V_{l}) ≤ η for l = 1, …, t − 1 . By Lemma 3.3 there exists ξ ∈ K^{∗} such that

h_{v}(P_{j}) ≤ 2 n d ∑_{l=1}^{t−1} h_{v}(W_{l}) + ((n + 1) max_{l} h_{v}(F_{l}) + 2 n (2 n + 5) log(n + 1) d) (1 + ∑_{l=1}^{t−1} deg W_{l})
− log |ξ|_{v}
≤ 2 n d ∑_{l=1}^{t−1} h_{v}(W_{l}) + (n + 1)^{2} (h_{v} + log s) d δ
+(3 (n + 1)^{4} + 2 n^{2} (2 n + 5) (n + 1)) d^{2} log(d + 1) δ − log |μ|_{v}

with μ := (det B)^{(n+1)^{2} d^{2} δ} ξ ∈ K^{∗}. Then

h_{v}(p_{i}) ≤ max_{j} h_{v}(P_{j}) + (h_{∞}(φ) + 2 log(n + 1)) max_{j} deg P_{j} + 2 (n + 1) log(d + 1) + log t
≤ 2 n d ∑_{l} h_{v}(W_{l}) + (n + 1)^{2} (h_{v} + log s) d δ
+(3 (n + 1)^{4} + 2 n^{2} (2 n + 5) (n + 1)) d^{2} log(d + 1) δ − log |μ|_{v}

+ (2 (n + 1) log(d + 1) + 2 log(n + 1)) 2 n^{2} d δ + 2 (n + 1) log(d + 1) + log(n + 1)

≤ 2 n d ∑_{l} h_{v}(W_{l}) + (n + 1)^{2} (h_{v} + log s) d δ + 7 (n + 1)^{3} (n + 2) d^{2} log(d + 1) δ − log |μ|_{v}.

Analogously h_{v}(p_{i}) ≤ 2 n d ∑_{l} h_{v}(W_{l}) + (n + 1)^{2} h_{v} d δ − log |μ|_{v} for v ∉ M_{K}^{∞}. Hence

h(p_{1}, …, p_{s}) ≤ 2 n d ∑_{l} h(W_{l}) + (n + 1)^{2} (h + log s) d δ + 7 (n + 1)^{3} (n + 2) d^{2} log(d + 1) δ
≤ 2 n^{2} d η + 2 n^{3} (7 n + 2) d^{2} log(d + 1) δ + (n + 1)^{2} (h_{v} + log s) d δ
+ 7 (n + 1)^{3} (n + 2) d^{2} log(d + 1) δ
≤ 2 n^{2} d η + (n + 1)^{2} (h_{v} + log s) d δ + 21 (n + 1)^{4} d^{2} log(d + 1) δ.

Finally we apply Lemma 1.3 to obtain a ∈ ZZ \ {0} such that g_{i} := a p_{i} ∈ O_{K}[x_{1}, …, x_{n}] . Thus

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

and the corresponding height estimates are multiplied by [K : Q] . □

We derive from this result and the Bézout inequality 4.8 the following estimate in terms of the degree and the height of the input polynomials:

Corollary 4.11 Let f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d_{i} := deg f_{i} and assume that d_{1} ≥ ⋯ ≥ d_{s} holds. Also set d := d_{1} = max_{i} deg f_{i}, h := h(f_{1}, …, f_{s}) , and n_{0} := min{n, s}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ O_{K}[x_{1}, …, x_{n}] such that • a = g_{1} f_{1} + ⋯ + g_{s} f_{s} ,

• deg g_{i} ≤ 2 n^{2} d ∏_{j=1}^{n_{0}−1} d_{j} ,

• h(a, g_{1}, …, g_{s}) ≤ 2 (n + 1)^{3} [K : Q] d ∏_{j=1}^{n_{0}−1} d_{j} (h + log s + 3 n(n + 7) d log(d + 1)) .

4.2.3 Estimates for the sparse case

Bernstein-Kushnirenko inequality 4.9 shows that both the degree and the height of a system are controlled by its volume. We derive then from Theorem 4.10 an arithmetic Nullstellensatz for sparse polynomial systems.

Corollary 4.12 (Sparse arithmetic Nullstellensatz) Let f_{1}, …, f_{s} ∈ O_{K}[x_{1}, …, x_{n}] be polynomials without common zeros in IA^{n}. Set d := max_{i} deg f_{i} and h := h(f_{1}, …, f_{s}) . Also let V denote the volume of the polynomial system 1, x_{1}, …, x_{n}, f_{1}, …, f_{s}. Then there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ O_{K}[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 2 n^{2} d V ,

• h(a, g_{1}, …, g_{s}) ≤ 2 (n + 1)^{3} [K : Q] d V ( h + log s + 2^{2n+4}d log(d + 1)).

Example 4.13 For 1 ≤ i ≤ s we let

f_{i} := a_{i 0} + a_{i 1}x_{1} + ⋯ + a_{i n}x_{n} + b_{i 1}x_{1} ⋯ x_{n} + ⋯ + b_{i d}(x_{1} ⋯ x_{n})^{d} ∈ ZZ[x_{1}, …, x_{n}]

be polynomials of degree bounded by n d without common zeros in IA^{n}. Set h := max_{i} h(f_{i}) . Also set P_{d} := Conv(0, e_{1}, …, e_{n}, d (e_{1} +⋯+e_{n})) ⊂ IR^{n}, so that P_{d} contains the Newton polytope of the polynomials 1, x_{1}, …, x_{n}, f_{1}, …, f_{s}. Then

V ≤ Vol(P_{d}) = n! d/(n − 1)! = n d.

We conclude that there exist a ∈ ZZ \ {0} and g_{1}, …, g_{s} ∈ ZZ[x_{1}, …, x_{n}] such that

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

• deg g_{i} ≤ 2 n^{4} d^{2} ,

• h(a), h(g_{i}) ≤ 2 n^{2} (n + 1)^{3} d^{2} ( h + log s + n 2^{2 n+4} d log(n d + 1)) .

This estimate is sharper than the one given by Theorem 1.

References

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

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

[3] C. A. Berenstein, A. Yger, Residue calculus and effective Nullstellensatz, Amer. J. Math. 121 (1999), pp. 723–796.

[4] D. N. Bernstein, The number of roots of a system of equations, Functional Anal. Appl. 9 (1975), pp. 183–185.

[5] J.-B. Bost, H. Gillet, C. Soulé, Height of projective varieties and positive Green forms, J. Amer. Math. Soc. 7 (1994), pp. 903–1027.

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

[7] L. Caniglia, A. Galligo, J. Heintz, Borne simplemente exponentielle pour les degrés dans le théorème des zéros sur un corps de charactéristique quelconte, C. R. Acad. Sci. Paris 307 (1988), pp. 255–258.

[8] J. Canny, I. Emiris, A subdivision–based algorithm for the sparse resultant, to appear in J. Symbolic Comput..

[9] L. Ein, R. Lazarsfeld, A geometric effective Nullstellensatz, Invent. Math. 137 (1999), pp. 427–448.

[10] G. Faltings, Diophantine approximation on abelian varieties, Ann. of Math. 133 (1991), pp. 549–576.

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

[12] N. Fitchas, M. Giusti, F. Smietanski, Sur la complexité du théorème des zéros, in J. Gudat et. al., eds., Approximation and optimization 8, Peter Lange Verlag, 1995, pp. 247– 329.

[13] W. Fulton, Intersection theory, Erg. Math., 3. Folge., 2. Bd., Springer–Verlag, 1984.

[14] I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Birkhäuser, 1994.

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

[16] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, L. M. Pardo, Straight–line programs in geometric elimination theory, J. Pure Appl. Algebra 124 (1998), pp. 101–146.

[17] M. Giusti, J. Heintz, J. Sabia, On the efficiency of effective Nullstellensätze, Comput. Complexity 3 (1993), pp. 56–95.

[18] K. Hägele, Intrinsic height estimates for the Nullstellensatz, Ph.D. Thesis, Univ. Cantabria, 1998.

[19] K. Hägele, J. E. Morais, L. M. Pardo, M. Sombra, On the intrinsic complexity of the arithmetic Nullstellensatz, to appear in J. Pure Appl. Algebra.

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

[21] J. Heintz, C.-P. Schnorr, Testing polynomials which are easy to compute, Monografie Enseignement Math. 30 (1982), pp. 237-254.

[22] G. Hermann, Der Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), pp. 736–788.

[23] S. Ji, J. Kollár, B. Shiffman, A global Lojasiewicz inequality for algebraic varieties, Trans. Amer. Math. Soc. 329 (1992), pp. 813–818.

[24] M. M. Kapranov, B. Sturmfels, A. V. Zelevinsky, Chow polytopes and generalized resultants, Duke Math. J. 67 (1992), 189–218.

[25] P. Koiran, Hilbert’s Nullstellensatz is in the polynomial hierarchy, J. Complexity 12 (1996), pp. 273–286.

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

[27] J. Kollár, Effective Nullstellensatz for arbitrary ideals, Manuscript, Univ. Utah, 1998.-prints:

    math. AG/9805091.

[28] T. Krick, L. M. Pardo, Une approche informatique pour l’approximation diophantienne, C. R. Acad. Sci. Paris 318 (1994), pp. 407–412.

[29] T. Krick, L. M. Pardo, A computational method for diophantine approximation, Progress in Math. 143, Birkhäuser, 1996, pp. 193–253.

[30] T. Krick, J. Sabia, P. Solernó, On intrinsic bounds in the Nullstellensatz, AAECC J. 8 (1997), pp. 125–134.

[31] E. Kunz, Kähler differentials, Adv. Lect. in Math., Vieweg–Verlag, 1986.

[32] A. G. Kushnirenko, Newton polyhedra and Bézout’s theorem, Functional Anal. Appl. 10 (1976), pp. 233-235.

[33] S. Lang, Algebraic number theory, Addison–Wesley, 1970.

[34] D. Lazard, Algèbre linéaire sur k[x_{1}, …, x_{n}] et élimination, Bull. Soc. Math. France 105 (1977), pp. 165–190.

[35] D. H. Lehmer, Factorization of certain cyclotomic functions, Ann. of Math. 34 (1933), pp. 461–479.

[36] P. Lelong, Mesure de Mahler et calcul des constantes universelles pour les polynômes de n variables, Math. Ann. 299 (1994), pp. 673–695.

[37] P. Lelong, L. Gruman, Entire functions of several complex variables, Grundl. Math. Wiss. 282, Springer–Verlag, 1986.

[38] K. Mahler, On some inequalities for polynomials in several variables, J. London Math. Soc. 37 (1962), pp. 341–344.

[39] V. Maillot, Géométrie d’Arakelov des variétés toriques et fibrés en droites intégrables, to appear in Mém. Soc. Math. France.

[40] D. W. Masser, G. Wüstholz, Fields of large trascendence degree generated by values of elliptic functions, Invent. Math. 72 (1983), pp. 407–464.

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

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

[43] P. Pedersen, B. Sturmfels, Product formulas for resultants and Chow forms, Math. Z. 214 (1993), pp. 377–396.

[44] P. Philippon, Critères pour l’indépendance algébrique, Publ. Math. IHES 64 (1986), pp. 5–52.

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

[46] P. Philippon, Sur des hauteurs alternatives, I, Math. Ann. 289 (1991), pp. 255–283; II, Ann. Inst. Fourier 44 (1994), pp. 1043–1065; III, J. Math. Pures Appl. 74 (1995), pp. 345–365.

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

[48] P. Solernó, Effective Lojasiewicz inequalities in semialgebraic geometry, AAECC 2 (1989), pp. 1–14.

[49] 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.

[50] M. Sombra, A sparse effective Nullstellensatz, Adv. Appl. Math. 22 (1999), pp. 271–295.

[51] M. Sombra, Estimaciones para el teorema de ceros de Hilbert, Ph.D. Thesis, Univ. Buenos Aires, 1998.

[52] C. Soulé, Géometrie d’Arakelov et nombres trascendants, J. Arithmétiques, Luminy’89, Asterisque 198–200 (1991), pp. 355–371.

[53] B. Sturmfels, Sparse elimination theory, in D. Eisenbud and L. Robbiano, eds., Computational algebraic geometry and commutative algebra, Cambridge Univ. Press, 1993, pp. 377–396.

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

[55] 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.

Teresa Krick: Departamento de Matemática, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina

E-mail :  krick@dm.uba.ar

Luis Miguel Pardo: Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, E-39071 Santander, España

E-mail:  pardo@matesco.unican.es

Martín Sombra: Departamento de Matemática, Universidad Nacional de La Plata, Calle 50 y 115, 1900 La Plata, Argentina, and School of Mathematics, Institute for Advanced Study, Princeton NJ 08540, USA,

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