Project topics and materials
Get Complete Project Material File(s) Now! »
Puiseux series and tropical semifield
In this section, we discuss the fundamental objects of this thesis—the field of Puiseux series and the tropical semifield. We start by briefly introducing the field of Puiseux series. More information about this field can be found in Appendix A, where we discuss in detail the dif- ferent fields used in tropical geometry (e.g., Puiseux series with rational exponents, generalized Puiseux series, Hahn series, both formal and convergent), prove their basic properties, and, following van den Dries and Speissegger [vdDS98], prove that all these fields are real closed (or algebraically closed in the case of complex coefficients). In this work, we use the field of con- vergent, generalized, real Puiseux series. In the context of tropical geometry, a variant of this field without without the convergence assumption first appeared in [Mar10]. Up to a change of variables, this field is isomorphic to the field of generalized Dirichlet series studied by Hardy and Riesz [HR15].
Puiseux series with rational exponents
In this section, we study in more detail the images by valuation of semialgebraic sets defined over the field of Puiseux series with rational exponents. Let us start by defining this field. Definition 3.14. We define the set of Puiseux series with rational exponents, denoted R{{t}}, in the following way. Let x = Σ1 i=1 ci ti be a Puiseux series as in (2.2). Then, x belongs to R{{t}} if there exists N 2 N such that the sequence (i) ⩾ 1 consists of rational numbers with common denominator N. Moreover, the empty series 0 belongs to R{{t}}. One can check that R{{t}} is a subfield of K. Moreover, R{{t}} is a real closed field, and (K, ,k, val, ac) = (R{{t}},Q,R, val, lc) is a model of the theory Thrcvf of real closed valued fields (see Appendix A for an extended discussion). Many authors studying tropical geometry use the field R{{t}}, often without the convergence assumption (or the analogues of these fields with complex coefficients), as the base field for their investigations. This is based on historical reasons (the history of the field R{{t}} can be traced back to Newton, see [BK12, Chapter 8.3]), the use of R{{t}} use in the study of plane algebraic curves [BK12, Chapter 8.3], the simplicity of definition, the fact that the field of formal Puiseux series with rational exponents and complex coefficients is the algebraic closure of the field of Laurent series [Eis04, Corollary 13.15], and the fact that R{{t}} is well adapted for computations [JMM08]. However, the disadvantage of R{{t}} lies in the fact that it has a rational value group. In this way, the image by valuation of a set defined over R{{t}} consists of only rational points, which makes the analysis somewhat less natural (one often studies the closure of the image by valuation). For this reasons, some authors [Mar10, EKL06] consider more general fields with real value group. We follow this convention in our work. The next result shows that this convention is richer—the set of images under the valuation map of semialgebraic sets defined over R{{t}} is a subset of the analogous set of images defined over K (up to taking the closure). Therefore, by studying these images over K we work with a larger class of sets than if we restrict our attention to R{{t}}. Furthermore, the proposition implies that the results obtained over K can be transferred to R{{t}}. In this way, one can use K to obtain theoretical results and R{{t}} for computations. The same result also follows from the analysis of Alessandrini [Ale13, Theorem 4.10].
Valuation of interior and regions of strict feasibility
To finish this chapter, we consider the problem of characterizing the image by valuation of the interior of a spectrahedron. As previously, let Q(1), . . . ,Q(n) 2 Km×m be a sequence of symmetric matrices, denote Q(x) := x1Q(1) +· · · +xnQ(n) and let S := {x 2 Kn ⩾0 : Q(x) ≽ 0} be the associated spectrahedral cone. We want to characterize the set val(int(S)). It turns out that the analysis done in the previous section extends to this problem if the matrices Q(k) are Metzler, but does not solve the case of non-Metzler matrices. To partially handle this case, we study the image by valuation of strictly feasible points of S, and show that our techniques extend naturally to this setting. Let Q(k) := sval(Q(k)) for all k 2 [n]. First, we suppose that the matrices Q(k) are Metzler. The following lemma extends the claim of Lemma 4.17.
Table of contents :
1 Introduction
1.1 Context of this work
1.2 Our contribution
1.3 Organization of the manuscript
1.4 Notation
2 Preliminaries
2.1 Polyhedra and polyhedral complexes
2.2 Real closed fields
2.3 Puiseux series and tropical semifield
2.4 Tropical polynomials
2.5 Valued fields
2.6 Model theory
2.6.1 Theories with quantifier elimination
2.6.2 Model completeness
2.7 Markov chains
I Tropical spectrahedra
3 Tropicalization of semialgebraic sets
3.1 Real analogue of the Bieri–Groves theorem
3.2 Puiseux series with rational exponents
4 Tropical spectrahedra
4.1 Tropical Metzler spectrahedra
4.2 Non-Metzler spectrahedra
4.3 Genericity conditions
4.4 Valuation of interior and regions of strict feasibility
5 Tropical analogue of the Helton–Nie conjecture
5.1 Tropical convexity
5.2 Real tropical cones as sublevel sets of dynamic programming operators
5.3 Description of real tropical cones by directed graphs
5.4 Tropical Helton–Nie conjecture for real tropical cones
5.5 Tropical Helton–Nie conjecture for Puiseux series
5.6 Extension to general fields
II Relation to stochastic mean payoff games
6 Introduction to stochastic mean payoff games
6.1 Optimal policies and Shapley operators
6.2 Sublevel sets, dominions, and the Collatz–Wielandt property
6.3 Bipartite games, their operators, and graphs
7 Equivalence between games and tropical spectrahedra
7.1 From stochastic mean payoff games to tropical spectrahedra
7.2 From tropical spectrahedra to stochastic mean payoff games
7.2.1 Games obtained from well-formed linear matrix inequalities
7.2.2 Preprocessing
7.3 Extension to non-Metzler matrices
7.4 Nonarchimedean semidefinite feasibility problems
8 Condition number of stochastic mean payoff games
8.1 Archimedean feasibility problems
8.1.1 Geometric interpretation of the condition number
8.2 Value iteration for constant value games
8.2.1 Oracle-based approximation algorithms
8.3 Estimates of condition number
8.4 Parametrized complexity bounds for stochastic mean payoff games
8.4.1 Solving constant value games
8.4.2 Finding the states with maximal value
8.5 Application to nonarchimedean semidefinite programming
8.5.1 A class of ergodic problems
8.5.2 Experimental results
9 Perspectives
Bibliography
