G K Rumindo

N Duchateau

P Croisille

J Ohayon

P Clarysse

Strain-Based Parameters for Infarct Localization: Evaluation via a Learning Algorithm on a Synthetic Database of Pathological Hearts

Keywords: Finite-element model, myocardial infarct, myocardial strain, infarct diagnosis, machine learning

Localization of infarcted regions is essential to determine the most appropriate treatment for patients with cardiac ischemia. Myocardial strain partially reflects the location of infarcted regions, which demonstrated potential use in clinical practice. However, strain patterns are complex and simple thresholding is not su cient to locate the infarcts. Besides, many strain-based parameters exist and their sensitivities to myocardial infarcts have not been directly investigated. In our study, we propose to evaluate nine strain-based parameters to locate infarcted regions. For this purpose, we designed a large database (n=200) of synthetic pathological finite-element heart models from 5 real healthy left ventricle geometries. The infarcts were incorporated with random location, shape and degree of severity. In addition, we used a state-of-theart learning algorithm to link deformation patterns and infarct location. Based on our evaluation, we propose to sort the strain-based parameters into three groups according to their performances in locating infarcts.

Introduction

The clinical value of determining myocardial viability to help the physicians decide on the best treatment for patients with cardiac ischemia has been established [START_REF] Flachskampf | Cardiac imaging after myocardial infarction[END_REF]. Late Gadolinium Enhancement -an MR imaging method -is generally accepted as the gold standard to assess myocardial viability and therefore to locate myocardial infarcts. However, it requires contrast injection, is costly and not available for all patients. Myocardial strains -extracted from cardiac MR [START_REF] Wang | Cardiac motion and deformation recovery from MRI: a review[END_REF] or echocardiography [START_REF] Dandel | Strain and strain rate imaging by echocardiography -basic concepts and clinical applicability[END_REF] -have also been used to identify dysfunctional regions of the heart [START_REF] Antoni | Prognostic importance of strain and strain rate after acute myocardial infarction[END_REF]. However, due to the complex strain patterns, simple thresholding is not su cient and further processing is required [START_REF] Sjøli | Diagnostic capability and reproducibility of strain by Doppler and by speckle tracking in patients with acute myocardial infarction[END_REF]. Learning-based algorithms have been investigated for better detecting [START_REF] Medrano-Garcia | Statistical shape modelling of the left ventricle: myocardial infarct classification challenge[END_REF] and locating [START_REF] Bleton | Myocardial infarct localization using neighborhood approximation forests[END_REF][START_REF] Duchateau | Infarct localization from myocardial deformation: prediction and uncertainty quantification by regression from a low-dimensional space[END_REF] infarcts from strain data. These methods are promising and can be generalized to di↵erent modalities and subjects, in addition to showing high accuracy of infarct detection.

Several strain-based parameters have been investigated for infarct localization. However, many more exist and their potential has not been evaluated. In our study, we propose to evaluate the following nine strain-based parameters; principal strain, e↵ective strain, fractional anisotropy [START_REF] Soleimanifard | Identification of myocardial infarction using three-dimensional strain tensor fractional anisotropy[END_REF], three local directional strains (radial, circumferential, longitudinal), and three stretch-dependent invariants (in fiber, cross-fiber, and sheet-normal directions). They were assessed in terms of their localization performance (sensitivity and specificity) given a learning algorithm to locate the infarcts. The algorithm uses a regression to find the transfer function between the tested parameters and the infarct location [START_REF] Duchateau | Infarct localization from myocardial deformation: prediction and uncertainty quantification by regression from a low-dimensional space[END_REF]. To do so, we designed a large database of synthetically-generated pathological cases that incorporates infarcts with di↵erent locations, shapes, sizes, and degrees of severity. Notably, we demonstrated that by properly designing and exploiting a large and su ciently varied database of pathological cases, we were able to really push the limits of each strain parameter used in the detection algorithm and to better estimate their localization performances.

Materials and methods

Five LV meshes (3552 hexahedral elements) from healthy volunteers were obtained from an open access source [START_REF] Genet | Distribution of normal human left ventricular myofiber stress at end diastole and end systole: a target for in silico design of heart failure treatments[END_REF]. A finite-element model of each healthy LV in the diastolic (filling) phase was simulated. Afterwards, 40 pathological cases were generated based on each LV geometry -resulting in 200 pathological cases -and the nine strain-based parameters were computed. Finally, the learning algorithm was applied to evaluate the localization performance of each parameter.

Database of pathological cases

Simulation of healthy cases. The diastolic simulation for the healthy LV model follows the principles detailed in [START_REF] Genet | Distribution of normal human left ventricular myofiber stress at end diastole and end systole: a target for in silico design of heart failure treatments[END_REF][START_REF] Rumindo | Comparison of di↵erent strainbased parameters to identify human left ventricular myocardial infarct during diastole: a 3D finite element study[END_REF]. Rule-based fiber orientation was incorporated into the LV geometry by first defining a pseudoprolate spheroidal coordinate system that consists of radial (orthogonal to the LV surface), circumferential and longitudinal (tangential to the LV surface) directions. Subsequently, an orthogonal fiber coordinate system was defined, which is comprised of fiber, sheet and sheet-normal directions. The fibers are oriented with an elevation angle distribution of -60 to +60 from the epicardium to the endocardium [START_REF] Holzapfel | Constitutive modelling of passive myocardium: a structurally-based framework for material characterization[END_REF].

The constitutive law was the transversely isotropic Fung-type law [START_REF] Genet | Distribution of normal human left ventricular myofiber stress at end diastole and end systole: a target for in silico design of heart failure treatments[END_REF] (Eq. 1). The strain energy density function is divided into two parts; the isochoric term, which is based on the Green-Lagrange strain tensor E, and the volumetric term:

W = Isochoric term z }| { C 2 (e Q 1) + Volumetric term z }| { 1 D ( J 2 1 2 ln J) Q = b f E 2 ff + b t E 2 ss + b t E 2 nn + b t (E 2 sn + E 2 ns ) + b fs (E 2 fs + E 2 sf + E 2 fn + E 2 nf ) | {z }
Exponential terms of the isochoric part; E : Green-Lagrange strain tensor

(1) where C, b f ,b t and b fs are the material parameters to be personalized for each subject; J is the determinant of the deformation gradient tensor F; whereas D was set to 0.001 to enforce quasi-incompressibility. The subscripts f , s and n denote the fiber, sheet and sheet-normal directions, respectively. Active tension was not taken into account as we only simulated the diastolic phase in this study. The models were solved using the finite-element software ABAQUS1 , and the constitutive law was implemented in ABAQUS user material subroutine UMAT.

The material parameters were personalized for each subject based on the end-diastolic pressure-volume relationships described in [START_REF] Klotz | Single-beat estimation of end-diastolic pressure-volume relationship: a novel method with potential for noninvasive application[END_REF]. The beginning-and end-diastolic volumes of each subject were known; the corresponding pressures were set to 0 and 9 mmHg, respectively.

Simulation of pathological cases. Forty synthetically-generated cases were generated from each of the 5 healthy LV models, resulting in 200 cases. Infarct regions were incorporated through a binary value at each mesh element. These regions were defined as follows: first, the intra-ventricular junction and apex of each LV were manually selected from the MR images, which enabled us to define the left anterior descending (LAD) coronary artery territory on each LV. The infarcts had truncated ellipsoidal or spheroidal shapes with arbitrary sizes ranging from 0.5-99.7 ml, whose center points were constrained to be on the endocardial surface and within the LAD territory. This territory was chosen due to its high prevalence [START_REF] Ortiz-Pérez | Correspondence between the 17-segment model and coronary arteryal anatomy using contrast-enhanced cardiac magnetic resonance imaging[END_REF]. The material properties of the infarct were set to be sti↵er compared to the healthy ones, and they were assigned in a uniformlydistributed manner by changing the material parameter C (Eq. 1) from 1 up to 2.50 times of the personalized healthy values. The resulting infarcts have an average myocardial mass of 22.9 ± 21.3 g and an average volume of 21.6 ± 20.1 ml, corresponding to 15.6 ± 13.2% of the myocardium total volume.

Strain-based parameters

Nine strain-based parameters were evaluated in this study (Table 1). Starting from the deformation gradient tensor F extracted from ABAQUS simulations, the right Cauchy stretch tensor C and the Green-Lagrange strain tensor E were calculated: C = F T .F; E = 1 2 (C I ); where I is the identity tensor.

+ 6(E 2 xy + E 2 yz + E 2 xz )]
Fractional anisotropy

q 3 2 ( 1 ) 2 +( 2 ) 2 +( 3 ) 2 2 1 + 2 2 + 2 3 = ( 1 + 2 + 3)/3 1, 2, 3: Eigenvalues of E

Infarct localization

Data alignment. Due to the use of di↵erent geometries, the strain parameters were not directly comparable and spatial correspondence should be obtained. Thus, normalized local coordinates were computed on each geometry corresponding to the pseudoprolate coordinate system explained in Sec. regression with a Gaussian kernel, with a balanced weight between similarity and regularization terms. The interpolation resulted in negligible errors. The whole process is summarized in Fig. 1.

Regression. The aligned strain parameters and infarct location were treated as column vectors of length equal to the number of elements for the reference mesh. The link between each strain parameters and infarct location was learned via kernel ridge regression, inspired by the algorithm described in [START_REF] Duchateau | Infarct localization from myocardial deformation: prediction and uncertainty quantification by regression from a low-dimensional space[END_REF]. Direct regression was preferred over going through an intermediate space of reduced dimensionality, whose purpose is mainly for uncertainty modeling without substantially a↵ecting the localization performance. Each healthy LV geometry was used to generate 40 out of the total 200 pathological cases, which in turn might present some biases in the detection algorithm due to a substantial amount of relatively similar cases, thereby limiting the di↵erence in deformation patterns and in the distribution of the evaluated parameters. To avoid this bias when a case was investigated, all other cases derived from the same geometry were not included in the training set. The training set was randomly constructed from the remaining cases with a certain percentage, which was in the range of 5-40% of the total population. The localization performance of each parameter was then tested against the size of the training set. The limit of 40% was set since it was observed that the algorithm was able to accurately detect the infarcts with this percentage of population as the training set.

The regression output consisted of a non-binary scalar value at each mesh element due to the linear combination of infarct locations. A binary localization of the infarct was obtained after thresholding this output by an appropriate value, as inspired by the two-step process described in [START_REF] Duchateau | Infarct localization from myocardial deformation: prediction and uncertainty quantification by regression from a low-dimensional space[END_REF]: 1) ROC analysis was first performed for each case to obtain a set of best individual thresholds. However, this analysis relies on the ground truth infarct location for each case, which is unrealistic in real-world clinical application, thus 2) the same optimal threshold was applied to all cases, whose values were chosen as the median of the set of the best individual thresholds. Thus, we ended up with a single consensual threshold, which is used in the rest of this paper.

Results

Fig. 2 depicts the infarct localization for pathological cases based on principal strain and sheet-normal invariant, which were observed as one of the best and worst parameters, respectively. The degree of severity of the infarct was based on how much sti↵er it was in comparison to the healthy ones, with respect to the value of the material parameter C. The principal strain is able to localize the infarcts substantially better than the sheet-normal invariant. The infarct localization performance was evaluated in terms of sensitivity and specificity after thresholding the regression output by the consensual value as explained in Sec. 2.3. The results were summarized in terms of the distance to the ideal localization performance, namely a sensitivity and a specificity equal to 1. Fig. 3 summarizes the performance of the nine strain-based parameters, with the color bar depicting the distance to an ideal localization. The horizontal axis represents a combination of the degree of severity and the size of the infarct normalized from 0 to 1, where 0 signifies smaller infarcts and/or infarcts with closer material properties to the healthy ones; whereas the vertical axis represents the percentage of the population included in the training set. Lower values on the color bar signify better accuracy. In addition, the histogram presents the distribution of the number of pathological cases that correspond to each infarct size-severity bin on the horizontal axis. As expected, the localization performance of all parameters increases with bigger and more severe infarcts, as well as with the size of the training set. Based on this, the performance of the evaluated parameters can be divided into three groups. The best group consists of principal strain, e↵ective strain, and fractional anisotropy. The second-best group consists of cross-fiber invariant and radial strain; whereas the last consists of fiber and sheet-normal invariant, circumferential and longitudinal strain.

Discussions

Our study details a novel strategy for evaluating di↵erent strain-based parameters for infarct diagnosis. We combined finite-element modeling to generate a large synthetic database of pathological hearts based on healthy volunteers' data and a state-of-the-art learning algorithm to localize myocardial infarct. Nine strain-based parameters, several of which have yet to be investigated for infarct localization, were evaluated. The large database allowed us to push the algorithm to its limit and thoroughly evaluate the localization performance of each parameter.

The di↵erences between the evaluated parameters were subtle, but we could identify them into three groups. The best group includes the principal strain, e↵ective strain, and fractional anisotropy. Their performances were very similar. The second group shows slightly inferior, yet still good performance. It notably comprises the radial strain, which is readily available in clinical setting. It is interesting that the best parameters are those that are direction-independent, which was somewhat expected as they may be able to better highlight and extract the general distribution of myocardial deformation. However, the invariant in the fiber direction performed worse than the radial strain and the invariant in cross-fiber direction. The reason for this might be due to the boundary conditions applied for the diastolic-filling simulation, which forced the elements to deform radially as the volume of the cavity increases and the incompressibility of the element is enforced. This should be investigated further. In addition, the combination between parameters were not investigated and are also left for future work.

Our synthetic database was derived only from five LV geometries. Although these geometries come from MRI examinations of healthy volunteers -thereby ensuring that the personalized healthy material parameters are physiological -it is of interest in the future to be able to generate a database with larger variability in terms of geometries and subsequently deformation patterns. It is also well known that geometrical alterations of the LV might occur in chronic ischemic patients, i.e. the thickening and thinning of ventricular wall around the remote and infarcted myocardium, respectively. Since our database was derived from healthy volunteers, this e↵ect was not taken into account.

It is certainly essential to evaluate the infarct detection performance of the strain-based parameters on real clinical data of ischemic patients. However, the complexity in acquiring and processing strain data from images with clinical routine quality is still very challenging. Thus, investigation on clinical data is reserved for future studies. Additionally, the exclusion of clinical data allowed us to evaluate the strain-based parameters on a fully-controlled setting. Our study was also limited by the regression approach used for the learning, which relies on a global distance between deformation patterns and linearly combines the infarct candidates. Although the learning algorithm was simply used in our study as a state-of-the-art infarct detection tool to test the performance of the strain-based parameters, further work using di↵erent regression approaches or learning algorithms needs to be explored.

Conclusions

We have proposed a thorough evaluation of various strain-based parameters in locating myocardial infarct. We took advantage of finite-element modeling to generate a large database of pathological hearts and test the limits of a given localization algorithm against a variety of infarct configurations. Although the strain-based parameters only showed slightly di↵erent performance towards locating infarcts, we were able to divide them into three groups, which we showed to be coherent with physiological interpretations.

  2.1. Then, a reference geometry was computed by Procrustes analysis with similarity transformation. Local coordinates were also computed for this reference geometry. Finally, local data (the strain parameters and the infarct binary labels) were transported to the reference geometry using the correspondence of the local coordinates. The data transportation involved interpolation, addressed by ridge

Figure 1 :Figure 2 :

 12 Figure 1: Left: The five LV and the calculated reference. Right: The local normalized pseudoprolate coordinates (radial, circumferential, longitudinal) and the average alignment error due to the interpolation of the local coordinates onto the reference.

Figure 3 :

 3 Figure 3: Performance of the strain-based parameters (median the tested cases). The color bar depicts the distance to an ideal localization. Horizontal axis: a normalized combination of the degree of severity and the size of the infarct. Vertical axis: the percentage of the population used as the training set. The histogram shows the number of cases that correspond to the infarct size-severity measure on the horizontal axis.

Table 1 :

 1 Strain-based parameters evaluated in this study

	Parameters	Formulae / Comments
	Radial strain
	Circ. strain	With respect to pseudoprolate coordinate system
	Long. strain
	Fiber invariant	f0.(Cf0) f0: fiber direction
	Cross-fiber invariant	s0.(Cs0) s0: cross-fiber direction
	Sheet-normal invariant n0.(Cn0) n0: sheet-normal direction
	Principal strain E↵ective strain	The max positive Eigenvalue of E v u u u t 2 9 [(Exx Eyy)

2 + (Eyy Ezz) 2 + (Exx Ezz) 2

http://www.3ds.com/products-services/simulia/products/abaqus/

This a pre-print version. The final document is available at http://www.springerlink.com

Acknowledgement. GK Rumindo is supported by the European Commission H2020 Marie Sklodowska-Curie European Training Network VPH-CaSE (www.vph-case.eu), grant agreement No 642612. This work was performed within the LABEX PRIMES (ANR-11-LABX-0063) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR); and the IMPULSION project from the Programme Avenir Lyon -St. Etienne.


Xavier Allamigeon
email: xavier.allamigeon@inria.fr

Stéphane Gaubert
email: stephane.gaubert@inria.fr

Mateusz Skomra
email: mateusz.skomra@polytechnique.edu

The tropical analogue of the Helton-Nie conjecture is true

Keywords: Convex algebraic geometry, spectrahedra, nonarchimedean fields, tropical geometry, semidefinite programming

Helton and Nie conjectured that every convex semialgebraic set over the field of real numbers can be written as the projection of a spectrahedron. Recently, Scheiderer disproved this conjecture. We show, however, that the following result, which may be thought of as a tropical analogue of this conjecture, is true: 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. The proof relies on game theory methods.

Introduction

Convex semialgebraic sets appear in various guises in computational optimization [START_REF] Blekherman | Semidefinite Optimization and Convex Algebraic Geometry[END_REF]. They include spectrahedra, i.e., feasible sets of semidefinite programs (SDPs). A long-standing problem is to characterize the convex semialgebraic sets that are SDP representable, meaning that they can be represented as the image of a spectrahedron by a (linear) projector. The notion of SDP representability originates from the monograph of [START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF]. [START_REF] Nemirovski | Advances in convex optimization: conic programming[END_REF] asked whether every convex semialgebraic set is SDP representable. Helton and Nie conjectured that the answer is positive.

Conjecture 1 [START_REF] Helton | Sufficient and necessary conditions for semidefinite representability of convex hulls and sets[END_REF]. Every convex semialgebraic set in R n is a projection of a spectrahedron.

Several classes of convex semialgebraic sets for which the answer is positive have been identified [START_REF] Helton | Sufficient and necessary conditions for semidefinite representability of convex hulls and sets[END_REF][START_REF] Helton | Linear matrix inequality representation of sets[END_REF][START_REF] Helton | Semidefinite representation of convex sets[END_REF][START_REF] Lasserre | Convex sets with semidefinite representation[END_REF][START_REF] Gouveia | Theta bodies for polynomial ideals[END_REF][START_REF] Gouveia | Positive polynomials and projections of spectrahedra[END_REF][START_REF] Nie | Semidefinite representation of the k-ellipse[END_REF]. In particular, it is known that the conjecture is true in dimension 2 (Scheiderer, 2018a). The conjecture has been recently disproved by Scheiderer (2018b), who showed that the cone of positive semidefinite forms cannot be expressed as a projection of spectrahedra, except in some particular cases. A comprehensive list of references can be found in this work.

Theorem 2 (Scheiderer, 2018b). The cone of positive semidefinite forms of degree 2d in n variables can be expressed as a projection of a spectrahedron only when 2d = 2 or n 2 or (n, 2d) = (3, 4).

The notion of convex and semialgebraic sets make sense over any real closed field, in particular over the nonarchimedean field K of real Puiseux series, equipped with the total order induced by its nonnegative cone K 0 , consisting of series with a nonnegative leading coefficient. Our main result shows that the next statement, which may be thought of as a "Helton-Nie conjecture for valuations," is valid.

Theorem 3. The image by the valuation of every convex semialgebraic subset of K n coincides with the image by the valuation of a projected spectrahedron over K.

Our approach relies on tropical methods. Tropical semialgebraic sets can be defined as the images by the nonarchimedean valuation of semialgebraic sets over K. The quantifier elimination techniques in real valued fields developed by [START_REF] Pas | Uniform p-adic cell decomposition and local zeta functions[END_REF], building on work of [START_REF] Denef | p-adic semi-algebraic sets and cell decomposition[END_REF], imply that tropical semialgebraic sets are semilinear. Moreover, the image by the nonarchimedean valuation of a convex set over K is a tropical convex set, i.e., a set stable by taking tropical convex combinations. In a previous work [START_REF] Allamigeon | Tropical spectrahedra[END_REF] we studied tropical spectrahedra, defined as the images by the nonarchimedean valuation of spectrahedra over K, and gave a combinatorial characterization of generic tropical spectrahedra.

The proof relies on the recently developed relations between tropical convex programming and zero-sum games [START_REF] Akian | Tropical polyhedra are equivalent to mean payoff games[END_REF]Allamigeon et al., 2018b). In particular, in the latter reference, we demonstrated a class of generic tropical spectrahedra that corresponds precisely to the sets of subharmonic vectors (subfixed points) of a class of nonlinear Markov operators (Shapley operators of stochastic mean payoff games). In that way, one obtains an explicit construction for these tropical spectrahedra.

The tropical perspective proved to be useful to find counterexamples to classical conjectures in real algebraic geometry. For instance, [START_REF] Itenberg | Patchworking algebraic curves disproves the Ragsdale conjecture[END_REF] disproved the Ragsdale conjecture as an application of the tropical patchworking method. More recently, Allamigeon et al. (2018a) contradicted, by a tropical method, the continuous analogue of the Hirsch conjecture proposed by [START_REF] Deza | Polytopes and arrangements: diameter and curvature[END_REF]. The validity of the tropical analogue of the Helton-Nie conjecture raises the question whether a counterexample could be found by a tropical approach, for instance, by studying images of convex semialgebraic sets and spectrahedra through a map carrying more information than the valuation.

We finally note that semilinear sets that are tropically convex have been studied recently by [START_REF] Bodirsky | Max-closed semilinear constraint satisfaction[END_REF] from a different perspective, motivated by a class of satisfiability problems. They showed in particular that feasibility and infeasibility certificates for these problems can be obtained from stochastic games. The tropical convex sets they consider differ from ours in two respects: the -∞ element is not allowed in their approach, whereas it appears as the image of the zero element by the nonarchimedean valuation; moreover, the tropicalizations of convex semialgebraic sets are always closed, and so, definable by weak inequalities, whereas systems including both strict and weak inequalities are considered in [START_REF] Bodirsky | Max-closed semilinear constraint satisfaction[END_REF].

Preliminaries

Puiseux series and tropical algebra

A (generalized formal real) Puiseux series is a formal series of the form

x = ∞ i=1 c λ i t λ i , ( 1
)
where t is a formal parameter, (λ i ) i 1 is a strictly decreasing sequence of real numbers that is either finite or unbounded, and c λ i ∈ R \ {0} for all λ i . There is also a special, empty series, which is denoted by 0. The Puiseux series can be added and multiplied in the natural way. They form a real closed field [START_REF] Markwig | A field of generalized Puiseux series for tropical geometry[END_REF], which we denote here by K. If x is a Puiseux series as in (1), then by lc(x) we denote its leading coefficient, lc(x) = c 1 (with the convention that lc(0) = 0). The (unique) total order on K is given by the relation x y ⇐⇒ lc(x -y) 0. The field of Puiseux series is equipped with a (nonarchimedean) valuation val : 1), then we define val(x) as the leading exponent of x, val(x) = λ 1 (with the convention that val(0) = -∞). It follows from the definition that we have the relations val(x + y) max(val(x), val(y))

K → R ∪ {-∞}. If x ∈ K is as in (
(2) val(xy) = val(x) + val(y)

(3)

0 x y =⇒ val(x) val(y) (4)
Furthermore, the inequality in (2) becomes an equality when the leading terms of x and y do not cancel, which is the case if val(x) val(y) or if x, y 0. We denote by K 0 the set of nonnegative Puiseux series (the series which fulfill the inequality x 0). Remark 4. We chose the specific field K for simplicity of exposition. Actually, a quantifier elimination argument allows one to deduce that our main results stated over K are also valid over other real closed nonarchimedean fields, see Remark 43.

Tropical semifield

The tropical semifield T describes the algebraic structure of K under the valuation map. The underlying set of T is defined as T R ∪ {-∞}, the tropical addition is defined as x ⊕ y = max(x, y), and the tropical multiplication is defined as x y = x + y. The structure T constitutes only a semifield, for the tropical addition does not have an inverse operation. We use the notation

n i=1 a i = a 1 ⊕ • • • ⊕ a n and a n = a • • • a (n times).
We also endow T with the standard order . The properties (2)-(4) imply that val is an order-preserving morphism of semifields from K 0 to T.

When dealing with semialgebraic sets, it is convenient to keep track not only of the valuations of the elements of K, but also of their signs. To this end, we introduce the sign function sign : K → {-1, 0, +1} defined as sign(x) = 1 if x > 0, sign(x) = -1 if x < 0, and sign(0) = 0. The set of signed tropical numbers is then defined as Here, is a formal symbol. Note that we can extend the definition of tropical multiplication to T ± using the usual rules for signs (e.g., we have ( 3) 7 = 10 and ( 3) ( 7) = 10). However, we only partially extend the tropical addition to the elements of T ± which have the same sign (e.g., we have 3 ⊕ 7 = 7 and ( 3) ⊕ ( 7) = 7, but ( 3) ⊕ 7 is not defined). One can extend the set T ± even further to get a semiring with a well-defined tropical addition [START_REF] Akian | Linear independence over tropical semirings and beyond[END_REF], or work with hyperfields [START_REF] Viro | Hyperfields for tropical geometry I. Hyperfields and dequantization[END_REF][START_REF] Connes | The hyperring of adèle classes[END_REF] instead of semifields, but we do not need that here. Furthermore, note that the tropical semiring T is isomorphic to T + ∪ {-∞}.

T ± ({+1, -1} × R) ∪ {(0, -∞)},
A tropical (signed) polynomial over the variables X 1 , . . . , X n is a formal expression of the form

P(X) = α∈Λ a α X α 1 1 • • • X α n n , (5)
where Λ ⊂ {0, 1, 2, . . . } n , and a α ∈ T ± \ {-∞} for all α ∈ Λ. If P is given as in (5), we define P + (resp. P -) as the tropical polynomial generated by the terms

|a α | X α 1 1 . . . X α n n
where a α ∈ T + (resp. T -). Note that the quantities P + (x) and P -(x) are well defined for all x ∈ T n , because the tropical polynomials P + and P -have only tropically positive coefficients.

We extend the functions val and sval to vectors and matrices by applying them coordinatewise.

Tropical convexity

In this section, we recall some basic facts about convexity in the usual and tropical sense. A set X ⊂ K n is called convex if for every x, y ∈ X and every λ ∈ K such that 0 λ 1 we have λ + (1 -λ)y ∈ X. Since the intersection of any number of convex sets in convex, for every set X ⊂ K n we can define its convex hull (denoted conv(X)) as the smallest (inclusionwise) convex set that contains X. This set is characterized by Carathéodory's theorem.

Theorem 5. If X ⊂ K n , then we have the equality

conv(X) = n+1 k=1 λ k x k ∈ K n : ∀k, x k ∈ X ∧ ∀k, λ 0 ∧ n+1 k=1 λ k = 1 .
We refer to (Schrijver, 1987, Corollary 7.1j) for a proof of Theorem 5 that is valid over every ordered field.

Let us now move to tropical convexity, referring the reader to [START_REF] Cohen | Duality and separation theorems in idempotent semimodules[END_REF][START_REF] Develin | Tropical convexity[END_REF] for background. We say that a set X ⊂ T n is tropically convex if for every x, y ∈ X and every λ, µ ∈ T such that λ ⊕ µ = 0 the point (λ x) ⊕ (µ y) belongs to X. The latter quantity corresponds to the tropical analogue of a convex combination of x and y. Indeed, the scalars λ and µ are implicitly "nonnegative" in the tropical sense, as they are greater than or equal to the tropical zero element -∞. Besides, their tropical sum equals the tropical unit 0. The intersection of any number of tropically convex sets is tropically convex. Hence, for any set X ⊂ T n we can define its tropical convex hull (denoted tconv(X)) as the smallest (inclusionwise) tropically convex set that contains X. Alternatively, one may work with a tropical (convex) cone X, defined by requiring (λ x)⊕(µ y) ∈ X for all λ, µ ∈ T. Tropical convex sets can be identified to cross sections of tropical convex cones [START_REF] Cohen | Duality and separation theorems in idempotent semimodules[END_REF]). Carathéodory's theorem is still true in the tropical setting:

Theorem 6 [START_REF] Helbig | On Carathéodory's and Kreȋn-Milman's theorems in fully ordered groups[END_REF], [START_REF] Briec | B-convexity[END_REF], [START_REF] Develin | Tropical convexity[END_REF]). If X ⊂ T n , then we have the equality

tconv(X) = n+1 k=1 (λ k x k ) : ∀k, x k ∈ X ∧ n+1 k=1 λ k = 0 .
A relation between the convexity in K and the tropical convexity is shown in the next two lemmas.

Lemma 7. If X ⊂ K n is a convex set, then val(X) is tropically convex.

Proof. Let x, y ∈ val(X) and take any λ, µ ∈ T such that λ ⊕ µ = 0. Without loss of generality, suppose that λ = 0. Take any points x ∈ X ∩ val -1 (x) and y ∈ X ∩ val -1 (y). Let us look at two cases. If µ < 0, then for any real positive constant c, we have 1ct µ > 0, and so the point z = (1ct µ )x + ct µ y belongs to X. We already noted that the equality holds in the inequality (2) if the leading terms do not cancel. Hence, choosing c such that clc(x k )/ lc(y k ) for all k ∈ [n] satisfying y k 0, we deduce that val(z) = (λ x) ⊕ (µ y). If µ = 0, then we take now a real constant c ∈ (0, 1) such that for all k ∈ [n] satisfying y k 0 we have c/(1c)lc(x k )/ lc(y k ). Then, the point z = (1c)x + cy belongs to X and we deduce as above that val(z) = (λ x) ⊕ (µ y).

The next lemma shows that a tighter relation holds for sets included in the nonnegative orthant of K.

Lemma 8. If X ⊂ K n 0 is any set, then we have val(conv(X)) = tconv(val(X)). Proof. We start by proving the inclusion ⊂. Take a point y ∈ conv(X). By Theorem 5, there exist λ 1 , . . . , λ n+1 0 and x 1 , . . . , x n+1 ∈ X such that y = λ 1 x 1 + • • • + λ n+1 x n+1 . Hence, by (2) and (3) (and using the fact that X ⊂ K n 0 ) we have val(y) = val(λ 1 ) val(x 1 ) ⊕ . . . ⊕ val(λ n+1 ) val(x n+1 ) .

Furthermore, we have n+1 k=1 λ k = 1 and hence n+1 k=1 val(λ k ) = 0. Therefore, val(y) ∈ tconv(X) by Theorem 6. Conversely, take any point y ∈ tconv(X). By Theorem 6, there exist λ 1 , . . . , λ n+1 ∈ T, n+1 k=1 λ k = 0 and x 1 , . . . , x n+1 ∈ X such that y = (λ 1 x 1 ) ⊕ . . . (λ n+1 x n+1 ). We define

λ k t λ k /( n+1 l=1 t λ l ).
Observe that for all k, val(λ k ) = λ k because the term n+1 l=1 t λ l has valuation n+1 l=1 λ l = 0. Moreover, we have λ k 0 and n+1 k=1 λ k = 1. Let x 1 , . . . , x n+1 be any points of X such that val(x i ) = x i . Then, the point y = λ 1 x 1 + • • • + λ n+1 x n+1 belongs to conv(X) and verifies val(y) = y.

We also need the following lemma.

Lemma 9. Suppose that sets X, Y ⊂ T n are tropically convex. Then we have the equality

tconv(X ∪ Y) = {(λ x) ⊕ (µ y) ∈ T n : x ∈ X, y ∈ Y, λ ⊕ µ = 0} .
Proof. The inclusion ⊃ follows immediately from the definition of tropical convex hull. The other inclusion holds because the set on the right-hand side contains X and Y and is tropically convex.

Tropicalization of convex semialgebraic sets

A set S ⊂ K n is called basic semialgebraic if it is of the form {x ∈ K n : ∀i = 1, . . . , p, P i (x) > 0 ∧ ∀i = p + 1, . . . , q, P i (x) = 0} , (6)
where

P i ∈ K[X 1 , . . . , X n ] are polynomials. A set S ⊂ K n is called semialgebraic if it is a finite
union of basic semialgebraic sets. In this section, we characterize the sets that arise as images by valuation of convex semialgebraic sets.

Lemma 10. If S ⊂ K n is a semialgebraic set, then conv(S) is also semialgebraic.

Proof. This is an immediate consequence of Theorem 5 and of the quantifier elimination in real closed fields (Marker, 2002, Theorem 3.3.15).

Let us make the following definition.

Definition 11. We say that a set S ⊂ T n is a tropicalization of a convex semialgebraic set if there exists a convex semialgebraic set S ⊂ K n such that val(S) = S.

Given d 1, the support of a point y ∈ T d is defined as the set of indices k ∈ [d] such that y k -∞. Given a nonempty subset K ⊂ [d],
and a set Y ⊂ T d , we define the stratum of Y associated with K as the subset of R K formed by the projection (y k ) k∈K of the points y ∈ Y with support K. The stratum associated with the set [d] is referred to as the main stratum.

We say that a set S ⊂ R d is a basic semilinear set if it is a relatively open polyhedron of the

form {x ∈ R d : ∀i = 1, . . . , p, A i , x > b i ∧ ∀i = p + 1, . . . , q, A i , x = b i } ,
where the matrix A ∈ Q q×d is rational, the vector b ∈ R q is real, and •, • denotes the standard scalar product in R d . We say that a set is semilinear if it is a finite union of basic semilinear sets. Note that S ⊂ R d is a closed semilinear set if and only if it is a finite union of polyhedra of the form Ax b, where the matrix A ∈ Q q×d is rational and the vector b ∈ R q is real. The following proposition characterizes the tropicalizations of convex semialgebraic sets. This result is based on the Denef-Pas quantifier elimination in the theory on real closed valued fields.

Proposition 12. A set S ⊂ T n is a tropicalization of a convex semialgebraic set if and only if S is tropically convex and every stratum of S is a closed semilinear set.

Proof. The "only if" part follows from [START_REF] Allamigeon | Tropical spectrahedra[END_REF], Theorems 4 and 10) and Lemma 7. To prove the opposite implication, suppose that S is tropically convex and has closed semilinear strata. Therefore, it is a finite union of sets of the form

W = {x ∈ T n : Ax K b, x [n]\K = -∞}, where, for every L ⊂ [n],
x L denotes the vector formed by the coordinates of x taken from L, the matrix A ∈ Q m×|K| is rational and the vector b ∈ R m is real. Take any such set W and consider the set

W {x ∈ K n 0 : ∀i ∈ [m], k∈K x A ik k t b i ∧ x [n]\K = 0} .
Note that W is semialgebraic. Moreover, by ( 2)-( 4) we have val(W) ⊂ W. Furthermore, if

x ∈ W, and we take x k t x k for all k ∈ [n] (with the convention that t -∞ = 0), then we have x ∈ W. Therefore val(W) = W. Let U denote the union of all sets W that arise in this way. We have val(U ) = S and U is semialgebraic. Thus, if we take S conv(U ), then S is convex and semialgebraic by Lemma 10. Moreover, Lemma 8 shows that val(S) = S.

Tropical Metzler spectrahedra

Let us recall that a real symmetric matrix is positive semidefinite if it admits a Cholesky decomposition. This is equivalent to the nonnegativity of its principal minors, its smallest eigenvalue, and the associated quadratic form. All of these properties are still equivalent for symmetric matrices defined over arbitrary real closed fields, such as Puiseux series (this is a consequence of the completeness of the theory of such fields, see Marker, 2002, Corollary 3.3.16). This implies that the definition of a spectrahedron is valid over K.

Definition 13. Suppose that Q (0) , . . . , Q (n) ∈ K m×m are symmetric matrices. Then, the spectrahedron associated with these matrices is defined as

S = {x ∈ K n : Q (0) + x 1 Q (1) + • • • + x n Q (n) 0} ,
where the symbol denotes the Loewner order on symmetric matrices. (By definition, X Y if X -Y is positive semidefinite.)

In our previous works [START_REF] Allamigeon | Tropical spectrahedra[END_REF](Allamigeon et al., , 2018b) ) we introduced the notion of tropical spectrahedra and a special subclass of these objects called tropical Metzler spectrahedra. The latter have a simpler combinatorial description; moreover, any generic tropical spectrahedron can be represented by a boolean combination of tropical Metzler spectrahedra (Allamigeon et al., 2016, Sections 5.3-5.4). Tropical spectrahedra are defined as follows.

Definition 14. We say that a set S ⊂ T n is a tropical spectrahedron if there exists a spectrahedron S ⊂ K n 0 such that S = val(S). A square matrix M is called a (negated) Metzler matrix if its off-diagonal entries are nonpositive. Similarly, a matrix M ∈ T m×m ± is called a tropical Metzler matrix if its off-diagonal entries belong to T -∪ {-∞}. Fix a sequence of symmetric tropical Metzler matrices Q (0) , . . . , Q (n) ∈ T m×m ± . For every pair (i, j) ∈ [m] 2 we consider the tropical polynomial Q i j (X) defined as

Q i j (X) Q (0) i j ⊕ (Q (1) i j X 1 ) ⊕ . . . ⊕ (Q (n) i j X n ) .
Definition 15. The tropical Metzler spectrahedron described by

Q (0) , . . . , Q (n) ∈ T m×m ± , denoted S(Q (0) |Q (1) , . . . , Q (n) )
, is the set of all points x ∈ T n which satisfy the following two conditions:

• Q + ii (x) Q - ii (x) for every i ∈ [m] • Q + ii (x) Q + j j (x) (Q i j (x)) 2 for every i, j ∈ [m] 2 , i j. Note that the function Q i j (x) is well-defined for all x ∈ T n because every Q (k) is a tropical Metzler matrix. If the matrix Q (0) is equal to -∞, then we say that S(-∞|Q (1) , . . . , Q (n) ) is a tropical Metzler spectrahedral cone. We say that a tropical Metzler spectrahedron S(Q (0) |Q (1) , . . . , Q (n) ) is real if it is included in R n .
Remark 16. The definition above differs slightly from the one of [START_REF] Allamigeon | Tropical spectrahedra[END_REF](Allamigeon et al., , 2018b)). Indeed, in these references it was enough to work with tropical Metzler spectrahedral cones, while the use of affine tropical spectrahedra is indispensable in the context of the Helton-Nie conjecture. The connection between the two notions is given in (Allamigeon et al., 2016, Lemma 20).

The name "tropical Metzler spectrahedron" is justified by the fact that these sets are indeed tropical spectrahedra, as shown in (Allamigeon et al., 2016, Proposition 23 and Lemma 20).

Proposition 17. Every tropical Metzler spectrahedron is a tropical spectrahedron.

The tropical analogue of the Helton-Nie conjecture

As stated in the introduction, Scheiderer (2018b) has shown that the cone of positive semidefinite forms over R is a counterexample to the Helton-Nie conjecture. We first note that this yields a counterexample to the analogue of this conjecture over Puiseux series.

Corollary 18 (of Scheiderer, 2018b, Corollary 4.25). The cone of positive semidefinite forms of degree 2d in n variables over K can be expressed as a projection of a spectrahedron over K only when 2d = 2 or n 2 or (n, 2d) = (3, 4).

Proof. Consider a real closed field K, and integers d, m, n, and p. The statement "the cone of positive semidefinite forms of degree 2d in n variables over K is the projection of a spectrahedron in K p associated with matrices of size m × m" is a sentence in the language of ordered rings. Since the theory of real closed fields is complete (Marker, 2002, Corollary 3.3.16), this sentence is true over R if and only if it is true over K.

We next state the main result of this paper. We shall prove a special case of this result in Section 4, and derive the general case in Section 5. We point out that Theorem 3 is a corollary of Theorem 19.

Proof of Theorem 3. Let S ⊂ K n be any convex semialgebraic set and let S val(S) ⊂ T n . By Theorem 19, the set S ⊂ T n is a projection of a tropical Metzler spectrahedron. In other words, there exists n 0 and a tropical Metzler spectrahedron S ⊂ T n+n such that π(S) = S, where π : T n+n → T n denotes the projection on the first n coordinates. By Proposition 17, there is a spectrahedron S ⊂ K n+n 0 such that val(S ) = S. Let π : K n+n → K n denote the projection on the first n coordinates. Then val(π(S )) = π(val(S )) = π(S) = S = val(S).

Tropical Helton-Nie conjecture for real tropical cones

In this section, we show that the tropical analogue of Helton-Nie conjecture is true for real tropical cones. We say that a set X ⊂ R n is a real tropical cone if for every x, y ∈ X and every λ, µ ∈ R we have (λ x) ⊕ (µ y) ∈ X. A real tropical cone is nothing but the main stratum of a tropical cone as defined in Section 2.3. Indeed, if Y is a tropical cone, then Y ∩ R n is a real tropical cone, whereas if X is a real tropical cone, then X ∪ {-∞} is a tropical cone.

Preliminaries on semilinear monotone homogeneous operators

A function F : R n → R m is said to be piecewise affine if there exist full-dimensional polyhedra W (1) , . . . , W (p) ⊂ R n satisfying ∪ p s=1 W (s) = R n and such that the restriction of F to W (s) is affine, i.e., F |W (s) (x) = A (s) x+b (s) for some matrix A (s) ∈ R m×n and vector b (s) ∈ R m . In particular, piecewise affine functions are continuous (since the polyhedra W (1) , . . . , W (p) are closed). We shall say that the family (W (s) , A (s) , b (s) ) s is a piecewise description of the function F.

We recall the following minimax representation result proved by [START_REF] Ovchinnikov | Max-min representations of piecewise linear functions[END_REF], in which we denote F(x) = (F 1 (x), . . . , F m (x)).

Theorem 20 [START_REF] Ovchinnikov | Max-min representations of piecewise linear functions[END_REF]. Suppose that the function F : R n → R m is piecewise affine, and let (W (s) , A (s) , b (s) ) s∈[p] be a piecewise description of F. Then, for every k ∈ [n] there exists a number M k 1 and a family

{S ki } i∈[M k ] of subsets of [p] such that for all x ∈ R n we have F k (x) = min i∈[M k ] max s∈S ki (A (s) k x + b (s) k ) .
We say that a function F : R n → R m is semilinear if its graph {(x, y) ∈ R n×m : y = F(x)} is a semilinear set. The next lemma shows that continuous semilinear functions are piecewise affine.

Lemma 21. Suppose that the continuous function F : R n → R m is semilinear. Then, it is piecewise affine. Moreover, it admits a piecewise description (W (s) , A (s) , b (s) ) s∈ [p] such that the polyhedra W (s) are semilinear, and the matrices A (s) are rational.

Proof. Since F is continuous and semilinear, the graph of F is a closed semilinear set. Therefore, it is a finite union of semilinear polyhedra. Let {(x, y) : Bx+Cy d}, where B ∈ Q p×n , C ∈ Q p×m , d ∈ R p be one of these polyhedra. If we fix x, then, by the definition of a graph, the polyhedron consisting of all y such that Cy d -Bx reduces to a point y. Thus, there exists an invertible submatrix

C I ∈ Q m×m of C such that y = C -1 I (d I -B I x) = C -1 I d I -C -1 I B I x.
In other words, the graph of F is a finite union of polyhedra of the form

W = {(x, y) : Bx + Cy d, y = C -1 I d I -C -1 I B I x} ,
where C I is an invertible submatrix of C. As a result, if π : R n+m → R n denotes the projection on the first n coordinates, and x ∈ π(W) is any point, then we have

F(x) = C -1 I d I -C -1 I B I x.
By eliminating the polyhedra π(W) that are not full dimensional, we obtain a piecewise description of F satisfying the expected requirements.

We say that a selfmap F : R n → R n is monotone if F(x) F(y) as soon as x y, where denotes the coordinatewise partial order over R n . Such a function is said to be (additively) homogeneous if F(λ + x) = λ + F(x) for all λ ∈ R and x ∈ R n . Here, if z ∈ R n , then λ + z stands for the vector with entries λ + z k .

The following observation is well known [START_REF] Crandall | Some relations between nonexpansive and order preserving mappings[END_REF].

Lemma 22. Every monotone homogeneous operator is nonexpansive in the supremum norm.

Proof. Observe that x x-y +y. Therefore, we get F(x) F( x-y +y) = x-y + F(y). [START_REF] Kolokoltsov | On linear, additive, and homogeneous operators in idempotent analysis[END_REF] showed that every monotone homogeneous operator F has a minimax representation as a dynamic programming operator of a zero-sum game. When F is semilinear, the following result shows that we have a finite representation of the same nature.

Lemma 23. If F : R n → R n is semilinear, monotone, and homogeneous, then it can be written in the form

∀k, F k (x) = min i∈[M k ] max s∈S ki (A (s) k x + b (s) k ) , (7)
where A (1) , . . . ,

A (p) ∈ Q n×n is a sequence of stochastic matrices, b (s) ∈ R n for all s ∈ [n], M k 1 for all k ∈ [n], and S ki is a subset of [p] for every k ∈ [n] and i ∈ [M k ].
Proof. Lemma 22 shows that F is continuous. Let (W (s) , A (s) , b (s) ) s∈[p] a piecewise description of F as provided by Lemma 21. In particular, every matrix A (s) is rational. We want to show that it is stochastic. To this end, take any x ∈ int(W s ). Let y be the sum of the columns of A (s) . Since F is homogeneous, for any ρ > 0 small enough we have F(ρ+ x) = A (s) x+b (s) +ρy = ρ+F(x). In other words, the sum of every line of A (s) is equal to 1. Let k denote the kth vector of standard basis in R n . Since F is monotone, for ρ > 0 small enough we have

F(x + ρ k ) = A (s) x + b (s) + ρA (s) k F(x).
In other words, the matrix A (s) has nonnegative entries in its kth column. Since k was arbitrary, A (s) is stochastic. Therefore, the claim follows from Theorem 20.

We now characterize the class of closed semilinear real tropical cones. To this end, we use the model-theoretic definition of semilinear sets. Let L og (0, +, ) denote the language of ordered groups. Then, the elimination of quantifiers in divisible ordered abelian groups (Marker, 2002, Theorem 3.1.17), shows that a set S ⊂ R n is semilinear if and only if there exists a number m 0, an L og -formula ψ(x 1 , . . . , x n+m ), and a vector b ∈ R m such that

S = {x ∈ R n : ψ(x 1 , . . . , x n , b) is true in R} .
Proposition 24. A set S ⊂ R n is a closed semilinear real tropical cone if and only if there exists a semilinear monotone homogeneous operator F : R n → R n such that S = {x ∈ R n : x F(x)}.

Proof. To prove the first implication, we consider two cases. If S is empty, then we take F(x) =

x -(1, . . . , 1). Otherwise, we define F by F k (x) sup{y k : y ∈ S , y x} for all k ∈ [n]. We claim that every supremum is attained. Indeed, the set {y ∈ S : y x} is nonempty (take an arbitrary z ∈ S, and consider λ + z for λ ∈ R small enough), closed, and bounded by x. Let y (k) ∈ S attaining the maximum in F k (x). Then the point y (1) ⊕ . . . ⊕ y (n) is an element of S smaller than or equal to x. We deduce that it coincides with F(x). Subsequently, F(x) belongs to S.

The operator F is semilinear because the supremum is definable in the language L og , and S is semilinear. Besides, F is obviously monotone. It is also homogeneous because if y ∈ S, then λ + y ∈ S for all λ ∈ R. Finally, the inclusion S ⊂ {x ∈ R n : x F(x)} is straightforward, while the inverse inclusion follows from the fact that if x F(x), then x = F(x).

Conversely, fix a semilinear monotone homogeneous operator F and take the set S = {x ∈ R n : x F(x)}. This set is semilinear. Moreover, S is closed because F is continuous. To prove that this is an real tropical cone, fix a pair λ, µ ∈ R and x, y ∈ S. Since F is monotone and homogeneous, we have F(max{λ + x, µ + y}) F(λ + x) = λ + F(x) λ + x and similarly F(max{λ + x, µ + y}) µ + y. Hence max{λ + x, µ + y} ∈ S.

Remark 25. One could ask if there is a more direct way to obtain a piecewise description of the operator F given a real tropical cone S (without the use of model theory). This can be done in the following way. We first decompose S = p s=1 {x ∈ R n : A (s) x b (s) } where the matrix A (s) has rational entries, and b (s) is a real vector. Then, given x ∈ R n we denote by P(x) ⊂ [p] the set of all s ∈ [p] such that the polyhedron {y : A (s) y b (s) , y x} is nonempty. By the strong duality of linear programming (and the fact that F(x) is well defined for all x ∈ R n ) we have

F k (x) = max s∈P(x) max{y k : A (s) y b (s) , y x} = max s∈P(x) min{z b (s) + w x : (A (s) ) z + w = k , z 0, w 0} .
For every s ∈ [p], let V (s) k denote the set of vertices of the rational polyhedron {(z, w) : (A (s) ) z + w = k , z 0, w 0}. Hence

F k (x) = max s∈P(x) min (z,w)∈V (s) k {z b (s) + w x} . (8)
Moreover, by Farkas' Lemma, the polyhedron {y : A (s) y b (s) , y x} is nonempty if and only if for all (z, w) such that (A (s) ) z + w = 0, z 0, w 0, we have z b (s) + w x 0. If U (s) consists of precisely one representative of every extreme ray of the rational cone {(z, w) : (A (s) ) z + w = 0, z 0, w 0}, this amounts to the finite system of linear inequalities z b (s) + w x 0 for all (z, w) ∈ U (s) . The inequalities of this form yield an arrangement of hyperplanes, and the value of P(x) is constant when x varies in the relative interior of any cell of this arrangement. By fixing the terms achieving the maximum and minimum in (8) we refine the latter arrangement in such a way that F is affine on every cell of the refinement. Since F is continuous (by Lemma 22), we can then restrict ourselves to those of these cells that are full dimensional, and this gives the piecewise description of F.

Example 26. We illustrate our results on the following example. Take n = 3, p = 2, M k = 1, S k,1 = {1, 2} for all k ∈ {1, 2, 3},

A (1) =           0 0 1 1/4 0 3/4 1 0 0           b (1) =           1 3/4 0           , A (2) =           0 1/3 2/3 0 0 1 0 1 0           b (2) =           4/3 2π 0           .
Then, the operator F : R 3 → R 3 is given by

F 1 (x) = max x 3 + 1, 1 3 x 2 + 2 3 x 3 + 4 3 , F 2 (x) = max 1 4 x 1 + 3 4 x 3 + 3 4 , x 3 + 2π , F 3 (x) = max{x 1 , x 2 } .
The real tropical cone {x ∈ R 3 : x F(x)} is depicted in Fig. 1.

Description of real tropical cones by directed graphs

We now describe how semilinear monotone homogeneous operators can be encoded by directed graphs. To this end we take a directed graph G (V, E), where the set of vertices is divided into Max vertices, Min vertices, and Random vertices, i.e., V V Min V Rand V Max , where the symbol denotes the disjoint union of sets. We suppose that the sets of Max vertices and Min vertices are nonempty. If v ∈ V is a vertex of G, then by In(v) := {(w, v) : (w, v) ∈ E} we denote the set of its incoming edges, and by Out(v) := {(v, w) : (v, w) ∈ E} we denote the set of its outgoing edges. We suppose that the every vertex has at least one outgoing edge. If v is a Min vertex or a Max vertex and e ∈ Out(v) is its outgoing edge, then we equip this edge with a real number r e . Furthermore, if v is a Random vertex, then we equip its set of outgoing edges with a rational probability distribution. More precisely, every edge e ∈ Out(v) is equipped with a strictly positive rational number q e ∈ Q, q e > 0, and we suppose that e∈Out(v) q e = 1. We also make the following assumptions: Assumption 27.

(i) Every path between any two Min vertices contains at least one Max vertex;

(ii) Every path between any two Max vertices contains at least one Min vertex;

(iii) From every Random vertex, there is a path to a Min or a Max vertex.

We now construct a semilinear monotone homogeneous operator from such a graph. We define a Markov chain with state space V, and transition probabilities p vv 1 for all v ∈ V Max V Min , p vw q (v,w) if v ∈ V Rand and (v, w) ∈ Out(v), and p vw 0 otherwise. Therefore, every state of V Max V Min is absorbing, and a trajectory of the Markov chain visits the states of V Rand by picking at random, for each vertex v ∈ V Rand , one edge in Out(v) according to the probability law given by q (v,•) , until it reaches a state of V Max V Min . In this way, after leaving a Min vertex, the trajectory reaches a Max vertex, and vice versa. If e is an edge and v is a Max or Min vertex, then we denote by p e v the conditional probability to reach the absorbing state v from the head of e. Note that every p e v is rational since we have assumed that the q e are in Q (Kemeny and Snell, 1976, Theorem 3.3.7). For the sake of simplicity, we assume that (v). We claim that if u ∈ [n] is a Min state, then p e u = 0. Indeed, by Assumption 27 (i), any path from the head of e to u in G contains a Max vertex. As a consequence, there is no path from the head of e to u in the subgraph in which we have removed the edges going out of the Max and Min vertices. We deduce that for every Min vertex v and edge e ∈ Out(v), we have w∈[m] p e w = 1. Analogously, we can show that for all Max vertices w and edge e ∈ Out(w), u∈[n] p e u = 1. We deduce that the operator F is homogeneous.

V Min = [n] and V Max = [m].
In the following lemma, we show that any semilinear monotone homogeneous operator is encoded by some digraph: Lemma 30. Let F : R n → R n be a semilinear monotone homogeneous operator. Then, there exists a directed graph G satisfying Assumption 27 such that F is encoded by G.

Proof. The idea is to identify the representation (7) to a special case of (9), in which the probabilities p e w with e ∈ Out(v) and v ∈ V Min take only the values 0 and 1. Formally, let A (1) , . . . , A (p) ∈ Q n×n and b (1) , . . . , b (p) ∈ R n such that Lemma 23 holds. We build G as the graph in which the set of Min vertices is [n], the set of Max vertices is k [M k ], and the set of Random vertices is

k∈[n], i∈[M k ] S ki .
Let k be a Min vertex. We add an edge (k, i) for every i ∈ [M k ], with r (k,i) 0. Moreover, for every i ∈ [M k ], we add an edge (i, s) for each s ∈ S ki , with r (i,s) b (s) k . Finally, if i ∈ [M k ] and s ∈ S ki , we add an edge (s, l) with q (s,l)

A (s) kl for every l ∈ [n] such that A (s) kl > 0. The requirements of Assumption 27 are straightforwardly satisfied.

Example 31. The graph presented in Fig. 2 encodes the operator from Example 26.

Construction of tropical Metzler spectrahedra

The following proposition characterizes the semilinear monotone homogeneous operators associated with tropical Metzler spectrahedral cones. We discussed this family of operators in our previous work (Allamigeon et al., 2018b), where we interpreted them as the dynamic programming operators of a zero-sum game.

Proposition 32. Suppose that the graph G fulfills Assumption 27 and has the following properties:

• every Random vertex has exactly two outgoing edges and the probability distribution associated with these edges is equal to (1/2, 1/2) 13 • every edge outgoing from a Random vertex has a Max vertex as its head.

Let F denote the semilinear monotone homogeneous operator encoded by G. Then, the set {x ∈ T n : x F(x)} is a tropical Metzler spectrahedral cone.

Proof. Consider the Markov chain introduced before Definition 28, take a Min vertex v ∈ [n] and an outgoing edge e ∈ Out(v). Under the assumptions over the graph G, the absorbing states reachable from the head of e form a set {w e , w e } ⊂ [m] of cardinality at most 2 (we use the convention w e = w e if there is only one such absorbing state). Moreover, if w e w e , then p e w e = p e w e = 1/2. Furthermore, observe that if w ∈ [m] is a Max vertex and e ∈ Out(w) is an outgoing edge, then our assumptions imply that the head of e is a Min vertex. We denote it by u e . With this notation, we have:

(F(x)) v = min e∈Out(v)
The operators of the form given in (10) are studied in (Allamigeon et al., 2018b, Sections 4.2 and 5.1). In particular, the claim follows from (Allamigeon et al., 2018b, Lemma 52).

We want to show that every real tropical cone associated with a graph G is a projection of a tropical Metzler spectrahedron. The idea of the proof is to take an arbitrary graph G and transform it (by adding auxiliary states) into a graph G that fulfills the conditions of Proposition 32. Furthermore, our construction needs to preserve the projection. A key ingredient is the following construction, which was used by [START_REF] Zwick | The complexity of mean payoff games on graphs[END_REF] to show the reduction from discounted games to simple stochastic games. • every Random vertex of G has exactly two outgoing edges and the probability distribution associated with these edges is equal to (1/2, 1/2)

• G and G encode the same operator.

Let us present the construction of Zwick and Paterson for the sake of completeness.

Proof. Fix a Random vertex v belonging to G. If this vertex has only one outgoing edge e, then we can delete v by joining all incoming edges In(v) with the head of e.

If v has at least three outgoing edges, then we enumerate the outgoing edges Out(v) by {e 1 , . . . , e d }, d 3. Let us recall that the vertex v is equipped with a probability distribution (q e s ) d s=1 . We now perform the transformation presented on Fig. 3. We replace the vertex v by a pair of vertices (w, u) such that all incoming edges of v are connected to w and w has two outgoing edges: one going to the head of e 1 with probability q e 1 and the other going to u with probability 1q e 1 . Finally, u has d -1 outgoing edges, the head of the sth outgoing edge is the head of e s , and the associated probability is equal to q e s /(1q e 1 ). We repeat this transformation until we reach a graph in which all Random vertices have exactly two outgoing edges.

If v has exactly two outgoing edges, then we denote the heads of these edges by w and u, and the associated probability distribution by (q, 1q), where q = a/b, a, b ∈ N * and a < b. If q 1/2, then we take r 1 such that 2 r b < 2 r+1 . We write a and b-a in binary, a = r s=0 c s 2 s and ba = r s=0 d s 2 s for c s , d s ∈ {0, 1}. We now replace the outgoing edges of vertex v by the construct presented on Fig. 4. In this construction, every Random node has exactly two outgoing edges and the associated probability distribution is equal to (1/2, 1/2). Furthermore, for any s, if c s = 1, then head of e s is w and if c s = 0, then the head of e s is v. Similarly, if d s = 1, then head of e s is u and if d s = 0, then the head of e s is v. Suppose that the Markov chain reaches v. Then, with probability a/2 r+2 the Markov chain goes to w without coming back to v. Similarly, with probability (ba)/2 r+2 the Markov chain moves to u without coming back to v. Therefore, the probability that the Markov chain finally reaches w is equal to a/b and the probability that it finally reaches u is equal to (ba)/b. We repeat this procedure for every Random vertex of our graph.

To finish the proof, observe that the operations described above do not affect the associated semilinear monotone homogeneous operator.

We now describe how to transform a graph given in Lemma 33 into a graph that verifies the conditions of Proposition 32. More precisely, we transform the graph G (which has n Min vertices) into a graph G (which has n Min vertices, where n n) in such a way that the real tropical cone {x ∈ R n : x F(x)} associated with G is a projection of the real tropical cone {x ∈ R n : x F (x)} associated with G . The main difficulty here is that the operators arising from tropical (Metzler) spectrahedra have a special structure, of "Player I -Chance -Player II" type, to adopt a game theoretical terminology, meaning that arcs in the graph connect Min vertices to Random vertices, Random vertices to Max vertices, and Max vertices to Min vertices, as is apparent from (10). By comparison, the Zwick-Paterson construction (Lemma 33) leads to a graph with consecutive sequences of Random nodes. We shall see, however, that the latter situation can be reduced from the former one by applying, as a basic ingredient, two transformations, the validity of which is expressed in Lemmas 34 and 35.

The first transformation that we execute is presented on Fig. 5. It is given as follows. Suppose that we are given a graph G. Denote V Min = [n] and V Max = [m]. Furthermore, let E Max ⊂ E denote the set of all edges that have a Max vertex as their tail. Let F denote the operator associated with G. For every Max vertex v ∈ [m] and outgoing edge e ∈ Out(v), we insert a Min vertex between v and the head of e, as illustrated in Fig. 5. In a similar way, for every Min vertex v and incoming edge e ∈ In(v), we insert a Max vertex between the tail of e and v. We denote the transformed graph by G . Observe that this graph fulfills Assumption 27. We refer to the Min vertices in G as follows: the vertices that were present in G are denoted by [n], whereas the added Min vertices are denoted by e ∈ E Max .

Lemma 34. Suppose that the operator F is obtained from F by the first transformation above. Then, the real tropical cone {x ∈ R n : x F(x)} is the projection of the real tropical cone The second transformation is given as follows. As previously, suppose that we are given a graph G. Denote V Min = [n] and V Max = [m]. Furthermore, let E Max ⊂ E denote the set of all edges that have a Max vertex as their tail. Let F denote the operator associated with G. Moreover, suppose that G is such that every edge e ∈ E Max has a Min vertex as its head. Suppose that e * ∈ E is a fixed edge in G that connects two Random vertices. We add a Max vertex m + 1 and a Min vertex n + 1 onto e * as presented on Fig. 6. We denote the transformed graph by G . Since every edge e ∈ E Max has a Min vertex as its head, every path that joins a Max vertex with a Min vertex has length 1. In particular, e * does not belong to any such path. Hence, the transformed graph G fulfills Assumption 27.

{(x, x ) ∈ R n × R |E Max | : (x, x ) F (x, x )}.
Lemma 35. Suppose that the operator F is obtained from F by the second transformation above. Then, the real tropical cone {x ∈ R n : x F(x)} is a projection of the real tropical cone {(x, x n+1 ) ∈ R n+1 : (x, x n+1 ) F (x, x n+1 )}. Let us introduce the following notation. For every e ∈ E, we denote by p e e * the conditional probability that the Markov chain reaches the head of e * from the head of e. Moreover, for every Max vertex w and every edge e ∈ E, we denote by p e w2 the conditional probability that the Markov chain reaches w from the head of e without passing by the head of e * . Thus, for every Max vertex w and every e ∈ E we have p e w = p e e * p e * w + p e w2 . Therefore, for any x n+1 ∈ R we have p e u x u .

Therefore, if x F(x) and we set

x n+1 = (F (x, 0)) n+1 , then (x, x n+1 ) F (x, x n+1 ). Conversely, if (x, x n+1 ) F (x, x n+1 ), then x n+1 (F (x, 0)) n+1 and hence x v (F(x)) v for all v ∈ [n].
Proposition 36. Every closed semilinear real tropical cone is a projection of a real tropical Metzler spectrahedron.

Proof. Take any closed semilinear real tropical cone S = {x ∈ R n : x F(x)}. Let G denote the graph associated with F. By Lemma 33 we may suppose that the probabilities associated with Random vertices in G are equal to 1/2. We perform the first transformation on the graph G. Denote the transformed graph by G 1 . We perform the second transformation on every edge in G 1 that joins two Random vertices. Denote the transformed graph by G and the associated operator as F . By Lemmas 34 and 35, the real tropical cone {x ∈ R n : x F(x)} is the projection of the real tropical cone {(x, x ) ∈ R n × R n : (x, x ) F (x, x )}. Furthermore, G fulfills the conditions of Proposition 32. Therefore, the set S = {(x, x ) ∈ T n × T n : (x, x ) F (x, x )} is a tropical Metzler spectrahedral cone. Finally, we take the set

S = {(x, x , y) ∈ T n × T n × T n+n : (x, x ) F (x, x ) ∧ (x, x ) + y 0} = {(x, x , y) ∈ R n × R n × R n+n : (x, x ) F (x, x ) ∧ (x, x ) + y 0} .
The set S is a real tropical Metzler spectrahedron. Moreover, S is a projection of S .

Example 37. Take the graph from Fig. 2 and consider the Random vertex that has Min vertices 2 and 3 as its neighbors. Figure 7 presents the outcome of the procedure described in the lemmas above when applied to this vertex.

General case of the tropical Helton-Nie conjecture

We now generalize Proposition 36 to tropically convex sets in T n . In order to study this case, we use the notion of homogenization of a convex set. There are many possible homogenizations of a given set. We need to use three different notions.

Definition 38. If S is a tropically convex set with only finite points (i.e., S ⊂ R n ), then we define its real homogenization as

S rh = {(x 0 , x 0 + x) ∈ R n+1 : x ∈ S} .
The set S rh is a real tropical cone. If S ⊂ T n is a tropically convex set, then we define its

homogenization as S h = {(x 0 , x 0 + x) ∈ T n+1 : x ∈ S} .
The set S h is a tropical cone. If S(Q (0) |Q (1) , . . . , Q (n) ) ⊂ T n is a tropical Metzler spectrahedron, then we define its formal homogenization as the tropical Metzler spectrahedron S f h ⊂ T n+1 , S f h S(-∞|Q (0) , Q (1) , . . . , Q (n) ). The set S f h is a tropical Metzler spectrahedral cone.

where λ ⊕ µ = 0, x ∈ S 1 , and y ∈ S 2 . Then z = x ⊕ ỹ, where x = (λ z 0 , (λ z 0 ) x) ∈ S h 1 , ỹ = (µ z 0 , (µ z 0 ) y) ∈ S h 2 .

Hence S h = S h 1 ⊕ S h We now prove the implication from Theorem 19 (c) to Theorem 19 (d). Let S ⊂ T n be as in Theorem 19 (c). If S is empty, then it is a tropical Metzler spectrahedron defined by a single inequality -∞ 0. Otherwise let K ⊂ [n] be any nonempty set such that the stratum S K ⊂ R |K| is nonempty. The set S K is a projection of a tropical Metzler spectrahedron S K ⊂ T |K| × T n . For any x ∈ T n we denote by x K ∈ T |K| the subvector formed by the coordinates of x with indices in K. Furthermore, let X K ⊂ T n denote the set

X K = {x ∈ T n : x k -∞ ⇐⇒ k ∈ K} .
The set S ∩ X K is a projection of a tropical Metzler spectrahedron defined as SK = {(x, y) ∈ T n × T n : (x K , y) ∈ S K ∧ ∀k K, -∞ x k } .

Moreover, for K = ∅, let us denote X ∅ = -∞. Note that the intersection S ∩ X ∅ is either empty or is equal to -∞, and that -∞ is a tropical Metzler spectrahedron (defined by the inequalities -∞

x k for all k ∈ [n]). Hence, we have S = ∪ K⊂[n] S ∩ X K = tconv(∪ K⊂[n] S ∩ X K ).

Therefore, the claim follows from Lemma 41. Finally, to prove the implication Theorem 19 (d) to Theorem 19 (a), let S ⊂ T n be a projection of a tropical Metzler spectrahedron S ⊂ T n × T n .

By Proposition 17, there is a spectrahedron S ∈ K n+n 0 such that val(S) = S. Let π : K n+n → K n denote the projection on the first n coordinates. Then S = val(π(S)).

Remark 42. Consider a convex semialgebraic subset S over K n . Theorem 3 shows that there exist integers p and m such that S has the same image by the valuation as a projection of some spectrahedron over K p associated with matrices of size m × m. The integers p and m appearing in the proof of this theorem have the following remarkable uniformity property: if S is given as a union of finitely many basic semialgebraic sets of the form (6), then p, m are bounded from above by a number N that depends only on the degrees and the number of polynomials involved in the description of S (i.e., that N is independent of the coefficients of these polynomials). The proof, however, is quite involved. First, one should observe that, given only the degrees and the number of polynomials describing S, the Denef-Pas quantifier elimination creates a finite set of L og -formulas such that every stratum of val(S) is described by a formula from this set. Second, Theorem 19 gives a tropical Metzler spectrahedron S such that val(S) is its projection. A careful examination of the proof presented here shows that the dimension and the size of the matrices defining S can be bounded by a quantity that depends only on the aforementioned L og -formulas (and not on the particular choice of their parameters). This gives the desired bound N.

Remark 43. Given the bound of Remark 42, the Denef-Pas quantifier elimination implies that our main result (Theorem 3) is valid not only over the field of Puiseux series considered here, but over every real closed valued field equipped with a nontrivial and convex valuation.

Concluding remarks

We showed that the convex semialgebraic sets and the projections of spectrahedra over the nonarchimedean field of real Puiseux series have the same images by the nonarchimedean valuation. We gave an explicit representation for these images, as the subfixed point sets of semilinear monotone homogeneous maps (dynamic programming operators of zero-sum stochastic games with perfect information). One may ask whether more insight on the projections of spectrahedra over nonarchimedean fields or over the field of real numbers can be gotten by tropical methods. In this respect, we note that we considered the simplest possible tropicalization, looking at the image of Puiseux series by their ordinary valuations. We also leave it as a further work to see whether more sophisticated tropicalizations, capturing also the sign, or higher order approximations of Puiseux series (spaces of jets) may be exploited.

  and the signed valuation is defined as sval : K → T ± , sval(x) = (sign(x), val(x)). The modulus function |•| : T ± → T is defined as the projection which forgets the first coordinate. The sign function sign : T ± → {-1, 0, 1} is defined as the projection which forgets the second coordinate. The elements of the form (1, a) of T ± are called positive tropical numbers and are denoted by T + . Similarly, the elements of the form (-1, a) of T ± are called negative tropical numbers and are denoted by T -. By convention, we denote the positive tropical number (1, a) by a, the negative tropical number (-1, a) by a, and the element (0, -∞) by -∞.

Theorem 19 .

 19 Fix a set S ⊂ T n . Then, the following conditions are equivalent: (a) S is a tropicalization of a convex semialgebraic set (b) S is tropically convex and has closed semilinear strata (c) S is tropically convex and every stratum of S is a projection of a real tropical Metzler spectrahedron (d) S is a projection of a tropical Metzler spectrahedron.

Figure 1 :

 1 Figure 1: A real tropical cone from Example 26 (for x 3 = 0).

Definition 28 .

 28 The operator encoded by G is the function F : R n → R n defined as ∀v ∈ [n], (F(x)) The operator encoded by G is semilinear monotone homogeneous. Proof. Let F be the operator encoded by G. It is obviously semilinear (as a definable function in L og ) and monotone. We already observed that the Max and Min vertices are absorbing states in the Markov chain constructed from G. Besides, Assumption 27 (iii) still holds in the subgraph obtained by removing the edges going out of the Max and Min vertices. As a consequence, for every Random vertex v, the probability to reach a Min or Max vertex starting from v is positive. We deduce that the Max and Min vertices are the only final classes in the Markov chain. Let v be a Min vertex, and e ∈ Out

Figure 2 :

 2 Figure 2: Graph that encodes the operator from Example 26. Min vertices are depicted by circles, Max vertices are depicted by squares, Random vertices are depicted by diamonds. We put r e = 0 for every edge e ∈ E that has no label.

  + x u e ) + max e ∈Out(w e )(r e + x u e ) .

Figure 3 :

 3 Figure 3: Lowering the degree. Random vertices are depicted by diamonds.

Figure 4 :

 4 Figure 4: The construct of Zwick and Paterson.

Proof.Figure 5 :Figure 6 :

 56 Figure 5: First transformation of a graph. Min vertices are presented by circles, Max vertices are presented by squares.

Proof.

  Denote the operator F as ∀v ∈ [n], (F(x)) v = min e∈Out

Figure 7 :

 7 Figure 7: The transformation of Lemmas 33 to 35 applied to one Random vertex from the graph presented in Fig. 2. Top left: the initial graph. Top right: the graph after the application of Lemma 33. Bottom left: the graph after the application of Lemma 34. Bottom right: the graph after the application of Lemma 35.

2

  and the claim follows from Lemma 40. We are now ready to present the proof of Theorem 19. Proof of Theorem 19. The equivalence between Theorem 19 (a) and Theorem 19 (b) is given in Proposition 12. The implication from Theorem 19 (b) to Theorem 19 (c) follows from Lemma 39.

Lemma 33[START_REF] Zwick | The complexity of mean payoff games on graphs[END_REF]. One can transform an arbitrary graph G into a graph G such that

Acknowledgements

A preliminary version of this paper was presented at MEGA 2017. We are grateful to the anonymous reviewers of MEGA and Journal of Symbolic Computation for their comments and suggestions.

The three authors were partially supported by the ANR projects CAFEIN (ANR-12-INSE-0007) and MALTHY (ANR-13-INSE-0003), by the PGMO program of EDF and Fondation Mathématique Jacques Hadamard, and by the "Investissement d'avenir", référence ANR-11-LABX-0056-LMH, LabEx LMH. M. Skomra is supported by a grant from Région Ile-de-France.

Proof. Take any closed semilinear tropically convex set S ⊂ R n and consider its real homogenization S rh . This is a closed semilinear real tropical cone in R n+1 . By Proposition 36, S rh is a projection of a tropical Metzler spectrahedron S 1 ⊂ T × T n × T n . Consider the set

The set S 2 is a tropical Metzler spectrahedron. Furthermore, S is its projection.

We now want to extend this result to tropically convex sets in T n . In order to do this, we proceed stratum-by-stratum. This requires us to show that a tropical convex hull of finitely many projected Metzler spectrahedra is a projected Metzler spectrahedron. In the classical case of real spectrahedra, it is known that a convex hull of finitely many projected spectrahedra is a projected spectrahedron. This fact has a very short proof presented in [START_REF] Netzer | A note on the convex hull of finitely many projections of spectrahedra[END_REF]. The proof in the tropical case is exactly the same (we only change the classical notation to the tropical one). Let us present this proof for the sake of completeness.

Lemma 40. A tropically convex set S ⊂ T n is a projected tropical Metzler spectrahedron if and only if its homogenization is a projected tropical Metzler spectrahedron.

Proof. First, suppose that S h is a projection of a tropical Metzler spectrahedron S 1 ⊂ T×T n ×T n .

Consider the set

The set S 2 is a tropical Metzler spectrahedron. Furthermore, S is its projection. Conversely, suppose that S is a projection of a tropical Metzler spectrahedron S 1 ⊂ T n × T n . Consider its formal homogenization S f h 1 ⊂ T 1+n+n and take the set

The set S 2 is a tropical Metzler spectrahedron. We will show that S h is a projection of S 2 . Take any point x ∈ S. Then, there exists y such that (0, x, y) ∈ S f h 1 . Therefore, (x 0 , x + x 0 e, y + x 0 e) ∈ S f h 1 for any x 0 ∈ R. If we take z k large enough, then (x 0 , x + x 0 e, y + x 0 e, z) ∈ S 2 . Moreover, we have -∞ ∈ S 2 . This shows that S h is included in the projection of S 2 . Conversely, suppose that (x 0 , x, y, z) ∈ S 2 . If x 0 = -∞, then x = -∞ and hence (x 0 , x) ∈ S h . If x 0 -∞, then we have (0, xx 0 e, yx 0 e, zx 0 e) ∈ S 2 . Hence (0, xx 0 e, yx 0 e) ∈ S f h 1 , (xx 0 e, yx 0 e) ∈ S 1 , and xx 0 e ∈ S. Therefore (x 0 , x) ∈ S h . Lemma 41. Suppose that S 1 , S 2 ⊂ T n are projected tropical Metzler spectrahedra. Then tconv(S 1 ∪ S 2 ) is a projected tropical Metzler spectrahedron.

Proof. Let S = tconv(S 1 ∪ S 2 ) and consider

Observe that we have the identity S h = S h 1 ⊕ S h 2 . Indeed, since S 1 ⊂ S, we have S h 1 ⊂ S h . Similarly, S h 2 ⊂ S h . Therefore, we have S h 1 ⊕ S h 2 ⊂ S h . Conversely, take a point z ∈ S h . By Lemma 9, we can write z as z = z 0 , z 0 (λ x) ⊕ (µ y) ∈ S h ,


Jean-Michel Desse

François Olchewsky

Dual-reference digital holographic interferometry for analyzing high density gradients in fluid mechanics

This paper proposes a dual-reference digital holographic interferometer for analyzing high refractive index encountered in transonic and supersonic flows. For that, a Wollaston prism is inserted in the reference arm in order to simultaneously generate two orthogonally polarized reference waves. As consequence, recorded interferograms contain two crossed and perpendicular interference patterns which give two orders fully separated in the Fourier spectrum. It is then possible to analyze a transparent object regardless the orientation of the refractive index gradient using the two phase maps reconstructed with each of the two first interference orders. Fusion of the phase maps yield a single phase map in which the phase singularities are removed. Experimental results demonstrate the suitability of the proposed approach for analyzing shock waves in the unsteady wake flow around a circular cylinder at Mach 0.75. © 2018 Optical Society of America In the domain of fluid mechanics, the flows consecutive to detachments, marginal vortices, jets and vortex bursting need to be characterized by fine and adapted optical methods. This requirement aims at deepening the phenomenology of these complex flows and to build databases from the gas density field for the qualification of the computational fluid dynamics codes. The two main alternative techniques currently used are velocity measurements that allow either local measurement at very high frame rates (velocity vector measurement by Laser Doppler Anemometry) [START_REF] Durst | Principles and Practice of Laserdoppler Anemometry[END_REF], or full-field measurement with two or three components (Particle Image Velocimetry) [START_REF] Adrian | Particle image velocimetry[END_REF]. It is therefore crucial to define tools for measuring smaller and smaller data in space and time. The digital holographic interferometer developed and tested at ONERA is a non-intrusive metrological tool, with high spatial and temporal resolution. The setup provides absolute and instantaneous measurements of the full field of gas density and the evolution of the field in time, unlike the differential methods which only give access to the local derivative of the measured quantity (differential interferometry, schlieren techniques, background oriented schlieren). The optical method has been successfully tested for the analysis of subsonic unsteady flows [START_REF] Desse | Advanced Holography-Metrology and Imaging[END_REF][START_REF] Desse | [END_REF], but as the Mach number increases and becomes close to the transonic regime, shock waves appear in the flow and cause phase singularities in phase unwrapping which depend on the fringe orientation. In order to solve this problem, we propose a dual reference digital holographic interferometer in which the sensitivity to phase singularities is reduced, and both reference waves interfere with the object wave. The two generated interference patterns have crossed orientations and they are recorded on the same sensor. For the interferogram analysis, 2D Fourier spectrum exhibits two fully separated diffraction orders that provide the reconstruction of two phase maps, one for each interference pattern. As high density gradients are analyzed (shock waves, for instance), phase singularities may appear in the first interference pattern because the fringes are parallel to the shock wave. In this case, the second interference pattern which has the fringes perpendicular to the shock wave is used and the refractive index shift can be determined through the shock wave. Then, fusion of the two phase maps yields a single phase map in which the phase singularities are removed. In literature, off-axis holographic interferometers generating several references either with several wavelengths or a single wavelength generating a double reference were published. As examples, for the measurement of displacements of scattering object, several authors use different color laser sources to measure the different components of the deformation [5,6], in digital holographic microscopy, to reconstruct the synthetic wavelength phase distribution of a reflective objet [7], or to quantify the threedimensional structure of cells [8]. Others researchers propose to measure the state of polarization of a magnetic sample by using two orthogonally polarized reference beams [START_REF] Khodadad | Proc. SPIE[END_REF]. Barada et al. [START_REF] Barada | [END_REF] and Ochiai et al. [11] describe a single reference wave and two object waves having perpendicular linear polarizations and driven by spatial light modulators. In this case, two cameras are used to record an interference pattern formed between one of the two object waves with the reference wave. Lee et al. propose a dualchannel Mach-Zehnder interferometer which provides the reconstruction of the field object from only two step measurements [12]. More precisely, the nearest works of those described in this letter are those of Abdelsalam et al. who developed a dual-wavelength digital holographic set-up based on the polarization separation for imaging polarimetry [13] and specially, the work of Beghuin [14] and Colomb [15] who used two reference beams presenting orthogonal polarizations and different propagation directions to measure spatial variations of the polarization of an object wave. In their experimental setup, they have to use several beam splitters, /4 and  /2 wave plates and a variable retarder. As comparison with our setup, we have just to introduce a Wollaston prism in the reference beam to generate two reference beams presenting orthogonal polarizations. Finally, we can also mention the work of Tahara [16] who imaged the distribution of the polarization of three-dimensional objects by using the space-division multiplexing of holograms. Unfortunately, the micro-polarizer array device used in this technique limits the resolution by a factor of 2.

In this letter, we present a dual-reference Mach-Zehnder digital holographic interferometer with phase map fusion for analyzing high refractive index in transonic and supersonic flows. In this type of flow, the difficulty lies in the measurement of phase step consecutive to the high density gradients where, for instance, it is not possible to get continuous interference fringes at the crossing of the shock waves. Thus we propose to use a Wollaston prism in order to simultaneously generate two reference waves with orthogonal polarization. As consequence, the interferogram recorded by the sensor contains two interference patterns with crossed directions which provide two orders fully separated in the Fourier spectrum. It is then possible to analyze a transparent object regardless the orientation of the refractive index gradients using the two phase maps reconstructed with each of the two interference orders. The next paragraph discusses an example of analyzing shock waves in the unsteady wake flow around a circular cylinder at Mach 0.75. The interferometer is presented in Fig. 1 and it uses a pulsed laser vertically polarized with an exposure time of 5 nanoseconds at a pulse rate of 10 Hz. The coherence length of the laser is 3 meters. The first beam splitter cube forms the object beam which passes through the test section (object beam) and the reference beam which passes below the test section. In the object beam, a spatial filter associated with the f800 mm lens allows illuminating the test section with parallel beam. A second f800 mm lens associated with the f70 mm lens provides the magnification of the test section at the sensor plane. In the reference beam, a second spatial filter and the f120 mm lens allow obtaining a parallel beam. A second beam splitter cube recombines the reference and object beams on the sensor. In the reference arm, a Wollaston prism is inserted between the spatial filter and the lens f = 120 mm at a distance d of the lens. The prism separates the reference wave into two orthogonally polarized waves S and P (red and blue in Fig. 1).

These two waves are separated by a small birefringence angle  = 2.(ne -no).tan() that depends on the pasting angle  and on the material (quartz or calcite) of the prisms. The refractive index variation ne -no represents the extraordinary and ordinary indices of the material. As the Wollaston prism is located inside the focal length of the f120 mm lens, the magnification G can be obtained according to Eq. ( 1):

𝑮 = 𝒇 𝒇-𝒅 = 𝜺 𝝐 ′ (1)
where ' is the birefringence angle measured behind the f120 mm lens.

It can be calculated as a function of the parameters of the optical setup and of the prism parameters:

𝜺 ′ = 𝟐 (𝟏 - 𝒅 𝒇 ) . (𝒏 𝒆 -𝒏 𝟎 ). 𝒕𝒂𝒏(𝜶) ( 2
)
The Wollaston prism inside the reference arm generates two reference waves, namely S (red) and P (blue), which can interfere with the S and P components of the object wave. Two configurations are possible. If one needs to generate orthogonal interference patterns inclined at -45° and +45°, the polarization direction of the reference and object waves has to be turned by 45° using a half wave plate oriented at 22.5° as shown in Fig. 1. Fig. 2(a) shows the polarization S and P of the two reference waves (red and blue, respectively) and the object wave (green). The second configuration consists in obtaining horizontal and vertical fringes. For that, the two half wave plates are removed of the set-up and the Wollaston prism is rotated by 45° around its axis so that the S and P components are inclined at -45° and +45° of the vertical axis. In the object beam, the polarization direction becomes vertical and the S and P components of the object wave are inclined at -45° and +45° of the vertical axis as shown in Fig. 3(a). Then, a very good spatial resolution has to be reached to correctly define the fringe period i (5 to 10 pixels, for instance). With the used camera (Hamamatsu Orca flash 2.8, pixel size of 3.65 m), the angle ' can be calculated by:

𝜺 ′ = 𝟐. 𝒂𝒓𝒄𝒔𝒊𝒏( 𝝀 𝟐𝒊 ) (3)
and, if the Wollaston prism is set at a distance d equal to f/2 , the angle  can be found according to Eq. ( 1). The numerical application gives = 4.85° and 9.62° for i = 10 pixels and 5 pixels respectively. As the birefringence angle has to be large, this requires the use of a calcite Wollaston (ne -n0 = 0.172) and a pasting angle  of 8° was chosen. In these conditions, when the Wollaston is placed at d varying from 30 mm to 90 mm, the pixels number of the fringe period varies from 4 to 12 pixels. The dual-reference digital holographic interferometer using Wollaston prism has been tested for analyzing the unsteady wake flow downstream a circular cylinder, 20 mm in diameter, at transonic Mach number (0.75). Fig. 4 shows the reference interferogram where the enlarged parts of the cylinder exhibits the checkerboard formed by the two inclined pattern of interference fringes arbitrarily set at +45° and -45° and the measurement interferogram shows the checkerboard disturbed by the separation layers emitted from the upper and lower surfaces. Then, the 2D Fast Fourier Transform is computed for each interferogram and the results are presented in Fig. 5. The spectra show the zero order at center, the +1 and -1 orders corresponding to the interferences between the polarized reference and object waves S and P (respectively red and blue). The useful signal for reconstructing the phase maps is contained inside the circles. The spatial frequencies of the fringes can be estimated from the spectrum. Thus, the +1 order of the S polarization is located at the coordinates (us = -21.69 lines/mm, vs =19.79 lines/mm) and the +1 order of the P polarization at the coordinates (up = 18.55 lines/mm, vp = 21.12 lines/mm). From that, the fringe period of the two S and P patterns along + 45° and -45° axis, respectively, are equal to 34.06 m and 35.57 m. The pixel number in each fringe period is 9.33 pixels for S and 9.75 for P. This was expected by positioning the Wollaston prism at d = 80 mm. For each S and P 2D Fourier spectra, the modulo 2 phase maps for the reference and measurement interferograms are computed. Fig. 6 shows the phase difference obtained between the measurement and the reference for the polarization S (left) and P (right). The white circles indicate the areas where the phase exhibits singularities. They are located on the upper part of the S polarization map and on the lower part of the P polarization map. The unwrapping of modulo 2 phase maps of Fig. 6 is presented in Fig. 7. The Herraez's algorithm which consists in determining a criterion of reliability for each pixel was used [17]. The criterion is equal to the inverse of the second difference with the neighboring pixels and the phase unwrapping can be operated following a non continuous path. The more reliable the pixels, the lower their second difference. An unwrapping path is defined by looking at the value of the reliability of the edges. The edges are stored in an array and sorted by value of reliability. The edges with a higher reliability are solved first. As seen in Fig. 7, the lower part of the S polarization image and the upper part of the P polarization image are correctly unwrapped and the phase singularities can be clearly seen in the white circles. The fusion of these two phase maps yields an error-free phase map. The processed phase difference shown in Fig. 8 is obtained by taking the lower part of the phase map calculated with S polarization image and the upper part of the phase map calculated with P polarization image. Between both phase maps, in areas without phase shifts or where the phase varies continuously (for instance, at the cylinder nose), a phase difference equivalent to a piston phase which can be determined by comparing, at a given pixel, the phase found in the S polarization map and those given by the P polarization map. Then, the correction of piston phase is numerically applied for the selected area or for all half of the map. As consequence, the shock waves, the detachment zones and shear layers are very well restored and the phase map no longer shows any residual phase singularities.

where s is the standard gas density computed at 1 atmosphere and 0°C, o the stagnation gas density,  the wavelength of the interferometer, e the width of the test section and K the Gladstone-Dale constant (K=296x10 -6 ). It follows that the gas density in the first vortex exhibits a strong decrease down to 90% of o. In the second vortex, the measured gas density is near to 80% of o. . A lot of interferograms have been analyzed in order to evaluate the axial evolution of the gas density along x inside the vortex cores. Two phases have been identified behind the cylinder of diameter D. For 0.5 < x/D < 1, the vortices are in a formation or agglomeration phase because the gas density decreases at their center. Then, when x/D > 1, the vortices enter a phase of dissipation because the gas density increases again at their centers. It remains to compare the experimental results with the results yielded by Computational Fluid Dynamic codes.

As conclusion, dual-reference digital holographic interferometry using Wollaston prism is ideally suited for analyzing high refractive index encountered in transonic and supersonic flows.

Funding. The French National Research Agency (ANR) (ANR-14-ASTR-0005).

  OCIS codes: (090.1995) Digital holography; (090.2880) Holographic interferometry; (110.2650) Fringe analysis; (110.5086) Phase unwrapping.

Fig. 1 .

 1 Fig. 1. Dual-reference digital holographic interferometer using Wollaston prism. BS, SF, FM and D are beam splitter cube, spatial filter, flat mirror and diaphragm respectively.

Fig. 2

 2 (b) shows the reference waves shifted by dx = '.f and the location of the object wave with respect to the two reference waves to obtain the inclined fringes patterns. Fig.2(c) shows the two interferences produced by the S and P components of the reference and object waves. Fig.2(d)shows the result of the superposition of the two patterns recorded by the sensor which gives a checkerboard of interference fringes inclined at 45°.

Fig. 2 .

 2 Fig. 2. Scheme of interferences generated at +45° and -45°.

Fig. 3 (

 3 b) and Fig.3(c) show the location of the object wave with respect to the two reference waves to obtain the vertical and horizontal checkerboard of interference fringes. The result of the superposition of the two patterns recorded by the camera (horizontal and vertical checkerboard) is given in Fig.3(d).

Fig. 3 .

 3 Fig. 3. Scheme of interferences generated at 0° and 90°.

Fig. 4 .

 4 Fig. 4. Interferograms recorded without and with flow. On each interferogram, we can see the shadow of the tips of pitot pressure and the unsteady pressure sensor which are implemented at the skin of the cylinder. Both sensors pass inside the model and outside the test section. With this equipment, the interferograms which are taken at different instants of the vortex street can be correlated with the unsteady pressure signals.

Fig. 5 .

 5 Fig. 5. 2D FFT spectra of interferograms recorded without flow (reference, left) and with flow (measurement, right).

Fig. 6 .

 6 Fig. 6. Modulo 2 phase difference maps (S and P polarization).

Fig. 7 .

 7 Fig. 7. Unwrapped phase difference maps (S and P polarization).

Fig. 8 .

 8 Fig. 8. Fusion of the phase maps from S and P polarization data.Note that the mixing of the two polarization images could be carried out by taking into account the highest values of the reliability factor on each modulo 2 phase map[17]. From a point of view of Fluids Mechanics, a phase variation  of about 120 radians between the stagnation point (just at the nose of the cylinder) and the center of the first vortex downstream the cylinder can be measured from the experimental results. The dimensionless gas density can be calculated from the phase difference  according the following relationship: 𝜌 𝜌 𝑜 = 1 -( 𝜌 𝑠 𝜌 𝑜