---

Condition and Homology in Semialgebraic Geometry

---

Awarded the 3rd Prize for doctoral theses in the Tiburtius Prizes 2020 of the Berlin Universities
and the MATH+ Dissertation Award 2020

---

---

---

---

---

Abstract

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 (Abstract in German)

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.

Laburpena (Abstract in Basque)

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.

Resumen (Abstract in Spanish)

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.

---

Citation of the thesis

For citing my doctoral thesis in your work, the following BibTeX entry is recomended.

    @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}},
    }

For citations in texts not compiled with TeX, LaTeX or other variants, it is important to add the Digital Object Identifier (DOI) to the citation. The latter can be indicated either with “DOI 10.14279/depositonce-9453” or with the link “http://dx.doi.org/10.14279/depositonce-9453”.

---

Doctoral degree

The official name of the obtained academic degree is Doktor der Naturwissenschaften (Dr. rer. nat.), which means “doctor in natural sciences”. In the anglosaxon academic system, this degree is equivalent to a PhD. The doctorate was obtained with the grade “mit Auszeichnung bestanden” (summa cum laude), which is the maximum grade obtained only when all the evaluators give the maximum grade to both the thesis and the defense.

---

Doctoral procedure

The doctoral procedure of the Technische Universität Berlin has three parts: 1) handing of the thesis, 2) doctoral defense, and 3) publication of the thesis.

Handing of the thesis (11th of October of 2019)

The doctoral thesis was handed in on the 11th of October of 2019. The chosen members of the doctoral committe were John M. Sullivan as president (Vorsitzender), and Peter Bürgisser, Felipe Cucker and Pierre Lairez as evluators (Gutachter). Traditionally at the Institut für Mathematik of the Technische Universität Berlin, the group of evaluators of the doctoral committe has been composed by the doctoral supervisor(s) (in my case, Peter Bürgisser and Felipe Cucker) and an external professor/researcher (in my case, Pierre Lairez). The evaluators must approve the handed version of the thesis (vorgelegte Dissertation) before the doctoral defense can take place.

Doctoral defense (28th of November of 2019)

The doctoral defense took place on the 28th of November of 2019 at 12:00 at room MA313/314 on the 3rd floor of the Institut für Mathematik of the Technische Universität Berlin (Str. des 17. Juni, 136). This public event consisted of a presentation of 30 minutes, followed by 90 minutes of discussion. After the defense, the doctoral committee met in private. Once they arrived at a decision, they communicated to me in private that I had successfully passed the doctoral examination. Additionally, they gave me comments and possible minor changes and corrections for preparing the final version of the thesis.

After a successful defense, there was a small celebration with food and drinks in the Matheon Lounge (MA315) with friends and relatives.

Show pictures of the afterdefence

Publication of the thesis (30th of December of 2019)

To obtain the doctoral certificate, one has to prepare the final version of the thesis (genehmigte Dissertation) and publish it. The chosen option was the DepositOnce Repository of the Technische Universität Berlin, which allows one to publish the thesis by submitting a digital version (in PDF format) and depositing a printed copy in the university library. The final version of the thesis was published on the 30th of December of 2019.

For the final version, several changes were made. However, all these changes were minor, and no result of the thesis was affected. The biggest change occurred in the used mathematics-font of the document, which was substituted by a new one matching better the chosen text-font of the document. To keep the record, the handed version of the thesis (vorgelegte Dissertation) can be downloaded at this link.

---

3rd Prize in the Tiburtius Prizes 2020 of the Berlin Universities

The thesis obtained the 3rd Prize for doctoral theses in the Tiburtius Prizes 2020 of the Berlin Universities. The jury's decision on the prize can be seen at this link. The thesis was nominated for the prize by Peter Bürgisser.

The Tiburtius Prizes of the Berlin Universities (Tiburtius-Preis - Preis der Berliner Hochschulen, in German) are awarded each year by the State Conference of Rectors and Presidents of Berlin Universities (LKRP). They consist on three prizes (1st, 2nd, and 3rd) and three recognition awards for doctoral theses defended the previous year at one of the Berlin universities, and on three prizes (1st, 2nd, and 3rd) for Master theses presented the previous year at one of the Berlin Fachhochschules (universities of applied sciences). To be considered for the Tiburtius Prizes, the thesis must have the highest possible grade and it should be nominated by one of the professors at the Berlin universities.

---

MATH+ Dissertation Award 2020

The thesis obtained the MATH+ Dissertation Award 2020. A press release can be seen at this link. The thesis was nominated for the prize by Peter Bürgisser.

The MATH+ Dissertation Awards are awarded each year by the Berlin Mathematics Research Center MATH+, the Berlin Mathematical School and the Einstein Foundation Berlin. Each year, there can be up to three awards having all the same status and value. To be considered for the MATH+ Dissertation Awards, the thesis must have the highest possible grade and it should be nominated by one of the professors at MATH+.

---

Note: The claims about the doctoral procedure at the Technische Universität Berlin applies only to how the doctoral procedure was at the Institut für Mathematik of the Technische Universität Berlin when I obtained my doctoral degree. Since this procedure might have changed, the above claims might not reflect faithfully anymore this procedure, although they do reflect it faithfully at the time I obtained my doctoral degree.