Wu's method of characteristic set


Wenjun Wu's method is an algorithm for solving multivariate polynomial equations introduced in the late 1970s by the Chinese mathematician Wen-Tsun Wu. This method is based on the mathematical concept of characteristic set introduced in the late 1940s by J.F. Ritt. It is fully independent of the Gröbner basis method, introduced by Bruno Buchberger, even if Gröbner bases may be used to compute characteristic sets.
Wu's method is powerful for mechanical theorem proving in elementary geometry, and provides a complete decision process for certain classes of problem. It has been used in research in his laboratory and around the world. The main trends of research on Wu's method concern systems of polynomial equations of positive dimension and differential algebra where Ritt's results have been made effective. Wu's method has been applied in various scientific fields, like biology, computer vision, robot kinematics and especially automatic proofs in geometry.

Informal description

Wu's method uses polynomial division to solve problems of the form:
where f is a polynomial equation and I is a conjunction of polynomial equations. The algorithm is complete for such problems over the complex domain.
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, or an irreducible remainder is left behind.
More specifically, for an ideal I in the ring k over a field k, a 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. 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 over a field k.
The variables are ordered linearly according to their subscript: x1 <... < xn.
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 xk with coefficients in k.
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 systems of linear equations in a natural way.

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:
In this way, forms a well partial order. However, the Ritt ordering is not a total order:
there exist polynomials p and q such that neither p <r q nor p >r q. In this case, we say that p and q are not comparable.
The Ritt ordering is comparing the rank of p and q. The rank, denoted by rank, of a non-constant polynomial p is defined to be a power of
its main variable: mvarmdeg and ranks are compared by comparing first the variables and then, in case of equality of the variables, the degrees.

Ritt ordering on triangular sets

A crucial generalization on Ritt ordering is to compare triangular sets.
Let T = and S = be two triangular sets
such that polynomials in T and S are sorted increasingly according to their main variables.
We say T is smaller than S w.r.t. Ritt ordering if one of the following assertions holds
Also, there exists incomparable triangular sets w.r.t Ritt ordering.

Ritt characteristic set

Let I be a non-zero ideal of k. A subset T of I is a Ritt characteristic set of I if one of the following conditions holds:
A polynomial ideal may possess many characteristic sets, since Ritt ordering is a partial order.

Wu characteristic set

The Ritt–Wu process, first devised by Ritt, subsequently modified by Wu, computes not a Ritt characteristic but an extended one, called Wu characteristic set or ascending chain.
A non-empty subset T of the ideal generated by F is a Wu characteristic set of F if one of the following condition holds
Wu characteristic set is defined to the set F of polynomials, rather to the ideal generated by F. Also it can be shown that a Ritt characteristic set T of 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

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 T1,...,
Te such that:
where W is the difference of V and V, here hi is the product of initials of the polynomials in Ti.