7
$\begingroup$

Given a system of complex polynomial equations, we seek the solution set. If we have more equations than variables, then we might expect a finite solution set. One may obtain the solution set by computing a Groebner basis, but this is slow in practice. Alternatively, one may leverage ideas from numerical algebraic geometry to obtain numerical solutions. Depending on the system, one might then apply LLL-type algorithms to promote these numerical solutions to exact solutions. But can you tell whether you have the full solution set?

Question: Given finite $F\subseteq\mathbb{C}[X_1,\ldots,X_n]$ and a finite set $S\subseteq\mathbb{C}^n$ of common zeros of $F$, is there an efficient way to certify whether $S$ contains every common zero of $F$?

The case of a single monic polynomial in one variable is straightforward: Take derivatives to deduce the multiplicity of each root, and then multiply binomial factors to obtain the original polynomial. This certifies completeness of the solution set.

When there are more variables, things are less obvious. In some cases, Bezout's theorem gives the size of the solution set (counted with multiplicity) provided the solution set is finite. Presumably, one may use calculus to determine the multiplicity of a given solution, but it's unclear how to rule out an infinite solution set.

To be clear, I am only interested in computational approaches that are (much) faster than Groebner basis calculation, at least in practice.

Edit: As François Brunault correctly points out, this computation is only feasible for instances in which the polynomials $F$ and common zeros $S$ can be represented in a computer. I am primarily interested in cases where the coefficients of the polynomials in $F$ are all rational and the entries of the members of $S$ are all algebraic. Presumably, techniques used in these cases can be extended to other computer-friendly cases.

$\endgroup$
4
  • $\begingroup$ A remark: it is not possible to encode a complex number on a computer. So any algorithm will just be numerical and it will be impossible to ascertain that the output is mathematically correct. You need a field where you can do exact computations, like $\mathbb{Q}$ or maybe $\overline{\mathbb{Q}}$. $\endgroup$ Mar 28, 2021 at 16:48
  • $\begingroup$ To be positive, here is an algorithm to find the intersection points of two plane curves: arxiv.org/abs/0907.0361 As said, you need a field where you can do exact operations, which enables you to use the Euclidean algorithm. At the end (section 3.3), you will have the exact number of intersection points. $\endgroup$ Mar 28, 2021 at 16:54
  • $\begingroup$ Not for the main question, but maybe relevant for computations of roots: arxiv.org/abs/1011.1091 $\endgroup$ Mar 29, 2021 at 19:55
  • $\begingroup$ You mentioned the Bezout bound for the number of solutions. There are other bounds, e.g., in terms of mixed volume, which can be sharp at least sometimes. (Also you can eliminate a variable by using resultants instead of Gröbner bases, but I would think that’s unlikely to be any faster than Gröbner bases.) (One more dumb idea: use linear algebra to compute the dimension of a high degree piece of the ideal, its codimension is the number of solutions. But how high a degree? Bounds from effective nullstellensatz are probably terrible.) $\endgroup$ Apr 7, 2021 at 1:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.