Conjuntos semialgebraicos y deformaciones

SABIA, JUAN; JERONIMO, GABRIELA; PERRUCCI, DANIEL

Córdoba, Argentina

Congreso; LVII Reunión Anual de la Unión Matemática Argentina; 2007

Unión Matemática Argentina

Conjuntos semi-algebraicos y deformaciones Una de las preguntas fundamentales en geometría algebraica real efectiva consiste en determinar si un conjunto definido en Rn por una familia de igualdades y desiguadades de polinomios multivariados con coeficientes reales es vacío o no. Este problema puede verse como un caso particular del problema de la eliminación de cuantificadores en la teoría de primer orden sobre los reales. Los algoritmos más eficientes conocidos para eliminación de cuantificadores (ver [BPR03]) se basan en procedimientos para el cálculo de un punto en cada componente conexa de los conjuntos determinados por cada condición de signo definida por una familia finita de polinomios (donde una condición de signo definida por g1, . . . , gs en Q[x1, . . . , xn] es g1&10, . . . , gs&s0, con &i en {=,>}). Para el cálculo de estos puntos, una estrategia que se ha utilizado consiste en considerar deformaciones infinitesimales del sistema para reducir el problema al caso de una hipersuperficie (considerando sumas de cuadrados de los polinomios) compacta y regular. En esta comunicación presentaremos un posible acercamiento al problema, basado también en técnicas de deformación, que sigue la línea de [BGHM01] y [SS03]. Este enfoque permite trabajar con el sistema de polinomios original, evitando considerar sumas de cuadrados y el consecuente crecimiento del grado de los polinomios que se refleja luego en la complejidad de los algoritmos. En el caso bivariado, describiremos un algoritmo construido en base a esta deformación para el cálculo de un punto en la clausura de cada componente conexa de cada uno de los conjuntos determinados por las condiciones de signo definidas por una familia finita de polinomios.Rn por una familia de igualdades y desiguadades de polinomios multivariados con coeficientes reales es vacío o no. Este problema puede verse como un caso particular del problema de la eliminación de cuantificadores en la teoría de primer orden sobre los reales. Los algoritmos más eficientes conocidos para eliminación de cuantificadores (ver [BPR03]) se basan en procedimientos para el cálculo de un punto en cada componente conexa de los conjuntos determinados por cada condición de signo definida por una familia finita de polinomios (donde una condición de signo definida por g1, . . . , gs en Q[x1, . . . , xn] es g1&10, . . . , gs&s0, con &i en {=,>}). Para el cálculo de estos puntos, una estrategia que se ha utilizado consiste en considerar deformaciones infinitesimales del sistema para reducir el problema al caso de una hipersuperficie (considerando sumas de cuadrados de los polinomios) compacta y regular. En esta comunicación presentaremos un posible acercamiento al problema, basado también en técnicas de deformación, que sigue la línea de [BGHM01] y [SS03]. Este enfoque permite trabajar con el sistema de polinomios original, evitando considerar sumas de cuadrados y el consecuente crecimiento del grado de los polinomios que se refleja luego en la complejidad de los algoritmos. En el caso bivariado, describiremos un algoritmo construido en base a esta deformación para el cálculo de un punto en la clausura de cada componente conexa de cada uno de los conjuntos determinados por las condiciones de signo definidas por una familia finita de polinomios. Referencias: [BGHM01] B. Bank, M. Giusti, J. Heintz, G.M. Mbakop. Polar varieties and efficient real elimination. Math. Z. 238 (2001), No. 1, 115–144. [BPR03] S. Basu, R. Pollack, M.-F. Roy, Algorithms in real algebraic geometry. Springer-Verlag, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set. Proc. of ISSAC 2003, 224–231 (electronic), ACM, New York, 2003.