Resolución de sistemas de polinomios sobredeterminados

Question

Intento resolver el siguiente sistema sobredeterminado de polinomios

\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}

Aquí $l_1,u_1, \ldots, l_n, u_n$ son enteros no negativos. El último $n$ significan que $x_i \in \{l_i, l_i +1, l_i+2, \ldots, u_i-1, u_i\}$ para todos $i \in \{1,\ldots, n\}$ . Sé que podemos utilizar las bases de Groebner para resolver el sistema polinómico.

Pero, ¿hay alguna forma mejor de resolver un sistema polinómico tan sobredeterminado? Agradeceré cualquier sugerencia o indicación.

Answer 1

No estoy seguro de entender lo que la elipsis $\dots$ significa en el último conjunto de ecuaciones, ya que parece que sólo tiene pares $l_i, u_i.$ Si eso es cierto, significa que hay $2^n$ valores posibles para el $n$ -tupla $x_1, \dotsc, x_n,$ y sustituyendo cada posible $n$ -en su primera $n$ ecuaciones, y la comprobación llevará tiempo aproximadamente $O(n 2^n)$ (con constantes pequeñas), que será MUCHO más rápido que las bases de Grobner en la práctica.

EDITAR El OP explica en el comentario que su notación significa que $x_k$ es un número entero como máximo igual a $u_k$ y al menos igual a $l_k.$ Si ese es el caso, y $u_i - l_1 \gg 1,$ de modo que la búsqueda por fuerza bruta sea prohibitivamente cara, el mejor enfoque es, casi con toda seguridad, la búsqueda por rastreo. De hecho, la forma del problema no es muy distinta de la del $N$ -problema de las reinas (que google).