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 quasi-component 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 quasi-component 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 commands Complement, Difference, Intersection, and Union are basic set-theoretical operations on constructible sets.

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 well-known 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 set-theoretic coprime factorization (and could be referred to as an intersection-free basis computation) which plays an important role in computing comprehensive triangular decompositions.

The command CylindricalDecompose returns an invariant cylindrical decomposition of the n-dimensional 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.  

The following is a list of available commands.

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

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

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

$f≔1-xy$

$f≔-xy+1$

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

$R≔\mathrm{polynomial\_ring}$

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

$\mathrm{cs}≔\mathrm{constructible\_set}$

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

$\mathrm{lrs}≔\left[\mathrm{regular\_system}\right]$

$\mathrm{rs}≔\mathrm{lrs}\left[1\right]$

$\mathrm{rs}≔\mathrm{regular\_system}$

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

$\mathrm{rc}≔\mathrm{regular\_chain}$

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

$\mathrm{true}$

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

$\mathrm{ineq}≔\left[x\right]$

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

$S≔\mathrm{polynomial\_ring}$

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

$T≔\mathrm{polynomial\_ring}$

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

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

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

$\mathrm{cs}≔\mathrm{constructible\_set}$

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

$\left[\left[yx-z\,y^3-z^2\right]\,\left[y\right]\right],\left[\left[x\,y\,z\right]\,\left[1\right]\right]$

$\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]$

$\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}$

$\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]$

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 set-theoretical 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, nonzero-divisor) 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 quasi-component 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 $n-s$, 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.

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):55-66.

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):143-167.

Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties". MEGA-2000 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 quasi-algebraic sets". IMACS ACA'98 Electrical Proceedings. 1998.

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

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