Hilbert's Basis Theorem · Invariance: The Mathematics of Emmy Noether

← Invariance: The Mathematics of Emmy Noether

Part 11 showed chains of ideals stopping in ℤ, in $k[x]$ , and among monomial ideals. Hilbert's basis theorem (1890) passes the chain condition from a ring to the polynomials over it:

R \text{ Noetherian} \;\Longrightarrow\; R[x] \text{ Noetherian}

Adding one variable at a time, every ideal of $k[x_1, \ldots, x_n]$ or $\mathbb Z[x_1, \ldots, x_n]$ is finitely generated, so every variety in $k^n$ is cut out by finitely many equations, even though already $(x, y) \subseteq k[x, y]$ needs two generators.

The chain inside the proof

Let $R$ be Noetherian and $I \subseteq R[x]$ an ideal. The proof builds a chain of ideals in $R$ out of leading coefficients.

For each $d \ge 0$ let $J_d \subseteq R$ be the leading coefficients of the polynomials in $I$ of degree at most $d$ , together with 0. Each is an ideal, and $J_0 \subseteq J_1 \subseteq J_2 \subseteq \cdots$
$R$ is Noetherian, so the chain stops at some $d^*$ : $J_{d^*} = J_{d^*+1} = \cdots$ . This is the only use of the chain condition.
Each $J_d$ is finitely generated. For each $d \le d^*$ pick polynomials in $I$ of degree $d$ whose leading coefficients generate $J_d$ .

ideal of ℤ[x]

Figure 1. Steps 1 to 3 for an ideal of $\mathbb Z[x]$ , computed exactly in the page. Row $d$ marks the integers from 0 to 150 that lie in $J_d$ . Rows fill in while the chain climbs (violet) and repeat once it has stopped (green). The integer echelon form behind it uses every shift $x^k f$ of the generators up to degree 24, and the page checks that degree 40 gives the same chain.

Take $g \in I$ of degree $\delta$ . Its leading coefficient lies in $J_\delta = J_{\min(\delta, d^*)}$ , so it is an $R$ -combination of the leading coefficients chosen in that degree. Subtracting the same combination of the chosen polynomials, times a power of $x$ , leaves a polynomial in $I$ of smaller degree.
The degree can drop only finitely often, so $g$ reaches 0, and $g$ lies in the ideal generated by the finite set.

use g + 1

Figure 2. Steps 4 and 5 on $g = a f_1 + b f_2$ , for the ideal chosen in Figure 1 and seeded random $a, b$ . Each point is one subtraction of a multiple of $p_d$ , the polynomial step 3 picked in degree $d = \min(\delta, d^*)$ , and the degree falls every time until $g$ reaches 0. With $g + 1$ the walk stalls on a leading coefficient outside $J_\delta$ . Since everything subtracted lay in $I$ , that proves $g + 1 \notin I$ .

Over ℤ the page can find $d^*$ and each $J_d$ because ℤ has a division algorithm. For a general Noetherian $R$ the proof gives no bound on $d^*$ and no recipe for the generators, only their existence.

Where the proof breaks without the chain condition

Over $R = k[x_1, x_2, x_3, \ldots]$ , the non-Noetherian ring of Part 11, take $I = (x_1 x,\; x_2 x^2,\; x_3 x^3, \ldots)$ . The coefficient of $x^j$ in any element of $I$ lies in $(x_1, \ldots, x_j)$ , and $x_d x^d \in I$ , so

J_1 = (x_1) \;\subsetneq\; J_2 = (x_1, x_2) \;\subsetneq\; J_3 = (x_1, x_2, x_3) \;\subsetneq\; \cdots

never stops. Step 2 fails, and so does the conclusion: a finite subset of $I$ lies in the ideal of the first $N$ generators, which misses $x_{N+1} x^{N+1}$ .

Gordan's objection

Hilbert's 1890 paper used the theorem to prove that the invariants of forms in any number of variables are finitely generated. Paul Gordan had proved the binary case in 1868 by constructing the generators, and his school had spent two decades pushing such constructions further. Hilbert's argument produced no formulas and no bounds. Gordan is reported (in Constance Reid's 1970 biography of Hilbert, and earlier accounts) to have said "Das ist nicht Mathematik, das ist Theologie": this is not mathematics, this is theology. Hilbert gave a more constructive treatment within a few years.

Noether's 1907 dissertation under Gordan was the kind of explicit calculation he favoured. In 1916 she proved the kind of bound Hilbert's proof lacked, for finite groups: in characteristic zero the invariants of a finite group $G$ acting linearly are generated in degree at most $|G|$ . Her 1921 Idealtheorie in Ringbereichen recast the basis theorem as the chain-condition argument above.

n = 7 k = 3

Figure 3. The cyclic group of order $n$ acting on $\mathbb C[x, y]$ by $x \mapsto \zeta x,\ y \mapsto \zeta^k y$ , with $\zeta$ a primitive $n$ -th root of unity. The action is diagonal, so the invariants are spanned by the invariant monomials $x^a y^b$ , those with $a + kb \equiv 0 \pmod n$ (filled). Outlined cells are the invariant monomials that are not a product of two others: a finite generating set, on or below the dashed line $a + b = n$ of Noether's bound. Click a cell, or focus the grid and use the arrow keys, to see it factored.

Gröbner bases

For polynomial ideals a constructive counterpart came later. In 1965 Bruno Buchberger gave an algorithm that turns any finite list of polynomials into a Gröbner basis, a generating set whose leading terms generate the ideal of all leading terms. It divides the S-polynomial of each pair (the combination that cancels their leading terms) by the current basis. A nonzero remainder has a leading term no current one divides, so adding it strictly enlarges the leading-term ideal. That chain of monomial ideals must stop, so the algorithm halts.

order

Figure 4. Buchberger's algorithm in exact rational arithmetic. The grid shows exponents $(i, j)$ of $x^i y^j$ : grey cells lie in the leading-term ideal of the current basis, and each new remainder adds a violet corner outside the old staircase. When every pair reduces to 0 the monomials left outside (green) form a basis of $k[x, y]/I$ . Switch the monomial order: the basis and the staircase change, the number of monomials outside does not.

What a Gröbner basis buys is division. By an arbitrary generating set, a member of the ideal can leave a nonzero remainder that depends on the order of the divisors. By a Gröbner basis the remainder is the same in any order, and 0 exactly for members.

h =

Figure 5. Remainders of $h$ on division by the generators $f_1 = x^2 - y,\ f_2 = xy - 1$ and by the reduced lex Gröbner basis $g_1, g_2$ of the same ideal from Figure 4, in both orders. $y^3 - 1$ is in the ideal, but no leading term of $f_1$ or $f_2$ divides $y^3$ , so dividing by them returns it unchanged (red). The bars repeat the test on 200 seeded random members $a f_1 + b f_2$ .

Quotients of Noetherian rings are Noetherian, so the coordinate ring of any affine variety is Noetherian too. The next article uses that to define the dimension of a variety.