2
$\begingroup$

I'm looking for an algorithm to solve a system of $n$ positive integer polynomial equations, assuming that there exists one and only one solution to the system.

Could anyone point me in the right direction or literature?

Example: Assume that the number of variables is $n$, usually we expect $10 \le n \le 50$. Assume that $n=5$ for the example. We need to solve: $$ x_1 = 5 $$ $$ x_1^2 x_2 x_3 = 100 $$ $$ x_2^2 x_3 + x_1 + x_4^2 = 62$$ $$ x_5 x_4 + 2 x_5 = 9 $$ $$ x_1 + x_5 x_2 + x_3 x_4 = 21 $$ $$ x_1 + x_2 + x_3 + x_4 + x_5 = 17 $$ Solution: From $x_1 = 5$ we get that $x_2 x_3 = 4$, thus $(x_2,x_3)=(1,4),(2,2),(4,1)$. From the third equation $x_5(x_4 + 2) = 9$, thus $(x_4, x_5) = (1, 3), (7, 1)$. From the last equation we have that $x_2 + x_3 + x_4 + x_5 = 12$, since the sum of $x_2 + x_3 = 4, 5$ and $x_4 + x_5 = 4, 8$, it means only option is $x_4 = 7, x_5 = 1, x_2 = 2, x_3 = 2$.

Note that I need an algorithm to do this , such that it is automated.

$\endgroup$
  • 2
    $\begingroup$ If you do not show the system of equations - how to solve it? $\endgroup$ – individ Aug 26 '16 at 16:05
  • 1
    $\begingroup$ I'm looking for a general algorithm to solve any such system. I don't have any concrete system, I can make one up, but the goal is to have a general algorithm for solving it (e.g. like for instance the Greatest Common Divider algorithm, or Gaussian Elimination) $\endgroup$ – Alex Botev Aug 26 '16 at 16:18
  • 1
    $\begingroup$ For systems of linear equations - standard method of Gauss. For quadratic and slightly higher extent have to wait until about it will tell. While about it to speak. Some systems can be found there. artofproblemsolving.com/community/… It is better to write the system - could work to solve it. $\endgroup$ – individ Aug 26 '16 at 16:32
  • $\begingroup$ What degrees? How many variables? You should consider posting a minimal example for a small $n$ at least. $\endgroup$ – dxiv Aug 26 '16 at 16:47
  • 2
    $\begingroup$ In general, deciding whether a solution to a system of polynomial equations exists is undecidable (this was Hilbert's tenth problem). This implies that any algorithm giving a solution to a system of equations guaranteed to have a root has time complexity growing faster than any computable function. I'd suspect the situation is no better for systems with a unique solution, but I can't tell. $\endgroup$ – Milo Brandt Aug 26 '16 at 21:12
3
$\begingroup$

If (and it's a big if) some variable has degree $1$ in one of the polynomials, you can substitute for that variable, obtaining a smaller set of equations in fewer variables, but in general with higher degrees.

Somewhat more generally, you can take a Groebner basis of your system of polynomials. In the example, I took a grevlex basis (using Maple's Groebner package) and obtained $[1]$, indicating that the system is inconsistent. With $20$ replaced by $21$ in the fifth equation, the grevlex basis was $ [-1+x_5, x_4-7, -2+x_3, -2+x_2, x_1-5]$, from which you can read off the solution.

Somewhat more generally, especially in the zero-dimensional case a pure lexicographic basis may work: the first element will typically be a polynomial with integer coefficients in the last variable in the lexicographic order. If there are integer solutions, factoring it will find them. Then substitute those integer solutions into the rest of the basis elements, and solve for the next variable.

Caution: Groebner bases for fairly small systems can get very big. The worst case complexity is terrible.

$\endgroup$
  • $\begingroup$ Thanks for the corrections. $\endgroup$ – Alex Botev Aug 27 '16 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.