View source for Hilbert's basis theorem

{{Short description|Polynomial ideals are finitely generated}} 
{{Use shortened footnotes|date=May 2021}}
In [[mathematics]] '''Hilbert's basis theorem''' asserts that every [[ideal (ring theory)|ideal]] of a [[polynomial ring]] over a [[field (mathematics)|field]] has a finite [[generating set of an ideal|generating set]] (a finite ''basis'' in Hilbert's terminology).

In modern [[algebra]], [[ring (mathematics)|ring]]s whose ideals have this property are called [[Noetherian ring]]s. Every field, and the ring of [[integer]]s are Noetherian rings. So, the theorem can be generalized and restated as: ''every polynomial ring over a Noetherian ring is also Noetherian''.

The theorem was stated and proved by [[David Hilbert]] in 1890 in his seminal article on [[invariant theory]]{{r|Hilbert1890}}, where he solved several problems on invariants. In this article, he proved also two other fundamental theorems on polynomials, the [[Nullstellensatz]] (zero-locus theorem) and the [[syzygy theorem]] (theorem on relations). These three theorems were the starting point of the interpretation of [[algebraic geometry]] in terms of [[commutative algebra]]. In particular, the basis theorem implies that every [[algebraic set]] is the intersection of a finite number of [[hypersurface]]s.

Another aspect of this article had a great impact on mathematics of the 20th century; this is the systematic use of [[constructive mathematics|non-constructive methods]]. For example, the basis theorem asserts that every ideal has a finite generator set, but the original proof does not provide any way to compute it for a specific ideal. This approach was so astonishing for mathematicians of that time that the first version of the article was rejected by [[Paul Gordan]], the greatest specialist of invariants of that time, with the comment "This is not mathematics. This is theology."{{Sfn|Reid|1996|p=34}} Later, he recognized "I have convinced myself that even theology has its merits."<ref name=":0">{{harvnb|Reid|1996|p=[https://books.google.com/books?id=mR4SdJGD7tEC&pg=PA37 37].}}</ref>

==Statement==
If <math>R</math> is a [[ring (mathematics)|ring]], let <math>R[X]</math> denote the ring of [[polynomial]]s in the indeterminate <math>X</math> over <math>R</math>. [[David Hilbert|Hilbert]] proved that if <math>R</math> is "not too large", in the sense that if <math>R</math> is Noetherian, the same must be true for <math>R[X]</math>. Formally,

<blockquote>'''Hilbert's Basis Theorem.''' If <math>R</math> is a Noetherian ring, then <math>R[X]</math> is a Noetherian ring.<ref>{{harvnb|Roman|2008|loc=p. 136 §5 Theorem 5.9}}</ref></blockquote>
<blockquote>'''Corollary.''' If <math>R</math> is a Noetherian ring, then <math>R[X_1,\dotsc,X_n]</math> is a Noetherian ring.</blockquote>

Hilbert proved the theorem (for the special case of [[multivariate polynomial]]s over a [[field (mathematics)|field]]) in the course of his proof of finite generation of [[ring of invariants|rings of invariants]].{{r|Hilbert1890}} The theorem is interpreted in [[algebraic geometry]] as follows: every [[algebraic set]] is the set of the common [[root of a polynomial|zeros]] of finitely many polynomials. 

Hilbert's proof is highly [[non-constructive proof|non-constructive]]: it proceeds by [[mathematical induction|induction]] on the number of variables, and, at each induction step uses the non-constructive proof for one variable less. Introduced more than eighty years later, [[Gröbner bases]] allow a direct proof that is as constructive as possible: Gröbner bases produce an algorithm for testing whether a polynomial belong to the ideal generated by other polynomials. So, given an infinite sequence of polynomials, one can construct algorithmically the list of those polynomials that do not belong to the ideal generated by the preceding ones. Gröbner basis theory implies that this list is necessarily finite, and is thus a finite basis of the ideal. However, for deciding whether the list is complete, one must consider every element of the infinite sequence, which cannot be done in the finite time allowed to an algorithm.

==Proof==
'''Theorem.''' If <math>R</math> is a left (resp. right) [[Noetherian ring]], then the [[polynomial ring]] <math>R[X]</math> is also a left (resp. right) Noetherian ring.

:'''Remark.''' We will give two proofs, in both only the "left" case is considered; the proof for the right case is similar.

===First proof===
Suppose <math>\mathfrak a \subseteq R[X]</math> is a non-finitely generated left ideal. Then by recursion (using the [[axiom of dependent choice]]) there is a sequence of polynomials <math>\{ f_0, f_1, \ldots \}</math> such that if <math>\mathfrak b_n</math> is the left ideal generated by <math>f_0, \ldots, f_{n-1}</math> then <math>f_n \in \mathfrak a \setminus \mathfrak b_n</math> is of minimal [[degree of a polynomial|degree]]. By construction,  <math>\{\deg(f_0), \deg(f_1), \ldots \}</math> is a non-decreasing sequence of [[natural number]]s. Let <math>a_n</math> be the leading coefficient of <math>f_n</math> and let <math>\mathfrak{b}</math> be the left ideal in <math>R</math> generated by <math>a_0,a_1,\ldots</math>. Since <math>R</math> is Noetherian the chain of ideals

:<math>(a_0)\subset(a_0,a_1)\subset(a_0,a_1,a_2) \subset \cdots</math>

must terminate. Thus <math>\mathfrak b = (a_0,\ldots ,a_{N-1})</math> for some [[integer]] <math>N</math>. So in particular,

:<math>a_N=\sum_{i<N} u_{i}a_{i}, \qquad u_i \in R.</math>

Now consider

:<math>g = \sum_{i<N}u_{i}X^{\deg(f_{N})-\deg(f_{i})}f_{i},</math>

whose leading term is equal to that of <math>f_N</math>; moreover, <math>g\in\mathfrak b_N</math>. However, <math>f_N \notin \mathfrak b_N</math>, which means that <math>f_N - g \in \mathfrak a \setminus \mathfrak b_N</math> has degree less than <math>f_N</math>, contradicting the minimality.

===Second proof=== 
Let <math>\mathfrak a \subseteq R[X]</math> be a left ideal. Let <math>\mathfrak b</math> be the set of leading coefficients of members of <math>\mathfrak a</math>. This is obviously a left ideal over <math>R</math>, and so is finitely generated by the leading coefficients of finitely many members of <math>\mathfrak a</math>; say <math>f_0, \ldots, f_{N-1}</math>. Let <math>d</math> be the maximum of the set <math>\{\deg(f_0),\ldots, \deg(f_{N-1})\}</math>, and let <math>\mathfrak b_k</math> be the set of leading coefficients of members of <math>\mathfrak a</math>, whose degree is <math>\le k</math>. As before, the <math>\mathfrak b_k</math> are left ideals over <math>R</math>, and so are finitely generated by the leading coefficients of finitely many members of <math>\mathfrak a</math>, say

:<math>f^{(k)}_{0}, \ldots, f^{(k)}_{N^{(k)}-1}</math>

with degrees <math>\le k</math>. Now let <math>\mathfrak a^*\subseteq R[X]</math> be the left ideal generated by:

:<math>\left\{f_{i},f^{(k)}_{j} \, : \ i<N,\, j<N^{(k)},\, k<d \right\}\!\!\;.</math>

We have <math>\mathfrak a^*\subseteq\mathfrak a</math> and claim also <math>\mathfrak a\subseteq\mathfrak a^*</math>. Suppose for the sake of contradiction this is not so. Then let <math>h\in \mathfrak a \setminus \mathfrak a^*</math> be of minimal degree, and denote its leading coefficient by <math>a</math>.

:'''Case 1:''' <math>\deg(h)\ge d</math>. Regardless of this condition, we have <math>a\in \mathfrak b</math>, so <math>a</math> is a left linear combination

::<math>a=\sum_j u_j a_j</math>

:of the coefficients of the <math>f_j</math>. Consider

::<math>h_0 =\sum_{j}u_{j}X^{\deg(h)-\deg(f_{j})}f_{j},</math>

:which has the same leading term as <math>h</math>; moreover <math>h_0 \in \mathfrak a^*</math> while <math>h\notin\mathfrak a^*</math>. Therefore <math>h - h_0 \in \mathfrak a\setminus\mathfrak a^*</math> and <math>\deg(h - h_0) < \deg(h)</math>, which contradicts minimality.

:'''Case 2:''' <math>\deg(h) = k < d</math>. Then <math>a\in\mathfrak b_k</math> so <math>a</math> is a left linear combination

::<math>a=\sum_j u_j a^{(k)}_j</math>

:of the leading coefficients of the <math>f^{(k)}_j</math>. Considering

::<math>h_0=\sum_j u_j X^{\deg(h)-\deg(f^{(k)}_{j})}f^{(k)}_{j},</math>

:we yield a similar contradiction as in Case 1.

Thus our claim holds, and <math>\mathfrak a = \mathfrak a^*</math> which is finitely generated.

Note that the only reason we had to split into two cases was to ensure that the powers of <math>X</math> multiplying the factors were non-negative in the constructions.

== Applications ==
Let <math>R</math> be a Noetherian [[commutative ring]]. Hilbert's basis theorem has some immediate [[corollary|corollaries]].

#By induction we see that <math>R[X_0,\dotsc,X_{n-1}]</math> will also be Noetherian. 
#Since any [[affine variety]] over <math>R^n</math> (i.e. a locus-set of a collection of polynomials) may be written as the locus of an ideal <math>\mathfrak a\subset R[X_0, \dotsc, X_{n-1}]</math> and further as the locus of its generators, it follows that every affine variety is the locus of finitely many polynomials — i.e. the [[intersection (set theory)|intersection]] of finitely many [[hypersurface]]s. 
#If <math>A</math> is a [[finitely-generated algebra|finitely-generated <math>R</math>-algebra]], then we know that <math>A \simeq R[X_0, \dotsc, X_{n-1}] / \mathfrak a</math>, where <math>\mathfrak a</math> is an ideal. The basis theorem implies that <math>\mathfrak a</math> must be finitely generated, say <math>\mathfrak a = (p_0,\dotsc, p_{N-1})</math>, i.e. <math>A</math> is [[Glossary_of_ring_theory#Finitely_presented_algebra|finitely presented]].

==Formal proofs==
Formal proofs of Hilbert's basis theorem have been verified through the [[Mizar system|Mizar project]] (see [http://www.mizar.org/JFM/Vol12/hilbasis.html HILBASIS file]) and [[Lean_(proof_assistant) | Lean]] (see [https://github.com/leanprover-community/mathlib/blob/937199a/src/ring_theory/polynomial/basic.lean#L353 ring_theory.polynomial]).

==References==
{{reflist|refs=
<ref name=Hilbert1890>{{Cite journal |last=Hilbert |first=David |author-link=David Hilbert |date=1890 |title=Über die Theorie der algebraischen Formen |journal=[[Mathematische Annalen]] |volume=36 |issue=4 |pages=473–534 |issn=0025-5831 |doi=10.1007/BF01208503|s2cid=179177713 }}</ref>
}}

==Further reading==
* Cox, Little, and O'Shea, ''Ideals, Varieties, and Algorithms'', Springer-Verlag, 1997.
* {{Cite book|last=Reid|first=Constance.|url=https://books.google.com/books?id=mR4SdJGD7tEC|title=Hilbert|publisher=[[Springer Publishing|Springer]]|year=1996|isbn=0-387-94674-8|location=New York|author-link=Constance Reid}} The definitive English-language biography of Hilbert.
*{{citation | last=Roman | first=Stephen
 | title=Advanced Linear Algebra | edition=Third | series=[[Graduate Texts in Mathematics]] | publisher  = Springer | date=2008| pages= | isbn=978-0-387-72828-5 |author-link=Steven Roman}}

[[Category:Commutative algebra]]
[[Category:Invariant theory]]
[[Category:Articles containing proofs]]
[[Category:Theorems in ring theory]]
[[Category:David Hilbert]]
[[Category:Theorems about polynomials]]