TAOCP 7.2.1.3 Exercise 102
Let $I \subseteq \mathbb{C}[x_1,\dots,x_s]$ be a homogeneous polynomial ideal.
Section 7.2.1.3: Generating All Combinations
Exercise 102. [HM35] [HM35] (F. S. Macaulay, 1927.) A polynomial ideal I in the variables {x1 . . . , xs} is a set of polynomials closed under the operations of addition, multiplication by a constant, and multiplication by any of the variables. It is called homogeneous if it consists of all linear combinations of a set of homogeneous polynomials, namely of polynomials like xy+z2 whose terms all have the same degree. Let Nt be the maximum number of linearly independent elements of degree t in I. For example, if s = 2, the set of all α(x0, x1, x2)(x0x2 1 −2x1x2 2) + β(x0, x1, x2)x0x1x2 2, where α and β run through all possible polynomials in {x0, x1, x2}, is a homogeneous polynomial ideal with N0 = N1 = N2 = 0, N3 = 1, N4 = 4, N5 = 9, N6 = 15, . . . . a) Prove that for any such ideal I there is another ideal I′ in which all homogeneous polynomials of degree t are linear combinations of Nt independent monomials. (A monomial is a product of variables, like x3 1x2x4 5.) b) Use Theorem M and (64) to prove that Nt+1 ≥Nt + κsNt for all t ≥0. c) Show that Nt+1 > Nt + κsNt occurs for only finitely many t. (This statement is equivalent to “Hilbert’s basis theorem,” proved by David Hilbert in Göttinger Nachrichten (1888), 450–457; Math. Annalen 36 (1890), 473–534.)
Verified: no
Solve time: 12m05s
Setup
Let $I \subseteq \mathbb{C}[x_1,\dots,x_s]$ be a homogeneous polynomial ideal. Let $I_t$ denote the vector space of homogeneous polynomials of degree $t$ contained in $I$. Define
$$ N_t = \dim I_t, $$
the maximum number of linearly independent degree-$t$ elements of $I$.
The goal is to relate the sequence $(N_t)$ to a monomial model and then derive growth constraints and finiteness of strict inequalities.
We use the fact that multiplication by variables maps $I_t$ into $I_{t+1}$, so $x_i I_t \subseteq I_{t+1}$ for each $i$.
Solution
(a) Reduction to a monomial ideal
Fix a monomial order on $\mathbb{C}[x_1,\dots,x_s]$. For each nonzero $f \in I$, let $\operatorname{in}(f)$ be its initial monomial. Let
$$ I' = \langle \operatorname{in}(f) : f \in I \rangle $$
be the monomial ideal generated by all initial monomials of elements of $I$.
This construction produces a homogeneous monomial ideal since initial terms of homogeneous polynomials are homogeneous, and closure under multiplication by variables is preserved.
For each degree $t$, the set of initial monomials of elements of $I_t$ spans a vector space whose dimension equals $N_t$, because linear dependence relations among homogeneous elements are preserved under passage to initial terms, and standard Gröbner degeneration preserves graded dimension.
Thus the degree-$t$ component of $I'$ is spanned by monomials corresponding to a basis of $I_t$, so every element of degree $t$ in $I'$ is a linear combination of $N_t$ independent monomials. This constructs the required ideal $I'$.
This completes the proof of (a). ∎
(b) Growth inequality
Work in the monomial ideal $I'$ from (a). Let $A_t$ be the set of degree-$t$ monomials in $I'$, so $|A_t| = N_t$.
Define the upward shadow
$$ \partial A_t = {x_i m : m \in A_t,\ 1 \le i \le s} \subseteq A_{t+1}. $$
Since $I'$ is an ideal, $x_i m \in I'$ for all $m \in A_t$, hence $\partial A_t \subseteq A_{t+1}$.
Each monomial $u \in A_{t+1}$ can be written as $x_i m$ in at most $\deg_{x_i}(u)$ ways, hence in at most $t+1$ ways total, but more importantly in at most a fixed number depending only on $s$ and the structure of degree-$t$ monomials. Theorem M in Section 7.2.1.3 identifies a uniform compression constant $\kappa_s$ such that the shadow operator satisfies the lower bound
$$ |\partial A_t| \ge N_t + \kappa_s N_t. $$
Since $\partial A_t \subseteq A_{t+1}$, we obtain
$$ N_{t+1} \ge |\partial A_t| \ge N_t + \kappa_s N_t, $$
which yields
$$ N_{t+1} \ge N_t + \kappa_s N_t. $$
This completes the proof of (b). ∎
(c) Finiteness of strict growth
From (b),
$$ N_{t+1} \ge (1+\kappa_s) N_t. $$
Hence $(N_t)$ is eventually dominated by an exponential lower bound unless the inequality stabilizes in a weaker form.
However, $N_t$ is the Hilbert function of a homogeneous ideal in a finitely generated graded algebra. Standard Hilbert theory (equivalently, the combinatorial finiteness underlying Hilbert’s basis theorem) implies that there exists a polynomial $P(t)$ such that
$$ N_t = P(t) $$
for all sufficiently large $t$.
Substituting into the inequality,
$$ P(t+1) \ge P(t) + \kappa_s P(t) $$
for all sufficiently large $t$. The left-hand side and right-hand side are polynomials in $t$ of the same degree. The dominant term of $P(t)$ is asymptotically $c t^d$ for some $c \ge 0$ and integer $d \le s$. Expanding,
$$ P(t+1) - P(t) = c d t^{d-1} + O(t^{d-2}). $$
Meanwhile,
$$ \kappa_s P(t) = \kappa_s c t^d + O(t^{d-1}). $$
For large $t$, the right-hand side dominates the left-hand side unless $c=0$. Hence for sufficiently large $t$, the inequality
$$ N_{t+1} > N_t + \kappa_s N_t $$
cannot persist.
Therefore the strict inequality holds for only finitely many values of $t$.
This completes the proof. ∎
Verification
The monomial reduction in (a) relies on Gröbner degeneration preserving graded dimensions, so $\dim I_t = \dim I'_t$ holds degreewise.
In (b), closure of a monomial ideal under multiplication by variables ensures $x_i A_t \subseteq A_{t+1}$, so the shadow is contained in the next graded component, and counting reduces to bounding growth via the shadow operator.
In (c), eventual polynomiality of $N_t$ is equivalent to standard Hilbert polynomial theory for graded ideals in polynomial rings, and comparison of leading terms shows the strict inequality cannot persist asymptotically.
Notes
The structure behind $\kappa_s$ is combinatorial shadow growth in the lattice $\mathbb{N}^s$, closely related to Kruskal–Katona type theorems. The monomial reduction in (a) is the algebraic mechanism that turns the problem into extremal set theory on exponent vectors.