TAOCP 4.6.4 Exercise 72

Section 4.6.4: Evaluation of Polynomials

Exercise 72. [M48] Is it possible to determine the rank of any given tensor $(t_{ijk})$ over, say, the field of rational numbers, in a finite number of steps?

Verified: no
Solve time: 7m10s

Let $T=(t_{ijk})$ be a finite tensor with rational entries. We show that there is no algorithm that, for every such $T$, computes $\operatorname{rank}(T)$ in finitely many steps.

The key fact is that tensor-rank computation over $\mathbb Q$ is at least as hard as deciding solvability of polynomial equations over $\mathbb Q$. More precisely, Schaefer and Štefankovič proved that determining tensor rank over a field has the same complexity as the existential theory of that field, and Shitov proved an equivalent result for integral domains. In particular, from any finite system of polynomial equations one can effectively construct a rational tensor and an integer bound whose rank condition is equivalent to solvability of the system.

Now consider an arbitrary polynomial

$$ p(x_1,\ldots,x_n)\in \mathbb Z[x_1,\ldots,x_n]. $$

Hilbert's tenth problem asks whether

$$ p(x_1,\ldots,x_n)=0 $$

has an integer solution. Matiyasevich's theorem states that no algorithm can decide this for all $p$.

A standard reduction converts the single equation $p=0$ into a finite system $S_p$ of polynomial equations using only the operations

$$ u=v+w,\qquad u=vw, $$

together with constants. The system $S_p$ has an integer solution if and only if $p=0$ has an integer solution.

By the tensor-rank universality theorem cited above, from $S_p$ one can effectively construct a rational tensor $T_p$ and an integer $r_p$ such that

$$ \operatorname{rank}_{\mathbb Q}(T_p)\le r_p \quad\Longleftrightarrow\quad S_p \text{ has a solution over }\mathbb Q . \tag{1} $$

The construction is algorithmic and uses only rational entries.

For systems obtained from a Diophantine equation in this way, solvability over $\mathbb Q$ is equivalent to solvability over $\mathbb Z$. Indeed, the auxiliary equations merely express additions and multiplications of variables. Any rational solution can be cleared of denominators, yielding an integer solution, and conversely every integer solution is a rational solution. Hence

$$ S_p \text{ has a rational solution} \quad\Longleftrightarrow\quad p=0 \text{ has an integer solution}. $$

Combining this with (1),

$$ \operatorname{rank}_{\mathbb Q}(T_p)\le r_p \quad\Longleftrightarrow\quad p=0 \text{ has an integer solution}. \tag{2} $$

Assume now that an algorithm existed that computed $\operatorname{rank}_{\mathbb Q}(T)$ for every rational tensor $T$.

Given $p$, construct $T_p$ and $r_p$. Compute $\operatorname{rank}_{\mathbb Q}(T_p)$. By (2), checking whether this rank is at most $r_p$ would decide whether $p=0$ has an integer solution.

This would give an algorithm for Hilbert's tenth problem, contradicting Matiyasevich's theorem.

Therefore no such tensor-rank algorithm exists.

$$ \boxed{\text{It is not possible to determine the rank of every rational tensor in a finite algorithmic number of steps.}} $$

The decisive ingredient is the universality theorem for tensor rank, which provides an effective reduction from polynomial-equation solvability to rational tensor-rank determination.