Effective Nullstellensatz

Let $f , f _ { 1 } , \dots , f _ { m } \in R : = k [ x _ { 1 } , \dots , x _ { n } ]$, where $k$ is a field. Hilbert's Nullstellensatz [a5] says that if $f$ vanishes on all the common zeros of the $f_i$ with coordinates in an algebraic closure of $k$, then, for some integer $\rho$, $f ^ { \rho } \in I : = ( f _ { 1 } , \dots , f _ { m} )$, i.e. there exist $a _ { 1 } , \dots , a _ { m } \in R$ such that

\begin{equation*} f ^ { \rho } = a _ { 1 } f _ { 1 } + \ldots + a _ { m } f _ { m }. \end{equation*}

An effective Nullstellensatz gives information on some aspect of the complexity of such a representation.

Degree bounds.

If $\operatorname { deg } f _ { i } \leq d$, how large might one have to take $\rho$ and ?

The projective version of the Masser–Philippon/Lazard–Mora example shows that this bound must be at least $d ^ { n }$. Although classical work of G. Hermann [a8] produces an explicit bound [a14], it is known that $d ^ { n }$ is the correct one [a16], [a17], [a11].

Height bounds.

How large might a common denominator or the numerators of the $a_i$ be?

Assume, in addition, that $k = \mathbf{Q}$ and that when the coefficients of all the $f_i$ are put over a common denominator, the absolute values of that denominator and the numerators of the coefficients are at most $H > 0$. One can, of course, first bound the degrees, and then apply estimates from linear algebra to obtain a bound of the unfortunate shape $( d H ) ^ { c _ { n } d ^ { n^{2} } }$. In fact, by [a15], a denominator of absolute value at most $\operatorname{exp} c _ { n } d ^ { n } ( d + h ) q$ suffices, with explicit $c _ { n }$. The same is true of the numerators if one allows slightly larger than optimal bounds on the degrees of the $f_i$: $\operatorname { deg } f _ { i } \leq c _ { n } d ^ { n }$ [a2], [a3], [a13].

Complexity bounds.

In the various models of computation, how many steps might be involved in finding such a representation?

In these models, as in the above classical case for heights, the complexity bounds turn out to be better than that obtained by simply applying linear algebra and using the degree bounds. Many interesting aspects, such as sparsity of the coefficients, arise. See [a9] for an introduction to a sizable and growing literature.

Generalizations.

Various effective generalizations of Hilbert's Nullstellensatz exist, cf. [a19], [a6], [a12], as well as insight into important special situations [a10]. See [a1] for the link between the complexity of the Nullstellensatz and the problem $\mathcal{P} \neq \mathcal{N} \mathcal{P}$ (cf. $\cal N P$).

References

[a1]	L. Blum, F. Cuker, M. Schub, S. Smale, "Complexity and real computation" , Springer (1998)
[a2]	C.A. Berenstein, A. Yger, "Effective Bezout identities in $\mathbf{Q}[ z _ { 1 } , \dots , z _ { n } ]$" Acta Math. , 166 (1991) pp. 69–120
[a3]	C.A. Berenstein, A. Yger, "Residue calculus and effective Nullstellensatz" Amer. J. Math. , 121 (1999) pp. 723–796
[a4]	L. Caniglia, A. Galligo, J. Heintz, "Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de characteristique quelconque" C.R. Acad. Sci. Paris , 307 (1988) pp. 255–258
[a5]	D. Hilbert, "Über die vollen Invariantesysteme" Math. Ann. , 42 (1893) pp. 313–373 (Also: Ges. Abh., II, pp. 287-344)
[a6]	L. Ein, R. Lazarsfeld, "A geometric effective Nullstellensatz" Invent. Math. , 137 (1999) pp. 427–448
[a7]	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
[a8]	G. Hermann, "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale" Math. Ann. , 95 (1926) pp. 736–788
[a9]	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
[a10]	I. Ojeda, R. Piedra, "Effective Nullstellensatz for binomial ideals" Manuscript (2000)
[a11]	J. Kollár, "Sharp effective Nullstellensatz" J. Amer. Math. Soc. , 1 (1988) pp. 963–975
[a12]	J. Kollár, "Effective Nullstellensatz for arbitrary ideals" J. Europ. Math. Soc. (JEMS) , 1 (1999) pp. 313–337
[a13]	T. Krick, L.M. Pardo, M. Sombra, "Sharp estimates for the arithmetic Nullstellensatz" http://front.math.ucdavis.edu , math.AG/9911094 (1999)
[a14]	D.W. Masser, G. Wüsholz, "Fields of large transcendence degree generated by values of elliptic functions" Invent. Math. , 72 (1983) pp. 407–464
[a15]	P. Phillipon, "Dénominateurs dans le théorème des zéros de Hilbert" Acta Arith. , 58 (1990) pp. 1–25
[a16]	W.D. Brownawell, "Bounds for the degrees in the Nullstellensatz" Ann. of Math. , 126 (1987) pp. 577–591
[a17]	W.D. Brownawell, "Borne effective pour l'exposant dans le théorème des zéros" C.R. Acad. Sci. Paris , 305 (1987) pp. 287–290
[a18]	W.D. Brownawell, "Local diophantine Nullstellen equalities" J. Amer. Math. Soc. , 1 (1988) pp. 311–322
[a19]	W.D. Brownawell, "A pure power product version of the Hilbert Nullstellensatz" Michigan Math. J. , 45 (1998) pp. 581–597