Proofs: Rational univariate representation

The RUR algorithm returns a rational univariate representation of the zeros full

This proof shows: correctness.

Setting. $K$ is a field of characteristic $0$ with algebraic closure $\overline{K}$, and $I \subseteq K[x_1, \ldots, x_n]$ is generated by the finite set $F$. We use the notation of the page: $A = K[x_1, \ldots, x_n] / I$, $D = \dim_K A$, $V(I) = \{\alpha_1, \ldots, \alpha_r\} \subset \overline{K}^n$, $\mu(\alpha)$ the multiplicity, $M_v$ the matrix of multiplication by $v$ in the basis $B$, and $\operatorname{Tr}(v) = \operatorname{tr}(M_v)$.

Theorem. If $I$ is zero-dimensional, RUR returns $(u, \bar f, g_1, g_{x_1}, \ldots, g_{x_n})$ with all polynomials in $K[T]$, $u$ separating, $\bar f = \prod_{\alpha \in V(I)} (T - u(\alpha))$, $g_1(u(\alpha)) \ne 0$ and $g_{x_i}(u(\alpha)) / g_1(u(\alpha)) = \alpha_i$ for every $\alpha \in V(I)$ and every $i$. So the map $t \mapsto (g_{x_1}(t) / g_1(t), \ldots, g_{x_n}(t) / g_1(t))$ is a bijection from the roots of $\bar f$ to $V(I)$, with inverse $\alpha \mapsto u(\alpha)$. If $I$ is not zero-dimensional, L1 stops with an error. If $I = (1)$, the output is $\bar f = 1$.

Lemma 1 (steps L1 and L2)

$G$ is a Gröbner basis of $I$ by Buchberger's theorem: the loop treats every pair or removes it by the coprime criterion or by Buchberger's chain criterion in the form "some $k \ne i, j$ has $\mathrm{LM}(g_k) \mid L_{ij}$ and the pairs $(i, k)$ and $(j, k)$ are no longer pending", and both criteria keep the conclusion (CLO, Chapter 2, Section 10). The selection order does not matter for correctness. Interreduction and scaling give the reduced basis.

By the theory of Gröbner bases, the monomials not in $\langle \mathrm{LM}(G) \rangle$, the set $B$, form a basis of $A$, and the normal form of $f$ is the unique combination of $B$ congruent to $f$ modulo $I$. The set $B$ is finite exactly when every variable $x_i$ has a power $x_i^{k}$ among the leading monomials (finiteness theorem, CLO, Chapter 5, Section 3), and $B$ is finite exactly when $V(I)$ is finite. So the error in L1 is raised exactly for ideals that are not zero-dimensional. If $1 \in G$, then $I = (1)$, $B = \emptyset$ and $V(I) = \emptyset$, and the output $\bar f = 1$ has no roots, as required.

Column $b$ of $M_i$ holds the coordinates of the normal form of $x_i b$, so $M_i$ is the matrix of multiplication by $x_i$ on $A$. Multiplication gives a ring homomorphism $A \to \operatorname{End}_K(A)$, $v \mapsto M_v$. So $M_{x_i b'} = M_i M_{b'}$, which is how L3 builds $M_b$ (the set $B$ is closed under division, so $b' = b / x_i \in B$), and $M_u = \sum_i \lambda^{i-1} M_i$ in L5.

Lemma 2 (Stickelberger)

For every $v \in A$, the characteristic polynomial of $M_v$ is $\prod_{\alpha \in V(I)} (T - v(\alpha))^{\mu(\alpha)}$. In particular $\operatorname{Tr}(v) = \sum_\alpha \mu(\alpha)\, v(\alpha)$.

Proof. The characteristic polynomial does not change when we extend scalars to $\overline{K}$, so we work in $\bar A = \overline{K}[x] / I \overline{K}[x]$, which has the same matrices $M_v$. Since $V(I)$ is finite, $I \overline{K}[x]$ is the intersection of primary ideals $Q_\alpha$, one for each $\alpha \in V(I)$, with $\sqrt{Q_\alpha} = \mathfrak{m}_\alpha$, the maximal ideal of $\alpha$. Distinct maximal ideals are comaximal, hence so are the $Q_\alpha$, and the Chinese remainder theorem gives $\bar A \cong \prod_\alpha \overline{K}[x] / Q_\alpha$. This decomposition is stable under multiplication by $v$, and $\mu(\alpha) = \dim \overline{K}[x] / Q_\alpha$ by definition. On the factor at $\alpha$, $v - v(\alpha) \in \mathfrak{m}_\alpha$, and $\mathfrak{m}_\alpha^k \subseteq Q_\alpha$ for some $k$, so multiplication by $v - v(\alpha)$ is nilpotent there. Hence multiplication by $v$ on that factor has the single eigenvalue $v(\alpha)$ with algebraic multiplicity $\mu(\alpha)$, and the characteristic polynomial of $M_v$ is the product of these. $\square$

Lemma 3 (step L3)

The rank $r$ of the Hermite matrix $H = (\operatorname{Tr}(b c))_{b, c \in B}$ equals $|V(I)|$.

Proof. By Lemma 2 applied to $v = ac$, the symmetric bilinear form $\langle a, c \rangle = \operatorname{Tr}(ac)$ on $A \otimes \overline{K}$ is $\sum_\alpha \mu(\alpha)\, \ell_\alpha(a)\, \ell_\alpha(c)$, where $\ell_\alpha(a) = a(\alpha)$ is evaluation at $\alpha$, a well-defined linear form on $\bar A$ since $I$ vanishes at $\alpha$. The forms $\ell_\alpha$ are linearly independent: for distinct points there are polynomials $p_\beta$ with $p_\beta(\alpha) = 1$ if $\alpha = \beta$ and $0$ otherwise (products of linear forms that separate the points), so $\sum_\alpha c_\alpha \ell_\alpha = 0$ gives $c_\beta = 0$ when applied to $p_\beta$. So the matrix of the form is $L^{\mathsf T} \operatorname{diag}(\mu(\alpha)) L$ with $L$ the $r \times D$ matrix of the $\ell_\alpha$ in the basis $B$, of rank $r$, and the $\mu(\alpha)$ are nonzero in characteristic $0$. So the rank is $r$. The rank of a matrix with entries in $K$ is the same over $K$ and over $\overline{K}$, and L3 computes it by exact elimination. $\square$

Lemma 4 (steps L5 to L8)

For a given $\lambda$, L7 returns $\bar f = \prod_{c \in u(V(I))} (T - c)$, and L8 exits exactly when $u$ is separating.

Proof. By Lemma 2, the eigenvalues of $M_u$ with algebraic multiplicity are the values $u(\alpha)$, each $\mu(\alpha)$ times, and the eigenvalues of $M_u^j$ are their $j$-th powers. So $s_j = \operatorname{tr}(M_u^j) = \sum_\alpha \mu(\alpha) u(\alpha)^j$ are the power sums of the $D$ roots of $f_u = \prod_\alpha (T - u(\alpha))^{\mu(\alpha)}$. Newton's identities $k e_k = \sum_{i=1}^{k} (-1)^{i-1} e_{k-i} s_i$ determine the elementary symmetric functions $e_1, \ldots, e_D$ of these roots, since $k$ is invertible in characteristic $0$, and $f_u = \sum_k (-1)^k e_k T^{D-k}$. In characteristic $0$, $f / \gcd(f, f')$ is the product of $(T - c)$ over the distinct roots $c$ of $f$. So $d$ is the number of distinct values of $u$ on $V(I)$. This equals $r = |V(I)|$ by Lemma 3 exactly when $u$ takes distinct values at distinct zeros. $\square$

Lemma 5 (termination of L4)

At most $(n - 1) \binom{r}{2}$ values of $\lambda \in \{0, 1, 2, \ldots\}$ give a form $u$ that is not separating, so the loop ends after at most $(n - 1) \binom{r}{2} + 1 \le (n - 1) \binom{D}{2} + 1$ trials.

Proof. For distinct $\alpha, \beta \in V(I)$, $u(\alpha) - u(\beta) = \sum_{i=1}^{n} \lambda^{i-1} (\alpha_i - \beta_i)$ is a polynomial in $\lambda$ of degree at most $n - 1$ (with $\lambda^0 = 1$ also at $\lambda = 0$) that is not identically zero, since some $\alpha_i \ne \beta_i$. It has at most $n - 1$ roots in $\overline{K}$. A value of $\lambda$ fails only if it is a root for some of the $\binom{r}{2}$ pairs. The integers $0, 1, 2, \ldots$ are distinct elements of $K$ in characteristic $0$, so among the first $(n - 1) \binom{r}{2} + 1$ of them at least one succeeds. $\square$

Lemma 6 (step L9)

Let $u$ be separating, $c_\alpha = u(\alpha)$ and $\bar f = \sum_{i=0}^{d} a_i T^i$ with $a_d = 1$. Then for every $v \in A$,

Proof. First, for every $c$,

where we put $i = d - m$ and used $\sum_{j=0}^{i-1} c^j T^{i-1-j} = (T^i - c^i)/(T - c)$. For a root $c = c_\alpha$ of $\bar f$, this is $\bar f(T) / (T - c_\alpha) = \prod_{\beta \ne \alpha} (T - c_\beta)$, since the $c_\beta$ are distinct. Second, by Lemma 2 applied to $v u^j$, $\operatorname{Tr}(v u^j) = \sum_\alpha \mu(\alpha) v(\alpha) c_\alpha^j$, and $\operatorname{tr}(M_v M_u^j)$ in L9 is this trace by Lemma 1. Exchanging the two finite sums gives the claim. $\square$

Proof of the theorem

By Lemma 1, L1 and L2 are correct, and the cases of the unit ideal and of ideals that are not zero-dimensional are handled. By Lemma 5 the loop ends, and by Lemma 4 the final $u$ is separating and $\bar f = \prod_\alpha (T - u(\alpha))$, a product over the $r$ zeros since $u$ is injective on $V(I)$. By Lemma 6, $g_1$ and the $g_{x_i}$ are the polynomials of the definition. Evaluating at $c_\alpha$, every term with $\beta$ in place of $\alpha$ contains the factor $c_\alpha - c_\alpha = 0$, so

With $v = 1$ this is nonzero, because $\mu(\alpha) \ne 0$ in characteristic $0$ and the $c_\beta$ are distinct. Dividing the case $v = x_i$ by the case $v = 1$ gives $g_{x_i}(c_\alpha) / g_1(c_\alpha) = \alpha_i$. Every root of $\bar f$ is some $c_\alpha$, and distinct zeros give distinct roots, so the map of the theorem is a bijection with inverse $\alpha \mapsto u(\alpha)$. Finally, all matrices have entries in $K$, so all traces, $\bar f$ and the $g_v$ have coefficients in $K$. $\blacksquare$