# Effective Nullstellensatz

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Let , where is a field. Hilbert's Nullstellensatz [a5] says that if vanishes on all the common zeros of the with coordinates in an algebraic closure of , then, for some integer , , i.e. there exist such that An effective Nullstellensatz gives information on some aspect of the complexity of such a representation.

## Degree bounds.

If , how large might one have to take and ?

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

## Height bounds.

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

Assume, in addition, that and that when the coefficients of all the are put over a common denominator, the absolute values of that denominator and the numerators of the coefficients are at most . One can, of course, first bound the degrees, and then apply estimates from linear algebra to obtain a bound of the unfortunate shape . In fact, by [a15], a denominator of absolute value at most suffices, with explicit . The same is true of the numerators if one allows slightly larger than optimal bounds on the degrees of the : [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 (cf. ).

How to Cite This Entry:
Effective Nullstellensatz. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Effective_Nullstellensatz&oldid=16412
This article was adapted from an original article by W. Dale Brownawell (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article