Condition and Homology in Semialgebraic Geometry
(Condición y Homología en Geometría Semialgebraica)
Obtuvo el 3º Premio para tesis doctorales en los Premios Tiburtius 2020 de las Universidades de Berlín
y el Premio MATH+ 2020 para Disertaciones
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},
type = {Doctoral Thesis},
month = dec,
year = 2019,
address = {DepositOnce Repository},
url = {http://dx.doi.org/10.14279/depositonce-9453},
doi = {10.14279/depositonce-9453},
note = {\href{http://dx.doi.org/10.14279/depositonce-9453}{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.
(©2019 Milica Valent)
Después de una defensa exitosa, hubo una pequeña celebración con comida y bebidas en el Matheon Lounge (MA315) con amigues y familiares.
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.
3º Premio en los Premios Tiburtius 2020 de las Universidades de Berlín
Esta tesis obtuvo el 3º Premio para tesis doctorales en los Premios Tiburtius 2020 de las Universidades de Berlín. El fallo del premio puede leerse en este enlace. La tesis fue nominada al premio por Peter Bürgisser.
Los Premios Tiburtius de las Universidades de Berlín (Tiburtius-Preis - Preis der Berliner Hochschulen, en alemán) son otorgados cada año por la Conferencia Estatal de Rectores y Presidentes de las Universidades de Berlín (LKRP). Estos premios consisten en tres premios (1º, 2º y 3º) y tres accésits para tesis doctorales defendidas el año anterior en una de las universidades de Berlín, y en tres premios (1º, 2º y 3º) para tesis de Máster presentadas el año anterior en una de las Fachhochschules (universidades de ciencias aplicadas) de Berlín. Para ser considarada para los Premios Tiburtius, la tesis ha debido obtener la nota más alta y debe ser nominada por uno de les profesores de las universidades de Berlín.
Premio MATH+ 2020 para Disertaciones
Esta tesis obtuvo el Premio MATH+ 2020 para Disertaciones. Una nota de prensa puede leerse, en inglés, en este enlace. La tesis fue nominada al premio por Peter Bürgisser.
Los Premios MATH+ para Disertaciones (MATH+ Dissertation Award, en inglés) son otorgados cada año por el Berlin Mathematics Research Center MATH+, la Berlin Mathematical School y la Einstein Foundation Berlin. Estos premios consisten en hasta tres premios teniendo todos ellos la misma categoría y valor. Para ser considarada para los Premios MATH+ para Disertaciones, la tesis ha debido obtener la nota más alta y debe ser nominada por uno de les profesores de MATH+.
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.