Cordian Riener
email: cordian.riener@uit.no

Mohab Safey
email: mohab.safey@lip6.fr

Real root finding for equivariant semi-algebraic systems

Let R be a real closed field. We consider basic semi-algebraic sets defined by n-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d < n. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most 2d -1 distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by s polynomials of degree d in time (sn) O(d) . This improves the state-of-the-art which is exponential in n. When the variables x1, . . . , xn are quantified and the coefficients of the input system depend on parameters y1, . . . , yt, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time (sn) O(dt) .

Let S n denote the group of permutations on a set of cardinality n. This group acts on R n by permuting the coordinates. One says that a subset of R n is symmetric when it is closed under this action. Let now f ∈ R[x 1 , . . . , x n ]. One says that f is invariant under the action of S n (or in short S n -invariant) when for all σ ∈ S n , f (σx) = f for x = (x 1 , . . . , x n ). The following result summarizes the current state-ofthe-art on symmetric semi-algebraic sets.

Theorem 1 ([50, 51, 65]). Let {f, f 1 , . . . , f s } ⊂ R[x 1 , . . . , x n ] be S n -invariant polynomials of degree at most d.

A. The real algebraic set V R (f ) is not empty if and only if it contains a point with at most ⌊ d 2 ⌋ distinct coordinates. B. The semi-algebraic set in S ⊂ R n defined by f 1 ≥ 0, . . . , f s ≥ 0 is not empty if and only if it contains a point with at most d distinct coordinates.

 Example 2]). When analyzing the equilibrium points of such systems w.r.t. parameters λ, we are led to solve equivariant semialgebraic systems. Main results. We provide a positive answer to this question. More precisely, the following holds. (i) On input F and G as above, deciding the emptiness of S(F, G) ∩ R n can be done in time n O(d) .

(ii) On input F and G in R[y 1 , . . . , y t ][x 1 , . . . , x n ] such that F and G satisfy the above S n -invariance and equivariance assumptions, the quantifier elimination problem ∃x ∈ R n F = 0, G > 0 can be solved in time n O(dt) . This result, which generalized Theorem 1, is of particular interest on families of systems where d is fixed and n grows. They are obtained by proving that S(F, G) is not empty if and only if it contains a point with at most 2d -1 distinct coordinates. A key ingredient to establish such a property is the use of representation theory for equivariant maps and basic results from polynomial optimization. Combining such a geometric result with efficient algorithms for real root finding or one-block quantifier elimination yields the above complexity results. More accurate complexity results (with explicit constants in the exponent) are given under some assumptions which are proved to be generic. We also report on practical experiments illustrating that algorithms described in this paper can tackle semi-algebraic systems which are out of reach of the current state-of-the-art.

Introduction

Let R be a real closed field. A semi-algebraic set is a subset of R n defined by a boolean formula whose atoms are polynomial equalities and inequalities with coefficients in R. In this article, we consider basic semi-algebraic sets defined as follows. Given F = (f 1 , . . . , f k ) and G = (g 1 , . . . , g s ) in R[x 1 , . . . , x n ], we denote by S(F, G) ⊂ R n the semi-algebraic set defined by f 1 = • • • = f k = 0, g 1 ≥ 0, . . . , g s ≥ 0. These sets arise in many areas of engineering sciences such as computational geometry, optimization, robotics (see e.g. [START_REF] Canny | The complexity of robot motion planning[END_REF][START_REF] Everett | The voronoi diagram of three lines[END_REF][START_REF] Tannenbaum | Robotic manipulators and the geometry of real semialgebraic sets[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]). Algorithmic problems encompass real root finding, connectivity queries, or quantifier elimination. Such problems are intrinsically hard [START_REF] Blum | Complexity and real computation[END_REF]. In the worst case, solving quantifier elimination over the reals is doubly exponential in n and polynomial in the maximum degree of the input polynomials, see [START_REF] Davenport | Real quantifier elimination is doubly exponential[END_REF]. This complexity is achieved by the Cylindrical Algebraic Decomposition algorithm [START_REF] Brown | The complexity of quantifier elimination and cylindrical algebraic decomposition[END_REF]. The idea of reducing real root finding to polynomial optimization in [START_REF] Seidenberg | A new decision method for elementary algebra[END_REF] is used in [START_REF] Grigoriev | Solving systems of polynomials inequalities in subexponential time[END_REF] to obtain the first algorithm with singly exponential complexity in n. This led to improvements for the decision problem [START_REF] Canny | Some algebraic and geometric computations in pspace[END_REF][START_REF] Heintz | On the theoretical and practical complexity of the existential theory of the reals[END_REF][START_REF] Renegar | On the computational complexity and geometry of the first order theory of the reals[END_REF][START_REF] Basu | A new algorithm to find a point in every cell defined by a family of polynomials[END_REF], quantifier elimination [START_REF] Heintz | Sur la complexité du principe de tarski-seidenberg[END_REF][START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF][START_REF] Hong | Variant quantifier elimination[END_REF] and connectivity queries [START_REF] Canny | The complexity of robot motion planning[END_REF][START_REF] Canny | Computing roadmaps in general semi-algebraic sets[END_REF][START_REF] Heintz | Single exponential path finding in semi-algebraic sets II: The general case[END_REF][START_REF] Gournay | Construction of roadmaps in semi-algebraic sets[END_REF][START_REF] Basu | Computing roadmaps of semi-algebraic sets (extended abstract)[END_REF][START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]. Later, polar varieties are introduced in [START_REF] Bank | Polar varieties and efficient real equation solving: the hypersurface case[END_REF] for the decision problem [START_REF] Bank | Polar varieties and efficient real elimination[END_REF][START_REF] Bank | Generalized polar varieties: Geometry and algorithms[END_REF][START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF][START_REF] Bank | Bipolar varieties and real solving of a singular polynomial equation[END_REF][START_REF] Bank | Intrinsic complexity estimates in polynomial optimization[END_REF], for computing roadmaps [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] or polynomial optimization [START_REF] Guo | Global optimization of polynomials using generalized critical values and sums of squares[END_REF][START_REF] Greuet | Probabilistic algorithm for polynomial optimization over a real algebraic set[END_REF][START_REF] Bank | Intrinsic complexity estimates in polynomial optimization[END_REF][START_REF] Greuet | Global optimization of polynomials restricted to a smooth variety using sums of squares[END_REF]. Complexity bounds are then cubic in some Bézout bound as well as practically efficient algorithms.

To break this curse of dimensionality, one exploits algebraic properties of systems defining semi-algebraic sets arising in applications. This has led to improvements, for e.g. the quadratic case [START_REF] Barvinok | Feasibility testing for systems of real quadratic equations[END_REF][START_REF] Grigoriev | Polynomial-time computing over quadratic maps[END_REF], the multihomogeneous case [START_REF] Bonnard | Determinantal sets, singularities and application to optimal control in medical imagery[END_REF][START_REF] Henrion | Real root finding for determinants of linear matrices[END_REF] and the important case of symmetric semi-algebraic sets. Related works. We already mentioned several previous works which led to Theorem 1. More generally, the question of using symmetry in the context of real algebraic geometry is not new. Fundamental work started with [START_REF] Procesi | Positive symmetric functions[END_REF][START_REF] Procesi | Inequalities defining orbit spaces[END_REF] which study the quotient of semi-algebraic sets, which are invariant under the action of a compact Lie group. In particular, Positivstellensätze for invariant polynomials which are non-negative on invariant semi-algebraic sets are derived. This line of work is further generalized by [START_REF] Bröcker | On symmetric semialgebraic sets and orbit spaces[END_REF] and was applied for example in [START_REF] Cimpric | Sums of squares and moment problems in equivariant situations[END_REF] to the context of the moment problem. A different line of work initiated by [START_REF] Gatermann | Symmetry groups, semidefinite programs, and sums of squares[END_REF] consists in exploiting symmetries in the context of sums of squares relaxations of polynomial optimization. In particular, for optimization problems which are invariant by the symmetric group, a variety of strategies are exhibited in [START_REF] Riener | Exploiting symmetries in sdp-relaxations for polynomial optimization[END_REF]. The topology of semi-algebraic sets defined by symmetric polynomials is also easier to understand: [START_REF] Basu | Bounding the equivariant betti numbers of symmetric semi-algebraic sets[END_REF][START_REF] Basu | Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets[END_REF] derived efficient algorithms to calculate e.g. their Euler-Poincaré characteristic. With a more algebraic flavour, computer algebra has been developed to solve polynomial systems which are invariant under the action of some groups. Approaches for this longstanding problem focus on the zerodimensional case and aim at describing algebraically the solution set. When all equations are invariant, invariants can be used for this purpose [START_REF] Colin | Solving a system of algebraic equations with symmetries[END_REF][START_REF] Sturmfels | Algorithms in invariant theory[END_REF]. Such an approach is completed by the use of SAGBI Gröbner bases techniques [START_REF] Faugère | Solving systems of polynomial equations with symmetries using sagbigröbner bases[END_REF][START_REF] Thiéry | Computing minimal generating sets of invariant rings of permutation groups with sagbigrobner basis[END_REF]. When the system is globally invariant, [START_REF] Faugère | Solving Polynomial Systems Globally Invariant Under an Action of the Symmetric Group and Application to the Equilibria of N vortices in the Plane[END_REF][START_REF] Faugère | Gröbner bases of ideals invariant under a commutative group: the nonmodular case[END_REF] provides an efficient dedicated Gröbner basis algorithm (see also [START_REF] Steidel | Gröbner bases of symmetric ideals[END_REF][START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF] for further developments). Structure of the paper. Section 2 recalls properties of symmetric semi-algebraic sets and explains why a direct generalization of Theorem 1 is hopeless. Section 3 provides a proof that S(F, G) is not empty iff it contains a point with at most 2d -1 distinct coordinates. Section 4 provides a description of the algorithms and the analysis of their complexity. Section 5 reports on practical performances.

Preliminaries

A crucial condition in Theorem 1 is that all the polynomials defining the considered semi-algebraic sets are indeed symmetric. Such an assumption is easily bypassed in the case of real algebraic sets.

Corollary 2. Let f 1 , . . . , f k ∈ R[X 1 , . . . , X n ] with deg f i ≤ d for all i. Then V R (f 1 , . . . , f n ) is not
empty if and only if it contains a point with at most d distinct coordinates.

Proof. Consider the polynomial g := k i=1 σ∈Sn σ(f i ) 2 . Then we have an equality of the real varieties V R (g) = V R (f 1 , . . . , f n ) and g is symmetric of degree 2d and in this situation statement (A) in Theorem 1 yields the result.

However, in many applications the semi-algebraic set is defined by polynomials that are not themselves symmetric. It is feasible to replace the non-invariant inequalities by a set of new inequalities which describe the same set but are invariant [START_REF] Bröcker | On symmetric semialgebraic sets and orbit spaces[END_REF]: any symmetric semi-algebraic set defined by s inequalities can be defined with s + 1 inequalities which are invariant by the action of the symmetric group (see also [START_REF] Cimpric | Sums of squares and moment problems in equivariant situations[END_REF][START_REF] Hubert | Invariant Algebraic Sets and Symmetrization of Polynomial Systems[END_REF] for a constructive approach). However, such a "symmetrization" process comes at a price: In general it will increase the degree of the polynomials drastically. We illustrate this phenomenon in the following easy example.

Example 3. Consider the positive orthant S

:= {x = (x 1 , . . . , x n ) ∈ R n : x 1 ≥ 0, . . . , x n ≥ 0}.
Clearly, S is symmetric. By considering the map which sends the coordinates of x ∈ R n to the coefficients of the polynomial h(t) := n i=1 (t-x i ) one can prove that S is equivalently defined by e 1 (x) ≥ 0, . . . , e n (x) ≥ 0 where e i denotes the i-th elementary symmetric polynomial. One implication is immediate: x ∈ S clearly entails that e i (x) ≥ 0 for 1 ≤ i ≤ n. We prove the other implication by induction on n. The case n = 1 is clear. Now let x = (x 1 , . . . , x n ) ∈ R n be not in S, i.e., let one of its coordinates be negative. Besides, without loss of generality we can assume that all x i = 0 (since S has non-empty interior). We show further that this implies that there exists 1 ≤ i ≤ n such that e i (x) < 0. Clearly, in the case when exactly one coordinate of x is negative we have e n (x) < 0 and hence our claim follows. Therefore, we assume that at least two coordinates are negative. We consider the polynomial h(t) as defined above. i.e., h(t) = t n + n i=1 (-1) i e i (x)t n-i . Notice that, by construction, all roots of h are real. By Rolle's Theorem, there exists a root of its derivative h ′ := ∂h ∂t between every two roots of h. Since h has by construction at least two negative roots, h ′ has a negative root. Consider (x 1 , . . . , xn-1 ) ∈ R n-1 the n -1 roots of h ′ (ordered decreasingly). Since (x 1 , . . . , xn-1 ) is not in the n -1 dimensional positive orthant we can apply the induction hypothesis to the case n -1 to infer that at least for one j ∈ {1, . . . , n -1} we have e j (x 1 , . . . , xn-1 ) < 0. But since h ′ is the derivative of h this clearly implies e j (x 1 , . . . , x n ) = 1 n-j e j (x 1 , . . . , xn-1 ) < 0. Of course, the description of S with symmetric polynomials is not unique. However, it follows from the equivalence shown above that no other description with symmetric polynomials can involve only symmetric polynomials of degree smaller than n. Indeed, suppose that S := {x ∈ R n : g 1 (x) ≥ 0, . . . , g m (x) ≥ 0}, where each g i is a symmetric polynomial. It is classically known that each symmetric polynomial can be uniquely represented as a polynomial in the elementary symmetric polynomials, i.e. for each i we have a polynomial γ i ∈ R[e 1 , . . . , e n ] such that g i (x) = γ i (e 1 (x), . . . , e n (x)). Now suppose that for each i we have deg g i < n. Since the polynomials γ i are unique and deg e n = n, it follows, that for each i we must have γ i (0, 0, . . . , 0, t) = 0. Consider the point ξ := (0, 1, 2, . . . , n -1). Similarly to the above reasoning, we consider a univariate polynomial h(t) := n i=1 (tξ i ) (with ξ i = i -1). Note that e n (ξ) = 0. Since all n roots of h are distinct, hε has also n distinct real roots, for a small enough positive ε. Let ζ ∈ R n be one of the roots of hε. Then, e n (ζ) < 0 and thus ζ ∈ S. But e i (ξ) = e i (ζ) for all 1 ≤ i ≤ n -1 and we deduce that γ j (ζ) = γ j (ξ) for 1 ≤ j ≤ m. Hence, we get a contradiction with ζ / ∈ S. Therefore, every representation of S in terms of symmetric polynomials must contain at least one polynomial of degree n, hence making useless Theorem 1 for algorithmic applications.

Notice that the semi-algebraic set S defined in the example above clearly contains points for which all coordinates are the same and we note the following generalization of Theorem 1 to basic convex semialgebraic sets. Proposition 4. Let S ⊂ R n be basic convex symmetric semi-algebraic set. Then S is not empty if and only if it contains a point for which all coordinates are equal.

Proof. Suppose that S is not empty and let x ∈ S. Since S is symmetric, S also contains the orbit {σ(x) : σ ∈ S n } of x. Since S is convex, it contains the point y := 1 n! σ∈Sn σ(x) and clearly all coordinates of y are equal.

Notice that the semi-algebraic set S defined in the example above contains points for which all coordinates are the same. In view of Proposition 4 it is natural to ask, to which extent it is possible to derive statements similar to Theorem 1 for symmetric semi-algebraic sets that are defined by polynomials of low degree, which are not invariant by the action of the symmetric group. The following example shows that for general semi-algebraic sets, such a generalization is not possible: 2 and its S n orbit which we denote by F . Let S be the semi-algebraic set {x ∈ R n : ∃g ∈ F with g(x) = 0}. By construction, S is a finite set which coincides with the orbit of ξ = (1, . . . , n). Therefore, all points in S have distinct coordinates, but S is described by quadratic polynomials.

Example 5. Let f := n i=1 (x i -i)

Main geometric result

One way to generalize Theorem 1 to semi-algebraic sets that are S n -invariant but not described by symmetric polynomials is to rely on results from the theory of finite reflection groups. A finite group is called a finite reflection group, if it is generated by orthogonal reflection on a finite set of hyperplanes. These groups are extensively studied and the particular case of the symmetric group acting by permuting the coordinates falls into this framework. We refer the interested reader to [START_REF] Grove | Finite reflection groups[END_REF] for more details. Definition 6. Let φ : R n → R n be a morphism given by x → (φ 1 (x), . . . , φ n (x)) and let G be a finite reflection group. Then φ is G-equivariant if we have g(φ) = φ(g(x)) for every g ∈ G . We will write Mor G (R n , R n ) for the set of G-equivariant morphisms.

We say that a sequence of polynomials of cardinality n is G-equivariant, if it defines a G-equivariant morphism.

Example 7. Let s be a bivariate symmetric polynomial and d ∈ N. The map

(x 1 , x 2 , x 3 ) → (x d 1 + s(x 2 , x 3 ), x d 2 + s(x 1 , x 3 ), x d 3 + s(x 1 , x 2 )
) is equivariant by the action of the symmetric group S 3 . Let R[x 1 , . . . , x n ] G be the ring of polynomials in R[x 1 , . . . , x n ] which are G-invariant. There is a natural action of R[x 1 , . . . , x n ] G on the set Mor G (R n , R n ) by multiplication: it clearly preserves the equivariance. In other words, the equivariant morphisms form a module over R[x 1 , . . . , x n ] G . It follows from the work of Shchvartsman [START_REF] Shchvartsman | Some remarks on the chevalley theorem[END_REF] that this module is a free module.

Theorem 8 (Shchwartsman). For any finite reflection group

G the set Mor G (R n , R n ) is a finite R[x 1 , . . . , x n ] G - module of rank n. Furthermore, let ψ 1 , . . . , ψ n be generators of R[x 1 , . . . , x n ] G ,
then every equivariant morphism can uniquely be written as

f i = n j=1 ∂ψj ∂xi s j where s j ∈ R[x 1 , . . . , x n ] G .
In the sequel we will be interested in basic semi-algebraic sets that are generated by polynomials which are S n equivariant in the sense of Definition 6. The general machinery developed by Shchwartsman allows in the case of S n for the following corollary, which gives a convenient description of such polynomials.

Corollary 9. Let {f 1 , . . . , f n } be a set of polynomials that define an S n equivariant morphism and let

deg f i ≤ d. Then f i = d j=0 s j • x j i , where s j ∈ R[x 1 , . . . , x n ]
Sn is symmetric and of degree ≤ dj + 1. Proof. It is classically known that every symmetric polynomial can be uniquely written in terms of the first n Newton sums p i := n j=1 x i j . Thus, we can use these polynomials as generators of R[x 1 , . . . , x n ] Sn and apply Theorem 8. Since Mor Sn (R n , R n ) is a free module and the polynomials p 1 , . . . , p n are algebraically independent, the degree restrictions follow at once, since we cannot have any cancellation of degrees in the representation.

Let us denote by A 2d-1 ⊂ R n the subset of points with at most 2d -1 distinct coordinates.

≤ i ≤ k and 1 ≤ j ≤ n. Assume that for 1 ≤ i ≤ k, f i is S n invariant, that G is S n -equivariant and that deg(g j ) ≥ 2 for 1 ≤ j ≤ n.
Then, the basic semi-algebraic set S(F, G) is empty if and only if S(F, G) ∩ A 2d-1 = ∅.

Recall that p i denotes the Newton sum n i=1 x j i . For the proof of Theorem 10, we study some varieties defined by the p i 's. Let γ := (γ 1 , . . . , γ d ) ∈ R d then we denote by N γ the real variety

N γ := {x ∈ R n : p 1 (x) = γ 1 , . . . , p d (x) = γ d }.
These varieties will play a crucial role for the proof of Theorem 10; the following lemma illustrates the importance of these sets.

Lemma 11. Reusing the notations introduced above, consider a

S n -invariant polynomial f in R[x 1 , . . . , x n ] of degree d. Then f is constant over N γ .
Proof. Since f is S n -invariant, one can write it as the composition q(p 1 , . . . , p n ) where q is a polynomial in R[u 1 , . . . , u n ] (u 1 , . . . , u n are new variables) and the p i 's are Newton polynomials as above. Since deg(f ) = d and deg(p i ) = i, one also deduces that deg(q, u j ) = 0 for d + 1 ≤ j ≤ n. This implies that q lies in R[u 1 , . . . , u d ] and our claim follows immediately from the definition of N γ .

Before going further, we first examine the possible roots of the polynomials g j in an S n -equivariant system on the variety N γ .

Lemma 12. Let d ≤ n, γ ∈ R d . Consider (h 1 , . . . , h n ) a sequence of polynomials of degree at most d in R[x 1 , . . . , x n ] which are S n -equivariant and ξ = (ξ 1 , . . . , ξ n ) ∈ N γ . Then, there exist {α 1 , . . . , α t } ∈ R t with t ≤ d -1 such that h i (ξ) = 0 if and only if ξ i ∈ {α 1 , . . . , α t }.
Proof. By Corollary 9, there exist symmetric polynomials s i of degree at most d such that h i := d j=1 s j • ∂pj ∂xi , with deg(s j ) ≤ d for all i ∈ {1, . . . , n}. Since for 1 ≤ j ≤ d, deg(s j ) ≤ d and s j is symmetric, it follows that the value of s j at ξ is determined by the value of the first d Newton sums at ξ (Lemma 11). Let γ i = p i (ξ) for 1 ≤ i ≤ d and γ = (γ 1 , . . . , γ d ) ; besides, observe that, since ξ ∈ R n , we have γ ∈ R d . This implies that there exist (b

1 , . . . , b d ) ∈ R d such that for all ζ ∈ N γ ⊂ R n , s 1 (ζ) = b 1 , . . . , s d (ζ) = b d . For 1 ≤ i ≤ n, let us define the univariate polynomial hi = d j=1 b j x j-1 i
. As a consequence, the equality h i (ζ) = hi (ζ) holds for all ζ ∈ N γ . Now, consider the univariate polynomial δ(U ) := d j=1 b j U j-1 and let {α 1 , . . . , α t } be its roots in R. Since δ has degree ≤ d -1, we have t ≤ d -1. Observe that for every point ξ ∈ N γ ⊂ R n , h i (ξ) = 0 iff hi (ξ) = 0 and that hi (ξ) = δ(ξ i ) where ξ i is the i-th coordinate of ξ. In other words, h i (ξ) = 0 iff ξ i ∈ {α 1 , . . . , α t-1 }.

Proof of Theorem 10. Further S denotes S(F, G). Note that it suffices to show that if S = ∅ then there exists a point in S ∩ A 2d-1 . So we assume that S = ∅ and pick y ∈ S. We set p 1 (y) = γ 1 , . . . , p d (y) = γ d and we consider the corresponding real variety N γ as defined above. We now take the intersection S ′ := S ∩ N γ . Notice that d ≥ 2 (by assumption) and hence N γ is contained in a sphere. Thus, it follows that S ′ is closed and bounded. Further, we slightly abuse notation by using p d+1 to denote the map x → p d+1 (x) and its restrictions to subsets of R n . Moreover, since S ′ is closed and bounded, we deduce that p d+1 (S ′ ) is closed and bounded too (see [START_REF] Bochnak | Real algebraic geometry[END_REF]Theorem 2.5.8]). Hence, we deduce that there exists ξ = (ξ 1 , . . . , ξ n ) ∈ S ′ with the property that p d+1 (ξ) is maximal among all points in S ′ . We claim that ξ ∈ A 2d-1 . Let {i 1 , . . . , i ℓ } be the set of indices such that g i (ξ) = 0 if and only if i ∈ {i 1 , . . . , i ℓ }. By Lemma 12 applied to G = (g 1 , . . . , g n ), we deduce that there exists α = (α 1 , . . . , α t ) ∈ R t with t ≤ d -1 such that for all i ∈ {i 1 , . . . , i ℓ }, we have ξ i ∈ {α 1 , . . . , α t }. Up to re-indexing the variables we can assume that {i 1 , . . . , i ℓ } = {nℓ + 1, . . . , n}. For i ∈ {nℓ + 1, . . . , n}, we denote by κ(i) the integer such that ξ i = α κ(i) . This leads us to consider the intersection of S ′ with the affine linear space H of R n defined by

x n-ℓ+1 -α κ(n-ℓ+1) = • • • = x n -α κ(n) = 0. We denote by S ′
α the intersection of S ′ with the aforementioned hyperplanes. Recall that ξ lies in S ′ α and chosen to maximize p d+1 on S ′ . Then, ξ also maximizes the restriction of p d+1 to S ′ α . Further, by construction, we have that g i (ξ) > 0 for all i ∈ {1, . . . , n -ℓ}. This shows that there exists a ball B centered at ξ, of radius small enough such that the following holds: (i) for i ∈ {1, . . . , n -ℓ}, g i does not vanish in B;

(ii) the intersection of B with the real algebraic set defined by

f 1 = • • • = f k = g n-ℓ+1 = • • • = g n = 0 coincides with S ′ α ∩ B.
Remark now that the real algebraic set defined by f 1 = • • • = f k = 0 contains N γ . Also, applying Lemma 12 to G, one deduces that the real algebraic set defined by g n-ℓ+1 = • • • = g n = 0 coincides with the affine linear space H. We conclude that S ′ α ∩ B contains N γ ∩ H. Besides, observe that ξ lies in N γ ∩ H and recall again that it maximizes the restriction of p d+1 to S ′ α . We deduce that ξ maximizes the restriction of p d+1 to N γ ∩ H. Now, two situations may occur. Either, at ξ, the truncated Jacobian matrix associated to (p 1 , . . . , p d ) obtained by considering the partial derivatives w.r.t. (x 1 , . . . , x n-ℓ ) is full rank or it is not. In both cases, since ξ = (ξ 1 , . . . , ξ n ) maximizes the restriction of p d+1 to N γ ∩H, one deduces that there exists (λ 0 , . . . ,

λ d ) ∈ R d+1 -{0} such that 0 = λ 0 ∂p d+1 ∂xj (ξ) -d i=1 λ i ∂pi ∂xj (ξ) for 1 ≤ j ≤ n -ℓ. This is rewritten as 0 = (d + 1)λ 0 ξ d j - d i=1 (i)λ i ξ i-1 j for 1 ≤ j ≤ n -ℓ.
The above algebraic relation entails that for 1 ≤ j ≤ nℓ, ξ j is a root of the non-zero univariate polynomial η(U ) := d i=0 λ i U i of degree at most d (recall that (λ 0 , . . . , λ d ) = (0, . . . , 0)). Therefore, at most d of the first nℓ coordinates of ξ can be distinct. Further, by construction, we have that there are at most d -1 possibilities for the last ℓ coordinates of ξ. Therefore, ξ ∈ A 2d-1 as claimed.

Remark 1. Observe that when F is S n -equivariant (instead of having all of its entries S n -invariant), the conclusions of Theorem 10 still hold. To see that it suffices to replace F be the sum of the squares of its entries. Also when the entries of F are subject to inequality constraints (instead of equality constraints), the conclusions of Theorem 10 still hold as one can replace inequalities by equations as in [START_REF] Basu | Computing roadmaps of semi-algebraic sets (extended abstract)[END_REF]Chap. 13].

Algorithms and complexity 4.1 Deciding emptiness

Further, we let Q be a real field, R be a real closed field containing Q and C be an algebraic closure of R. We consider F = (f 1 , . . . , f k ) and G = (g 1 , . . . , g n ) be polynomial sequences in Q[x 1 , . . . , x n ]. As above, the semi-algebraic set of R n defined by

f 1 = • • • = f k = 0, g 1 ≥ 0, . . . , g n ≥ 0
is denoted by S(F, G). We start with a first complexity statement.

Theorem 13. Let F and G be as above and d be an integer bounding the degrees of the polynomials in F and G. Assume that the polynomials in F are S n -invariant and that the map x → (g 1 (x), . . . , g n (x)) is S n -equivariant and that d ≤ n/2.

There exists an algorithm which, on input (F, G) decides whether S(F, G) is empty using at most n O(d) arithmetic operations in Q.

Proof. By Theorem 10, S(F, G) is non-empty if and only if there exists x ∈ S(F, G) with at most 2d -1 distinct coordinates. For x = (x 1 , . . . , x n ) ∈ R n , we denote by v(x) = {v 1 , . . . , v p } (with p ≤ n depending on x) the set of values taken by the coordinates of x and by P(x) = (P 1 , . . . , P p ) the partition given by the sets

P j = {x i | x i = v j }.
Up to renumbering, one assumes that the P i 's are given by ascending cardinality. Hence, set r = 2d -1 and consider a partition γ = [γ 1 , . . . , γ r ] of n of size r, i.e. γ 1 + • • • + γ r = n with γ i ∈ N -{0} for 1 ≤ i ≤ r and γ i-1 ≤ γ i (by convention, γ 0 = 0). We say that a partition P 1 , . . . , P p of (x 1 , . . . , x n ) is compatible with γ if p ≤ r and there exists an increasing sequence of integers s i such that

|P i | = γ si-1 + • • • + γ si .
We prove below that, given γ, one can decide in time n O(r) the existence of a real point x in S(F, G) such that P(x) is compatible with γ. Bounding further the number of partitions of size r by n r will establish the announced result (recall that r = 2d -1). Assume that such a point x = (x 1 , . . . , x n ) exists and consider P(x) = (P 1 , . . . , P p ). For σ ∈ S n we denote by σ(P i ) the set {x σ(j) | x j ∈ P i }. Let σ be a permutation of S n such that σ(P i ) = {x si-1 , . . . , x si } and consider σ(x) = (x σ(1) , . . . , x σ(n) ). Now, remark that since all entries of F are invariant by the action of S n and that G is S n -equivariant, σ(x) ∈ S(F, G). This leads us to associate to γ the partition Γ = (Γ 1 , . . . , Γ r ) of (x 1 , . . . , x n ) defined by Γ i = {x γi-1+1 , . . . , x γi } with γ 0 = 0 by convention. Now, let a 1 , . . . , a r be new indeterminates. Next, we perform the substitution

x γi-1+1 = • • • = x γi = a i for 1 ≤ i ≤ r in F and G.
In the end, one obtains polynomial families in R[a 1 , . . . , a r ]. The above discussion shows that we only need to decide the existence of real points to the new system one obtains this way. Using [10, ], this is done in time n O(r) . To finish the proof, it remains to count the number of partitions γ = (γ 1 , . . . , γ r ) of n. The number p(n, r) of partitions of n of size r satisfies the recurrence relation p(n, r) = p(n -1, r) + p(nr, r) with p(n, r) = 0 if n < r and p(n, n) = p(n, 1) = 1. A simple induction establishes the inequality p(n, r) ≤ n r which finishes the proof.

The next result establishes a more precise complexity statement: we will actually identify the constant which is in the big-Oh exponent, when the input system satisfies some properties that we will prove to be generic. Further, given a polynomial family H in R[x 1 , . . . , x n ], V (H) ⊂ C n denotes the set of common solutions to H in C n . Hence, let as above F = (f 1 , . . . , f k ) and G = (g 1 , . . . , g n ) in R[x 1 , . . . , x n ]. Further, for I = {i 1 , . . . , i ℓ } ⊂ {1, . . . , n}, we denote by H I the set F ∪ {g i1 , . . . , g i ℓ }. We say that (F, G) satisfies the assumption R when

• the jacobian matrix of F has maximal rank at all points in V (F );

• for all I ⊂ {1, . . . , n}, the jacobian matrix of H I has maximal rank at any point of V (H I ). Now, let r in {1, . . . , n}; we say that (F, G) satisfies assumption A r if for any partition γ = (γ 1 , . . . , γ r ) of n, when performing the substitution

x γi-1+1 = • • • = x γi = a i (1 ≤ i ≤ r)
where a 1 , . . . , a r are new variables in (F, G), the obtained couple of polynomial sequences (F γ , G γ ) satisfies R.

Further, the entries of F γ (resp. G γ ) are denoted by f 1,γ , . . . , f k,γ (resp. g 1,γ , . . . , g n,γ ). We can now state our complexity result.

Theorem 14. Let F and G be as above in R[x 1 , . . . , x n ], d be the maximum of the polynomials in F and G and E be the complexity of evaluating (F, G). Assume that for 1 ≤ i ≤ n, f i is S n invariant, that g is S n -equivariant and that deg(g j ) ≥ 2 for 1 ≤ j ≤ n and that (F, G) satisfies assumption A r .

There exists an algorithm which on input (F, G) satisfying A, decides whether S(F, G) is empty using

O ˜ n 2d (2d) 4d+1 (pE + d 2 ) arithmetic operations in Q.
Proof. Further we set r = 2d-1. By Theorem 10, S(F, G) is not empty if and only if S(F, G) contains a point of R n with at most r distinct coordinates. Besides, using the invariance of (F, G) under the action of S n as in the proof of Theorem 13, deciding if S(F, G) contains a real point with at most r distinct coordinates can be done by deciding if at least one of the semi-algebraic sets S γ = S(F γ , G γ ) is non-empty when γ ranges of the set of partitions of n of length r. We already established that the number of such partitions is upper bounded by n r at the end of the proof of Theorem 13.

Hence, let us focus on the complexity of deciding if S γ is empty. We need to introduce some notation. For I = {i 1 , . . . , i ℓ } ⊂ {1, . . . , n}, we denote by V γ,I ⊂ C n the algebraic set defined by

f 1,γ = • • • = f k,γ = g i1,γ = • • • = g i ℓ ,γ = 0. Further, we denote by H = (h 1 , . . . , h m ) ⊂ R[a 1 , .
. . , a r ] these polynomials defining V γ,I . Further, we use linear changes of variables. Hence for A ∈ GL n (R), we denote by h A i the polynomial obtained by performing the change of variables a → A -1 a in h i and by H A the sequence (h A 1 , . . . , h A m ). Using [START_REF] Basu | Algorithms in real algebraic geometry[END_REF], we deduce that, to decide the emptiness of S γ , it suffices to compute sample points in each connected component of the real algebraic set V γ,I ∩ R n for all {i 1 , . . . , i ℓ } ⊂ {1, . . . , n} and filter out those points which lie in S γ . Since (F, G) satisfies A, V γ,I is either empty or smooth and equidimensional of co-dimension k + ℓ and the above polynomial system generates a radical ideal (by the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19]). We conclude that we only need to consider subsets of cardinality ℓ ≤ rk. We are in position to apply the results in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. Actually, we use a variant of the algorithm in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF], combining the geometric approach described therein with [START_REF] El Din | Bit complexity for multi-homogeneous polynomial system solving application to polynomial minimization[END_REF]. Let π i be the canonical projection (a 1 , . . . , a r ) → (a 1 , . . . , a i ) and, given an equidimensional and smooth algebraic set V , let W (π i , V ) be the critical locus of the restriction of π i to V . We will also consider the projections ϕ i : (a 1 , . . . , a r ) → a i . By [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Theorem 2], in order to decide the emptiness of V A γ,I ∩R n , it suffices to perform a generic linear change of variables A ∈ GL r (R) and next compute rational parametrizations of all sets π

-1 i-1 (0) ∩ W (π i , V A γ,I ) for 1 ≤ i ≤ dim(V A γ,I ) + 1. Technical but immediate computations show that π -1 i-1 (0) ∩ W (π i , V A γ,I ) = W (ϕ i , Z i ) where Z i = π -1 i-1 (0) ∩ V A γ,I . Observe that in order to compute Z i = π -1 i-1 (0) ∩ V A γ,I it suffices to solve the so-called Lagrange system h A 1,i-1 = • • • = h A m,i-1 = 0, [ℓ 1 , . . . , ℓ m ]jac(H A i-1 , i) = 0 where h A j,i-1 (resp. H A i-1 ) is the polynomial obtained by setting a 1 = • • • = a i-1 = 0 in h A j (resp. H A ),

and jac(H

A i-1 , 1)
is the submatrix obtained by removing the first column of the Jacobian matrix associated with H A i-1 . By [55, Proposition B.1], after performing a generic linear change of variables, assumptions needed to apply [START_REF] El Din | Bit complexity for multi-homogeneous polynomial system solving application to polynomial minimization[END_REF]Theorem 16]. This latter result shows that, letting E H be the complexity of evaluating H and r i = r -(i -1), one can solve the above Lagrange system using

O ˜ r 3 i ri m d 2ri+1 (pE H + r i d + r 2 i ) arithmetic operations in Q. Hence, since dim(V γ,I ) = r -m the total cost of computing sample points in each connected component of V γ,I ∩ R n uses O ˜ r 4 2 2r d 2r+1 (pE H + rd + r 2 )
arithmetic operations in Q. Finally, observe that E H is bounded by the complexity of evaluating the input (F, G). Also, summing up this cost to take into account all possible subsets I (bounded by 2 r ) and the number of partitions γ (bounded by n r ) ends the proof.

It remains to establish the genericity of assumption A. To do that, we need to define the parameters'space in which the genericity statement will hold, i.e. the space of the coefficients of (F, G) where all entries of F are S n -invariant and G is S n -equivariant (recall also that all entries of (F, G) have degree bounded by d). Let R be the Reynolds operator which sends f ∈ C[x 1 , . . . , x n ] to R(f ) = 1 n! σ∈Sn σ(f ). Let now M be the set of all monomials of degree ≤ d in C[x 1 , . . . , x n ] and M R = R(M), c = |M R | and T i = (t i,1 , . . . , t i,c ) be new indeterminates for 1 ≤ i ≤ k. we define now f i = mj ∈M R t i,j m j and f = (f 1 , . . . , f k ) in C(T 1 , . . . , T k )[x 1 , . . . , x n ]. Observe that any sequence F such that all entries have degree bounded by d and are S n -invariant are obtained by specializing the indeterminates (T 1 , . . . , T k ). Finally, we consider an additional sequence of indeterminates T k+1 = (t k+1,1 , . . . , t k+1,c ) a polynomial g = mj∈M R t k+1,j m j . Again, any sequence G which is S n -equivariant is obtained as the gradient vector of a polynomial obtained by instantiating T k+1 in g. Then, we set N = c(k + 1) and the parameters'space we consider is C N , i.e. the one endowed by the indeterminates (T 1 , . . . , T k+1 ). Proof. Let I = {i 1 , . . . , i ℓ } ⊂ {1, . . . , n}, r = 2d -1, γ = (γ 1 , . . . , γ r ) and E γ ⊂ C n be the linear subspace defined by x γi-1+1 = • • • = x γi (for 1 ≤ i ≤ r). We denote by Γ this set of linear equations which define Ext γ . We consider the map Φ I,γ :

z = (x, t) ∈ E γ × C N → f 1 (z), . . . , f k (z), ∂g ∂xi 1
(z), . . . , ∂g ∂xi ℓ (z) . Assume for the moment that 0 is a regular value of Φ I . Then, the algebraic version of Thom's weak transversality theorem (see e.g. [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Proposition B.3]) states that there exists a non-empty Zariski open set O I such that for any t ∈ O I , 0 is a regular value for the specialized map x → Φ I (x, t). In other words, at any x ∈ C N in the zero-set of the union of Γ with f 1 (., t), . . . , f k (., t), ∂g ∂xi 1 (., t), . . . , ∂g ∂xi ℓ (., t), the Jacobian matrix of that polynomial family is full rank. By the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19], we deduce that this polynomial family satisfies R. It remains to prove that for I = {i 1 , . . . , i ℓ } ⊂ {1, . . . , n}, 0 is a regular value of the map Φ I,γ , i.e. the Jacobian matrix associated to Φ I,γ is invertible at any point of Φ -1 I,γ (0). To do that, we prove that the Jacobian matrix associated to Γ and f 1 , . . . , f k , ∂g ∂xi 1 , . . . , ∂g ∂xi ℓ is full rank at any point of Φ -1 I,γ (0). We extract a full rank submatrix of that Jacobian matrix as follows:

• since Γ is a set of independent linear equations, one extracts a full rank square submatrix J with entries in C whose columns correspond to partial derivatives w.r.t. variables in x 1 , . . . , x n ; • we select the columns corresponding to the partial derivatives w.r.t. indeterminates encoding the constant terms in f i ; this yields a diagonal submatrix ∆ with 1's on the diagonal; • we select the columns corresponding to the partial derivatives w.r.t. the indeterminate multiplying (x 1 + • • • + x n ) in g; this yields a diagonal submatrix ∆ ′ , with 1's on the diagonal.

In the end, the submatrix we have extracted is block-diagonal and these blocks on the diagonal are J, ∆ and ∆ ′ . This ends the proof.

One-block quantifier elimination

We now study the situation where

F = (f 1 , . . . , f k ) and G = (g 1 , . . . , g n ) are polynomials in Q[x 1 , . . . , x n , y 1 , . . . , y t ] such that (i) the action of S n on (x 1 , . . . , x n ) leaves invariant f i ; (ii) the map x = (x 1 , . . . , x n ) → (g 1 (x, .), . . . , g n (x, .)) is S n equivariant.
We consider the problem of computing a semi-algebraic description of the projection on the (y 1 , . . . , y t )-space of the set S(F, G) ⊂ R n × R t defined by f 1 = • • • = f k = 0, g 1 ≥ 0, . . . , g n ≥ 0. This is equivalent to solve the one-block quantifier elimination problem:

Φ : ∃x ∈ R n f 1 = • • • = f k = 0, g 1 ≥ 0, . . . , g n ≥ 0, (4.1)
hence computing a quantifier-free formula which is equivalent to the quantified formula Φ. A geometric interpretation is that one aims at computing a semi-algebraic description of Π(S(F, G)) where Π is the projection (x, y) ∈ R n × R t → y.

Theorem 16. Let F , G and Φ be as above, d be the maximum degree in the variables in (x 1 , . . . , x n ) of the entries of F and G and assume that d ≤ n 2 . Then, there exists a quantifier-free formula Ψ(Y ) = ∪ K k=1 Ψ k (Y ) which is equivalent to Φ, and such that K ≤ n O(d) and:

Ψ k (Y ) = ∨ ℓ k i=1 ∧ ℓ i,k j=1 (∨ ℓ i,j,k u=1 sign(ϕ i,j,u,k ) = σ i,j,h,k ) with σ i,j,h,k ∈ {0, 1, -1}, ℓ k ≤ (n + k) d+1 n O(dt) ℓ i,k ≤ (n + k) d+1 n O(d) , ℓ i,j,k ≤ n O(d)
and the degrees of the polynomials ϕ i,j,u are bounded by n d . Moreover, there exists an algorithm which computes Ψ using at most (k + n) dt n O(dt) arithmetic operations in Q.

Proof. The proof is similar to the one of Theorem 13. We reduce the considered one-block quantifier elimination problem to solving finitely many one-block quantifier elimination problems. Set r = 2d -1 and let Γ(n, r) be the set of partitions γ = (γ 1 , . . . , γ r ) of n of size r (γ 0 = 0 by convention).

As in the proof of Theorem 13, we associate to γ the substitution

x γi-1+1 = • • • = x γi = a i for 1 ≤ i ≤ r,
where a 1 , . . . , a r are new variables. We denote by Φ γ the formula obtained after performing this substitution in Φ and by S γ (F, G) the semi-algebraic set in R r × R t defined by the system obtained after applying the same substitution. Assume, for the moment, the following equality:

Π(S(F, G)) = ∪ γ∈Γ(n,r) Π(S γ (F, G)). (4.2)
Then, performing quantifier elimination on formula Φ is equivalent to performing quantifier elimination on each formula Φ γ -which yields a quantifier-free formula Ψ γ defining Π(S γ (F, G)) -and returning γ⊂Γ(n,r) Ψ γ . Using [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Theorem 14.16], one deduces that performing quantifier elimination on Φ γ is done using (k+n) dt n O(dt) arithmetic operations in Q and it yields a formula Ψ γ (Y ) = ∨ ℓ i=1 ∧ ℓi j=1 (∨ ℓi,j u=1 sign(ϕ i,j,u ) = σ i,j,h ) such that ℓ ≤ (n + k) d+1 n O(dt) , ℓ i ≤ (n + k) d+1 n O(d) and ℓ i,j ≤ n O(d) . Now, recall that Γ(n, r) has cardinality bounded by n O(d) (this bounds the integer K in the statement of the Theorem). Hence, runtime and degree bounds on the output formula are established. Now, we prove that (4.2) holds which will end the proof. Let y ∈ Π(S(F, G)) and S y ⊂ R n be the projection of S(F, G)∩Π -1 (y) on the (x 1 , . . . , x n )-space. Observe that S y is defined by the polynomial system obtained by instantiating variables (y 1 , . . . , y t ) to the coordinates of y in F and G ; we denote the obtained polynomial sequences by F y and G y . Observe that all entries of F y are S n -invariant, the sequence G y defines an equivariant map and all entries of F y and G y have degree ≤ n 2 by assumption. Hence, we can apply Theorem 10. It establishes that the semi-algebraic set S y is empty if and only if it contains a point x with at most 2d -1 coordinates. Now, observe, as in the proof of Theorem 13, thanks to the invariance of (F γ , G γ ) that since under the action of S n , there exists a partition γ = (γ 1 , . . . , γ r ) in Γ(n, r) such that S y has a non-empty intersection with the hyperplanes defined by x γi-1+1 = • • • = x γi for 1 ≤ i ≤ r. In other words, there exists γ ∈ Γ(n, r) such that y ∈ Π(S γ (F, G)). We deduce that Π(S(F, G)) ⊂ ∪ γ∈Γ(n,r) Π(S γ (F, G)). The reverse inclusion is immediate once we observe that ∪ γ∈Γ(n,r) S γ (F, G) ⊂ S(F, G).

Experimental results

Our experiments make use of the following software • RAGlib. [START_REF] Din | Raglib (real algebraic geometry library[END_REF]. This is a Maple library, based on the FGb library by J.-C. Faugère. It implements algorithms based on the critical point method running in time singly exponential in n. • Mathematica-CAD [START_REF] Strzeboński | Cylindrical algebraic decomposition using validated numerics[END_REF], RealTriangularize [START_REF] Chen | Computing the real solutions of polynomial systems with the regularchains library in maple[END_REF] which are packages computing Cylindrical Algebraic Decompositions (CAD) adapted to polynomial sequences.

Finally, let us consider the following examples extracted from [START_REF] Djukić | The IMO compedium. A collection of problems suggested at the International Mathematical Olympiads[END_REF]:

• the problem SWE [26, p. 98] consists in proving that for 0 < a < b, the semi-algebraic set defined by m 2 > m 2 The first (resp. second) table provides timings for SWE (resp. ROM). As observed previously, implementations based on the critical point methods scale way better than those based on CAD. Also our approach combined with critical point methods allows us to tackle problems which are out of reach of the state-of-theart.

Theorem 10 .

 10 Let F = (f 1 , . . . , f k ) and G = (g 1 , . . . , g n ) be sequences of polynomials in R[x 1 , . . . , x n ]. Let d be the maximum of deg(f i ) and deg(g j ) for 1

Theorem 15 .

 15 There exists a non-empty Zariski open set O ⊂ C N such that for (F, G) in O, (F, G) satisfies assumption A.

  Finally, we define O as the intersection of the finitely many non-empty Zariski open subsets O I ⊂ C N . Hence, O is a non-empty Zariski open set of C N and for any (F, G) ∈ O, (F, G) satisfies A.

1 (a+b) 2 4ab, 2 • 4 >

 1224 (bx 1 )(x 1a) ≥ 0, . . . , (bx n )(x na) ≥ 0 is empty with the problem 3.40.1 (referred to as ROM) in[26, p. 302] leads to decide the existence of real roots to the semi-algebraic system: 0, x 1 > 0, . . . , xn > 0

  Cordian Riener is supported by the Tromsø Research Foundation grant 17 matte CR. Mohab Safey El Din is supported by the ANR grant ANR-17-CE40-0009 Galop and the PGMO grant Gamma.

	n	3	4	5	6	7	8	9
	RS	0.12	0.14	0.3	0.5	0.6	0.74	1.2
	RAG	0.2	0.3	0.5	1.6	9.8	131	1978
	M	0.2	14.7	-	-	-	-	-
	n	3	4	5	6	7	8	9
	RS	0.25	0.8	4.2	95	6874	6902	14023
	RAG	0.3	1	4.5	97	6664	-	-
	M	0.04	0.5	1246	-	-	-	-

We have considered the following test-suites:

• S1. We take the gradient of randomly chosen dense symmetric polynomials for G, letting F be the empty sequence; the coefficients of these polynomials are chosen between -2 16 and 2 16 using the random tool generator of Maple. • S2. We take random dense systems of symmetric polynomials and equivariant families in

To solve these polynomial systems, we will use the following implementations of critical point method-based algorithms and CAD:

• RAG refers to the Real Algebraic Geometry library RAGlib; • M refers to the CAD in Mathematica;

• T refers to the CAD package in Maple.

The direct use of these polynomials will be compared with algorithms on which Theorems 13 and 14 rely. These consist in using critical point based algorithms to decide if the input system has a real solution with at most 2d -1 distinct coordinates (where d bounds the degree of the inputs). Also we can substitute the use of those algorithms by ones that are based on CAD. This leads us to consider in our comparisons the following:

• RS: consists in using RAGlib; this is an implementation of the algorithm on which Theorems 13 and 14 rely. • RS-T: consists in using the CAD Maple package to look at solutions with at most 2d -1 distinct coordinates.

The computations are performed on an Intel(R) Xeon(R) CPU E3-1505M v6 @ 3.00GHz with 32 Gb of RAM. Timings are given in seconds. The symbol '-' means that no result was obtained after 2 days of computation or because of a lack of memory. Tables 1 and2 provide the results obtained for the test-suites S1 and S2. One can see that the use of Theorem 10 allows us to tackle examples that are out of reach of other implementations. We also observe that when 2d -1 becomes larger than 4 or 5 implementations based on CAD cannot tackle most of the examples considered here while the critical point method based implementation RAGlib scales far much better.


Raymond Chan

Kam-Pui Chow

Threat analysis of an elevator control system

Keywords: Programmable logic controllers, elevator control, threats, mitigation 1

Introduction

Industrial control systems are used across the critical infrastructure to manage physical processes. Industrial control systems include supervisory control and data acquisition (SCADA) systems and distributed control systems (DCSs), both of which incorporate component devices such as programmable logic controllers (PLCs). Programmable logic controllers are connected to human-machine interfaces (HMIs) to enable command and control by human operators and to engineering/development workstations for configuration, programming and diagnostics. Programmable logic controllers commonly execute ladder logic programs to perform their monitoring and control activities.

Traditionally, industrial control systems operated using proprietary protocols in closed (air-gapped) networks. However, many industrial control net-works are now connected to external networks -even the Internet -to support remote operations, configuration and diagnostics. This exposes industrial control systems and the critical assets they manage to external attacks in addition to attacks by malicious insiders.

Several issues impact the security of industrial control systems. One is that engineers and operators are more concerned about availability than security. Another is the lack of a security mindset. Yet another is the fact that the scale, complexity and diversity of industrial control systems render the implementation of security mechanisms extremely cost-prohibitive. Moreover, adding extra layers of protection can significantly affect the performance and reliability of industrial control systems -asset owners and operators are reluctant to implement security mechanisms that can affect command and control.

Stuxnet has demonstrated that a sophisticated adversary can gain access to an extremely well-protected industrial control network. Once inside the network, the adversary can leverage the fact that programmable logic controllers, because they have limited memory and processing power, are unable to implement security controls such as encryption and intrusion detection. This makes it possible to extract and reprogram the ladder logic to change the behavior of the control system.

This research focuses on programmable logic controllers, arguably the most vulnerable components of industrial control systems. It analyzes the threats to the internal environment of an elevator control system that engages a Siemens programmable logic controller and presents a proof-of-concept program that demonstrates the feasibility of attacks. Also, it describes several approaches for mitigating the threats to the elevator control system.

Related Work

Considerable research has focused on industrial control system security (see, e.g., [START_REF] Krotofil | Industrial control systems security: What is happening[END_REF]) and managing the risks (see, e.g., [START_REF] Spyridopoulos | Incident analysis and digital forensics in SCADA and industrial control systems[END_REF]). Hadziosmanovic et al. [START_REF] Hadziosmanovic | Challenges and opportunities in securing industrial control systems[END_REF] discuss the challenges involved in protecting industrial control system hosts and networks. Several high-level solutions have been developed for protecting industrial control systems (see, e.g., [START_REF] Miyachi | Current issues and challenges on cyber security for industrial automation and control systems[END_REF][START_REF] Piggin | Emerging good practice for cyber security of industrial control systems and SCADA[END_REF]). Wei and Ji [START_REF] Wei | Resilient industrial control system (RICS): Concepts, formulation, metrics and insights[END_REF] have proposed a three-layer architecture for enhancing the security and reliability of industrial control systems. Cohen [START_REF] Cohen | A reference architecture approach to ICS security[END_REF] has specified a reference architecture and guidelines for securing industrial control networks. Jie and Li [START_REF] Jie | Industrial control system security[END_REF] have analyzed industrial control system security risks and have proposed strategies for protecting control devices. Ghena et al. [START_REF] Ghena | Green lights forever: Analyzing the security of traffic infrastructure[END_REF] have leveraged wireless access to maliciously control traffic lights. These research efforts discuss security problems and solutions for industrial control systems, but ignore threats to the internal networks of industrial control systems.

Several researchers have focused on discovering vulnerabilities in industrial control networks. Beresford [START_REF] Beresford | Exploiting Siemens Simatic S7 PLCs[END_REF] has analyzed the Siemens S7 protocol and has developed exploits that target Siemens programmable logic controllers. In particular, Beresford demonstrated that it is possible to bypass the authentication protocol and perform memory-read, write-logic and other attacks. Timorin [START_REF] Timorin | SCADA deep inside: Protocols and security mechanisms[END_REF] has demonstrated how to capture S7 challenge-response messages and perform replay attacks. Also, Timorin has analyzed the Siemens Total Integrated Automation (TIA) Portal project file, and has shown how to extract the SHAprotected password and change user permissions in the file. Korkmaz et al. [START_REF] Korkmaz | ICS security testbed with delay attack case study[END_REF] have discovered a time delay attack on a control system that could result in the failure of an entire power generation facility. Abe et al. [START_REF] Abe | Security threats of Internet-reachable ICSs[END_REF] have identified several cyber attacks on Internet-connected control systems; these attacks leverage malware that sends STOP and RESET commands to programmable logic controllers, negatively impacting the industrial control system and the underlying process.

Cardenas et al. [START_REF] Cardenas | Rethinking security properties, threat models and the design space in sensor networks: A case study in SCADA systems[END_REF] have specified a threat model that covers outsider attacks, key-compromise attacks and insider attacks on SCADA systems. Hadziosmanovic et al. [START_REF] Hadziosmanovic | Challenges and opportunities in securing industrial control systems[END_REF] have classified industrial control system threats into systemrelated threats and process-related threats. McLaughlin and Zonouz [START_REF] Mclaughlin | Controller-aware false data injection against programmable logic controllers[END_REF] have introduced a threat model that covers the use of any industrial control system component to upload malicious code to a programmable logic controller. Malchow et al. [START_REF] Malchow | PLC Guard: A practical defense against attacks on cyber-physical systems[END_REF] have proposed a threat model that covers a scenario where an adversary can control an engineering workstation using malware and inject malicious code into a programmable logic controller.

In general, most industrial control system security approaches focus on redesigning the entire architecture or incorporating security mechanisms throughout the architecture. In the case of operational industrial control systems, there are certain latent security problems, especially pertaining to the internal environment, which often has fewer security mechanisms than external networks -examples are the development zone and human-machine control zone. As a result, this research seeks to identify potential vulnerabilities that enable practical and reproducible attacks on the internal networks of industrial control systems. An elevator control system is used as a case study because it is small and ubiquitous, but still a representative, real-world industrial control system. Additionally, the elevator system has several sensors and safety protection mechanisms that can be targeted to cause harm.

Threat Model

This research assumes that an adversary can gain access to the internal network of an industrial control system by various means and is able to launch attacks. The attacks are assumed to target: (i) confidentiality; (ii) integrity; or (iii) availability. The proposed threat model focuses on Siemens programmable logic controllers. The model considers the attack capabilities of an adversary upon gaining access to an industrial control network; these capabilities are in addition to implanting malware on a programmable logic controller. In general, it is difficult for an adversary to enter an industrial control network via a phishing email, external USB thumb drive or even as an insider.

Confidentiality Threats

Most industrial control systems do not use encryption and authentication. As a result, an adversary who has access to a network and captures communications data can perform the following attacks:

Programmable Logic Controller Discovery Attack: An adversary can discover all the programmable logic controllers in an internal industrial control network by connecting to the network and capturing network packets using a tool such as Wireshark. Figure 1 illustrates the network packet capture process in the case of a Siemens programmable logic controller that uses the Link Layer Discovery Protocol (LLDP) to broadcast its presence. Important information such as the MAC address, model number, CPU information, hardware information and firmware information are transferred in plaintext. An adversary who captures the internal network traffic can easily obtain detailed information about the programmable logic controllers that could be used to plan specific attacks.

False Command or Signal Injection Attack: Most industrial control system designs assume that all the devices operate in a trusted and closed network. No encryption and authentication mechanisms are implemented between human-machine interfaces and programmable logic controllers. Moreover, many human-machine interfaces and programmable logic controllers are connected to external networks, including the Internet. An adversary who accesses the network interface could inject various control commands. For example, injecting a STOP or RESET command would move a programmable logic controller to the STOP mode and the controller would not operate until it receives a START command. Many programmable logic controllers in production systems have been operational for several years and often have outdated firmware. McLaughlin and Zonouz [START_REF] Mclaughlin | Controller-aware false data injection against programmable logic controllers[END_REF] have developed the CaFDI tool that sends false data to programmable logic controllers. Abe et al. [START_REF] Abe | Security threats of Internet-reachable ICSs[END_REF] have demonstrated that sending a STOP or RESET command is adequate to disrupt most programmable logic controllers. An adversary could also send a fake sensor input signal in order to alter an output, potentially causing the entire industrial control system to crash [START_REF] Mo | False data injection attacks in control systems[END_REF].

A personal computer installed with the Siemens Step 7 software can send a discovery command to flash the LED light of a Siemens PLC, leading the operator to believe that the programmable logic controller is malfunctioning. Figure 2 shows the command sent from a personal computer to manipulate the LED of a Siemens programmable logic controller.

Ladder Logic Program Leakage Attack:

A ladder logic program specifies how a programmable logic controller should process input signals and generate responses in the form of output signals. A Siemens programmable logic controller implements a control command that enables an engineer to download the ladder logic program from the controller. An adversary who has the requisite access can request the programmable logic controller to send its ladder logic program, enabling the adversary to access and reverse engineer the program.

Integrity Threats

As mentioned above, programmable logic controllers usually do not implement any authentication checks. An adversary who knows the IP address of a programmable logic controller could seize control of the device and transmit messages. The operator at the human-machine interface would be unable to determine that the messages do not come from an authorized entity.

The following attacks target the integrity of an industrial control system:

Response Injection Attack: Since it is not possible to determine whether or not a message is sent by an authorized programmable logic controller, an adversary can execute a man-in-the-middle attack and inject or alter a response message variable or sensor value sent by a programmable logic controller to display false information on a humanmachine interface. Any number of replay attacks are also possible.

Ladder Logic Modification Attack:

No authentication checks are performed when uploading a ladder logic program from a development workstation to a programmable logic controller. Thus, an adversary to can create a malicious ladder logic program and upload it to the programmable logic controller so that it replaces the original program. This is possible because no software attestation or protection mechanisms are implemented to verify that the new ladder logic program is authentic. If the new ladder logic program sends valid outputs to the human-machine interface, a behavior-based protection mechanism would be unable to detect the attack at the network level.

Availability Threats

Programmable logic controllers are devices with low processing power that are designed to operate in real time. It is possible to send malformed packets that delay or disrupt the responses of a programmable logic controller. An example attack on availability is: Denial-of-Service Attack: One type of denial-of-service attack involves the transmission of malicious commands or packets that delay the response or even crash a programmable logic controller. Another type of attack targets the human-machine interface by installing malware on programmable logic controllers. In this case, an adversary uploads malicious ladder logic programs to all the programmable logic controllers in the industrial control network. When certain attack criteria are satisfied (e.g., time or process conditions), the programmable logic controllers could be made to disrupt the human-machine interface by simultaneously sending it malicious packets.

4.

Elevator System Case Study

An elevator system testbed was used to validate the proposed threat model and demonstrate the feasibility of attacks.

Experimental Setup

Figure 3 presents the elevator system testbed used in the experiments. The control circuit of the model elevator system comprised a DC power supply, programmable logic controller, magnetic circuit breaker contactors, relays and variable frequency drives. The control circuit provided an interface for controlling high power devices (e.g., three-phase AC motor) via small control signals transmitted by the programmable logic controller. The KTP600 Control Panel served as the human-machine interface for an operator to obtain status data and control elevator operation. A personal computer installed with the Siemens TIA Portal and connected to the switch of the elevator system (i.e., internal network) was assumed to be exploited by the adversary to launch attacks.

The programmable logic controller was configured to control the model elevator. The model elevator system had two cars that operated over nine floors. Sensors were located on every floor for elevator car positioning. As in a typical modern passenger elevator, the model had two call buttons (car call and hall call) to choose a floor. Door controls were incorporated to close or reopen the doors. An object in the path of the moving doors was detected by sensors or were handled by manually activating a switch that reopened the doors. Otherwise, the elevator doors closed after a preset time.

A driving mechanism moved the elevator car up and down. The elevator control system coordinated the movements of the two elevator cars to provide optimal service by reducing passenger wait times.

In the experiments, the ladder logic program for elevator control was uploaded to the Siemens S7-1200 programmable logic controller (Firmware v4.0) using the Siemens TIA Portal v13. The Siemens S7-1200 programmable logic controller is one of the popular models available in the market and has been deployed in numerous infrastructure assets.

The experiments assumed that the adversary had installed malware in the personal computer connected to the elevator switch, which enabled him to discover, monitor and control the programmable logic controller in the elevator system. Specifically, the adversary could perform three actions: (i) discover the presence of the programmable logic controller in the network; (ii) query information about the programmable logic controller; and (iii) launch attacks to control and crash the programmable logic controller.

S7 Base Protocol and Configuration

The S7 base protocol is used by Siemens programmable logic controllers for communications. The protocol has been exploited by Beresford [START_REF] Beresford | Exploiting Siemens Simatic S7 PLCs[END_REF] and several third-party software tools are available to control Siemens programmable logic controllers. Starting with Firmware V4.0, Siemens updated the S7 protocol (S7 Plus) for the Siemens S7-1200/1500 programmable logic controller model to provide additional security features. However, this research discovered that the S7 base protocol can still be used to query and command a new programmable logic controller due to the design decision to maintain compatibility with older versions. In particular, the experiments used the S7 base protocol to retrieve information from the programmable logic controller and then change its behavior.

The S7 base protocol incorporates commands for querying and changing the digital inputs (PA) and digital outputs (PE) of the programmable logic controller. No configuration settings were available for protecting access to the PA and PE entries. In fact, this research discovered that the S7 base protocol could be used to communicate with the programmable logic controller without the authentication checks required by the new S7 protocol implemented in the controller. Indeed, the experiments confirmed that the new S7 protocol does not provide any protection to the digital inputs or outputs when the base protocol is used. Based on these findings, a proof-of-concept ladder logic program was developed to send S7 base protocol commands to change the behavior of the elevator system. Figure 4 shows the ladder logic program that manages the elevator system. Figure 5 shows the attack entry point to the elevator system.

PLC Discovery Attack

As discussed in the section on confidentiality threats, an adversary has to first locate the personal computer with Siemens Step 7 installed and the Siemens programmable logic controller in the internal industrial control network. Information about these devices may be collected in a passive or ac- tive manner. In the passive collection mode, the personal computer and programmable logic controller broadcast their information to the network periodically using LLDP, which enables the adversary to capture and analyze LLDP packets to identify the devices. In the active collection mode, the adversary uses the PROFINET Discovery and Basic Configuration Protocol (PN-DCP) to query and determine the existence of the personal computer and programmable logic controller [START_REF] Timorin | SCADA deep inside: Protocols and security mechanisms[END_REF],

The proof-of-concept program developed in this research sends PN-DCP messages to the network devices and captures and analyzes the response packets to identify the devices of interest. The model information and IP addresses of the devices were obtained by sending simple PN-DCP broadcast packets. Figure 6 shows the response packets from the programmable logic controller that were captured by Wireshark.

False Command Injection Attack

After the programmable logic controller was discovered, the proof-of-concept program attempted to modify the behavior of the elevator system by sending a write command to the PA entry of the programmable logic controller. After the input value was changed, the programmable logic controller responded to the input according to its ladder logic program. The injected input signal requested the elevator to go to a different floor; this injected signal was the same as the signal that would be sent upon pressing the car call button on the control panel. Figure 7 shows how the proof-of-concept program used the S7 base protocol read-variable and write-variable commands to query and manipulate the status of the programmable logic controller.

Control Signal Injection Attack

The false input command injection attack changed the behavior of the elevator system by sending a write command to the PE entry of the programmable logic controller. An output (control) signal injection attack is more harmful. This attack can change the power output directly, which means that the programmable logic controller would behave differently from the manner specified by its ladder logic program. In the case of the elevator, the false command in- jection attack merely moved the elevator in the same way as when the control panel is used. However, the output control signal injection attack can force the elevator to stop between two floors. Figure 8 shows the result -the elevator car stopped between the fifth and sixth floors after the false control signal was sent to the programmable logic controller.

Control Variable Injection Attack

A ladder logic program contains a number of variables called programmable logic controller tags that control or perform various operations. An adversary who is able to control the personal computer with the TIA Portal installed would be able to obtain the running ladder logic (including the variables and their addresses) using the Download from PLC function.

In the case of the model elevator system, after the downloaded ladder logic program was modified and uploaded to the programmable logic controller, it was possible to fully control the elevator, including making it function improperly. In the experiments, the buzzer variable was changed from false to true, which caused the buzzer to sound forever. The current position of the elevator was also changed while it was moving, which caused the elevator to move to the wrong floor. Note that these variables cannot be configured as read-only as a security measure because the human-machine interface must be able to change the values of variables during normal operations. Figure 9 shows some of the programmable logic controller variables in the TIA Portal that are used to command the elevator. Figure 10 shows the current and desired positions of the elevator while it was moving.

Sensor Value Response Modification Attack

Sensor values are stored as programmable logic controller tags. These values can be changed to negatively impact the elevator logic. Since the communications between the sensor and programmable logic controller are neither encrypted nor authenticated, the ladder logic program of the programmable logic controller would then execute based on the changed sensor values. In the experiments, the door light sensor value was changed, which prevented the elevator control system from detecting that something was jammed between the doors and the elevator kept trying to close the doors. Figure 11 shows the sensor variables in the TIA Portal that may be modified in sensor value response modification attacks.

Discussion and Recommendations

Current programmable logic controller security mechanisms are inadequate for combating malicious attacks. All workstations and personal computers installed with the Siemens TIA Portal and located in an internal control network are attractive targets for attacks. As shown in Figure 1, an adversary can discover these computing platforms by capturing and analyzing LLDP packets.

Installing sensors throughout an industrial control network provides situational awareness about attacks and anomalies, but sophisticated adversaries can tamper with the sensor values and send false commands and signals to programmable logic controllers. Because of the complexity of industrial control systems and their underlying physical processes, network intrusion detection and prevention systems have obvious limitations. A promising solution is to encrypt and authenticate all communications involving human-machine interfaces, programmable logic controllers and engineering/development workstations. This is especially important because future industrial control system attacks will go beyond utilizing an engineering workstation to download malicious ladder logic programs and seek to control and attack the programmable logic controllers directly.

Programmable logic controller protection mechanisms also must be enhanced because adversaries can exploit the S7 base protocol and bypass the security configurations to execute attacks. The S7 base protocol should be locked down in modern versions of Siemens programmable logic controllers. In the case of the Siemens TIA Portal, the PE and PA entries in programmable logic controllers should be configured to provide adequate security.

Figure 12 shows that malware can easily discover the development personal computer by capturing and analyzing LLDP packets. Having discovered the personal computer, the adversary could attempt to gain access to it. Firewalls or other network filtering mechanisms must be deployed to block these protocol packets so that it is more difficult to discover devices in an industrial control network.

The following recommendations are made to secure the internal network of an industrial control system:

The development personal computer should be well protected. External device and Internet connections should be disabled to prevent malware attacks.

Firewalls should be deployed to ensure that discovery and control commands only come from authorized devices.

Multiple programmable logic controllers from different vendors should be employed in order to survive attacks that target a specific programmable logic controller model or brand.

Logging and heartbeat mechanisms should be incorporated in ladder logic programs to detect unauthorized modifications. Industrial control engineers must be cognizant of programmable logic controller vulnerabilities and potential attacks.

Conclusions

The vast majority of research in industrial control system security has focused on network-level intrusion detection and protection mechanisms. In contrast, this research has specifically considered the threats to the internal networks of industrial control systems, which include the connections from the computer platforms that manage programmable logic controllers. The threat model assumes that an adversary can gain access to the internal network of an industrial control system by various means and specifies several attacks on the confidentiality, integrity and availability of programmable logic controllers. Experiments involving a model elevator system with a Siemens programmable logic controller demonstrate the potential attacks and their impacts, and provide guidance for implementing security solutions that can mitigate the attacks.

Future research will concentrate on a larger testbed with programmable logic controllers from different vendors. Additionally, efforts will be directed at developing lightweight security solutions for programmable logic controllers that satisfy the real-time constraints of production industrial control systems.

Figure 1 .

 1 Figure 1. Leveraging LLDP broadcast messages to discover device information.

Figure 2 .

 2 Figure 2. Manipulating the LED of a programmable logic controller.

Figure 3 .

 3 Figure 3. Elevator system testbed.

Figure 4 .

 4 Figure 4. Ladder logic program used by the elevator system.

Figure 5 .

 5 Figure 5. Attack entry point to the elevator system.

Figure 6 .

 6 Figure 6. Discovering programmable logic controller information via PN-DCP.

Figure 7 .

 7 Figure 7. Using the S7 base protocol to read and write data.

Figure 8 .

 8 Figure 8. Stopping the elevator car between two floors.

Figure 9 .

 9 Figure 9. Variables used to store commands.

Figure 10 .

 10 Figure 10. Variables used to store the current and desired elevator positions.

Figure 11 .

 11 Figure 11. Sensor variables in the TIA Portal.

Figure 12 .

 12 Figure 12. Using the Siemens TIA Portal to obtain information via LLDP.