Characteristic set

Characteristic set

The mathematical concept of a characteristic set was discovered in the late forties by J.F. Ritt. Besides Gröbner basis method, it provides an alternative algorithmic way for solving multivariate polynomial equations or differential equations.In the late seventies, the Chinese mathematician Wen-Tsun Wu specialized it with modifications to commutative algebra. He demonstrated its power for mechanical theorem proving.

Informal description

For an ideal I in the ring 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). Given a characteristic set C of I, one can decide if a polynomial f is zero modulo I. That is, membership test is checkable for I, provided a characteristic set of I.

Ritt characteristic set

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

* Notation

Let R be the multivariate polynomial ring k [x1, ..., xn] 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 [x1, ..., xk-1] .The degree of p as a univariate polynomial in its main variable is also called its main degree.

* Triangular set and fine triangular set

A set T of non-constant polynomials is called a triangular set if all polynomials in T have dinstinct main variables. This generalizes triangular systems of linear equations in a natural way. A triangular set T is said to be fine, if each of the initials of T is not pseudo-reduced to zero with respect to T. This can be further generalized to the notion of regular chain.

* Ritt ordering

For two non-canstant polynomials p and q, we say p is smaller than q w.r.t 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 [x1, ..., xn] , <r) 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.Note that the Ritt ordering is comparing the rank of p and q. The rank, denotey by rank(p), of a non-constant polynomial p is defined to be a power of its main variable: mvar(p)mdeg(p).

* Ritt ordering on triangular sets

A crucial generalization on Ritt ordering is to compare triangular sets. Let T = { t1, ..., tu} and S = { s1, ..., sv} 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 U w.r.t. Ritt ordering if one of the following assertions holds:(1) there exists k ≤ min(u, v) such that rank(ti) = rank(si) for 1 ≤ i < k and tk <r sk, :(2) u > v and rank(ti) = rank(si) for 1 ≤ i ≤ v.

Also, there exists incomparable triangular sets w.r.t Ritt ordering.

* Ritt characteristic set

Let I be a non-zero ideal of k [x1, ..., xn] . A subset T of I is a Ritt characteristic set of I if one of the following conditions holds::(1) T consists of a single nonzero constant of k,:(2) T is a triangular set and T is minimal w.r.t Ritt ordering in the set of all fine triangular sets contained in I.

A polynomial ideal may possess (infinitely) 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

:(1) T = {a} with a being a nonzero constant,:(2) T is a triangular set and there exists a subset G of such that = and every polynomial in G is pseudo-reduced to zero with respect to T.

Note that 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.

Decomposing algebraic varieties

An most important 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:

:V(F) = W(T_1)cup cdots cup W(T_e) ,

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

ee also

*Groebner basis
*Regular chain

References

*P. Aubry, D. Lazard, M. Moreno Maza (1999). On the theories of triangular sets. Journal of Symbolic Computation, 28(1-2):105-124
*Ritt, J. (1966). Differential Algebra. New York, Dover Publications.
*Wang, D. M. (1998). Elimination Methods. Springer-Verlag, Wien, Springer-Verlag
*Wu, W. T. (1984). Basic principles of mechanical theorem proving in elementary geometries. J. Syst. Sci. Math. Sci., 4, 207-35
*Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2-12


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • 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… …   Wikipedia

  • Characteristic based product configurator — A characteristic based product configurator is a product configurator extension which uses a set of discrete variables, called characteristics (or features), to define all the possible product variations. The characteristics There are two… …   Wikipedia

  • Characteristic class — In mathematics, a characteristic class is a way of associating to each principal bundle on a topological space X a cohomology class of X. The cohomology class measures the extent to which the bundle is twisted particularly, whether it possesses… …   Wikipedia

  • Characteristic polynomial — This article is about the characteristic polynomial of a matrix. For the characteristic polynomial of a matroid, see Matroid. For that of a graded poset, see Graded poset. In linear algebra, one associates a polynomial to every square matrix: its …   Wikipedia

  • Characteristic function (probability theory) — The characteristic function of a uniform U(–1,1) random variable. This function is real valued because it corresponds to a random variable that is symmetric around the origin; however in general case characteristic functions may be complex valued …   Wikipedia

  • Characteristic function (convex analysis) — In the field of mathematics known as convex analysis, the characteristic function of a set is a convex function that indicates the membership (or non membership) of a given element in that set. It is similar to the usual indicator function, and… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • set — I [[t]se̱t[/t]] NOUN USES ♦ sets 1) N COUNT: oft N of n A set of things is a number of things that belong together or that are thought of as a group. There must be one set of laws for the whole of the country... I might need a spare set of… …   English dictionary

  • characteristic function — Math. 1. a function defined on a given set, having value 1 for every element of the set and value 0 for every element not contained in the set. 2. See characteristic polynomial. [1875 80] * * * …   Universalium

  • characteristic function — noun A function which is equal to 1 for all points in its domain which belong to a given set, and is equal to 0 for all points in the domain which do not belong to that given set. The characteristic function of a set A is often represented as… …   Wiktionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”