When I have two equations f=0 and g=0 over the reals, I can equivalently rewrite them as one equation f2+g2=0. Are there any alternative such encodings known? I am specifically interested in (multivariate) polynomial equations.
Are there any interesting options when more generally not considering equivalence but only equi-satisfiability?
Thomas, can you please specify your problem (or its background) via some example? Alexei
As an example you can take any polynomials for f and g, like:
- f := x³ - 6⋅x² + 11⋅x - 6
- g := x² - 6⋅x + 8
- h := f2+ g2 = x⁶ - 12⋅x⁵ + 59⋅x⁴ - 156⋅x³ + 245⋅x² - 228⋅x + 100.
h has exactly one real zero at x=2, and this is exactly the (only) common real zero of f and g. This is all known for at least a hundred years.
The first question is: Has anybody ever considered alternatives to sums of squares in that context?
As for the second question: In some applications one is primarily interested in solvability but not so much in the solutions. Then it would be sufficient to construct some h that has any solution if and only if f and g have any common solution. This should be easier, but still, I am not aware of any alternatives to sums of squares.
I see. I'd like to mention just only one obstacle in this approach - in the univariate case. How will you discover that the polynomial $ h $ possesses a REAL zero? In fact, x=2 is its multiple zero of an even order - and so: no alternatives of signes in its vicinity, no Newton-like methods... In the example, you've presented it's obvious, but it might be not always the case.
>As for the second question: In some applications one is primarily interested in >solvability but not so much in the solutions
I got it. I'm interested also in this problem - for the multivariate case. Can you please drop me a mail at
Thomas, for univariate polynomials as in your example the trivial answer is gcd(f,g) which in this case is equivalent to computing the reduced Gröbner basis. I doubt that for the multivariate case (which is what you are really interested in) a simpler answer than f2+g2 exists for the simple reason that the complex number are a field extension of degree 2 over the reals. Of course, one could start computing a reduced Gröbner basis for the ideal generated by f and g, but I do not see that generally you will find a single polynomial expressing the solvability of f and g. Furthermore, this is of course a rather expensive approach...
Regards Werner
If you are interested in calculations, see the answer by Werner. If you are interested in theory, and not only in polynomials,then instead of the sum of squares you can take sum of fourth powers, and many similar expressions.
- Badges
- Science topic
- Similar topics
- Biological Science
- Bioecology
- Systems Ecology
- Landscape Ecology
- Connectivity