Proofs: Regular chain

Correctness of the regular chain operations full

This proof shows: correctness.

We prove that the three operations of the page are correct: pseudo-reduction by a chain, the membership test for the saturated ideal, and the regularity test by iterated resultants. The test for a regular chain is then correct by induction on its length.

Setting. $K$ is a field and $X = (x_1 < \cdots < x_n)$. A triangular set $T = (T_1, \ldots, T_r)$ in $K[X]$ has main variables $y_1 < \cdots < y_r$, main degrees $d_k = \deg_{y_k} T_k \ge 1$ and initials $h_k = \operatorname{init}(T_k)$. Let $h = h_1 \cdots h_r$, $(T)$ the ideal generated by $T$, and $\operatorname{sat}(T) = (T) : h^\infty = \{p : h^e p \in (T) \text{ for some } e\}$. A polynomial $p$ is reduced with respect to $T$ when $\deg_{y_k} p < d_k$ for all $k$. A polynomial $p$ is regular modulo an ideal $J$ when $p$ is not a zero divisor in $K[X]/J$, that is $p q \in J$ implies $q \in J$. We take the convention that $0$ is a zero divisor, so $p \in J$ is never regular. $T$ is a regular chain when $h_k$ is regular modulo $\operatorname{sat}(T_1, \ldots, T_{k-1})$ for each $k$.

Lemma 1 (pseudo-reduction). Let $r = \operatorname{prem}(p, T)$ as computed by PREM-CHAIN. Then $r$ is reduced with respect to $T$, and $h^e p - r \in (T)$ for some $e \ge 0$.

Proof. One pseudo-division of $f$ by $T_k$ replaces $f$ by $h_k f - c\, y_k^{m - d_k} T_k$, where $m = \deg_{y_k} f$ and $c$ is the leading coefficient of $f$ in $y_k$. This removes the term of degree $m$ in $y_k$ and does not raise the degree in $y_k$. So the loop ends with $\deg_{y_k} f < d_k$, and $f$ changes by a multiple of $h_k$ and an element of $(T)$. PREM-CHAIN reduces by $T_r$ first and then by $T_{r-1}, \ldots, T_1$. When it reduces by $T_k$, the polynomials $h_k$ and $T_k$ contain no $y_j$ with $j > k$, so the degree in each such $y_j$ does not grow, and the reductions already done stay valid. Collecting the factors gives $h_r^{e_r} \cdots h_1^{e_1} p - r \in (T)$, and multiplying by more initials gives the form $h^e p - r \in (T)$. $\square$

The tower. Let $U$ be the variables of $X$ that are not main variables, $F = K(U)$, and $S = K[U] \setminus \{0\}$. Then $F[Y] = S^{-1} K[X]$ with $Y = (y_1, \ldots, y_r)$, and $K[X] \subset F[Y]$. Note that $h_k$ and the coefficients of $T_k$ in $y_k$ lie in $F[y_1, \ldots, y_{k-1}]$, because they contain only variables smaller than $y_k$.

Lemma 2 (localization). Let $I$ be an ideal of $F[Y]$ and $J = I \cap K[X]$. Then $K[X]/J$ embeds in $F[Y]/I$, and $a \in K[X]$ is regular modulo $J$ if and only if $a$ is not a zero divisor in $F[Y]/I$.

Proof. The map $K[X]/J \to F[Y]/I$ has kernel $I \cap K[X] = J$, so it is injective. If $a b \in J$ with $b \notin J$, then $a b = 0$ in $F[Y]/I$ and $b \ne 0$ there. Conversely, let $a (b/s) \in I$ with $b/s \notin I$, $b \in K[X]$, $s \in S$. Then $a b = s \cdot a (b/s) \in I \cap K[X] = J$, and $b \notin J$ because $b/s \notin I$ and $s$ is a unit of $F[Y]$. $\square$

Lemma 3 (structure). Let $T$ be a regular chain. Define $R_0 = F$ and, for $k = 1, \ldots, r$, $R_k = R_{k-1}[y_k]/(T_k)$. Then for each $k$:

• (a) $h_k$ is a unit of $R_{k-1}$, and $R_k = R_{k-1}[y_k]/(M_k)$ with the monic polynomial $M_k = h_k^{-1} T_k$ of degree $d_k$;
• (b) $R_k$ is an $F$-vector space with basis the reduced monomials $y_1^{a_1} \cdots y_k^{a_k}$, $0 \le a_j < d_j$; in particular $\dim_F R_k = d_1 \cdots d_k \ge 1$;
• (c) with $I_k$ the kernel of $F[Y] \to R_k[y_{k+1}, \ldots, y_r]$, we have $\operatorname{sat}(T_1, \ldots, T_k) = I_k \cap K[X]$, and a polynomial $p \in K[X]$ is in $\operatorname{sat}(T_1, \ldots, T_k)$ if and only if $\operatorname{prem}(p, (T_1, \ldots, T_k)) = 0$.

Proof. Induction on $k$. For $k = 0$ there is nothing in (a), (b) holds with the basis $\{1\}$, and (c) says $\{0\} = \{0\}$, since $I_0 = 0$ and $\operatorname{prem}(p, \emptyset) = p$.

Let $k \ge 1$. (a) By hypothesis $h_k$ is regular modulo $\operatorname{sat}(T_1, \ldots, T_{k-1}) = I_{k-1} \cap K[X]$. By Lemma 2, $h_k$ is not a zero divisor in $R_{k-1}[y_k, \ldots, y_r]$. Since $h_k$ contains none of $y_k, \ldots, y_r$, it multiplies the coefficients of a polynomial separately, so $h_k$ is not a zero divisor in $R_{k-1}$. By (b), $R_{k-1}$ is a finite-dimensional $F$-vector space, and multiplication by $h_k$ is an injective $F$-linear map of it to itself, hence onto. So $h_k u = 1$ for some $u$, and $h_k$ is a unit. Then $(T_k) = (M_k)$ in $R_{k-1}[y_k]$, and $M_k$ is monic of degree $d_k$.

(b) Division by the monic $M_k$ shows that $R_{k-1}[y_k]/(M_k)$ is a free $R_{k-1}$-module with basis $1, y_k, \ldots, y_k^{d_k - 1}$. Combined with the basis of $R_{k-1}$ this gives the stated $F$-basis.

(c) Let $T_{\le k} = (T_1, \ldots, T_k)$ and $g = h_1 \cdots h_k$. In $R_k$ every $T_j$ with $j \le k$ is $0$ and $g$ is a unit by (a) at each level. If $p \in \operatorname{sat}(T_{\le k})$, then $g^e p \in (T_{\le k})$, so $g^e p = 0$ in $R_k[y_{k+1}, \ldots]$, so $p = 0$ there, that is $p \in I_k$. Now let $p \in I_k \cap K[X]$ and $\rho = \operatorname{prem}(p, T_{\le k})$. By Lemma 1, $g^e p - \rho \in (T_{\le k}) \subset I_k$, so $\rho \in I_k$. The polynomial $\rho$ is reduced, so as a polynomial in $y_{k+1}, \ldots, y_r$ its coefficients are $F$-combinations of reduced monomials in $y_1, \ldots, y_k$. Its image in $R_k[y_{k+1}, \ldots]$ is $0$, and by the basis in (b) all these combinations are $0$. So $\rho = 0$ as a polynomial, hence $g^e p \in (T_{\le k})$ and $p \in \operatorname{sat}(T_{\le k})$. This proves $I_k \cap K[X] = \operatorname{sat}(T_{\le k})$, and the proof also showed that every $p$ in this ideal has $\operatorname{prem}(p, T_{\le k}) = 0$. Conversely, $\operatorname{prem}(p, T_{\le k}) = 0$ gives $g^e p \in (T_{\le k})$ by Lemma 1, so $p \in \operatorname{sat}(T_{\le k})$. $\square$

Theorem 1 (membership). For a regular chain $T$, IN-SAT returns true if and only if $p \in \operatorname{sat}(T)$.

Proof. This is Lemma 3 (c) with $k = r$. $\square$

Lemma 4 (norm). Let $A$ be a commutative ring, $M \in A[y]$ monic of degree $d \ge 1$, $a \in A[y]$ of formal degree $m \ge 0$ (all coefficients up to $y^m$ given, the top one possibly $0$), and $\mu_a$ the multiplication by $a$ on the free $A$-module $B = A[y]/(M)$ with basis $1, \ldots, y^{d-1}$. Then $\operatorname{Res}_{d,m}(M, a) = \det \mu_a$, where $\operatorname{Res}_{d,m}$ is the determinant of the Sylvester matrix with these formal degrees. Also $a$ is a unit of $B$ if and only if $\operatorname{Res}_{d,m}(M, a)$ is a unit of $A$.

Proof. Both sides are polynomials with integer coefficients in the $d$ lower coefficients of $M$ and the $m + 1$ coefficients of $a$, so it suffices to prove the identity over $\mathbb{Z}[\text{coefficients}]$, and for that over $\mathbb{C}$ on a dense set of values. Over $\mathbb{C}$ with $M = \prod_i (y - \alpha_i)$ and distinct $\alpha_i$, $B \cong \mathbb{C}^d$ by $f \mapsto (f(\alpha_i))_i$, so $\det \mu_a = \prod_i a(\alpha_i)$. The Poisson formula for a monic first argument gives $\operatorname{Res}_{d,m}(M, a) = \prod_i a(\alpha_i)$ as well; it holds for formal degrees because a zero top coefficient of $a$ only changes the second block of rows of the Sylvester matrix, and both sides are polynomial in that coefficient. For the second claim, $a$ is a unit of $B$ if and only if $\mu_a$ is bijective, and an $A$-linear endomorphism of a free module of finite rank is bijective if and only if its determinant is a unit (the adjugate gives the inverse; conversely $\det(\mu_a) \det(\mu_{a^{-1}}) = \det(\mu_1) = 1$). $\square$

Theorem 2 (regularity). Let $T$ be a regular chain and $p \in K[X]$. IS-REGULAR returns true if and only if $p$ is regular modulo $\operatorname{sat}(T)$.

Proof. By Lemma 3 (c) with $k = r$ and Lemma 2, $p$ is regular modulo $\operatorname{sat}(T)$ if and only if $p$ is not a zero divisor in $R_r$, since every main variable is in $R_r$ and $F[Y]/I_r = R_r$. As $R_r$ is finite-dimensional over $F$, this holds if and only if $p$ is a unit of $R_r$ (the argument of Lemma 3 (a)); and $0$ is not a unit since $\dim_F R_r \ge 1$.

The algorithm first replaces $p$ by $\rho = \operatorname{prem}(p, T)$. By Lemma 1, $h^e p - \rho \in (T)$, so $p$ and $\rho$ differ by the unit $h^e$ in $R_r$, and one is a unit if and only if the other is. If $\rho = 0$ the answer false is correct. Otherwise the algorithm computes $\rho_r = \rho$ and $\rho_{k-1} = \operatorname{Res}_{y_k}(\rho_k, T_k)$ for $k = r, \ldots, 1$, where a step with $\deg_{y_k} \rho_k \le 0$ keeps $\rho_{k-1} = \rho_k$. We show by downward induction that $\rho_k$ is a unit of $R_k$ if and only if $\rho_{k-1}$ is a unit of $R_{k-1}$. The resultant is a polynomial in the coefficients, so it commutes with the map $K[U][y_1, \ldots, y_{k-1}] \to R_{k-1}$, provided the formal degrees $m = \deg_{y_k} \rho_k$ and $d_k$ are kept, which the code does since it builds the Sylvester matrix from the degrees in $K[X]$. In $R_{k-1}[y_k]$ we have $T_k = h_k M_k$, and scaling the $m$ rows of $T_k$ in the Sylvester matrix gives $\operatorname{Res}(T_k, \rho_k) = h_k^m \operatorname{Res}(M_k, \rho_k)$; swapping the arguments changes only the sign. Since $h_k$ is a unit, Lemma 4 with $A = R_{k-1}$ gives the claim. In a step with $\deg_{y_k} \rho_k \le 0$, the element $\rho_k$ lies in $R_{k-1}$, and multiplication by it on the free $R_{k-1}$-module $R_k$ has determinant $\rho_k^{d_k}$, so again $\rho_k$ is a unit of $R_k$ if and only if it is a unit of $R_{k-1}$. At the end $\rho_0 \in K[U] \subset F = R_0$, which is a unit if and only if it is not $0$. $\square$

Theorem 3 (chain test). IS-REGULAR-CHAIN returns true if and only if $T$ is a regular chain.

Proof. Line R3 rejects exactly the sets that are not triangular (a constant, or main variables not strictly increasing). For $k = 1$ the initial $h_1 \ne 0$ is regular modulo $\operatorname{sat}(\emptyset) = 0$, because $K[X]$ is a domain, so the loop starts at the second polynomial. When the loop reaches index $k$, all earlier tests passed, so $(T_1, \ldots, T_{k-1})$ is a regular chain, and by Theorem 2 the call IS-REGULAR$(h_k, T_{<k})$ answers exactly the condition of the definition for $T_k$. So the loop returns true if and only if every condition holds. $\square$

Termination. Every pseudo-division loop lowers the degree in the main variable, the chain loops are bounded by $r$, and Bareiss elimination on an $(m + d) \times (m + d)$ Sylvester matrix uses a bounded number of exact polynomial divisions, each exact by Sylvester's identity. $\blacksquare$