Complexity and Random Polynomials - Diego Armentano (2012)

En esta disertación analizamos dos enfoques diferentes para el problema de resolver sistemas de ecuaciones polinomiales. En la primer parte de esta memoria analizamos la complejidad de ciertos algoritmos para resolver sistemas de ecuaciones, a saber, métodos homotópicos o métodos de seguimiento de caminos. Ponemos especial atención al problema de valores propios, introduciendo un marco proyectivo para analizar este problema. El resultado principal es acotar la complejidad de caminos de homotopía en términos de la longitud del camino en la métrica de condición. También estudiaremos el problema de la complejidad del teorema de Bézout, reconsiderando el algoritmo de Smale en la luz del trabajo hecho en los últimos años. Al final de esta primera parte definimos un nuevo número de condición adaptado a perturbaciones con direcciones uniformes en un contexto general entre variedades Riemannianas, relacionándolo con los números de condición clásicos en varios ejemplos interesantes. En la segunda parte de esta memoria nos concentramos en las soluciones de sistemas de ecuaciones cuando los coeficientes de estos son tomados al azar con cierta distribuci ́n de probabilidad. Empezaremos dando una breve reseña sobre la fórmula de Rice para campos aleatorios. Repasaremos algunos resultados recientes relacionados al número esperado de raíces reales de un sistema de ecuaciones polinomiales. También repasaremos, dando nuevas pruebas, algunos resultados conocidos relacionados al caso indeterminado, es decir, cuando el sistema de ecuaciones aleatorias tiene más variables que ecuaciones. También estudiaremos sistemas polinomiales aleatorios complejos. Introduciremos las técnicas de Rice en la teoría de campos aleatorios complejos. En particular, daremos un enfoque probabilista al teorema de Bézout usando las fórmulas de Rice. En el final de esta segunda parte consideramos el siguiente problema: ¿cómo están distribuidas las raíces de polinomios complejos aleatorios? Probaremos que puntos en la esfera asociados a raíces de polinomios complejos aleatorios están sorprendentemente bien distribuídos con respecto al mínimo de la energía logaritmica sobre la esfera. Esto es, raíces de polinomios aleatorios brindan una muy buena aproximación de los puntos de Fekete elípticos.