ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 01 Dec 2015 05:16:28 -0600Reformulation of a semialgebraic set, without quantifiershttps://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/According to wikipedia:
> The [Tarski–Seidenberg](https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem) theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities.
That's great, and my question is if it can be done in practice, in a particular case. I have read that the original Tarski–Seidenberg algorithm is of little practical use, but maybe my problem is tractable with another algorithm:
We have a finite set of points in C^2 (z_i,w_i), and I want to project onto the first C coordinate the intersection of the cones {(z,w): |z-z_i|>|w-w_i|}. It would be awesome, for example for plotting the set, if I could actually get the polynomial inequalities that define the projection. Getting only the higher dimensional strata is fine (an open set in C).
Any idea? Thanks in advance.Tue, 27 Oct 2015 04:26:42 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/Comment by pang for <p>According to wikipedia:</p>
<blockquote>
<p>The <a href="https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem">Tarski–Seidenberg</a> theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities.</p>
</blockquote>
<p>That's great, and my question is if it can be done in practice, in a particular case. I have read that the original Tarski–Seidenberg algorithm is of little practical use, but maybe my problem is tractable with another algorithm:</p>
<p>We have a finite set of points in C^2 (z_i,w_i), and I want to project onto the first C coordinate the intersection of the cones {(z,w): |z-z_i|>|w-w_i|}. It would be awesome, for example for plotting the set, if I could actually get the polynomial inequalities that define the projection. Getting only the higher dimensional strata is fine (an open set in C).</p>
<p>Any idea? Thanks in advance.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30311#post-id-30311For the record: I couldn't get qepcad to make a projection of codimension 2 using even 4 points, but I did get some significant results by restricting to a three dimensional space, so that qepcad only projects along lines.Wed, 28 Oct 2015 06:27:21 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30311#post-id-30311Answer by tmonteil for <p>According to wikipedia:</p>
<blockquote>
<p>The <a href="https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem">Tarski–Seidenberg</a> theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities.</p>
</blockquote>
<p>That's great, and my question is if it can be done in practice, in a particular case. I have read that the original Tarski–Seidenberg algorithm is of little practical use, but maybe my problem is tractable with another algorithm:</p>
<p>We have a finite set of points in C^2 (z_i,w_i), and I want to project onto the first C coordinate the intersection of the cones {(z,w): |z-z_i|>|w-w_i|}. It would be awesome, for example for plotting the set, if I could actually get the polynomial inequalities that define the projection. Getting only the higher dimensional strata is fine (an open set in C).</p>
<p>Any idea? Thanks in advance.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?answer=30292#post-id-30292You should install and use `qepcad`. It has been updated recenty, so it should work, just install the latest version of Sage and run `sage -i qepcad`, see [this page](http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html) for more information.
Tue, 27 Oct 2015 07:20:23 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?answer=30292#post-id-30292Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=31238#post-id-31238I had problems installing sage from source, but I finally did it, and qepcap installed without problems. Thanks again, Thierry!Tue, 01 Dec 2015 05:16:28 -0600https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=31238#post-id-31238Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30295#post-id-30295I downloaded the program and I'm calling it from the command line. I can't get it to work on any non-trivial example (it does work with all the examples from its documentation). The output is:
Failure occurred in: GCSI (final check)
Reason for the failure: Too few cells reclaimed.Tue, 27 Oct 2015 10:19:49 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30295#post-id-30295Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30296#post-id-30296It just finished installing. Thanks for taking care of this packege, Thierry!Tue, 27 Oct 2015 10:31:11 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30296#post-id-30296Comment by tmonteil for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30297#post-id-30297Great. Please do not hesitate to tell if there is some issue with this package.Tue, 27 Oct 2015 10:38:56 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30297#post-id-30297Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30305#post-id-30305I get a "RuntimeError: unable to start QEPCAD". I upgraded to sage 6.9 with
./sage -upgrade
and I installed qepcad with
./sage -i qepcad
The first upgrade reported errors when building the html docs, but nothing else, and everything seems to work fine. The installation of qepcad produced no errors (I think), and there are qepcad and saclib folders in sage/pkgs.Wed, 28 Oct 2015 04:26:30 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30305#post-id-30305Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30306#post-id-30306I have bug traces etc: should I open a ticket?Wed, 28 Oct 2015 04:36:28 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30306#post-id-30306Comment by tmonteil for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30313#post-id-30313If you found a bug, you should fill a ticket. Or you can report the problem here if you do not want to ask for a trac account.Wed, 28 Oct 2015 08:11:09 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30313#post-id-30313Comment by tmonteil for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30314#post-id-30314Did you try to reinstall Sage from scratch ? What was your previous Sage version ?Wed, 28 Oct 2015 08:12:02 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30314#post-id-30314Comment by pang for <p>You should install and use <code>qepcad</code>. It has been updated recenty, so it should work, just install the latest version of Sage and run <code>sage -i qepcad</code>, see <a href="http://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/qepcad.html">this page</a> for more information.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30318#post-id-30318I do have a trac account. I'll try first with a fresh sage install. My current sage install is old, and has been updated several times. I'll need a few days: if it works I'll comment here, and if it doesn't I'll fill a bug. Regards!Wed, 28 Oct 2015 09:33:01 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?comment=30318#post-id-30318Answer by pang for <p>According to wikipedia:</p>
<blockquote>
<p>The <a href="https://en.wikipedia.org/wiki/Tarski%E2%80%93Seidenberg_theorem">Tarski–Seidenberg</a> theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities.</p>
</blockquote>
<p>That's great, and my question is if it can be done in practice, in a particular case. I have read that the original Tarski–Seidenberg algorithm is of little practical use, but maybe my problem is tractable with another algorithm:</p>
<p>We have a finite set of points in C^2 (z_i,w_i), and I want to project onto the first C coordinate the intersection of the cones {(z,w): |z-z_i|>|w-w_i|}. It would be awesome, for example for plotting the set, if I could actually get the polynomial inequalities that define the projection. Getting only the higher dimensional strata is fine (an open set in C).</p>
<p>Any idea? Thanks in advance.</p>
https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?answer=30288#post-id-30288I found the optional package qepcad:
http://flask.sagenb.org/src/interfaces/qepcad.py
mentioned in this site:
http://mathoverflow.net/questions/159901/real-algebraic-geometry-softwareTue, 27 Oct 2015 04:30:09 -0500https://ask.sagemath.org/question/30287/reformulation-of-a-semialgebraic-set-without-quantifiers/?answer=30288#post-id-30288