Conjuntos semialgebraicos y deformaciones

GABRIELA JERONIMO; DANIEL PERRUCCI; JUAN SABIA

Córdoba, Pcia. de Córdoba

Congreso; LVII Reunión de Comunicaciones Científicas de la UMA; 2007

UMA

Una de las preguntas fundamentales en geometría algebraica real efectiva consiste en determinar si un conjunto definido en R^n 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 ∈ Q[x1 , . . . , xn ] es g1 σ1 0, . . . , gs σs 0, con σi ∈ {=, >}). Para el cálculo de estos puntos, unaestrategia que se ha utilizado consiste en considerar deformaciones infinitesimales del sistema para reducir elproblema al caso de una hipersuperficie (considerando sumas de cuadrados de los polinomios) compacta yregular.En esta comunicación presentaremos un posible acercamiento al problema, basado también en técnicasde deformación, que sigue la línea de [BGHM01] y [SS03]. Este enfoque permite trabajar con el sistema depolinomios original, evitando considerar sumas de cuadrados y el consecuente crecimiento del grado de lospolinomios que se refleja luego en la complejidad de los algoritmos. En el caso bivariado, describiremos unalgoritmo construido en base a esta deformación para el cálculo de un punto en la clausura de cada componenteconexa de cada uno de los conjuntos determinados por las condiciones de signo definidas por una familia finitade polinomios.[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.