Spelling suggestions: "subject:"géométrie tropicales"" "subject:"géométrie tropical""
1 |
Tropical orbit spaces and moduli spaces of tropical curvesHerold, Matthias 25 January 2011 (has links) (PDF)
Un principal résultat de la thèse est une preuve conceptionnelle du fait que le nombre pondéré de courbes tropicales de degré et genre donnés qui passent par le bon nombre de points en position générale dans $\RR^2$ (resp., qui passent par le bon nombre de points en position générale dans $ \RR^r $ et représentent un point fixé dans l'espace de modules de courbes tropicales abstraites de genre g ) ne dépend pas du choix de points. Un autre principal résultat est un nouveau théorème de correspondance entre les cycles tropicaux plans et les courbes algébriques elliptiques planes.
|
2 |
Géométrie tropicale et systèmes polynomiaux / Tropical geometry and polynomial systemsEl Hilany, Boulos 21 September 2016 (has links)
Les systèmes polynomiaux réels sont omniprésents dans de nombreux domaines des mathématiques pures et appliquées. A. Khovanskii a fourni une borne fewnomiale supérieure sur le nombre de solutions positives non-dégénérées d'un système polynomial réel de n équations à n variables qui ne dépend que du nombre de monômes apparaissant dans les équations. Cette dernière borne a été récemment améliorée par F. Bihan et F. Sottile, mais la borne résultante peut être encore améliorée, même dans certains cas simples.Le but de ce travail est d'aborder trois problèmes importants dans la théorie des Fewnomials. Considérons une famille de systèmes polynomiaux réels avec une structure donnée (par exemple, support ou le nombre de monômes). Un problème est de trouver de bonnes bornes supérieures pour leurs nombres de solutions réelles (ou positives). Un autre problème est de construire des systèmes dont le nombre de solutions réelles (ou positives) sont proches de la meilleure borne supérieure connue. Lorsqu'une borne supérieure optimale est bien connue, qu'est ce qu'on peut dire dans le cas où elle est atteinte?Dans cette thèse, nous affinons un résultat de M. Avendaño en démontrant que le nombre de points d'intersection réels d'une droite réelle avec une courbe réelle plane définie par un polynôme avec au plus t monômes est soit infini ou ne dépasse pas $6t -7$. En outre, on montre que notre borne est optimale pour t=3 en utilisant les dessins d'enfant réels de Grothendieck. Cela montre que le nombre maximal de points d'intersection réels d'une droite réelle avec une courbe trinomiale réelle plane est onze.Nous considérons ensuite le problème de l'estimation du nombre maximal de points d'intersection transverses positifs d'une courbe plane trinomiale et d'une courbe plane t-nomiale. T-Y Li, J.-M. Rojas et X. Wang ont montré que ce nombre est borné par 2^t - 2, et récemment P. Koiran, N. Portier et S. Tavenas ont trouvé la borne supérieure 2t^3/3 +5t. Nous fournissons la borne supérieure $ 3*2^(t-2) - 1 qui est optimale pour t = 3 et est la plus petite pour t=4,...,9. Ceci est réalisé en utilisant la notion de dessins d'enfant réels. De plus, nous étudions en détail le cas t = 3 et nous donnons une restriction sur les supports des systèmes atteignant la borne optimale cinq.Un circuit est un ensemble de n+ 2 points dans $mathbb{R}^n$ qui sont minimalement affinement dépendants. Il est connu qu'un système supporté sur un circuit a au plus n+1 solutions positives non dégénérées, et que cette borne est optimale. Nous utilisons les dessins d'enfant réels et le patchwork combinatoire de Viro pour donner une caractérisation complète des circuits supportant des systèmes polynomiaux avec le nombre maximal de solutions positives non dégénérées.Nous considérons des systèmes polynomiaux de deux équations à deux variables avec cinq monômes distincts au total. Ceci est l'un des cas les plus simples où la borne supérieure optimale sur le nombre de solutions positives non dégénérées n'est pas connue. F. Bihan et F. Sottile ont prouvé que cette borne optimale est majorée par quinze. D'autre part, les meilleurs exemples avaient seulement cinq solutions positives non dégénérées.Nous considérons des systèmes polynomiaux comme avant, mais défini sur le corps des séries de Puiseux réelles généralisées et localement convergentes. Les images par l'application de valuation des solutions d'un tel système sont des points d'intersection de deux courbes tropicales planes. En utilisant des intersections non transverses des courbes tropicales planes, on obtient une construction d'un système polynomial réel comme ci-dessus ayant sept solutions positives non dégénérées. / Real polynomial systems are ubiquitous in many areas of pure and applied mathematics. A. Khovanskii provided a fewnomial upper bound on the number of non-degenerate positive solutions of a real polynomial system of $n$ equations in n variables that depends only on the number of monomials appearing in the equations. The latter bound was recently improved by F. Bihan and F. Sottile, but the resulting bound still has room for improvement, even in some simple cases.The aim of this work is to tackle three main problems in Fewnomial theory. Consider a family of real polynomial systems with a given structure (for instance, supports or number of monomials). One problem is to find good upper bounds for their numbers of real (or positive) solutions. Another problem is to construct systems whose numbers of real (or positive) solutions are close to the best known upper bound. When a sharp upper bound is known, what can be said about reaching it?In this thesis, we refine a result by M. Avendaño by proving that the number of real intersection points of a real line with a real plane curve defined by a polynomial with at most t monomials is either infinite or does not exceed 6t -7. Furthermore, we prove that our bound is sharp for t=3 using Grothendieck's real dessins d'enfant. This shows that the maximal number of real intersection points of a real line with a real plane trinomial curve is eleven.We then consider the problem of estimating the maximal number of transversal positive intersection points of a trinomial plane curve and a t-nomial plane curve. T-Y Li, J.-M. Rojas and X. Wang showed that this number is bounded by 2^t-2, and recently P. Koiran, N. Portier and S. Tavenas proved the upper bound 2t^3/3 +5t. We provide the upper bound 3*2^{t-2} - 1 that is sharp for t=3 and is the tightest for t=4,...,9. This is achieved using the notion of real dessins d'enfant. Moreover, we study closely the case t=3 and give a restriction on the supports of systems reaching the sharp bound five.A circuit is a set of n+2 points in mathbb{R}^n that is minimally affinely dependent. It is known that a system supported on a circuit has at most n+1 non-degenerate positive solutions, and that this bound is sharp. We use real dessins d'enfant and Viro's combinatorial patchworking to give a full characterization of circuits supporting polynomial systems with the maximal number of non-degenerate positive solutions.We consider polynomial systems of two equations in two variables with a total of five distinct monomials. This is one of the simplest cases where the sharp upper bound on the number of non-degenerate positive solutions is not known. F. Bihan and F. Sottile proved that this sharp bound is not greater than fifteen. On the other hand, the best examples had only five non-degenerate positive solutions. We consider polynomial systems as before, but defined over the field of real generalized locally convergent Puiseux series. The images by the valuation map of the solutions of such a system are intersection points of two plane tropical curves. Using non-transversal intersections of plane tropical curves, we obtain a construction of a real polynomial system as above having seven non-degenerate positive solutions.
|
3 |
Results in perturbative quantum supergravity from string theory / Résultats perturbatifs dans les théories de supergravité quantique par la théorie des cordesTourkine, Piotr 09 June 2014 (has links)
Les théories de supergravité sont des extensions supersymmetriques de la relativité générale (RG) d'Einstein. Leur comportement ultraviolet (UV) est meilleur que celui de la RG car les contributions bosoniques et fermioniques se compensent dans les diagrammes en boucles. La supergravité maximale a le meilleur comportement UV, toutefois les prédictions les plus précises venant aussi bien de la théorie des champs que de la théorie des cordes indiquent que la théorie devrait elle aussi souffrir de divergences UV, à partir de 7 boucles. Cette question ouverte constitue un cadre dans lequel peut être problématisés ma thèse. En général, l'approche que j'ai suivie consiste à étudier les amplitudes de diffusion en théorie des cordes dans la limite ou la longueur de la corde devient nulle; on s'attend ainsi à retrouver les amplitudes de diffusion de supergravité. Curieusement, on sait très peu de choses sur cette limite au délà d'une boucle. Une part importante de mon travail thèse a consisté à développer des outils mathématiques basés sur la géométrie tropicale pour décrire cette limite en genre deux et au délà. Afin de tester la précision des prédiction de la théorie des cordes, dans ma thèse j'ai aussi travaillé sur le comportement UV des théories de supergravité demi-maximale. Nous avons montré un théorème de non-renormalisation qui expliqué l'absence de divgerence à 3 boucles et en prédit une à 4 boucles. Enfin je me suis intéressé aux techniques utilisées en théorie des champs pour calculer ces amplitudes à haut nombre de boucles en théorie des champs, et notament à la "double copie BCJ", dont avons proposé la première analyse à une boucle depuis la théorie des cordes. / Supergravity theories are supersymmetric extensions of General Relativity (GR). They have a better ultraviolet (UV) behavior than GR, due to cancellations between bosons and fermions in loop diagrams. Maximal supergravity is a candidate for a UV finite point-like theory of quantum gravity. Nowadays, the most advanced understanding coming from field theory and string theory indicate that the theory should not be UV finite, and that the first UV divergences should appear at the 7-loop order. This open question constitutes a background in which my PhD thesis can be problematized.In this thesis, our approach consists in using string theory scattering amplitudes and study their point-like limit, in which supergravity amplitudes are expected to be recovered. Very little is known beyond one loop on this limit and in this manuscript I describe first how a recent field of mathematics, tropical geometry, may be used in this process, and mention some applications and open issues.Another way to cross-check the predictions of string theory on the UV behavior of maximal supergravity consists in performing the same analysis in theories of reduced supersymmetry.I discuss the case of half-maximal supergravity theories, and show a non-renormalization theorem in heterotic string which explains the vanishing of the 3-loop divergence of this theory and predicts a 4-loop divergence.The last aspect of my work is focused on a string theoretic understanding on the techniques used in field theory to compute higher loop amplitudes. I describe the first analysis of the so called BCJ double copy construction at one-loop from string theory, and partly explain the origin of the BCJ prescription.
|
4 |
Tropical intersection theory, and real inflection points of real algebraic curves / Théorie d’intersection tropicale, et points d’inflexion réels des courbes algébriques réellesGaray-Lopez, Cristhian Emmanuel 29 September 2015 (has links)
Cette thèse est divisée en deux parties principales. D’abord on étudie des relations entre les théories d’intersection en géométrie tropicale et géométrie algébrique. Puis on étudie la question des possibilités pour la distribution de points d’inflexion réels associés à un système linéaire réel défini sur une courbe algébrique réelle lisse. Dans la première partie, nous présentons des nouveaux résultats reliant les théories d’intersection algébrique et tropicale dans une variété algébrique très affine définie sur un corps non-archimédien particulier (dit corps de Mal’cev-Neumann). Le résultat principale concerne l’intersection d’un cycle algébrique de dimension 1 dans une variété à tropicalisation simple avec un diviseur de Cartier. Dans la deuxième partie, nous obtenons d’abord une caractérisation de la répartition des points d’inflexion réels d’un système linéaire complet de degré d>1 sur une courbe elliptique réelle lisse. Puis nous étudions quelques courbes réelles non-hyperelliptiques canoniques de genre 4 dans l’espace projectif de dimension 3. Nous obtenons une formule qui relie le nombre de points de Weierstrass réels d’une telle courbe avec la caractéristique d’Euler-Poincaré d’un certain espace topologique. Finalement, en utilisant la technique du Patchworking (dû à O. Viro), on construit un exemple de courbe réelle, lisse, non-hyperelliptique de genre 4 ayant 30 points de Weierstrass réels. / This thesis is divided in two main parts. First, we study the relationships between intersection theories in tropical and algebraic geometry. Then, we study the question of the possibilities for the distribution of the real inflection points associated to a real linear system defined on a smooth real algebraic curve. In the first part, we present new results linking algebraic and tropical intersection theories over a very-affine algebraic variety defined over a particular non-Archimedean field (known as Mal’cev-Newmann field). The main result concerns the intersection of a one-dimensional algebraic cycle with a Cartier divisor in a variety with simple tropicalization. In the second part, we obtain first a characterization of the distribution of real inflection points associated to a real complete linear system of degree d>1 defined over a smooth real elliptic curve. Then we study some canonical, non-hyperelliptic real algebraic curves of genus 4 in a 3-dimensional projective space. We obtain a formule that relies the amount of real Weierstrass points of such a curve with the Euler-Poincaré characteristic of certain topological space. Finally, using O. Viro’s Patch-working technique, we construct an example of a smooth, non-hyperelliptic real algebraic curve of genus 4 having 30 real Weierstrass points.
|
5 |
Tropical spectrahedra : Application to semidefinite programming and mean payoff games / Spectraèdres tropicaux : application à la programmation semi-définie et aux jeux à paiement moyenSkomra, Mateusz 05 December 2018 (has links)
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.
|
6 |
A tropical geometry and discrete convexity approach to bilevel programming : application to smart data pricing in mobile telecommunication networks / Une approche par la géométrie tropicale et la convexité discrète de la programmation bi-niveau : application à la tarification des données dans les réseaux mobiles de télécommunicationsEytard, Jean-Bernard 12 November 2018 (has links)
La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.
|
Page generated in 0.077 seconds