RegularChains[ParametricSystemTools] - Maple Programming Help

Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : ParametricSystemTools Subpackage : RegularChains/ParametricSystemTools/RealRootClassification

RegularChains[ParametricSystemTools]

 RealRootClassification
 compute a real root classification of a parametric semi-algebraic system

 Calling Sequence RealRootClassification(F, N, P, H, d, n, R) RealRootClassification(F, N, P, H, d, r, R) RealRootClassification(F, N, P, H, d, n, R, 'output'='formula') RealRootClassification(F, N, P, H, d, n, R, 'output'='samples')

Parameters

 R - polynomial ring F - list of polynomials of R N - list of polynomials of R P - list of polynomials of R H - list of polynomials of R d - positive integer n - non-negative integer r - non-negative integer range or an integer range

Description

 • For a semi-algebraic system with parametric variables (parameters), RealRootClassification computes conditions on the parameters for the system to have a given number of real solutions.
 • More precisely, consider a semi-algebraic system $S$ with polynomial equations, non-negative polynomial inequalities, (strictly) positive polynomial inequalities, and polynomial inequations given respectively by F, N, P, and H, and with the last d variables of R as parameters.
 This command returns a pair $\left[C,\mathrm{BP}\right]$, such that, provided $\mathrm{BP}$ does not vanish, the semi-algebraic system $S$ has exactly n distinct real solutions (or, the number of distinct real solutions of $S$ falls into the range r) if and only if the parameters are taking values in $C$.
 • In the returned pair, $\left[C,\mathrm{BP}\right]$, $C$ is of type semi_algebraic_set (a list of regular_semi_algebraic_sets) representing the conditions, and $\mathrm{BP}$ is of type border_polynomial excluding some exceptional parameter values. Note that all the polynomials in $C$ and $\mathrm{BP}$ involve only parameters.
 • Note that, in special circumstances, the returned pair $\left[C,\mathrm{BP}\right]$ is not well defined. See BorderPolynomial or the related explanation below.
 • r is an integer range of the form $a..k$ where $a$ is a non-negative integer and $k$ is either a non-negative integer satisfying $a\le k$ or a name without value standing for infinity.
 • There are two special cases where the computed condition $\left[C,\mathrm{BP}\right]$ is not well defined or does not return the expected answer. One is when the system $S$ is positive dimensional for almost all parameter values. In this case some variables will be treated as parameters, and the command returns conditions for the system to have real solutions w.r.t. the new parameters set. The second case is when the input system is inconsistent.
 • There are $2$ representations of regular_semi_algebraic_sets in the current implementation according to the different nature of the input systems. The related representations are quantifier-free formula, quantifier-free formula with $n$-th root indices, and isolating box. For the latter one, see RealRootIsolate.
 • One can get a more detailed description on the result of the command RealRootClassification by setting the $\mathrm{infolevel}$ variable to be greater than 0 (see the examples below).
 • Because of the inner representation of data in Maple and the strategy of formula simplification in RealRootClassification, the output conditions $C$ for mathematically equivalent input (e.g. all are same but different variable order in ring $R$) may be different in their form but are equivalent to each other, of course.
 • The algorithm is described in the paper by Yang, L., Hou, X., Xia, B. "A complete algorithm for automated discovering of a class of inequality-type theorems." Sci. China Ser. F, Vol. 44 (2001): 33--49.
 • The algorithm is complete in theory, however, the command RealRootClassification may quit and output a necessary condition for some examples due to too heavy computation.

Options

 • The option 'output'='samples' modifies the algorithm as follows: instead of returning a pair, $\left[C,\mathrm{BP}\right]$, where $C$ is of type semi_algebraic_set (a list of regular_semi_algebraic_sets) the command returns sample points in the parameter space. All these sample points belong to the complement of the hypersurface defined by $\mathrm{BP}$ in the parameter space. Moreover there is at least sample point per connected component satisfying the following property: the input parametric semi-algebraic system $S$ has n distinct real solutions (or, the number of distinct real solutions of $S$ falls into the range r) above this component. In addition, there is no sample points belonging to the connected components not satisfying the previous property.
 • The option 'output'='samples' also modifies the output format as follows. It is a record with five fields. DecomposedSystems is a list of basic semi-algebraic systems  (each of them consisting of a list of equational constraints and a list positive inequality constraints) such that the union of their solution sets equals the solution set of the input semi-algebraic system $S$ outside of the hypersurface defined by its border polynomial. BorderPolynomial is the border polynomial of $S$ as computed by this command. Parameters lists the parameters in the projection order used by the underlying OPENCAD sampling algorithm. ProjectionPolynomials is a list of lists of polynomials, where each inner list consists of the polynomials used in each OPENCAD projection. SamplePoints is the list of the sample points described above.
 • The option 'output'='formula' is the default option of this command.
 The computations performed for the option 'output'='samples' are a first step in the computations  performed for option 'output'='formula'. This latter option is often more computationally intensive than the former one while the information provided by this former may often be sufficient in practice.

Examples

 > $\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}}$ (1)
 > $F≔\left[a{x}^{2}+bx+c\right];$$N≔\left[\right];$$P≔\left[\right];$$H≔\left[\right]$
 ${F}{≔}\left[{a}{}{{x}}^{{2}}{+}{b}{}{x}{+}{c}\right]$
 ${N}{≔}\left[{}\right]$
 ${P}{≔}\left[{}\right]$
 ${H}{≔}\left[{}\right]$ (2)

We compute the condition on $\left[a,b,c\right]$ for the system to have no real solutions.

 > $\mathrm{rrc}≔\mathrm{RealRootClassification}\left(F,N,P,H,3,0,R\right)$
 ${\mathrm{rrc}}{≔}\left[\left[{\mathrm{regular_semi_algebraic_set}}\right]{,}{\mathrm{border_polynomial}}\right]$ (3)

We first inspect the border polynomial.

 > $\mathrm{Info}\left({\mathrm{rrc}}_{2},R\right)$
 $\left[{a}{,}{-}{4}{}{a}{}{c}{+}{{b}}^{{2}}\right]$ (4)

We then inspect the regular semi-algebraic set.

 > $\mathrm{rc}≔\mathrm{RepresentingChain}\left({{\mathrm{rrc}}_{1}}_{1},R\right)$
 ${\mathrm{rc}}{≔}{\mathrm{regular_chain}}$ (5)
 > $\mathrm{Info}\left(\mathrm{rc},R\right)$
 $\left[{}\right]$ (6)
 > $\mathrm{rsas}≔{{\mathrm{rrc}}_{1}}_{1}$
 ${\mathrm{rsas}}{≔}{\mathrm{regular_semi_algebraic_set}}$ (7)
 > $\mathrm{pbx}≔\mathrm{RepresentingBox}\left(\mathrm{rsas},R\right)$
 ${\mathrm{pbx}}{≔}{\mathrm{parametric_box}}$ (8)
 > $\mathrm{qff}≔\mathrm{RepresentingQuantifierFreeFormula}\left(\mathrm{pbx}\right)$
 ${\mathrm{qff}}{≔}{\mathrm{quantifier_free_formula}}$ (9)
 > $\mathrm{Info}\left(\mathrm{qff},R\right)$
 $\left[\left[{4}{}{a}{}{c}{-}{{b}}^{{2}}\right]{,}\left[\left[{1}\right]\right]\right]$ (10)

We now pretty print the quantifier-free formula.

 > $\mathrm{DisplayQuantifierFreeFormula}\left(\mathrm{qff}\right):$
 ${4}{}{a}{}{c}{-}{{b}}^{{2}}{>}{0}$ (11)

We compute the condition on $\left[a,b,c\right]$ for the system to have real solutions.

 > $\mathrm{rrc}≔\mathrm{RealRootClassification}\left(F,N,P,H,3,1..k,R\right)$
 ${\mathrm{rrc}}{≔}\left[\left[{\mathrm{regular_semi_algebraic_set}}\right]{,}{\mathrm{border_polynomial}}\right]$ (12)

We first inspect the border polynomial.

 > $\mathrm{Info}\left({\mathrm{rrc}}_{2},R\right)$
 $\left[{a}{,}{-}{4}{}{a}{}{c}{+}{{b}}^{{2}}\right]$ (13)

We then inspect the regular semi-algebraic set.

 > $\mathrm{rc}≔\mathrm{RepresentingChain}\left({{\mathrm{rrc}}_{1}}_{1},R\right)$
 ${\mathrm{rc}}{≔}{\mathrm{regular_chain}}$ (14)
 > $\mathrm{Info}\left(\mathrm{rc},R\right)$
 $\left[{}\right]$ (15)
 > $\mathrm{rsas}≔{{\mathrm{rrc}}_{1}}_{1}$
 ${\mathrm{rsas}}{≔}{\mathrm{regular_semi_algebraic_set}}$ (16)
 > $\mathrm{pbx}≔\mathrm{RepresentingBox}\left(\mathrm{rsas},R\right)$
 ${\mathrm{pbx}}{≔}{\mathrm{parametric_box}}$ (17)
 > $\mathrm{qff}≔\mathrm{RepresentingQuantifierFreeFormula}\left(\mathrm{pbx}\right)$
 ${\mathrm{qff}}{≔}{\mathrm{quantifier_free_formula}}$ (18)

We now pretty print the quantifier-free formula.

 > $\mathrm{DisplayQuantifierFreeFormula}\left(\mathrm{qff}\right):$
 ${4}{}{a}{}{c}{-}{{b}}^{{2}}{<}{0}$ (19)

Below we make use of the option 'output'='samples' for the cases where the input system has exactly one positive solution when a is positive.

 > $\mathrm{rrc}≔\mathrm{RealRootClassification}\left(F,N,\left[a,x\right],H,3,1,R,\mathrm{output}=\mathrm{samples}\right)$
 ${\mathrm{rrc}}{≔}\left\{\begin{array}{lll}{\mathrm{Parameters}}& {:}& {}\left[{c}{,}{b}{,}{a}\right]\\ {\mathrm{BorderPolynomial}}& {:}& {}\left[{a}{,}{c}{,}{-}{4}{}{a}{}{c}{+}{{b}}^{{2}}\right]\\ {\mathrm{ProjectionPolynomials}}& {:}& {}\left[\left[{c}\right]{,}\left[{b}\right]{,}\left[{a}{,}{-}{4}{}{a}{}{c}{+}{{b}}^{{2}}\right]\right]\\ {\mathrm{SamplePoints}}& {:}& {}\left[\left[{c}{=}{-}\frac{{1}}{{2}}{,}{b}{=}{-}\frac{{1}}{{2}}{,}{a}{=}\frac{{1}}{{2}}\right]{,}\left[{c}{=}{-}\frac{{1}}{{2}}{,}{b}{=}\frac{{1}}{{2}}{,}{a}{=}\frac{{1}}{{2}}\right]\right]\\ {\mathrm{DecomposedSystems}}& {:}& {}\left[\left[\left[{{x}}^{{2}}{}{a}{+}{x}{}{b}{+}{c}\right]{,}\left[{a}{,}{x}\right]\right]\right]\end{array}\right\$ (20)

Using the info printing an alternative and more verbose output is illustrated hereafter.

 > ${\mathrm{infolevel}}_{\mathrm{RegularChains}}≔1:$

We consider another parametric semi-algebraic system.

 > $R≔\mathrm{PolynomialRing}\left(\left[z,y,x,b,a\right]\right)$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (21)
 > $F≔\left[{x}^{2}+{y}^{2}-xy-1,{y}^{2}+{z}^{2}-yz-{a}^{2},{z}^{2}+{x}^{2}-zx-{b}^{2}\right]$
 ${F}{≔}\left[{{x}}^{{2}}{-}{x}{}{y}{+}{{y}}^{{2}}{-}{1}{,}{-}{{a}}^{{2}}{+}{{y}}^{{2}}{-}{y}{}{z}{+}{{z}}^{{2}}{,}{-}{{b}}^{{2}}{+}{{x}}^{{2}}{-}{x}{}{z}{+}{{z}}^{{2}}\right]$ (22)
 > $N≔\left[a-1,b-a\right];$$P≔\left[x,y,z,a,b,a+1-b\right];$$H≔\left[\right]$
 ${N}{≔}\left[{a}{-}{1}{,}{b}{-}{a}\right]$
 ${P}{≔}\left[{x}{,}{y}{,}{z}{,}{a}{,}{b}{,}{a}{+}{1}{-}{b}\right]$
 ${H}{≔}\left[{}\right]$ (23)

We compute the conditions on $\left[b,a\right]$ for the system to have exactly two distinct real solutions.

 > $\mathrm{rrc}≔\mathrm{RealRootClassification}\left(F,N,P,H,2,2,R\right)$
 RealRootClassification:   FINAL RESULT: RealRootClassification:   The system has given number of real solution(s) IF AND ONLY IF RealRootClassification:   [R[1] < 0, 0 < R[2], 0 < R[3]] RealRootClassification:   where                                                   RealRootClassification:   R[1] = a^2-b^2+b-1 RealRootClassification:   R[2] = a^2-b^2+a+1 RealRootClassification:   R[3] = 81*a^12-216*a^10*b^2+144*a^8*b^4-18*a^6*b^6+144*a^4*b^8-216*a^2*b^10+81*b^12-216*a^10+414*a^8*b^2-204*a^6*b^4-204*a^4*b^6+414*a^2*b^8-216*b^10+144*a^8-204*a^6*b^2+241*a^4*b^4-204*a^2*b^6+144*b^8-18*a^6-204*a^4*b^2-204*a^2*b^4-18*b^6+144*a^4+414*a^2*b^2+144*b^4-216*a^2-216*b^2+81 RealRootClassification:   PROVIDED THAT                                                  RealRootClassification:   a-1 <> 0 RealRootClassification:   a-b <> 0 RealRootClassification:   b-1 <> 0 RealRootClassification:   b+1 <> 0 RealRootClassification:   a+1 <> 0 RealRootClassification:   a+b <> 0 RealRootClassification:   a^2-b^2-b-1 <> 0 RealRootClassification:   a^2-b^2+b-1 <> 0 RealRootClassification:   a^2-b^2-a+1 <> 0 RealRootClassification:   a^2-b^2+a+1 <> 0 RealRootClassification:   a^2-a*b+b^2-1 <> 0 RealRootClassification:   a^2+a*b+b^2-1 <> 0 RealRootClassification:   81*a^12-216*a^10*b^2+144*a^8*b^4-18*a^6*b^6+144*a^4*b^8-216*a^2*b^10+81*b^12-216*a^10+414*a^8*b^2-204*a^6*b^4-204*a^4*b^6+414*a^2*b^8-216*b^10+144*a^8-204*a^6*b^2+241*a^4*b^4-204*a^2*b^6+144*b^8-18*a^6-204*a^4*b^2-204*a^2*b^4-18*b^6+144*a^4+414*a^2*b^2+144*b^4-216*a^2-216*b^2+81 <> 0 RealRootClassification:   1.390*seconds
 ${\mathrm{rrc}}{≔}\left[\left[{\mathrm{regular_semi_algebraic_set}}\right]{,}{\mathrm{border_polynomial}}\right]$ (24)

We first inspect the border polynomial.

 > $\mathrm{Info}\left({\mathrm{rrc}}_{2},R\right)$
 $\left[{b}{+}{1}{,}{a}{-}{1}{,}{a}{+}{1}{,}{a}{+}{b}{,}{a}{-}{b}{,}{b}{-}{1}{,}{1}{+}{{b}}^{{12}}{-}\frac{{8}}{{3}}{}{{a}}^{{10}}{-}\frac{{8}}{{3}}{}{{b}}^{{10}}{+}\frac{{16}}{{9}}{}{{a}}^{{8}}{+}\frac{{16}}{{9}}{}{{b}}^{{8}}{-}\frac{{2}}{{9}}{}{{a}}^{{6}}{-}\frac{{2}}{{9}}{}{{b}}^{{6}}{+}\frac{{16}}{{9}}{}{{a}}^{{4}}{+}\frac{{16}}{{9}}{}{{b}}^{{4}}{-}\frac{{8}}{{3}}{}{{a}}^{{2}}{-}\frac{{8}}{{3}}{}{{a}}^{{10}}{}{{b}}^{{2}}{+}\frac{{16}}{{9}}{}{{a}}^{{8}}{}{{b}}^{{4}}{-}\frac{{2}}{{9}}{}{{a}}^{{6}}{}{{b}}^{{6}}{+}\frac{{16}}{{9}}{}{{a}}^{{4}}{}{{b}}^{{8}}{-}\frac{{8}}{{3}}{}{{a}}^{{2}}{}{{b}}^{{10}}{+}\frac{{46}}{{9}}{}{{a}}^{{8}}{}{{b}}^{{2}}{-}\frac{{68}}{{27}}{}{{a}}^{{6}}{}{{b}}^{{4}}{-}\frac{{68}}{{27}}{}{{a}}^{{4}}{}{{b}}^{{6}}{+}\frac{{46}}{{9}}{}{{a}}^{{2}}{}{{b}}^{{8}}{-}\frac{{68}}{{27}}{}{{a}}^{{6}}{}{{b}}^{{2}}{+}\frac{{241}}{{81}}{}{{a}}^{{4}}{}{{b}}^{{4}}{-}\frac{{68}}{{27}}{}{{a}}^{{2}}{}{{b}}^{{6}}{-}\frac{{68}}{{27}}{}{{a}}^{{4}}{}{{b}}^{{2}}{-}\frac{{68}}{{27}}{}{{a}}^{{2}}{}{{b}}^{{4}}{+}\frac{{46}}{{9}}{}{{a}}^{{2}}{}{{b}}^{{2}}{-}\frac{{8}}{{3}}{}{{b}}^{{2}}{+}{{a}}^{{12}}{,}{{a}}^{{2}}{-}{{b}}^{{2}}{-}{b}{-}{1}{,}{{a}}^{{2}}{-}{{b}}^{{2}}{+}{b}{-}{1}{,}{{a}}^{{2}}{-}{{b}}^{{2}}{-}{a}{+}{1}{,}{{a}}^{{2}}{-}{{b}}^{{2}}{+}{a}{+}{1}{,}{{a}}^{{2}}{-}{a}{}{b}{+}{{b}}^{{2}}{-}{1}{,}{{a}}^{{2}}{+}{a}{}{b}{+}{{b}}^{{2}}{-}{1}\right]$ (25)

We then inspect the regular semi-algebraic set.

 > $\mathrm{rc}≔\mathrm{RepresentingChain}\left({{\mathrm{rrc}}_{1}}_{1},R\right)$
 ${\mathrm{rc}}{≔}{\mathrm{regular_chain}}$ (26)
 > $\mathrm{Info}\left(\mathrm{rc},R\right)$
 $\left[{}\right]$ (27)
 > $\mathrm{pbx}≔\mathrm{RepresentingBox}\left({{\mathrm{rrc}}_{1}}_{1},R\right)$
 ${\mathrm{pbx}}{≔}{\mathrm{parametric_box}}$ (28)
 > $\mathrm{qff}≔\mathrm{RepresentingQuantifierFreeFormula}\left(\mathrm{pbx}\right)$
 ${\mathrm{qff}}{≔}{\mathrm{quantifier_free_formula}}$ (29)
 > $\mathrm{DisplayQuantifierFreeFormula}\left(\mathrm{qff}\right):$
 ${{a}}^{{2}}{-}{{b}}^{{2}}{+}{b}{<}{1}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{{a}}^{{2}}{-}{{b}}^{{2}}{+}{a}{+}{1}{>}{0}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{81}{}{{a}}^{{12}}{-}{216}{}{{a}}^{{10}}{}{{b}}^{{2}}{+}{144}{}{{a}}^{{8}}{}{{b}}^{{4}}{-}{18}{}{{a}}^{{6}}{}{{b}}^{{6}}{+}{144}{}{{a}}^{{4}}{}{{b}}^{{8}}{-}{216}{}{{a}}^{{2}}{}{{b}}^{{10}}{+}{81}{}{{b}}^{{12}}{-}{216}{}{{a}}^{{10}}{+}{414}{}{{a}}^{{8}}{}{{b}}^{{2}}{-}{204}{}{{a}}^{{6}}{}{{b}}^{{4}}{-}{204}{}{{a}}^{{4}}{}{{b}}^{{6}}{+}{414}{}{{a}}^{{2}}{}{{b}}^{{8}}{-}{216}{}{{b}}^{{10}}{+}{144}{}{{a}}^{{8}}{-}{204}{}{{a}}^{{6}}{}{{b}}^{{2}}{+}{241}{}{{a}}^{{4}}{}{{b}}^{{4}}{-}{204}{}{{a}}^{{2}}{}{{b}}^{{6}}{+}{144}{}{{b}}^{{8}}{-}{18}{}{{a}}^{{6}}{-}{204}{}{{a}}^{{4}}{}{{b}}^{{2}}{-}{204}{}{{a}}^{{2}}{}{{b}}^{{4}}{-}{18}{}{{b}}^{{6}}{+}{144}{}{{a}}^{{4}}{+}{414}{}{{a}}^{{2}}{}{{b}}^{{2}}{+}{144}{}{{b}}^{{4}}{-}{216}{}{{a}}^{{2}}{-}{216}{}{{b}}^{{2}}{+}{81}{>}{0}$ (30)

We discuss the situation when the parameter satisfies a^2+a+1=0.

 > $\mathrm{RealRootClassification}\left(\left[{a}^{2}+a+1,\mathrm{op}\left(F\right)\right],N,P,H,2,2,R\right)$
 RealRootClassification:   The system does NOT have the given number of real solution(s)! RealRootClassification:   .74e-1*seconds
 $\left[\left[{}\right]{,}{\mathrm{border_polynomial}}\right]$ (31)

In the printed information below, (1)S[1] means that if b is specified and satisfies the output inequality, a should be the least real root of S[1].

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

In the following example, we compute the real root classification of ${x}^{4}+a{x}^{2}+bx+c=0$ when the parameters satisfy $b=0$ and $-2{a}^{3}+8ac-9{b}^{2}=0$.

 > $F≔\left[b,-2{a}^{3}+8ac-9{b}^{2},{x}^{4}+a{x}^{2}+bx+c\right];$$N≔\left[\right];$$P≔\left[\right];$$H≔\left[\right]$
 ${F}{≔}\left[{b}{,}{-}{2}{}{{a}}^{{3}}{+}{8}{}{a}{}{c}{-}{9}{}{{b}}^{{2}}{,}{{x}}^{{4}}{+}{a}{}{{x}}^{{2}}{+}{b}{}{x}{+}{c}\right]$
 ${N}{≔}\left[{}\right]$
 ${P}{≔}\left[{}\right]$
 ${H}{≔}\left[{}\right]$ (33)
 > $\mathrm{RealRootClassification}\left(F,N,P,H,3,1..4,R\right)$
 RealRootClassification:   The system has given number of real solution(s) IF AND ONLY IF RealRootClassification:   [R[1] < 0, (1)S[1], (1)S[2]] RealRootClassification:   where                                                       RealRootClassification:   R[1] = a RealRootClassification:   and                                                         RealRootClassification:   S[1] = b RealRootClassification:   S[2] = a^2-4*c RealRootClassification:   PROVIDED THAT                      RealRootClassification:   a <> 0 RealRootClassification:   .14e-1*seconds
 $\left[\left[{\mathrm{regular_semi_algebraic_set}}\right]{,}{\mathrm{border_polynomial}}\right]$ (34)

References

 Yang, L.; Hou, X.; and Xia, B. "A complete algorithm for automated discovering of a class of inequality-type theorems." Science in China Ser F. Vol. 44, (2001): 33-49.