Interface to QEPCAD#
The basic function of QEPCAD is to construct cylindrical algebraic decompositions (CADs) of \(\RR^k\), given a list of polynomials. Using this CAD, it is possible to perform quantifier elimination and formula simplification.
A CAD for a set \(A\) of \(k\)-variate polynomials decomposes \(\RR^j\) into disjoint cells, for each \(j\) in \(0 \leq j \leq k\). The sign of each polynomial in \(A\) is constant in each cell of \(\RR^k\), and for each cell in \(\RR^j\) (\(j > 1\)), the projection of that cell into \(\RR^{j-1}\) is a cell of \(\RR^{j-1}\). (This property makes the decomposition ‘cylindrical’.)
Given a formula \(\exists x. P(a,b,x) = 0\) (for a polynomial \(P\)), and
a cylindrical algebraic decomposition for \(P\), we can eliminate the
quantifier (find an equivalent formula in the two variables \(a\), \(b\)
without the quantifier \(\exists\)) as follows. For each cell \(C\) in
\(\RR^2\), find the cells of \(\RR^3\) which project to \(C\). (This
collection is called the stack
over \(C\).) Mark \(C\) as true if
some member of the stack has sign \(= 0\); otherwise, mark \(C\) as false.
Then, construct a polynomial formula in \(a\), \(b\) which specifies
exactly the true cells (this is always possible). The same technique
works if the body of the quantifier is any boolean combination of
polynomial equalities and inequalities.
Formula simplification is a similar technique. Given a formula which describes a simple set of \(\RR^k\) in a complicated way as a boolean combination of polynomial equalities and inequalities, QEPCAD can construct a CAD for the polynomials and recover a simple equivalent formula.
Note that while the following documentation is tutorial in nature, and
is written for people who may not be familiar with QEPCAD, it is
documentation for the sage interface rather than for QEPCAD. As
such, it does not cover several issues that are very important to use
QEPCAD efficiently, such as variable ordering, the efficient use of
the alternate quantifiers and _root_
expressions, the
measure-zero-error
command, etc. For more information on
QEPCAD, see the online documentation at
url{http://www.cs.usna.edu/~qepcad/B/QEPCAD.html} and Chris Brown’s
tutorial handout and slides from
url{http://www.cs.usna.edu/~wcbrown/research/ISSAC04/Tutorial.html}.
(Several of the examples in this documentation came from these
sources.)
The examples below require that the optional qepcad package is installed.
QEPCAD can be run in a fully automatic fashion, or interactively. We first demonstrate the automatic use of QEPCAD.
Since sage has no built-in support for quantifiers, this interface
provides qepcad_formula
which helps construct quantified
formulas in the syntax QEPCAD requires.
sage: var('a,b,c,d,x,y,z')
(a, b, c, d, x, y, z)
sage: qf = qepcad_formula
>>> from sage.all import *
>>> var('a,b,c,d,x,y,z')
(a, b, c, d, x, y, z)
>>> qf = qepcad_formula
We start with a simple example. Consider an arbitrarily-selected ellipse:
sage: ellipse = 3*x^2 + 2*x*y + y^2 - x + y - 7
>>> from sage.all import *
>>> ellipse = Integer(3)*x**Integer(2) + Integer(2)*x*y + y**Integer(2) - x + y - Integer(7)
What is the projection onto the \(x\) axis of this ellipse? First we construct a formula asking this question.
sage: F = qf.exists(y, ellipse == 0); F
(E y)[3 x^2 + 2 x y + y^2 - x + y - 7 = 0]
>>> from sage.all import *
>>> F = qf.exists(y, ellipse == Integer(0)); F
(E y)[3 x^2 + 2 x y + y^2 - x + y - 7 = 0]
Then we run qepcad to get the answer:
sage: qepcad(F) # optional - qepcad
8 x^2 - 8 x - 29 <= 0
>>> from sage.all import *
>>> qepcad(F) # optional - qepcad
8 x^2 - 8 x - 29 <= 0
How about the projection onto the \(y\) axis?
sage: qepcad(qf.exists(x, ellipse == 0)) # optional - qepcad
8 y^2 + 16 y - 85 <= 0
>>> from sage.all import *
>>> qepcad(qf.exists(x, ellipse == Integer(0))) # optional - qepcad
8 y^2 + 16 y - 85 <= 0
QEPCAD deals with more quantifiers than just ‘exists’, of course.
Besides the standard ‘forall’, there are also ‘for infinitely
many’, ‘for all but finitely many’, ‘for a connected subset’, and
‘for exactly k’. The qepcad()
documentation has examples
of all of these; here we will just give one example.
First we construct a circle:
sage: circle = x^2 + y^2 - 3
>>> from sage.all import *
>>> circle = x**Integer(2) + y**Integer(2) - Integer(3)
For what values \(k\) does a vertical line \(x=k\) intersect the combined figure of the circle and ellipse exactly three times?
sage: F = qf.exactly_k(3, y, circle * ellipse == 0); F
(X3 y)[(3 x^2 + 2 x y + y^2 - x + y - 7) (x^2 + y^2 - 3) = 0]
sage: qepcad(F) # not tested (random order)
x^2 - 3 <= 0 /\ 8 x^2 - 8 x - 29 <= 0 /\ 8 x^4 - 26 x^2 - 4 x + 13 >= 0 /\ [ 8 x^4 - 26 x^2 - 4 x + 13 = 0 \/ x^2 - 3 = 0 \/ 8 x^2 - 8 x - 29 = 0 ]
>>> from sage.all import *
>>> F = qf.exactly_k(Integer(3), y, circle * ellipse == Integer(0)); F
(X3 y)[(3 x^2 + 2 x y + y^2 - x + y - 7) (x^2 + y^2 - 3) = 0]
>>> qepcad(F) # not tested (random order)
x^2 - 3 <= 0 /\ 8 x^2 - 8 x - 29 <= 0 /\ 8 x^4 - 26 x^2 - 4 x + 13 >= 0 /\ [ 8 x^4 - 26 x^2 - 4 x + 13 = 0 \/ x^2 - 3 = 0 \/ 8 x^2 - 8 x - 29 = 0 ]
Here we see that the solutions are among the eight (\(4 + 2 + 2\)) roots of the three polynomials inside the brackets, but not all of these roots are solutions; the polynomial inequalities outside the brackets are needed to select those roots that are solutions.
QEPCAD also supports an extended formula language, where
_root_k
\(P(\bar x, y)\) refers to a particular zero of
\(P(\bar x, y)\) (viewed as a polynomial in \(y\)). If there are \(n\) roots,
then _root_1
refers to the least root and _root_n
refers to
the greatest. Also, _root_-n
refers to the least root and
_root_-1
refers to the greatest.
This extended language is available both on input and output; see the QEPCAD documentation for more information on how to use this syntax on input. We can request output that is intended to be easy to interpret geometrically; then QEPCAD will use the extended language to produce a solution formula without the selection polynomials.
sage: qepcad(F, solution='geometric') # not tested (random order)
x = _root_1 8 x^2 - 8 x - 29
\/
8 x^4 - 26 x^2 - 4 x + 13 = 0
\/
x = _root_-1 x^2 - 3
>>> from sage.all import *
>>> qepcad(F, solution='geometric') # not tested (random order)
x = _root_1 8 x^2 - 8 x - 29
\/
8 x^4 - 26 x^2 - 4 x + 13 = 0
\/
x = _root_-1 x^2 - 3
We then see that the 6 solutions correspond to the vertical tangent on the left side of the ellipse, the four intersections between the ellipse and the circle, and the vertical tangent on the right side of the circle.
Let us do some basic formula simplification and visualization. We will look at the region which is inside both the ellipse and the circle:
sage: F = qf.and_(ellipse < 0, circle < 0); F
[3 x^2 + 2 x y + y^2 - x + y - 7 < 0 /\ x^2 + y^2 - 3 < 0]
sage: qepcad(F) # not tested (random order)
y^2 + 2 x y + y + 3 x^2 - x - 7 < 0 /\ y^2 + x^2 - 3 < 0
>>> from sage.all import *
>>> F = qf.and_(ellipse < Integer(0), circle < Integer(0)); F
[3 x^2 + 2 x y + y^2 - x + y - 7 < 0 /\ x^2 + y^2 - 3 < 0]
>>> qepcad(F) # not tested (random order)
y^2 + 2 x y + y + 3 x^2 - x - 7 < 0 /\ y^2 + x^2 - 3 < 0
We get back the same formula we put in. This is not surprising (we started with a pretty simple formula, after all), but it is not very enlightening either. Again, if we ask for a ‘geometric’ output, then we see an output that lets us understand something about the shape of the solution set.
sage: qepcad(F, solution='geometric') # not tested (random order)
[
[
x = _root_-2 8 x^4 - 26 x^2 - 4 x + 13
\/
x = _root_2 8 x^4 - 26 x^2 - 4 x + 13
\/
8 x^4 - 26 x^2 - 4 x + 13 < 0
]
/\
y^2 + 2 x y + y + 3 x^2 - x - 7 < 0
/\
y^2 + x^2 - 3 < 0
]
\/
[
x > _root_2 8 x^4 - 26 x^2 - 4 x + 13
/\
x < _root_-2 8 x^4 - 26 x^2 - 4 x + 13
/\
y^2 + x^2 - 3 < 0
]
>>> from sage.all import *
>>> qepcad(F, solution='geometric') # not tested (random order)
[
[
x = _root_-2 8 x^4 - 26 x^2 - 4 x + 13
\/
x = _root_2 8 x^4 - 26 x^2 - 4 x + 13
\/
8 x^4 - 26 x^2 - 4 x + 13 < 0
]
/\
y^2 + 2 x y + y + 3 x^2 - x - 7 < 0
/\
y^2 + x^2 - 3 < 0
]
\/
[
x > _root_2 8 x^4 - 26 x^2 - 4 x + 13
/\
x < _root_-2 8 x^4 - 26 x^2 - 4 x + 13
/\
y^2 + x^2 - 3 < 0
]
There is another reason to prefer output using _root_ expressions; not only does it sometimes give added insight into the geometric structure, it also can be more efficient to construct. Consider this formula for the projection of a particular semicircle onto the \(x\) axis:
sage: F = qf.exists(y, qf.and_(circle == 0, x + y > 0)); F
(E y)[x^2 + y^2 - 3 = 0 /\ x + y > 0]
sage: qepcad(F) # not tested (random order)
x^2 - 3 <= 0 /\ [ x > 0 \/ 2 x^2 - 3 < 0 ]
>>> from sage.all import *
>>> F = qf.exists(y, qf.and_(circle == Integer(0), x + y > Integer(0))); F
(E y)[x^2 + y^2 - 3 = 0 /\ x + y > 0]
>>> qepcad(F) # not tested (random order)
x^2 - 3 <= 0 /\ [ x > 0 \/ 2 x^2 - 3 < 0 ]
Here, the formula \(x > 0\) had to be introduced in order to get a solution formula; the original CAD of F did not include the polynomial \(x\). To avoid having QEPCAD do the extra work to come up with a solution formula, we can tell it to use the extended language; it is always possible to construct a solution formula in the extended language without introducing new polynomials.
sage: qepcad(F, solution='extended') # not tested (random order)
x^2 - 3 <= 0 /\ x > _root_1 2 x^2 - 3
>>> from sage.all import *
>>> qepcad(F, solution='extended') # not tested (random order)
x^2 - 3 <= 0 /\ x > _root_1 2 x^2 - 3
Up to this point, all the output we have seen has basically been in the
form of strings; there is no support (yet) for parsing these outputs
back into sage polynomials (partly because sage does not yet have
support for symbolic conjunctions and disjunctions). The function
qepcad()
supports three more output types that give numbers which
can be manipulated in sage: any-point, all-points, and cell-points.
These output types give dictionaries mapping variable names to values.
With any-point, qepcad()
either produces a single dictionary
specifying a point where the formula is true, or raises an exception
if the formula is false everywhere. With all-points,
qepcad()
either produces a list of dictionaries for all
points where the formula is true, or raises an exception if the
formula is true on infinitely many points. With cell-points,
qepcad()
produces a list of dictionaries with one point for
each cell where the formula is true. (This means you will have at least
one point in each connected component of the solution, although you will
often have many more points than that.)
Let us revisit some of the above examples and get some points to play with. We will start by finding a point on our ellipse.
sage: p = qepcad(ellipse == 0, solution='any-point'); p # optional - qepcad
{'x': -1.468501968502953?, 'y': 0.9685019685029527?}
>>> from sage.all import *
>>> p = qepcad(ellipse == Integer(0), solution='any-point'); p # optional - qepcad
{'x': -1.468501968502953?, 'y': 0.9685019685029527?}
(Note that despite the decimal printing and the question marks, these are really exact numbers.)
We can verify that this point is a solution. To do so, we create a copy of ellipse as a polynomial over \(\QQ\) (instead of a symbolic expression).
sage: pellipse = QQ['x,y'](ellipse)
sage: pellipse(**p) == 0 # optional - qepcad
True
>>> from sage.all import *
>>> pellipse = QQ['x,y'](ellipse)
>>> pellipse(**p) == Integer(0) # optional - qepcad
True
For cell-points, let us look at points not on the ellipse.
sage: pts = qepcad(ellipse != 0, solution='cell-points'); pts # optional - qepcad
[{'x': 4, 'y': 0},
{'x': 2.468501968502953?, 'y': 1},
{'x': 2.468501968502953?, 'y': -9},
{'x': 1/2, 'y': 9},
{'x': 1/2, 'y': -1},
{'x': 1/2, 'y': -5},
{'x': -1.468501968502953?, 'y': 3},
{'x': -1.468501968502953?, 'y': -1},
{'x': -3, 'y': 0}]
>>> from sage.all import *
>>> pts = qepcad(ellipse != Integer(0), solution='cell-points'); pts # optional - qepcad
[{'x': 4, 'y': 0},
{'x': 2.468501968502953?, 'y': 1},
{'x': 2.468501968502953?, 'y': -9},
{'x': 1/2, 'y': 9},
{'x': 1/2, 'y': -1},
{'x': 1/2, 'y': -5},
{'x': -1.468501968502953?, 'y': 3},
{'x': -1.468501968502953?, 'y': -1},
{'x': -3, 'y': 0}]
For the points here which are in full-dimensional cells, QEPCAD has the freedom to choose rational sample points, and it does so.
And, of course, all these points really are not on the ellipse.
sage: [pellipse(**p) != 0 for p in pts] # optional - qepcad
[True, True, True, True, True, True, True, True, True]
>>> from sage.all import *
>>> [pellipse(**p) != Integer(0) for p in pts] # optional - qepcad
[True, True, True, True, True, True, True, True, True]
Finally, for all-points, let us look again at finding vertical lines that intersect the union of the circle and the ellipse exactly three times.
sage: F = qf.exactly_k(3, y, circle * ellipse == 0); F
(X3 y)[(3 x^2 + 2 x y + y^2 - x + y - 7) (x^2 + y^2 - 3) = 0]
sage: pts = qepcad(F, solution='all-points'); pts # optional - qepcad
[{'x': 1.732050807568878?}, {'x': 1.731054913462534?}, {'x': 0.678911384208004?}, {'x': -0.9417727377417167?}, {'x': -1.468193559928821?}, {'x': -1.468501968502953?}]
>>> from sage.all import *
>>> F = qf.exactly_k(Integer(3), y, circle * ellipse == Integer(0)); F
(X3 y)[(3 x^2 + 2 x y + y^2 - x + y - 7) (x^2 + y^2 - 3) = 0]
>>> pts = qepcad(F, solution='all-points'); pts # optional - qepcad
[{'x': 1.732050807568878?}, {'x': 1.731054913462534?}, {'x': 0.678911384208004?}, {'x': -0.9417727377417167?}, {'x': -1.468193559928821?}, {'x': -1.468501968502953?}]
Since \(y\) is bound by the quantifier, the solutions only refer to \(x\).
We can substitute one of these solutions into the original equation:
sage: pt = pts[0] # optional - qepcad
sage: pcombo = QQ['x,y'](circle * ellipse)
sage: intersections = pcombo(y=polygen(AA, 'y'), **pt); intersections # optional - qepcad
y^4 + 4.464101615137755?*y^3 + 0.2679491924311227?*y^2
>>> from sage.all import *
>>> pt = pts[Integer(0)] # optional - qepcad
>>> pcombo = QQ['x,y'](circle * ellipse)
>>> intersections = pcombo(y=polygen(AA, 'y'), **pt); intersections # optional - qepcad
y^4 + 4.464101615137755?*y^3 + 0.2679491924311227?*y^2
and verify that it does have three roots:
sage: intersections.roots() # optional - qepcad
[(-4.403249005600958?, 1), (-0.06085260953679653?, 1), (0, 2)]
>>> from sage.all import *
>>> intersections.roots() # optional - qepcad
[(-4.403249005600958?, 1), (-0.06085260953679653?, 1), (0, 2)]
Let us check all six solutions.
sage: [len(pcombo(y=polygen(AA, 'y'), **p).roots()) for p in pts] # optional - qepcad
[3, 3, 3, 3, 3, 3]
>>> from sage.all import *
>>> [len(pcombo(y=polygen(AA, 'y'), **p).roots()) for p in pts] # optional - qepcad
[3, 3, 3, 3, 3, 3]
We said earlier that we can run QEPCAD either automatically or interactively. Now that we have discussed the automatic modes, let us turn to interactive uses.
If the qepcad()
function is passed interact=True
, then
instead of returning a result, it returns an object of class
Qepcad
representing a running instance of QEPCAD that you can
interact with. For example:
sage: qe = qepcad(qf.forall(x, x^2 + b*x + c > 0), interact=True); qe # optional - qepcad
QEPCAD object in phase 'Before Normalization'
>>> from sage.all import *
>>> qe = qepcad(qf.forall(x, x**Integer(2) + b*x + c > Integer(0)), interact=True); qe # optional - qepcad
QEPCAD object in phase 'Before Normalization'
This object is a fairly thin wrapper over QEPCAD; most QEPCAD commands
are available as methods on the Qepcad
object. Given a
Qepcad
object qe
, you can type qe.[tab]
to see
the available QEPCAD commands; to see the documentation for an
individual QEPCAD command, for example d_setting
, you can type
qe.d_setting?
. (In QEPCAD, this command is called
d-setting
. We systematically replace hyphens with underscores
for this interface.)
The execution of QEPCAD is divided into four phases. Most commands are
not available during all phases. We saw above that QEPCAD starts out
in phase 'Before Normalization'
. We see that the d_cell
command
is not available in this phase:
sage: qe.d_cell() # optional - qepcad
Error GETCID: This command is not active here.
>>> from sage.all import *
>>> qe.d_cell() # optional - qepcad
Error GETCID: This command is not active here.
We will focus here on the fourth (and last) phase, 'Before Solution'
,
because this interface has special support for some operations in this
phase. Consult the QEPCAD documentation for information on the other
phases.
We can tell QEPCAD to finish off the current phase and move to the
next with its go
command. (There is also the step
command, which partially completes a phase for phases that have
multiple steps, and the finish
command, which runs QEPCAD to
completion.)
sage: qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (x)'
sage: qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Choice'
sage: qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Solution'
>>> from sage.all import *
>>> qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (x)'
>>> qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Choice'
>>> qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Solution'
Note that the Qepcad
object returns the new phase whenever the
phase changes, as a convenience for interactive use; except that when
the new phase is 'EXITED'
, the solution formula printed by QEPCAD is
returned instead.
sage: qe.go() # optional - qepcad
4 c - b^2 > 0
sage: qe # optional - qepcad
QEPCAD object in phase 'EXITED'
>>> from sage.all import *
>>> qe.go() # optional - qepcad
4 c - b^2 > 0
>>> qe # optional - qepcad
QEPCAD object in phase 'EXITED'
Let us pick a nice, simple example, return to phase 4, and explore the
resulting qe
object.
sage: qe = qepcad(circle == 0, interact=True); qe # optional - qepcad
QEPCAD object in phase 'Before Normalization'
sage: qe.go(); qe.go(); qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (y)'
QEPCAD object has moved to phase 'Before Choice'
QEPCAD object has moved to phase 'Before Solution'
>>> from sage.all import *
>>> qe = qepcad(circle == Integer(0), interact=True); qe # optional - qepcad
QEPCAD object in phase 'Before Normalization'
>>> qe.go(); qe.go(); qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (y)'
QEPCAD object has moved to phase 'Before Choice'
QEPCAD object has moved to phase 'Before Solution'
We said before that QEPCAD creates ‘cylindrical algebraic decompositions’; since we have a bivariate polynomial, we get decompositions of \(\RR^0\), \(\RR^1\), and \(\RR^2\). In this case, where our example is a circle of radius \(\sqrt{3}\) centered on the origin, these decompositions are as follows:
The decomposition of \(\RR^0\) is trivial (of course). The
decomposition of \(\RR^1\) has five cells: \(x < -\sqrt{3}\), \(x =
-\sqrt{3}\), \(-\sqrt{3} < x < \sqrt{3}\), \(x = \sqrt{3}\), and \(x >
\sqrt{3}\). These five cells comprise the stack
over the single
cell in the trivial decomposition of \(\RR^0\).
These five cells give rise to five stacks in \(\RR^2\). The first and fifth stack have just one cell apiece. The second and fourth stacks have three cells: \(y < 0\), \(y = 0\), and \(y > 0\). The third stack has five cells: below the circle, the lower semicircle, the interior of the circle, the upper semicircle, and above the circle.
QEPCAD (and this QEPCAD interface) number the cells in a stack
starting with 1. Each cell has an index
, which is a tuple of
integers describing the path to the cell in the tree of all cells.
For example, the cell ‘below the circle’ has index (3,1) (the first
cell in the stack over the third cell of \(\RR^1\)) and the interior of
the circle has index (3,3).
We can view these cells with the QEPCAD command d_cell
. For
instance, let us look at the cell for the upper semicircle:
sage: qe.d_cell(3, 4) # optional - qepcad
---------- Information about the cell (3,4) ----------
Level : 2
Dimension : 1
Number of children : 0
Truth value : T by trial evaluation.
Degrees after substitution : Not known yet or No polynomial.
Multiplicities : ((1,1))
Signs of Projection Factors
Level 1 : (-)
Level 2 : (0)
---------- Sample point ----------
The sample point is in a PRIMITIVE representation.
alpha = the unique root of x^2 - 3 between 0 and 4
= 1.7320508076-
Coordinate 1 = 0
= 0.0000000000
Coordinate 2 = alpha
= 1.7320508076-
----------------------------------------------------
>>> from sage.all import *
>>> qe.d_cell(Integer(3), Integer(4)) # optional - qepcad
---------- Information about the cell (3,4) ----------
Level : 2
Dimension : 1
Number of children : 0
Truth value : T by trial evaluation.
Degrees after substitution : Not known yet or No polynomial.
Multiplicities : ((1,1))
Signs of Projection Factors
Level 1 : (-)
Level 2 : (0)
---------- Sample point ----------
The sample point is in a PRIMITIVE representation.
<BLANKLINE>
alpha = the unique root of x^2 - 3 between 0 and 4
= 1.7320508076-
<BLANKLINE>
Coordinate 1 = 0
= 0.0000000000
Coordinate 2 = alpha
= 1.7320508076-
----------------------------------------------------
We see that, the level of this cell is 2, meaning that it is part of the decomposition of \(\RR^2\). The dimension is 1, meaning that the cell is homeomorphic to a line (rather than a plane or a point). The sample point gives the coordinates of one point in the cell, both symbolically and numerically.
For programmatic access to cells, we have defined a sage wrapper class
QepcadCell
. These cells can be created with the
cell()
method; for example:
sage: c = qe.cell(3, 4); c # optional - qepcad
QEPCAD cell (3, 4)
>>> from sage.all import *
>>> c = qe.cell(Integer(3), Integer(4)); c # optional - qepcad
QEPCAD cell (3, 4)
A QepcadCell
has accessor methods for the important state held
within a cell. For instance:
sage: # optional - qepcad
sage: c.level()
2
sage: c.index()
(3, 4)
sage: qe.cell(3).number_of_children()
5
sage: len(qe.cell(3))
5
>>> from sage.all import *
>>> # optional - qepcad
>>> c.level()
2
>>> c.index()
(3, 4)
>>> qe.cell(Integer(3)).number_of_children()
5
>>> len(qe.cell(Integer(3)))
5
One particularly useful thing we can get from a cell is its sample point, as sage algebraic real numbers.
sage: c.sample_point() # optional - qepcad
(0, 1.732050807568878?)
sage: c.sample_point_dict() # optional - qepcad
{'x': 0, 'y': 1.732050807568878?}
>>> from sage.all import *
>>> c.sample_point() # optional - qepcad
(0, 1.732050807568878?)
>>> c.sample_point_dict() # optional - qepcad
{'x': 0, 'y': 1.732050807568878?}
We have seen that we can get cells using the cell()
method.
There are several QEPCAD commands that print lists of cells; we can
also get cells using the make_cells()
method, passing it the
output of one of these commands.
sage: qe.make_cells(qe.d_true_cells()) # optional - qepcad
[QEPCAD cell (4, 2), QEPCAD cell (3, 4), QEPCAD cell (3, 2),
QEPCAD cell (2, 2)]
>>> from sage.all import *
>>> qe.make_cells(qe.d_true_cells()) # optional - qepcad
[QEPCAD cell (4, 2), QEPCAD cell (3, 4), QEPCAD cell (3, 2),
QEPCAD cell (2, 2)]
Also, the cells in the stack over a given cell can be accessed using array subscripting or iteration. (Remember that cells in a stack are numbered starting with one; we preserve this convention in the array-subscripting syntax.)
sage: c = qe.cell(3) # optional - qepcad
sage: c[1] # optional - qepcad
QEPCAD cell (3, 1)
sage: [c2 for c2 in c] # optional - qepcad
[QEPCAD cell (3, 1), QEPCAD cell (3, 2), QEPCAD cell (3, 3),
QEPCAD cell (3, 4), QEPCAD cell (3, 5)]
>>> from sage.all import *
>>> c = qe.cell(Integer(3)) # optional - qepcad
>>> c[Integer(1)] # optional - qepcad
QEPCAD cell (3, 1)
>>> [c2 for c2 in c] # optional - qepcad
[QEPCAD cell (3, 1), QEPCAD cell (3, 2), QEPCAD cell (3, 3),
QEPCAD cell (3, 4), QEPCAD cell (3, 5)]
We can do one more thing with a cell: we can set its truth value. Once the truth values of the cells have been set, we can get QEPCAD to produce a formula which is true in exactly the cells we have selected. This is useful if QEPCAD’s quantifier language is insufficient to express your problem.
For example, consider again our combined figure of the circle and the ellipse. Suppose you want to find all vertical lines that intersect the circle twice, and also intersect the ellipse twice. The vertical lines that intersect the circle twice can be found by simplifying:
sage: F = qf.exactly_k(2, y, circle == 0); F
(X2 y)[x^2 + y^2 - 3 = 0]
>>> from sage.all import *
>>> F = qf.exactly_k(Integer(2), y, circle == Integer(0)); F
(X2 y)[x^2 + y^2 - 3 = 0]
and the vertical lines that intersect the ellipse twice are expressed by:
sage: G = qf.exactly_k(2, y, ellipse == 0); G
(X2 y)[3 x^2 + 2 x y + y^2 - x + y - 7 = 0]
>>> from sage.all import *
>>> G = qf.exactly_k(Integer(2), y, ellipse == Integer(0)); G
(X2 y)[3 x^2 + 2 x y + y^2 - x + y - 7 = 0]
and the lines that intersect both figures would be:
sage: qf.and_(F, G)
Traceback (most recent call last):
...
ValueError: QEPCAD formulas must be in prenex (quantifiers outermost) form
>>> from sage.all import *
>>> qf.and_(F, G)
Traceback (most recent call last):
...
ValueError: QEPCAD formulas must be in prenex (quantifiers outermost) form
…except that QEPCAD does not support formulas like this; in QEPCAD input, all logical connectives must be inside all quantifiers.
Instead, we can get QEPCAD to construct a CAD for our combined figure and set the truth values ourselves. (The exact formula we use doesn’t matter, since we’re going to replace the truth values in the cells; we just need to use a formula that uses both polynomials.)
sage: qe = qepcad(qf.and_(ellipse == 0, circle == 0), interact=True) # optional - qepcad
sage: qe.go(); qe.go(); qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (y)'
QEPCAD object has moved to phase 'Before Choice'
QEPCAD object has moved to phase 'Before Solution'
>>> from sage.all import *
>>> qe = qepcad(qf.and_(ellipse == Integer(0), circle == Integer(0)), interact=True) # optional - qepcad
>>> qe.go(); qe.go(); qe.go() # optional - qepcad
QEPCAD object has moved to phase 'Before Projection (y)'
QEPCAD object has moved to phase 'Before Choice'
QEPCAD object has moved to phase 'Before Solution'
Now we want to find all cells \(c\) in the decomposition of \(\RR^1\) such that the stack over \(c\) contains exactly two cells on the ellipse, and also contains exactly two cells on the circle.
Our input polynomials are ‘level-2 projection factors’, we see:
sage: qe.d_proj_factors() # optional - qepcad
P_1,1 = fac(J_1,1) = fac(dis(A_2,1))
= 8 x^2 - 8 x - 29
P_1,2 = fac(J_1,2) = fac(dis(A_2,2))
= x^2 - 3
P_1,3 = fac(J_1,3) = fac(res(A_2,1|A_2,2))
= 8 x^4 - 26 x^2 - 4 x + 13
A_2,1 = input
= y^2 + 2 x y + y + 3 x^2 - x - 7
A_2,2 = input
= y^2 + x^2 - 3
>>> from sage.all import *
>>> qe.d_proj_factors() # optional - qepcad
P_1,1 = fac(J_1,1) = fac(dis(A_2,1))
= 8 x^2 - 8 x - 29
P_1,2 = fac(J_1,2) = fac(dis(A_2,2))
= x^2 - 3
P_1,3 = fac(J_1,3) = fac(res(A_2,1|A_2,2))
= 8 x^4 - 26 x^2 - 4 x + 13
A_2,1 = input
= y^2 + 2 x y + y + 3 x^2 - x - 7
A_2,2 = input
= y^2 + x^2 - 3
so we can test whether a cell is on the ellipse by checking that the sign of the corresponding projection factor is 0 in our cell. For instance, the cell (12,2) is on the ellipse:
sage: qe.cell(12,2).signs()[1][0] # optional - qepcad
0
>>> from sage.all import *
>>> qe.cell(Integer(12),Integer(2)).signs()[Integer(1)][Integer(0)] # optional - qepcad
0
So we can update the truth values as desired like this:
sage: for c in qe.cell(): # optional - qepcad
....: count_ellipse = 0
....: count_circle = 0
....: for c2 in c:
....: count_ellipse += (c2.signs()[1][0] == 0)
....: count_circle += (c2.signs()[1][1] == 0)
....: c.set_truth(count_ellipse == 2 and count_circle == 2)
>>> from sage.all import *
>>> for c in qe.cell(): # optional - qepcad
... count_ellipse = Integer(0)
... count_circle = Integer(0)
... for c2 in c:
... count_ellipse += (c2.signs()[Integer(1)][Integer(0)] == Integer(0))
... count_circle += (c2.signs()[Integer(1)][Integer(1)] == Integer(0))
... c.set_truth(count_ellipse == Integer(2) and count_circle == Integer(2))
and then we can get our desired solution formula. (The 'G'
stands for
'geometric'
, and gives solutions using the same rules as
solution='geometric'
described above.)
sage: qe.solution_extension('G') # not tested (random order)
8 x^2 - 8 x - 29 < 0
/\
x^2 - 3 < 0
>>> from sage.all import *
>>> qe.solution_extension('G') # not tested (random order)
8 x^2 - 8 x - 29 < 0
/\
x^2 - 3 < 0
AUTHORS:
Carl Witty (2008-03): initial version
Thierry Monteil (2015-07) repackaging + noncommutative doctests.
- class sage.interfaces.qepcad.Qepcad(formula, vars=None, logfile=None, verbose=False, memcells=None, server=None)[source]#
Bases:
object
The wrapper for QEPCAD.
- answer()[source]#
For a QEPCAD instance which is finished, return the simplified quantifier-free formula that it printed just before exiting.
EXAMPLES:
sage: qe = qepcad(x^3 - x == 0, interact=True) # optional - qepcad sage: qe.finish() # not tested (random order) x - 1 <= 0 /\ x + 1 >= 0 /\ [ x = 0 \/ x - 1 = 0 \/ x + 1 = 0 ] sage: qe.answer() # not tested (random order) x - 1 <= 0 /\ x + 1 >= 0 /\ [ x = 0 \/ x - 1 = 0 \/ x + 1 = 0 ]
>>> from sage.all import * >>> qe = qepcad(x**Integer(3) - x == Integer(0), interact=True) # optional - qepcad >>> qe.finish() # not tested (random order) x - 1 <= 0 /\ x + 1 >= 0 /\ [ x = 0 \/ x - 1 = 0 \/ x + 1 = 0 ] >>> qe.answer() # not tested (random order) x - 1 <= 0 /\ x + 1 >= 0 /\ [ x = 0 \/ x - 1 = 0 \/ x + 1 = 0 ]
- assume(assume)[source]#
The following documentation is from
qepcad.help
.Add an assumption to the problem. These will not be included in the solution formula.
For example, with input (E x)[ a x^2 + b x + c = 0], if we issue the command
assume [ a /= 0 ]
we will get the solution formula b^2 - 4 a c >= 0. Without the assumption we’d get something like [a = 0 /b /= 0] / [a /= 0 /4 a c - b^2 <= 0] / [a = 0 /b = 0 /c = 0].
EXAMPLES:
sage: var('a,b,c,x') (a, b, c, x) sage: qf = qepcad_formula sage: qe = qepcad(qf.exists(x, a*x^2 + b*x + c == 0), interact=True) # optional - qepcad sage: qe.assume(a != 0) # optional - qepcad sage: qe.finish() # optional - qepcad 4 a c - b^2 <= 0
>>> from sage.all import * >>> var('a,b,c,x') (a, b, c, x) >>> qf = qepcad_formula >>> qe = qepcad(qf.exists(x, a*x**Integer(2) + b*x + c == Integer(0)), interact=True) # optional - qepcad >>> qe.assume(a != Integer(0)) # optional - qepcad >>> qe.finish() # optional - qepcad 4 a c - b^2 <= 0
- cell(*index)[source]#
Given a cell index, returns a
QepcadCell
wrapper for that cell. Uses a cache for efficiency.EXAMPLES:
sage: # optional - qepcad sage: qe = qepcad(x + 3 == 42, interact=True) sage: qe.go(); qe.go(); qe.go() QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.cell(2) QEPCAD cell (2) sage: qe.cell(2) is qe.cell(2) True
>>> from sage.all import * >>> # optional - qepcad >>> qe = qepcad(x + Integer(3) == Integer(42), interact=True) >>> qe.go(); qe.go(); qe.go() QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.cell(Integer(2)) QEPCAD cell (2) >>> qe.cell(Integer(2)) is qe.cell(Integer(2)) True
- final_stats()[source]#
For a QEPCAD instance which is finished, return the statistics that it printed just before exiting.
EXAMPLES:
sage: qe = qepcad(x == 0, interact=True) # optional - qepcad sage: qe.finish() # optional - qepcad x = 0 sage: qe.final_stats() # random, optional - qepcad ----------------------------------------------------------------------------- 0 Garbage collections, 0 Cells and 0 Arrays reclaimed, in 0 milliseconds. 492840 Cells in AVAIL, 500000 Cells in SPACE. System time: 8 milliseconds. System time after the initialization: 4 milliseconds. -----------------------------------------------------------------------------
>>> from sage.all import * >>> qe = qepcad(x == Integer(0), interact=True) # optional - qepcad >>> qe.finish() # optional - qepcad x = 0 >>> qe.final_stats() # random, optional - qepcad ----------------------------------------------------------------------------- 0 Garbage collections, 0 Cells and 0 Arrays reclaimed, in 0 milliseconds. 492840 Cells in AVAIL, 500000 Cells in SPACE. System time: 8 milliseconds. System time after the initialization: 4 milliseconds. -----------------------------------------------------------------------------
- make_cells(text)[source]#
Given the result of some QEPCAD command that returns cells (such as
d_cell()
,d_witness_list()
, etc.), return a list of cell objects.EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.make_cells(qe.d_false_cells()) # optional - qepcad [QEPCAD cell (5, 1), QEPCAD cell (4, 3), QEPCAD cell (4, 1), QEPCAD cell (3, 5), QEPCAD cell (3, 3), QEPCAD cell (3, 1), QEPCAD cell (2, 3), QEPCAD cell (2, 1), QEPCAD cell (1, 1)]
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.make_cells(qe.d_false_cells()) # optional - qepcad [QEPCAD cell (5, 1), QEPCAD cell (4, 3), QEPCAD cell (4, 1), QEPCAD cell (3, 5), QEPCAD cell (3, 3), QEPCAD cell (3, 1), QEPCAD cell (2, 3), QEPCAD cell (2, 1), QEPCAD cell (1, 1)]
- phase()[source]#
Return the current phase of the QEPCAD program.
EXAMPLES:
sage: # optional - qepcad sage: qe = qepcad(x > 2/3, interact=True) sage: qe.phase() 'Before Normalization' sage: qe.go() QEPCAD object has moved to phase 'At the end of projection phase' sage: qe.phase() 'At the end of projection phase' sage: qe.go() QEPCAD object has moved to phase 'Before Choice' sage: qe.phase() 'Before Choice' sage: qe.go() QEPCAD object has moved to phase 'Before Solution' sage: qe.phase() 'Before Solution' sage: qe.go() 3 x - 2 > 0 sage: qe.phase() 'EXITED'
>>> from sage.all import * >>> # optional - qepcad >>> qe = qepcad(x > Integer(2)/Integer(3), interact=True) >>> qe.phase() 'Before Normalization' >>> qe.go() QEPCAD object has moved to phase 'At the end of projection phase' >>> qe.phase() 'At the end of projection phase' >>> qe.go() QEPCAD object has moved to phase 'Before Choice' >>> qe.phase() 'Before Choice' >>> qe.go() QEPCAD object has moved to phase 'Before Solution' >>> qe.phase() 'Before Solution' >>> qe.go() 3 x - 2 > 0 >>> qe.phase() 'EXITED'
- set_truth_value(index, nv)[source]#
Given a cell index (or a cell) and an integer, set the truth value of the cell to that integer.
Valid integers are 0 (false), 1 (true), and 2 (undetermined).
EXAMPLES:
sage: qe = qepcad(x == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.set_truth_value(1, 1) # optional - qepcad
>>> from sage.all import * >>> qe = qepcad(x == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.set_truth_value(Integer(1), Integer(1)) # optional - qepcad
- solution_extension(kind)[source]#
The following documentation is modified from
qepcad.help
:solution-extension x
Use an alternative solution formula construction method. The parameter x is allowed to be T,E, or G. If x is T, then a formula in the usual language of Tarski formulas is produced. If x is E, a formula in the language of Extended Tarski formulas is produced. If x is G, then a geometry-based formula is produced.
EXAMPLES:
sage: var('x,y') (x, y) sage: qf = qepcad_formula sage: qe = qepcad(qf.and_(x^2 + y^2 - 3 == 0, x + y > 0), interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.solution_extension('E') # not tested (random order) x > _root_1 2 x^2 - 3 /\ y^2 + x^2 - 3 = 0 /\ [ 2 x^2 - 3 > 0 \/ y = _root_-1 y^2 + x^2 - 3 ] sage: qe.solution_extension('G') # not tested (random order) [ [ 2 x^2 - 3 < 0 \/ x = _root_-1 2 x^2 - 3 ] /\ y = _root_-1 y^2 + x^2 - 3 ] \/ [ x^2 - 3 <= 0 /\ x > _root_-1 2 x^2 - 3 /\ y^2 + x^2 - 3 = 0 ] sage: qe.solution_extension('T') # not tested (random order) y + x > 0 /\ y^2 + x^2 - 3 = 0
>>> from sage.all import * >>> var('x,y') (x, y) >>> qf = qepcad_formula >>> qe = qepcad(qf.and_(x**Integer(2) + y**Integer(2) - Integer(3) == Integer(0), x + y > Integer(0)), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.solution_extension('E') # not tested (random order) x > _root_1 2 x^2 - 3 /\ y^2 + x^2 - 3 = 0 /\ [ 2 x^2 - 3 > 0 \/ y = _root_-1 y^2 + x^2 - 3 ] >>> qe.solution_extension('G') # not tested (random order) [ [ 2 x^2 - 3 < 0 \/ x = _root_-1 2 x^2 - 3 ] /\ y = _root_-1 y^2 + x^2 - 3 ] \/ [ x^2 - 3 <= 0 /\ x > _root_-1 2 x^2 - 3 /\ y^2 + x^2 - 3 = 0 ] >>> qe.solution_extension('T') # not tested (random order) y + x > 0 /\ y^2 + x^2 - 3 = 0
- class sage.interfaces.qepcad.QepcadCell(parent, lines)[source]#
Bases:
object
A wrapper for a QEPCAD cell.
- index()[source]#
Give the index of a QEPCAD cell.
EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.cell().index() # optional - qepcad () sage: qe.cell(1).index() # optional - qepcad (1,) sage: qe.cell(2, 2).index() # optional - qepcad (2, 2)
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.cell().index() # optional - qepcad () >>> qe.cell(Integer(1)).index() # optional - qepcad (1,) >>> qe.cell(Integer(2), Integer(2)).index() # optional - qepcad (2, 2)
- level()[source]#
Return the level of a QEPCAD cell.
EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.cell().level() # optional - qepcad 0 sage: qe.cell(1).level() # optional - qepcad 1 sage: qe.cell(2, 2).level() # optional - qepcad 2
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.cell().level() # optional - qepcad 0 >>> qe.cell(Integer(1)).level() # optional - qepcad 1 >>> qe.cell(Integer(2), Integer(2)).level() # optional - qepcad 2
- number_of_children()[source]#
Return the number of elements in the stack over a QEPCAD cell. (This is always an odd number, if the stack has been constructed.)
EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.cell().number_of_children() # optional - qepcad 5 sage: [c.number_of_children() for c in qe.cell()] # optional - qepcad [1, 3, 5, 3, 1]
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.cell().number_of_children() # optional - qepcad 5 >>> [c.number_of_children() for c in qe.cell()] # optional - qepcad [1, 3, 5, 3, 1]
- sample_point()[source]#
Return the coordinates of a point in the cell, as a tuple of sage algebraic reals.
EXAMPLES:
sage: # optional - qepcad sage: qe = qepcad(x^2 - x - 1 == 0, interact=True) sage: qe.go(); qe.go(); qe.go() QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: v1 = qe.cell(2).sample_point()[0]; v1 -0.618033988749895? sage: v2 = qe.cell(4).sample_point()[0]; v2 1.618033988749895? sage: v1 + v2 == 1 True
>>> from sage.all import * >>> # optional - qepcad >>> qe = qepcad(x**Integer(2) - x - Integer(1) == Integer(0), interact=True) >>> qe.go(); qe.go(); qe.go() QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> v1 = qe.cell(Integer(2)).sample_point()[Integer(0)]; v1 -0.618033988749895? >>> v2 = qe.cell(Integer(4)).sample_point()[Integer(0)]; v2 1.618033988749895? >>> v1 + v2 == Integer(1) True
- sample_point_dict()[source]#
Return the coordinates of a point in the cell, as a dictionary mapping variable names (as strings) to sage algebraic reals.
EXAMPLES:
sage: qe = qepcad(x^2 - x - 1 == 0, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.cell(4).sample_point_dict() # optional - qepcad {'x': 1.618033988749895?}
>>> from sage.all import * >>> qe = qepcad(x**Integer(2) - x - Integer(1) == Integer(0), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'At the end of projection phase' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.cell(Integer(4)).sample_point_dict() # optional - qepcad {'x': 1.618033988749895?}
- set_truth(v)[source]#
Set the truth value of this cell, as used by QEPCAD for solution formula construction.
The argument
v
should be either a boolean orNone
(which will set the truth value to'undetermined'
).EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: qe.solution_extension('T') # optional - qepcad y^2 + x^2 - 1 = 0 sage: qe.cell(3, 3).set_truth(True) # optional - qepcad sage: qe.solution_extension('T') # optional - qepcad y^2 + x^2 - 1 <= 0
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> qe.solution_extension('T') # optional - qepcad y^2 + x^2 - 1 = 0 >>> qe.cell(Integer(3), Integer(3)).set_truth(True) # optional - qepcad >>> qe.solution_extension('T') # optional - qepcad y^2 + x^2 - 1 <= 0
- signs()[source]#
Return the sign vector of a QEPCAD cell.
This is a list of lists. The outer list contains one element for each level of the cell; the inner list contains one element for each projection factor at that level. These elements are either -1, 0, or 1.
EXAMPLES:
sage: var('x,y') (x, y) sage: qe = qepcad(x^2 + y^2 == 1, interact=True) # optional - qepcad sage: qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' sage: from sage.interfaces.qepcad import QepcadCell sage: all_cells = flatten(qe.cell(), ltypes=QepcadCell, max_level=1) # optional - qepcad sage: [(c, c.signs()[1][0]) for c in all_cells] # optional - qepcad [(QEPCAD cell (1, 1), 1), (QEPCAD cell (2, 1), 1), (QEPCAD cell (2, 2), 0), (QEPCAD cell (2, 3), 1), (QEPCAD cell (3, 1), 1), (QEPCAD cell (3, 2), 0), (QEPCAD cell (3, 3), -1), (QEPCAD cell (3, 4), 0), (QEPCAD cell (3, 5), 1), (QEPCAD cell (4, 1), 1), (QEPCAD cell (4, 2), 0), (QEPCAD cell (4, 3), 1), (QEPCAD cell (5, 1), 1)]
>>> from sage.all import * >>> var('x,y') (x, y) >>> qe = qepcad(x**Integer(2) + y**Integer(2) == Integer(1), interact=True) # optional - qepcad >>> qe.go(); qe.go(); qe.go() # optional - qepcad QEPCAD object has moved to phase 'Before Projection (y)' QEPCAD object has moved to phase 'Before Choice' QEPCAD object has moved to phase 'Before Solution' >>> from sage.interfaces.qepcad import QepcadCell >>> all_cells = flatten(qe.cell(), ltypes=QepcadCell, max_level=Integer(1)) # optional - qepcad >>> [(c, c.signs()[Integer(1)][Integer(0)]) for c in all_cells] # optional - qepcad [(QEPCAD cell (1, 1), 1), (QEPCAD cell (2, 1), 1), (QEPCAD cell (2, 2), 0), (QEPCAD cell (2, 3), 1), (QEPCAD cell (3, 1), 1), (QEPCAD cell (3, 2), 0), (QEPCAD cell (3, 3), -1), (QEPCAD cell (3, 4), 0), (QEPCAD cell (3, 5), 1), (QEPCAD cell (4, 1), 1), (QEPCAD cell (4, 2), 0), (QEPCAD cell (4, 3), 1), (QEPCAD cell (5, 1), 1)]
- class sage.interfaces.qepcad.QepcadFunction(parent, name)[source]#
Bases:
ExpectFunction
A wrapper for a QEPCAD command.
- class sage.interfaces.qepcad.Qepcad_expect(memcells=None, maxread=None, logfile=None, server=None)[source]#
Bases:
ExtraTabCompletion
,Expect
The low-level wrapper for QEPCAD.
- sage.interfaces.qepcad.qepcad(formula, assume=None, interact=False, solution=None, vars=None, **kwargs)[source]#
Quantifier elimination and formula simplification using QEPCAD B.
If
assume
is specified, then the given formula is'assumed'
, which is taken into account during final solution formula construction.If
interact=True
is given, then aQepcad
object is returned which can be interacted with either at the command line or programmatically.The type of solution returned can be adjusted with
solution
. The options are'geometric'
, which tries to construct a solution formula with geometric meaning;'extended'
, which gives a solution formula in an extended language that may be more efficient to construct;'any-point'
, which returns any point where the formula is true;'all-points'
, which returns a list of all points where the formula is true (or raises an exception if there are infinitely many); and'cell-points'
, which returns one point in each cell where the formula is true.All other keyword arguments are passed through to the
Qepcad
constructor.For much more documentation and many more examples, see the module docstring for this module (type
sage.interfaces.qepcad?
to read this docstring from the sage command line).The examples below require that the optional qepcad package is installed.
EXAMPLES:
sage: qf = qepcad_formula sage: var('a,b,c,d,x,y,z,long_with_underscore_314159') (a, b, c, d, x, y, z, long_with_underscore_314159) sage: K.<q,r> = QQ[] sage: qepcad('(E x)[a x + b > 0]', vars='(a,b,x)') # not tested (random order) a /= 0 \/ b > 0 sage: qepcad(a > b) # optional - qepcad b - a < 0 sage: qepcad(qf.exists(x, a*x^2 + b*x + c == 0)) # not tested (random order) 4 a c - b^2 <= 0 /\ [ c = 0 \/ a /= 0 \/ 4 a c - b^2 < 0 ] sage: qepcad(qf.exists(x, a*x^2 + b*x + c == 0), assume=(a != 0)) # optional - qepcad 4 a c - b^2 <= 0
>>> from sage.all import * >>> qf = qepcad_formula >>> var('a,b,c,d,x,y,z,long_with_underscore_314159') (a, b, c, d, x, y, z, long_with_underscore_314159) >>> K = QQ['q, r']; (q, r,) = K._first_ngens(2) >>> qepcad('(E x)[a x + b > 0]', vars='(a,b,x)') # not tested (random order) a /= 0 \/ b > 0 >>> qepcad(a > b) # optional - qepcad b - a < 0 >>> qepcad(qf.exists(x, a*x**Integer(2) + b*x + c == Integer(0))) # not tested (random order) 4 a c - b^2 <= 0 /\ [ c = 0 \/ a /= 0 \/ 4 a c - b^2 < 0 ] >>> qepcad(qf.exists(x, a*x**Integer(2) + b*x + c == Integer(0)), assume=(a != Integer(0))) # optional - qepcad 4 a c - b^2 <= 0
For which values of \(a\), \(b\), \(c\) does \(a x^2 + b x + c\) have 2 real zeroes?
sage: exact2 = qepcad(qf.exactly_k(2, x, a*x^2 + b*x + c == 0)); exact2 # not tested (random order) a /= 0 /\ 4 a c - b^2 < 0
>>> from sage.all import * >>> exact2 = qepcad(qf.exactly_k(Integer(2), x, a*x**Integer(2) + b*x + c == Integer(0))); exact2 # not tested (random order) a /= 0 /\ 4 a c - b^2 < 0
one real zero?
sage: exact1 = qepcad(qf.exactly_k(1, x, a*x^2 + b*x + c == 0)); exact1 # not tested (random order) [ a > 0 /\ 4 a c - b^2 = 0 ] \/ [ a < 0 /\ 4 a c - b^2 = 0 ] \/ [ a = 0 /\ 4 a c - b^2 < 0 ]
>>> from sage.all import * >>> exact1 = qepcad(qf.exactly_k(Integer(1), x, a*x**Integer(2) + b*x + c == Integer(0))); exact1 # not tested (random order) [ a > 0 /\ 4 a c - b^2 = 0 ] \/ [ a < 0 /\ 4 a c - b^2 = 0 ] \/ [ a = 0 /\ 4 a c - b^2 < 0 ]
No real zeroes?
sage: exact0 = qepcad(qf.forall(x, a*x^2 + b*x + c != 0)); exact0 # not tested (random order) 4 a c - b^2 >= 0 /\ c /= 0 /\ [ b = 0 \/ 4 a c - b^2 > 0 ]
>>> from sage.all import * >>> exact0 = qepcad(qf.forall(x, a*x**Integer(2) + b*x + c != Integer(0))); exact0 # not tested (random order) 4 a c - b^2 >= 0 /\ c /= 0 /\ [ b = 0 \/ 4 a c - b^2 > 0 ]
\(3^{75}\) real zeroes?
sage: qepcad(qf.exactly_k(3^75, x, a*x^2 + b*x + c == 0)) # optional - qepcad FALSE
>>> from sage.all import * >>> qepcad(qf.exactly_k(Integer(3)**Integer(75), x, a*x**Integer(2) + b*x + c == Integer(0))) # optional - qepcad FALSE
We can check that the results don’t overlap:
sage: qepcad(r'[[%s] /\ [%s]]' % (exact0, exact1), vars='a,b,c') # not tested (random order) FALSE sage: qepcad(r'[[%s] /\ [%s]]' % (exact0, exact2), vars='a,b,c') # not tested (random order) FALSE sage: qepcad(r'[[%s] /\ [%s]]' % (exact1, exact2), vars='a,b,c') # not tested (random order) FALSE
>>> from sage.all import * >>> qepcad(r'[[%s] /\ [%s]]' % (exact0, exact1), vars='a,b,c') # not tested (random order) FALSE >>> qepcad(r'[[%s] /\ [%s]]' % (exact0, exact2), vars='a,b,c') # not tested (random order) FALSE >>> qepcad(r'[[%s] /\ [%s]]' % (exact1, exact2), vars='a,b,c') # not tested (random order) FALSE
and that the union of the results is as expected:
sage: qepcad(r'[[%s] \/ [%s] \/ [%s]]' % (exact0, exact1, exact2), vars=(a,b,c)) # not tested (random order) b /= 0 \/ a /= 0 \/ c /= 0
>>> from sage.all import * >>> qepcad(r'[[%s] \/ [%s] \/ [%s]]' % (exact0, exact1, exact2), vars=(a,b,c)) # not tested (random order) b /= 0 \/ a /= 0 \/ c /= 0
So we have finitely many zeroes if \(a\), \(b\), or \(c\) is nonzero; which means we should have infinitely many zeroes if they are all zero.
sage: qepcad(qf.infinitely_many(x, a*x^2 + b*x + c == 0)) # not tested (random order) a = 0 /\ b = 0 /\ c = 0
>>> from sage.all import * >>> qepcad(qf.infinitely_many(x, a*x**Integer(2) + b*x + c == Integer(0))) # not tested (random order) a = 0 /\ b = 0 /\ c = 0
The polynomial is nonzero almost everywhere iff it is not identically zero.
sage: qepcad(qf.all_but_finitely_many(x, a*x^2 + b*x + c != 0)) # not tested (random order) b /= 0 \/ a /= 0 \/ c /= 0
>>> from sage.all import * >>> qepcad(qf.all_but_finitely_many(x, a*x**Integer(2) + b*x + c != Integer(0))) # not tested (random order) b /= 0 \/ a /= 0 \/ c /= 0
The non-zeroes are continuous iff there are no zeroes or if the polynomial is zero.
sage: qepcad(qf.connected_subset(x, a*x^2 + b*x + c != 0)) # not tested (random order) 4 a c - b^2 >= 0 /\ [ a = 0 \/ 4 a c - b^2 > 0 ]
>>> from sage.all import * >>> qepcad(qf.connected_subset(x, a*x**Integer(2) + b*x + c != Integer(0))) # not tested (random order) 4 a c - b^2 >= 0 /\ [ a = 0 \/ 4 a c - b^2 > 0 ]
The zeroes are continuous iff there are no or one zeroes, or if the polynomial is zero:
sage: qepcad(qf.connected_subset(x, a*x^2 + b*x + c == 0)) # not tested (random order) a = 0 \/ 4 a c - b^2 >= 0 sage: qepcad(r'[[%s] \/ [%s] \/ [a = 0 /\ b = 0 /\ c = 0]]' % (exact0, exact1), vars='a,b,c') # not tested (random order) a = 0 \/ 4 a c - b^2 >= 0
>>> from sage.all import * >>> qepcad(qf.connected_subset(x, a*x**Integer(2) + b*x + c == Integer(0))) # not tested (random order) a = 0 \/ 4 a c - b^2 >= 0 >>> qepcad(r'[[%s] \/ [%s] \/ [a = 0 /\ b = 0 /\ c = 0]]' % (exact0, exact1), vars='a,b,c') # not tested (random order) a = 0 \/ 4 a c - b^2 >= 0
Since polynomials are continuous and \(y > 0\) is an open set, they are positive infinitely often iff they are positive at least once.
sage: qepcad(qf.infinitely_many(x, a*x^2 + b*x + c > 0)) # not tested (random order) c > 0 \/ a > 0 \/ 4 a c - b^2 < 0 sage: qepcad(qf.exists(x, a*x^2 + b*x + c > 0)) # not tested (random order) c > 0 \/ a > 0 \/ 4 a c - b^2 < 0
>>> from sage.all import * >>> qepcad(qf.infinitely_many(x, a*x**Integer(2) + b*x + c > Integer(0))) # not tested (random order) c > 0 \/ a > 0 \/ 4 a c - b^2 < 0 >>> qepcad(qf.exists(x, a*x**Integer(2) + b*x + c > Integer(0))) # not tested (random order) c > 0 \/ a > 0 \/ 4 a c - b^2 < 0
However, since \(y >= 0\) is not open, the equivalence does not hold if you replace ‘positive’ with ‘nonnegative’. (We assume \(a \neq 0\) to get simpler formulas.)
sage: qepcad(qf.infinitely_many(x, a*x^2 + b*x + c >= 0), assume=(a != 0)) # not tested (random order) a > 0 \/ 4 a c - b^2 < 0 sage: qepcad(qf.exists(x, a*x^2 + b*x + c >= 0), assume=(a != 0)) # not tested (random order) a > 0 \/ 4 a c - b^2 <= 0
>>> from sage.all import * >>> qepcad(qf.infinitely_many(x, a*x**Integer(2) + b*x + c >= Integer(0)), assume=(a != Integer(0))) # not tested (random order) a > 0 \/ 4 a c - b^2 < 0 >>> qepcad(qf.exists(x, a*x**Integer(2) + b*x + c >= Integer(0)), assume=(a != Integer(0))) # not tested (random order) a > 0 \/ 4 a c - b^2 <= 0
- sage.interfaces.qepcad.qepcad_banner()[source]#
Return the QEPCAD startup banner.
EXAMPLES:
sage: from sage.interfaces.qepcad import qepcad_banner sage: qepcad_banner() # optional - qepcad ======================================================= Quantifier Elimination in Elementary Algebra and Geometry by Partial Cylindrical Algebraic Decomposition ... by Hoon Hong ([email protected]) With contributions by: Christopher W. Brown, George E. Collins, Mark J. Encarnacion, Jeremy R. Johnson Werner Krandick, Richard Liska, Scott McCallum, Nicolas Robidoux, and Stanly Steinberg =======================================================
>>> from sage.all import * >>> from sage.interfaces.qepcad import qepcad_banner >>> qepcad_banner() # optional - qepcad ======================================================= Quantifier Elimination in Elementary Algebra and Geometry by Partial Cylindrical Algebraic Decomposition ... by Hoon Hong ([email protected]) With contributions by: Christopher W. Brown, George E. Collins, Mark J. Encarnacion, Jeremy R. Johnson Werner Krandick, Richard Liska, Scott McCallum, Nicolas Robidoux, and Stanly Steinberg =======================================================
- sage.interfaces.qepcad.qepcad_console(memcells=None)[source]#
Run QEPCAD directly. To exit early, press Control + C.
EXAMPLES:
sage: qepcad_console() # not tested ... Enter an informal description between '[' and ']':
>>> from sage.all import * >>> qepcad_console() # not tested ... Enter an informal description between '[' and ']':
- class sage.interfaces.qepcad.qepcad_formula_factory[source]#
Bases:
object
Contains routines to help construct formulas in QEPCAD syntax.
- A(v, formula)[source]#
Given a variable (or list of variables) and a formula, returns the universal quantification of the formula over the variables.
This method is available both as
forall()
andA()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.forall(a, a^2 + b > b^2 + a) (A a)[a^2 + b > b^2 + a] sage: qf.forall((a, b), a^2 + b^2 > 0) (A a)(A b)[a^2 + b^2 > 0] sage: qf.A(b, b^2 != a) (A b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.forall(a, a**Integer(2) + b > b**Integer(2) + a) (A a)[a^2 + b > b^2 + a] >>> qf.forall((a, b), a**Integer(2) + b**Integer(2) > Integer(0)) (A a)(A b)[a^2 + b^2 > 0] >>> qf.A(b, b**Integer(2) != a) (A b)[b^2 /= a]
- C(v, formula, allow_multi=False)[source]#
Given a variable and a formula, returns a new formula which is true iff the set of values for the variable at which the original formula was true is connected (including cases where this set is empty or is a single point).
This method is available both as
connected_subset()
andC()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.connected_subset(a, a^2 + b > b^2 + a) (C a)[a^2 + b > b^2 + a] sage: qf.C(b, b^2 != a) (C b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.connected_subset(a, a**Integer(2) + b > b**Integer(2) + a) (C a)[a^2 + b > b^2 + a] >>> qf.C(b, b**Integer(2) != a) (C b)[b^2 /= a]
- E(v, formula)[source]#
Given a variable (or list of variables) and a formula, returns the existential quantification of the formula over the variables.
This method is available both as
exists()
andE()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.exists(a, a^2 + b > b^2 + a) (E a)[a^2 + b > b^2 + a] sage: qf.exists((a, b), a^2 + b^2 < 0) (E a)(E b)[a^2 + b^2 < 0] sage: qf.E(b, b^2 == a) (E b)[b^2 = a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.exists(a, a**Integer(2) + b > b**Integer(2) + a) (E a)[a^2 + b > b^2 + a] >>> qf.exists((a, b), a**Integer(2) + b**Integer(2) < Integer(0)) (E a)(E b)[a^2 + b^2 < 0] >>> qf.E(b, b**Integer(2) == a) (E b)[b^2 = a]
- F(v, formula)[source]#
Given a variable and a formula, returns a new formula which is true iff the original formula was true for infinitely many values of the variable.
This method is available both as
infinitely_many()
andF()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.infinitely_many(a, a^2 + b > b^2 + a) (F a)[a^2 + b > b^2 + a] sage: qf.F(b, b^2 != a) (F b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.infinitely_many(a, a**Integer(2) + b > b**Integer(2) + a) (F a)[a^2 + b > b^2 + a] >>> qf.F(b, b**Integer(2) != a) (F b)[b^2 /= a]
- G(v, formula)[source]#
Given a variable and a formula, returns a new formula which is true iff the original formula was true for all but finitely many values of the variable.
This method is available both as
all_but_finitely_many()
andG()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.all_but_finitely_many(a, a^2 + b > b^2 + a) (G a)[a^2 + b > b^2 + a] sage: qf.G(b, b^2 != a) (G b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.all_but_finitely_many(a, a**Integer(2) + b > b**Integer(2) + a) (G a)[a^2 + b > b^2 + a] >>> qf.G(b, b**Integer(2) != a) (G b)[b^2 /= a]
- X(k, v, formula, allow_multi=False)[source]#
Given a nonnegative integer \(k\), a variable, and a formula, returns a new formula which is true iff the original formula is true for exactly \(k\) values of the variable.
This method is available both as
exactly_k()
andX()
(the QEPCAD name for this quantifier).(Note that QEPCAD does not support \(k=0\) with this syntax, so if \(k=0\) is requested we implement it with
forall()
andnot_()
.)The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.exactly_k(1, x, x^2 + a*x + b == 0) (X1 x)[a x + x^2 + b = 0] sage: qf.exactly_k(0, b, a*b == 1) (A b)[~a b = 1]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.exactly_k(Integer(1), x, x**Integer(2) + a*x + b == Integer(0)) (X1 x)[a x + x^2 + b = 0] >>> qf.exactly_k(Integer(0), b, a*b == Integer(1)) (A b)[~a b = 1]
- all_but_finitely_many(v, formula)[source]#
Given a variable and a formula, returns a new formula which is true iff the original formula was true for all but finitely many values of the variable.
This method is available both as
all_but_finitely_many()
andG()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.all_but_finitely_many(a, a^2 + b > b^2 + a) (G a)[a^2 + b > b^2 + a] sage: qf.G(b, b^2 != a) (G b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.all_but_finitely_many(a, a**Integer(2) + b > b**Integer(2) + a) (G a)[a^2 + b > b^2 + a] >>> qf.G(b, b**Integer(2) != a) (G b)[b^2 /= a]
- and_(*formulas)[source]#
Return the conjunction of its input formulas.
(This method would be named ‘and’ if that were not a Python keyword.)
Each input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b,c,x') (a, b, c, x) sage: qf = qepcad_formula sage: qf.and_(a*b, a*c, b*c != 0) [a b = 0 /\ a c = 0 /\ b c /= 0] sage: qf.and_(a*x^2 == 3, qf.or_(a > b, b > c)) [a x^2 = 3 /\ [a > b \/ b > c]]
>>> from sage.all import * >>> var('a,b,c,x') (a, b, c, x) >>> qf = qepcad_formula >>> qf.and_(a*b, a*c, b*c != Integer(0)) [a b = 0 /\ a c = 0 /\ b c /= 0] >>> qf.and_(a*x**Integer(2) == Integer(3), qf.or_(a > b, b > c)) [a x^2 = 3 /\ [a > b \/ b > c]]
- atomic(lhs, op='=', rhs=0)[source]#
Construct a QEPCAD formula from the given inputs.
INPUT:
lhs
– a polynomial, or a symbolic equality or inequalityop
– a relational operator, default ‘=’rhs
– a polynomial, default 0
If
lhs
is a symbolic equality or inequality, thenop
andrhs
are ignored.This method works by printing the given polynomials, so we do not care what ring they are in (as long as they print with integral or rational coefficients).
EXAMPLES:
sage: qf = qepcad_formula sage: var('a,b,c') (a, b, c) sage: K.<x,y> = QQ[] sage: def test_qf(qf): ....: return qf, qf.vars sage: test_qf(qf.atomic(a^2 + 17)) (a^2 + 17 = 0, frozenset({'a'})) sage: test_qf(qf.atomic(a*b*c <= c^3)) (a b c <= c^3, frozenset({'a', 'b', 'c'})) sage: test_qf(qf.atomic(x+y^2, '!=', a+b)) (y^2 + x /= a + b, frozenset({'a', 'b', 'x', 'y'})) sage: test_qf(qf.atomic(x, operator.lt)) (x < 0, frozenset({'x'}))
>>> from sage.all import * >>> qf = qepcad_formula >>> var('a,b,c') (a, b, c) >>> K = QQ['x, y']; (x, y,) = K._first_ngens(2) >>> def test_qf(qf): ... return qf, qf.vars >>> test_qf(qf.atomic(a**Integer(2) + Integer(17))) (a^2 + 17 = 0, frozenset({'a'})) >>> test_qf(qf.atomic(a*b*c <= c**Integer(3))) (a b c <= c^3, frozenset({'a', 'b', 'c'})) >>> test_qf(qf.atomic(x+y**Integer(2), '!=', a+b)) (y^2 + x /= a + b, frozenset({'a', 'b', 'x', 'y'})) >>> test_qf(qf.atomic(x, operator.lt)) (x < 0, frozenset({'x'}))
- connected_subset(v, formula, allow_multi=False)[source]#
Given a variable and a formula, returns a new formula which is true iff the set of values for the variable at which the original formula was true is connected (including cases where this set is empty or is a single point).
This method is available both as
connected_subset()
andC()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.connected_subset(a, a^2 + b > b^2 + a) (C a)[a^2 + b > b^2 + a] sage: qf.C(b, b^2 != a) (C b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.connected_subset(a, a**Integer(2) + b > b**Integer(2) + a) (C a)[a^2 + b > b^2 + a] >>> qf.C(b, b**Integer(2) != a) (C b)[b^2 /= a]
- exactly_k(k, v, formula, allow_multi=False)[source]#
Given a nonnegative integer \(k\), a variable, and a formula, returns a new formula which is true iff the original formula is true for exactly \(k\) values of the variable.
This method is available both as
exactly_k()
andX()
(the QEPCAD name for this quantifier).(Note that QEPCAD does not support \(k=0\) with this syntax, so if \(k=0\) is requested we implement it with
forall()
andnot_()
.)The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.exactly_k(1, x, x^2 + a*x + b == 0) (X1 x)[a x + x^2 + b = 0] sage: qf.exactly_k(0, b, a*b == 1) (A b)[~a b = 1]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.exactly_k(Integer(1), x, x**Integer(2) + a*x + b == Integer(0)) (X1 x)[a x + x^2 + b = 0] >>> qf.exactly_k(Integer(0), b, a*b == Integer(1)) (A b)[~a b = 1]
- exists(v, formula)[source]#
Given a variable (or list of variables) and a formula, returns the existential quantification of the formula over the variables.
This method is available both as
exists()
andE()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.exists(a, a^2 + b > b^2 + a) (E a)[a^2 + b > b^2 + a] sage: qf.exists((a, b), a^2 + b^2 < 0) (E a)(E b)[a^2 + b^2 < 0] sage: qf.E(b, b^2 == a) (E b)[b^2 = a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.exists(a, a**Integer(2) + b > b**Integer(2) + a) (E a)[a^2 + b > b^2 + a] >>> qf.exists((a, b), a**Integer(2) + b**Integer(2) < Integer(0)) (E a)(E b)[a^2 + b^2 < 0] >>> qf.E(b, b**Integer(2) == a) (E b)[b^2 = a]
- forall(v, formula)[source]#
Given a variable (or list of variables) and a formula, returns the universal quantification of the formula over the variables.
This method is available both as
forall()
andA()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.forall(a, a^2 + b > b^2 + a) (A a)[a^2 + b > b^2 + a] sage: qf.forall((a, b), a^2 + b^2 > 0) (A a)(A b)[a^2 + b^2 > 0] sage: qf.A(b, b^2 != a) (A b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.forall(a, a**Integer(2) + b > b**Integer(2) + a) (A a)[a^2 + b > b^2 + a] >>> qf.forall((a, b), a**Integer(2) + b**Integer(2) > Integer(0)) (A a)(A b)[a^2 + b^2 > 0] >>> qf.A(b, b**Integer(2) != a) (A b)[b^2 /= a]
- formula(formula)[source]#
Constructs a QEPCAD formula from the given input.
INPUT:
formula
– a polynomial, a symbolic equality or inequality, or a list of polynomials, equalities, or inequalities
A polynomial \(p\) is interpreted as the equation \(p = 0\). A list is interpreted as the conjunction (‘and’) of the elements.
EXAMPLES:
sage: var('a,b,c,x') (a, b, c, x) sage: qf = qepcad_formula sage: qf.formula(a*x + b) a x + b = 0 sage: qf.formula((a*x^2 + b*x + c, a != 0)) [a x^2 + b x + c = 0 /\ a /= 0]
>>> from sage.all import * >>> var('a,b,c,x') (a, b, c, x) >>> qf = qepcad_formula >>> qf.formula(a*x + b) a x + b = 0 >>> qf.formula((a*x**Integer(2) + b*x + c, a != Integer(0))) [a x^2 + b x + c = 0 /\ a /= 0]
- iff(f1, f2)[source]#
Return the equivalence of its input formulas (that is, given formulas \(P\) and \(Q\), returns ‘\(P\) iff \(Q\)’).
The input formulas may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.iff(a, b) [a = 0 <==> b = 0] sage: qf.iff(a^2 < b, b^2 < a) [a^2 < b <==> b^2 < a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.iff(a, b) [a = 0 <==> b = 0] >>> qf.iff(a**Integer(2) < b, b**Integer(2) < a) [a^2 < b <==> b^2 < a]
- implies(f1, f2)[source]#
Return the implication of its input formulas (that is, given formulas \(P\) and \(Q\), returns ‘\(P\) implies \(Q\)’).
The input formulas may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.implies(a, b) [a = 0 ==> b = 0] sage: qf.implies(a^2 < b, b^2 < a) [a^2 < b ==> b^2 < a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.implies(a, b) [a = 0 ==> b = 0] >>> qf.implies(a**Integer(2) < b, b**Integer(2) < a) [a^2 < b ==> b^2 < a]
- infinitely_many(v, formula)[source]#
Given a variable and a formula, returns a new formula which is true iff the original formula was true for infinitely many values of the variable.
This method is available both as
infinitely_many()
andF()
(the QEPCAD name for this quantifier).The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.infinitely_many(a, a^2 + b > b^2 + a) (F a)[a^2 + b > b^2 + a] sage: qf.F(b, b^2 != a) (F b)[b^2 /= a]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.infinitely_many(a, a**Integer(2) + b > b**Integer(2) + a) (F a)[a^2 + b > b^2 + a] >>> qf.F(b, b**Integer(2) != a) (F b)[b^2 /= a]
- not_(formula)[source]#
Return the negation of its input formula.
(This method would be named ‘not’ if that were not a Python keyword.)
The input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.not_(a > b) [~a > b] sage: qf.not_(a^2 + b^2) [~a^2 + b^2 = 0] sage: qf.not_(qf.and_(a > 0, b < 0)) [~[a > 0 /\ b < 0]]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.not_(a > b) [~a > b] >>> qf.not_(a**Integer(2) + b**Integer(2)) [~a^2 + b^2 = 0] >>> qf.not_(qf.and_(a > Integer(0), b < Integer(0))) [~[a > 0 /\ b < 0]]
- or_(*formulas)[source]#
Return the disjunction of its input formulas.
(This method would be named ‘or’ if that were not a Python keyword.)
Each input formula may be a
qformula
as returned by the methods ofqepcad_formula
, a symbolic equality or inequality, or a polynomial \(p\) (meaning \(p = 0\)).EXAMPLES:
sage: var('a,b,c,x') (a, b, c, x) sage: qf = qepcad_formula sage: qf.or_(a*b, a*c, b*c != 0) [a b = 0 \/ a c = 0 \/ b c /= 0] sage: qf.or_(a*x^2 == 3, qf.and_(a > b, b > c)) [a x^2 = 3 \/ [a > b /\ b > c]]
>>> from sage.all import * >>> var('a,b,c,x') (a, b, c, x) >>> qf = qepcad_formula >>> qf.or_(a*b, a*c, b*c != Integer(0)) [a b = 0 \/ a c = 0 \/ b c /= 0] >>> qf.or_(a*x**Integer(2) == Integer(3), qf.and_(a > b, b > c)) [a x^2 = 3 \/ [a > b /\ b > c]]
- quantifier(kind, v, formula, allow_multi=True)[source]#
A helper method for building quantified QEPCAD formulas; not expected to be called directly.
Takes the quantifier kind (the string label of this quantifier), a variable or list of variables, and a formula, and returns the quantified formula.
EXAMPLES:
sage: var('a,b') (a, b) sage: qf = qepcad_formula sage: qf.quantifier('NOT_A_REAL_QEPCAD_QUANTIFIER', a, a*b==0) (NOT_A_REAL_QEPCAD_QUANTIFIER a)[a b = 0] sage: qf.quantifier('FOO', (a, b), a*b) (FOO a)(FOO b)[a b = 0]
>>> from sage.all import * >>> var('a,b') (a, b) >>> qf = qepcad_formula >>> qf.quantifier('NOT_A_REAL_QEPCAD_QUANTIFIER', a, a*b==Integer(0)) (NOT_A_REAL_QEPCAD_QUANTIFIER a)[a b = 0] >>> qf.quantifier('FOO', (a, b), a*b) (FOO a)(FOO b)[a b = 0]
- sage.interfaces.qepcad.qepcad_version()[source]#
Return a string containing the current QEPCAD version number.
EXAMPLES:
sage: qepcad_version() # random, optional - qepcad 'Version B 1.69, 16 Mar 2012'
>>> from sage.all import * >>> qepcad_version() # random, optional - qepcad 'Version B 1.69, 16 Mar 2012'