Tesis doctoral


Condition and Homology in Semialgebraic Geometry

(Condición y Homología en Geometría Semialgebraica)




Portada de Conditionand Homology in Semialgebraic Geometry por Josué Tonelli Cueto
Josué Tonelli Cueto sosteniendo una copia de su tesis doctoral

Entrega de la Tesis
11/10/2019

Defensa de la Tesis
28/11/2019

Publicación de la Tesis
30/12/2019


Resumen

El cálculo de los grupos de homología de conjuntos semialgebraicos (dados por fórmulas booleanas) es todavía uno de los mayores desafíos de la geometría semialgebraica computacional. Aunque se busca un algoritmo que tome a lo sumo tiempo simplemente exponencial en el número de variables, hasta el día de hoy todos los algoritmos existentes son simbólicos y doblemente exponenciales. En esta tesis doctoral, mostramos cómo se puede obtener un algoritmo numérico que tome tiempo simplemente exponencial con alta probabilidad, lo cual es una mejora del estado del arte. Para ello, explicamos las ideas, métodos y técnicas subyacentes procedentes de la geometría algebraica numérica, de la complejidad numérica y del análisis topológico de datos que han hecho posible este progreso. Terminamos con una lista de problemas y preguntas abiertas que indican un posible futuro de la computación numérica de invariantes topológicos.

Además, en los apéndices, estudiamos el número esperado de ceros reales de un sistema oligonómico aleatorio y damos una visión informal del tema principal de esta tesis en castellano.

Laburpena (Resumen en euskera)

Multzo semialjebraikoen (formula boolearrek emandakoen) homologia-taldeak kalkulatzeak jarraitzen du, oraindik ere, geometria semialjebraiko konputazionalaren erronka handienetako bat izaten. Bilatzen den algoritmoak aldagai kopuruan baino ez du hartzen denbora behin esponentziala; hala ere, gaur egun dauden algoritmo guztiak sinbolikoak eta bi aldiz esponentzialak dira. Doktorego-tesi honetan erakusten dugu nola lor daitekeen debora behin esponentzialean eta probabilitate handiarekin exekutatzen den zenbakizko algoritmo bat; hori teknikaren egoeraren hobekuntza da. Horretarako, zenbakizko geometria aljebraikoaren, zenbakizko konplexutasunaren eta datu-analisi topologikoaren azpian dauden eta aurrerapen hori posible egin duten ideia, metodo eta teknikak azaltzen ditugu. Problemen eta galdera irekien zerrenda batekin bukatzen dugu, zeinek inbariante topologikoen zenbakizko konputazioaren etorkizun posible bat adierazten baitute.

Gainera, eranskinetan, ausazko sistema oligonomiko baten zero kopurua aztertzen dugu, eta tesi honen ikuspegi informala ematen dugu gaztelaniaz.

Abstract (Resumen en inglés)

The computation of the homology groups of semialgebraic sets (given by Boolean formulas) remains one of the open challenges of computational semialgebraic geometry. Despite the search for an algorithm taking singly exponential time only on the number of variables, as of today, the existing algorithms are symbolic and doubly exponential. In this PhD thesis, we show how to obtain a numerical algorithm running in single exponential time with very high probability, which improves the state-of-the-art. To do so, we explain the underlying ideas, methods and techniques from numerical algebraic geometry, numerical complexity and topological data analysis that made this progress possible. We finish with a list of open problems and questions pointing to a possible future of the numerical computation of topological invariants.

Additionally, in the appendices, we cover the topic of the expected number of real zeros of a random fewnomial system and we give an accessible account of the central theme in Spanish.

Zusammenfassung (Resumen en alemán)

Die Berechnung der Homologiegruppen von semialgebraischen Mengen (gegeben durch boolesche Formeln) bleibt eine der offenen Herausforderungen der algorithmischen semialgebraischen Geometrie. Trotz der Suche nach einem Algorithmus mit einfach exponentieller Laufzeit in der Anzahl der Variablen, sind die nach heutigem Stand bekannten Algorithmen symbolisch und doppelt exponentiell. In dieser Doktorarbeit zeigen wir, wie man einen numerischen Algorithmus konstruiert, der mit großer Wahrscheinlichkeit einfach exponentiell ist und somit den Stand der Forschung verbessert. Dazu erklären wir die zugrundliegenden Ideen, Methoden und Techniken von numerischer algebraischen Geometrie, numerischer Komplexität und topologischer Datenanalyse, die dieser Fortschrift möglich machten. Wir enden mit einer Liste offener Probleme und Fragen, die auf eine mögliche Zukunft von Berechnung der topologischen Invarianten weisen.

Außerdem, behandeln wir im Anhange die erwartete Anzahl reeller Nullstellen eines zufälligen Systems polynomialer Gleichungen mit wenigen Termen und geben einen informellen Überblick über das Hauptthema auf Spanisch.


Citación de la tesis

Para citar mi tesis doctoral en tu trabajo, se recomienda la siguiente entrada de BibTeX.

    @phdthesis{tonellicuetothesis,
      author  = {Tonelli-Cueto, Josu\'{e}},
      title   = {{Condition and Homology in Semialgebraic Geometry}},
      school  = {Technische Universit\"at Berlin},
      month   = dec,
      year    = 2019,
      address = {DepositOnce Repository},
      note    = {http://dx.doi.org/10.14279/depositonce-9453},
    }

Para citar en textos no compilados con TeX, LaTeX u otras variantes, es importante indicar el Identificador de Objeto Digital (DOI) en la cita. Este puede indicarse añadiendo “DOI 10.14279/depositonce-9453” o el enlace “http://dx.doi.org/10.14279/depositonce-9453 “.


Grado de doctor

El nombre oficial del grado académico conseguido es Doktor der Naturwissenschaften (Dr. rer. nat.), que significa “doctor en ciencias naturales”. En el sistema académico anglosajón, este grado académico es equivalente al de un PhD. La nota final del doctorado es “mit Auszeichnung bestanden” (summa cum laude), que es la nota máxima que se obtiene solamente cuando todes les evaluadores dan la nota máxima tanto a la tesis como a la defensa.


Proceso de obtención del doctorado

El proceso de obtención del doctorado en la Technische Universität Berlin consta de tres partes: 1) entrega de la tesis, 2) defensa de la tesis, y 3) publicación de la tesis.

Entrega de la tesis (11 de octubre del 2019)

La tesis doctoral fue entregada el 11 de octubre del 2019. Los miembros elegidos para el tribunal de tesis fueron John M. Sullivan como presidente (Vorsitzender), y Peter Bürgisser, Felipe Cucker y Pierre Lairez como evaluadores (Gutachter). En el Institut für Mathematik de la Technische Universität Berlin, el grupo de evaluadores del tribunal de tesis ha estado compuesto tradicionalmente por le(s) director(es) de tesis (en mi caso, Peter Bürgisser y Felipe Cucker) y por une profesor/investigador externe (en mi caso, Pierre Lairez). Les evaluadores deben aprobar la versión entregada de la tesis (vorgelegte Dissertation) antes de que la defensa pueda suceder.

Defensa de la tesis (28 de noviembre del 2019)

La defensa doctoral tuvo lugar el 28 de noviembre del 2019 a las 12:00 en el aula MA313/314 en la 3ª planta del Institut für Mathematik de la Technische Universität Berlin (Str. des 17. Juni 136). Este evento público consistió de una presentación de 30 minutos seguida por una discusión de 90 minutos. Tras la defensa, el tribunal de tesis se reunió en privado. Tras tomar una descisión, se me comunicó en privado que había superado el proceso de evaluación del doctorado. Adicionalmente, me dieron comentarios, y cambios y correcciones menores posibles para la versión final de la tesis.

Después de una defensa exitosa, hubo una pequeña celebración con comida y bebidas en el Matheon Lounge (MA315).

Publicación de la tesis (30 de diciembre del 2019)

Para obtener el certificado de doctor, se debe preparar la versión final de la tesis (genehmigte Dissertation) y publicarla. La opción elegida para ello ha sido el Repositorio DepositOnce de la Technische Universität Berlin, que permite publicar la tesis entregando una versión digital, en formato PDF format, y depositando una copia impresa en la biblioteca universitaria. La versión final de la tesis fue publicada el 30 de diciembre del 2019.

Para la versión final, se realizaron varios cambios. Sin embargo, todos ellos fueron cambios menores y ningún resultado de la tesis se vio afectado. El mayor cambio ocurrió en la fuente para matemáticas usada en el documento, la cual fue substituida por una nueva que encajaba mejor con la fuente elegida para el texto en el documento. Para mantener el registro, la versión entregada (o leída) de la tesis aun se puede descargar en este enlace.


Nota: Las afirmaciones acerca del proceso de obtención del doctorado en la Technische Universität Berlin son válidas únicamente para el proceso de obtención del doctorado en el Institut für Mathematik de la Technische Universität Berlin en la época en la que obtuve mi doctorado. Dado que este proceso ha podido cambiar desde entonces, las afirmaciones hechas pueden no reflejar fielmente este proceso a día de hoy, aunque lo reflejan fielmente en el momento en el obtuve mi título de doctor.