No description available.

This thesis is primarily concerned in studying the relationship between different exponents of Diophantine approximation, which are quantities arising naturally in the study of rational approximation to a fixed n-tuple of real irrational numbers. As Khinchin observed, these exponents are not independent of each other, spurring interest in the study of the spectrum of a given family of exponents, which is the set of all possible values that can be taken by said family of exponents. Introduced in 2009-2013 by Schmidt and Summerer and completed by Roy in 2015, the parametric geometry of numbers provides strong tools with regards to the study of exponents of Diophantine approximation and their associated spectra by the introduction of combinatorial objects called n-systems. Roy proved the very surprising result that the study of spectra of exponents is equivalent to the study of certain quantities attached to n-systems. Thus, the study of rational approximation can be replaced by the study of n-systems when attempting to determine such spectra. Recently, Roy proved two new results for the case n=3, the first being that spectra are semi-algebraic sets, and the second being that spectra are stable under the minimum with respect to the product ordering. In this thesis, it is shown that both of these results do not hold in general for n>3, and examples are given. This thesis also provides non-trivial examples for n=4 where the spectra is stable under the minimum. An alternate and much simpler proof of a recent result of Marnat-Moshchevitin proving an important conjecture of Schmidt-Summerer is also given, relying only on the parametric geometry of numbers instead. Further, a conjecture which generalizes this result is also established, and some partial results are given towards its validity. Among these results, the simplest, but non-trivial, new case is also proven to be true. In a different vein, this thesis considers certain generalizations theta(q) of the classical theta q-series. We show under conditions on the coefficients of the series that theta(q) is neither rational nor quadratic irrational for each integer q>1.

This thesis consists of six chapters and deals with four topics related to De Rham Theory on semialgebraic sets. The first topic deals with L-infinity cohomology on semialgebraic sets. We introduce smooth L-infinity differential forms on a singular (semialgebraic) space X in Rn. Roughly speaking, a smooth L-infinity differential form is a collection of smooth forms on disjoint smooth subsets (stratification) of X with matching tangential components on the adjacent strata and of bounded size (in the metric induced from Rn). We identify the singular homology of X as the homology of the chain complex generated by semialgebraic singular simplices, i.e. continuous semialgebraic maps from the standard simplex into X. Singular cohomology of X is defined as the homology of the Hom dual to the chain complex of the singular chains. Finally, we prove a De Rham type theorem establishing a natural isomorphism between the singular cohomology and the cohomology of smooth L-infinity forms. The second topic is a construction of a Lipschitz deformation retraction on a neighborhood of a point in a semialgebraic set with estimates on its derivatives. Such a deformation retraction is the key to the results of the first and the third topics. The third topic is related to Poincare inequality on a semialgebraic set. We study Poincare type Lp inequality for differential forms on a compact semialgebraic subset of Rn for p >> 1. First we derive a local inequality by using a Lipschitz deformation retraction with estimates on its derivatives from the second topic and then we extend it to a global inequality by employing a technique developed in the appendix. As a consequence we obtain an isomorphism between Lp cohomology and singular cohomology of a normal compact semialgebraic set. The final topic is in the appendix. It deals with an explicit proof of Poincare type inequality for differential forms on compact manifolds. We prove the latter inequality by means of a constructive 'globalization' method of a local Poincare inequality on convex sets. The appendix serves as a model case for the results of the third topic in Chapter 5.

This thesis consists of six chapters and deals with four topics related to De Rham Theory on semialgebraic sets. The first topic deals with L-infinity cohomology on semialgebraic sets. We introduce smooth L-infinity differential forms on a singular (semialgebraic) space X in Rn. Roughly speaking, a smooth L-infinity differential form is a collection of smooth forms on disjoint smooth subsets (stratification) of X with matching tangential components on the adjacent strata and of bounded size (in the metric induced from Rn). We identify the singular homology of X as the homology of the chain complex generated by semialgebraic singular simplices, i.e. continuous semialgebraic maps from the standard simplex into X. Singular cohomology of X is defined as the homology of the Hom dual to the chain complex of the singular chains. Finally, we prove a De Rham type theorem establishing a natural isomorphism between the singular cohomology and the cohomology of smooth L-infinity forms. The second topic is a construction of a Lipschitz deformation retraction on a neighborhood of a point in a semialgebraic set with estimates on its derivatives. Such a deformation retraction is the key to the results of the first and the third topics. The third topic is related to Poincare inequality on a semialgebraic set. We study Poincare type Lp inequality for differential forms on a compact semialgebraic subset of Rn for p >> 1. First we derive a local inequality by using a Lipschitz deformation retraction with estimates on its derivatives from the second topic and then we extend it to a global inequality by employing a technique developed in the appendix. As a consequence we obtain an isomorphism between Lp cohomology and singular cohomology of a normal compact semialgebraic set. The final topic is in the appendix. It deals with an explicit proof of Poincare type inequality for differential forms on compact manifolds. We prove the latter inequality by means of a constructive 'globalization' method of a local Poincare inequality on convex sets. The appendix serves as a model case for the results of the third topic in Chapter 5.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Esta dissertaÃÃo està baseada em uma sÃrie de trabalhos publicados por H. Delfs e M. Knebusch sobre uma teoria de homologia para espaÃos semialgÃbricos sobre corpos reais fechados. Neste trabalho, reunimos as definiÃÃes e principais resultados sobre a teoria de homologia semialgÃbrica. AlÃm dissso, como aplicaÃÃo dessa teoria, trazemos uma prova do Teorema de Ax-Grothendick para aplicaÃÃes polinomiais sobre corpos reais fechados. / This thesis is based on a series of papers published by H. Delfs and M. Knebusch on a homology theory to semialgebraic spaces on real closed fields. In this work, we collect the definitions and main results on the theory of semialgebraic homology. Furthermore, as application of this theory, we present a proof of the theorem of Ax-Grothendick for polynomials applications on real closed fields.

This thesis analyses the semialgebraic sets, that is, a finite union of solu- tions to a finite sequence of polynomial inequalities. We introduce a notion of cylindrical algebraic decomposition as a tool for the construction of a semialge- braic stratification and a triangulation of a semialgebraic set. On this basis, we prove several important and well-known results of real algebraic geometry, such as Hardt's semialgebraic triviality or Sard's theorem. Drawing on Morse theory, we finally give a proof of a Thom-Milnor bound for a sum of Betti numbers of a real algebraic set. 1

La programmation semi-définie est un outil fondamental d'optimisation convexe et polynomiale. Elle revient à optimiser une fonction linéaire sur un spectraèdre (un ensemble défini par des inégalités matricielles linéaires). En particulier, la programmation semi-définie est une généralisation de la programmation linéaire.Nous étudions l'analogue non-archimédien de la programmation semi-définie, en remplaçant le corps des nombres réels par le corps des séries de Puiseux. Notre approche est fondée sur des méthodes issues de la géométrie tropicale et, en particulier, sur l'étude de la tropicalisation des spectraèdres.En première partie de la thèse, nous analysons les images par la valuation des ensembles semi-algébriques généraux définis dans le corps des séries de Puiseux. Nous montrons que ces images ont une structure polyédrale, ce qui fournit un analogue réel du théorème de Bieri et Groves. Ensuite, nous introduisons la notion de spectraèdres tropicaux et nous montrons que, sous une hypothèse de généricité, ces objets sont décrits par des systèmes d'inégalités polynomiales de degré 2 sur le semi-corps tropical. Cela généralise un résultat de Yu sur la tropicalisation du cône des matrices positives.Une question importante relative à la programmation semi-définie sur les réels consiste à caractériser des projections de spectraèdres. Dans ce cadre, Helton et Nie ont conjecturé que tout ensemble semi-algébrique convexe est la projection d'un spectraèdre. La conjecture a été réfutée par Scheiderer. Néanmoins, nous montrons qu'elle est vraie ''à valuation près'' : dans le corps réel clos des séries de Puiseux, les ensembles semi-algébriques convexes et les spectraèdres projetés ont exactement les mêmes images par la valuation non-archimédienne.En seconde partie de la thèse, nous étudions des questions algorithmiques liées à la programmation semi-définie. Le problème algorithmique de base consiste à décider si un spectraèdre est vide. On ne sait pas si ce problème appartient à NP dans le modèle de la machine de Turing, et les algorithmes fondés sur la décomposition cylindrique algébrique ou la méthode de points critiques constituent l'état de l'art dans ce domaine. Nous montrons que, dans le cadre non-archimédien, les spectraèdres tropicaux génériques sont décrits par des opérateurs de Shapley associés aux jeux à paiement moyen stochastiques. Cela donne une méthode pour résoudre des problèmes de réalisabilité en programmation semi-définie non-archimédienne en utilisant les algorithmes combinatoires conçus pour les jeux stochastiques.Dans les chapitres finals de la thèse, nous établissons des bornes de complexité pour l'algorithme d'itération sur les valeurs qui exploitent la correspondance entre les jeux stochastiques et la convexité tropicale. Nous montrons que le nombre d'itérations est contrôlé par un nombre de conditionnement relié au diamètre intérieur du spectraèdre tropical associé.Nous fournissons des bornes supérieures générales sur le nombre de conditionnement. Pour cela, nous établissons des bornes optimales sur la taille en bits des mesures invariantes de chaînes de Markov. Comme corollaire, notre estimation montre que l'itération sur la valeur résout les jeux ergodiques à paiement moyen en temps pseudo-polynomial si le nombre de positions aléatoires est fixé. Enfin, nous expérimentons notre approche à la résolution de programmes semi-définis non-archimédiens aléatoires de grande taille. / Semidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing the linear functions over the spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming.The purpose of this thesis is to study the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra.In the first part of the thesis, we analyze the images by valuation of general semialgebraic sets defined over the Puiseux series. We show that these images have a polyhedral structure, giving the real analogue of the Bieri--Groves theorem. Subsequently, we introduce the notion of tropical spectrahedra and show that, under genericity conditions, these objects can be described explicitly by systems of polynomial inequalities of degree 2 in the tropical semifield. This generalizes the result of Yu on the tropicalization of the SDP cone.One of the most important questions about real SDPs is to characterize the sets that arise as projections of spectrahedra. In this context, Helton and Nie conjectured that every semialgebraic convex set is a projected spectrahedron. This conjecture was disproved by Scheiderer. However, we show that the conjecture is true ''up to taking the valuation'': over a real closed nonarchimedean field of Puiseux series, the convex semialgebraic sets and the projections of spectrahedra have precisely the same images by the nonarchimedean valuation.In the second part of the thesis, we study the algorithmic questions related to SDP. The basic computational problem associated with SDP over real numbers is to decide whether a spectrahedron is nonempty. It is unknown whether this problem belongs to NP in the Turing machine model, and the state-of-the-art algorithms that certify the (in)feasibility of spectrahedra are based on cylindrical decomposition or the critical points method. We show that, in the nonarchimedean setting, generic tropical spectrahedra can be described by Shapley operators associated with stochastic mean payoff games. This provides a tool to solve nonarchimedean semidefinite feasibility problems using combinatorial algorithms designed for stochastic games.In the final chapters of the thesis, we provide new complexity bounds for the value iteration algorithm, exploiting the correspondence between stochastic games and tropical convexity. We show that the number of iterations needed to solve a game is controlled by a condition number, which is related to the inner radius of the associated tropical spectrahedron. We provide general upper bounds on the condition number. To this end, we establish optimal bounds on the bit-length of stationary distributions of Markov chains. As a corollary, our estimates show that value iteration can solve ergodic mean payoff games in pseudopolynomial time, provided that the number of random positions of the game is fixed. Finally, we apply our approach to large scale random nonarchimedean SDPs.

Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

Suite aux travaux de Zbigniew Szafraniec et Nicolas Dutertre, je me suis intéressée aux calculs de caractéristiques d'Euler de certains espaces semi-algébriques. En particulier, ceux de laforme : $ {(-1)^{varepsilon_1} G_1geq 0 }cap...cap{(-1)^{varepsilon_l} G_lgeq 0}cap W$, où $epsilon=(epsilon_1,...,epsilon_l)in{0,1}^l$, $G=(G_1,...,G_l):R^nrightarrowR^l$ polynomiale et $W:=F^{-1}(0)subsetR^n$ où $F:R^nrightarrowR^k$ et $k+lleq n$. Une fois le cas lisse traité, on intersecte ces ensembles avec ${ fgeq 0}$ ou ${ fleq 0}$, où $f$ est polynomiale telle que $f^{-1}(0)$ admette un nombre fini de singularités. J'énonce alors un théorème reliant ces caractéristiques au degré d'applications faisant intervenir les fonctions $f$, $F$ et $G$. Pour finir, on s'intéresse au cas où l'ensemble $W$ possède un lieu critique compact.Dans une autre partie, je travaille sur l'indice radial, indice défini sur des variétés singulières. J'énonce un résultat faisant le lien entre l'indice radial d'un champ de vecteurs V en une singularité avec l'indice radial de son opposé -V. Finalement, je relie l'indice radial à un indice d'intersection. / After the works of Zbigniew Szafraniec and Nicolas Dutertre, we are interested in computing Euler characteristics of some particular semialgebraic sets. In particular, the ones of the form : $ {(-1)^{varepsilon_1} G_1geq 0 }cap...cap{(-1)^{varepsilon_l} G_lgeq 0}cap W$, where $varepsilon=(varepsilon_1,...,varepsilon_l)in{0,1}^l$, $G=(G_1,...,G_l):R^nrightarrowR^l$ polynomial and $W:=F^{-1}(0)subsetR^n$ where $F:R^nrightarrowR^k$ and $k+lleq n$. Once the smooth case is treated, we intersect these sets with ${ fgeq 0}$ or ${ fleq 0}$, where $f$ is polynomial such that $f^{-1}(0)$ contains a finite number of singularities. Then we state a theorem that makes a link between these caracteristics and some degrees of mappings involving the functions $f$, $F$ and $G$. Finally, we study the case where $W$ has a compact singular set.In another part, I work with the radial index, an index defined for singular manifolds. I have a result making a link between the radial index of a vector field V and its opposite -V at a singularity. Finally, I relate that radial index to an intersection index.

Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournis. / In this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided.