El problema de decisión para una clase de funciones Pfaffianas

BARBAGALLO, MARÍA LAURA; JERONIMO, GABRIELA; SABIA, JUAN

La Plata

Congreso; LXVII Reunión anual de comunicaciones científicas de la Unión Matemática Argentina; 2018

En 1948, Tarski planteó el problema de decisión para la teoría de primer orden sobre los reales extendida con exponenciación. El problema fue resuelto parcialmente en [MacWil96] bajo la hipótesis de que la conjetura de Schanuel es válida y, más recientemente, fue considerado desde el punto de vista algorítmico para fragmentos de la teoría, desarrollándose métodos numéricos para su resolución [McCWei12]) aunque sin un estudio de la complejidad.En este marco, analizamos el problema de decisión para fórmulas de primer orden que involucran funciones Pfaffianas de orden 1; más precisamente, funciones de la forma f(x) = F(x, S(x)), con F en Z[x,y], para una función S fija que es solución de una ecuación diferencial del tipo S'(x) = T(x, S(x)) con T en Z[x,y]. Una clase particular de funciones de este tipo son los E-polinomios, que son aquellas en las que S(x) = e^{h(x)} para un polinomio h en Z[x] fijo.Presentamos un algoritmo simbólico nuevo con estimaciones de complejidad para la resolución de este problema quegeneraliza los procedimientos conocidos para fórmulas que sólo involucran polinomios sobre R (ver, por ejemplo, [BPR06]). La herramienta fundamental es una noción apropiada de secuencia de Sturm que introducimos para la clase de funciones considerada, que nos permite determinar, dadas dos funciones f y g, las cantidades de ceros reales de f en los que g se anula, en los que g es positiva y en los que g es negativa.A partir de una construcción algorítmica de secuencias de Sturm, desarrollamos un método simbólico para determinar las condiciones de signo realizables sobre una familia finita de funciones de esta clasey lo aplicamos para el diseño de un algoritmo simbólico de decisión.Para funciones Pfaffianas de orden 1 arbitrarias, como es habitual en la literatura ([GabVor04]), utilizamos un oráculo para determinar el signo que una función toma en un número algebraico. Para el caso particular de E-polinomios, aplicando herramientas desarrolladas en [BJS16], obtenemos un algoritmo para resolver el problema sin necesidad de un oráculo y con estimaciones explícitas de complejidad.Bibliografía[BJS16] M.L. Barbagallo, G. Jeronimo, J. Sabia. Zero counting for a class of univariate Pfaffian functions.J. Algebra 452 (2016), 549--573.[BPR06] S. Basu, R. Pollack, M.-F. Roy. Algorithms in realalgebraic geometry. Second edition. Algorithms and Computation in Mathematics,10. Springer-Verlag, Berlin, 2006.[GabVor04] A. Gabrielov, N. Vorobjov. Complexity of computations with Pfaffian andNoetherian functions. In Normal Forms, Bifurcations and Finiteness Problems in DifferentialEquations, Kluwer, 2004.[McCWei12] S. McCallum, V. Weispfenning. Deciding polynomial-transcendental problems. J.Symbolic Comput. 47 (2012), no. 1, 16--31.[MacWil96] A. Macintyre, A.J. Wilkie, On the decidability of the real exponential field,Kreiseliana: About and around Georg Kreisel, A.K. Peters, 1996, pp. 441--467.