Overview of the RegularChains[ConstructibleSetTools] Subpackage

Calling Sequence


RegularChains[ConstructibleSetTools][command](arguments)
command(arguments)


Description


•

The RegularChains[ConstructibleSetTools] subpackage is a collection of commands for manipulating these two types of algebraic objects: constructible set and regular system. Given an input polynomial system F (with equations and inequations) over some field, the solution set of F is (by definition) a constructible set; this set can be described (or represented) by a finite list of regular systems.

•

The commands, Complement, Difference, Intersection, IsContained, Union, and RegularSystemDifference are basic operations on constructible sets. Advanced operations are also provided, namely CylindricalDecompose, MakePairwiseDisjoint, PolynomialMapImage, PolynomialMapPreimage, RationalMapImage, RationalMapPreimage, Projection, and RefiningPartition and SeparateZeros. The other operations, namely ConstructibleSet, EmptyConstructibleSet, GeneralConstruct, IsEmpty, QuasiComponent, RegularSystem, RepresentingChain, RepresentingInequations, and RepresentingRegularSystems, are used to build regular systems and constructible sets or inspect their internal structures and data.

•

The command RegularSystem is used to build a regular system from a regular chain C and a list L of polynomials. For this regular system to be valid, each polynomial in the list L must be regular with respect to the saturated ideal of the regular chain C. The solution set of the corresponding regular system is the set of the points that belong to the quasicomponent of C and that do not cancel any polynomials in L.

•

The command ConstructibleSet is used to build a constructible set, given as the union of the solution sets of finitely many regular systems. Any constructible set can actually be encoded in this way.

•

The command QuasiComponent can be used to build a constructible set when it is simply the quasicomponent of a regular chain.

•

The command GeneralConstruct builds a constructible set as the solution set of a polynomial system given by a list of equations, a regular chain, and a list of inequations.

•

The empty set is a special constructible set which can be constructed by the command EmptyConstructibleSet.

•

The commands RepresentingChain and RepresentingInequations are used to extract the representation (or data, or information) from a regular system, and the command RepresentingRegularSystems is used to extract regular systems from a constructible set. The general command Info can be used to display the contents of a regular chain, a regular system, or a constructible set in terms of polynomials.

•

The command RegularSystemDifference is a special one, which plays the most important role in this subpackage. Almost all hard computations involve this function. Moreover, the commands IsEmpty and IsContained can be used to check specific properties on constructible sets.

•

Originally, the term constructible set was introduced while considering the image of an algebraic set under certain maps. In this subpackage, we provide a set of advanced commands for this purpose.

•

Given a constructible set C and a polynomial map T from an affine space A1 to an affine space A2, the command PolynomialMapImage will compute the image of C in the affine space A2 under the polynomial map T.

•

Standard projection is a special kind of polynomial map that simply ignores those coordinates corresponding to some larger variables. The command Projection will do such a job directly.

•

If you have an algebraic variety V in A2, the command PolynomialMapPreimage will compute the preimage of V in A1.

•

The commands RationalMapImage and RationalMapPreimage extend the previous ones to the case where T is a rational map and the mapped object is a constructible set. The output of these commands are all constructible sets, and this is the wellknown Chevalley's Theorem.

•

Since a constructible set can be written as a finite disjoint union of local closed subsets, the command MakePairwiseDisjoint will achieve such a goal. It takes a constructible set as input, returns another constructible set. As two sets, these two constructible sets are equal; however, the zero set of the defining regular systems of the output are pairwise disjoint.

•

Given a set of constructible sets L, the command RefiningPartition generates another set M of pairwise disjoint constructible sets such that each constructible set in L can be written as a union of constructible sets in M. This process may be seen as a settheoretic coprime factorization (and could be referred to as an intersectionfree basis computation) which plays an important role in computing comprehensive triangular decompositions.

•

The command CylindricalDecompose returns an invariant cylindrical decomposition of the ndimensional complex space, where n is the number of variables in the given ring.

•

The command SeparateZeros decomposes the zeros of constructible set regarding all variables but the largest one as parameters.



List of RegularChains[ConstructibleSetTools] Subpackage Commands



The following is a list of available commands.



Examples


>

$\mathrm{with}\left(\mathrm{RegularChains}\right)\:$

>

$\mathrm{with}\left(\mathrm{ChainTools}\right)\:$

>

$\mathrm{with}\left(\mathrm{ConstructibleSetTools}\right)\:$

Constructible sets are the fundamental objects of Algebraic Geometry; they play there the role that ideals play in Polynomial Algebra. The simplest example is the following: for which values of x does $f\left(y\,x\right)\=0$ have solutions, with f as below?
${f}{:=}{}{x}{}{y}{\+}{1}$
 (1) 
The answer is whenever $x\ne 0$ holds. Formally speaking, this is the projection on the xaxis of the hyperbola $f\=0$. The above function Projection implements such a process through triangular decompositions. The output is an object of type constructible_set. Its internal representation is given by a list of socalled regular systems.
>

$R:=\mathrm{PolynomialRing}\left(\left[y\,x\right]\right)$

${R}{:=}{\mathrm{polynomial\_ring}}$
 (2) 
>

$\mathrm{cs}:=\mathrm{Projection}\left(\left\{f\right\}\,1\,R\right)$

${\mathrm{cs}}{:=}{\mathrm{constructible\_set}}$
 (3) 
>

$\mathrm{lrs}:=\mathrm{RepresentingRegularSystems}\left(\mathrm{cs}\,R\right)$

${\mathrm{lrs}}{:=}\left[{\mathrm{regular\_system}}\right]$
 (4) 
>

$\mathrm{rs}:={\mathrm{lrs}}_{1}$

${\mathrm{rs}}{:=}{\mathrm{regular\_system}}$
 (5) 
Each regular system is a pair consisting of a regular chain and an inequation given by one or more polynomials:
>

$\mathrm{rc}:=\mathrm{RepresentingChain}\left(\mathrm{rs}\,R\right)$

${\mathrm{rc}}{:=}{\mathrm{regular\_chain}}$
 (6) 
>

$\mathrm{IsEmptyChain}\left(\mathrm{rc}\,R\right)$

>

$\mathrm{ineq}:=\mathrm{RepresentingInequations}\left(\mathrm{rs}\,R\right)$

${\mathrm{ineq}}{:=}\left[{x}\right]$
 (8) 
We consider now another illustrative topic. A frequent question in Algebraic Geometry is the computation of images and preimages of algebraic varieties by a polynomial map. This question can also be formulated in terms of an "implicit function" study. Start with an elementary example. Assume that the field of coordinates is the complex field. Consider the map sending the variable t to the point of coordinates ($t$, ${t}^{2}$, ${t}^{3}$). What is the image of this map in the threedimensional space? To answer that question, first define the polynomial rings S and T associated with the source and target spaces.
>

$S:=\mathrm{PolynomialRing}\left(\left[t\right]\right)$

${S}{:=}{\mathrm{polynomial\_ring}}$
 (9) 
>

$T:=\mathrm{PolynomialRing}\left(\left[x\,y\,z\right]\right)$

${T}{:=}{\mathrm{polynomial\_ring}}$
 (10) 
Next, define the polynomial map PM.
>

$\mathrm{PM}:=\left[t\,{t}^{2}\,{t}^{3}\right]$

${\mathrm{PM}}{:=}\left[{t}{\,}{{t}}^{{2}}{\,}{{t}}^{{3}}\right]$
 (11) 
Now compute its image. The first argument is the empty list since there are no constraints on t.
>

$\mathrm{cs}:=\mathrm{PolynomialMapImage}\left(\left[\right]\,\mathrm{PM}\,S\,T\right)$

${\mathrm{cs}}{:=}{\mathrm{constructible\_set}}$
 (12) 
For this particular example, you obtain a famous curve (the twisted cubic) given by the above two regular systems.
>

$\mathrm{Info}\left(\mathrm{cs}\,T\right)$

$\left[\left[{y}{}{x}{}{z}{\,}{{y}}^{{3}}{}{{z}}^{{2}}\right]{\,}\left[{y}\right]\right]{\,}\left[\left[{x}{\,}{y}{\,}{z}\right]{\,}\left[{1}\right]\right]$
 (13) 
Clearly this variety is defined by $yxz\=0$ and ${y}^{3}{z}^{2}\=0$. Using the PolynomialMapPreimage command, you can compute its preimage: you retrieve the whole 1dimensional space.
>

$\mathrm{ds}:=\mathrm{PolynomialMapPreimage}\left(\left[z\+xy\,{y}^{3}{z}^{2}\right]\,\mathrm{PM}\,S\,T\right)\;$$\mathrm{Info}\left(\mathrm{ds}\,S\right)$

${\mathrm{ds}}{:=}{\mathrm{constructible\_set}}$
 
$\left[\left[{}\right]{\,}\left[{1}\right]\right]$
 (14) 
Note that you could ask for the preimages of some more specific points, such as those satisfying $x\+y\+z\=0$, as below:
>

$\mathrm{ds}:=\mathrm{PolynomialMapPreimage}\left(\left[z\+xy\,{y}^{3}{z}^{2}\,z\+y\+x\right]\,\mathrm{PM}\,S\,T\right)$

${\mathrm{ds}}{:=}{\mathrm{constructible\_set}}$
 (15) 
>

$\mathrm{Info}\left(\mathrm{ds}\,S\right)$

$\left[\left[{{t}}^{{2}}{\+}{t}{\+}{1}\right]{\,}\left[{1}\right]\right]{\,}\left[\left[{t}\right]{\,}\left[{1}\right]\right]$
 (16) 


Mathematical Definitions


•

Constructible sets arise naturally when one considers the image of an algebraic set under certain maps (for example, polynomial maps and rational maps). When projecting an algebraic set into a coordinate space, the image is not necessarily open or closed (with respect to the Zariski topology), rather, it is a constructible set. The set C of all constructible sets in an affine space ${K}^{n}$ (where $K$ is an algebraically closed field) consists of (1) all closed subsets, (2) any finite union of elements in C, and (3) the complement of any element of C.

•

A constructible set can always be written as a finite union of locally closed sets, where a locally closed set is the intersection of an open subset and a closed subset. Furthermore, such a union can always be refined: a constructible set can be written as a finite union of pairwise disjoint locally closed subsets.

•

A constructible set can also be defined in terms of a unique sequence of varieties. Given a monomial ordering, the reduced Groebner bases of the ideals of these varieties comprise a complete invariant for the constructible set (see the paper "Groebner bases for constructible sets" by J. O'Halloran and M. Schilmoeller). Such a representation is hard to manipulate in view of computing the intersection or settheoretical difference of constructible sets. For this reason, you can use the fact that every constructible set can be represented as a finite union of zero sets of regular systems (see the paper "On the verification of polynomial system solvers" by C. Chen, M. Moreno Maza, W. Pan, and Y. Xie).

•

Let k be a field and R be the polynomial ring $k\[\mathrm{x1},...,\mathrm{xn}\]$. Let T be a regular chain in R, and p be a polynomial of R. The pair (T, p) is called a regular system if p is regular (that is, nonzerodivisor) with respect to the saturated ideal of the regular chain T. Let K be the algebraic closure of k. A point Q in the affine space ${K}^{n}$ is a zero of the regular system (T, p) if it is a zero of T that cancels neither p nor h, the product of the initials of T. That is to say, the zero set of (T, p) is $W\left(T\right)$ \ $V\left(p\right)$, where $W\left(T\right)\=V\left(T\right)$ \ $V\left(h\right)$ is the quasicomponent of T. Since T is a regular chain, it is well known that the algebraic set defined by its saturated ideal $\mathrm{Sat}\left(T\right)$ is nonempty and unmixed. In particular, all associated primes of $\mathrm{Sat}\left(T\right)$ have the same dimension $ns$, where s is the number of elements in T. Since the polynomial p is regular with respect to $\mathrm{Sat}\left(T\right)$, we deduce that the zero set of (T, p) (that is, $W\left(T\right)$ \ $V\left(p\right)$) is not empty. Please refer to the RegularChains package for more information about the concept of a regular chain and related ideas.



References



Chen, C.; Lemaire, F.; Golubitsky, O.; Moreno Maza, M.; and Pan, W. "Comprehensive Triangular Decomposition" Proceedings of CASC 2007, Lecture Notes in Computer Science, Vol. 4770. Springer, 2007.


Chen, C.; Moreno Maza, M.; Pan, W.; and Xie, Y. "On the verification of polynomial system solvers" Frontiers of Computer Science in China. Vol. 2. (2008):5566.


Cox, D. A.; Little, J.; and O'Shea. D. Ideals, Varieties and Algorithms. Springer, 1997.


Eisenbud, D. Commutative Algebra. Graduate Texts in Mathematics No. 150. Springer, 1994.


Kalkbrener, M. "Three contributions to elimination theory". PhD Thesis. Austria: University of Linz, 1991.


Kalkbrener, M. "A generalized Euclidean algorithm for computing triangular representations of algebraic varieties". J. Symb. Comp., Vol. 15. (1993):143167.


Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties". MEGA2000 conference Bath, England, 2000.


O'Halloran, J. and Schilmoeller, M. "Groebner bases for constructible sets." Journal of Communications in Algebra, Vol. 30, No. 11. (2002).


Sit, W. "Computations on quasialgebraic sets". IMACS ACA'98 Electrical Proceedings. 1998.


Wang, D. M. "An elimination method for polynomial systems". J. Symb. Comp., Vol. 16. (1993):83114.


Wang, D. M. "Decomposing Polynomial Systems into Simple Systems". J. Symb. Comp., Vol. 25, No. 3. (1998): 295314.


