Message Boards Message Boards

0
|
363 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Proof of correctness for FindInstace

I am interested in solving a (complex, non-zero dimensional) polynomial system.
It seems that in this case FindInstance is guaranteed to return a solution if it exists.
The algorithm for this case is described in the tutorial ("Complex Polynomial Systems") with a sketch of a proof that I did not completely followed.

Is there a reference for a paper or a book that describes this algorithm and prove its correctness?

POSTED BY: Dan Feldman
4 Replies

I don’t know offhand which bit of documentation from that tutorial you have in mind. I do think it will be covered quite well by the Springer UTM text “Ideals, Varieties and Algorithms: an Introduction to Computational Commutative Algebra and Algebraic Geometry” by David Cox, John Little and Donal O’Shea.

POSTED BY: Daniel Lichtblau

Thank you so much for the quick reply, Daniel. I am well familiar with this book and others of Cox et al. However, from the text, the algorithm and proof seem novel and I could not find them anywhere.

I am referring to the algorithm for computing "FindInstance" in Section "Arbitrary Complex Polynomial System" in Page 16 of "Wolfram Mathematica Tutorial Collection Advanced Algebra" here: https://library.wolfram.com/infocenter/Books/8502/AdvancedAlgebra.pdf

POSTED BY: Dan Feldman

I'll try to outline the argument though this might be more confusing than the original. Also I will confess that I do not follow every detail, or at least do not know the motivation behind the overall approach.

First note that for a system of polynomials over the complexes 9or rationals), it has empty solution set iff the reduced minimal Groebner basis is {1}. Your case does not have that issue. Also I gather there is no unequation to be satisfied in your example, so you can (mostly) ignore the use of a polynomial g in that tutorial.

The idea is to find a maximal independent set of variables and treat them as parameters. A reference for this part would be Thomas Becker and Volker Weispfenning (with Heinz Kredel). Gr"obner Basis: A Computational Approach to Commutative Algebra. It's in chapter 9 section 3 in the first edition, with the algorithm based on a total degree term order presented on p. 449.

One can then derive solutions by giving those parameters different values. A lexicographic Groebner basis, with the parameters ordered last, allows to solve for the dependent variables once the parameters are given values.

I do not know offhand why it is necessary to recast leading coefficients of lowest-degree polynomials in each successive polynomial as being independent of lesser dependent variables. Possibly this is a convenience to reduce the number of random attempts, since in a bad case lead coefficients might vanish. But the idea now is to make the ideal smaller, but in a "nice" way that does not change its dimension or set of parameters, and in a way that forces these leading coefficients to be strictly in terms of parameters. That's where these H ideals arise. A tricky part is to prove that these ideals do not mess up the independence of the parameters. The idea behind that proof is to show that if a dependency emerged when expanding the ideal by such a leading coefficient, then there would have been a different polynomial with the same lead variable but smaller in the term ordering, contradicting how that polynomial was chosen.

When the process is done, all minimal-degree polynomials with lead variable x_i will have coefficients only in terms of the parameter variables (the independent set). Now one need only take values for the parameters for which no such lead coefficient vanishes. This is sufficient to guarantee that each dependent variable can be solved for, and the solution percolates up variable by variable, so to say.

This solvability is guaranteed, in essence, by an old result known as the Gianni-Kalkbrenner specialization theorem, because each presented it independently at the same conference and published in the Proceedings of the European Conference on Computer Algebra (EuroCal) 1987.

Patrizia Gianni, Properties of Gr¨obner bases under specialization, Lect. N. Comp. Sci. Berlin, Heidelberg, New York: Springer 378 (1987), 293–297. MR1033305 (91g:13032)

Michael Kalkbrenner, Solving systems of algebraic equations using Gr¨obner bases, Lect. N. Comp. Sci. Berlin, Heidelberg, New York: Springer 378 (1987), 282–292.

I hope this helps a bit.

POSTED BY: Daniel Lichtblau

That you for the detailed answer! I will try to turn it into a formal proof. It also surprises me that such a nice algorithm for a fundamental problem does not appear in the academic literature with a full proof.

POSTED BY: Dan Feldman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract