In broad terms, a CTD of a parametric polynomial system F provides a finite partition P of the parameter space into regions, so that above each region the geometry (number of irreducible components together with their dimensions and degrees) of the solution set of F is the same at each parameter value. In addition, for each region C of the partition P, a CTD provides an associated (finite) set of regular chains S such that for each parameter value u in C the regular chains evaluated at u form a triangular decomposition (into regular chains) of the specialized system $F\left(u\right)$.

A CTD of the parametric polynomial system F does not need any assumptions on F or on the field of its coefficients. The computation of a CTD essentially proceeds in two steps. First, compute the set of all regular chains that are associated with the regions of the partition P. This first step is called pre-comprehensive triangular decomposition. Then, the partition P is computed.

Consider a simple example with a polynomial system F with two parameters u and v. You can answer questions such as: when does F have solutions? finitely many solutions? N solutions, for a given N? When you declare the polynomial ring, you do not specify yet which variables are regarded as parameters. This will be done during the function calls, which allows more flexibility.

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

$R≔\mathrm{polynomial\_ring}$

The input polynomial system F consists of two equations.

$F≔\left\{ux-vy\,x^2+y^2-1\right\}$

$F≔\left\{ux-vy\,x^2+y^2-1\right\}$

Below, one computes a (traditional) triangular decomposition of the system F.

$\mathrm{dec}≔\mathrm{Triangularize}\left(F\,R\,\mathrm{output}=\mathrm{lazard}\right)$

$\mathrm{dec}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right]$

$\mathrm{map}\left(\mathrm{Info}\,\mathrm{dec}\,R\right)$

$\left[\left[ux-yv\,\left(u^2+v^2\right)y^2-u^2\right]\,\left[x-1\,y\,u\right]\,\left[x+1\,y\,u\right]\,\left[x^2+y^2-1\,u\,v\right]\right]$

$\left\{\mathrm{op}\left(\mathrm{map}\left(\mathrm{Info}\,\mathrm{dec}\,R\right)\right)\right\}$

$\left\{\left[ux-yv\,\left(u^2+v^2\right)y^2-u^2\right]\,\left[x-1\,y\,u\right]\,\left[x+1\,y\,u\right]\,\left[x^2+y^2-1\,u\,v\right]\right\}$

Without additional computations, the questions above cannot be answered completely from this decomposition. For instance, it is not clear for which values of $u,v$ the system F has solutions. This question can be answered by means of the Projection function from the RegularChains:-ConstructibleSetTools subpackage. More precisely, it can project the variety onto the parameter space, the parameters being the last two variables in the polynomial ring. Note that this projection is not a variety in general. So, the returned type must be a constructible set, which is given here by four regular systems.

$\mathrm{cs}≔\mathrm{Projection}\left(F\,2\,R\right)\;$$\mathrm{RepresentingRegularSystems}\left(\mathrm{cs}\,R\right)$

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

$\left[\mathrm{regular\_system}\,\mathrm{regular\_system}\,\mathrm{regular\_system}\right]$

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

$\left[\left[\right]\,\left[u\,u^2+v^2\right]\right],\left[\left[u\right]\,\left[1\right]\right],\left[\left[u\,v\right]\,\left[1\right]\right]$

One obtains 4 cells in the parameter space. Clearly, this representation can be made simpler. To do so, as seen before, one can use the command MakePairwiseDisjoint.

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

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

$\left[\mathrm{regular\_system}\,\mathrm{regular\_system}\right]$

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

$\left[\left[u\right]\,\left[1\right]\right],\left[\left[\right]\,\left[u\,u^2+v^2\right]\right]$

Now a clear answer has been reached. The system F has solutions if and only if $u=0$ or $u\left(u^2+v^2\right)\ne 0$. Now, consider the next question: when does F have finitely many solutions? Different tools are available in this subpackage to answer that question. First, you can compute a CTD of F using the ComprehensiveTriangularize command.

$\mathrm{ctd}≔\mathrm{ComprehensiveTriangularize}\left(F\,2\,R\right)$

$\mathrm{ctd}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right],\left[\left[\mathrm{constructible\_set}\,\left[1\right]\right]\,\left[\mathrm{constructible\_set}\,\left[2\,3\right]\right]\,\left[\mathrm{constructible\_set}\,\left[2\,3\,4\right]\right]\right]$

One retrieves the triangular decomposition (see below) together with some additional information. The three constructible sets above form a partition of the projection of the solution set of F onto the parameter space such that above each part (or cell, or region), the solution set of F is given by the regular chains whose indices appear in the list associated with that cell. Hence, when $u=v=0$, the solutions of F are given by the last three regular chains in ${\mathrm{ctd}}_1$. In this case, there are infinitely many solutions (because of the fourth regular chain). The other two cases do not involve this fourth regular chain, and they lead to finitely many solutions, actually 2. Note that each of the first two cells is given just by one regular system; the last one is given by two.

$\mathrm{map}\left(\mathrm{Info}\,\mathrm{ctd}\left[1\right]\,R\right)$

$\left[\left[ux-yv\,\left(u^2+v^2\right)y^2-u^2\right]\,\left[x-1\,y\,u\right]\,\left[x+1\,y\,u\right]\,\left[x^2+y^2-1\,u\,v\right]\right]$

$\mathrm{lcs}≔\left[\mathrm{seq}\left(\mathrm{ctd}\left[2\right]\left[i\right]\left[1\right]\,i=1..\mathrm{nops}\left(\mathrm{ctd}\left[2\right]\right)\right)\right]$

$\mathrm{lcs}≔\left[\mathrm{constructible\_set}\,\mathrm{constructible\_set}\,\mathrm{constructible\_set}\right]$

$\mathrm{map}\left(\mathrm{RepresentingRegularSystems}\,\mathrm{lcs}\,R\right)$

$\left[\left[\mathrm{regular\_system}\right]\,\left[\mathrm{regular\_system}\right]\,\left[\mathrm{regular\_system}\right]\right]$

$\mathrm{map}\left(\mathrm{Info}\,\mathrm{lcs}\,R\right)$

$\left[\left[\left[\right]\,\left[u\,u^2+v^2\right]\right]\,\left[\left[u\right]\,\left[v\right]\right]\,\left[\left[u\,v\right]\,\left[1\right]\right]\right]$

A more direct, but less detailed, answer to this question can be obtained by using the DiscriminantSet command. The output is the set of the parameter values at which the system F has infinitely many solutions or no solutions. This is again a constructible set.

$\mathrm{ds}≔\mathrm{DiscriminantSet}\left(F\,2\,R\right)\:$$\mathrm{Info}\left(\mathrm{ds}\,R\right)$

$\left[\left[u\,v\right]\,\left[1\right]\right],\left[\left[u^2+v^2\right]\,\left[v\right]\right]$

Observe that you can compute the set of the parameter values at which F has finitely many solutions just by computing the set theoretical difference of two constructible sets, cs and ds. One retrieves the result that you could read from the CTD: the input system F has finitely many solutions if and only if one of these three conditions holds:

(1) $u=0$ and $v\ne 0$

(2) $u\left(u^2+v^2\right)\ne 0$

(3) $v=0$ and $u\ne 0$

$\mathrm{fs}≔\mathrm{Difference}\left(\mathrm{cs}\,\mathrm{ds}\,R\right)\:$$\mathrm{Info}\left(\mathrm{fs}\,R\right)$

$\left[\left[u\right]\,\left[v\right]\right],\left[\left[\right]\,\left[u\,u^2+v^2\,v\right]\right],\left[\left[v\right]\,\left[u\right]\right]$

Consider now a second example where the goal is to avoid bad specializations. Indeed, comprehensive triangular decompositions have a motivation other than counting solutions depending on parameters. This other feature can be stated as follows: above each cell in the parameter space, each regular chain in the associated triangular decomposition must be well-behaved under specialization. This concept is made more precise later. Consider a polynomial system F in two unknowns, x and y, and one parameter, s, over the complex field.

$R≔\mathrm{PolynomialRing}\left(\left[x\,y\,s\right]\right)\;$$F≔\left[s-\left(y+1\right)x\,s-\left(x+1\right)y\right]$

$R≔\mathrm{polynomial\_ring}$

$F≔\left[s-\left(y+1\right)x\,s-\left(x+1\right)y\right]$

Start by computing a (traditional) triangular decomposition of F.

$\mathrm{td}≔\mathrm{Triangularize}\left(F\,R\,\mathrm{output}=\mathrm{lazard}\right)\:$$\mathrm{map}\left(\mathrm{Equations}\,\mathrm{td}\,R\right)$

$\left[\left[\left(y+1\right)x-s\,y^2+y-s\right]\,\left[x+1\,y+1\,s\right]\right]$

It is clear from the above decomposition that s can be replaced by any complex number, producing two triangular sets. Hence, any specialization of s gives rise to solutions of F. This is confirmed by the following computation. Indeed, the complement of the projection of the variety of F on the s-axis is empty!

$\mathrm{es}≔\mathrm{Complement}\left(\mathrm{Projection}\left(F\,1\,R\right)\,R\right)\:$$\mathrm{IsEmpty}\left(\mathrm{es}\,R\right)$

$\mathrm{true}$

However, when you specialize the regular chain $\mathrm{rc1}={\mathrm{td}}_1$ at $s=0$, you do not obtain a regular chain anymore. Indeed, the initial of the first polynomial is not regular (that is, a zero-divisor) modulo the second polynomial. One checks this fact below.

$\mathrm{rc1}≔\mathrm{td}\left[1\right]\:$$\mathrm{rc2}≔\mathrm{td}\left[2\right]\:$$\mathrm{p1}≔\mathrm{eval}\left(\mathrm{Equations}\left(\mathrm{rc1}\,R\right)\left[1\right]\,s=0\right)$

$\mathrm{p1}≔\left(y+1\right)x$

$\mathrm{p2}≔\mathrm{eval}\left(\mathrm{Equations}\left(\mathrm{rc1}\,R\right)\left[2\right]\,s=0\right)\;$$\mathrm{IsRegular}\left(\mathrm{Initial}\left(\mathrm{p1}\,R\right)\,\mathrm{Chain}\left(\left[\mathrm{p2}\right]\,\mathrm{Empty}\left(R\right)\,R\right)\,R\right)$

$\mathrm{p2}≔y^2+y$

$\mathrm{false}$

This situation is avoided by a CTD, since it detects that the regular chain $\mathrm{rc1}$ does not specialize well at $s=0$.  The command DefiningSet computes, for a regular chain $\mathrm{rc}$, the parameter values at which $\mathrm{rc}$ specializes to a regular chain, with the same rank (main variables and main degrees) as the input regular chain. The above computation shows that $\mathrm{rc1}$ does not specialize well at $s=0$. It also shows that $\mathrm{rc2}$ specializes well only at $s=0$, which is obvious since s is a polynomial of this regular chain.

$\mathrm{ds1}≔\mathrm{DefiningSet}\left(\mathrm{rc1}\,1\,R\right)\:$$\mathrm{Info}\left(\mathrm{ds1}\,R\right)$

$\left[\left[\right]\,\left[s\right]\right]$

$\mathrm{ds2}≔\mathrm{DefiningSet}\left(\mathrm{rc2}\,1\,R\right)\:$$\mathrm{Info}\left(\mathrm{ds2}\,R\right)$

$\left[\left[s\right]\,\left[1\right]\right]$

Below a CTD of F is computed. This produces three regular chains and two cells in the parameter space, given by constructible sets.

$\mathrm{ctd}≔\mathrm{ComprehensiveTriangularize}\left(F\,1\,R\right)$

$\mathrm{ctd}≔\left[\mathrm{regular\_chain}\,\mathrm{regular\_chain}\,\mathrm{regular\_chain}\right],\left[\left[\mathrm{constructible\_set}\,\left[3\,2\right]\right]\,\left[\mathrm{constructible\_set}\,\left[1\right]\right]\right]$

Two of these regular chains are the ones that you obtained before. The new regular chain (the third one) is there to handle the case $s=0$ without introducing non-regular chains.

$\mathrm{map}\left(\mathrm{Info}\,\mathrm{ctd}\left[1\right]\,R\right)$

$\left[\left[\left(y+1\right)x-s\,y^2+y-s\right]\,\left[x+1\,y+1\,s\right]\,\left[x\,y\,s\right]\right]$

The cell $s=0$ is associated with the two regular chains admitting $s$ as an equation (that is, the second and third). The cell $s\ne 0$ is associated with the first regular chain, which is the regular chain from the output of Triangularize above, $\mathrm{rc1}$.

The command below displays this association: the first set tells you that the first constructible set corresponds to the case where $s=0$ and there are no parameters, and the second set tells you that the second constructible set corresponds to the case where $s$ is a parameter.

$\mathrm{map}\left(\mathrm{Info}\,\left[\mathrm{seq}\left(\mathrm{ctd}\left[2\right]\left[i\right]\left[1\right]\,i=1..\mathrm{nops}\left(\mathrm{ctd}\left[2\right]\right)\right)\right]\,R\right)$

$\left[\left[\left[s\right]\,\left[1\right]\right]\,\left[\left[\right]\,\left[s\right]\right]\right]$

Finally, if you are only interested in the regular chains that appear in a CTD (and not the cells), then the command PreComprehensiveTriangularize should be used.

$\mathrm{pctd}≔\mathrm{PreComprehensiveTriangularize}\left(F\,1\,R\right)\:$$\mathrm{map}\left(\mathrm{Info}\,\mathrm{pctd}\,R\right)$

$\left[\left[\left(y+1\right)x-s\,y^2+y-s\right]\,\left[x+1\,y+1\,s\right]\,\left[x\,y\,s\right]\right]$

It is worth noticing that this last command does not compute the cell partition, which can save a significant amount of running time for large examples.

For precise definitions of the terms comprehensive triangular decomposition (CTD), pre-comprehensive triangular decomposition, discriminant set, and defining set, refer to the documentation of the commands ComprehensiveTriangularize, PreComprehensiveTriangularize, DiscriminantSet, and DefiningSet, respectively.

If a semi-algebraic system (SAS) contains parameters, it is called a parametric SAS. For a parametric SAS and a prescribed non-negative integer n, the command RealRootClassification computes the conditions on the parameters such that the system has exactly n distinct real solutions.

For a defined polynomial ring R and a SAS given by polynomial lists F, N, P, and H, we specify by the fifth argument, d, that the last d unknowns of R are viewed as parameters, and by the sixth argument, n, that we would compute the conditions for the system to have exactly n distinct real solutions. The polynomial lists F, N, P, and H successively define the equations, the non-negative inequalities, the positive inequalities and the inequations. For example,

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

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

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

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

$R≔\mathrm{polynomial\_ring}$

$F≔\left[a{x}^2+bx+c\right]\;$$N≔\left[\right]\;$$P≔\left[x\right]\;$$H≔\left[a\right]$

$F≔\left[a{x}^2+bx+c\right]$

$N≔\left[\right]$

$P≔\left[x\right]$

$H≔\left[a\right]$

$\mathrm{rrc}≔\mathrm{RealRootClassification}\left(F\,N\,P\,H\,3\,2\,R\right)$

$\mathrm{rrc}≔\left[\left[\mathrm{regular\_semi\_algebraic\_set}\right]\,\mathrm{border\_polynomial}\right]$

The output is a list of regular semi-algebraic sets (LRSAS) and a border polynomial object (BP); they are equivalent to some logic formula. More precisely, the LRSAS gives necessary and sufficient conditions for the input SAS to have the prescribed number of real solutions, provided that the condition encode by BP holds.

The role of the border polynomial is to exclude some degenerate cases which can be handled later with further computations (more on this below).

The first command below shows the contents of BP: this is actually a list of polynomials and the logical condition encoded by BP is that none of those polynomials should be zero. The other commands extract the information representing the LRSAS and display the logical condition encoded by it.

In first approximation, a regular semi-algebraic set (RSAS) is a subset of the real solutions of a regular chain. More precisely, a RSAS is encoded by three pieces of data: a quantifier-free formula (QFF), a regular chain (RC) and a list of lists of indices (LLI). This encoding is called a parametric box (PB). The QFF part of it specifies the conditions of the variables which are not algebraic in RC, whereas RC and LLI specify the conditions of the variables which are algebraic in RC.

In our example, RC and LLI are empty (which is often the case); therefore the conditions encoded by the PB is just the conditions encoded by the QFF, which can be shown by the command DisplayQuantifierFreeFormula. To summarize, the answer to our particular question is:  provided that BP holds, the input SAS has exactly 2 distinct positive real solutions if and only QFF holds.

$\mathrm{bp}≔\mathrm{rrc}\left[2\right]$

$\mathrm{bp}≔\mathrm{border\_polynomial}$

$\mathrm{Info}\left(\mathrm{bp}\,R\right)$

$\left[a\,b\,c\,-4ac+b^2\right]$

$\mathrm{rsas}≔\mathrm{rrc}\left[1\right]\left[1\right]$

$\mathrm{rsas}≔\mathrm{regular\_semi\_algebraic\_set}$

$\mathrm{pb}≔\mathrm{RepresentingBox}\left(\mathrm{rsas}\,R\right)$

$\mathrm{pb}≔\mathrm{parametric\_box}$

$\mathrm{qff}≔\mathrm{RepresentingQuantifierFreeFormula}\left(\mathrm{pb}\right)$

$\mathrm{qff}≔\mathrm{quantifier\_free\_formula}$

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

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

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

$\mathrm{lli}≔\mathrm{RepresentingRootIndex}\left(\mathrm{pb}\right)$

$\mathrm{lli}≔\left[\right]$

Recall that the border polynomial (BP) is a list of polynomials such that the union of all hypersurfaces defined by each polynomial contains all the abnormal parameter values of the input parametric SAS. For the above example, the border polynomial is $\left[c\,a\,4ac-b^2\right]$. It's obvious that the number of distinct non-zero solutions changes if $a\left(4ac-b^2\right)c=0$. Note that one can use the RegularChains:-Info command to view the contents of a BP.

One might want to go further in analyzing the number of real solutions of the input SAS, that is, one might want to figure out what's happening when a parameter value cancels BP. This is very simple: it suffices to add the product of the polynomials in BP to the list of equations when calling RealRootClassification (or to add the polynomials in BP one by one to the equations of the system and call RealRootClassification accordingly).

Recall that, in our example, we are investigating the cases where the input system has 2 distinct positive real solutions. When we add the $4ac-b^2$ to it, we obtain no RSAS part in the output of RealRootClassification. This means that it cannot happen that the equation $a{X}^2+bX+c=0$ has 2 distinct positive real solutions, when its discriminant is zero. This is obvious, of course!

$\mathrm{rrc1}≔\mathrm{RealRootClassification}\left(\left[4ac-b^2\,\mathrm{op}\left(F\right)\right]\,N\,P\,H\,3\,2\,R\right)$

$\mathrm{rrc1}≔\left[\left[\right]\,\mathrm{border\_polynomial}\right]$

$\mathrm{bp1}≔\mathrm{rrc1}\left[2\right]$

$\mathrm{bp1}≔\mathrm{border\_polynomial}$

$\mathrm{Info}\left(\mathrm{bp1}\,R\right)$

$\left[b\,a\right]$

The above output means: provided $cb\ne 0$, the new system never admits two distinct positive real solutions. The cases where one of the parameters a, b, or c could be investigated similarly.