Editing Hilbert's Nullstellensatz (section)

== Effective Nullstellensatz ==
In all of its variants, Hilbert's Nullstellensatz asserts that some polynomial {{mvar|g}} belongs or not to an ideal generated, say, by {{math|''f''<sub>1</sub>, ..., ''f<sub>k</sub>''}}; we have {{math|''g'' {{=}} ''f<sup>&thinsp;r</sup>''}} in the strong version, {{math|''g'' {{=}} 1}} in the weak form. This means the existence or the non-existence of polynomials {{math|''g''<sub>1</sub>, ..., ''g<sub>k</sub>''}} such that {{math|''g'' {{=}} ''f''<sub>1</sub>''g''<sub>1</sub> + ... + ''f<sub>k</sub>g<sub>k</sub>''}}. The usual proofs of the Nullstellensatz are not constructive, non-effective, in the sense that they do not give any way to compute the {{math|''g<sub>i</sub>''}}.

It is thus a rather natural question to ask if there is an effective way to compute the {{math|''g<sub>i</sub>''}} (and the exponent {{mvar|r}} in the strong form) or to prove that they do not exist. To solve this problem, it suffices to provide an upper bound on the total degree of the {{math|''g<sub>i</sub>''}}: such a bound reduces the problem to a finite [[system of linear equations]] that may be solved by usual [[linear algebra]] techniques. Any such upper bound is called an '''effective Nullstellensatz'''.

A related problem is the '''ideal membership problem''', which consists in testing if a polynomial belongs to an ideal. For this problem also, a solution is provided by an upper bound on the degree of the {{math|''g<sub>i</sub>''}}. A general solution of the ideal membership problem provides an effective Nullstellensatz, at least for the weak form.

In 1925, [[Grete Hermann]] gave an upper bound for ideal membership problem that is doubly exponential in the number of variables. In 1982 Mayr and Meyer gave an example where the {{math|''g<sub>i</sub>''}} have a degree that is at least double exponential, showing that every general upper bound for the ideal membership problem is doubly exponential in the number of variables.  

Since most mathematicians at the time assumed the effective Nullstellensatz was at least as hard as ideal membership, few mathematicians sought a bound better than double-exponential.  In 1987, however, [[W. Dale Brownawell]] gave an upper bound for the effective Nullstellensatz that is simply exponential in the number of variables.<ref>{{citation|last=Brownawell|first=W. Dale|title=Bounds for the degrees in the Nullstellensatz|journal=[[Ann. of Math.]]|volume=126|year=1987|issue=3|pages=577–591|mr=0916719|doi=10.2307/1971361|jstor=1971361 }}</ref>  Brownawell's proof relied on analytic techniques valid only in characteristic 0, but, one year later, [[János Kollár]] gave a purely algebraic proof, valid in any characteristic, of a slightly better bound.

In the case of the weak Nullstellensatz, Kollár's bound is the following:<ref>{{citation| first=János| last=Kollár| title=Sharp Effective Nullstellensatz| journal=[[Journal of the American Mathematical Society]]| volume=1| issue=4| year=1988| pages=963–975| url=http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Kollar/kollarnullstellen.pdf| doi=10.2307/1990996| jstor=1990996| mr=0944576| access-date=2012-10-14| archive-url=https://web.archive.org/web/20140303174253/https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Kollar/kollarnullstellen.pdf| archive-date=2014-03-03| url-status=dead}}</ref>

:Let {{math|''f''<sub>1</sub>, ..., ''f<sub>s</sub>''}} be polynomials in {{math|''n'' ≥ 2}} variables, of total degree {{math|''d''<sub>1</sub> ≥ ... ≥ ''d<sub>s</sub>''}}. If there exist polynomials {{math|''g<sub>i</sub>''}} such that {{math|''f''<sub>1</sub>''g''<sub>1</sub> + ... + ''f<sub>s</sub>g<sub>s</sub>'' {{=}} 1}}, then they can be chosen such that 
::<math>\deg(f_ig_i) \le \max(d_s,3)\prod_{j=1}^{\min(n,s)-1}\max(d_j,3).</math> 
:This bound is optimal if all the degrees are greater than 2.

If {{mvar|d}} is the maximum of the degrees of the {{math|''f<sub>i</sub>''}}, this bound may be simplified to 
:<math>\max(3,d)^{\min(n,s)}.</math>

An improvement due to M. Sombra is<ref>{{citation|first=Martín|last=Sombra|title=A Sparse Effective Nullstellensatz| journal=[[Advances in Applied Mathematics]]|volume= 22|issue=2|year=1999| pages=271–295 |arxiv=alg-geom/9710003|doi=10.1006/aama.1998.0633 | mr=1659402|s2cid=119726673 }}</ref>

:<math>\deg(f_ig_i) \le 2d_s\prod_{j=1}^{\min(n,s)-1}d_j.</math>

His bound improves Kollár's as soon as at least two of the degrees that are involved are lower than&nbsp;3.