TAOCP 4.6.4 Exercise 27

**Corrected Solution.

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 27. [**] [M22] Let $R$ be a set that includes all $(n+1)$-tuples $(q_n, \ldots, q_1, q_0)$ of real numbers such that $q_n \ne 0$; prove that $R$ does not have at most $n$ degrees of freedom.

Verified: yes
Solve time: 8m33s

Corrected Solution.

We are asked to prove that the set

$$ R = { (q_n, q_{n-1}, \dots, q_0) \in \mathbb{R}^{n+1} : q_n \ne 0 } $$

does not have at most $n$ degrees of freedom.

Solution.

Suppose, for the sake of contradiction, that $R$ has at most $n$ degrees of freedom. By definition, this means there exist $n$ real parameters $p_1, \dots, p_n$ and functions

$$ f_0, f_1, \dots, f_n : \mathbb{R}^n \to \mathbb{R} $$

such that every $(q_n, q_{n-1}, \dots, q_0) \in R$ can be expressed as

$$ q_k = f_k(p_1, \dots, p_n), \qquad 0 \le k \le n. $$

Define the map

$$ F : \mathbb{R}^n \to \mathbb{R}^{n+1}, \qquad F(p_1, \dots, p_n) = \bigl(f_n(p_1, \dots, p_n), \dots, f_0(p_1, \dots, p_n)\bigr). $$

By assumption, the image of $F$ is exactly $R$.

Observe that

$$ R = { (q_n, \dots, q_0) \in \mathbb{R}^{n+1} : q_n \ne 0 }. $$

The set ${ q_n \ne 0 }$ is open in $\mathbb{R}^{n+1}$ because it is the preimage of the open set $\mathbb{R} \setminus {0}$ under the continuous projection

$$ (q_n, \dots, q_0) \mapsto q_n. $$

Therefore, $R$ is an open subset of $\mathbb{R}^{n+1}$.

Now, consider the general fact from topology: if $n < m$, the image of any continuous map from $\mathbb{R}^n$ to $\mathbb{R}^m$ cannot contain a nonempty open set in $\mathbb{R}^m$. More precisely, by Brouwer's invariance of domain theorem, a continuous injective map from $\mathbb{R}^n$ to $\mathbb{R}^{n+1}$ has image that is homeomorphic to $\mathbb{R}^n$ and thus cannot contain an open subset of $\mathbb{R}^{n+1}$. Even without injectivity, a standard result in topology states that the image of $\mathbb{R}^n$ under a continuous map into $\mathbb{R}^{n+1}$ has empty interior.

Therefore, no map $F : \mathbb{R}^n \to \mathbb{R}^{n+1}$ can have an open set of $\mathbb{R}^{n+1}$ as its image.

But $R$ itself is an open set in $\mathbb{R}^{n+1}$, and we assumed that $F(\mathbb{R}^n) = R$. This is a contradiction.

Hence, the assumption that $R$ has at most $n$ degrees of freedom is false.

Therefore, $R$ does not have at most $n$ degrees of freedom.

$$ \boxed{\text{Q.E.D.}} $$

Remarks.

  1. This argument avoids any assumption of differentiability. The contradiction follows purely from topological dimension considerations.
  2. The openness of $R$ ensures that it is $(n+1)$-dimensional in the sense needed for the degrees-of-freedom argument.
  3. Consequently, any parametrization requires more than $n$ parameters, so $R$ has strictly more than $n$ degrees of freedom.