Mateusz Skomra. Signed tropical halfspaces Georg Loho

Mateusz Skomra

Signed tropical halfspaces and convexity

Introduction

Convexity is a powerful structure which is often behind the existence of efficient algorithms. In this spirit, tropical convexity, arising from classical convexity by replacing addition with maximization and multiplication by addition, found several applications from optimization [START_REF] Xavier Allamigeon | What tropical geometry tells us about the complexity of linear programming[END_REF], phylogenetics [START_REF] Yoshida | Tropical principal component analysis and its application to phylogenetics[END_REF] and machine learning [START_REF] Maragos | Tropical geometry and machine learning[END_REF]. While tropical convexity was mainly considered with a non-negativity constraint for a long time, the recent paper [START_REF] Loho | Signed Tropical Convexity[END_REF] introduced a notion of signed tropical convexity to overcome this restriction. In this paper, we extend the fundamentals of signed tropical convexity and exhibit a slightly different version of signed tropical convexity.

The crucial building blocks of the two versions of signed tropical convexity are open and closed tropical halfspaces. We coin the name TO-convexity (tropical open convexity) for the convexity in which the hull of finitely many points equals the intersection of the open tropical halfspaces containing them. Additionally, we define TC-convexity (tropical closed convexity) in such a way that the hull of finitely many points equals the intersection of the closed tropical halfspaces containing them. For technical reasons, we actually introduce it via the hull of only two points first (Definition 3.5) and give the characterization for bigger sets by closed tropical halfspaces as one of our main results.

Our main result is Theorem 6.1 which shows that the definition via hulls of only two points is actually equivalent to the definition via intersection of closed tropical halfspaces. This gives an analog of the hyperplane separation theorem for TCconvexity. To arrive at this statement, we need to gather extensive insights into the structure of TC-convex sets and their lifts to Puiseux series. We make explicit use of the connection between separation of sets over Puiseux series and their signed valuation established in Theorem 4.10. We use this to strengthen the separation results which we derive directly for TC-convex sets. The main insights for those is the fundamental elimination property of TC-convexity given in Theorem 5.2. To combine this with the separation properties for lifts, we investigate TC-hemispacesthose TC-convex sets whose complement is also TC-convex. We show that they are nearly tropical halfspaces in Theorem 5.10 and provide several structural insights on their boundary. Along the way, we also give new separation results for TO-convex sets including the Pasch & Kakutani properties (Theorem 3.3). Furthermore, we derive Carathéodory-type results for TC-convexity. We finish with Minkowski-Weyl theorems for finitely generated TC-convex sets (Theorem 6.3 and Theorem 6.4).

Comparison of TO-convexity and TC-convexity. From the viewpoint of abstract convexity [START_REF] Van De | Theory of Convex Structures[END_REF], TO-convexity is generated by open tropical halfspaces and TC-convexity is generated by closed tropical halfspaces. This yields that TOconvex sets are also TC-convex. While TO-convex sets still behave rather well with the algebraic operations, as TO-convex hull can be written using (tropical) convex combinations with hyperoperations, this structure is lost for TC-convexity.

To describe the latter, we use a non-commutative addition, which we call left sum (Definition 2.11). It generalizes the composition of vectors in an oriented matroid. In this way, this operation already appeared in work on Bergman fans for matroid over hyperfields generalizing composition of sign vectors of an oriented matroid [START_REF] Celaya | Lattice points, oriented matroids, and zonotopes[END_REF][START_REF] Anderson | Vectors of matroids over tracts[END_REF]. We will elaborate more about the implication of this connection in upcoming work.

Another remarkable difference is the behavior with respect to lifts to Puiseux series. In [START_REF] Loho | Signed Tropical Convexity[END_REF]Theorem 3.14], it was shown that the TO-convex hull of finitely many points arises as union of the signed valuations of the convex hulls ranging over all lifts. We show in Corollary 6.2, that the TC-convex hull arises as the intersection of these lifts.

Motivation. Our work is motivated by the need for a better structural basis underlying (recent) applications of tropical convexity. New insights on the complexity of classical linear programming based on tropical geometry have been a great success story in recent years [START_REF] Allamigeon | Combinatorial simplex algorithms can solve mean payoff games[END_REF][START_REF] Xavier Allamigeon | Log-barrier interior point methods are not strongly polynomial[END_REF][START_REF] Xavier Allamigeon | What tropical geometry tells us about the complexity of linear programming[END_REF][START_REF] Xavier Allamigeon | No self-concordant barrier interior point method is strongly polynomial[END_REF]. The point of origin for these advances is the tropicalization of linear programs -where one always had to impose additional nonnegativity constraints. A thorough foundation of signed tropical convexity will allow to study the signed tropicalization of general linear programs.

Furthermore, tropical convexity has an intimate connection with mean payoff games as the feasibility problem for tropical inequality systems (restricted to the tropical nonnegative orthant) is equivalent to mean payoff games [START_REF] Akian | Tropical polyhedra are equivalent to mean payoff games[END_REF]. The latter have an intriguing complexity status in the intersection of NP and co-NP while no polynomial-time algorithm is known [START_REF] Zwick | The complexity of mean payoff games on graphs[END_REF]; see the recent paper [START_REF] Colcombet | The theory of universal graphs for infinite duration games[END_REF] for a good overview including the flourishing advances on the subclass of parity games. Studying the polar of a tropical polyhedron naturally leads to tropically convex sets without a nonnegativity constraint which was modeled by pairs of nonnegative numbers in former work [START_REF] Xavier Allamigeon | Tropical polar cones, hypergraph transversals, and mean payoff games[END_REF]. We think that signed tropical convexity may enrich the insights in the structure of these games.

Yet another motivation comes from interest in signed tropicalization of semialgebraic sets [START_REF] Jell | Real Tropicalization and Analytification of Semialgebraic Sets[END_REF]. The study of unsigned tropicalizations of semialgebraic sets already lead to a fruitful connection between stochastic games and (non-Archimedean) semidefinite programs [START_REF] Allamigeon | Solving generic nonarchimedean semidefinite programs using stochastic game algorithms[END_REF]. In particular, the analysis of tropical cones arising in this work resulted in a recent universal complexity bounds on value iteration for a large class of games in [START_REF] Allamigeon | Universal complexity bounds based on value iteration and application to entropy games[END_REF]. Our framework allows to capture also other classes of optimization problems where the nonnegativity condition is a priori not satisfied.

Finally, already in [START_REF] Loho | Signed Tropical Convexity[END_REF], it was demonstrated that signed tropical linear inequality systems with unit coefficients are the same as Boolean formulas. In this sense, more general signed tropical linear inequality systems form a 'quantitative' generalization of Boolean formulas. Therefore, the feasibility problem for linear systems over signed tropical numbers is a natural generalization of SAT. Note that the solution sets of these systems are actually not TO-convex. However, they are exactly the finitely generated TC-convex sets.

Related work. We refer to the book [START_REF] Joswig | Essentials of tropical combinatorics[END_REF] for a general overview on (unsigned) tropical convexity. Different versions of separation theorems in the tropical convexity have been obtained by numerous authors [START_REF] Zimmermann | A general separation theorem in extremal algebras[END_REF][START_REF] Samborskiȋ | Convex sets in the semimodule of bounded functions[END_REF][START_REF] Cohen | Max-plus convex sets and functions[END_REF][START_REF] Develin | Tropical convexity[END_REF][START_REF] Briec | Halfspaces and Hahn-Banach like properties in Bconvexity and max-plus convexity[END_REF][START_REF] Gaubert | Cyclic projectors and separation theorems in idempotent convex geometry[END_REF]. Likewise, the Carathéodory theorem for tropical convexity has been discovered independently in different works [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]. The tropical analogue of the Minkowski-Weyl theorem for was proven in [START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF]. In order to prove our main separation theorem, we rely on works on abstract convexity, which were already applied to the usual tropical convexity in [START_REF] Horvath | Some general principles in tropical convexities[END_REF]. Furthermore, our proof requires to give a partial characterization of signed tropical hemispaces. A full characterization of tropical hemispaces in one orthant is given in [START_REF] Briec | Halfspaces and Hahn-Banach like properties in Bconvexity and max-plus convexity[END_REF][START_REF] Katz | Characterization of tropical hemispaces by (p,r)-decompositions[END_REF][START_REF] Daniel Ehrmann | The geometric structure of max-plus hemispaces[END_REF].

The link between the tropical convexity and convexity over Puiseux series was established in the work [START_REF] Develin | Tropical polytopes and cellular resolutions[END_REF] which studies the tropicalization of polyhedra. This was later generalized to spectrahedra in [START_REF] Yu | Tropicalizing the positive semidefinite cone[END_REF][START_REF] Xavier Allamigeon | Tropical spectrahedra[END_REF] and to convex semialgebraic sets in [START_REF] Allamigeon | The tropical analogue of the Helton-Nie conjecture is true[END_REF]. The tropicalizations of general semialgebraic sets are studied in [START_REF] Alessandrini | Logarithmic limit sets of real semi-algebraic sets[END_REF] and this study is extended to signed tropicalizations in [START_REF] Jell | Real Tropicalization and Analytification of Semialgebraic Sets[END_REF] and [START_REF] Xavier Allamigeon | Tropical spectrahedra[END_REF]Section 4].

Signed tropical numbers first appeared in the context of the symmetrized semiring [START_REF] Akian | Linear systems in (max, +) algebra[END_REF]. The idea that tropical convexity could be extended to signed tropical numbers appeared already in [START_REF] Briec | B-convexity[END_REF][START_REF] Briec | Some remarks on an idempotent and non-associative convex structure[END_REF], where two such extensions (different than the ones considered here) are introduced. Our work is most closely related to the paper [START_REF] Loho | Signed Tropical Convexity[END_REF] which introduces and studies the TO-convexity.

Preliminaries on signed tropical numbers

We give a brief overview of necessary notions related to signed numbers; for more see [START_REF] Akian | Tropical Cramer determinants revisited[END_REF][START_REF] Akian | Linear systems in (max, +) algebra[END_REF][START_REF] Loho | Signed Tropical Convexity[END_REF]. The signed tropical numbers T ± are obtained by glueing two copies of (R ∪ {-∞}) at the tropical zero element O = -∞ giving rise to the nonnegative tropical numbers T ≥O = R ∪ {O} and the non-positive tropical numbers

T ≤O = { x | x ∈ R} ∪ {O}.
The signed numbers can be extended to the symmetrized semiring S, which forms a semiring containing T ± , by attaching balanced numbers T • = { •x | x ∈ R}∪{O}. We will often use the norm | . | on T ± which maps each element of T ≥O to itself, removes the sign of an element in T ≤O and the • from an element in T • . This is complemented by the map tsgn from S to {⊕, , •, O} keeping only the sign information.

Throughout, we use the notation [d] = {1, 2, . . . , d} and [d] 0 = [d] ∪ {0}. For a vector z ∈ T d ± we denote its support, positive support and negative support, respectively, by supp

(z) = { i ∈ [d] | z i = O} supp ⊕ (z) = { i ∈ [d] | z i ∈ T >O } supp (z) = { i ∈ [d] | z i = T <O } . (1)
For x, y ∈ S, the addition is defined by

x ⊕ y = argmax x,y (|x|, |y|) if |χ| = 1 • argmax x,y (|x|, |y|) else . ( 2
)
where

χ = { tsgn(ξ) | ξ ∈ (argmax(|x|, |y|))}.
The multiplication is given by

x y = (tsgn(x) * tsgn(y)) (|x| + |y|) , (3)
where the * -multiplication table is the usual multiplication of {-1, 1, 0} for { , ⊕, •} with the additional specialty that multiplication with O yields O. The operations ⊕ and extend to vectors and matrices componentwise. We use ⊕, and • also as unary operations on S with = ⊕, • = •• = • = • and where ⊕ just acts as identity. The fact that S with these operations forms a commutative semiring justifies the name introduced above. We also point out that balanced numbers in the symmetrized semiring are equivalent to the use of a multivalued addition as in the theory of hyperfields [START_REF] Connes | The hyperring of adèle classes[END_REF][START_REF] Baker | Matroids over partial hyperstructures[END_REF]. More precisely, the addition in the symmetrized semiring is equivalent to the multivalued addition in the real tropical hyperfield discussed in [START_REF] Jell | Real Tropicalization and Analytification of Semialgebraic Sets[END_REF][START_REF] Viro | Hyperfields for tropical geometry i. hyperfields and dequantization[END_REF].

Example 2.1. One has 2 1 = 3, (0 ⊕ 0) -1 = •0 -1 = • -1, -1 -1 = -2, 1 1 = 2.
We recall some relations which serve to order the symmetrized semiring S. For x, y ∈ S we set

x > y ⇔ x y ∈ T >O x y ⇔ x y ∈ T >O ∪ T • x ≥ y ⇔ x > y ∨ x = y (4)
For a ∈ S, we set

U(a) = [ |a|, |a|] = {x ∈ T ± | |a| ≤ x ≤ |a|} for a ∈ T • {a} else . (5)
We extend this to vectors by setting

U(v) = i∈[d] U(v i ).
Example 2.2. One has 2 > 3 but •4 and 3 are incomparable via '>' since

•4 3 = •4 ⊕ 3 = •4 = 4 • 4.
Though it holds •4 3 and 3 •4 and 3 •4 showing, e.g., that ' ' is not anti-symmetric.

The signed tropical numbers are equipped with the order topology induced by the strict order <. With this, T ± is homeomorphic to R with the usual order topology via

slog : R → T ± , slog(x) =      log(x) for x > 0 log(|x|) for x < 0 O for x = 0 .
This extends to T d ± via the product topology, in particular T d ± is homeomorphic to R d . Hence, we can use all topological properties of R d also for vectors of signed tropical numbers.

Recall that a partial order on some set S is dense if for every two elements x, y ∈ S such that x < y there exists z ∈ S that satisfies x < z < y. With this, the order < on T ± is dense.

2.1. Halfspaces. The different versions of halfspaces form the building blocks for our convexity notions.

H(a) = x ∈ T d ± a 0 x ∈ T • , (6)
the open signed (affine) tropical halfspace by

H + (a) = x ∈ T d ± a 0 x ∈ T >O , (7)
the closed signed (affine) tropical halfspace by

H + (a) = x ∈ T d ± a 0 x ∈ T >O ∪ T • , (8)
and the semi-closed signed (affine) tropical halfspace by

H + (a) = x ∈ T d ± a 0 x ∈ T ≥O . (9)
If a 0 = O, we call a tropical halfspaces linear instead of affine.

We denote

H -(a) = H + ( a) and H -(a) = H + ( a). Furthermore, given J ⊆ [d], we say that a tropical halfspace H + (a) is of type J if J = { i ≥ 1 | a i ∈ T >O }.
To express H + (a) using a more classical notation, we recall that max ∅ = -∞.

(|a i | + |x i |) ≥ max a - 0 , max tsgn(xi) =tsgn(ai) (|a i | + |x i |) , (10)
where (a + 0 , a - 0 ) = (a 0 , -∞) for a 0 ∈ T ≥O and (a + 0 , a - 0 ) = (-∞, |a 0 |) otherwise. We have x ∈ H + (a) if and only if the inequality in [START_REF] Xavier Allamigeon | Log-barrier interior point methods are not strongly polynomial[END_REF] is strict. The following lemma gathers the basic topological properties of tropical halfspaces. Proof. Equation [START_REF] Xavier Allamigeon | Log-barrier interior point methods are not strongly polynomial[END_REF] shows that the restriction of H + (a) to any closed orthant of

T d ± is closed. Therefore, H + (a) is closed and H + (a) = T d ± \ H - (
a c O ∧ b ⊕ c O ⇒ a ⊕ b ⊕ c O ∧ a ⊕ b c O.
Proof. We distinguish two cases.

b ∈ T ± or a ⊕ b ∈ T • . Lemma 2.7. Let u, v, w ∈ T ± , q ∈ U(v ⊕ w), p ∈ U(u ⊕ v). (a) U(u ⊕ q) ⊆ U(u ⊕ v ⊕ w) and U(p ⊕ w) ⊆ U(u ⊕ v ⊕ w), (b) U(u ⊕ q) ∩ U(p ⊕ w) = ∅.
Proof. For (a): By commutativity, it suffices to prove the first inclusion. For v⊕w ∈ T ± , we have q = v ⊕ w and therefore U(u ⊕ q) = U(u ⊕ v ⊕ w). Otherwise, the claim follows from the definition of U(.) using

|u ⊕ q| = |u| ⊕ |q| ≤ |u| ⊕ |u ⊕ w| = |u ⊕ v ⊕ w| by distinguising |u| > |v ⊕ w| and |u| ≤ |v ⊕ w|. For (b): Case 1 (U(v ⊕ w) or U(u ⊕ v) is singleton.) Assume without loss of generality that U(v ⊕ w) is a singleton. This implies U(u ⊕ q) = U(u ⊕ v ⊕ w) ⊇ U(p ⊕ w),
where the inclusion follows from (a).

Case 2 (v ⊕ w and u ⊕ v are balanced.) Here, we have u = v = w. This means we have either p = w and, hence,

U(p ⊕ w) = U(u ⊕ v ⊕ w), or p ⊕ w = w = u.
The same applies to q and u. Therefore, in each of the four combinations of the two possibilities, one has a non-empty intersection.

As U(.) is defined componentwise, we obtain a higher-dimensional extension of Lemma 2.7(b).

Corollary 2.8. For u, v, w ∈ T d ± and q ∈ U(v ⊕ w), p ∈ U(u ⊕ v), one gets U(u ⊕ q) ∩ U(p ⊕ w) = ∅. Lemma 2.9 ([42, Lemma 3.5(b)]). If a ∈ U(x), b ∈ U(y), and c ∈ T ± , then U(c a ⊕ b) ⊆ U(c x ⊕ y).
Observation 2.10. Let a, b, µ ∈ T ± and s, t ∈ S with a ∈ U(s) and b ∈ U(t). Then µ a ∈ U(µ s) and a ⊕ b ∈ U(s ⊕ t).

Left sum.

The following notion of one-sided addition of tropical signed numbers is crucial for our study of convexity over signed tropical numbers. Definition 2.11. Given two tropical numbers x, y ∈ S we define their left sum as

x y = x if |x| = |y|, x ⊕ y otherwise.
We extend this definition to vectors x, y ∈ S d by putting (x y

) k = x k y k for every k ∈ [d].
Remark 2.12. For the special case of vectors with entries in {O, 0, 0}, the left sum operation is just the composition of sign vectors in an oriented matroid [START_REF] Björner | Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications[END_REF]. The generalization to signed vectors with real entries already appears for the description of real Bergman fans [START_REF] Celaya | Lattice points, oriented matroids, and zonotopes[END_REF] and even more generally in the context of matroids over tracts [START_REF] Anderson | Vectors of matroids over tracts[END_REF]Section 6.2]. From this point of view, later on in Proposition 3.17 we will see an extension of the elimination property of oriented matroids. We will discuss this connection further in upcoming work.

The left sum operation is not commutative as one can see on the example 0 ⊕ ( 0) = 0 = 0 = ( 0) ⊕ 0. Nevertheless, it is associative and compatible with the order on T ± . Observation 2.13. For every x, y, z ∈ T

d ± we have (a) (x y) z = x (y z) (b) |x y| = |x| ⊕ |y|. Lemma 2.14. Let a 1 , b 1 , a 2 , b 2 ∈ T ± . (a) If a 1 ≤ b 1 and a 2 ≤ b 2 , then a 1 a 2 ≤ b 1 b 2 . (b) if a 1 < b 1 and a 2 < b 2 , then a 1 a 2 < b 1 b 2 . (c) if a 1 ≥ b 1 and a 2 ≥ b 2 , then a 1 a 2 ≥ b 1 b 2 (d) if a 1 > b 1 and a 2 > b 2 , then a 1 a 2 > b 1 b 2 . Proof. It is enough to prove (a) and (b) as (c),(d) follow by replacing (a 1 , a 2 , b 1 , b 2 ) with ( a 1 , a 2 , b 1 , b 2 ). Hence, we suppose that a 1 ≤ b 1 and a 2 ≤ b 2 (or a 1 < b 1 and a 2 < b 2 ). Let x = a 1 a 2 and y = b 1 b 2 . If (x, y) ∈ {(a 1 , b 1 ), (a 2 , b 2 )}, then the claim is trivial. If (x, y) = (a 1 , b 2 ), then we have |b 2 | ≥ |b 1 | and |a 1 | ≥ |a 2 |. If b 2 ≥ O, then b 2 ≥ b 1 ≥ a 2 (or b 2 > a 1 if a 1 < b 1 ). If b 2 < O, then a 2 ≤ b 2 < O implies that |a 1 | ≥ |a 2 | ≥ |b 2 | ≥ |b 1 |. Therefore, a 1 ≤ b 1 implies that a 1 ≤ O. Since |a 1 | ≥ |a 2 |, we get a 1 ≤ a 2 ≤ b 2 (or a 1 < b 2 if a 2 < b 2 ). If (x, y) = (a 2 , b 1 ), then we have |a 2 | ≥ |a 1 |, |b 1 | ≥ |b 2 |
, and an analogous proof as above applies.

n ∈ T ± , x (2) 1 , . . . , x (2)
n ∈ T ± be such that a ≤ x (1) 1 . . . x (1) n and b ≤ x

(2) 1 . . . x (2) n . Then a ⊕ b ≤ w 1 . . . w n for all w 1 ∈ U(x

(1) 1 ⊕ x (2) 1 ), . . . , w n ∈ U(x (1)
n ⊕ x (2)
n ). By multiplying with 0, the implication also holds if one replaces '≤' by '≥'.

Proof. Let p, q ∈ [n] be the smallest indices such that x

(1) 1 . . . x (1) n = x (1) p and x (2) 1 . . . x (2) n = x (2)
q . Then Lemma 2.14 implies that a b ≤ x

(1) p x (2)
q and b a ≤ x

q , x (2) q x (1) p .
By definition, for any s, t ∈ T ± , the interval U(s ⊕ t) has the boundary points s t and t s. There is a choice of orders τ 1 , . . . , τ n ∈ Sym(2) which minimizes the expression x

(τi(1)) i x (τi(2)) i
. By the former observation and Lemma 2.14 it is smaller than w 1 . . . w n for all w 1 ∈ U(x

(1) 1 ⊕ x (2) 1 ), . . . , w n ∈ U(x (1)
n ⊕ x (2) n ). Let x ( ) j
for j ∈ [n] and ∈ {1, 2} be the entry which defines the value of this expression, which means the first summand with maximal absolute value. If = 1 then j = p, otherwise j = q. In either case, we get x

(τ (1)) i x (τ (2)) i = x (1) p x (2) q or x (τ (1)) i x (τ (2)) i = x (2) q x (1)
p . In particular, we obtain

w 1 . . . w n ≥ x (τ (1)) i x (τ (2)) i ≥ min x (1) p x (2) q , x (2) q x (1) p ≥ a ⊕ b . Example 2.16. Let a = 0, b = 0, x (1) 1
= O, x (1) 2
= 0, x

= 0, x (2) 1
= O,

w 1 = 0, w 2 = 0. Then a ≤ x (1) 1 x (1) 2 , b ≤ x (2) 1 x (2) 2 , w 1 = x (1) 1 ⊕ x (2) 1 , w 2 = x (1) 2 ⊕ x (2)
2 , but 0 = a b > w 1 w 2 = 0. This example shows that the assumption tsgn(a) = tsgn(b) cannot be omitted in the previous lemma.

Flavors of signed convexity

In [START_REF] Loho | Signed Tropical Convexity[END_REF], a notion of convexity for signed tropical numbers was introduced. We revisit this notion under the name TO-convexity and give several new insights. Furthermore, we establish a second notion of convexity for signed tropical numbers in an equally natural way.

Recall that a cone is a set X ⊆ T d ± such that λ X ⊆ X for all λ ∈ T >O . Based on the two convexity notions we will also consider cones over the respective convex sets.

We will often identify a finite set with the columns of a matrix and vice versa.

3.1. TO-convexity. We collect several results from [START_REF] Loho | Signed Tropical Convexity[END_REF]. Note that TO-convexity appears under the name 'signed tropical convexity' there.

The TO-convex hull of a matrix A ∈ T d×n For a vector s ∈ S d with possibly balanced entries, the set U(s) ⊂ T d ± can be seen as a hypercube. If s has k entries in T • \ {O}, we say that the hypercube U(s) has dimension k. Furthermore, we say that U(s ) is a face of U(s) if s k = s k for every k such that s k ∈ T ± and |s k | = |s k | for every other k. A face of dimension zero is called a vertex of U(s). In particular, a hypercube of dimension k has 2 k vertices.

± is conv TO (A) =    U(A x) x ∈ T n ≥O , j∈[n] x j = 0    ⊆ T d ± . ( 11
) A set M ⊆ T d ± is TO-convex if conv TO (T ) ⊆ M for all finite T ⊆ M .
We recall a crucial property of TO-convexity.

Lemma 3.1 ([42, Proposition 3.6]). A subset U ⊆ T d ± is TO-convex if and only if conv TO ({p, q}) is contained in U for all p, q ∈ U .
The TO-convex hull of a finite set can also be given as intersection of open tropical halfspaces. This is the origin of the name 'TO-convex' derived from 'tropical open'. Furthermore, it motivates the definition of the TC-convex hull ('tropical closed') in Section 3.2. It turns out that TO-convexity has rather well-behaved separation properties: it fulfills the Pasch property and the Kakutani property. For this, we need the notion of a TO-hemispace, this is a TO-convex subset X ⊆ T d ± for which also T d ± \ X is TO-convex. A similar statement was proven for the unsigned case in [START_REF] Horvath | Some general principles in tropical convexities[END_REF].

Theorem 3.3. TO-convexity has the Pasch property and the Kakutani property. In other words,

(i) (Pasch property) if (a, b 1 , b 2 , c 1 , c 2 ) ∈ T d ± are such that b 1 ∈ conv TO (a, c 1 ), b 2 ∈ conv TO (a, c 2 ), then conv TO (c 1 , b 2 ) ∩ conv TO (c 2 , b 1 ) = ∅; (ii) (Kakutani property) if A, B ⊆ T d
± are two disjoint TO-convex sets, then there exists a TO-hemispace

X ⊆ T d ± such that A ⊆ X and B ⊆ (T d ± \ X).
Proof. For (i), we follow the proof of the Pasch property over arbitrary ordered fields, see [

s 1 ⊕ s1 = 0 , s 2 ⊕ s2 = 0 (12)
and We define

b 1 ∈ U(s 1 a ⊕ s1 c 1 ) and b 2 ∈ U(s 2 a ⊕ s2 c 2 ) . (13)
t 1 = s 2 (s 1 ⊕ s1 s 2 ) -1 t1 = s 1 s2 (s 1 ⊕ s1 s 2 ) -1 t 2 = s1 s 2 (s 1 ⊕ s1 s 2 ) -1 t2 = s 1 (s 1 ⊕ s1 s 2 ) -1 . (14)
Using ( 12), we obtain

s 2 ⊕ s 1 s2 = s 1 s 2 ⊕ s1 s 2 ⊕ s 1 s2 = s 1 s 2 ⊕ s 1 s2 ⊕ s1 s 2 = s 1 ⊕ s1 s 2 ,
which implies

t 1 ⊕ t1 = (s 2 ⊕ s 1 s2 ) (s 1 ⊕ s1 s 2 ) -1 = 0 .
Note that we also have t 2 ⊕ t2 = 0. Hence, we obtain

U(t 1 b 1 ⊕ t1 c 2 ) ⊆ conv TO (b 1 , c 2 ) and U(t 2 c 1 ⊕ t2 b 2 ) ⊆ conv TO (c 1 , b 2 ) .
Multiplying by the denominator s 1 ⊕ s1 s 2 in (14), we see that the intersection conv

TO (b 1 , c 2 ) ∩ conv TO (c 1 , b 2 ) is not empty if U(s 2 b 1 ⊕ s 1 s2 c 2 ) ∩ U(s 1 s 2 c 1 ⊕ s 1 b 2 ) = ∅ .
Scaling (13) to

s 2 b 1 ∈ U(s 2 s 1 a ⊕ s 2 s1 c 1 ) and s 1 b 2 ∈ U(s 1 s 2 a ⊕ s 1 s2 c 2 )
allows to apply Corollary 2.8 by setting

v = s 1 s 2 a, q = s 2 b 1 , w = s1 s 2 c 1 , p = s 1 b 2 , u = s 1 s2 c 2 .
To prove (ii), we use [24, Theorem 5], which shows that the Pasch property and the Kakutani property are equivalent for 2-ary convexities (see also [41, Theorem 4.1] for a more recent improvement). TO-convexity is 2-ary by Lemma 3.1. This concludes the proof.

Example 3.4. Let a = (0, 0), b 1 = (O, 0), b 2 = (0, 0), c 1 = ( 0, 0), and c 2 = (O, 1). Figure 3 depicts this configuration of points. The TO-convex hull of a and c 1 is the straight line connecting them, so b 1 ∈ conv TO (a, c 1 ). Furthermore, (-1) c 2 ⊕ a = (0, •0), so b 2 ∈ conv TO (a, c 2 ). One gets that the TO-convex hull of b 1 and c 2 is the dashed line connecting them and the TO-convex hull of c 1 and b 2 is just the shaded whole square. Their non-empty intersection visualizes the Pasch property in this example. For technical reasons, we first only define the TC-convex hull of two points, and then extend it to arbitrary sets using these TC-convex line segments. Later it turns out that, for an arbitrary finite set, this is actually the same as just taking the intersection of all closed tropical halfspaces containing it.

For basics on general convexity, we refer to [START_REF] Van De | Theory of Convex Structures[END_REF]. We will mainly rely on the notion of a convexity structure [51, §1.1]. In particular, we are interested in convexity structures induced by an interval operator [51, §4.1]. Definition 3.5. We define the TC-convex hull of two points x, y ∈ T d ± as conv TC (x, y) =

x,y∈H

+ (a) H + (a) . (15)
Sets of this form are TC-convex intervals.

Definition 3.6. We say that a set X ⊂ T d ± is TC-convex if conv TC (x, y) ⊆ X for all x, y ∈ X.

We have the following desirable properties.

Corollary 3.7. The TC-convex sets form a convexity structure. In particular, TC-convex sets are closed by intersection and nested union.

The definition of TC-convexity directly gives two important classes of TC-convex sets.

Corollary 3.8. A closed signed affine tropical halfspace and a signed affine tropical hyperplane is TC-convex. TC-convex intervals, i.e. sets of the form conv TC (x, y), for x, y ∈ T d ± , are TC-convex.

Proof. Right from the definition we get that closed signed affine tropical halfspaces are TC-convex. The TC-convexity of the other sets follows from the intersection property.

Corollary 3.7 allows us to extend the hull operator routinely to arbitrary sets

M ⊆ T d ± by setting conv TC (M ) = M ⊆S,S TC-convex S .
In particular, this convexity structure is 'domain finite' by [START_REF] Van De | Theory of Convex Structures[END_REF]Theorem 1.3] which means the following. Corollary 3.9. For an arbitrary set M ⊆ T d ± we have

conv TC (M ) =
T ⊆M,T finite conv TC (T ) .

Corollary 3.10. For an arbitrary set M ⊆ T d ± we have conv TC (M ) ⊆ conv TO (M ). Furthermore, each TO-convex set is also TC-convex.

Proof. For two point x, y ∈ T d ± , [START_REF] Loho | Signed Tropical Convexity[END_REF]Theorem 5.4] implies that conv TO (x, y) is an intersection of finitely many closed halfspaces. Now, combining with the Definition 3.5 yields conv TC (x, y) ⊆ conv TO (x, y). Therefore, by definition of a TCconvex set via TC-convex intervals (Definition 3.6), each TO-convex set is also TC-convex. Hence, using the extension of the hull operators for TO-convexity and TC-convexity to not necessarily finite sets gives the first claim. To describe the TC-convex hull explicitly, we need significantly more tools than for the TO-convex hull.

x 1 x 2 (a) convTO((0, 0), ( -2, -2)) x 1 x 2 (b) convTO((0, 0), ( -3, -2)) x 1 x 2 (c) convTC((0, 0), ( -2, -2)) x 1 x 2 (d) convTC((0, 0), ( -3, -2))
Definition 3.11. Given a set of points X = {x 1 , . . . , x n } ∈ T d ± , we define Vert(X) = Vert(x 1 , . . . , x n ) := x σ(1) x σ(2) . . . x σ(n) σ ∈ Sym(n) ⊂ T d ± ,
where Sym(n) denotes the group of permutations of [n]. Furthermore, we denote by Faces(X) := Faces(x 1 , . . . , x n ) the union of all faces of U(

x 1 ⊕ • • • ⊕ x n ) (considering it as a hypercube) whose vertices belong to Vert(x 1 , . . . , x n ).
While the convex structure of cancellation for TO-convexity only depends on the balanced outcome, the non-associative structure of TC-convexity is far more subtle. Therefore, it is not enough to apply a univariate operator like U(.) but we have to use the multivariate operator Faces(.). Though, equipped with this tool, we will be able to describe the TC-hull also in terms of an analog of convex combinations.

Directly from the definition and Observation 2.13 we get the next.

Corollary 3.12. The set Vert(x 1 , . . . , x n ) is a subset of vertices of the hypercube

U(x 1 ⊕ • • • ⊕ x n ).
In particular, it contains at most 2 d points.

Example 3.13. If we only consider two points, there are essentially three cases. We illustrate them on small examples. In the first case, the sum does not have a balanced entry.

Vert 0 0 , 1 -1 = 1 0 = Faces 0 0 , 1 -1 .
In the second case, we have

Vert 0 0 , 1 0 = 1 0 , 1 0 which yields Faces 0 0 , 1 0 = 1 s : s ∈ [ 0, 0] .
In the last case, there is more than one balanced entry

Vert 0 0 , 0 0 = 0 0 , 0 0 = Faces 0 0 , 0 0 .
Proposition 3.14. We have

conv TC (x, y) = { Faces(λ x, µ y) | λ, µ ∈ T ≥O , λ ⊕ µ = 0} . ( 16
)
Proof. By Corollary 3.10, we know that conv TC (x, y) ⊆ conv TO (x, y). With [START_REF] Xavier Allamigeon | What tropical geometry tells us about the complexity of linear programming[END_REF], this implies that it suffices to consider which part of U(λ x ⊕ µ y) is contained in conv TC (x, y) for each pair λ, µ ∈ T ≥O , λ ⊕ µ = 0. Note that, for different such pairs λ 1 , µ 1 and λ 2 , µ 2 , the sets U(λ 1 x ⊕ µ 1 y) and U(λ 2 x ⊕ µ 2 y) are either disjoint or identical. Therefore, it is enough to consider the sets U(λ x ⊕ µ y) for a fixed pair λ, µ. Hence, fixing such a pair, we distinguish three cases.

For a = (a 0 , ā) ∈ T d+1 ± let H + (a) be an affine halfspace containing x and y. This means that

λ a 0 ⊕ ā λ x O and µ a 0 ⊕ ā µ y O . (17)
Recall that at least one of λ, µ is 0. Case 1 (λ x ⊕ µ y has no balanced entry. ) Adding the relations in (17) yields

a 0 ⊕ ā (λ x ⊕ µ y) O .
That already concludes this case, where indeed λ x ⊕ µ y = λ x µ y = µ y λ x.

Case 2 (λ x⊕µ y has exactly one balanced entry. ) Without loss of generality, we assume that the d-th entry is balanced. Reformulating [START_REF] Baker | Matroids over partial hyperstructures[END_REF] implies

λ a 0 ⊕ d-1 =1 a λ x λ a d x d µ a 0 ⊕ d-1 =1 a µ y µ a d y d .
Using b := λ x d = µ y d , the side-wise addition of the relations yields

a 0 ⊕ d-1 =1 a (λ x ⊕ µ y ) a d ⊕ •b .
Therefore, each point in

{(λ x 1 ⊕ µ y 1 , . . . , λ x d-1 ⊕ µ y d-1 , s) : s ∈ [ |b|, |b|]}
is contained as claimed. Furthermore, the latter set is indeed the line between λ x µ y and µ y λ x. Case 3 (λ x ⊕ µ y has more than one balanced entry. ) Without loss of generality, exactly the coordinates k +1 to d of λ x⊕µ y are balanced. Then [START_REF] Baker | Matroids over partial hyperstructures[END_REF] amounts to

λ a 0 ⊕ k =1 a λ x ⊕ d =k+1 a λ x O µ a 0 ⊕ k =1 a µ y ⊕ d =k+1 a µ y O .
Using Lemma 2.6 in the same way as we did for Case 2, we obtain that λ x µ y and µ y λ x are also contained in H + (a).

Up until now, we have proven the first inclusion. Now, we set b

= λ x = µ y for ∈ [d] \ [k]
. We look at the halfspaces

H + ( 0, O, . . . , O, 1 b -1 k+1 , . . . , d-k b -1 d ) (18)
for each ∈ { , ⊕} d-k \ {( , . . . , ), (⊕, . . . , ⊕)}. By putting x and y in the corresponding relation, we see that they are both contained. Now let w 1 = λ x µ y and w 2 = µ y λ x. Note that w 1 and x have the same sign pattern on the coordinates k + 1 up to d, and the same for w 2 and y, respectively. We pick any point

z ∈ U(λ x 1 ⊕ µ y 1 , . . . , λ x k ⊕ µ y k , •b k+1 , . . . , •b d ) \ {w 1 , w 2 }
Case 3a (z has the same sign pattern as w 1 or w 2 . ) Without loss of generality, we assume that z has the same sign pattern as w 1 . Then there is a coordinate of z, say the (k + 1)st, such that

|z k+1 | < |λ x k+1 | = |µ y k+1 |. We let ( 1 , . . . , d-k ) = (tsgn(z k+1 ), tsgn(z k+2 ), . . . , tsgn(z d-k )) As |z k+1 |b k+1 | -1 | < 0, we get 0 ⊕ 1 |b k+1 | -1 z k+1 ⊕ • • • ⊕ d-k |b d | -1 z d-k < O.
Hence, there is a halfspace among those in ( 18) not containing z.

Case 3b (z has a different sign pattern from w 1 and w 2 . ) We let

( 1 , . . . , d-k ) = ( tsgn(z k+1 ), . . . , tsgn(z d-k ))
be the negative of the sequence of signs. Because of the relation

0 ⊕ 1 |b k+1 | -1 z k+1 ⊕ • • • ⊕ d-k |b d | -1 z d-k < O
there is a halfspace among those in ( 18) not containing z, as these include all sign patterns except for those of x and y.

Example 3.15. Figure 5 compares TC-intervals with TO-intervals in a plane. If we take x = (0, 0) and y = ( -3, -2), then for every λ, µ ∈ T ≥O such that λ ⊕ µ = 0 we have Faces(λ x, µ y) = U(λ x ⊕ µ y). In particular, in this case the intervals coincide, conv TO (x, y) = conv TC (x, y). If we take y = ( -2, -2) instead, then the equality no longer holds. Indeed, for λ = -2, µ = 0 we have

U(λ x ⊕ µ y) = U(•2, •2) = [ -2, -2] × [ -2, -2] and Faces(λ x, µ y) = {( -2, -2), (-2, -2)}.
The next example shows that the TC-convexity does not have the Pasch property or the Kakutani property. Nevertheless, in Section 5 we will show that the TCconvexity satisfies a weaker separation property.

2 ∈ Faces(a, -1 c 2 ), so that b 1 ∈ conv TC (a, c 1 ), b 2 ∈ conv TC (a, c 2 ). Nevertheless, the interval conv TC (c 1 , b 2 ) is reduced to two points, conv TC (c 1 , b 2 ) = {c 1 , b 2 }, while conv TC (c 2 , b 1 ) = {O} × [ 0, 1]. In particular, the intersection conv TC (c 1 , b 2 ) ∩ conv TC (c 2 , b 1
) is empty, so the TC-convexity does not have the Pasch property. This also shows that the TC-convexity does not have the Kakutani property: there is no TC-hemispace that separates conv TC (c 1 , b 2 ) from conv TC (c 2 , b 1 ), because the point a could not belong to either side of this hemispace. Even further, we note that conv TC (b 1 , c 2 ) = conv TO (b 1 , c 2 ). Hence, this example shows that the TO-convexity and TC-convexity do not satisfy the Kakutani property for pairs of convexities studied in [START_REF] Law | Separation properties of convexity spaces[END_REF].

Proposition 3.17. A set M ⊆ T d
± is TC-convex if and only if it is closed under the following two operations: (i) for x, y ∈ M and λ, µ ∈ T ≥O with λ ⊕ µ = 0, we have λ x µ y ∈ M ;

(weighted left sum)

(ii) if (u, v, w), (u, v, w) ∈ T k ± × T ± × T d-k-1 ± for k ∈ [d] 0 are contained in M then {u} × [ |v|, |v|] × {w} ⊆ M. (local elimination)
Proof. By Proposition 3.14, a TC-convex set fulfills these two properties. It suffices to prove that the TC-convex hull of two points can be generated by these two operations. So we fix two points x, y ∈ M ⊆ T d ± . Let λ, µ ∈ T ≥O with λ ⊕ µ = 0. By the first property, Vert(λ x, µ y) is contained in M . If Vert(λ x, µ y) do not form the vertices of a face of the respective hypercube, it equals Faces(λ x, µ y). Otherwise Faces(λ x, µ y) is the line segment arising from the second property. Now, Proposition 3.14 concludes the proof.

Example 3.18. For (p, r), (q, r)

∈ T ± × T d-1 ± with p < q, one gets conv TC ({(p, r), (q, r)}) = [p, q] × {r}. ( 19
)
To see this, we first assume that p < q have the same sign, w.l.o.g. both are positive.

Then [p, q] × {r} = { (p, r) λ (q, r) | O ≤ λ ≤ 0}.
Otherwise, assume that p < O and |p| < q. Then ( p, r) = (q -|p|) (q, r) (p, r) and the claim follows with the local elimination property. The other cases follow by suitably adapting the signs and scalars.

For p, q ∈ T d ± with p ≤ q (defined component-wise), we denote

[p, q] = x ∈ T d ± p i ≤ x i ≤ q i ∀i ∈ [d] , (p, q) = x ∈ T d ± p i < x i < q i ∀i ∈ [d] . Example 3.19. For p, q ∈ T d ± with p ≤ q, one gets conv TC ({p 1 , q 1 } × • • • × {p d , q d }) = [p, q]. (20)
To see this, we can fix all but one coordinate and then iteratively use Example 3.18. Note that it also holds that

conv TO ({p 1 , q 1 } × • • • × {p d , q d }) = [p, q]. (21)
Let C be a subcomplex of the faces of [-1, 1] d with the property: if all vertices of a face are contained in C then so is the face.

For ∼ ∈ {≤, ≥} d , we define

x ∼ y ⇔ (x k ∼ k y k for all k ∈ [d]). Lemma 3.20. A point z ∈ [-1, 1] d is contained in C if
vertex v of F which is not contained in C. With v we associate a vector ∼ (v) ∈ {≤, ≥} d by converting -1 to ≤ and +1 to ≥. Then v is the unique vertex of [-1, 1] d with v ∼ (v) z because there is a unique choice of τ ∈ {-1, 1} with τ ∼ (v) k z k for k ∈ K. As v is not a vertex of C this concludes the first direction.
On the other hand, if a point z is contained in C then also the face

F is contained in C. Let ∼ ∈ {≤, ≥} d be arbitrary. We define a vertex v of [-1, 1] d by v = z for ∈ I ∪ J and v k = 1 if ∼ k equals ≥, -1 if ∼ k equals ≤ for k ∈ K. By construction, v is a vertex of F
∈ Vert(x 1 , . . . , x n ) such that y k ∼ k w k for all k ∈ [d].
Proof. By Definition 3.11, the set Faces(x 1 , . . . , x n ) forms a subcomplex of the faces of the (stretched) hypercube U(x 1 ⊕• • •⊕x n ) exactly with the property required of C in Lemma 3.20. As Vert(x 1 , . . . , x n ) select exactly the vertices of this subcomplex, Lemma 3.20 gives the required equivalence.

Fundamental properties of TC

-convex sets. Fix finite sets X, Y ⊆ T d ± . Lemma 3.22. Let s, t ∈ S with |s| = | X| and |t| = | Y | such that U(s) ⊆ Faces(X) and U(t) ⊆ Faces(Y ). Then U(s t) ⊆ Faces(X ∪ Y ).
Proof. Note that, by definition of s, we have the inclusion U(•s) ⊆ U( X) and further, using U(s) ⊆ Faces(X), that every vertex of U(s) is a vertex of U( X). Analogously, every vertex of U(t) is a vertex of U( Y ).

Therefore as part of Faces( X), all vertices of U(s) are of the form X σ for some ordering σ of X, and analogously, all vertices of U(t) are of the form Y τ for some ordering τ of Y . Now, we consider a vertex u of U(s t). We partition [d] in two sets, I := {i : |u i | = |s i |} and its complement.

By definition of the left sum, u is given by (signed versions of) the entries of s on I and (signed versions of) the entries of t on [d] \ I. Let v be a vertex of U(s) which agrees with u on I and let w be a vertex of U(t) which agrees with u on [d] \ I. This just means that u = v w. Furthermore, by construction, the latter left sum lies in Vert(X ∪ Y ). As u belongs to Vert(X ∪ Y ), we get the inclusion U(s t) ⊆ Faces(X ∪ Y ) by definition of Faces(.). Lemma 3.23. The set Faces(X) is TC-convex.

In particular, we have Faces(X) = conv TC (Vert(X))

Proof. Let x = | X| and let x σ for σ ∈ { , ⊕} d denote a signed version of x.

Recall that the points Vert(X) are of the form x σ where σ ranges over a subset Σ of { , ⊕} d . Let H + τ = H + 0, (x τ 1 ) -1 , . . . , (x τ d ) -1 be the halfspace with its 'apex' at the point x τ for τ ∈ { , ⊕} d containing O and H - τ the opposite closed one. Then the intersection τ ∈{ ,⊕} d H + τ exactly yields the hypercube U(•x). If we further intersect this with all halfspaces H - τ for τ ∈ { , ⊕} d \Σ we get Faces(X) as H - τ exactly cuts off all faces of the cube containing x τ with τ not in Σ. Hence, it is TC-convex as an intersection of TC-convex sets. Now, we look at a face F of U(•x) for which all vertices V are contained in Vert(X). Applying Proposition 3.14 iteratively on pairs of points, which only differ in the sign of one component, we get Faces(V ) = F ⊆ conv TC (V ). Ranging over all faces in Faces(X) yields Faces(X) ⊆ conv TC (X). But as Faces(X) is TC-convex, we get an equality. Proposition 3.24. Let X ⊆ T d ± be an n-element set interpreted as a matrix. Then

conv TC (X) = Faces(X diag(λ)) λ ∈ T n ≥O , i λ i = 0 . ( 22
)
Proof. Let x 1 , . . . , x n ∈ X and λ 1 , . . . , λ n ∈ T ≥O be such that i λ i = 0. We will start by showing that y = λ 1 x 1 . . . λ n x n belongs to conv TC (X). The proof goes by induction over n.

The claim is trivial for n = 1. For higher n, let µ = i>1 λ i . The claim is trivial if µ = O. Otherwise, let µ i = λ i -µ for every i > 1. Then, we have λ 1 x 1 . . . λ n x n = λ 1 x 1 µ (µ 2 x 2 . . . µ n x n ). By the induction hypothesis, the point z = µ 2 x 2 . . . µ n x n belongs to conv TC (X). Therefore, the point y = λ 1 x 1 µ z belongs to conv TC (X) by Proposition 3.14. Thus, we have proven that every point of the form λ 1 x 1 . . . λ n x n belongs to conv TC (X). In particular, the set Vert(X diag(λ)) belongs to conv TC (X). Hence, Lemma 3.23 implies that Faces(X diag(λ)) = conv TC (Vert(X diag(λ))) is contained in conv TC (X).

To finish the proof, we will show that the set on the right-hand side of ( 22) is TCconvex. To do so, suppose that a ∈ Faces(X diag(λ)) and b ∈ Faces(X diag(µ)) for some λ i , µ i ∈ T ≥O and i λ i = i µ i = 0. Further, let α, β ∈ T ≥O be such that α ⊕ β = 0. By Lemma 3.22, the set Vert(α a, β b) is included in Faces(α X diag(λ) ∪ β X diag(µ)). Hence, Faces(α a, β b) is also included in this set by Lemma 3.23. Thus, by Proposition 3.14, conv TC (a, b) is included in the set defined on the right-hand side of [START_REF] Briec | Halfspaces and Hahn-Banach like properties in Bconvexity and max-plus convexity[END_REF] since Faces(α

X diag(λ) ∪ β X diag(µ)) = Faces(X diag(ν)) with ν = α diag(λ) ⊕ β diag(µ), which fulfills ν ∈ T n ≥O and i ν i = 0.
Using the representation of the convex hull as union of finite convex hulls stated in Corollary 3.9 we get the following.

Corollary 3.25. If X ⊆ T d ± , then conv TC (X) = Faces(X diag(λ)) λ ∈ T X ≥O , i λ i = 0, | supp(λ)| < +∞ .
We now give estimates on the Carathéodory-number of TC-convexity. The core case for this is the representation of vertices from a small set of generators.

Lemma 3.26. Let X = {x 1 , . . . , x n } ⊆ T d ± . Then there is a subset Y ⊆ X with |Y | ≤ d2 d and Vert(X) ⊆ Vert(Y ), hence, Vert(X) = Vert(Y ). Proof. Let y ∈ Vert(X) and let σ ∈ Sym(n) such that y = x σ(1) . . . x σ(n) . For every coordinate k ∈ [d] let j k ∈ [n] be the smallest number such that y k = (x σ(j k ) ) k and let J y = { σ(j k ) | k ∈ [d]} ⊆ [n]. Note that |J y | ≤ d. Now, let I y = (i 1 , .
. . , i |Jy| ) be the ascending sequence of the elements in J y . Observe that for any set J with J y ⊆ J ⊆ [n], it holds y = x i1 . . . x |Jy| i∈J\Jy x i for any order of the summands indexed by J \ J y .

Finally, we define J to be the union y∈Vert(X) J y . By the above reasoning, we have |J| ≤ d2 d and Vert(X) ⊆ Vert(Y ). As each left-sum of the elements in Y already defines a point for which the absolute values of the components equal the components of • X, we also get the reverse inclusion Vert(Y ) ⊆ Vert(X).

Proposition 3.27. If X ⊆ T d ± , then conv TC (X) = Faces(X diag(λ)) λ ∈ T X ≥O , i λ i = 0, | supp(λ)| ≤ c d ,
where

c d = d2 d + 1.
Proof. Let y ∈ conv TC (X). By Corollary 3.25 there is some λ ∈ T X ≥O with i λ i = 0 such that y ∈ Faces(X diag(λ)).

Let j 0 be an index with λ j0 = 0. We derive a new coefficient vector µ from λ with µ j0 = 0, Vert(X diag(λ)) = Vert(X diag(µ)) and | supp(µ)| ≤ c d = d2 d + 1. Lemma 3.26 implies that we can achieve this by setting all but c d entries of λ to O.

With Lemma 3.23, we obtain

y ∈ Faces(X diag(λ)) = conv TC (Vert(X diag(λ))) ⊆ conv TC (Vert(X diag(µ)) = Faces(X diag(µ)) .
Taking the subset Y of X given by the support of µ, one sees y ∈ conv TC (Y ).

While TC-convexity extends the 'usual' tropical convexity whose Carathéodory number is d + 1 as discussed in [START_REF] Gaubert | Carathéodory, Helly and the others in the max-plus world[END_REF], we already get an exponential lower bound from a simple example.

(X) = { λ x | λ ∈ T ≥O , x ∈ conv TC (X)} . Lemma 3.30. If X ⊆ T d ± , then cone TC (X) = Faces(X diag(λ)) λ ∈ T X ≥O , | supp(λ)| < +∞ .
Proof. By Proposition 3.24 we have the equality

cone TC (X) = µ Faces(X diag(λ)) µ ∈ T ≥O , λ ∈ T X ≥O , i λ i = 0, | supp(λ)| < +∞ = Faces(X diag(µ λ)) µ ∈ T ≥O , λ ∈ T X ≥O , i λ i = 0, | supp(λ)| < +∞ Furthermore, if ξ ∈ T X ≥O ξ = O has finite support, then we can write it as ξ = µ λ, where µ = ξ 1 ⊕ • • • ⊕ ξ d ∈ T ≥O and λ ∈ T X ≥O , i λ i = 0 is defined as λ i = ξ i µ -1 for all i. Therefore, we get cone TC (X) = Faces(X diag(µ λ)) µ ∈ T ≥O , λ ∈ T X ≥O , i λ i = 0, | supp(λ)| < +∞ = Faces(X diag(λ)) λ ∈ T X ≥O , | supp(λ)| < +∞ .
Corollary 3.31. The set cone TC (X) is the smallest TC-convex cone that contains X and O.

Proof. We set X = X ∪ O and use the representation from Lemma 3.30 to get cone TC (X)

= µ∈T ≥O Faces(X diag(λ)) λ ∈ T X ≥O , i λ i ≤ µ, | supp(λ)| < +∞ = µ∈T ≥O Faces( X diag(λ)) λ ∈ T X ≥O , i λ i = µ, | supp(λ)| < +∞ = µ∈T ≥O conv TC µ X .
As this is a nested union for increasing µ, it is a TC-convex set by Corollary 3.7. Furthermore, let Z be the smallest TC-convex cone containing X. By definition of a cone, one gets µ X ⊆ Z for all µ > O and, by TC-convexity, also conv TC µ X ⊆ Z for all µ > O. Since O belongs to Z, the equality above shows the minimality of cone TC (X).

Lemma 3.32. Suppose that V, W ⊂ T d ± are two nonempty finite sets. Let V = { (v, 0) | v ∈ V }, Ŵ = (w, O) w ∈ Ŵ , and X = conv TC { v λ w | v ∈ V, w ∈ W, λ ∈ T ≥O } .
Then, we have the equality

{ (x, 0) | x ∈ X} = cone TC ( V ∪ Ŵ ) ∩ {x d+1 = 0} .
Proof. Let x ∈ X. By Proposition 3.27, we have

x ∈ Faces µ 1 (v 1 λ 1 w 1 ), . . . , µ (v λ w )
for some

µ i ∈ T ≥O , i µ i = 0, λ i ∈ T ≥O , v i ∈ V , w i ∈ W . Denote ξ i = µ i λ i for all i and observe that Vert µ 1 (v 1 λ 1 w 1 ), . . . , µ (v λ w ) = Vert(µ 1 v 1 ξ 1 w 1 , . . . , µ v ξ w ) ⊆ Vert(µ 1 v 1 , . . . , µ v , ξ i w 1 , . . . , ξ w ) . By Lemma 3.23 we get z ∈ Faces(µ 1 v 1 , . . . , µ v , ξ i w 1 , . . . , ξ w ). Let vi = (v i , 0) ∈ V and ŵi = (w i , O) ∈ Ŵ for all i. Since i µ i = 0 we get (x, 0) ∈ Faces(µ 1 v1 , . . . , µ v , ξ i ŵ1 , . . . , ξ ŵ ) .
In particular, Lemma 3.30 implies that (x, 0) ∈ cone TC ( V ∪ Ŵ ). Conversely, suppose that (x, 0) ∈ cone TC ( V ∪ Ŵ ). Then, Lemma 3.30 shows that there exist µ ∈ T ≥O , ξ ∈ T ≥O , vi ∈ V , ŵi ∈ Ŵ such that (x, 0) ∈ Faces(µ 1 v1 , . . . , µ v , ξ i ŵ1 , . . . , ξ ŵ ). Since the last coordinate of (x, 0) is 0, we get i µ i = 0. Without loss of generality, we can suppose that µ 1 = 0. Observe that Vert(µ 1 v1 , . . . , µ v , ξ i ŵ1 , . . . , ξ ŵ )

= Vert(µ 1 v1 , . . . , µ v , (-1) v1 ξ i ŵ1 , . . . , (-1) v1 ξ ŵ )

= Vert(µ 1 v1 , . . . , µ v , (-1) ẑ1 , . . . , (-1) ẑ ) ,

where ẑ = v1 (ξ i + 1) ŵi . Hence, by Lemma 3.23 we get (x, 0) ∈ Faces(µ 1 v1 , . . . , µ v , (-1) ẑ1 , . . . , (-1) ẑ ) .

For every i, let v i , z i ∈ T d ± be the projection of vi , ẑi obtained by deleting the last coordinate. Then, we have

{v 1 , . . . , v , z 1 , . . . , z } ⊆ { v λ w | v ∈ V, w ∈ W, λ ∈ T ≥O } .
Furthermore, since the last coordinate of every point vi , ẑi is equal to 0 and i µ i = 0, we get x ∈ Faces(µ 1 v 1 , . . . , µ v , (-1) z 1 , . . . , (-1) z ). Therefore, by Proposition 3.27 we have x ∈ X.

Lifts of signed halfspaces

Some of our results rely on a correspondence between tropical halfspaces and halfspaces defined over non-Archimedean valued fields. In the following, we consider the field of (generalized) real Puiseux series K = R{t}, whose elements

γ = c i t ai , a i , c i ∈ R , a 0 > a 1 > a 2 > . . . (23)
are formal power series with real exponents and such that the sequence (a i ) i is either finite or unbounded. The addition and multiplication of Puiseux series are defined in the natural way. Furthermore, given a series γ as in [START_REF] Celaya | Lattice points, oriented matroids, and zonotopes[END_REF], we say that c 0 is its leading coefficient and we denote by lc : K → R the map that sends a Puiseux series to its leading coefficient, with the convention that lc(0) = 0. We also say γ is positive if its leading coefficient is positive. This makes K an ordered field via γ > δ if and only if γδ is positive. It is known that K is a real closed field [START_REF] Markwig | A field of generalised Puiseux series for tropical geometry[END_REF] and this remains true even if one considers a subfield formed by Puiseux series that are absolutely convergent for sufficiently large t [START_REF] Van Den Dries | The real field with convergent generalized power series[END_REF]. All our results are valid for both of these fields. The crucial property of a real closed field is that for 'well-structured' statements (in the sense of model theory), they behave exactly as the 'usual' real numbers via Tarski's principle [START_REF] Tarski | A Decision Method for Elementary Algebra and Geometry[END_REF], [START_REF] Marker | Model Theory: An Introduction[END_REF]Corollary 3.3.16].

The field of Puiseux series is linked with signed tropical numbers via the signed valuation map. Definition 4.1. The map sval : K → T ± sends a Puiseux series as in [START_REF] Celaya | Lattice points, oriented matroids, and zonotopes[END_REF] to its signed valuation,

sval(γ) =      a 0 if γ > 0 O if γ = 0 a 0 if γ < 0 . We extend sval to vectors in K d componentwise by putting sval(x) = sval(x i ) i∈[d] .
General properties of the images of semialgebraic sets under the signed valuation map were studied in [START_REF] Jell | Real Tropicalization and Analytification of Semialgebraic Sets[END_REF], see also [START_REF] Xavier Allamigeon | Tropical spectrahedra[END_REF]Section 4].

The following lemma summarizes basic properties of the signed valuation.

Lemma 4.2. The signed valuation map has the following properties:

(i) if x 1 , x 2 ∈ K satisfy x 1 ≥ x 2 , then sval(x 1 ) ≥ sval(x 2 ); (ii) if x 1 , . . . , x n ∈ K, then sval(x 1 • • • x n ) = sval(x 1 ) • • • sval(x n ); (iii) if x 1 , . . . , x n ∈ K d , then sval(x 1 + • • • + x n ) ∈ U sval(x 1 ) ⊕ • • • ⊕ sval(x n ) .
Proof. The first property is trivial if x 1 ≥ 0 ≥ x 2 . Suppose that x 1 ≥ x 2 > 0 but sval(x 1 ) < sval(x 2 ). Then, the leading coefficient of x 2 -x 1 is equal to lc(x 2 ) > 0, so x 2 -x 1 > 0, which gives a contradiction. Analogously, if 0 > x 1 ≥ x 2 , but sval(x 1 ) < sval(x 2 ), then the leading coefficient of x 2 -x 1 is equal to -lc(x 1 ) > 0, which gives a contradiction.

The second property for n = 2 follows from the definition of multiplication of Puiseux series. The extension to n > 2 follows by an immediate induction.

To prove the third property, it is enough to consider the case d = 1 since sval and U are defined componentwise. Furthermore, observe that if y, z ∈ K are nonnegative (or nonpositive), then sval(y + z) = sval(y) ⊕ sval(z) by the definition of addition in Puiseux series. We can order x 1 , . . . , x n in such a way that x 1 , . . . , x k are nonnegative and x k+1 , . . . , x n are negative. Let

x + = x 1 + • • • + x k and x -= x k+1 + • • • + x n . By the observation above, we have sval(x + ) = sval(x 1 ) ⊕ • • • ⊕ sval(x k ) and sval(x -) = sval(x k+1 ) ⊕ • • • ⊕ sval(x n ). If sval(x + ) = sval(x -),
then the definition of addition in Puiseux series implies that sval(x + + x -) = sval(x + ) ⊕ sval(x -). If sval(x + ) = sval(x -) = a, then the definition of addition in Puiseux series implies that sval(x

+ +x -) ∈ [ a, a] = U(sval(x + )⊕sval(x -)).
The signed valuation map allows us to study sets defined over K d by looking at their images under sval. Conversely, it is sometimes useful to study a set defined in T d

± by looking at its 'lift' in the Puiseux series. Since sval is not bijective, we have many possible choices for the lift. We now introduce different types of lifts of points x ∈ T d ± into Puiseux series that are used in this work. Similar lifts were used in [START_REF] Xavier Allamigeon | Tropicalizing the simplex algorithm[END_REF] to derive properties about lifts of tropical halfspaces within T d ≥O . We start with the simplest one, the canonical lift. where σ ∈ {-, 0, +} is the "de-tropicalized" version of tsgn(x i ) ∈ { , O, ⊕} and we use the convention that t O = 0.

The canonical lifts are very simple, but it turns out that they are not particularly well suited for our purposes. Instead, it is more useful for us to consider lifts that vary from one orthant of T d ± to another. To this end, we introduce the following definition.

Definition 4.4. Given a point x ∈ T d ± and a set J ⊆ [d] we define the lift of x of type J, denoted li J (x) ∈ K d , by ∀i ∈ [d], li J (x) i =      (d + 1)t |xi| if tsgn(x i ) = ⊕ and i ∈ J, -(d + 1)t |xi| if tsgn(x i ) = and i / ∈ J, σt |xi| otherwise,
where σ is the "untropical" version of tsgn(x i ).

In this way, li ∅ (x) coincides with cli(x) on the nonnegative orthant of T d ± , li [d] (x) coincides with cli(x) on the nonpositive orthant of T d ± and so on. Also, for every x and J we have sval li J (x) = x.

4.1. Tropicalization of halfspaces. We now characterize the signed valuation of halfspaces. This is a simple generalization of the characterization known for tropical halfspaces in one orthant. To start, we fix our notation for halfspaces over Puiseux series. Definition 4.5. For a vector (a 0 , a 1 , . . . , a d ) ∈ K d+1 such that (a 1 , . . . , a d ) = 0 we define the (closed affine) halfspace by

H + (a) = x ∈ K d a • 0 x ≥ 0 . (24)
Furthermore, we denote H

-(a) = H + (-a).
The next lemma characterizes the signed valuation of halfspaces. The next lemma gives a more explicit connection between tropical halfspaces of type J and lifts of type J. Before giving the proof, let us note that if x ∈ H + (a), then any lift of x belongs to H + (a) for any lift a of a. However, in order to lift the points that belong to the boundary of H + (a) we need to be more careful.

) ∈ U(a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d ). Hence, we either have a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d ∈ T • or a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d ∈ T >O . Conversely, if x ∈ H + (a) and we let x = cli(x), then Lemma 4.2 shows that sval(a 0 + a 1 x 2 + • • • + a d x d ) ∈ U(a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d ), which is a singleton in T >O , so x ∈ H + (a). Hence H + (a) ⊆ sval H + (a) ⊆ H + (a).
Proof. Let x = li J (x) and a = li K (a). By definition, we have

a 0 = (d + 1)t a0 if a 0 ∈ T >O , -
t |ai|+|xi| , (25)
where (α, β) = (1, 0) if a 0 ∈ T >O and (α, β) = (0, 1) otherwise. Let y ∈ K denote the series on the left-hand side of (10) and z ∈ K denote the series on the righthand side of [START_REF] Xavier Allamigeon | Log-barrier interior point methods are not strongly polynomial[END_REF]. By Lemma 4.2 we have sval(y -z)

∈ U sval(y) sval(z) = U(a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d ). If U(a 0 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d
) is a nonnegative singleton, then yz ≥ 0. Otherwise, we have sval(y) = sval(z) > O. In this case, note that lc(y) ≥ d + 1 and lc(z) ≤ d. Hence yz ≥ 0.

4.2. Separation over Puiseux series. We also need the following version of the hyperplane separation theorem over Puiseux series. We recall that a set X ⊆ K d is a cone if λx ∈ X for all x ∈ X and λ > 0. We also recall that a set X is semialgebraic if it is defined by a finite Boolean combination of polynomial inequalities. Since the field of Puiseux series is real closed, the semialgebraic sets over K d have similar properties to the semialgebraic sets over R d -we refer to [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] for more information on this topic. For the sake of generality, we state the next two propositions for semialgebraic sets, but the familiarity with semialgebraic sets is not necessary to understand the other results of this paper-it is enough to admit that polyhedra are semialgebraic. The first proposition is a hyperplane separation theorem for convex semialgebraic sets. The argument is based on the existence of finite formulas for describing X and Y and the existence of a separating hyperplane in a real closed field due to their convexity; for more details see Appendix A.

Remark 4.9. We note that the assumption that X, Y are semialgebraic cannot be entirely skipped. Indeed, it is shown in [START_REF] Robson | Separating points from closed convex sets over ordered fields and a metric for Rn[END_REF] that R is the only ordered field that admits the general hyperplane separation theorem. For the interested reader, we adapt the example from [START_REF] Robson | Separating points from closed convex sets over ordered fields and a metric for Rn[END_REF] to K in Appendix A. We also note that a special case of Proposition 4.8 is still valid for sets that are definable in definably complete extensions of real closed fields, see [START_REF] Aschenbrenner | Definable versions of theorems by Kirszbraun and Helly[END_REF]Corollary 2.20]. Also, [START_REF] Robson | Separating points from closed convex sets over ordered fields and a metric for Rn[END_REF] gives a version of the separation theorem that is valid for arbitrary ordered fields.

The next proposition is an application of Proposition 4.8 that characterizes the signed valuations. Theorem 4.10. Suppose that X ⊆ K d is a nonempty closed convex semialgebraic set. Then, for every y / ∈ sval(X) there exists a ∈ K d+1 such that X ⊆ H + (a) and y / ∈ H + (sval(a)). In particular, sval(X) is equal to the intersection of the closed tropical halfspaces that contain it.

Proof. To prove the first part of the claim, let y / ∈ sval(X). Since X is closed and semialgebraic, sval(X) is also closed by [36, Theorem 6.9] or [START_REF] Xavier Allamigeon | Tropical spectrahedra[END_REF]Corollary 4.11]. Therefore, there exists an open neighborhood of y that does not intersect sval(X). Since the order on T ± is dense, we can find 1 , . . . , d , r 1 , . . . , r d ∈ T ± such that

1 < y 1 < r 1 , 2 < y 2 < r 2 , . . . , d < y d < r d and such that the box B = [ 1 , r 1 ]×[ 2 , r 2 ]ו • •×[ d , r d ] does not intersect sval(X). Consider the lifted box B = [cli( 1 ), cli(r 1 )] × [cli( 2 ), cli(r 2 )] × • • • × [cli( d ), cli(r d )] ⊂ K d .
The set B is convex and semialgebraic. Moreover, we have It remains to show that X ⊆ H + (â). Indeed, if there exists x ∈ X such that

X ∩ B = ∅ because sval(X) ∩ sval(B) = sval(X) ∩ B = ∅.
x T â < 0, then for any λ > -a 0 /x T â > 0 we have λx

∈ P but λx / ∈ H + (a),
which is a contradiction. Therefore, we can suppose that a satisfies a 0 = 0.

Example 4.12. We note that neither of the assumptions of Theorem 4.10 can be skipped. Indeed, the set X = { x ∈ K | x > 0} is semialgebraic and convex but not closed. We have sval(X) = T >O , which is not an intersection of closed tropical halfspaces. Likewise, the set Y = { x ∈ K | sval(x) > 0} is closed and convex, but not semialgebraic. We have sval(Y ) = { x ∈ T ± | x > 0}, which is not an intersection of closed tropical halfspaces.

The following lemma gives a partial characterization of the intersection of all closed tropical halfspaces that contain a given finite set. Lemma 4.13. Given a finite set X = {x 1 , . . . , x m } ⊂ T d ± we have

H + (a) X ⊆ H + (a) = sval(X) X ⊆ K d convex ∧ X ⊆ sval(X) = J⊆[d]
sval conv li J (x 1 ), . . . , li J (x m ) .

Proof. Denote

U = H + (a) X ⊆ H + (a) , V = sval(X) X ⊆ K d convex ∧ X ⊆ sval(X) , W = J⊆[d]
sval conv li J (x 1 ), . . . , li J (x m ) .

We start by showing that

V = sval conv x 1 , . . . , x m ∀i, sval(x i ) = x i . (26)
Indeed, the inclusion ⊆ in ( 26) holds as we just range over a smaller set. To prove the opposite inclusion, it is enough to observe that any convex set X such that {x 1 , . . . , x m } ⊆ sval(X) contains some set of the form conv x 1 , . . . , x m . Hence, the equality (26) holds.

As conv(x 1 , . . . , x m ) is a closed convex semialgebraic set for each choice with sval(x i ) = x i for all i ∈ [m], we can apply Theorem 4.10 to each set in the intersection [START_REF] Colcombet | The theory of universal graphs for infinite duration games[END_REF]. This implies that V is an intersection of a family of closed tropical halfspaces. Since X ⊆ V , all of these halfspaces contain X. Hence, U ⊆ V .

The inclusion V ⊆ W is trivial. Therefore, it remains to prove that W ⊆ U . To this end, take a point z / ∈ U . By definition, there is a closed tropical halfspace H + (a)

that contains X with z / ∈ H + (a). Suppose that H + (a) is of type J ⊆ [d] and let

K = [d] 0 \ J be its complement. Then, Lemma 4.7 shows that li J (x i ) ∈ H + li K (a) for every i ∈ [m]. Since the set H + li K (a) is convex, we obtain conv li J (x 1 ), . . . , li J (x m ) ⊂ H + li K (a) .
Using the representation of the valuation of halfspace from Lemma 4.6, we get

W ⊆ sval conv li J (x 1 ), . . . , li J (x m ) ⊂ sval H + li K (a) = H + (a).
In particular, we get z / ∈ W and so W ⊆ U as claimed.

The next lemma strengthens the claim of Corollary 4.11 for polyhedral cones.

Lemma 4.14. Suppose that P ⊆ K d is a polyhedral cone. Then, sval(P ) is an intersection of finitely many linear closed tropical halfspaces.

Proof. Let P = x ∈ K d Ax ≥ 0 for some matrix A ∈ K n×d . By Farkas' lemma [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Corollary 7.1h], for every a ∈ K d we have the equivalence

P ⊆ H + (0, a) ⇐⇒ a ∈ y T A y ≥ 0 . ( 27
)
The intersection of y T A y ≥ 0 with any closed orthant K d is a polyhedral cone, and so it is generated by a finite family of rays by the Minkowski-Weyl theorem [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Corollary 7.1a]. For any closed orthant Lemma 4.15. Let X ⊆ K d be an arbitrary set. Take λ ∈ K such that λ ≥ 0 and denote sval(λ) = λ. Then, we have

O ⊂ K d , let U O ⊂ K d be a finite set such that y T A y ≥ 0 ∩ O = cone(U O ). Let U = O U O be
sval conv(λX) = λ sval conv(X) . ( 28
)
In particular, we have the equality

sval cone(X) = sval conv(t λ X) λ ∈ T ≥O .
Proof. Let x ∈ sval conv(λX) . Since conv(λX) = λ conv(X), there exists y ∈ conv(X) such that x = sval(λy) = sval(λ) sval(y) = λ sval(y). Hence x ∈ λ sval conv(X) . Conversely, suppose that x ∈ λ sval conv(X) . Then, there exists y ∈ conv(X) such that x = λ sval(y) = sval(λy), so that x ∈ sval conv(λX) . To prove the second claim, note that [START_REF] Develin | Tropical convexity[END_REF] gives sval conv(λX) = sval conv(t λ X) .

In particular, we get

sval cone(X) = sval conv(λX) λ ≥ 0 = sval conv(t λ X) λ ∈ T ≥O .

Separation and Hemispaces

A TC-hemispace is a TC-convex subset X ⊆ T d ± for which also T d ± \ X is TCconvex. The fundamental elimination property of TC-convexity (Theorem 5.2) leads to a representation of a TC-convex set as intersection of its containing TChemispaces (Theorem 5.3). Then, we identify that TC-hemispaces are close to halfspaces (Theorem 5.10); based on a more thorough study of TC-hemispaces, this leads to a representation of TC-hemispaces by convex lifts (Proposition 5.18). 5.1. Fundamental separation property. For ∼ ∈ {≤, ≥} d , a point w with

y k ∼ k w k for all k ∈ [d] is said to dominate y with respect to ∼. Lemma 5.1. If µ ≤ 0 and w ∈ U(v 1 ⊕µ v 2 ), then Faces(X ∪v 1 )∩Faces(Y ∪v 2 ) ⊆ Faces(X ∪ µ Y ∪ w).
Proof. Let z be an arbitrary point in Faces(X ∪ v 1 ) ∩ Faces(Y ∪ v 2 ). Using Corollary 3.21, for every ∼ ∈ {≤, ≥} d , there exist vertices x1 v 1 x2 and ỹ1 v 2 ỹ2 in Vert(X ∪ v 1 ) and Vert(Y ∪ v 2 ), respectively, which dominate z with respect to ∼. Here, x1 , x2 arise as left sum of points in X and ỹ1 , ỹ2 arise analogously. As x1 µ ỹ1 ∈ U(x 1 ⊕ µ ỹ1 ), w ∈ U(v 1 ⊕ µ v 2 ) and x2 µ ỹ2 ∈ U(x 2 ⊕ µ ỹ2 ), by Lemma 2.15, x1 µ ỹ1 w x2 µ ỹ2 dominates z with respect to ∼. Ranging over all ∼, these points form a subset of Vert(X ∪µ Y ∪w). Again using Corollary 3.21, z is contained in Faces(X ∪ µ Y ∪ w).

Theorem 5.2. Fix a set X = {x 0 , . . . , x n } ⊂ T d ± . Then, for every y 1 , y 2 , z ∈ T d ± such that x 0 ∈ conv TO (y 1 , y 2 ) we have the implication

z ∈ conv TC (X ∪ {y 1 }) ∧ z ∈ conv TC (X ∪ {y 2 }) =⇒ z ∈ conv TC (X) .
Proof. Breaking the symmetry between y 1 and y 2 , there is a µ ∈ T ≥O with µ ≤ 0 such that x 0 ∈ U(y 1 ⊕µ y 2 ). So let λ (1) ∈ T n+1 ≥O , λ (2) ∈ T n+1 ≥O and and

ρ 1 , ρ 2 ∈ T ≥O with λ (1) ⊕ ρ 1 = λ (2) ⊕ ρ 2 = 0. z ∈ Faces(diag(λ (1) ) X ∪ ρ 1 y 1 ) ∩ Faces(diag(λ (2) ) X ∪ ρ 2 y 2 ).
First, if ρ 2 = O then z ∈ Faces(diag(λ (2) ) X) yields the desired containment. Furthermore, if µ = O then x 0 = y 1 which concludes the claim with z ∈ Faces(diag(λ (1)

) X ∪ ρ 1 y 1 ). Otherwise, let δ = ρ 1 -ρ 2 + µ = ρ 1 ρ -1 2
µ, or equivalently δ ρ 2 = ρ 1 µ. We have to distinguish two cases, depending on the real sign of δ.

Case 1 (δ ≤ 0.) By Lemma 5.1, we obtain that

z ∈ Faces(diag(λ (1) ) X ∪ δ diag(λ (2) ) X ∪ w)
for an arbitrary w ∈ U(ρ 1 y 1 ⊕ δ ρ 2 y 2 ). With δ ρ 2 = ρ 1 µ, this implies that z ∈ Faces(diag(λ (1) ) X ∪ δ diag(λ (2) ) X ∪ ρ 1 x 0 ) . In particular, this yields z ∈ conv TC (X) since δ, ρ 1 ≤ 0 and, therefore,

λ (1) ⊕ δ λ (2) ⊕ ρ 1 = λ (1) ⊕ ρ 1 = 0. Case 2 (δ > 0.) By Lemma 5.1, we obtain that z ∈ Faces(δ -1 diag(λ (1) ) X ∪ diag(λ (2) ) X ∪ w) for an arbitrary w ∈ U(δ -1 ρ 1 y 1 ⊕ ρ 2 y 2 ). With δ -1 ρ 1 = ρ 2 µ -1 , this implies that z ∈ Faces(δ -1 diag(λ (1) ) X ∪ diag(λ (2) ) X ∪ ρ 2 µ -1 x 0 ) .
In particular, this yields z ∈ conv TC (X) since δ -1 , ρ 2 ≤ ρ 2 µ -1 = δ -1 ρ 1 < 0 and, therefore, 2) , using δ -1 ( λ (1) ) < 0 and ρ 2 µ -1 < 0.

λ (2) ≤ δ -1 ( λ (1) ) ⊕ λ (2) ⊕ ρ 2 µ -1 ≤ λ (2) ⊕ ρ 2 = 0 = λ (
The maximal set of elements which is tropically convex and does not contain a fixed point is called semispace in [START_REF] Katz | Characterization of tropical hemispaces by (p,r)-decompositions[END_REF]. This concept (for unsigned tropical convexity) was used to study hemispaces. We use a similar idea in the following proof.

Theorem 5.3. Every TC-convex set G ⊆ T d
± is an intersection of TC-hemispaces. More precisely, each of these TC-hemispaces can be chosen such that its complement is TO-convex.

Proof. The proof is a variant of the argument given in [START_REF] Law | Abstract convex structures in topology and set theory[END_REF]Thm. 5.2] and [START_REF] Van De | Theory of Convex Structures[END_REF]Thm. I.4.13]. If G ∈ {∅, T d ± }, then the claim is trivial. Otherwise, let z / ∈ G. We want to prove that there exists a TC-hemispace H * such that G ⊆ H * and z / ∈ H * . To do so, we consider the family F of TC-convex subsets S of T d ± such that G ⊆ S and z / ∈ S. We partially order F by inclusion. Any chain C ⊆ F is upper bounded by ( S∈C S) ∈ F using that TC-convexity is closed under arbitrary nested unions. Therefore, the Kuratowski-Zorn lemma implies that F has at least one maximal element H * . By construction, H * is TC-convex; hence to prove that H * is a TC-hemispace we show that T d ± \ H * is TO-convex. Note that this implies that it is also TC-convex. Suppose that T d ± \ H * is not TO-convex. Then, there exist y 1 , y 2 ∈ T d ± \ H * and x 0 ∈ conv TO (y 1 , y 2 ) such that x 0 ∈ H * . Furthermore, by the maximality of H * we get z ∈ conv TC (H * ∪ {y 1 }) and z ∈ conv TC (H * ∪ {y 2 }). Hence, by Proposition 3.24, there exist finite sets X 1 , X 2 ⊆ H * such that z ∈ conv TC (X 1 ∪ {y 1 }) and z ∈ conv TC (X 2 ∪ {y 2 }). By putting X = {x 0 } ∪ X 1 ∪ X 2 , we get x 0 ∈ conv TO (y 1 , y 2 ), z ∈ conv TC (X ∪ {y 1 }), z ∈ conv TC (X ∪ {y 2 }), and z / ∈ conv TC (X) ⊆ H * . This gives a contradiction with Theorem 5.2. Since z / ∈ G was arbitrary, we obtain that G is an intersection of TC-hemispaces. 5.2. TC-hemispaces are nearly halfspaces. For a cone X ⊆ T d ± , a relative conic TC-hemispace w.r.t. X is a subset H ⊆ X ⊆ T d ± such that H and X \ H are TC-convex cones.

Note that if G ⊆ T d ± is a TC-hemispace as well as a cone and X ⊆ T d ± is a TC-convex cone then G ∩ X is a relative conic TC-hemispace w.r.t. X.

We summarize a crucial insight on the structure of tropical hemispaces in the non-negative tropical orthant T d ≥O ; see [START_REF] Briec | Halfspaces and Hahn-Banach like properties in Bconvexity and max-plus convexity[END_REF] >O be such that y / ∈ G. Then, for sufficiently small ω ∈ T >O , the point x ω y ∈ T d >O belongs to H + (O, a), which implies that it belongs to G. Hence, by the TC-convexity of X \ G, we have x ∈ G. This shows that

H + (O, a) ∩ X ⊆ G. Analogously, we get H -(O, a) ∩ X ⊆ (X \ G), which implies that G ⊆ H + (O, a) ∩ X.
We note that the assumption

G ∩ T d >O / ∈ {∅, T d >O } implies that supp ⊕ (a) = ∅ and supp (a) = ∅.
In order to prove our characterization of TC-hemispaces we need to generalize Corollary 5.5 to handle multiple orthants. We start by characterizing relative hemispaces w.r.t. the halfspace X = x ∈ T d ± x 1 > O . To do so, in Lemmas 5.6 to 5.8 we suppose that G is a relative conic TC-hemispace w.r.t. X. Furthermore, we suppose that there exists an orthant O in cl(X) such that G ∩ int(O) / ∈ {∅, int(O)}. Then, G ∩ O is a relative conic TC-hemispace w.r.t. O ∩ X. In particular, by Corollary 5.5, there is a vector (a 1 , . . . , a

d ) ∈ T d ± with (a 1 , . . . , a d ) = O such that H + (O, a) ∩ O ∩ X ⊆ G ∩ O ⊆ H + (O, a) ∩ O ∩ X. Let Q be a neighboring orthant of
O in X, i.e., an orthant obtained from O by changing one sign (other than the sign of the first coordinate). In the next two lemmas (Lemma 5.6 and Lemma 5.7), we show that the relative TC-hemispaces G ∩ O in O and G ∩ Q in Q are essentially determined by the same vector a.

By suitably flipping signs and permuting variables, we can assume that O = T d ≥O and Q differs in the sign of the d-th component. We denote

T = (O ∪ Q) ∩ X.
In the following proofs, ω ∈ T >O and Ω ∈ T >O will mean a sufficiently small and sufficiently big number, respectively. Lemma 5.6. There are exactly two possibilities for the part of the relative TChemispace G in Q to be trivial:

(i) G ∩ int(Q) = int(Q) ⇔ supp (a) = {d} ⇔ { y ∈ Q ∩ X | y d < O} ⊆ G, (ii) G ∩ int(Q) = ∅ ⇔ supp ⊕ (a) = {d} ⇔ { y ∈ Q ∩ X | y d < O} ∩ G = ∅. Proof. To start, suppose that G∩int(Q) = int(Q) but there is k ∈ supp (a)∩[d-1].
As we assume that G ∩ int(O) / ∈ {∅, int(O)}, there exists j ∈ supp ⊕ (a). We define x ∈ O, y ∈ Q and derive x y ∈ O via

x i = Ω i = j ω else y i =      2Ω i = k ω i = d ω else (x y) i =      2Ω i = k Ω i = j ω else
By construction, x, y ∈ G but x y ∈ G, as one can see from a x > O and a (x y) < O. This contradicts the fact that G is TC-convex. Hence, supp (a) ⊆ {d} and as

G ∩ int(O) / ∈ {∅, int(O)} we get supp (a) = {d}. Now, assume that supp (a) = {d} but there is a point y ∈ (Q ∩ X) \ G such that y d < O. Consider two cases: if y k > O for some k ∈ supp ⊕ (a), then we define x, z ∈ O ∩ X via x i = Ω i = d y i else z i = ω i = d y i else
Then z is on the line segment between x and y, but x, y ∈ T \ G while z ∈ G. This contradicts the fact that G is a relative TC-hemispace. If y k = O for every k ∈ supp ⊕ (a), then we define x, z ∈ O ∩ X via

x i = |y d | i = d ω else z i =      2ω i = d y i i = d, y i = O ω else
We note that z ∈ Faces(x, y). Moreover, the assumption on y implies that a z > O. Hence, as above we have x, y

∈ T \ G while z ∈ G, contradicting the fact that G is a relative TC-hemispace. The implication { y ∈ Q ∩ X | y d < O} ⊆ G ⇒ G ∩ int(Q) = int(Q) is trivial, proving the first point of the lemma.
The second point follows analogously as it can be obtained by considering the complement of G.

Lemma 5.7. H + (O, a) ∩ T ⊆ G ∩ T ⊆ H + (O, a) ∩ T .
Proof. The case of a trivial intersection of G with int(Q) follows directly from Lemma 5.6. Hence, by Corollary 5.5, we can assume that there exists a vector

(b 1 , . . . , b d ) ∈ T d ± \ {O} such that H + (O, b) ∩ Q ∩ X ⊆ G ∩ Q ⊆ H + (O, b) ∩ Q ∩ X.
We show with an exhaustive case distinction that the defining vectors a and b agree up to positive scaling; then this concludes the proof of the lemma. Case 1 (Different sign pattern.) Let j be the smallest index for which tsgn(a j ) = tsgn(b j ). Breaking the symmetry in a and b, we can assume that j ∈ supp(a).

By taking the complement in both orthants, we can assume that j ∈ supp ⊕ (a) which means tsgn(b j ) ∈ {O, }.

Case 1a (j = d.)

Since the sign of a and b differ in d = j ∈ supp ⊕ (a), there is an r ∈ supp ⊕ (b)\{d}. As the relative TC-hemispace in int(O) is not trivial, there is an index s ∈ supp (a). Note that r, s, d are pairwise different due to the minimality assumption on j. We define x ∈ O, y ∈ Q and derive x ⊕ y via

x i =      Ω i = s 2Ω i = d ω else y i =      0 i = r 2Ω i = d ω else (x ⊕ y) i =          0 i = r Ω i = s •2Ω i = d ω else . By construction, a x > O, b y > O. Choosing z ∈ U(x ⊕ y) with z d = ω, we get a point in G. However, z ∈ O and a z < O, a contradiction. Case 1b (j = d.)
Let k = min supp (a) (which cannot equal j then). As the relative TC-hemispace in int(Q) is not trivial, there is an index r ∈ supp (b) (which could equal j).

We define x ∈ O, y ∈ Q and derive x y ∈ O via

x i = 0 i = k ω else y i =          Ω i = j 0 i = r, i = j ω i = d ω else (x y) i =          Ω i = j 0 i = r, i = j 0 i = k ω else
By construction, a x < O, b y < O but a (x y) > O, a contradiction to the TC-convexity of G.

From the cases considered so far, we deduce that a and b have the same sign pattern. Hence, only the following possibility is remaining.

Case 2 Now, we have that the sign patterns of a and b are the same. If a and b are not the same up to scaling, then there are three indices i, j, k ∈ [d] such that not all three signs of the respective components agree and among the quotients

a i b -1 i , a j b -1 j , a k b -1 k
at least one has a different value from the other two. Then there are indices p, q ∈ {i, j, k} with tsgn(a p ) = tsgn(b p ) = ⊕, tsgn(a q ) = tsgn(b q ) = , and a p b q = a q b p .

Case 2a (d ∈ {p, q}. ) By scaling a and b, we can assume that a p = b p = 0. By the symmetry in a and b, we can assume that

|a q | > |b q |. We choose ξ a , ξ b ∈ T >O with ξ a < |a -1 q | < ξ b < |b -1 q |.
With this, we define x ∈ O, y ∈ Q and derive x y ∈ O via

x i =      ξ a i = q 0 i = p ω else y i =          ξ b i = q ω i = d 0 i = p ω else (x y) i =      ξ b i = q 0 i = p ω else
The choice of ξ a and ξ b yields |ξ a a q | < 0 and |ξ b b q | < 0 as well as |ξ b a q | > 0. This implies that a x > O, b y > O and a (x y) < O, a contradiction. Case 2b (d ∈ {p, q}. ) By taking complements in both orthants, we can assume that

d = p, so d ∈ supp ⊕ (a) = supp ⊕ (b). Since H + (O, b) ∩ int(Q) = ∅, there is at least one r ∈ supp ⊕ (b) \ {d}.
By scaling, we can assume that a q = b q = 0. By the previous case, we have a r = b r . By the symmetry in a and b, we can suppose that

|a d | > |b d |.
We choose ξ r , ξ q ∈ T >O with

a d > ξ q > ξ r a r = ξ r b r > b d .
With this, we define x ∈ O, y ∈ Q and z ∈ O via

x i =      ξ q i = q 0 i = d ω else y i =      ξ r i = r 0 i = d, ω else
z i =      ξ q i = q ξ r i = r ω else We have z ∈ Faces(x, y). Moreover, a x > O, b y > O, but a z < O, a contradiction.
We now extend Lemma 5.7 from a union of two orthants to the entire set X.

Lemma 5.8. We have

H + (O, a) ∩ X ⊆ G ⊆ H + (O, a) ∩ X.
Proof. Let Q be any orthant in cl(X). We want to show that

H + (a) ∩ Q ∩ X ⊆ G ∩ Q ⊆ H + (a) ∩ Q ∩ X. Let ν ∈ {⊕, } d be the sign vector corresponding to Q, i.e., the vector such that int(Q) = x ∈ T d ± ∀k, tsgn(x k ) = ν k .
For the purposes of this proof, we say that an orthant is good if H + (O, a) subdivides its interior in a non-trivial way; that is if there exists a pair (k, l) ∈ supp(a) such that

ν k tsgn(a k ) = ν l tsgn(a l ). Let r = | { k ∈ [d] | k ∈ supp(a), ν k = } |.
We divide the proof into two cases.

Case 1 (We have | supp(a)| ≥ 3 or r ∈ {0, 1}.) In this case, we start by proving that there exists a sequence of orthants

T d ≥O = Q 0 , Q 1 , . . . , Q p = Q in cl(X) such that Q i , Q i+1 differ
by flipping one sign and the Q i are good for all i ≤ p -1. Such a sequence can be obtained in the following way. The orthant Q 0 is good by the assumption of the lemma. To go from Q 0 to Q, we first flip the signs in { k / ∈ supp(a) | ν k = } (in any order) and note that all orthants obtained in this way are good. Then, we flip the signs in { k ∈ supp(a) | ν k = }. If r ∈ {0, 1}, then this already proves the existence of the sequence, because this step either does nothing or flips one sign. If | supp(a)| ≥ 3 and r ≥ 3, then there are at most two orthants that are not good and could be obtained at this step. However, since the graph of the r-dimensional hypercube is r-vertex-connected and r ≥ 3, there is a way of flipping the signs in { k ∈ supp(a) | ν k = } that avoids going through these two orthants (except, possibly, for the last step, since Q may be not good). If | supp(a)| ≥ 3 and r = 2, then we let k, l be the two indices in supp(a) such that ν k = ν l = and j be any index in supp(a) such that ν j = ⊕. If tsgn(a j ) = tsgn(a k ) or tsgn(a k ) = tsgn(a l ), then we first flip the sign of the component indexed by k and subsequently we flip the sign of the component indexed by l. If tsgn(a j ) = tsgn(a l ), then we start by flipping the sign of the component indexed by l and subsequently we flip the sign of the component indexed by k.

Given the sequence Q 0 , . . . , Q p we apply Lemma 5.7 to ≥O is good, we can suppose (up to permuting k and l) that tsgn(a k ) = ⊕ and tsgn(a l ) = . Then, Lemma 5.6 shows that

T = (Q 0 ∪ Q 1 ) ∩ X. This gives H + (a) ∩ Q 1 ∩ X ⊆ G ∩ Q 1 ⊆ H + (a) ∩ Q 1 ∩ X. Furthermore, since Q 1 is good,
G ∩ int(Q {k} ) = ∅ and G ∩ int(Q {l} ) = int(Q {l} ).
We first show that G ∩ int(Q {k,l} ) / ∈ {∅, int(Q {k,l} )}. We define x ∈ Q {k,l} , y ∈ T d ≥O and derive x y ∈ Q {k} via

x i =      ω i = k Ω i = l 0 else y i =      0 i = k Ω i = l 0 else (x y) i =      0 i = k Ω i = l 0 else
We have y / ∈ G and x y ∈ G. Therefore, x ∈ G ∩ int(Q {k,l} ). Similarly, if we define For contradiction, assume that |a l | < η -1 < ξ -1 < |b l | for some η, ξ ∈ T >O . We define x ∈ Q {k, } , y ∈ T ≥O and derive x y ∈ Q {k} via

x i =      Ω i = k ω i = l 0 else y i =      Ω i = k 0 i = l 0 else (x y) i =      Ω i = k 0 i = l
x i =      0 i = k ξ i = l ω else y i =      0 i = k η i = l ω else (x y) i =      0 i = k η i = l ω else . ( 29
)
We have x, y ∈ G (as b x > O and a y > O) but x y / ∈ G, which gives a contradiction. Analogously, if |a l | > η -1 > ξ -1 > |b l | for some ξ, η ∈ T >O , and we define x, y as in [START_REF] Develin | Tropical polytopes and cellular resolutions[END_REF], then x, y / ∈ G but y x ∈ G, giving a contradiction. Therefore, we have a = b.

To finish the proof, note that we can go from Q {k,l} to Q by a sequence of good orthants obtained by flipping the signs that do not belong to supp(a). This gives the claim by the same reasoning as in Case 1.

Example 5.9. We illustrate the last case in the proof of Lemma 5.8.

Let a = (0, 0) and b = (0, 3). We take η = -1, ξ = -2, so x = ( 0, (-2)), y = (0, -1). Then a y = 0, b x = 1 so x, y ∈ G but x y = ( 0, -1) so a (x y) = 0, b (x y) = 2 and x y / ∈ G.

x 1

x 2 (0, 0) (0, -1)

( 0, -3) ( 0, -2) ( 0, -1)
Figure 6. Sketch of the positions for the first part of Example 5.9.

Likewise, if a = (0, 3) and b = (0, 0), then we take η = -2, ξ = -1, so x = ( 0, (-1)), y = (0, -2). We have a y = 1, b x = 0 so x, y / ∈ G but y x = (0, (-1)) satisfies a (y x) = 2, b (y x) = 0 and y x ∈ G. Now, we combine the last lemmas to prove that a TC-hemispace is nearly a halfspace. ∈ G} \ {O}. Since both G and its complement are TCconvex, we have

H = { λ (z, 0) | λ ∈ T >O , z ∈ G} , H = { λ (z, 0) | λ ∈ T >O , z / ∈ G} .
In particular, H = cone TC { (z, 0) | z ∈ G} ∩ X, which implies that H is a TCconvex cone. Analogously, H is a TC-convex cone. Furthermore, we have H ∪H = X because any point x = (x 1 , . . . , x d+1 ) in X can be written as x = x d+1 (y 1 , . . . , y d , 0), where y i = x i x -1 d+1 and y either belongs to G or not. Likewise, we have H ∩ H = ∅ because if x ∈ H ∩ H, then the point y defined as above belongs both to G and its complement, which gives a contradiction. Thus, H is a relative conic TC-hemispace w.r.t. X and H ∩ T d+1 >O / ∈ {∅, T d+1 >O }. Hence, by Lemma 5.8, there exists a vector (a 1 , . . . , a d+1 ) ∈ T d+1 ± such that (a 1 , . . . , a d+1 ) = O and

H + (O, a) ∩ X ⊆ H ⊆ H + (O, a) ∩ X. In particular, x ∈ T d ± a d+1 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d > O ⊆ G ⊆ x ∈ T d ± a d+1 ⊕ a 1 x 1 ⊕ • • • ⊕ a d x d O .
Since supp (a) = ∅ and supp ⊕ (a) = ∅, we have (a 1 , . . . , a d ) = O.

Case 2 (G ∩ int(O) ∈ {∅, int(O)} for every orthant O ⊆ T d ± .) By taking suitable combinations, we see that G cannot only consist of parts of coordinate hyperplanes. Hence, by flipping signs, we can assume that T d >O ⊆ G. We show that there is a k ∈

[d] such that x ∈ T d ± x k > O ⊆ G ⊆ x ∈ T d ± x k ≥ O . ( 30
)
Suppose the right inclusion does not hold, then for each ∈ [d] there is an orthant O ( ) with int(O ( ) ) ⊆ G whose -th component is negative. As each O ( ) contains points close to the negative of the -th tropical unit vector, taking convex combinations of these points and (0, . . . , 0) ∈ T d >O yields points in the interior of every orthant in T d ± . This would imply G = T d ± , which was excluded. Hence, G ⊆ x ∈ T d ± x k ≥ O . Therefore, for half of the orthants the interior is contained in G and, by the same argument, for half of the orthants the interior is contained in the complement G of G. But as G and G cover the whole space, we get that G ⊆ x ∈ T d ± x k ≤ O . By taking again the complement, this concludes the second case.

As TO-hemispaces are also TC-hemispaces we immediately get the following. For a fixed a, comprising the points with (1) the same set Argmax(a, x), (2) in the same orthant yields a cell decomposition of T d ± .

Taking the common refinement of the cell decompositions for several possible a yields a generalization of the decomposition which was studied under the name 'type decomposition' [START_REF] Develin | Tropical convexity[END_REF] or 'covector decomposition' [START_REF] Joswig | Weighted digraphs and tropical cones[END_REF].

Right from the definition, we obtain some basic properties.

Corollary 5.12. We have We start with a statement that be seen orthantwise.

(i) If 0 ∈ Argmax(a, x) ∪ Argmax(a, ρ x), then Argmax(a, ρ x) = Argmax(a, x) for ρ ∈ T ± \ {O}; (ii) Argmax(a, x) = ∅ if and only if a (0, x) = O; (iii) Argmax(a, x) = [d] 0 if and only if |a 0 | = |a 1 | + |x 1 | = • • • = |a d | + |x d | = O.
Lemma 5.13. For ρ ∈ R with Argmax(a, x) = Argmax(a, ρ x), we have ρ x ∈ G.

Proof. The claim is trivial for ρ = 0, so we start with ρ < 0. If 0 ∈ Argmax(a, x), then the equality Argmax(a, x) = Argmax(a, ρ x) implies that Argmax(a, ρ x) = {0} = Argmax + (a, ρ x) and so ρ x ∈ H + (a) ⊆ G. If 0 / ∈ Argmax(a, x), then we fix k ∈ Argmax + (a, x) ∩ [d] = Argmax + (a, x). We define a point y ∈ T d ± as y = ρ x k e k where e k is the k-th tropical unit vector. We have y ∈ H + (a) and so y ∈ G. Furthermore, ρ x = ρ x y and therefore ρ x ∈ G by the TC-convexity of G.

If ρ > 0, then we define x = ρ x, G = T d ± \ G, and a = a. Suppose that x ∈ G . Then, G is a TC-hemispace such that H + (a ) ⊆ G ⊆ H + (a ) and we have x = (-ρ) x . Hence, the same reasoning as above shows that x ∈ G , giving a contradiction.

Lemma 5.14. For y ∈ T d ± with Argmax(a, y) = Argmax(a, x) and tsgn(y k ) = tsgn(x k ) for all k ∈ Argmax(a, x) ∩ [d], we have y ∈ G.

Proof. As noted above, Argmax + (a, x) = ∅, so we fix k ∈ Argmax + (a, x) and consider the following two cases.

Case 1 (y j = x j for all j ∈ Argmax(a, x) ∩

[d].) Case 1a (|x j | ≤ |y j | for all j / ∈ Argmax(a, x).) Define M = 0 if k = 0 and M = 1 otherwise. Let z ∈ T d
± be the point defined as

z i = O if i ∈ Argmax(a, y) \ {k}, M y i otherwise.
Then, z satisfies Argmax(a, z) = Argmax + (a, z) = {k} as one sees by taking scalar product with a. In particular, we have z ∈ H + (a) ⊆ G. Moreover, |x j | ≤ |y j | for all j / ∈ Argmax(a, x) implies that y = (-M ) z x, and so y ∈ G. Case 1b (There exists an / ∈ Argmax(a, x) such that |x | > |y |.) Let u ∈ T d ± be any point that satisfies u j = x j for all j ∈ Argmax(a, x) and |u j | = |x j | otherwise. Then, we have Argmax(a, u) = Argmax(a, x) and u ∈ G by the previous case. Since u was arbitrary, Example 3.19 implies that the point v ∈ T d ± defined as

v i = x i if i ∈ Argmax(a,
This yields x j = y j for j ∈ Argmax(a, x) ∩ [d] because tsgn(x j ) = tsgn(y j ). By the case assumption, we have max k∈

[d]0 |a k x k | = max k∈[d]0 |a k y k | as y = x but Argmax(a, y) = Argmax(a, x).
In particular, 0 / ∈ Argmax(a, y). Furthermore, [START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF]

gives |a 0 | < |a | |y | = |a | |x |, so 0 ∈ Argmax(a, x
). This implies that 0 ∈ Argmax(a, x) ∪ Argmax(a, x ). Therefore, we have Argmax(a, x ) = Argmax(a, x) by Corollary 5.12 and Lemma 5.13 implies x ∈ G. Since x j = y j for all j ∈ Argmax(a, x) ∩ [d], Case 1 shows that y ∈ G.

The structure of the boundary of TC-hemispaces relies heavily on the support of the halfspaces sandwiching it. We discuss this in a simple example which is visualized in Fig. 8.

Example 5.15. Suppose that G ⊂ T 2 ± is a TC-hemispace such that x ∈ T 2 ± x 1 > 0 ⊆ G ⊆ x ∈ T 2 ± x 1 ≥ 0 . (32)
Furthermore, suppose that there is a point x ∈ G such that x 1 = 0 and let y ∈ T 2 ± be any point such that y 1 = 0. Then, for a = ( 0, 0, O) we get Argmax(a, x) = {0, 1} = Argmax(a, y) and tsgn(x 1 ) = tsgn(y 1 ), so Lemma 5.14 implies that y ∈ G. Hence, there are only two TC-hemispaces that satisfy [START_REF] Gaubert | Carathéodory, Helly and the others in the max-plus world[END_REF], namely G =

x ∈ T 2 ± x 1 > 0 and G = x ∈ T 2 ± x 1 ≥ 0 . By contrast, suppose that G ⊂ T 2 ± is a TC-hemispace such that x ∈ T 2 ± x 1 > O ⊆ G ⊆ x ∈ T 2 ± x 1 ≥ O . (33)
Furthermore, suppose that there is a point x ∈ G such that x 1 = O and let y ∈ T 2 ± be any point such that y 1 = O. Then, for a = (O, 0, O) we get Argmax(a, x) = ∅ so the assumption of Lemma 5.14 is not satisfied and we cannot deduce anything about y using this lemma. Indeed, if y 2 < x 2 , then

G = x ∈ T 2 ± x 1 > O ∪ x ∈ T 2 ± x 1 = O, x 2 ≥ x 2
is a TC-hemispace that does not contain y and

G = x ∈ T 2 ± x 1 > O ∪ x ∈ T 2 ± x 1 = O, x 2 ≤ x 2
Is a TC-hemispace that contains y. In particular, there are infinitely many TChemispaces that satisfy (33).

π : T d ± → T d-|K| ±
be the projection that forgets the coordinates from K. As the components in K of G∩X , X \G ⊆ X are all O, Proposition 3.17 implies that the set π(G ∩ X ) is a TC-hemispace in T d-|K| ± . Hence, by the induction hypothesis, we have π(G ∩ X ) = sval(G ) for some convex set G ⊆ K d-|K| . We embed the set G into K d by adding 0 coordinates to every point and this gives a convex set

G ⊥ ⊆ K d such that sval(G ⊥ ) = G ∩ X .
Next, we show that there exists a convex set

G = ⊆ K d with sval(G = ) = G ∩ X.
To construct an appropriate lift with Definition 4.4, let

J = { k ∈ [d] | a k > O} be such that H + (a) is of type J. Set G = = conv( li J (x) ∈ K d x ∈ G ∩ X ).
Then, G = is convex and right from the definition we have G ∩ X ⊆ sval(G = ).

To prove that sval(G = ) ⊆ G ∩ X, let y ∈ G = be arbitrary and y = sval(y). Then, the Carathéodory theorem in K d shows that y = λ 1 li J (y (1)

) + • • • + λ m li J (y (m) ) (34)
for some m ≤ d + 1, y (1) , . . . , y (m) ∈ G ∩ X, λ 1 , . . . , λ m > 0, and i λ i = 1. As we aim to prove that y ∈ G ∩ X, we will estimate the leading terms of the components in the sum [START_REF] Helbig | On Carathéodory's and Kreȋn-Milman's theorems in fully ordered groups[END_REF]. For every

i ∈ [m] let λ i = sval(λ i ) > O and γ i = lc(λ i ) > 0.
We assume that the points y (1) , . . . , y (m) are labeled such that γ 1 ≥ • • • ≥ γ m . To relate y with the hemispace property of G, we set z = λ 1 y (1) . . . λ m y (m) .

With i λ i = 0, the TC-convexity of G implies z ∈ G. Moreover, we also have z ∈ X. Indeed, this is trivial if a 0 = O. Otherwise, because of y (1) ∈ X, it has a component k ∈ [d] such that a k y (1) k = O and so a k z k = O. Thus, z ∈ G ∩ X. We will prove that y ∈ G using Lemma 5.16. To do so, suppose that there exists

k ∈ Argmax + (a, z) ∩ [d]. If a k > O and z k > O, then we define a vector u ∈ R m by u i = lc li J (y (i) ) k if λ i y (i) k = |z k |, 0 otherwise.
Since k ∈ J, we have u ∈ {-1, 0, d + 1} m . Moreover, since z k > O, the vector u is nonzero. Let p ∈ [m] be the smallest index such that u p = 0, which is exactly the entry defining the kth component in the left sum [START_REF] Horvath | Some general principles in tropical convexities[END_REF]. Hence, we have

z k = λ p y (p) k . Now, z k > O implies y (p)
k > O and therefore u p = d + 1 by the definition of the lift of type J.

We are ready to estimate the sum of the leading coefficients of the dominating terms in the sum λ

1 li J (x 1 ) k + • • • + λ m li J (x m ) k . This is just γ 1 u 1 + • • • + γ m u m ≥ (d + 1)γ p -γ p+1 -• • • -γ m ≥ (d + 1)γ p -(m -p)γ p ≥ pγ p > 0 . (36)
Therefore, there is no cancellation of the leading terms in [START_REF] Helbig | On Carathéodory's and Kreȋn-Milman's theorems in fully ordered groups[END_REF] To finish the proof, let G = conv(G ⊥ ∪ G = ) ⊆ K d . Then, G is convex and G ⊆ sval(G). To prove that sval(G) ⊆ G, note that this inclusion is trivial if a 0 = O. Otherwise, let z ∈ G. Then, there exist x ∈ G ⊥ , y ∈ G = , λ, µ ≥ 0, λ + µ = 1 such that z = λx + µy. Denote z = sval(z), x = sval(x), y = sval(y), λ = sval(λ), µ = sval(µ), and w = λ x µ y ∈ G. If λ = O or µ = O, then we trivially have z ∈ G. Otherwise, y ∈ X and µ = O imply that w ∈ X. Furthermore, x ∈ X implies that z k = µ y k = w k for all k ∈ K. Therefore, z ∈ G by Lemma 5.14.

TC-hull as intersection of closed halfspaces

In Section 5, we prepared the crucial tools for proving the representation of the TC-convex hull of finitely many points as the intersection of its containing closed halfspaces. It relies on the understanding of the structure of TC-hemispaces and a representation of those using insights on their lifts from Section 4. Finally, we arrive at analogs of the Minkowski-Weyl theorem for polyhedra. Theorem 6.1. For every x 1 , . . . , x n ∈ T d ± we have

conv TC (x 1 , . . . , x n ) = a∈T d+1 ± H + (a) {x 1 , . . . , x m } ⊆ H + (a) .
Proof. The inclusion ⊆ follows from Corollary 3.8. For the reverse direction, Lemma 4.13 shows the equality

a∈T d+1 ± H + (a) {x 1 , . . . , x m } ⊆ H + (a) = sval(X) X ⊆ K d is convex and {x 1 , . . . , x m } ⊆ sval(X) ⊆ sval(X) X ⊆ K d convex,
(X) X ⊆ K d convex, {x 1 , . . . , x m } in TC-hemispace sval(X) = { G | G TC-hemispace with {x 1 , . . . , x m } ⊆ G} = conv TC (x 1 , . . . , x n ) .
Combining Theorem 6.1 and Lemma 4.13 we obtain the following corollary, which is an analog of [START_REF] Loho | Signed Tropical Convexity[END_REF]Theorem 3.14] for TC-convexity. Corollary 6.2. For every x 1 , . . . , x n ∈ T d ± we have conv TC (x 1 , . . . , x n ) = sval conv(x 1 , . . . , x m ) ∀i,

x i ∈ sval -1 (x i ) = J⊆[d]
sval conv li J (x 1 ), . . . , li J (x m ) .

Based on the description of the TC-convex hull by closed halfspaces, we obtain several further insights on TC-convex hulls. We start with a conic version. Theorem 6.3. Let X ⊆ T d ± be an arbitrary set. Then, the following are equivalent: (i) X is an intersection of finitely many closed linear tropical halfspaces. (ii) X = cone TC (x 1 , . . . , x m ) for a finite collection of points {x 1 , . . . , x m }.

(iii) There exists a finite collection of polyhedral cones P 1 , . . . , P m ⊆ K d such that i sval(P i ) = X .

(iv) There exists a finite collection of linear halfspaces H 1 , . . . , H m ⊆ K d such that i sval(H i ) = X .

Proof. To prove the implication (i) ⇒ (iv), suppose that X = To prove the implication (i) ⇒ (ii), we use the tropical Minkowski-Weyl theorem for unsigned tropical convexity [START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF]Theorem 1]. This theorem implies that for every closed orthant O of T d ± there exists a finite set U O ⊂ O such that X ∩ O = cone TC (U O ). Let U = O U O . We will show that X = cone TC (U ). Since cone TC (U O ) ⊆ cone TC (U ) for every O, we get X ⊆ cone TC (U ). To prove the opposite inclusion, note that U ⊆ X implies conv TC (U ) ⊆ X by Corollary 3.8. Since X is an intersection of linear tropical halfspaces, we get cone TC (U ) ⊆ X.

To finish the proof, it is enough to show the implication (ii) ⇒ (iii). To do so, let P J = cone li J (x 1 ), . . . , li J (x m ) for all J ⊆ [d]. We will show that X = J⊆[d] sval(P J ). If x ∈ X, there exists λ ∈ T ≥O such that x ∈ λ conv TC (x 1 , . . . , x m ). By combining Theorem 6.1 with Lemma 4.13, for all J ⊆ [d], we get conv TC (x 1 , . . . , x m ) ⊆ sval conv li J (x 1 ), . . . , li J (x m ) .

Hence, by Lemma 4.15 we have λ conv TC (x 1 , . . . , x m ) ⊆ λ sval conv li J (x 1 ), . . . , li J (x m ) = sval conv t λ li J (x 1 ), . . . , t λ li J (x m ) ⊆ sval(P J ) and x ∈ J⊆[d] sval(P J ). Conversely, if x ∈ J⊆[d] sval(P J ) then, by Lemma 4.15, for every J ⊆ [d] there exists λ J ∈ T ≥O such that x ∈ sval conv t λ J li J (x 1 ), . . . , t λ J li J (x m ) = sval conv li J (λ J x 1 ), . . . , li J (λ J x m ) .

Hence, by combining Theorem 6.1 with Lemma 4.13 and Lemma 3.30 we get

x ∈ J sval conv li J (λ J x i ) J ⊆ [d], i ∈ [m] = conv TC λ J x i J ⊆ [d], i ∈ [m]
⊆ cone TC (x 1 , . . . , x m ) = X .

Establishing an affine version of the former theorem requires us to come up with an appropriate concept of dehomogenization. Theorem 6.4. Let X ⊆ T d ± be an arbitrary set. Then, the following are equivalent: (i) X is an intersection of finitely many closed tropical halfspaces. (ii) There exist two finite sets V, W ⊂ T d ± such that

conv TC { v λ w | v ∈ V, w ∈ W, λ ∈ T ≥O } = X .
(iii) There exists a finite collection of polyhedra P 1 , . . . , P m ⊂ K d such that i sval(P i ) = X .

(iv) There exists a finite collection of affine halfspaces H 1 , . . . , H m ⊆ K d such that i sval(H i ) = X .

Proof. The theorem is trivial if X is empty. From now on we suppose that X is nonempty.

The implication (i) ⇒ (iv) follows by the same argument as in the proof of Theorem 6.3.

The implication (iv) ⇒ (iii) is trivial.

To prove that (iii) ⇒ (ii), for every i ∈ [m], let Q i = {(λx, λ) : λ ≥ 0, x ∈ P i } ⊆ K d+1 . The set Q i is a polyhedral cone. Furthermore, we have the equality sval(Q i ) ∩ {x d+1 = 0} = { (x, 0) | x ∈ sval(P i )} .

Indeed, if x ∈ sval(P i ), then there exists x ∈ P i such that sval(x) = x. Therefore, (x, 1) ∈ Q i and (x, 0) ∈ sval(Q i ). Conversely, if (x, 0) ∈ sval(Q i ), then there exist λ ≥ 0 and x ∈ P i such that sval(λ) = 0 and x = sval(λx) = sval(λ) + sval(x) = sval(x). Therefore x ∈ sval(P i ) and ( 37) is satisfied. Let Y = m i=1 sval(Q i ) ⊆ T d+1 ± . By [START_REF] Joswig | Essentials of tropical combinatorics[END_REF], we get

Y ∩ {x d+1 = 0} = { (x, 0) | x ∈ X} . (38)
Applying Theorem 6.3 to the set Y , there exists a finite set U = {u 1 , . . . , u n } ⊂ T d+1 ± such that Y = cone TC (U ). Since Y is a cone, we can suppose that U contains O. Moreover, we have y d+1 ≥ O for every y ∈ Y . Hence, we can scale every point u (i) ∈ U in such a way that u (i) d+1 ∈ {O, 0}. Thus, we can write U = V ∪ Ŵ where V contains the elements of U whose last coordinate is 0 and Ŵ contains the elements whose last coordinate is O. Since U contains O, the set Ŵ is nonempty. Since X is nonempty, [START_REF] Joswig | Weighted digraphs and tropical cones[END_REF] implies that V is also nonempty. Therefore, by combining [START_REF] Joswig | Weighted digraphs and tropical cones[END_REF] with Lemma 3.32 we get

X = conv TC { v λ w | v ∈ V, w ∈ W, λ ∈ T ≥O } ,
where V, W are the projections of V , Ŵ obtained by deleting the last coordinate.

To prove the implication (ii) ⇒ (i), we define V = {(v, 0) : v ∈ V } and Ŵ = {(w, O) : w ∈ Ŵ }. By Theorem 6.3, we have

cone TC ( V ∪ Ŵ ) = n i=1 x ∈ T d+1 ± a i,1 x 1 ⊕ • • • ⊕ a i,d+1 x d+1 O
for some finite set {a 1 , . . . , a n } ∈ T d+1 ± \ {O}. By Lemma 3.32 we have the equality {(x, 0) : x ∈ X} = cone TC ( V ∪ Ŵ ) ∩ {x d+1 = 0} and therefore

X = n i=1 x ∈ T d+1 ± a i,d+1 ⊕ a i,1 x 1 ⊕ • • • ⊕ a i,d x d O .
We conclude with a strengthening of the separation theorems in [42, Section 5] using the Pash property of TO-convexity shown in Theorem 3.3. Theorem 6.5. Suppose that a set X ⊆ T d ± is TO-convex. Then, the set cl(X) is equal to the intersection of closed tropical halfspaces that contain it.

Furthermore, if X is a nonempty TO-convex cone, then cl(X) is equal to the intersection of linear closed tropical halfspaces that contain it.

Proof. Let X be a TO-convex set. It is obvious that cl(X) is included in the intersection of closed tropical halfspaces that contain it. To prove the opposite inclusion, let y / ∈ X. We can find 1 , . . . , d , r 1 , . . . , r d ∈ T ± such that

Conclusion

One of our main results is the representation of a finitely generated TC-convex set as an intersection of closed tropical halfspaces in Theorem 6.1. Furthermore, we show in Theorem 4.10 that also the valuation of a closed convex semialgebraic set has such a representation. This motivates the following.

Such a more general statement could be deduced from a more direct proof of the representation by halfspaces. On one hand, it would be interesting to get stronger separation without relying on the separation results over Puiseux series by using Lemma 4.13 in the proof of Theorem 6.1. On the other hand, the proof of Theorem 5.3 uses the Kuratowski-Zorn lemma which is highly non-constructive. An approach for the former question would be via a better understanding of the operator Faces(•). In Definition 3.11, we introduced it as a crucial building block for the structure of TC-convex sets. On a more abstract level, the operator produces certain cubical subcomplexes of the cubical complex formed by the faces of a hypercube. A better understanding of these complexes might lead to a better bound.

2 Figure 1 .Definition 2 . 3 .

 2123 Figure 1. An open and a closed signed tropical halfspace.

Lemma 2 . 4 .

 24 The set H + (a) is closed, its interior is equal to H + (a), and the closure of H + (a) is equal to H + (a).

2 . 2 .Lemma 2 . 6 .

 2226 a) is open. Also, [42, Lemma 5.2] shows that H + (a) is the closure of H + (a). In particular, H + (a) is included in the interior of H + (a). To finish, we note that the interior of H + (a) cannot contain any point that belongs to H(a) ⊆ H -(a) because H -(a) is the closure of H -(a) and H + (a) ∩ H -(a) = ∅. Basic calculations in S. We collect and extend basic properties from [42]. Lemma 2.5 ([42, Lemma 2.6]). Let a, b, c, d ∈ S. (a) a ⊕ c b ⇔ a b c (b) a b ∧ c d ⇒ a ⊕ c b ⊕ d. (c) If c ∈ T ± , then b c and c a imply b a. (d) a b implies c a ⊕ d c b ⊕ d for c ∈ T ≥O and c b ⊕ d c a ⊕ d for c ∈ T ≤O . Let a, b, c ∈ S. Then,

  Case 1 (c ∈ T • ) Adding the equivalent relations a c and b c side-wise yields a ⊕ b •c. This is equivalent to a ⊕ b • c O and shows the required as in this case •c = c = c. Case 2 (c ∈ T ± ) Without loss of generality, we can assume that c ≥ O. With a c this implies |a| ≥ |c|. Combining a c and c b yields a ⊕ b O in this case. With |a ⊕ b| = |a| ⊕ |b| ≥ |a| ≥ |c| we get a ⊕ b c ≥ c by checking the two possibilities a ⊕

Lemma 2 . 15 .

 215 Fix a, b ∈ T ± with tsgn(a) = tsgn(b) and let x

  p . Due to tsgn(a) = tsgn(b), this yields a⊕b ≤ min x

  The hull operator extends by setting conv TO (M ) = M ⊆S,S TO-convex S = T ⊆M,T finite conv TO (T ) .

Theorem 3 . 2 ([ 42 ,

 3242 Theorem 5.1]). The TO-convex hull of a finite subset M ⊆ T d ± equals the intersection of all open halfspaces containing M , i.e., conv TO (M ) = M ⊂H + (a) H + (a)

2 Figure 2 .

 22 Figure 2. The Pasch property in the real plane.

2 Figure 3 .

 23 Figure 3. The Pasch property in the TO-convexity is satisfied.

2 Figure 4 .

 24 Figure 4. The Pasch property in the TC-convexity is not satisfied; see Example 3.16.

Figure 5 .

 5 Figure 5. TO-convex intervals and TC-convex intervals in the plane (see Example 3.15)

Example 3 . 16 .

 316 As in Example 3.4, let a = (0, 0), b 1 = (O, 0), b 2 = (0, 0), c 1 = ( 0, 0), and c 2 = (O, 1). Figure 4 depicts this configuration of points. Note that we have b 1 ∈ Faces(a, c 1 ) and b

Example 3 .

 3 [START_REF] Develin | Tropical convexity[END_REF]. Let X = { 0, 0} d . Then, Lemma 3.23 shows that conv TC (X) = [ 0, 0] d . In particular, we have O ∈ conv TC (X). Moreover, if Y X is any strict subset of X, then Lemma 3.23 shows that conv TC (Y ) is the union of faces of [ 0, 0] d whose vertices belong to Y . In particular, O / ∈ conv TC (Y ). This example shows the lower bound c d ≥ 2 d for the Carathéodory number of TC-convexity. We do not know what is the optimal value of c d . Definition 3.29. Given an arbitrary set X ⊆ T d ± , we denote cone TC

Definition 4 . 3 .

 43 Given a point x ∈ T d ± we define its canonical lift, cli(x) ∈ K d , as the point ∀i ∈ [d], cli(x) i = σt |xi| ,

  Furthermore, the set sval H + (a) is closed by [36, Theorem 6.9] or, equivalently, [13, Corollary 4.11]. Therefore, Lemma 2.4 implies that sval H + (a) = H + (a).

Lemma 4 . 7 .

 47 Suppose that H + (a) is a tropical halfspace of type J ⊆ [d]. Let x ∈ H + (a) and denote K = [d] 0 \ J. Then li J (x) ∈ H + li K (a) .

Proposition 4 . 8 .

 48 Suppose that X, Y ⊆ K d are two nonempty convex semialgebraic sets such that X ∩ Y = ∅. Then, there exists a halfspace H+ (a) such that X ⊆ H + (a) and Y ⊆ H -(a).Proof. If we replace K by R, then the claim follows from the hyperplane separation theorem in R d , see, e.g.,[START_REF] Rockafellar | Convex Analysis[END_REF] Theorem 11.3 and Theorem 11.7]. Since the sets X, Y are supposed to be semialgebraic, the claim for K follows from the completeness of the theory of real closed fields, see, e.g.,[START_REF] Marker | Model Theory: An Introduction[END_REF] Corollary 3.3.16] or[START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] Theorem 2.80].

Corollary 5 . 5 .

 55 Let X = x ∈ T d ≥O x 1 > O . If G ⊆ X is a relative conic TChemispace w.r.t. X and G∩T d >O / ∈ {∅, T d >O }, then there exists a vector (a 1 , . . . , a d ) ∈ T d ± , (a 1 , . . . , a d ) = O, such that H + (O, a) ∩ X ⊆ G ⊆ H + (O,a) ∩ X. Proof. By Proposition 5.4, there exists a vector (a 1 , . . . , a d ) ∈ T d ± , (a 1 , . . . , a d ) = O, such that H + (O, a) ∩ T d >O ⊆ G ∩ T d >O ⊆ H + (O, a) ∩ T d >O . Let x ∈ H + (O, a) ∩ X be any point and let y ∈ T d

Lemma 5 .

 5 6 implies that G∩int(Q 1 ) = {∅, int(Q 1 )}. Hence, by applying Lemmas 5.6 and 5.7 toT = (Q 1 ∪Q 2 )∩X we get that H + (a)∩Q 2 ∩X ⊆ G∩Q 2 ⊆ H + (a)∩Q 2 ∩X and G ∩ int(Q 2 ) = {∅, int(Q 2 )}.By repeating this reasoning, we obtain the claim. Case 2 (We have | supp(a)| = r = 2.) In this case, let {k, l} = supp(a) and let Q {k} , Q {l} , Q {k,l} be the orthants obtained from T d ≥O by flipping the signs of the components indexed by k and l. Since T d

  0 else then y ∈ G and x y / ∈ G. Hence, we have x / ∈ G and x ∈ int(Q {k,l} ). This implies G ∩ int(Q {k,l} ) / ∈ {∅, int(Q {k,l} )}. Now, by Corollary 5.5, there exists a vector b ∈ T d ± \ {O} such that H + (O, b) ∩ Q {k,l} ⊆ G∩Q {k,l} ⊆ H + (O, b)∩Q {k,l} . By applying Lemma 5.6 to Q {k,l} ∪Q {k} and Q {k,l} ∪ Q {l} we get supp (b) = supp (a) = {l} and supp ⊕ (b) = supp ⊕ (a) = {k}. By scaling a and b, we can assume that a k = b k = 0. We want to show that a l = b l .

Theorem 5 . 10 .

 510 If G ⊆ T d ± is a TC-hemispace and G / ∈ {∅, T d ± }, then there exists a vector (a 0 , . . . , a d ) ∈ T d+1 ± , (a 1 , . . . , a d ) = O, such that H + (a) ⊆ G ⊆ H + (a). Proof. We consider two cases. Case 1 (There exists an orthant O ∈ T d ± such that G ∩ int(O) / ∈ {∅, int(O)}.) By flipping signs, we assume that O = T d ≥O . Let X = x ∈ T d+1 ± x d+1 > O . We define two sets H, H ⊆ X by putting H = cone TC { (z, 0) | z ∈ G} \ {O} and H = cone TC { (z, 0) | z /

Corollary 5 . 11 . 5 . 3 .

 51153 If G ⊆ T d ± is a TO-hemispace and G / ∈ {∅, T d ± }, then there exists a vector (a 0 , . . . , a d ) ∈ T d+1 ± , (a 1 , . . . , a d ) = O, such that H + (a) ⊆ G ⊆ H + (a). The boundary of TC-hemispaces. Before stating the next lemmas, we introduce the following notation. If a = (a 0 , . . . , a d ) ∈ T d+1 ± and x ∈ T d ± , then we denoteArgmax(a, x) = { k ∈ [d] 0 | a k x k = O ∧ ∀ ∈ [d] 0 , |a k | + |x k | ≥ |a | + |x |} = argmax k∈[d]0 |a k x k | ∩ supp(a) ∩ supp(x) and Argmax + (a, x) = { k ∈ Argmax(a, x) | a k x k > O} ,where we use the convention that x 0 = 0. Note that Argmax + (a, x) ⊆ Argmax(a, x) ⊆ supp(x) ∪ {0}.

ForFigure 7 .

 7 Figure 7. Argmax and Argmax + for ( 0, -1, -1)

  x), O otherwise belongs to G. Now we can apply the Case 1a with v instead of x since O = |v j | ≤ |y j | for all j ∈ Argmax(a, x). Hence, we obtain y ∈ G. Case 2 (There exists an ∈ Argmax(a, x) ∩ [d] such that y = x .) Let ρ = |y | |x | -1 ∈ R and consider the point x = ρ x. Then, for each j ∈ Argmax(a, x) ∩ [d] we have |a j | |x j | = ρ |a j | |x j | = ρ |a | |x | = |a | |y | = |a j | |y j | .

2 Figure 8 .Lemma 5 . 16 .

 28516 Figure 8. Possibilities of boundary of TC-hemispace sandwiched between x 1 ≥ 0 and x 1 > 0 or x 1 ≥ O and x 1 > O.

  let

  which implies y k = sval(y k ) = z k . Analogously, we obtainy k = z k if a k < O and z k < O. In particular, y k = z k for every k ∈ Argmax + (a, z) ∩ [d].Furthermore, for every ∈ [d] we have |z | ≤ y ≤ |z | by Lemma 4.2. Therefore, y ∈ G by Lemma 5.16. Moreover, we have y ∈ X. Indeed, this is trivial if a 0 = O. Otherwise, Argmax + (a, z) ∩ [d] = ∅ and so a k y k = O for at least one k ∈ [d]. Thus, we have sval(G = ) = G ∩ X.

  i ) for some a 1 , . . . , a m ∈ T d+1 ± . For every i ∈ [m], let H i = H + cli(a i ) . By Lemma 4.6 we have X = m i=1 H + (a i ) = m i=1 sval(H i ).The implication (iv) ⇒ (iii) is trivial and the implication (iii) ⇒ (i) follows from Lemma 4.14.

1 < y 1

 1 < r 1 , 2 < y 2 < r 2 , . . . , d < y d < r d and such that the boxB = [ 1 , r 1 ] × [ 2 , r 2 ] × • • • × [ d , r d ] does not intersect cl(X).Since B and X are TO-convex and disjoint, Theorem 3.3 implies that there exists a TO-hemispace G such that X ⊆ G and B ⊆ T d ± \ G. Therefore, by Theorem 5.10, there exists a closed tropical halfspace H + (a) such that cl(X) ⊆ H + (a) and B ⊆ H -(a). Furthermore, y belongs to the interior of B and so we have y ∈ H -(a) by Lemma 2.4. Since y was arbitrary, we get the first claim. To prove the second claim, suppose that X is a nonempty TO-convex cone and let y / ∈ cl(X). By the first part of the theorem, there exists a ∈ T d+1 ± such that cl(X) ⊆ H + (a) and y ∈ H -(a). Since X is a nonempty cone, we have O ∈ cl(X). In particular, a 0 ≥ O. Let ã = (O, a 1 , . . . , a d ). Then, y ∈ H -(ã). Suppose that x ∈ cl(X) is such that x / ∈ H + (ã). Then, a 1 x 1 ⊕ • • • ⊕ a d x d < O and so λ x ∈ H -(a) for a sufficiently large λ > O. This gives a contradiction with cl(X) ⊆ H + (a). Hence, we have cl(X) ⊆ H + (ã), which finishes the proof.

Conjecture 7 . 1 .

 71 For all closed TC-convex sets, we haveX = a∈T d+1 ± H + (a) X ⊆ H + (a) .

Question 7 . 2 .

 72 How can one deduce Theorem 6.1 in a more constructive way? Example 3.28 discusses the Carathéodory number c d of TC-convexity. The examples gives a lower bound c d ≥ 2 d complementing the upper bound c d ≤ d2 d + 1 given in Proposition 3.27. Recall that TC-convexity extends the 'usual' tropical convexity which has Carathéodory number d + 1 as already shown in [34, 28, 21]. Question 7.3. What is the Carathéodory number of TC-convexity?

  and, hence, of C. Furthermore, we get v ∼ z proving the claim. Corollary 3.21. We have y ∈ Faces(x 1 , . . . , x n ) if and only if for every ∼ ∈ {≤, ≥} d there exists w

  Hence, by Proposition 4.8, there exists a ∈ K d+1 such that X ⊆ H

			-(sval(a))
	by Lemma 4.6. Since y belongs to the interior of B, Lemma 2.4 shows that y ∈
	H -(sval(a)). In particular, we have y / ∈ H	+ (sval(a)). To prove the second part
	of the claim, note that sval(X) ⊆ H	+ (sval(a)) by Lemma 4.6. In other words,
	the closed tropical halfspace H	+ (sval(a)) contains sval(X) but not y. Since y was
	arbitrary, we get that sval(X) is an intersection of some family of closed tropical
	halfspaces. Therefore, it is also an intersection of all the closed tropical halfspaces
	that contain it.

+ (a) and B ⊆ H -(a). Therefore B ⊆ H Corollary 4.11. If X ⊆ K d from Theorem 4.10 is a cone, we can choose the tropical halfspaces to be linear.

Proof. To see that, suppose that a 0 = 0. Since 0 ∈ X, we have a 0 > 0. Consider â = (0, a 1 , . . . , a d ). Since H + (â) ⊆ H + (a), we get y / ∈ H + (sval(â)) by Lemma 4.6.

  in such a way that a 0 = 0 by Corollary 4.11; hence, we let a ∈ K d . Let O ⊂ K d be a closed orthant such that a = (a 1 , . . . , a d ) ∈ O. By (27) we have a ∈ cone(U O ). Denote U O = {u 1 , . . . , u m }. Since the orthant O is fixed, we have sval(a) ∈ cone TC (sval(U O )) by [8, Lemma 8]. Suppose that y ∈ H

	The inclusion "⊆" follows by combining (27) with Lemma 4.6. To prove the opposite inclusion, let y / ∈ sval(P ). By Theorem 4.10, there exists a ∈ K d+1 such that P ⊆ H + (a) and y / ∈ H + (sval(a)). Since P is a cone, we can H + (O, y), which implies that y ∈ H + (O, sval(a)), giving a contradiction. Hence, there exists i ∈ [m] such that y / ∈ H + (O, sval(u i )). Since y was arbitrary, choose a Therefore sval(a) ∈ we get u∈U H

the set of all rays obtained in this way. We claim that sval(P ) = u∈U H + (O, sval(u)). + (O, sval(u i )) for all i ∈ [m]. Then, we also have sval(u i ) ∈ H + (O, y) for all i ∈ [m]. As closed halfspaces are convex by Corollary 3.8, we get conv TC (sval(U O )) = conv TC sval(u 1 ), . . . , sval(u m ) ⊆ H + (O, y). Furthermore, since the tropical halfspace H + (O, y) is linear, we get conv TC (sval(U O )) ⊆ H + (O, y). + (O, sval(u)) ⊆ sval(P ).

  , [39, Section 4],[START_REF] Daniel Ehrmann | The geometric structure of max-plus hemispaces[END_REF] Section 4]. Proposition 5.4 can be extended to characterize relative hemispaces that are included in the nonnegative orthant and contain (parts of) the boundary of T d ≥O . The next corollary gives one such extension that is needed in our proofs.

	Proposition 5.4. If G ⊆ T d >O is a relative conic TC-hemispace w.r.t. T d >O and
	G / ∈ {∅, T d

>O }, then there exists a vector (a 1 , . . . , a d )

∈ T d ± , (a 1 , . . . , a d ) = O, such that H + (O, a) ∩ T d >O ⊆ G ⊆ H + (O, a) ∩ T d >O .

Acknowledgements

We thank the 2021 HIM program Discrete Optimization during which part of this work was developed.

If m = 0, then we have y j = x j for all j ∈ Argmax(a, x) and so the claim follows from Lemma 5.14.

If m > 0, there is a k ∈ Argmax + (a, y) \ Argmax + (a, x). Consider the point z ∈ T d ± defined as

Then, we have z ∈ G be the induction hypothesis. Furthermore, since |a 0 | < 1 + |a k | + |y k |, the point w ∈ T d ± defined as

belongs to H + (a). In particular, w ∈ G. Since y = (-1) w z, we get y ∈ G.

Combining the previous lemmas leads to the following description, when two points have the same Argmax(a, •). It shows that the structure of hemispaces behaves rather well with respect to fixing Argmax. In particular, the following statement extends [START_REF] Daniel Ehrmann | The geometric structure of max-plus hemispaces[END_REF]Lemma 3.1].

Proposition 5.17. Let y ∈ T d ± be such that Argmax(a, x) = Argmax(a, y) and Argmax + (a, x) ⊆ Argmax + (a, y). Then, we have y ∈ G. Lemma 5.16 implies z ∈ G. Furthermore, Argmax(a, z) = Argmax(a, x) = Argmax(a, y) and tsgn(z j ) = tsgn(y j ) for all j ∈ Argmax(a, z)∩ [d]. Hence, we have y ∈ G by Lemma 5.14.

5.4.

Lifts of TC-hemispaces. As a final ingredient for the proof of Theorem 6.1, we relate TC-hemispaces with convex lifts. For this, we construct specific lifts in the sense of Section 4 based on the structural insights for TC-hemispaces in Section 5 so far.

Otherwise, Theorem 5.10 shows that there exists a = (a 0 , . . . ,

We prove the claim by induction over d. If d = 1, then the claim follows from the fact that, for any a ∈ T ± , each set

Note that X is essentially the set of points whose support is disjoint from the support of a. We will construct a lift for the intersection of G with X and X and finish by taking their convex hull.

We start by showing that there exists a convex set We give more explanations for the statement and proof of Proposition 4.8. We refer to [START_REF] Marker | Model Theory: An Introduction[END_REF]Corollary 3.3.20] for another example of a proof that works in the same way.

Extended proof of Proposition 4.8. Recall that X, Y ⊆ K d are two nonempty convex semialgebraic sets such that X ∩ Y = ∅. Since X, Y are semialgebraic, there exist two first-order formulas φ(x 1 , . . . , x d , y 1 , . . . y n1 ), ψ(x 1 , . . . , x d , y 1 , . . . , y n2 ) in the language of ordered fields and two vectors r ∈ K n1 , s ∈ K n2 such that

For every w ∈ K n1 , z ∈ K n2 , let X w , Y z be the semialgebraic sets defined as

Now, the statement "For every w, z such that X w , Y z are nonempty, convex, and disjoint, there exists a vector a such that X w ⊆ H + (a) and

can be written as sentence in the language of ordered fields. This sentence is true over R by the hyperplane separation theorem, and so it is true over K by the completeness of the theory of real closed fields. By taking (w, z) = (r, s) we obtain the claim.

Example A.1. The assumption that both sets X, Y are semialgebraic cannot be dropped from Proposition 4.8 as the following example, taken from [START_REF] Robson | Separating points from closed convex sets over ordered fields and a metric for Rn[END_REF], shows.

In this way, A ∪ B is the set of nonnegative Puiseux series, A does not have a least upper bound in K, B does not have a greatest lower bound in K, and a < b for all

where

We note that X is nonempty because it contains (0, 0). Also, both X 1 and X 2 arise as intersections of closed convex sets, so X 1 and X 2 are both convex and closed. Hence X is closed. To see that X is also convex, let (x 1 , y 1 ) ∈ X 1 and (x 2 , y 2 ) ∈ X 2 be such that x 1 > 0 and x 2 < 0. Pick λ ∈ [0, 1] such that λx 1 + (1 -λ)x 2 = 0 and let z = max(0, y 1 /x 1 ). Since z is a lower bound for B, we have z ∈ A. Hence λy 1 + (1 -λ)y 2 ≤ z(λx 1 + (1 -λ)x 2 ) = 0. Therefore, the point λ(x 1 , y 1 ) + (1 -λ)(x 2 , y 2 ) belongs to both X 1 and X 2 . Hence, the whole segment between these two points belongs to X. Despite the fact that X is closed and convex, it cannot be separated by a hyperplane from any point w / ∈ X. To see that, suppose that (c 0 , c 1 , c 2 ) is such that (c 1 , c 2 ) = (0, 0) and c 0 + c 1 x + c 2 y ≥ 0 for all (x, y) ∈ X. Since (t x , 0), (0, -t x ), (-t x , -t x ), (t x , t x-0.5 ) ∈ X for arbitrarily large values of x > 0, we have c 1 > 0 and c 2 < 0. Let z = c 1 /|c 2 |. If z ∈ A, then by taking any z ∈ A that is greater than z and considering the points (t x , z t x ) ∈ X we get c 0 + c 1 t x + c 2 z t x ≥ 0 ⇐⇒ z ≤ z + (c 0 /|c 2 |)t -x , which is a contradiction for x large enough. Likewise, if z ∈ B, then by taking any z ∈ B that is smaller than z and considering the points (-t x , -z t x ) ∈ X we get c 0 -c 1 t xc 2 z t x ≥ 0 ⇐⇒ z ≥ z -(c 0 /|c 2 |)t -x , which is a contradiction for x large enough.

(Georg Loho) University of Twente, Department of Applied Mathematics, The Netherlands, Email address: g.loho@utwente.nl (Mateusz Skomra) LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France, Email address: mateusz.skomra@laas.fr