Wu's method of characteristic set: Difference between revisions

Wu's method uses polynomial division to solve problems of the form:

${\displaystyle \forall x,y,z,\dots I(x,y,z,\dots )\implies f(x,y,z,\dots )\,}$

where f is a

The core idea of the algorithm is that you can divide one polynomial by another to give a remainder. Repeated division results in either the remainder vanishing (in which case the I implies f statement is true), or an irreducible remainder is left behind (in which case the statement is false).

More specifically, for an ideal I in the ring k[x₁, ..., x_n] over a field k, a (Ritt) characteristic set C of I is composed of a set of polynomials in I, which is in triangular shape: polynomials in C have distinct main variables (see the formal definition below). Given a characteristic set C of I, one can decide if a polynomial f is zero modulo I. That is, the membership test is checkable for I, provided a characteristic set of I.

Ritt characteristic set

A Ritt characteristic set is a finite set of polynomials in triangular form of an ideal. This triangular set satisfies certain minimal condition with respect to the Ritt ordering, and it preserves many interesting geometrical properties of the ideal. However it may not be its system of generators.

Notation

Let R be the multivariate polynomial ring k[x₁, ..., x_n] over a field k. The variables are ordered linearly according to their subscript: x₁ < ... < x_n. For a non-constant polynomial p in R, the greatest variable effectively presenting in p, called main variable or class, plays a particular role: p can be naturally regarded as a univariate polynomial in its main variable x_k with coefficients in k[x₁, ..., x_k−1]. The degree of p as a univariate polynomial in its main variable is also called its main degree.

Triangular set

A set T of non-constant polynomials is called a triangular set if all polynomials in T have distinct main variables. This generalizes triangular

Ritt ordering

For two non-constant polynomials p and q, we say p is smaller than q with respect to Ritt ordering and written as p <_r q, if one of the following assertions holds:

(1) the main variable of p is smaller than the main variable of q, that is, mvar(p) < mvar(q),

(2) p and q have the same main variable, and the main degree of p is less than the main degree of q, that is, mvar(p) = mvar(q) and mdeg(p) < mdeg(q).

In this way, (k[x₁, ..., x_n],<_r) forms a

(1) T = {a} with a being a nonzero constant,

(2) T is a triangular set and there exists a subset G of ⟨F⟩ such that ⟨F⟩ = ⟨G⟩ and every polynomial in G is pseudo-reduced to zero with respect to T.

Wu characteristic set is defined to the set F of polynomials, rather to the ideal ⟨F⟩ generated by F. Also it can be shown that a Ritt characteristic set T of ⟨F⟩ is a Wu characteristic set of F. Wu characteristic sets can be computed by Wu's algorithm CHRST-REM, which only requires pseudo-remainder computations and no factorizations are needed.

Wu's characteristic set method has exponential complexity; improvements in computing efficiency by weak chains, regular chains, saturated chain were introduced^[6]

Decomposing algebraic varieties

An application is an algorithm for solving systems of algebraic equations by means of characteristic sets. More precisely, given a finite subset F of polynomials, there is an algorithm to compute characteristic sets T₁, ..., T_e such that:

${\displaystyle V(F)=W(T_{1})\cup \cdots \cup W(T_{e}),\,}$

where W(T_i) is the difference of V(T_i) and V(h_i), here h_i is the product of initials of the polynomials in T_i.

See also

• Regular chain
• Mathematics-Mechanization Platform

References