{"history":[],"article":{"id":"3092b2b9-93eb-4719-9118-61cc591cee84","title":"Wu's method of characteristic set","slug":"wu-s-method-of-characteristic-set","content":":::summary\n:::\n\n# \n**[Wenjun Wu](https://bliptext.com/articles/wu-wenjun)'s method** is an algorithm for solving [multivariate polynomial equations](https://bliptext.com/articles/systems-of-polynomial-equations) introduced in the late 1970s by the Chinese mathematician [Wen-Tsun Wu](https://bliptext.com/articles/wu-wenjun).\nThis method is based on the mathematical concept of **characteristic set** introduced in the late 1940s by [J.F. Ritt](https://bliptext.com/articles/joseph-ritt).\nIt is fully independent of the [Gröbner basis](https://bliptext.com/articles/gr-bner-basis) method, introduced by [Bruno Buchberger](https://bliptext.com/articles/bruno-buchberger) (1965), even if Gröbner bases may be used to compute characteristic sets.\nWu's method is powerful for [mechanical theorem proving](https://bliptext.com/articles/automatic-theorem-proving) in [elementary geometry](https://bliptext.com/articles/elementary-geometry), and provides a complete decision process for certain classes of problem.\nIt has been used in research in his laboratory (KLMM, Key Laboratory of Mathematics Mechanization in Chinese Academy of Science) and around the world.\nThe main trends of research on Wu's method concern [systems of polynomial equations](https://bliptext.com/articles/systems-of-polynomial-equations) of positive dimension and [differential algebra](https://bliptext.com/articles/differential-algebra) where [Ritt](https://bliptext.com/articles/joseph-ritt)'s results have been made effective.\nWu's method has been applied in various scientific fields, like biology, [computer vision](https://bliptext.com/articles/computer-vision), [robot kinematics](https://bliptext.com/articles/robot-kinematics) and especially [automatic proofs](https://bliptext.com/articles/automated-theorem-proving) in geometry.\n\n# Informal description\n**Wu's method** uses [polynomial](https://bliptext.com/articles/polynomial) division to solve problems of the form:\nwhere f is a [polynomial equation](https://bliptext.com/articles/polynomial-equation) and I is a [conjunction](https://bliptext.com/articles/logical-conjunction) of [polynomial equation](https://bliptext.com/articles/polynomial-equation)s.\nThe algorithm is complete for such problems over the [complex domain](https://bliptext.com/articles/complex-domain).\nThe core idea of the algorithm is that you can divide one polynomial by another to give a remainder.\nRepeated 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).\nMore specifically, for an [ideal](https://bliptext.com/articles/ideal-[ring](https://bliptext.com/articles/ring-mathematics)-theory) I in the [ring](https://bliptext.com/articles/ring-mathematics) k[x1, ..., xn] 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).\nGiven a characteristic set C of I, one can decide if a polynomial f is zero modulo I.\nThat is, the membership test is checkable for I, provided a characteristic set of I.\n\n# Ritt characteristic set\nA Ritt characteristic set is a finite set of polynomials in [triangular form](https://bliptext.com/articles/system-of-polynomial-equations) of an ideal.\nThis triangular set satisfies\ncertain minimal condition with respect to the Ritt ordering, and it preserves many interesting geometrical properties\nof the ideal.\nHowever it may not be its system of generators.\n\n## Notation\nLet R be the multivariate polynomial ring k[x1, ..., xn] over a field k.\nThe 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:\np can be naturally regarded as a univariate polynomial in its main variable xk with coefficients in k[x1, ..., xk−1].\nThe degree of p as a univariate polynomial in its main variable is also called its main degree.\n\n## Triangular set\nA set T of non-constant polynomials is called a **triangular set** if all polynomials in T have distinct main variables.\nThis generalizes triangular [systems of linear equations](https://bliptext.com/articles/systems-of-linear-equations) in a natural way.\n\n## Ritt ordering\nFor two non-constant polynomials p and q, we say p is smaller than q with respect to **Ritt ordering** and written as p

History