# Solving over-determined system of polynomials

I am trying to solve the following over determined system of polynomials

\begin{align} & p_1(x_1,x_2,\ldots,x_n)=0, \\ & p_2(x_1,x_2,\ldots,x_n)=0, \\ & \vdots \\ & p_m(x_1,x_2, \ldots, x_n)=0, \\ & (x_1-l_1) (x_1-(l_1+1)) (x_1 - (l_1 + 2))\cdots (x_1-(u_1-1))(x_1-u_1)=0, \\ & \vdots \\ & (x_n-l_n) (x_n-(l_n+1)) (x_n - (l_n + 2))\cdots (x_n-(u_n-1))(x_n-u_n)=0 \cdots (x_n-u_n)=0. \end{align}

Here $l_1,u_1, \ldots, l_n, u_n$ are non-negative integers. The last $n$ equations mean that $x_i \in \{l_i, l_i +1, l_i+2, \ldots, u_i-1, u_i\}$ for all $i \in \{1,\ldots, n\}$. I know that we can use Groebner bases to solve the polynomial system.

But is there a better way to solve such over-determined polynomial system? I will appreciate any suggestion or direction.

• How large is $n$ typically in your problem? – Moritz Firsching Aug 5 '15 at 5:46
• In my problem $n$ is the difference between the number of edges and nodes of a directed graph. For now I am taking $n \leq 50$. – SDG Aug 5 '15 at 12:55
• Check out the edit to my answer. – Igor Rivin Aug 5 '15 at 13:45
• Thanks a lot for your answer, I will check it. It seems that constraint programming too might be a good alternative. – SDG Aug 5 '15 at 14:08

I am not sure I understand what the ellipsis $\dots$ means in the last set of equations, since it seems that you only have pairs $l_i, u_i.$ If that is true, that means that there are $2^n$ possible values for the $n$-tuple $x_1, \dotsc, x_n,$ and substituting each possible $n$-tuple into your first $n$ equations, and checking will take time roughly $O(n 2^n)$ (with small constants), which will be WAY faster than Grobner bases in practice.
EDIT The OP explains in the comment that his notation means that $x_k$ is an integer at most equal to $u_k$ and at least equal to $l_k.$ If that is the case, and $u_i - l_1 \gg 1,$ so that brute force search is prohibitively expensive, the best approach is almost certainly back-tracking search. In fact, the form of the problem is not unlike that of the $N$-queens problem (which google).
• Thanks a lot for your response. Actually it means $x_i \in \{l_i,l_i+1,l_i+2,\ldots,u_i-1,u_i\}$, with $l_i, u_i$ being non-negative integers. – SDG Aug 5 '15 at 13:04