RegularChains - Maple Programming Help

Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : SemiAlgebraicSetTools Subpackage : RegularChains/ConstructibleSetTools/Complement

RegularChains

 ConstructibleSetTools[Complement]
 compute the complement of a constructible set
 SemiAlgebraicSetTools[Complement]
 compute the complement of a semi-algebraic set

 Calling Sequence Complement(cs, R) Complement(lrsas, R)

Parameters

 cs - constructible set lrsas - list of regular semi-algebraic systems R - polynomial ring

Description

 • The command Complement(cs, R) returns the complement of the constructible set cs in the affine space associated with R. If K is the algebraic closure of the coefficient field of R and n is the number of variables in R, then this affine space is ${K}^{n}$.  The polynomial ring may have characteristic zero or a prime characteristic.
 • The command Complement(lrsas, R) returns the complement of the semi-algebraic set represented by lrsas (see RealTriangularize for this representation). The polynomial ring must have characteristic zero. The empty semi-algebraic set is encoded by the empty list.
 • The empty constructible set represents the empty set of ${K}^{n}$.
 • This command is available once RegularChains[ConstructibleSetTools] submodule or RegularChains[SemiAlgebraicSetTools] submodule have been loaded. It can always be accessed through one of the following long forms: RegularChains[ConstructibleSetTools][Complement] or RegularChains[SemiAlgebraicSetTools][Complement].

Examples

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

First define the polynomial ring $R$ and two polynomials of $R$.

 > $R≔\mathrm{PolynomialRing}\left(\left[x,a,b,c,d\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (1)
 > $F≔ax+c$
 ${F}{≔}{a}{}{x}{+}{c}$ (2)
 > $G≔bx+d$
 ${G}{≔}{b}{}{x}{+}{d}$ (3)

The goal is to determine for which parameter values of $a$, $b$, $c$ and $d$ the generic linear equations $F$ and $G$ have solutions. Project the variety defined by $F$ and $G$ onto the parameter space.

 > $\mathrm{cs}≔\mathrm{Projection}\left(\left[F,G\right],4,R\right)$
 ${\mathrm{cs}}{≔}{\mathrm{constructible_set}}$ (4)
 > $\mathrm{Info}\left(\mathrm{cs},R\right)$
 $\left[\left[{d}{}{a}{-}{c}{}{b}\right]{,}\left[{d}{,}{b}\right]\right]{,}\left[\left[{b}{,}{d}\right]{,}\left[{a}\right]\right]{,}\left[\left[{c}{,}{d}\right]{,}\left[{1}\right]\right]{,}\left[\left[{a}{,}{b}{,}{c}{,}{d}\right]{,}\left[{1}\right]\right]$ (5)

Therefore, four regular systems encode this projection in the parameter space. The complement of cs should be those points that make the linear equations have no common solutions.

 > $\mathrm{com_cs}≔\mathrm{Complement}\left(\mathrm{cs},R\right)$
 ${\mathrm{com_cs}}{≔}{\mathrm{constructible_set}}$ (6)
 > $\mathrm{Info}\left(\mathrm{com_cs},R\right)$
 $\left[\left[\right]{,}\left[{d}{}{a}{-}{b}{}{c}{,}{d}\right]\right]{,}\left[\left[{d}\right]{,}\left[{c}{,}{b}\right]\right]{,}\left[\left[{a}{,}{b}\right]{,}\left[{d}\right]\right]{,}\left[\left[{a}{,}{b}{,}{d}\right]{,}\left[{c}\right]\right]$ (7)

If you call Complement twice, you should retrieve the constructible set cs.

 > $\mathrm{com_com_cs}≔\mathrm{Complement}\left(\mathrm{com_cs},R\right)$
 ${\mathrm{com_com_cs}}{≔}{\mathrm{constructible_set}}$ (8)
 > $\mathrm{IsContained}\left(\mathrm{cs},\mathrm{com_com_cs},R\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{and}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{IsContained}\left(\mathrm{com_com_cs},\mathrm{cs},R\right)$
 ${\mathrm{true}}$ (9)

Semi-algebraic case

 > $R≔\mathrm{PolynomialRing}\left(\left[a,b,c\right]\right):$
 > $\mathrm{S1}≔\left[{a}^{2}-ca-a=0,0
 ${\mathrm{S1}}{≔}\left[{{a}}^{{2}}{-}{c}{}{a}{-}{a}{=}{0}{,}{0}{<}{a}{-}{c}\right]$ (10)
 > $\mathrm{out}≔\mathrm{RealTriangularize}\left(\mathrm{S1},R\right)$
 ${\mathrm{out}}{≔}\left[{\mathrm{regular_semi_algebraic_system}}{,}{\mathrm{regular_semi_algebraic_system}}\right]$ (11)
 > $\mathrm{compl}≔\mathrm{Complement}\left(\mathrm{out},R\right)$
 ${\mathrm{compl}}{≔}\left[{\mathrm{regular_semi_algebraic_system}}{,}{\mathrm{regular_semi_algebraic_system}}{,}{\mathrm{regular_semi_algebraic_system}}\right]$ (12)
 > $\mathrm{expected}≔\left[\left[{a}^{2}-ca-a\ne 0\right],\left[a-c\le 0\right]\right]$
 ${\mathrm{expected}}{≔}\left[\left[{{a}}^{{2}}{-}{c}{}{a}{-}{a}{\ne }{0}\right]{,}\left[{a}{-}{c}{\le }{0}\right]\right]$ (13)
 > $\mathrm{expected}≔\mathrm{map}\left(t→\mathrm{op}\left(\mathrm{RealTriangularize}\left(t,R\right)\right),\mathrm{expected}\right)$
 ${\mathrm{expected}}{≔}\left[{\mathrm{regular_semi_algebraic_system}}{,}{\mathrm{regular_semi_algebraic_system}}{,}{\mathrm{regular_semi_algebraic_system}}\right]$ (14)

Verify compl = expected as set of points by Difference.

 > $\mathrm{Difference}\left(\mathrm{compl},\mathrm{expected},R\right)$
 $\left[\right]$ (15)
 > $\mathrm{Difference}\left(\mathrm{expected},\mathrm{compl},R\right)$
 $\left[\right]$ (16)

References

 Chen, C.; Golubitsky, O.; Lemaire, F.; Moreno Maza, M.; and Pan, W. "Comprehensive Triangular Decomposition". Proc. CASC 2007, LNCS, Vol. 4770: 73-101. Springer, 2007.
 Chen, C.; Davenport, J.-D.; Moreno Maza, M.; Xia, B.; and Xiao, R. "Computing with semi-algebraic sets represented by triangular decomposition". Proceedings of 2011 International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), ACM Press, pp. 75--82, 2011.

Compatibility

 • The RegularChains[SemiAlgebraicSetTools][Complement] command was introduced in Maple 16.
 • The lrsas parameter was introduced in Maple 16.
 • For more information on Maple 16 changes, see Updates in Maple 16.