##
**Exponential simple bound for the degrees in the Nullstellensatz over a field of arbitrary characteristic.
(Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque.)**
*(French)*
Zbl 0686.14001

The authors prove the following theorem: “Let \(P_ i\), \(1\leq i\leq s\), be polynomials of degree \( d_ i\leq d\) in \(n\quad variables\) over a field k. If the \(P_ i\)’s generate the unit ideal, write \(\sum P_ iQ_ i =1\) and let \(N\) be the minimium of the maximum degrees of \(P_ iQ_ i\), where \(Q_ i\)’s satisfy the above relation. Let \(F_ i\) be the homogenisations of \(P_ i\). If \(\partial\) is the codimension of \(V(F_ 1,...,F_ s)\) (in \({\mathbb{P}}^ n)\) and \(p\) the depth of \(V(F_ 1,...,F_ s)\) [see below: reviewer’s comment], then \(N\leq d^ s\) with \(2s=(n+1- p)^ 2-\partial^ 2+(n+1-p)+\partial.''\)

A simpler estimate has been obtained by J. Kollár [J. Am. Math. Soc. 1, No. 4, 963–975 (1988; Zbl 0682.14001)].

The reviewer had difficulties in understanding the arguments in the paper. A query to one of the authors elicited the following reply: “.... I confess that our notation is ambiguous and has to be changed. However this point has to be fixed more precisely”.

Revised review (Zbl 0968.14002)

This research note, published in May 1988, provided an abridged version of one of the main results contained in the authors’ more comprehensive paper “Some new effective bounds in computational geometry” [L. Caniglia, A. Galligo and J. Heintz in: Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conf. AAECC-6, Rome 1988, Lect. Notes Comput. Sci. 357, 131–151 (1989; Zbl 0685.68044)]. On the other hand, the latter, more elaborated article had been circulating as a preprint since early 1987, and had been accepted for the Conference Proceedings after its submittance later on in the same year. Honored with a “Best paper award”, the comprehensive article mentioned above appeared then in the Conference proceedings. – With a view to this historical background, the research note under review must be seen as rushing harbinger of the conference paper mentioned above, which on its part was submitted before, yet published after this note.

Now, as for the contents, the authors made a major contribution to the following classical question concerning Hilbert’s Nullstellensatz: Let \(f_1,\dots,f_s\) be polynomials in \(n\) variables over an algebraically closed field \(K\). Then, if these polynomials have no common zero in \(K^n\), Hilbert’s Nullstellensatz states that there are polynomials \(g_1, \dots,g_s\) such that \(\sum^s_{i=1} f_i\cdot g_i=1\). However, the usual proofs of Hilbert’s Nullstellensatz do not provide any information about those polynomials \(g_i\). In particular, they do not give any effective bound on the degrees of such polynomials. The classical problem of determining such an effective, possibly sharp bound was first tackled by Grete Hermann in 1926 [cf.: G. Hermann “Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”, Math. Ann. 95, 736–788 (1926; JFM 52.0127.01)]. Using elimination theory, she obtained a bound on the degree of the polynomials \(g_i\), \(1\leq i\leq s\), which was doubly exponential in the number \(n\) of variables, and her results remained the sharpest one for almost sixty years. A decisive breakthrough was then achieved by W. D. Brownawell in 1987 [Ann. Math. (2) 126, 577-592 (1987; Zbl 0641.14001)], who proved that in the case of the complex number field, one has the much simpler bound \[ \deg(g_i)\leq n\cdot \min(s,n) \cdot D^{\min (s,n)}+ \min(s,n) \cdot D,\;1\leq i\leq s, \] whenever \(\deg(f_i) \leq D\) and \(\sum^s_{i=1} f_i\cdot g_i=1\). Brownawell’s result (in characteristic zero) was based on methods from transcendental number theory and deep results by H. Skoda (1972) in this context.

The present paper, published shortly after Brownawell’s breakthrough in the characteristic-zero case, provided another major step forward, this time in the general case of arbitrary characteristic of the ground field. The main result states that, if \(N\) denotes the minimum of the maxima of the degrees of the polynomials \(f_i\cdot g_i\), \(1\leq i\leq s\), then \(N\leq D^{n(n+3)/2}\).

Compared to Brownawell’s bound in the characteristic-zero case, which can be read as \(N\leq 3n^2\cdot D^n\), the authors’ bound is still doubly exponential in the number of variables, but it is just valid in arbitrary characteristic, and somewhat stronger than any (refined) Hermann-type bound published by back then. The authors’ new bound was obtained by exclusively using elementary ideal theory in homogeneous polynomial rings, and that is, apart from the higher effectiveness of their new bound, one of the main advantages of their approach to the problem in the general case. Moreover, it seems that the authors have derived the best possible bound achievable by most elementary, purely ideal-theoretic methods.

At about the same time, in early May 1988, the paper “Sharp effective Nullstellensatz” by J. Kollár [J. Am. Math. Soc. 1, No. 4, 963–975 (1988; Zbl 0682.14001)] was submitted for publication. In this paper, J. Kollár gives yet another bound for the degrees of the polynomials \(g_i\), \(1\leq i\leq s\), which even improves and generalizes Brownawell’s simply exponential bound to arbitrary characteristics, essentially so by eliminating the factor \(n\cdot\min(s,k)\) from Brownawell’s bound. In most cases, J. Kollár’s bound really gives the best possible result. Kollár’s stronger result is obtained by “almost elementary” methods, too, whereby the only nonstandard ingredients are given by some basic local (sheaf) cohomology of projective varieties.

Altogether, and in spite of J. Kollár’s independent, stronger result, the authors’ approach presented in the research note under review, and fully elaborated in their other paper cited above, was and remains interesting on its own. Namely, it not only demonstrated the striking power of elementary, computational algebraic methods in this context, but also gained its fair rank within the historical development of this classical subject in algebro-geometric complexity theory.

A simpler estimate has been obtained by J. Kollár [J. Am. Math. Soc. 1, No. 4, 963–975 (1988; Zbl 0682.14001)].

The reviewer had difficulties in understanding the arguments in the paper. A query to one of the authors elicited the following reply: “.... I confess that our notation is ambiguous and has to be changed. However this point has to be fixed more precisely”.

Revised review (Zbl 0968.14002)

This research note, published in May 1988, provided an abridged version of one of the main results contained in the authors’ more comprehensive paper “Some new effective bounds in computational geometry” [L. Caniglia, A. Galligo and J. Heintz in: Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conf. AAECC-6, Rome 1988, Lect. Notes Comput. Sci. 357, 131–151 (1989; Zbl 0685.68044)]. On the other hand, the latter, more elaborated article had been circulating as a preprint since early 1987, and had been accepted for the Conference Proceedings after its submittance later on in the same year. Honored with a “Best paper award”, the comprehensive article mentioned above appeared then in the Conference proceedings. – With a view to this historical background, the research note under review must be seen as rushing harbinger of the conference paper mentioned above, which on its part was submitted before, yet published after this note.

Now, as for the contents, the authors made a major contribution to the following classical question concerning Hilbert’s Nullstellensatz: Let \(f_1,\dots,f_s\) be polynomials in \(n\) variables over an algebraically closed field \(K\). Then, if these polynomials have no common zero in \(K^n\), Hilbert’s Nullstellensatz states that there are polynomials \(g_1, \dots,g_s\) such that \(\sum^s_{i=1} f_i\cdot g_i=1\). However, the usual proofs of Hilbert’s Nullstellensatz do not provide any information about those polynomials \(g_i\). In particular, they do not give any effective bound on the degrees of such polynomials. The classical problem of determining such an effective, possibly sharp bound was first tackled by Grete Hermann in 1926 [cf.: G. Hermann “Die Frage der endlich vielen Schritte in der Theorie der Polynomideale”, Math. Ann. 95, 736–788 (1926; JFM 52.0127.01)]. Using elimination theory, she obtained a bound on the degree of the polynomials \(g_i\), \(1\leq i\leq s\), which was doubly exponential in the number \(n\) of variables, and her results remained the sharpest one for almost sixty years. A decisive breakthrough was then achieved by W. D. Brownawell in 1987 [Ann. Math. (2) 126, 577-592 (1987; Zbl 0641.14001)], who proved that in the case of the complex number field, one has the much simpler bound \[ \deg(g_i)\leq n\cdot \min(s,n) \cdot D^{\min (s,n)}+ \min(s,n) \cdot D,\;1\leq i\leq s, \] whenever \(\deg(f_i) \leq D\) and \(\sum^s_{i=1} f_i\cdot g_i=1\). Brownawell’s result (in characteristic zero) was based on methods from transcendental number theory and deep results by H. Skoda (1972) in this context.

The present paper, published shortly after Brownawell’s breakthrough in the characteristic-zero case, provided another major step forward, this time in the general case of arbitrary characteristic of the ground field. The main result states that, if \(N\) denotes the minimum of the maxima of the degrees of the polynomials \(f_i\cdot g_i\), \(1\leq i\leq s\), then \(N\leq D^{n(n+3)/2}\).

Compared to Brownawell’s bound in the characteristic-zero case, which can be read as \(N\leq 3n^2\cdot D^n\), the authors’ bound is still doubly exponential in the number of variables, but it is just valid in arbitrary characteristic, and somewhat stronger than any (refined) Hermann-type bound published by back then. The authors’ new bound was obtained by exclusively using elementary ideal theory in homogeneous polynomial rings, and that is, apart from the higher effectiveness of their new bound, one of the main advantages of their approach to the problem in the general case. Moreover, it seems that the authors have derived the best possible bound achievable by most elementary, purely ideal-theoretic methods.

At about the same time, in early May 1988, the paper “Sharp effective Nullstellensatz” by J. Kollár [J. Am. Math. Soc. 1, No. 4, 963–975 (1988; Zbl 0682.14001)] was submitted for publication. In this paper, J. Kollár gives yet another bound for the degrees of the polynomials \(g_i\), \(1\leq i\leq s\), which even improves and generalizes Brownawell’s simply exponential bound to arbitrary characteristics, essentially so by eliminating the factor \(n\cdot\min(s,k)\) from Brownawell’s bound. In most cases, J. Kollár’s bound really gives the best possible result. Kollár’s stronger result is obtained by “almost elementary” methods, too, whereby the only nonstandard ingredients are given by some basic local (sheaf) cohomology of projective varieties.

Altogether, and in spite of J. Kollár’s independent, stronger result, the authors’ approach presented in the research note under review, and fully elaborated in their other paper cited above, was and remains interesting on its own. Namely, it not only demonstrated the striking power of elementary, computational algebraic methods in this context, but also gained its fair rank within the historical development of this classical subject in algebro-geometric complexity theory.

Reviewer: N.Mohan Kumar