TAOCP 4.6.4 Exercise 28

Section 4.6.4: Evaluation of Polynomials

Exercise 28. [HM20] Show that if $f_0(\alpha_1, \ldots, \alpha_s), \ldots, f_r(\alpha_1, \ldots, \alpha_s)$ are multivariate polynomials with integer coefficients, then there is a nonzero polynomial $g(x_0, \ldots, x_r)$ with integer coefficients such that $g(f_0(\alpha_1, \ldots, \alpha_s), \ldots, f_r(\alpha_1, \ldots, \alpha_s)) = 0$ for all real $\alpha_1, \ldots, \alpha_s$. (Hence any polynomial chain with $s$ parameters has at most $s$ degrees of freedom.) Hint: Use the theorems about "algebraic dependence" that are found, for example, in B. L. van der Waerden's Modern Algebra, translated by Fred Blum (New York: Ungar, 1949), Section 64.

Verified: yes
Solve time: 4m37s

---

Solution

Let

$$ f_0(\alpha_1,\ldots,\alpha_s),; f_1(\alpha_1,\ldots,\alpha_s),; \ldots,; f_r(\alpha_1,\ldots,\alpha_s) $$

be polynomials with integer coefficients. We must prove that there exists a nonzero polynomial

$$ g(x_0,\ldots,x_r)\in \mathbf Z[x_0,\ldots,x_r] $$

such that

$$ g\bigl(f_0(\alpha),\ldots,f_r(\alpha)\bigr)=0 $$

for all real values of $\alpha=(\alpha_1,\ldots,\alpha_s)$.

Consider the polynomial ring

$$ R=\mathbf Z[x_0,\ldots,x_r,\alpha_1,\ldots,\alpha_s]. $$

Define the ideal

$$ I= \bigl( x_0-f_0(\alpha),, x_1-f_1(\alpha),, \ldots,, x_r-f_r(\alpha) \bigr) \subseteq R. $$

The quotient ring $R/I$ is obtained by replacing each $x_i$ by

$f_i(\alpha)$; hence

$$ R/I \cong \mathbf Z[\alpha_1,\ldots,\alpha_s]. $$

Therefore the image of the subring

$\mathbf Z[x_0,\ldots,x_r]$ inside $R/I$ has transcendence degree at most

$s$.

Now there are $r+1$ elements

$$ x_0,\ldots,x_r $$

in that image. When $r+1>s$, the theorem on algebraic dependence

(van der Waerden, Section 64) implies that these elements satisfy a nontrivial polynomial relation over $\mathbf Z$. Consequently,

$$ I\cap \mathbf Z[x_0,\ldots,x_r] \neq {0}. $$

Choose a nonzero polynomial

$$ g(x_0,\ldots,x_r)\in I\cap \mathbf Z[x_0,\ldots,x_r]. $$

Since $g\in I$, there exist polynomials

$h_0,\ldots,h_r\in R$ such that

$$ g(x_0,\ldots,x_r) = \sum_{i=0}^{r} h_i\bigl(x_i-f_i(\alpha)\bigr). $$

Substituting

$$ x_i=f_i(\alpha)\qquad(0\le i\le r) $$

makes every term on the right-hand side vanish. Hence

$$ g\bigl(f_0(\alpha),\ldots,f_r(\alpha)\bigr)=0 $$

identically in $\alpha_1,\ldots,\alpha_s$.

Thus there exists a nonzero polynomial with integer coefficients satisfying

$$ g\bigl(f_0(\alpha_1,\ldots,\alpha_s),\ldots, f_r(\alpha_1,\ldots,\alpha_s)\bigr)=0 $$

for all real $\alpha_1,\ldots,\alpha_s$.

The parenthetical conclusion follows immediately. If a polynomial chain has only $s$ parameters, every quantity produced by the chain is an integer-coefficient polynomial in those $s$ parameters. By the result just proved, any collection of more than $s$ output coordinates is algebraically dependent. Therefore the set of all outputs cannot have more than $s$ degrees of freedom.

This completes the proof.

∎