Jean-Charles Faugère
email: jean-charles.faugere@inria.fr.

George Labahn
email: glabahn@uwaterloo.ca.

Mohab Safey
email: mohab.safey@lip6.fr.

El Din

Éric Schost
email: eschost@uwaterloo.ca.

Thi Xuan Vu
email: txvu@uwaterloo.ca.

Computing critical points for invariant algebraic systems

Let K be a field and φ, f = (f 1 , . . . , f s ) in K[x 1 , . . . , x n ] be multivariate polynomials (with s < n) invariant under the action of S n , the group of permutations of {1, . . . , n}. We consider the problem of computing the points at which f vanish and the Jacobian matrix associated to f , φ is rank deficient provided that this set is finite.

We exploit the invariance properties of the input to split the solution space according to the orbits of S n . This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in d s , n+d d and n s+1 where d is the maximum degree of the input polynomials. When d, s are fixed, this is polynomial in n while when s is fixed and d ≃ n this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.

Introduction

Our main motivation in this paper is the problem of finding the critical points of a polynomial map φ restricted to an algebraic set V (f ), where f = (f 1 , . . . , f s ) and φ come from the multivariate polynomial ring K[x 1 , . . . , x n ], with K a field of characteristic zero. The problem of computing such points appears in many application areas including for example polynomial optimization and real algebraic geometry.

In our case we consider the closely related problem of computing a description of the set W (φ, f ) defined by the following equations:

f 1 , . . . , f s + M s+1 (Jac(f , φ)) (1)
where, Jac(f , φ) is the Jacobian matrix of (f 1 , . . . , f s , φ) with respect to (x 1 , . . . , x n ), and M r (G) denotes the set of all r-minors of a matrix G. If we assume that the Jacobian matrix operations in K. Here D reg = d(s -1) + (d -2)n + 2, and ω is the exponent of multiplying two (n × n)-matrices with coefficients in K (see [START_REF] Spaenlehauer | On the complexity of computing critical points with Gröbner bases[END_REF] for a generalization to systems with mixed degrees).

In this paper, we consider the important case where the polynomials f 1 , . . . , f s and φ are all invariant under the action of the symmetric group S n . As we will show later, the set W (φ, f ) is then also invariant under S n .

There has been considerable work on solving symmetric algebraic systems. Indeed, while it is always possible to compute the Gröbner basis of a set of symmetric polynomials, symmetries of the initial system are lost during the computation. In [START_REF] Colin | Solving a system of algebraic equations with symmetries[END_REF], for a finite symmetry group, Colin proposed to use primary and secondary invariants [START_REF] Sturmfels | Algorithms in Invariant Theory[END_REF] to reformulate the problem. For the particular case of S n -invariant equations, in [START_REF] Faugère | Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases[END_REF], the authors compute a SAGBI-Gröbner basis in the ring K[e 1 , . . . , e n ], where e i is a variable corresponding to i-th elementary symmetric polynomial η i in (x 1 , . . . , x n ). However, even if f 1 , . . . , f s and φ are S n -invariant, the equations in [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF] are usually not invariant, so these technique cannot be directly applied to our problem.

It is possible to prove that the system of equations in (1) is globally invariant: for all σ ∈ S n , and any g among either f 1 , . . . , f s or the (s + 1)-minors of Jac(f , φ), either σ(g) or -σ(g) belongs again to the same set of equations. This implies that W (φ, f ) is S n -invariant, as we claimed above. As an example, with n = 3 and s = 1, in order to determine the critical points of φ = x 1 x 2 x 3 -3x 1 -3x 2 -3x 3 over the sphere defined by f = x 2 1 + x 2 2 + x 2 3 -6, one has to solve the globally invariant set of equations defined by

{f = 0 , x 2 1 x 3 -x 2 2 x 3 -3x 1 +3x 2 = 0, x 2 1 x 2 -x 2 x 2 3 -3x 1 +3x 3 = 0, x 1 x 2 2 -x 1 x 2 3 -3x 2 +3x 3 = 0}.
For such systems, following [START_REF] Faugère | The membrane inclusions curvature equations[END_REF], the authors in [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] used divided differences to construct a new system which is S n -invariant. Our work is inspired by this reference, but the specific type of the equations that we solve, involving minors of a Jacobian matrix, requires us to extend the work from [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] (in addition, no complexity analysis is given in that reference). The global invariance property allows us to split the set W = W (φ, f ) into orbits under the action of the symmetric group. The size of the orbit of a point in W will depend on the number of pairwise distinct coordinates of that point. For example, for f and φ as above, the points (2, 1, 1), (0, √ 3, √ 3), (-2, -1, -1) are solutions with three elements in their respective S 3 -orbits, while the point (

√ 2, √ 2, √ 2
) is also a solution, with only one point in its orbit (this is the whole decomposition of W into orbits). To devise a fast algorithm, the different sizes of orbits needs to be taken into consideration. This phenomenon is to be expected for systems such as [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF], but is not discussed for the particular family of equations in [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] (on the other hand, that reference takes into consideration further properties of the family of equations considered therein). The structure of these orbits is determined by the number of pairwise distinct coordinates of the points they contain. To study them, we make use of partitions of n. A sequence λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ), with the ℓ i and n i positive integers and

n 1 < • • • < n r , is called a partition of n if n 1 ℓ 1 + n 2 ℓ 2 + • • • + n r ℓ r = n.
Partitions of n will be used to parameterize orbits, with λ as above parameterizing those points in W having ℓ 1 distinct sets of n 1 equal coordinates, ℓ 2 distinct sets of n 2 equal coordinates and so on. We will write W λ for the set of such orbits contained in W , so that W is the disjoint union of all W λ , for all partitions λ of n.

For instance, for the φ and f mentioned previously, our algorithm will determine that the set W (1 3 ) of orbits parameterized by λ = (1 3 ), which corresponds to the orbits with all distinct coordinates (ξ 1 , ξ 2 , ξ 3 ), is equal to the zero set of (f, -4, -2(x 1 + x 2 + x 3 ), 2(x 2 1 + x 2 2 + x 2 3 ) + 8(x 1 x 2 + x 2 x 3 + x 1 x 3 ) -36) (and so W (1 3 ) is empty, as we saw above). The set W (1 1 2 1 ) of orbits parameterized by λ = (1 1 2 1 ), that is, orbits of points of the form (ξ 1 , ξ 2 , ξ 2 ), with ξ 1 = ξ 2 , is the orbit of the zero set of (x 2 1 + 2x 2 2 -6, x 2 2 + x 1 x 2 -3, x 2 -x 3 ), where the first component is f restricted to the hyperplane x 2 = x 3 . In particular, W (1 1 2 1 ) is the union of the orbits of the points (2, 1, 1), (0, √ 3, √ 3), (-2, -1, -1) seen above. In this paper we provide a procedure to determine invariant polynomials that describe these S n -orbits. For an orbit parameterized by the partition λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ), we work with points which have distinct coordinates (ξ 1,1 , . . . , ξ 1,ℓ 1 , ξ 2,1 , . . . , ξ 2,ℓ 2 , . . . , ξ r,1 , . . . , ξ r,ℓr ), so that instead of n coordinates, there are only ℓ = ℓ 1 + • • • + ℓ r distinct coordinates for points in this orbit. Then, invariance under of W permutations implies that single distinct points are permuted, groups of two points are permuted, etc. This will allow us to work with polynomials in K[e 1 , . . . , e r ] = K[e 1,1 , . . . , e 1,ℓ 1 , e 2,1 , . . . , e 2,ℓ 2 , . . . , e r,1 , . . . , e r,ℓr ], in order to represent a certain "compressed" image W ′ λ ⊂ K ℓ of W λ ; here, e i,1 , . . . , e i,ℓ i are variables standing for the elementary symmetric polynomial in ℓ i indeterminates and K is an algebraic closure of K. In our running example, for λ = (1 1 2 1 ), we have ℓ = 2 and W ′

(1 1 2 1 ) is the set {(2, 1), (0, √ 3), (-2, -1)}. Throughout the paper, we will assume that W , and thus all W λ and W ′ λ , are finite. Then, for λ as above, the cardinality of W ′ λ is smaller than that of W λ by a factor γ λ = n n 1 , . . . , n 1 , . . . , n r , . . . , n r ,

where each n i is repeated ℓ i times. Altogether, if d is the maximum of the degrees of the input of polynomials, then we will prove some bounds, which will be denoted by c λ , on the cardinality of the finite set W ′ λ ; we will see that, in practice, each of the c λ provides an accurate bound on the cardinality of W ′ λ . The sum of the c λ 's then gives us an upper bound on the size of the output of our main algorithm. We did not find a closed formula for this sum, but we can prove that it is bounded above by

c = d s n + d -1 n . (2)
We will see that, in practice, this is a rather rough upper bound but in several cases, it compares well to the upper bound

c = d s (d -1) n-s n s (3)
from Nie and Ranestad [34, Theorem 2.2] on the size of W . For example, when d = 2, we have c = 2 s (n + 1) while c = 2 s n s . More generally, when d and s are fixed, c is polynomial in n (since it is bounded above by

d s (n + d -1) d ) while c is exponential in n (since it is greater than (d -1) n ). When s is fixed and d = n, c is n O(1) 2 n , whereas c is n O(1) (n -1) n-s .
In view of this discussion, our algorithm will naturally compute descriptions of the sets W ′ λ rather than W λ (we will also explain how one would recover the later knowing the former). There are a number of ways to represent algebraic sets; in our case we make use of a representation based on univariate polynomials. In particular, if Y ⊂ K m is a zero-dimensional variety defined by polynomials in K[z 1 , . . . , z m ], then a zero-dimensional parametrization R = ((q, v 1 , . . . , v m ), µ) of Y consists of (i) a squarefree polynomial q in K[y], with y a new indeterminate and deg(q

) = |Y |, (ii) polynomials (v 1 , . . . , v m ) in K[y] with deg(v i ) < deg(q) for all i, and satisfying Y = {(v 1 (τ ), . . . , v m (τ )) ∈ K m | q(τ ) = 0}, (iii) a vector µ = (µ 1 , . . . , µ m ) in K m such that µ 1 v 1 + • • • + µ m v m = y.
When these conditions hold, we write Y = Z(R).

The last condition says that the roots of q are the values taken by the linear form

µ 1 z 1 + • • • + µ m z m on Y .
In particular, this linear form takes pairwise distinct values on the points of Y . This representation was first introduced in the works of Kronecker and König [START_REF] Kronecker | Grundzüge einer arithmetischen Theorie der algebraischen Grössen[END_REF] and has been widely used in computer algebra [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF][START_REF] Gianni | Algebraic solution of systems of polynomial equations using Gröbner bases[END_REF][START_REF] Giusti | Straight-line programs in geometric elimination theory[END_REF]21,[START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF][START_REF] Rouillier | Solving zero-dimensional systems through the Rational Univariate Representation[END_REF]. The output of our algorithm will thus be a collection of zero-dimensional parameterizations, one for each of the sets W ′ λ ; we will call such a data structure a symmetric representation of W (precise definitions are in Section 2).

However, rather than using Gröbner bases to compute such descriptions, we will use a symbolic homotopy continuation, so as to control precisely the cost of the algorithm. Homotopy continuation has become a foundational tool for numerical algorithms while the use of symbolic homotopy continuation algorithms is more recent. Such algorithms first appeared in [START_REF] Bompadre | Polynomial equation solving by lifting procedures for ramified fibers[END_REF][START_REF] Heintz | Deformation techniques for efficient polynomial equation solving[END_REF], for general inputs, and later for sparse [START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF][START_REF] Herrero | Computing isolated roots of sparse polynomial systems in affine space[END_REF][START_REF] Herrero | Affine solution sets of sparse polynomial systems[END_REF][START_REF] Herrero | Elimination for generic sparse polynomial systems[END_REF] and multi-homogeneous systems [START_REF] El Din | Bit complexity for multi-homogeneous polynomial system solving -application to polynomial minimization[END_REF][START_REF] Heintz | Intersection theory and deformation algorithms: the multi-homogeneous case[END_REF][START_REF] Hauenstein | Solving determinantal systems using homotopy techniques[END_REF].

In our case we can make use of a recent sparse symbolic homotopy method given in [START_REF] Labahn | Homotopy techniques for solution of sparse determinantal ideals[END_REF] specifically designed to handle determinantal systems over weighted polynomial rings, that is, multivariate polynomial rings where each variable has a weighted degree, which is a positive integer. These domains arise naturally for our orbits: the domain arising from an orbit parameter λ has variables e i,k which are defined corresponding to elementary symmetric polynomials η i,k ; since η i,k has degree k, the variable e i,k will naturally be assigned weight k.

Theorem 1.1. Suppose f = (f 1 , . . . , f s ) and φ are S n -invariant polynomials in K[x 1 , . . . , x n ], with degree at most d ≥ 2, and suppose that W = W (φ, f ) is finite. There exists a randomized algorithm that takes f , φ as input and outputs a symmetric representation for the set W , and whose runtime is polynomial in d s , n+d d , n s+1 . The total number of points described by the output is at most

d s n+d-1 n .
Note that the runtime is polynomial in the bound we give on the output size, as well as the number n s+1 of maximal minors in the matrix Jac(f , φ). Section 4 gives a more precise estimate on the runtime of the algorithm.

We use standard notions and notations of commutative algebra and algebraic geometry which can be found for example in [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF][START_REF] Eisenbud | Commutative Algebra: with a View Toward Algebraic Geometry[END_REF]. We will assume that the reader is familiar with concepts such as dimension, Zariski topology, equidimensional algebraic set and the degree of an algebraic set, with definitions found in [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF][START_REF] Eisenbud | Commutative Algebra: with a View Toward Algebraic Geometry[END_REF].

The remainder of the paper is organized as follows. In the next section, we provide several properties of invariant polynomials and discuss in detail the sets W λ and W ′ λ mentioned above. Section 3 contains our main algorithm, called Critical Points Per Orbit and includes a proof of correctness. The runtime of this algorithm is analysed in Section 4, finishing the proof of Theorem 1.1. Experiments to validate our new algorithm is given in Section 5 followed by a section which gives topics for future research. The latter section also includes a discussion on how our results can decide emptiness of S n -invariant algebraic sets over a real field. The appendices include a proof of two technical propositions.

Partitions and distinct coordinates of S n -invariants

One of our key observations, formalized in the next section, is that the special nature of our set of critical points allows us to split W (φ, f ) into subsystems defined by the orbits of the symmetric group S n .

More precisely, in this paper an orbit is a set of the form S n (ξ), for some point ξ in K n , that is, it is the set of all S n -conjugates of ξ. As mentioned in the introduction, the size of an orbit S n (ξ) will depend on the number of pairwise distinct coordinates of ξ. For example, with n = 3, a point of the form (ξ 1 , ξ 2 , ξ 2 ) will have an orbit of size 3, unless we have ξ 1 = ξ 2 (in which case the orbit has size 1).

As a result, we need to consider the separation of distinct coordinates in an orbit, which is what we do in this section. We do this through a discussion of the geometry of (finite) S n -invariant subsets of K n and the data structures we can use to represent them. Much of what follows is preliminary for our description of orbits presented in the next section.

Partitions

Partitions play a major role in describing our orbits. In this subsection, we gather the basic definitions of partitions and of a few notions attached to them, which will be used throughout this section.

A sequence λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ), with ℓ i 's and n i 's positive integers and

n 1 < • • • < n r , is called a partition of n, sometimes denoted by λ ⊢ n, if n 1 ℓ 1 + n 2 ℓ 2 + • • • + n r ℓ r = n. The number ℓ = r
i=1 ℓ i is called the length of the partition λ. We remark that to a partition such as λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) we can associate (in a one-to-one manner) the ordered list (n 1 , . . . , n 1 , . . . , n r , . . . , n r ), with each n i repeated ℓ i times.

We will make use of the refinement order on partitions. To describe this we first need to define the union of partitions: if λ and λ ′ are partitions of a and a ′ , respectively, then λ ∪ λ ′ is the partition of a + a ′ whose ordered list is obtained by merging those of λ and λ ′ . Then, consider two partitions λ = (n

ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) and λ ′ = (m k 1 1 m k 2 2 .
. . m ks s ) of the same integer n. As in [33, p. 103] (or e.g. [3, p. 16]), we write λ ≤ λ ′ , and we say that λ refines λ ′ , if λ is the union of some partitions (λ i,j ) 1≤i≤s,1≤j≤k i , where λ i,j is a partition of m i for all i, j.

Example 2.1. For the partitions of n = 3, we have

(1 3 ) ≤ (1 1 2 1 ) ≤ (3 1 ). Let λ = (n ℓ 1 1 n ℓ 2 2 .
. . n ℓr r ) be a partition of n having length ℓ. For k = 1, . . . , r, we will denote by Z k = (z k,1 , . . . , z k,ℓ k ) a sequence of ℓ k indeterminates. When convenient, we will also index the entire sequence of indeterminates (Z 1 , . . . , Z r ) = (z 1,1 , . . . , z r,ℓr ) as (z 1 , . . . , z ℓ ), so that z 1 = z 1,1 , . . . , z ℓ = z r,ℓr . From this point of view, introducing τ 0 = 0 and τ k = k i=1 ℓ i , for k = 1, . . . , r, any index i in 1, . . . , ℓ can be written uniquely as i = τ k-1 + u, for some k in 1, . . . , r and u in 1, . . . , ℓ k . Thus, the indeterminates z k,1 , . . . , z k,ℓ k are numbered z τ k-1 +1 , . . . , z τ k , with τ r = ℓ.

We will let S λ be the group

S λ = S ℓ 1 × • • • × S ℓr .
S λ acts naturally on K[Z 1 , . . . , Z r ], and we will denote by K[Z 1 , . . . , Z r ] S λ the K-algebra of S λ -invariant polynomials. Note that S λ can be seen as a subgroup of the permutation group S ℓ of {1, . . . , ℓ}, where S ℓ 1 acts on the first ℓ 1 indices, S ℓ 2 acts on the next ℓ 2 ones, etc. Finally, for i = 1, . . . , r, we will let η i = (η i,1 , . . . , η i,ℓ i ) denote the vector of elementary symmetric polynomials in variables Z i , where η i,j has degree j for all i, j.

S λ -invariant polynomials: the Symmetric Coordinates algorithm

Let λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) be a partition of n having length ℓ, and, for i = 1, . . . , r, let e i = (e i,1 , . . . , e i,ℓ i ) be a set of ℓ i new variables. Then, by the fundamental theorem of symmetric polynomials [9, Theorem 3.10.1], for any f in K[Z 1 , . . . , Z r ] S λ , there exists a unique f in K[e 1 , . . . , e r ] with

f (Z 1 , . . . , Z r ) = f (η 1 , . . . , η r ), (4)
for η 1 , . . . , η r as defined in the previous subsection. We will need a quantitative version of this existence result, which gives an estimate on the cost of computing f from f . Lemma 2.2. There exists an algorithm Symmetric Coordinates(λ, f ) which, given a partition λ of n and f of degree at most d in K[Z 1 , . . . , Z r ] S λ , returns f such that f = f (η 1 , . . . , η r ), using O˜( ℓ+d d 2 ) operations in K. 1Proof. Algorithm Symmetric Coordinates is a slight generalization of the procedure described in the proof of Bläser and Jindal's algorithm [4, Theorem 4], which was written only for the case of r = 1, and for polynomials represented as straight-line programs.

The key to the algorithm is the following. Assume we know an integral domain L containing K[e 1 , . . . , e r ], and vectors ζ 1 , . . . , ζ r of elements in L, where for each i,

ζ i = (ζ i,1 , . . . , ζ i,ℓ i ) ∈ L ℓ i are the ℓ i pairwise distinct roots of P i (T ) = T ℓ i -(e i,1 + ρ i,1 )T ℓ i -1 + • • • + (-1) ℓ i (e i,ℓ i + ρ i,ℓ i ),
and where ρ i,1 , . . . , ρ i,ℓ i are the elementary symmetric polynomials evaluated at 1, . . . , ℓ i . Then, f satisfies f (e 1,1 + ρ 1,1 , . . . , e r,ℓr + ρ r,ℓr

) = f (ζ 1 , . . . , ζ r ).
As in Bläser and Jindal's algorithm, we take for L a ring of multivariate power series, namely L = K[[e 1 , . . . , e r ]]. Our construction, involving the shifts by (ρ 1,1 , . . . , ρ r,ℓr ) shows that at

e 1 = • • • = e r = 0, P i (T ) factors as (T -1) • • • (T -ℓ i ).
Applying Newton's iteration, we deduce the existence of the requested power series roots

ζ i = (ζ i,1 , . . . , ζ i,ℓ i ).
In order to obtain the polynomial f , we only need truncations of these roots at precision d. For i = 1, . . . , r, we can obtain the truncation of ζ i using O˜(ℓ i ℓ i +d d

) operations in K, where the factor ℓ i +d d accounts for the cost of multivariate power series arithmetic [START_REF] Lecerf | Fast multivariate power series multiplication in characteristic zero[END_REF]. Taking all i's into account, this adds up to O˜(ℓ ℓ+d d ) arithmetic operations. We then evaluate f at these truncated power series. Since f has degree at most d, this can be done using O( ℓ+d d ) (+, ×) operations on ℓ-variate power series truncated in degree d, for a total of O˜( ℓ+d d 2 ) operations in K. This gives us f (e 1,1 + ρ 1,1 , . . . , e r,ℓr + ρ r,ℓr ). We then apply the translation (e i,j ) i,j ← (e i,j -ρ i,j ) i,j in order to obtain the polynomial f , also at a cost of O˜( ℓ+d d 2 ) operations in K: through successive multiplications, we incrementally compute the translates of all monomials of degree up to d and then, before combining, using the coefficients of f (e 1,1 + ρ 1,1 , . . . , e r,ℓr + ρ r,ℓr ).

S λ -equivariant polynomials: the Symmetrize algorithm

As before we let λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) denote a partition of n of length ℓ = r i=1 ℓ i . The aim of this subsection is to define S λ -equivariant systems of polynomials and give a detailed description of an algorithm, called Symmetrize, that turns an S λ -equivariant system into one which is S λ -invariant.

Consider a sequence of polynomials q = (q 1 , . . . , q ℓ ) in K[Z 1 , . . . , Z r ]. We say that q is S λ -equivariant if for any σ in S λ and i in 1, . . . , ℓ, we have σ(q i ) = q σ(i) , or equivalently q(z σ(1) , . . . , z σ(ℓ) ) = q σ(i) (z 1 , . . . , z ℓ ); here, we are implicitly seeing the elements of S λ as permutations of {1, . . . , ℓ}, as explained in Section 2.1.

In geometric terms, the zero-set V (q) ⊂ K ℓ of such a system is S λ -invariant, even though the equations themselves may not be invariant. In what follows, we describe how to derive equations p = (p 1 , . . . , p ℓ ) that generate the same ideal as q (in a suitable localization of K[Z 1 , . . . , Z r ]) and are actually S λ -invariant. We will need an assumption, discussed below, that z i -z j divides q i -q j for all pairwise distinct indices i, j.

Example 2.3. Let n = 3 and λ = (1 2 2 1 ) so r = 2, ℓ 1 = 2, ℓ 2 = 1 and ℓ = 3; we have S λ = S 2 × S 1 . We take q = (q 1 , q 2 , q 3 ), where

q 1 = z 2 z 2 3 (z 1 + z 2 + 2z 3 ) + z 1 z 2 z 2 3 , q 2 = z 1 z 2 3 (z 1 + z 2 + 2z 3 ) + z 1 z 2 z 2 3 , q 3 = z 1 z 2 z 3 (z 1 + z 2 + 2z 3 ) + z 1 z 2 z 2 3 .
These polynomials satisfy both the equivariance property and the divisibility property. Our procedure will produce the following polynomials:

p 1 = (z 1 + z 2 + 2z 3 )z 3 , p 2 = (z 1 + z 2 + 2z 3 )z 2 z 3 + (z 1 + z 2 + 2z 3 )z 1 z 3 , p 3 = z 1 z 2 z 3 (z 1 + z 2 + 2z 3 ) + z 1 z 2 z 2 3 .
The polynomials (p 1 , p 2 , p 3 ) are symmetric in (z 1 , z 2 ) and (z 3 ), that is, are S 2 × S 1 -invariant. They generate the same ideal as (q 1 , q 2 , q 3 ) in the localization

K[z 1 , z 2 , z 3 ] (z 1 -z 2 )(z 1 -z 3 )(z 2 -z 3 ) .
In order to construct a set of invariant generators we make use of divided differences of q = (q 1 , . . . , q ℓ ). These are defined as q {i} = q i for i in {1, . . . , ℓ}, and for each set of k distinct integers I := {i 1 , . . . , i k } ⊂ {1, . . . , ℓ}, with k ≥ 2,

q I = q {i 1 ,...,i r-1 ,i r+1 ,...,i k } -q {i 1 ,...,i q-1 ,i q+1 ,...,i k } z ir -z iq , (5)
for any choice of i r , i q in I, with i r = i q . Indeed, it is known (see e.g. [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]Theorem 1]) that this defines q I unambiguously (independently of the choice of i r , i q ). Another useful property of divided differences is the following:

(i) if z i -z j divides q i -q j for all 1 ≤ i < j ≤ ℓ, then q I is a polynomial for all I ⊂ {1, . . . , ℓ}.

The following proposition then gives our construction of the polynomials p. In what follows, for i ≥ 0, η i (y 1 , . . . , y s ) denotes the degree i elementary symmetric function in variables y 1 , . . . , y s .

Proposition 2.4. Suppose the sequence q = (q 1 , . . . , q ℓ ) in

K[Z 1 , . . . , Z r ] ℓ is S λ -equivariant and satisfies z i -z j divides q i -q j for 1 ≤ i < j ≤ ℓ. For 0 ≤ k ≤ r -1 and 1 ≤ j < ℓ k+1 , define p τ k+1 = τ k+1 i=τ k +1 q {i,τ k+1 +1,...,τr} , p τ k +j = j s=1 η j-s (z τ k +s+2 , . . . , z τ k+1 ) τ k +s i=τ k +1
q {i,τ k +s+1,...,τr} .

Then the sequence

p = p 1 , . . . , p τ 1 , p τ 1 +1 , . . . , p τ 2 , . . . , p τ r-1 +1 , . . . , p τr is in K[Z 1 , . . . , Z r ] S λ . If all q i 's have degree at most d, then deg(p i ) ≤ d -ℓ + i holds for i = 1, . . . , ℓ. In particular, if ℓ ≥ d + 2, then p i = 0 for all i = 1, . . . , ℓ -d -1.
The degree bound comes by inspection. We defer the rest of the proof (which follows by induction) to Appendix A.

We can also show that q can be written as a linear combination of p, that is, we can find an ℓ × ℓ matrix polynomial U such that pU = q. The construction of U proceeds as follows.

Let M be the block-diagonal matrix with blocks M 1 , . . . , M r given by

M k+1 =           1 η 1 (z τ k +3 , . . . , z τ k+1 ) η 2 (z τ k +3 , . . . , z τ k+1 ) • • • η ℓ k+1 -2 (z τ k +3 , . . . , z τ k+1 ) 0 0 1 η 1 (z τ k +4 , . . . , z τ k+1 ) • • • η ℓ k+1 -3 (z τ k +4 , . . . , z τ k+1 ) 0 0 0 1 • • • η ℓ k+1 -4 (z τ k +5 , . . . , z τ k+1 ) 0 . . . . . . . . . . . . . . . 0 0 0 • • • 1 0 0 0 0 • • • 0 1           , for all 0 ≤ k ≤ r -1. Note that det(M k+1 ) = 1 for all k, hence det(M) = 1.
For a non-negative integer u, denote by I u the identity matrix of size u and by 0 a zero matrix. Then for k = 0, . . . , r -1 and j = 1, . . . , ℓ k+1 , we define the following τ r × τ r polynomial matrices. Set B τ 0 +1 = I τr , C τ 0 +1 = I τr , D τ 0 +j = I τr , and

B τ k +j =   I τ k 0 0 0 E k,j 0 0 0 I τr-τ k+1   , with E k,j =        I j-1 z τ k +j -z τ k +1 . . . z τ k +j -z τ k +j-1 0 0 . . . 0 -1 0 0 0 I ℓ k+1 -j        , (6)
C τ k +j =   I τ k 0 0 0 F k,j 0 0 0 I τr-τ k+1   , with F k,j =   diag(z τ k +j -z τ k +t ) j-1 t=1 0 0 -1 j . . . -1 j -1 j 0 0 0 I ℓ k+1 -j   , (7)
D τ k +j =   diag(z τ k +j -z t ) τ k t=1 0 0 G k,j I ℓ k+1 0 0 0 I τr-τ k+1   , G k,j : j th row is (1, . . . , 1
), rest zeros.

(8) Then we have: Proposition 2.5. Suppose the sequence q = (q 1 , . . . , q ℓ ) in K[Z 1 , . . . , Z r ] ℓ satisfies the conditions of Proposition 2.4. Let ∆ = 1≤i<j≤ℓ (z i -z j ) be the Vandermonde determinant associated with z 1 , . . . , z ℓ . Then the matrix U in K[Z 1 , . . . , Z r ] ℓ×ℓ , defined by

M • U = r-1 k=0 ℓ k+1 j=1 B τ k +j C τ k +j D τ k +j has determinant a unit in K[Z 1 , . . . , Z r , 1/∆] and satisfies pU = q.
The proof of Proposition 2.5 follows by induction and is deferred to Appendix B.

Example 2.6. Consider again the polynomials q = (q 1 , q 2 , q 3 ) and p = (p 1 , p 2 , p 3 ) of Example 2.3. The matrix U which relates p to q is constructed as follows. For k = 0 and j = 1, 2 let

B 1 =   1 0 0 0 1 0 0 0 1   , C 1 =   1 0 0 0 1 0 0 0 1   D 1 =   1 0 0 0 1 0 0 0 1   , B 2 =   1 z 2 -z 1 0 0 -1 0 0 0 1   , C 2 =   z 2 -z 1 0 0 -1 2 -1 2 0 0 0 1   , D 2 =   1 0 0 0 1 0 0 0 1  
while for k = 1 and j = 1 we have

B 3 =   1 0 0 0 1 0 0 0 -1   , C 3 =   1 0 0 0 1 0 0 0 -1   , D 3 =   z 3 -z 1 0 0 0 z 3 -z 2 0 1 1 1   .
In the case λ = (1 2 2 1 ),

M =   1 0 0 0 1 0 0 0 1   and hence U = (B 1 C 1 D 1 )(B 2 C 2 D 2 )(B 3 C 3 D 3 ) =   1 2 (z 3 -z 1 )(z 2 -z 1 ) -1 2 (z 2 -z 1 )(z 3 -z 2 ) 0 1 2 (z 3 -z 1 ) 1 2 (z 3 -z 2 ) 0 1 1 1   . Note that det(U) = 1 2 (z 3 -z 1 )(z 3 -z 2 )(z 2 -z 1 ).
The formulas defining p are straightforward to implement. The following proposition describes the resulting algorithm, called Symmetrize, and gives the cost of this procedure. Proposition 2.7. There exists an algorithm Symmetrize(λ, q) which takes as input q as in Proposition 2.4 and a partition λ of n, and returns p as defined in that proposition. For q of degree at most d, the runtime is O˜(ℓ 3 ℓ+d d ) operations in K. The proof occupies the rest of this section. Write q = (q 1 , . . . , q ℓ ), and recall the expressions defining p = (p 1 , . . . , p ℓ ): for k = 0, . . . , r -1, we have

p τ k +ℓ k+1 = τ k+1 i=τ k +1
q {i,τ k+1 +1,...,τr} and for j = 1, . . . , ℓ k+1 -1,

p τ k +j = j s=1 η j-s (z τ k +s+2 , . . . , z τ k+1 ) s i=1 q {τ k +i,τ k +s+1,...,τr} .
The main issue is to compute the divided differences q {τ k +i,τ k +s+1,...,τr} appearing in these expressions, for k = 0, . . . , r -1 and 1 ≤ i ≤ s ≤ ℓ k+1 . Once this is done, the combinations necessary to obtain p τ k +j are easily carried out. The main ingredient in the proof is the following lemma which describes the computation of a single divided difference. Lemma 2.8. There exists an algorithm Divided Difference(q, I) that takes as input q as in Proposition 2.7 and a subset I = {i 1 , . . . , i k } of {1, . . . , ℓ}, and returns q I . For q of degree at most d, the runtime is O˜(ℓ ℓ+d d ) operations in K. Proof. For j = 1, . . . , k -1, we claim that given q {i 1 ,...,i j-1 } , we can obtain q {i 1 ,...,i j } using O˜( ℓ+d d ) operations in K. To see this note that q {i 1 ,...,i k-1 } has degree at most d. In order to compute q {i 1 ,...,i j } , we use evaluation / interpolation. Choosing ℓ+d d points as prescribed in [START_REF] Canny | Solving systems of non-linear polynomial equations faster[END_REF], the algorithm given there allows us to compute the values of both numerator and denominator in [START_REF] Bompadre | Polynomial equation solving by lifting procedures for ramified fibers[END_REF] in O˜( ℓ+d d ) operations, then compute their ratio, and finally interpolate q {i 1 ,...,i j } in the same asymptotic runtime. The result then follows.

Our Symmetrize algorithm then proceeds as follows. Apply algorithm Divided Difference from Lemma 2.8 to all [τ k + i, τ k + s + 1, . . . , τ r ], for k = 0, . . . , r -1 and 1 ≤ i ≤ s ≤ ℓ k+1 . There are O(ℓ 2 ) such indices, so this step takes O˜(ℓ 3 ℓ+d d ) operations in K, allowing us to compute all sums s i=1 q {τ k +i,τ k +s+1,...,τr} for the same asymptotic cost. For k = 0, . . . , r -1, j = 1, . . . , ℓ k+1 -1 and s = 1, . . . , j, we then compute the elementary symmetric polynomial η j-s (z τ k +s+2 , . . . , z τ k+1 ), which does not involve any arithmetic operations. We multiply it by the above sum, with cost O˜( ℓ+d d ), since the polynomials involved in the product have degree sum at most d and at most ℓ variables. Taking all indices k, j, s into account, this adds another O˜(ℓ 3 ℓ+d d ) steps to the total.

Symmetric representations

In this subsection we describe the geometry of S n -orbits in K n , we define the data structure we will use to represent S n -invariant sets, and present some basic algorithms related to it.

The mapping E λ and its fibers. For a partition λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) of n, we define the following two subsets of K n : (i) C λ : the set of all points ξ in K n that can be written as : the set of all ξ in C λ for which the ξ i,j 's in [START_REF] Derksen | Computational Invariant Theory. Invariant Theory and Algebraic Transformation Groups[END_REF] are pairwise distinct.

ξ = ξ 1,1 , . . . , ξ 1,1 n 1 , . . . , ξ 1,ℓ 1 , . . . , ξ 1,ℓ 1 n 1 , . . . , ξ
To any point ξ in K n we can associate its type: this is the unique partition λ of n such that there exists σ in S n for which σ(ξ) lies in C strict λ . Since all points in an orbit have the same type, we can then define the type of an orbit as the type of any point in it. Any orbit of type λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) has size

γ λ = n n 1 , . . . , n 1 , . . . , n r , . . . , n r = n! n 1 ! ℓ 1 • • • n r ! ℓr since the stabilizer of a point in C strict λ is S ℓ 1 n 1 × • • • × S ℓr nr .
Clearly all points in C strict λ have type λ, but this is not necessarily true for all points in C λ . This can be understood with the help of the refinement order we introduced in Subsection 2.1, as C λ contains points of type λ ′ for all λ ′ ≥ λ. More precisely, C λ is the disjoint union of all C strict λ for all λ ′ ≥ λ.

Example 2.9. For the partitions of n = 3, we have

(1 3 ) < (1 1 2 1 ) < (3 1 ). In addition, (a) C (1 3 ) is K 3 , while C strict (1 3
) is the set of all points ξ with pairwise distinct coordinates.

(b) C (1 1 2 1 )
is the set of points that can be written ξ

= (ξ 1,1 , ξ 2,1 , ξ 2,1 ), while C strict (1 1 2 1 ) is the subset of it where ξ 1,1 = ξ 2,1 . (c) C (3 1 ) = C strict (3 1 )
is the set of points ξ whose coordinates are all equal.

For λ as above, we define a mapping E λ :

C λ → K ℓ by E λ : ξ as in (9) → (η i (ξ i,1 , . . . , ξ i,ℓ i ), . . . , η ℓ i (ξ i,1 , . . . , ξ i,ℓ i )) 1≤i≤r ,
where for i = 1, . . . , r and j = 1, . . . , ℓ i , η j (ξ i,1 , . . . , ξ i,ℓ i ) is the degree j elementary symmetric function in ξ i,1 , . . . , ξ i,ℓ i . One should see this mapping as a means to compress orbits: through the application of E λ , one can represent a whole orbit O of type λ, which has size γ λ , by the single point

E λ (O ∩ C λ ) = E λ (O ∩ C strict λ ).
To put this into practice, we need to be able to recover an orbit from its image. Note that the mapping E λ is onto: for ε = (ε 1,1 , . . . , ε r,ℓr ) in K ℓ , one can find a point ξ in the preimage E -1 λ (ε) by finding the roots ξ i,1 , . . . , ξ i,ℓ i of

P i (T ) = T ℓ i -ε i,1 T ℓ i -1 + • • • + (-1) ℓ i ε i,ℓ i ,
for i = 1, . . . , r. Since we will use this idea often, we will write E * λ (ε) = S n (ξ) for the orbit of any such point ξ in E -1 λ (ε). This is well-defined, as all points in this fiber are S n -conjugate. More generally, for a set G in K ℓ , we will write E * λ (G) for the union of the orbits E * λ (ε), for ε in G.

The image E λ (C strict λ ) of those points having type λ is an open subset O λ K ℓ , defined by the conditions that the polynomials P i above are pairwise coprime and squarefree. For

ε in K ℓ \ O λ , the orbit E * λ (ε)
does not have type λ, but rather type λ ′ , for some partition λ ′ > λ.

Example 2.10. With n = 3 and λ = (1 1 2 1 ), we have ℓ = 2 and E λ maps points of the form

(ξ 1,1 , ξ 2,1 , ξ 2,1 ) to (ξ 1,1 , ξ 2,1
). The polynomials P 1 , P 2 defined in the previous paragraph are respectively given by P

1 (T ) = T -ε 1,1 and P 2 (T ) = T -ε 2,1 , and O λ is defined by ε 1,1 = ε 2,1 . The point ε = (2, 3) is in O λ ; the orbit E * λ (2, 3) is {(2, 3, 3), (3, 2, 3), (3, 3, 2)}. On the other hand, ε = (1, 1) is not in O λ ; the orbit E * λ (1, 1) is the point {(1, 1, 1)}, and it has type (3 1 ) > (1 1 2 1 ). Finally, if we define G = {(1, 1), (2, 3)}, then E * λ (G) is the set W = {(1, 1, 1), (2, 3, 3), (3, 2, 3), (3, 3, 2)}.
We will need an algorithm that computes the type λ ′ of the orbit E * λ (ε), for a given ε in K ℓ , and also computes the value that the actual compression mapping E λ ′ takes at this orbit. The algorithm's specification assumes inputs in K (since our computation model is a RAM over K) but the procedure makes sense over any field extension of K. We will use this remark later in the proof of Lemma 2.16.

Lemma 2.11. There exists an algorithm Type Of Fiber(λ, ε) which takes as input a partition λ of n with length ℓ and a point ε in K ℓ , and returns a partition λ ′ of n of length k and a tuple f in K k , such that

(i) λ ′ is the type of the orbit O := E * λ (ε) (ii) E λ ′ (O ∩ C strict λ ′ ) = {f }.

The algorithm runs in time O˜(n).

Proof. Write ε = (ε 1,1 , . . . , ε r,ℓr ). The points in E -1 λ (ε) are obtained as permutations of , where for i = 1, . . . , r, ξ i,1 , . . . , ξ i,ℓ i are the roots of

ξ = ξ 1,1 , . . . , ξ 1,1 n 1 , . . . , ξ
P i (T ) = T ℓ i -ε i,1 T ℓ i -1 + • • • + (-1) ℓ i ε i,ℓ i = 0.
Finding the type of such a point ξ amounts to finding the duplicates among the ξ i,j 's. Finding such duplicates can be done by computing the product

P = T ℓ 1 -ε 1,1 T ℓ 1 -1 + • • • + (-1) ℓ 1 ε 1,ℓ 1 n 1 • • • T ℓr -ε r,1 T ℓr-1 + • • • + (-1
) ℓr ε r,ℓr nr and its squarefree factorization

P = Q m 1 1 • • • Q ms s , with m 1 < • • • < m s and all Q i 's squarefree and pairwise coprime. If k i = deg(Q i ) then ξ has type λ ′ = (m k 1 1 m k 2 2 . . . m ks s ) with λ ′ > λ. If we write Q i = T k i -f i,1 T k i -1 + • • • + (-1) k i f i,k i , 1 ≤ i ≤ s, then our output is (λ ′ , f ), where f = (f 1,1 , . . . , f s,ks ).
Using subproduct tree techniques [START_REF] Gathen | Modern Computer Algebra[END_REF]Chapter 10] to compute P and fast GCD [18, Chapter 14], all computations take quasi-linear time O˜(n).

Example 2.12. Let n = 3 and λ = (1

1 2 1 ), with E λ (ξ 1,1 , ξ 2,1 , ξ 2,1 ) = (ξ 1,1 , ξ 2,1 ). We saw that for ε = (1, 1) in K 2 , the orbit E * λ (1, 1) is {(1, 1, 1)}, which has type λ ′ = (3 1
). Since n 1 = 1 and n 2 = 2, the above algorithm first expands the product (T -1)(T -1) 2 as T 3 -3T 2 + 3T -1, then computes its squarefree factorization as (T -1) 3 . From this, we read off that s = 1, m 1 = 3 and k 1 = 1, so that λ ′ is indeed (3 1 ). The output is (λ ′ , E λ ′ (1, 1, 1)), the latter being equal to [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF].

A data structure for S n -invariant sets. The previous setup allows us to represent invariant sets in K n as follows. Let W be a set in K n , invariant under the action of S n . For a partition λ of n with ℓ, we write

W λ = S n (W ∩ C strict λ ) ⊂ K n and W ′ λ = E λ (W ∩ C strict λ ) ⊂ K ℓ , (10)
where

S n (W ∩ C strict λ
) is the orbit of W ∩ C strict λ under S n , or, equivalently, the set of points of type λ in W (so this matches the notation used in the introduction).

For two distinct partitions λ, λ ′ of n, W λ and W λ ′ are disjoint, so that any invariant set W can be written as the disjoint union W = ⊔ λ⊢n W λ . When W is finite, we then can represent W λ by describing the image W ′ λ . Indeed, the cardinality of the set W ′ λ is smaller than that of the orbit W λ by a factor of γ λ , and we can recover W λ as W λ = E * λ (W ′ λ ). Altogether, we are led to the following definition. Definition 2.13. Let W be a finite set in K n , defined over K and S n -invariant. A symmetric representation of W is a sequence (λ i , R i ) 1≤i≤N , where the λ i 's are all the partitions of n for which W λ i is not empty, and, for each i, R i is a zero-dimensional parametrization of W ′ λ i . Example 2.14. Suppose n = 3 and

W = {(1, 1, 1), (2, 3, 3), (3, 2, 3), (3, 3, 2)}. Then with λ = (1 1 2 1 ) we have W λ = {(2, 3, 3), (3, 2, 3), (3, 3, 2)}, W ′ λ = {(2, 3)} ⊂ K 2 and γ λ = 3, while with λ ′ = (3 1 ), we have W λ ′ = {(1, 1, 1)}, W ′ λ ′ = {(1)} ⊂ K 1 and γ λ ′ = 1. A symmetric representation of W would consist of (λ, R λ ) and (λ ′ , R λ ′ ), with Z(R λ ) = {(2, 3)} and Z(R λ ′ ) = {(1)}.
Our main algorithm will have to deal with the following situation. As input, we will be given a representation of the set G in K ℓ ; possibly, some points in G will not be in the open set O λ (that is, may correspond to orbits having type λ ′ , for some λ ′ > λ). As usual, the finite set G will be described by means of a zero-dimensional parametrization. Our goal will then be to compute a symmetric representation of E * λ (G). Example 2.15. Take n = 3, and again let λ = (1 1 2 1 ), with E λ (ξ 1,1 , ξ 2,1 , ξ 2,1 ) = (ξ 1,1 , ξ 2,1 ). Assume we are given G = {(1, 1), (2, 3)} ⊂ K 2 . In this case, E * λ (G) is the set W seen in Examples 2.10 and 2.14, and the output we seek is a distinct coordinates representation of W , as discussed in Example 2.14.

Lemma 2.16. There exists a randomized algorithm Decompose(λ, R), which takes as input a partition λ of n with length ℓ and a zero-dimensional parametrization R of a set G ⊂ K ℓ ; it returns a symmetric representation of

E * λ (G). The expected runtime is O˜(D 2 n) operations in K, with D = deg(R) = |G|.
Proof. In the first step, we apply our algorithm Type Of Fiber from Lemma 2.11 where the input fiber is given not with coefficients in K, but as the points described by R. A general algorithmic principle, known as dynamic evaluation, allows us to do this as follows. Let R = ((q, v 1 , . . . , v ℓ ), µ), with q and the v i 's in K[y]. We then call Type Of Fiber with input coordinates (v 1 , . . . , v ℓ ), and attempt to run the algorithm over the residue class ring K[y]/q, as if q were irreducible.

If q is irreducible, K[y]/q is a field, and we encounter no problem. However, in general, K[y]/q is only a product of fields, so the algorithm may attempt to invert a zero-divisor. When this occurs, a "splitting" of the computation occurs. This amounts to discovering a non-trivial factorization of q. A direct solution then consists of running the algorithm again modulo the two factors that were discovered. Overall, this computes a sequence (R i , λ i , f i ) 1≤i≤N , where for i = 1, . . . , N, (i) R i = ((q i , v i,1 , . . . , v i,ℓ ), µ i ) is a zero-dimensional parametrization that describes a set F i ⊂ F . In addition F is the disjoint union of F 1 , . . . , F N ;

(ii) λ i is a partitition of n, of length ℓ i ;

(iii) f i is a sequence of ℓ i elements with entries in the residue class ring K[y]/q i ;

(iv) for any ε in F i , corresponding to a root τ of q i , Type Of Fiber(λ, ε) = (λ i , f i (τ )).

Since Type Of Fiber takes time O˜(n), this process takes time O˜(D 2 n), with D = deg(R).

The overhead O˜(D 2 ) is the penalty incurred by a straightforward application of dynamic evaluation techniques. For i = 1, . . . , N, let

V i = E -1 λ (F i ), so that W = S n (V )
is the union of the orbits W i = S n (V i ). Then, from (iv) above we see that all points in W i have type λ i and that

(W i ) ′ λ i is the set G i = {f i (τ ) | q i (τ ) = 0} ⊂ K ℓ i . Using the algorithm of [35, Proposition 1], we can compute a zero-dimensional parametrization S i of G i in time O˜(D 2 i n), with D i = deg(R i ). The total cost is thus O˜(D 2 n).
The λ i 's may not be pairwise distinct. Up to changing indices, we may assume that λ 1 , . . . , λ s are representatives of the pairwise distinct values among them. Then, for i = 1, . . . , s, we compute a zero-dimensional parametrization T i that describes the union of those Z(S j ), for j such that λ j = λ i . Using algorithm [START_REF] Poteaux | On the complexity of computing with zero-dimensional triangular sets[END_REF]Lemma 3], this takes a total of O˜(D 2 n) operations in K. Finally, we return (λ i , T i ) 1≤i≤s .

Algorithms for computing critical points

We can now turn to the main question in this article. Let f = (f 1 , . . . , f s ) be polynomials in K[x 1 , . . . , x n ] Sn , with s ≤ n, and with V = V (f ) ⊂ K n denoting the algebraic set defined by

f 1 = • • • = f s = 0. Given a polynomial φ in K[x 1 , . . . ,
x n ] Sn , we are interested in describing the algebraic set W = W (φ, f ) defined by the simultaneous vanishing of the polynomials

f 1 , . . . , f s , M s+1 (Jac(f , φ)) (11)
where M s+1 (Jac(f , φ)) is the set of (s + 1)-minors of the Jacobian matrix Jac(f , φ) ∈ K[x 1 , . . . , x n ] (s+1)×n . Equivalently, this is the set of all x in V at which Jac(f , φ) has rank less than s + 1.

If we assume that Jac(f ) has full rank s at any point of V , then V is smooth of codimension s (or empty) and W is the set of critical points of φ on it. However, most of our discussion can take place without this assumption. For the sake of simplicity, in any case, we will still refer to the solutions of ( 11) as critical points.

Description of the algebraic set W

Fundamental to our results is the fact that W is invariant under the action of the symmetric group. This follows from the next lemma, being a direct consequence of the chain rule. Lemma 3.1. Let g be in K[x 1 , . . . , x n ] and σ in S n . Then for k in {1, . . . , n}, we have

σ ∂g ∂x k = ∂(σ(g)) ∂x σ(k) . ( 12
)
Corollary 3.2. The algebraic set W is S n -invariant.

Proof. Let ξ be in W and σ be in S n . We need to show that σ(ξ) is in W , that is, f i (σ(ξ)) = 0 for all i and Jac(f , φ) has rank at most s at σ(ξ).

The first statement is clear, since ξ cancels f and f is S n -invariant. For the second claim, since all f i 's and φ are S n -invariant, Lemma 3.1 implies that the Jacobian matrix Jac(f , φ) at σ(ξ) is equal to (Jac(f , φ)(ξ))A -1 , where A is the matrix of σ. Therefore, as with Jac(f , φ)(ξ), it has rank at most s .

We remark that the proof of the corollary implies a slightly stronger property, which we already mentioned in the introduction: the system f 1 , . . . , f s , M s+1 (Jac(f , φ)) is globally invariant (that is, applying any σ ∈ S n permutes these equations, possibly changing signs). However, our algorithm does not use this fact directly.

The corollary above also implies that the discussion in Section 2.4 applies to W . In particular, for a partition λ of n, the sets W λ and W ′ λ of (10) are well-defined. In what follows, we fix a partition λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) of n and we let ℓ be its length; we explain how to compute a description of W ′ λ along the lines of Section 2.4. For this, we let Z 1 , . . . , Z r be the indeterminates associated to λ, as defined in Section 2.1, with Z i = z i,1 , . . . , z i,ℓ i . As in that section, we also write all indeterminates z 1,1 , . . . , z r,ℓr as z 1 , . . . , z ℓ . Definition 3.3. With λ and Z 1 , . . . , Z r as above, we define T λ , the K-algebra homomorphism

K[x 1 , . . . , x n ] → K[Z 1 , . . . , Z r ] mapping x 1 , . . . , x n to z 1,1 , . . . , z 1,1 n 1 , . . . , z 1,ℓ 1 , . . . , z 1,ℓ 1 n 1
. . . , z r,1 , . . . , z r,1 nr , . . . , z r,ℓr , . . . , z r,ℓr nr .

(

) 13
The operator T λ extends to vectors or matrices of polynomials entrywise.

We can now define

f [λ] = T λ (f ) = (f [λ] 1 , . . . , f [λ] s ) and J [λ] = T λ (Jac(f , φ)) = J [λ] i,j 1≤i≤s+1,1≤j≤n . (14)
Notice that for f in K[x 1 , . . . , x n ] Sn , and for any indices j, k in {1, . . . , n} for which T λ (x j ) = T λ (x k ), we have

T λ ∂f ∂x j = T λ ∂f ∂x k ; ( 15
)
this follows by applying Lemma 3.1 to f and the transposition (j k). Thus

T λ ∂f ∂x 1 , . . . , ∂f ∂x n = f [λ] 1,1 , . . . , f [λ] 1,1 n 1 , . . . , f [λ] 1,ℓ 1 , . . . , f [λ] 1,ℓ 1 n 1 , . . . , f [λ] r,1 , . . . , f [λ] r,1 nr , . . . , f [λ]
r,ℓr , . . . , f

[λ] r,ℓr nr , (16) where f
[λ] i,j are polynomials in the variables (Z 1 , . . . , Z r ).

Lemma 3.4. The columns of the transformed Jacobian matrix J [λ] have the form:

J [λ] = J [λ] 1,1 , . . . , J [λ] 1,1 n 1 , . . . , J [λ] 1,ℓ 1 , . . . , J [λ] 1,ℓ 1 n 1 , . . . , J [λ] r,1 , . . . , J [λ] r,1 nr , . . . , J [λ] r,ℓr , . . . , J [λ] r,ℓr nr , (17)
Proof. This follows directly from [START_REF] Faugère | Critical points and Gröbner bases: The unmixed case[END_REF], since (J

[λ] s+1,1 , . . . , J [λ] s+1,n ) = T λ ∂φ ∂x 1 , . . . , ∂φ ∂x n and (J [λ] i,1 , . . . , J [λ] i,n ) = T λ ∂f i ∂x 1 , . . . , ∂f i ∂x n
for i = 1, . . . , s, and all polynomials f 1 , . . . , f s , φ are in K[x 1 , . . . , x n ] Sn .

We will then let

G [λ] = [G [λ]
i,j ] 1≤i≤s+1,1≤j≤ℓ be the matrix with entries in K[Z 1 , . . . , Z r ] obtained from Jac(f , φ) by first applying T λ and then keeping only one representative among all repeated columns highlighted in the previous lemma.

Example 3.5. Let s = 1 and n = 5, so we consider two polynomials f 1 , φ in K[x 1 , . . . , x 5 ], and take λ = (1 1 2 2 ). Then

f [λ] 1 (z 1,1 , z 2,1 , z 2,2 ) = T λ (f 1 ) = f 1 (z 1,1 , z 2,1 , z 2,1 , z 2,2 , z 2,2 ),
and

G [λ] =   T λ ( ∂f 1 ∂x 1 ) T λ ( ∂f 1 ∂x 2 ) T λ ( ∂f 1 ∂x 4 ) T λ ( ∂φ ∂x 1 ) T λ ( ∂φ ∂x 2 ) T λ ( ∂φ ∂x 4 )   ∈ K[z 1,1 , z 2,1 , z 2,2 ] 2×3 .
It is easy to see that the polynomials f [λ] are S λ -invariant, where S λ is the permutation group S ℓ 1 × • • • × S ℓr introduced in the previous section. However, this is generally not the case for the entries of G [λ] . Lemma 3.6. Let g [λ] = (g

[λ] 1 , . . . , g [λ] ℓ ) be a row of G [λ] . Then (i) z i -z j divides g [λ] i -g [λ] j for 1 ≤ i < j ≤ ℓ; (ii) g [λ] is S λ -equivariant.
Proof. For the sake of definiteness, let us assume that g [λ] is the row corresponding to the gradient of f 1 , with the other cases treated similarly.

For statement (i), we start from indices i, j as in the lemma and let S be the Kalgebra homomorphism K[Z 1 , . . . , Z r ] → K[Z 1 , . . . , Z r ] that maps z i to z j , leaving all other variables unchanged. Let u, v in {1, . . . , n} be indices such that g

[λ] i = T λ (∂f 1 /∂x u ) and g

[λ] j = T λ (∂f 1 /∂x v ) and σ ∈ S n the transposition (u v). From Lemma 3.1, we have that σ(∂f 1 /∂x u ) = ∂f 1 /∂x v and applying S • T λ gives S(T λ (σ(∂f 1 /∂x u ))) = S(T λ (∂f 1 /∂x v )). For any h ∈ K[x 1 , . . . , x n ] we have, by construction, S(T λ (σ(h))) = S(T λ (h)). Applying this on the left-hand side of the previous equality gives S(g

[λ] i ) = S(g [λ] j ). As a result, z i -z j divides g [λ] i -g [λ]
j , as claimed. For statement (ii), we take indices k in {1, . . . , r} and j, j ′ in {1, . . . , ℓ k }. We let σ ∈ S λ be the transposition that maps (k, j) to (k, j ′ ) and prove that σ(g

[λ] k,j ) = g [λ]
k,j ′ . As before, there exist indices u, v in {1, . . . , n} such that g

[λ] k,j = T λ (∂f 1 /∂x u ) and g [λ] k,j ′ = T λ (∂f 1 /∂x v ).
Without loss of generality, assume that u and v are the smallest such indices. Then T λ maps x u , . . . , x u+ℓ k -1 to z k,j and x v , . . . , x v+ℓ k -1 to z k,j ′ .

Let τ ∈ S n be permutation that permutes (u, . . . , u+ℓ k -1) with (v, . . . , v +ℓ k -1). From Lemma 3.1, we get τ (∂f

1 /∂x v ) = ∂f 1 /∂x u . Then T λ (τ (∂f 1 /∂x u )) = T λ (∂f 1 /∂x v ) = g [λ]
k,j ′ . By construction, the left-hand side is equal to σ(T λ (∂f 1 /∂x u )), that is, σ(g

[λ]
k,j ). Lemma 3.6 implies that we can apply Algorithm Symmetrize from Section 2.3 to each row of G [λ] . The result is a polynomial matrix H [λ] in K[Z 1 , . . . , Z r ], whose rows are all S λ -equivariant, and such that H [λ] = G [λ] U [λ] , for some polynomial matrix U [λ] in K[Z 1 , . . . , Z r ] ℓ×ℓ . Applying Algorithm Symmetric Coordinates from Lemma 2.2 to the entries of both f [λ] and H [λ] gives polynomials f [λ] and a matrix H[λ] , all with entries in K[e 1 , . . . , e r ], with variables e i = e i,1 , . . . , e i,ℓ 1 for all i, and such that f

[λ] = f [λ] (η 1 , . . . , η r ) and H [λ] = H[λ] (η 1 , . . . , η r ).
The following summarizes the main properties of this construction. For the definitions of the sets C λ , C strict λ , the mapping E λ and the open set O λ ⊂ K ℓ , see Section 2.4. Proposition 3.7. Let λ be a partition of n of length ℓ.

(i) If ℓ ≤ s, then E λ (W ∩ C λ ) is the zero-set of f [λ] in K ℓ . (ii) If ℓ > s, then W ′ λ = E λ (W ∩ C strict λ ) is the zero-set of f [λ] and all (s + 1)-minors of H[λ] in O λ ⊂ K ℓ .
Proof. Let ξ be in the set C λ defined in Section 2.4, and write

ξ = ξ 1,1 , . . . , ξ 1,1 n 1 , . . . , ξ 1,ℓ 1 , . . . , ξ 1,ℓ 1 n 1
, . . . , ξ r,1 , . . . , ξ r,1 nr , . . . , ξ r,ℓr , . . . , ξ r,ℓr nr .

Set ζ = (ξ 1,1 , ξ 1,2 , . . . , ξ r,ℓr ) ∈ K ℓ and ε = E λ (ξ) ∈ K ℓ . By definition, we have f (ξ) = f [λ] (ζ) and Jac(f , φ)(ξ) = J [λ] (ζ). Thus, ξ is in W ∩ C λ if and only if it cancels f and Jac(f , φ) has rank at most s at ξ, that is, if f [λ] (ζ) = 0 and J [λ] (ζ) has rank at most s. The point ξ is in W ∩ C strict λ
if all the entries of ζ are also pairwise distinct. In addition, we have f [λ] (ζ) = f [λ] (ε) and, by construction, rank(J [λ]

(ζ)) = rank(G [λ] (ζ)). If ℓ ≤ s then, since G [λ] has ℓ columns, we see that ξ is in W ∩ C λ if and only if ε = E λ (ξ) cancels f [λ] . Since E λ : C λ → K ℓ is onto, this implies our first claim.
Suppose further that ξ is in C strict λ , so that ε is in O λ . From Proposition 2.4, we have

H [λ] = G [λ] U [λ] .
Our assumption on ξ implies that U [λ] (ζ) is invertible, so that G [λ] and H [λ] have the same rank at ζ. Finally, we have

H [λ] (ζ) = H[λ] (ε). All this combined shows that ξ is in W ′ λ = E λ (W ∩ C strict λ ) if

The Critical Points Per Orbit algorithm

The main algorithm of this paper is Critical Points Per Orbit which takes as input symmetric f = (f 1 , . . . , f s ) and φ in K[x 1 , . . . , x n ] and, if finite, outputs a symmetric representation of the critical point set W = W (φ, V (f )). Using our notation from Section 2, this means that we want to compute zero-dimensional parametrizations of

W ′ λ = E λ (W ∩ C strict λ
), for all partitions λ of n for which this set is not empty. The algorithm is based on Proposition 3.7, with a minor modification, as we will see that it is enough to consider partitions of n of length ℓ either exactly equal to s, or at least s + 1.

For any partition λ, we first need to transform f and φ, in order to obtain the polynomials in Proposition 3.7. Proof. In the first case, applying T λ to f takes linear time in the number of monomials O(n n+d d ) and gives us f [λ] . We then invoke Symmetric Coordinates(λ, f [λ] ), using Lemma 2.2, in order to obtain f [λ] with the cost being O˜(n n+d d ) 2 operations in K. In the second case, we obtain f [λ] as above. We also compute the matrix Jac(f , φ), which takes O(n 2 n+d d ) operations. For the same cost, we apply T λ to all its entries and remove redundant columns, as specified in Lemma 3.4, so as to yield the matrix G [λ] . We then apply Algorithm Symmetrize from Proposition 2.7 to all rows of G [λ] , which takes O˜(n 4 n+d d ) operations, and returns H [λ] . Finally, we apply Symmetric Coordinates to all entries of this matrix which gives H[λ] and takes O˜(n 2 n+d d 2 ) operations in K.

At the core of the algorithm, we need a procedure for finding isolated solutions of certain polynomial systems. In our main algorithm, we solve such systems using procedures called Isolated Points(g) and Isolated Points(g, H, k). Given polynomials g, the former returns a zero-dimensional parametrization of the isolated points of V (g). The latter takes as input polynomials g, a polynomial matrix H and an integer k, and returns a zero-dimensional parametrization of the isolated points of V (g, M k (H)), where M k (H) denotes the set of kminors of H (note that the former procedure can be seen as a particular case of the latter, where we take H to be a matrix with no row and k = -1). To establish correctness of the main algorithm, any implementation of these procedures is suitable.

Apart from the subroutines discussed above and the function Decompose from Lemma 2.16, our algorithm also requires a procedure Remove Duplicates(S). This inputs a list S = (λ i , R i ) 1≤i≤N , where each λ i is a partition of n and R i a zero-dimensional parametrization. As all λ i 's may not be distinct in this list, this procedure removes pairs (λ i , R i ) from S so as to ensure that all resulting partitions are pairwise distinct (the choice of which entries to remove is arbitrary; it does not affect correctness of the overall algorithm). Proposition 3.9. Algorithm Critical Points Per Orbit is correct.

Proof. The goal of the algorithm is to compute zero-dimensional representations of

W ′ λ = E λ (W ∩ C strict λ
) for all partitions λ of n for which this set is not empty. To understand the first loop, recall first that W is assumed to be finite. Hence this also holds for all W ∩ C λ , and thus for all E λ (W ∩ C λ ). As a result, for λ of length s, Proposition 3.7(i) implies that at Step 2b , Isolated Points( fλ ) returns a zero-dimensional parametrization of G := E λ (W ∩ C λ ). Then, we recall from Lemma 2.16 that the output of Decompose(λ, R λ ) is a symmetric representation of E * λ (G). Note that the latter set is the orbit of W ∩ C λ , that is, the set of all orbits contained in W whose type λ ′ satisfies λ ′ ≥ λ. Taking into account all partitions λ of length s, the set of partitions λ ′ ≥ λ covers all partitions of length ℓ ∈ {1, . . . , s}, so that at the end of Step 2, we have zero-dimensional Algorithm 1 Critical Points Per Orbit(f , φ)

Input: f = (f 1 , . . . , f s ) and φ in K[x 1 , . . . , x n ] Sn such that W = W (φ, V (f )) is finite. Output: A symmetric representation of W . 1. S = [ ] 2. For λ ⊢ n of length s (a) f [λ] = Prepare F(f , λ) (b) R λ = Isolated Points( f [λ] ) (c) append the output of Decompose(λ, R λ ) to S 3. For λ ⊢ n of length in {s + 1, . . . , n} (a) f [λ] , H[λ] = Prepare F H(f , φ, λ) (b) R λ = Isolated Points( f [λ] , H[λ] , s + 1) (c) (λ i , R i ) 1≤i≤N = Decompose(λ, R λ ) (d) append (λ i 0 , R i 0 ) to S, where i 0 is such that λ i 0 = λ, if such an i 0 exists 4. Return Remove Duplicates(S) parametrizations of W ′
λ for all partitions of length ℓ ∈ {1, . . . , s} (with possible repetitions). Calling Remove Duplicates(S) will remove any duplicates among this list.

The second loop deals with partitions λ of length at least s + 1. Since we assume that W is finite, W ′ λ is finite for any such λ. Proposition 3.7(ii) then implies that the points in W ′ λ are isolated points of the zero-set of f [λ] and of the (s + 1)-minors of H[λ] . As a result, W ′ λ is a subset of Z(R λ ), for R λ computed in Step 3b with all other points in Z(R λ ) corresponding to points in W with type λ ′ > λ. In particular, after the call to Decompose, it suffices to keep the entry in the list corresponding to the partition λ, to obtain a description of W ′ λ .

Cost of the Critical Points Per Orbit Algorithm

In this section we provide a complexity analysis of our Critical Points Per Orbit algorithm and hence also complete the proof of Theorem 1.1. At the core of the Critical Points Per Orbit algorithm is a procedure, Isolated Points. Recall that on input polynomials g, a polynomial matrix H and an integer k, it returns a zerodimensional parametrization of the isolated points of V (g, M k (H)), where M k (H) denotes the set of k-minors of H. We apply this procedure to polynomials with entries in K[e 1 , . . . , e r ] = K[e 1,1 , . . . , e 1,ℓ 1 , e 2,1 , . . . , e 2,ℓ 2 , . . . , e r,1 , . . . , e r,ℓr ].

Rather than using classical methods for solving these polynomial systems, we use the symbolic homotopy method for weighted domains given in [START_REF] Labahn | Homotopy techniques for solution of sparse determinantal ideals[END_REF], as this algorithm is the best suited to handle a weighted-degree structure exhibited by such systems. Indeed, the polynomial ring arising from an orbit parameter λ, K[e 1 , . . . , e r ], is obtained through a correspondence between the variable e i,k and the elementary symmetric polynomial η i,k (x j 1 , . . . , x jm ), for certain indices j 1 , . . . , j m . More precisely, for any f in K[Z 1 , . . . , Z r ] S λ , let f be the polynomial in K[e 1 , . . . , e r ] satisfying f (Z 1 , . . . , Z r ) = f (η 1 , . . . , η r ), with η i = (η i,1 , . . . , η i,ℓ i ) for all i. Since each η i,k has degree k, it is natural to assign a weight k to variable e i,k , so that the weighted degree of f equals the degree of f . Our vector of variable weights is then is w = (1, . . . , ℓ 1 , 1, . . . , ℓ 2 , . . . , 1, . . . , ℓ r ).

Solving weighted determinantal systems

In this section, we briefly review the algorithm for solving determinantal systems over a ring of weighted polynomials. Suppose we work with polynomials in

K[Y ] = K[y 1 , . . . , y m ],
where each variable y i has weight w i ≥ 1 (denoted by wdeg(y i ) = w i ). The weighted degree of a monomial y α 1 1 • • • y αm m is then m i=1 w i α i , and the weighted degree of a polynomial is the maximum of the weighted degree of its terms with non-zero coefficients. The weighted column degrees of a polynomial matrix is the sequence of the weighted degrees of its columns, where the weighted degree of a column is simply the maximum of the weighted degrees of its entries.

Let f = (f 1 , . . . , f τ ) be a sequence of polynomials in K[Y ] and G = [g i,j ] ∈ K[Y ] p×q a matrix of polynomials such that p ≤ q and m = q -p + τ + 1, and let V p (G, f ) denote the set of points in K at which all polynomials in f and all p-minors of G vanish. In [START_REF] Labahn | Homotopy techniques for solution of sparse determinantal ideals[END_REF], a symbolic homotopy algorithm for weighted domains is presented which constructs a symbolic homotopy from a generic start system to the system defining V p (G, f ) and then uses this to efficiently determine the isolated points of V p (G, f ).

The main theorem of [START_REF] Labahn | Homotopy techniques for solution of sparse determinantal ideals[END_REF], in the special case of weighted polynomial rings, is given in terms of a number of parameters. Let (γ 1 , . . . , γ τ ) be the weighted degrees of (f 1 , . . . , f τ ), let (δ 1 , . . . , δ q ) be the weighted column degrees of G, let d be the maximum of the degrees (in the usual sense) of all f , G and set

Γ = m 2 m + d m + m 4 q p .
The following quantities are all related to the degrees of some geometric objects present in the algorithm. We define

c = γ 1 • • • γ τ • η m-τ (δ 1 , . . . , δ q ) w 1 • • • w m and e = (γ 1 + 1) • • • (γ τ + 1) • η m-τ (δ 1 + 1, . . . , δ q + 1) w 1 • • • w m ,
where where η n-s is the elementary symmetric polynomial of degree n -s. For a subset i = {i 1 , . . . , i m-τ } ⊂ {1, . . . , q}, we further let (d i,1 , . . . , d i,m ) denote the sequence obtained by sorting (γ 1 , . . . , γ τ , δ i 1 , . . . , δ i m-τ ) in non-decreasing order, and we write

κ i = max 1≤k≤m (d i,1 • • • d i,k w k+1 • • • w m ) and κ = i={i 1 ,...,i m-τ }⊂{1,...,q} κ i . (18)
Note that without loss of generality, in these equations, we may also assume that the weights w 1 , . . . , w m are reordered to form a non-decreasing sequence.

Theorem 4.1. [31, Theorem 5.3] Let G be a matrix in K[Y] p×q and f = (f 1 , . . . , f τ ) be polynomials in K[Y] such that p ≤ q and m = q -p + τ + 1. There exists a randomized algorithm which takes G and f as input and computes a zero-dimensional parametrization of these isolated solutions using

O˜ c(e + c 5 ) + d 2 κ w 1 • • • w m 2 m 4 Γ operations in K.
Moreover, the number of solutions in the output is at most c.

When there is no matrix G, so τ = m, then the runtimes reported above remain the same with the term Γ becoming Γ = m 2 m+d m . In this case, the term κ is simply equal to

κ = max 1≤k≤m (γ 1 • • • γ k w k+1 • • • w m ),
assuming that the degrees γ 1 , . . . , γ k are given in nondecreasing order.

We finish this subsection with an observation in those cases with m > q -p + τ + 1.

Remark 4.2. Note that when m > q -p + τ + 1, then there are no isolated points in V p (G, f ). Indeed if we let I ⊂ K[Y] be the ideal generated by the p-minors of G then a result due to Eagon and Northcott [10, Section 6] implies that all irreducible components of V (I) have codimension at most q -p + 1. By Krull's theorem the irreducible components of V p (G, f ) = V (I + f 1 , . . . , f τ ) then have codimension at most q -p + 1 + τ . This implies that the irreducible components of

V p (G, f ) in K m have dimension at least m -(q -p + τ + 1),
which is positive when m > q -p + τ + 1.

The complexity of the Isolated Points procedure

Estimating the runtimes for the Isolated Points algorithms follows from Theorem 4.1, for the weighted domains associated to various partitions of n. Thus we let λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) be a partition of length ℓ, with ℓ ≥ s.

The parameters that appear in Theorem 4.1 can be determined as follows. The weights of variables (e 1 , . . . , e r ) are w = (1, . . . , ℓ 1 , . . . , 1, . . . , ℓ r ). For i = 1, . . . , s, the weighted degree of f [λ] i is the same as the degree of f

[λ] i
and so is at most d. For j = 1, . . . , ℓ, the weighted column degree of the jth column of H[λ] is at most δ j = d -1 -ℓ + j (note that all entries of the Jacobian matrix of f , φ have degree at most d -1; then apply Proposition 2.4). In particular, if ℓ > d, then all entries on the j-th column of H[λ] equal zero for j = 1, . . . , ℓ -d. Finally, in what follows, we let

Γ = n 2 n + d d + n 4 n s + 1 .
Partitions of length s. We recall that when the length ℓ of the partition λ equals s, we do not need to deal with a matrix H[λ] . In this situation, one only needs to compute the isolated points of V ( f [λ] ). Consider such a partition λ = (n ℓ 1 1 n ℓ 2 2 . . . n ℓr r ) and the corresponding variables (e 1 , . . . , e r ), with wdeg(e i,k ) = k for all i = 1, . . . , r and k = 1, . . . , ℓ i . We make the following claim: if there exists i such that ℓ i > d, then there is no isolated point in V ( f [λ] ). Indeed, in such a case, variable e i,ℓ i does not appear in f [λ] , for weighted degree reasons, so that the zero-set of this system is invariant with respect to translations along the e i,ℓ i axis. In particular, it admits no isolated solution.

Therefore we can suppose that all ℓ i 's are at most d. In this case, the quantities c, e, κ used in Theorem 4.1 become respectively

c λ = d s w λ , e λ = n(d + 1) s w λ , κ λ = d s = w λ c λ , with w λ = ℓ 1 ! • • • ℓ r !. In this case Theorem 4.1 implies that V ( f [λ]
) contains at most c λ isolated points, and that and one can compute all of them using

O˜ c λ (e λ + c 5 λ ) + d 2 c 2 λ n 4 Γ λ ⊂ O˜ d 2 c λ (e λ + c 5 λ )n 4 Γ operations in K.
Partitions of length greater than s. For a partition λ of length ℓ greater than s, we have to take into account the minors of the matrix H[λ] . Note that the assumptions of Theorem 4.1 are satisfied: the matrix H[λ] is in K[e 1 , . . . , e r ] (s+1)×ℓ , with ℓ ≥ s + 1, and we have s equations f [λ] in K[e 1 , . . . , e r ], so the number of variables ℓ does indeed satisfy

ℓ = ℓ -(s + 1) + s + 1. We claim that if ℓ > d, then the algebraic set V s+1 ( H[λ] , f [λ]
) does not have any isolated point. Indeed, in this case, we pointed out above that the columns of indices 1 to ℓ-d in H[λ] are identically zero. After discarding these zero-columns from H[λ] , we obtain a matrix

L [λ] of dimension (s + 1) × d such that V s+1 ( H[λ] , f [λ] ) = V s+1 (L [λ] , f [λ]
), and using Remark 4.2 with p = s + 1, q = d, τ = s and m ≥ ℓ shows that this algebraic set has no isolated points.

Thus, let us now assume that ℓ ≤ d. The matrix H[λ] has weighted column degrees (δ 1 , . . . , δ ℓ ) = (d -ℓ, . . . , d -1), whereas the weighted degrees of all polynomials in f [λ] is at most d. To estimate the runtime of Isolated Points( H[λ] , f [λ] ), we will need the following property.

Lemma 4.3. Let κ be defined as in [START_REF] Gathen | Modern Computer Algebra[END_REF] with m = ℓ, τ = s, p = s + 1, q = ℓ, (δ 1 , . . . , δ ℓ ) = (d -1 -ℓ, . . . , d -1), and (γ 1 , . . . , γ s ) = (d, . . . , d). Then, for partitions of length ℓ at most d, one has κ = d s η ℓ-s (d -1, . . . , d -ℓ).

Proof. Without loss of generality, we reorder the weights w as

w ′ = (w ′ 1 , . . . , w ′ ℓ ) such that w ′ 1 ≤ • • • ≤ w ′ ℓ . Take i = (i 1 , .
. . , i ℓ-s ) ⊂ {1, . . . , ℓ}, and let d i = (d i,1 , . . . , d i,ℓ ) be the sequence obtained by reordering (d, . . . , d, δ i 1 , . . . , δ i ℓ-s ) in non-decreasing order; we first compute the value of κ i from [START_REF] Gathen | Modern Computer Algebra[END_REF]. If d i,1 = 0 (which can happen only if ℓ = d), then κ i = 0. Otherwise, the sequence d i starts with d i,1 ≥ 1 and increases until index ℓ -s, after which it keeps the value d. On the other hand, the ordered sequence of weights never increases by more than 1, so that for all k = 1, . . . , ℓ, we have w ′ k ≤ d i,k . In this case,

κ i = max 1≤k≤ℓ (d i,1 • • • d i,k w k+1 • • • w m ) = d i,1 • • • d i,ℓ = d s δ i 1 • • • δ i ℓ-s ;
note that this equality also holds if d i,1 = 0, since then both sides vanish. Since κ = i={i 1 ,...,i ℓ-s }⊂{1,...,q} κ i , we get κ = i={i 1 ,...,i ℓ-s }⊂{1,...,ℓ}

d s δ i 1 • • • δ i ℓ-s = d s η ℓ-s (d -1, . . . , d -ℓ). (19)
as claimed.

The procedure Isolated Points f For the remaining operations, the total cost of Prepare F and Prepare F H is

n 4 λ⊢n,ℓ λ ≥s n + d d 2 . Since n+d d ≤ (n + 1) n+d-1 d
, the binomial term in the sum is in O(n 2 c 2 ), so the total is O(n 5 c 3 ), and can be neglected. Similarly, the cost of Remove Duplicates is negligible. Therefore, the total complexity of Critical Points Per Orbit is then in

O˜ n 11 d 6s+2 n + d d 6 n + d d + n s + 1 ⊂ d s n + d d n s + 1 O(1)
.

Finally, the total number of solutions reported by our algorithm is at most λ⊢n,ℓ λ ≥s c λ , which itself is at most c.

Experimental results

In this section, we report on an implementation and set of experimental runs supporting the results in this paper. We compare our Critical Points Per Orbit algorithm from Section 3.2 with a naive algorithm which computes a zero-dimensional parametrization of V (I), where I is the ideal generated by f and the (s + 1)-minors of Jac(f , φ). Since no implementation of the weighted sparse determinantal homotopy algorithm is available at the moment, both algorithms use Gröbner bases computations to solve polynomial systems. Furthermore, using Gröbner bases computations is sufficient to see the advantage of our algorithm when the symmetric structure is exploited in our algorihm.

Our experiments are run using the Maple computer algebra system running on a computer with 16 GB RAM; the Gröbner basis computation in Maple uses the implementation of the F 4 and FGLM algorithms from the FGb package [START_REF] Faugère | FGb: A Library for Computing Gröbner Bases[END_REF]. The symmetric polynomials f and φ are chosen uniformly at random in K[x 1 , . . . , x n ], with K = GF(65521), and have the same degree n as the number of variables, that is, deg

(f 1 ) = • • • = deg(f s ) = deg(φ) = n; the number s of equations f ranges from 2 to n -1.
Our experimental results support the theoretical advantage gained by exploiting the symmetric structure of the input polynomials. In Table 1, we first report the number of points, denoted by D, that we compute using our algorithm; that is, D is the sum of the degrees deg(R λ ) that we obtain for all partitions λ of length at least s. The next column is ℓ λ ≥s c λ , which is an upper bound on D (here, c λ is as in Subsection 4.2); as we can see, this bound is quite sharp in general. We next give the upper bound c from (2), which we proved in Lemma 4.4. While this bound is sufficient to prove asymptotic results (for fixed input degree, for instance, see the discussion in the introduction), we see that it is far from sharp.

Finally, we give the number of points deg(I) computed by the naive algorithm, together with the upper bound c from (3); in some cases, we did not complete computations with the naive algorithm, so deg(I) was unavailable. We see that in all cases, the output of our algorithm is significantly smaller than the one from the direct approach. In Table 2, we report on our timings in a detailed fashion. Here, we give the time needed to compute the zero-dimensional representations deg(R λ ) obtained by our algorithm, together with their degrees; Time(total) denotes the total time spent in our algorithm. On the other hand, Time(naive) is the time to compute a zero-dimensional parametrization for the algebraic set V (I) using the naive algorithm. Experiments are stopped once the computation has gone past 24 hours, with the corresponding time marked with a dash.

In our experiments, the output R λ was always empty for partitions of length less than s. Indeed, for any partition λ of length at most s -1,

Z(R λ ) = V ( f [λ] 1 , . . . , f [λ] s ), where the f [λ]
i are s polynomials in less than s variables derived from the input f . Since the polynomials f are chosen at random, the evaluated block symmetric polynomials f

[λ] 1 , . . . , f [λ]
s are generic. Using [31, Proposition 2.1.(ii)] or modifiying slightly the proof of [31, Proposition 4.5], we indeed expect Z(R λ ) to be empty for such partitions λ of length less than s. However, we point out that this output can be non-trivial in the general, non-generic case.

Conclusion and topics for future research

In this paper we have provided a new algorithm for efficiently describing the critical point set of a function φ a variety V (f ) with φ and the defining functions of the variety all symmetric. The algorithm takes advantage of the symmetries and lower bounds for describing the generators of the set of critical points and as a result is more efficient than previous approaches.

When

f = (f 1 , . . . , f s ) ⊂ R[x 1 , . . . , x n ],
with R is a real field, then computing the critical points of polynomial maps restricted to V (f ) finds numerous applications in computational real algebraic geometry. In particular such computations provide an effective Morse-theoretic approach to many problems such as real root finding, quantifier elimination or answering connectivity queries (see [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]). We view the complexity estimates in this paper as a possible first step towards better algorithms for studying real algebraic sets defined by S n -invariant polynomials.

For instance, let d be the maximum degree of the entries in f = (f 1 , . . . , f s ) and assume that f generates an (n -s)-equidimensional ideal whose associated algebraic set is smooth. Then under these assumptions, we observe that the set W (φ u , V (f )) with

φ u : (x 1 , . . . , x n ) → (x 1 -u) 2 + • • • + (x n -u) 2
and u ∈ R, has a non-empty intersection with all connected components of V (f ) ∩ R n . Hence, when W (φ u , f ) is finite for a generic choice of u, then one can use our algorithm to decide whenever V (f ) ∩ R n is empty. This is done in time polynomial in d s , n+d d , n s+1 . In such cases, for d, s fixed, we end up with a runtime which is polynomial in n as in [START_REF] Timofte | On the positivity of symmetric polynomial functions.: Part i: General results[END_REF][START_REF] Riener | On the degree and half-degree principle for symmetric polynomials[END_REF][START_REF] Riener | Symmetric semi-algebraic sets and non-negativity of symmetric polynomials[END_REF]. These latter references are restricted to situations when d < n is fixed. If now, one takes families of systems where d = n and s is fixed, we obtain a runtime which is polynomial in 2 n . This is an exponential speed-up with the best previous possible alternatives which run in time 2 O(n log(n)) as in for example [2, Chap. 13] (but note that these algorithms are designed for general real algebraic sets). To prove statement [START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF] we use decreasing induction on t = j, . . . , 1. The statement is true when t = j since in this case p τ k +j,j = τ k +j i=τ k +1 q {i,τ k +j+1,...,τr} , which is symmetric in z :j by Lemma A.2, while each summand q {i,τ k +j+1,...,τr} is symmetric in z j+1: by Lemma A.1. Assume now that ( 22) is true for some index t in {2, . . . , j}; we show that it also holds for t -1. That is, we have p τ k +j,t is block symmetric in z :t and z t+1: and need to show that p τ k +j,t-1 is block symmetric in z :t-1 and z t: . From Lemma A.2, we have that

n s Partition(λ) Time(R λ ) deg(R λ ) ⌈c λ ⌉ Time(total) Time(naive) deg(I) 4 2 λ = (1 4 ) λ = (1 2 2 1 ) λ = (2 2 ) λ = (1 1 3
λ = (1 5 ) λ = (1 3 2 1 ) λ = (1 2 3) λ = (1 1 2 2 ) λ = (1 1 4 1 ) λ = (2
5 3 λ = (1 5 ) λ = (1 3 2 1 ) λ = (1 2 3) λ = (1 1 15575
λ = (1 6 ) λ = (1 4 2 1 ) λ = (1 3 3) λ = (1 2 2 2 ) λ = (2 3 ) λ = (1 2 4 1 ) λ = (1 1 2 1 3 1 ) λ = (1 1 5 1 ) λ = (2 1 4 1 ) λ = ( 3
3 λ = (1 6 ) λ = (1 4 2 1 ) λ = (1 3 3) λ = (1 2 2 2 ) λ = (2 3 ) λ = (1 2 4 1 ) λ = (1 1 2 1 3
τ k +t-1
i=τ k +1 q {i,τ k +t,...,τr} is symmetric in z :t-1 . Furthermore, from our induction hypothesis, the polynomial p τ k +j,t is symmetric in z :t-1 , while η j-t+1 (z τ k +t+1 , . . . , τ k+1 ) depends only on z t: . Thus, in view of (21), we see that p τ k +j,t-1 is symmetric in z :t-1 . It remains to prove that it is also symmetric in z t: . We will prove this by showing σ(p τ k +j,t-1 ) = p τ k +j,t-1 for any σ = (τ k + t + 1, τ k + ǫ) with ǫ ∈ {t, t + 2, . . . , ℓ k+1 }. For any such σ with t + 2 ≤ ǫ ≤ ℓ k+1 , our induction hypothesis implies that σ(p τ k +j,t ) = p τ k +j,t , while σ(η j-t+1 (z τ k +t+1 , . . . , τ k+1 )) = η j-t+1 (z τ k +t+1 , . . . , τ k+1 ) and σ q {i,τ k +t,...,τr} = q {i,τ k +t,...,τr} hold for all i. Together with (21), we get σ(p τ k +j,t-1 ) = p τ k +j,t-1 . Finally, if σ = (τ k + t + 1, τ k + t), then we have σ(η j-t+1 (z τ k +t+1 , . . . , τ k+1 )) = η j-t+1 (z τ k +t , z τ k +t+2 , . . . , τ k+1 ) and σ q {i,τ k +t,...,τr} = q {i,τ k +t,...,τr} for all i = τ k + 1, . . . , τ k + t -1. Notice that

η j-t+1 (z τ k +t , z τ k +t+2 , . . . , τ k+1 )-η j-t+1 (z τ k +t+1 , . . . , τ k+1 ) = (z τ k +t -z τ k +t+1 ) η j-t (z τ k +t+2 , . . . , z τ k+1 ). Therefore, σ(p τ k +j,t-1 ) -p τ k +î,t-1 = σ(p τ k +j,t ) -p τ k +j,t + (z τ k +t -z τ k +t+1 ) η j-t (z τ k +t+2 , . . . , z τ k+1 ) τ k +t-1 i=τ k +1 q {i,τ k +t,...,τr} = σ(p τ k +j,t ) -p τ k +j,t + η j-t (z τ k +t+2 , . . . , z τ k+1 ) τ k +t-1 i=τ k +1 (q {i,τ k +t+1,τ k +t+2,...,τr} -q {i,τ k +t,τ k +t+2,...,τr} ) , (23)
where the last equality follows from the definition of divided differences. In particular,

σ(p τ k +j,j-1 ) -p τ k +j,j-1 = σ(p τ k +j,j ) -p τ k +j,j + τ k +j-1 i=τ k +1
(q {i,τ k +j+1,...,τr} -q {i,τ k +j,τ k +j+2,...,τr} ).

In addition, since p τ k +j,j = τ k +j i=τ k +1 q {i,τ k +j+1,...,τr} , then when σ = (τ k + j + 1, τ k + j), we have σ(p τ k +j,j ) -p τ k +j,j = τ k +j-1 i=τ k +1 (q {i,τ k +j,τ k +j+2,...,τr} -q {i,τ k +j+1,...,τr} ). This implies that σ(p τ k +j,j-1 ) -p τ k +j,j-1 = 0.

When t ≤ j -1, from (21), taken at index t + 1, if σ = (τ k + t + 1, τ k + t), we also have

σ(p τ k +j,t ) = σ(p τ k +j,t+1 ) + η j-t (z τ k +t+2 , . . . , z τ k+1 ) τ k +t-1 i=τ k +1
q {i,τ k +t,τ k +t+2,...,τr} + q {τ k +t,τ k +t+1,...,τ k+1 } .

Then, by subtraction:

σ(p τ k +j,t ) -p τ k +j,t = σ(p τ k +j,t+1 ) -p τ k +j,t+1 + η j-t (z τ k +t+2 , . . . , z τ k+1 )

τ k +t-1 i=τ k +1
(q {i,τ k +t,τ k +t+2,...,τr} -q {i,τ k +t+1,...,τr} ) and so σ(p τ k +j,t+1 ) -p τ k +j,t+1 =σ(p τ k +j,t ) -p τ k +j,t + η j-t (z τ k +t+2 , . . . , z τ k+1 )

τ k +t-1 i=τ k +1
(q {i,τ k +t+1,...,τr} -q {i,τ k +t,τ k +t+2,...,τr} ) .

Combining ( 23) and ( 24) gives σ(p τ k +j,t-1 )-p τ k +j,t-1 = σ(p τ k +j,t+1 )-p τ k +j,t+1 . By induction, we have that p τ k +j,t+1 is symmetric in z :t+1 and so σ(p τ k +j,t+1 ) = p τ k +j,t+1 for σ = (τ k + t + 1, τ k + t) which in turn implies that σ(p τ k +j,t-1 ) = p τ k +j,t-1 . This gives our result.

B Proof of Proposition 2.5

Define the row vector h = h τ 0 +1 , . . . , h τ 1 , . . . , h τ r-1 +1 , . . . , h τr where, for k = 0, . . . , r -1 and j = 1, . . . , ℓ k+1 ,

h τ k +j = τ k +j i=τ k +1
q {i,τ k +j+1,...,τr} .

Then for all i = 1, . . . , m, k = 0, . . . , r -1, p τ k +ℓ k+1 = h τ k +ℓ k+1 , and for j = 1, . . . , ℓ k+1 -1, p τ k +j = j s=1 η j-s (z τ k +s+2 , . . . , z τ k+1 ) h τ k +s .

Then h = p M, where we recall that M is the block-diagonal matrix with blocks M 1 , . . . , M r where

M k+1 =          
0 0 0 • • • 0 1           .
Then det(M) = 1 and N = M -1 is also a polynomial matrix in K[Z] with det(N) = 1. We construct a matrix J which defines the column operations converting h into q as follows. Recall that for k = 0, . . . , r -1 and j = 1, . . . , ℓ k+1 , we have defined the following τ r × τ r polynomial matrices. Set B τ 0 +1 = I τr , C τ 0 +1 = I τr , D τ 0 +j = I τr , and We will prove that this matrix satisfies q = h J. Note first that, for k = 0, . . . , r -1 and j = 1, . . . , ℓ k+1 we have det(B τ k +j ) = det(E k,j ) = -1, det(C τ k +j ) = det(F k,j ) = (z τ k +j -z t ) = α∆ for some α ∈ K =0 .

Define U = N J. Then p = q U, and det(U) is a unit in K[Z 1 , . . . , Z r , 1/∆], as claimed. It remains to prove q = h J. For s = 0, . . . , τ r , define q s = q {1,s+1,...,τr} . . . q {s,s+1,...,τr} h s+1 . . . h τr , so that for s = 0 we have q 0 = h, whereas for s = τ r we have q τr = q. We prove the following: for k in {0, . . . , r -1} and j in {1, . . . , ℓ k },

q τ k +j = q τ k +j-1 B τ k +j C τ k +j D τ k +j . (26)
Our claim q = h J then follows from a direct induction, taking into account the values of q 0 and q τr given above.

Take k in {0, . . . , r -1} and j in {1, . . . , ℓ k }. Right-multiplying q τ k +j-1 by B τ k +j only affects the entry at index τ k + j. It replaces h τ k +j by j-1 i=1 q {τ k +i,τ k +j,...,τr} (z τ k +j -z τ k +i ) -h τ k +j .

Using the defining relation of divided differences, we get q {τ k +i,τ k +j,...,τr} (z τ k +j -z τ k +i ) = q {τ k +i,τ k +j+1,...,τr} -q {τ k +j,τ k +j+1,...,τr} .

With the definition of h τ k +j in [START_REF] Heintz | Deformation techniques for efficient polynomial equation solving[END_REF], the new entry at index τ k +j simplifies as -jq {τ k +j,τ k +j+1,...,τr} . When we multiply the resulting vector by C τ k +j , we affect only entries from indices τ k + 1 to τ k + j. More precisely, the previous relation shows that we obtain the vector q {1,τ k +j,...,τr} . . . q {τ k ,τ k +j,...,τr} q {τ k +1,τ k +j+1,...,τr} . . . q {τ k +j,τ k +j+1,...,τr} h k +j+1 . . . h τr .

Finally, right-multiplication by D τ k +j affects entries of indices 1, . . . , τ k . For i = 1, . . . , τ k , it replaces q {i,τ k +j,...,τr} by q {i,τ k +j,...,τr} (z τ k +j -z i ) + q {τ k +j,τ k +j+1,...,τr} = q {i,τ k +j+1,...,τr} . Thus, the resulting vector is q {1,τ k +j+1,...,τr} . . . q {τ k ,τ k +j+1,...,τr} q {τ k +1,τ k +j+1,...,τr} . . . q {τ k +j,τ k +j+1,...,τr} h τ k +j+1 . . . h τr which is precisely q τ k +j , as claimed in [START_REF] Herrero | Computing isolated roots of sparse polynomial systems in affine space[END_REF].

C Proof of Lemma 4.4

To simplify our notation, for all 1 ≤ s ≤ ℓ, we abbreviate η ℓ-s (d -1, . . . , d -ℓ) to g ℓ-s . Then, we claim that one has

Let a be a sequence of m + 1 numbers (a 0 , a 1 , . . . , a m ) and let p a (t) = m i=0 a i t i be its generating polynomial.

where w a (λ) is the function w a (λ) = m i=1 a ℓ i i , and ℓ λ , ℓ λ ′ are the respective lengths of λ and λ ′ . If we consider m = n, a = (1, . . . , 1) = 1 and k = d, then equation (28) becomes

d n 1 = λ⊢n, ℓ λ ′ ≤n h(λ) d ℓ λ ′ .
For any partition λ of n, the length of its conjugate satisfies ℓ λ ′ ≤ n and so

[t n ](1 + t + • • • + t n ) d = d n 1 = λ⊢n h(λ) d ℓ λ . (29)
Furthermore,

(1 + t + • • • + t n ) d = (1 -t n+1 ) d (1 -t) d = d k=0 (-1) k d k t (n+1)k ∞ i=0 d + i -1 i t i ,
where t n appears only when k = 0 and i = n. In other words,

[t n ] (1 + t + • • • + t n ) d = n + d -1 n . (30)
Combining ( 27), ( 29) and ( 30 We prove the inequality λ⊢n, ℓ λ ≥s e λ ≤ n(d + 1) s n+d n similarly.

  r,1 , . . . , ξ r,1 nr , . . . , ξ r,ℓr , . . . , ξ r,ℓr nr . (9) (ii) C strict λ

Lemma 3 . 8 . 2 ) 2 )

 3822 There exists an algorithm Prepare F(f , λ) which takes as input f as above and a partition λ, and returns f [λ] . If f has degree at most d, the algorithm takes O˜(n n+d d operations in K. Similarly, there exists an algorithm Prepare F H(f , φ, λ) which takes as input f , φ as above and a partition λ, and returns f [λ] and H[λ] . If f and φ have degree at most d, then the algorithm takes O˜(n 4 n+d d operations in K.

+ d 2 c 2 λ n 4 Γ

 4 [λ] , H[λ] then uses the algorithm in Theorem 4.1 with input f [λ] , H[λ] . Writing as before w λ = ℓ 1 ! • • • ℓ r !, the quantities used in the theorem becomec λ = d s η ℓ-s (d -1, . . . , d -ℓ) w λ , e λ = n(d + 1) s η ℓ-s (d, . . . , d -ℓ + 1) w λ , κ λ = d s η ℓ-s (d -1, . . . , d -ℓ) = w λ c λ .This implies that running Isolated Pointsf [λ] , H[λ] uses O˜ c λ (e λ + c 5 λ )operations which is again in O˜ d 2 c λ (e λ + c 5 λ )n 4 Γ . As before, the number of solutions in the output is at most c λ .4.3 Finishing the proof of Theorem 1.1

Lemma 4 . 4 . 1 n 5 =

 4415 With all notation being as above, the following holds λ⊢n,ℓ λ ≥s c λ ≤ c and λ⊢n,ℓ λ ≥s e λ ≤ e, where c = d s n+d-1 n and e = n (d + 1) s n+d n . Proof. The proof relies on the combinatorics of integer partitions and properties of elementary symmetric functions. Details are given in Appendix C. As a result, the total cost incurred by our calls to Isolated Points and Decompose is O˜ c(e + c 5 )n 9 d 2 simplify this further, by noticing that for d ≥ 2 we have e = n (d + 1) s n+d n ≤ n(n + 1)d 5s n+d-n(n + 1)c 5 so this is O˜ c 6 n 11 d 2 n + d d + n s + 1 .

1 η 1

 1 (z τ k +3 , . . . , z τ k+1 ) η 2 (z τ k +3 , . . . , z τ k+1 ) • • • η ℓ k+1 -2 (z τ k +3 , . . . , z τ k+1 ) 0 0 1 η 1 (z τ k +4 , . . . , z τ k+1 ) • • • η ℓ k+1 -3 (z τ k +4 , . . . , z τ k+1 ) η ℓ k+1 -4 (z τ k +5 , . . . , z τ k+1 )

1 0B

 1 z τ k +j -z τ k +1 . . . z τ k +j -z τ k +j-, with F k,j =   diag(z τ k +j -z τ k +t ) τ k +j -z t ) τ k , G k,j : j th row is (1, . . . ,1); others are zeros. τ k +j C τ k +j D τ k +j ∈ K[Z 1 , . . . , Z r ] τr×τr .

  τ k +j -z t ), and det(Dτ k +j ) = τ k t=1 (z τ k +j -z t ). This implies that det(J) = α k +j -z t ) τ k t=1

  g ℓ-s < d(d -1) • • • (d -ℓ + 1). Indeed, let f (t) = (t + d -1)(t + d -2) • • • (t + d -ℓ), so that f (1) = d(d -1) • • • (d -ℓ + 1). From Vieta's formula we have f (t) = ℓ s=0 g ℓ-s t sand so we also have f (1) = ℓ s=0 g ℓ-s . Therefore,d(d -1) • • • (d -ℓ + 1) = ℓ s=0 g ℓ-sand sog ℓ-s < d(d -1) • • • (d -ℓ + 1) for all 1 ≤ s ≤ ℓ.Now, for any partition λ = (n ℓ 1 1 . . . n ℓr r ) ⊢ n of length ℓ λ , we havec λ = d s g ℓ λ -s w λ with w λ = r i=1 ℓ i ! = d s ℓ λ ! r i=1 ℓ i ! g ℓ λ -s ℓ λ ! = d s h(λ) F d,ℓ λ ,s , where h(λ) = ℓ λ ! r i=1 ℓ i ! = ℓ λ ℓ 1 ,...,ℓr and F d,ℓ λ ,s = g ℓ λ -s ℓ λ ! . From our previous inequality we haveF d,ℓ λ ,s ≤ d(d -1) • • • (d -ℓ λ + 1) ℓ λ ! = d ℓ λand so λ⊢n, ℓ λ ≥s c λ ≤ d s λ⊢n, ℓ λ ≥s h(λ) d ℓ λ .

  d s n + d -1 n .

  1,ℓ 1 , . . . , ξ 1,ℓ 1

		, . . . , ξ r,1 , . . . , ξ r,1	, . . . , ξ r,ℓr , . . . , ξ r,ℓr
	n 1	nr	nr

  We can now finish estimating the runtime of the Critical Points Per Orbit Algorithm. For partitions of length s, at Step 2a, we only need to compute f [λ] which takes O˜(n n+d d 2 ) operations in K as per Lemma 3.8. At Step 2b, the procedure Isolated Points( f [λ] ) takes at most O˜(d 2 c λ (e λ + c 5 λ )n 4 Γ) operations in K, as we saw in Subsection 4.2. The output of this procedure contains at most c λ points; then, by Lemma 2.16, the cost of the call to Decompose at Step 2c is O˜(c 2 λ n), which is negligible compared to the previous costs. For partitions of length greater than s, computing f [λ] and H[λ] at Step 3a takes O˜(n 4 n+d d 2 ) operations in K, by Lemma 3.8. The procedure Isolated Points f [λ] , H[λ] at Step 3b requires at most O˜(d 2 c λ (e λ + c 5 λ )n 4 Γ) operations in K, as we saw in Subsection 4.2. Again, since the number of solutions in the output is at most c λ , the cost of Decompose at Step 3c is still O˜(c 2 λ n) which, as before, is negligible in comparison to the other costs. To complete our analysis, we need the following lemma.

Table 1 :

 1 Degrees and bounds

	n s	D	ℓ λ ≥s c λ	c	deg(I)	c
	4 2	79	80	560	856	864
	4 3	47	48	2240	744	768
	5 2 425	432	3150	15575 16000
	5 3 357	370	15750	18760 20000
	5 4 143	157	78750	11160 12500
	6 2 2222	2227	16632	-	337500
	6 3 2439	2453	99792	-	540000
	6 4 1482	1503	598752	-	486000
	6 5 470	486	3592512	-	233280

Table 2 :

 2 Algorithm Timings 29Obtaining an algorithm to decide whether V (f ) ∩ R n is empty in time polynomial in d s , n+d d , n s+1 , without assuming that W (φ u , f ) is finite for a generic u ∈ R, is still an open problem.

			92.881s	63	68
			773.924s	756	765
			114.064s	504	504
			495.432s	756	756	1658.071s	-	-
			7.356s	36	36
			9.236s	108	108
		1 )	17.908s	216	216
		λ = (1 6 )	98.312s	142	153
	6 4	λ = (1 4 2 1 ) λ = (1 3 3)	591.78s 26.196s	800 216	810 216	842.256s	-	-
		λ = (1 2 2 2 )	46.420s	324	324
	6 5	λ = (1 6 ) λ = (1 4 2 1 )	154.808s 121.768s	150 320	162 324	251.752s	-	-

  The polynomial coefficients associated to a are defined byk n a = [t n ] (p a (t) k ), if 0 ≤ n ≤ mk 0, if n < 0 or n > mk where [t n ] i c i t i = c n is the coefficient of t n in the series i c i t i .For any partition λ of n, let further λ ′ be its conjugate partition. By [12, Lemma 2.1], we have

	k n a	=	λ⊢n,	a k-ℓ λ ′ 0	h(λ)w a (λ)	k ℓ λ	,
			ℓ λ ′ ≤n

Throughout this paper we use O˜(•) to indicate that polylogarithmic factors are omitted, that is, f is O˜(g) if there exists a constant k such that f is O(g log k (g)).

Acknowledgements. G. Labahn is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), grant number RGPIN-2020-04276. É. Schost is supported by an NSERC Discovery Grant. T.X. Vu is supported by a labex CalsimLab fellowship/scholarship. The labex CalsimLab, reference ANR-11-LABX-0037-01, is funded by the program "Investissements d'avenir" of the Agence Nationale de la Recherche, reference ANR-11-IDEX-0004-02. M. Safey El Din and T.X. Vu are supported by the ANR grants ANR-18-CE33-0011 Sesame, ANR-19-CE40-0018 De Rerum Natura and ANR-19-CE48-0015 ECARP, the PGMO grant CAMiSAdo and the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement N. 813211 (POEMA).

A Proof of Proposition 2.4

The proof of Proposition 2.4 will be done in stages. We start with some rather straightforward lemmas.

Lemma A.1. Consider an S λ -equivariant sequence q = (q 1 , . . . , q ℓ ) in K[Z 1 , . . . , Z r ]. Then, for any I ⊂ {1, . . . , ℓ} and any σ in S λ , we have σ(q I ) = q σ(I) .

Proof. By induction on the size of I.

Lemma A.2. Consider a sequence q = (q 1 , . . . , q ℓ ) in K[Z 1 , . . . , Z r ], and suppose that

Then, for k in {1, . . . , r} and s in {1, . . . , ℓ k }, the polynomial τ k +s i=τ k +1 q {i,τ k +s+1,...,ℓ} is invariant under any permutation of {z τ k +1 , . . . , z τ k +s }.

Proof. For any σ ∈ S λ permuting only {z τ k +1 , . . . , z τ k +s }, we have, using the previous lemma,

q {σ(i),τ k +s+1,...,ℓ} .

Since σ permutes {z τ k +1 , . . . , z τ k +s } and the last sum runs over all i = τ k + 1, . . . , τ k + s, it equals τ k +s i=τ k +1 q {i,τ k +s+1,...,ℓ} .

We can now prove the proposition. The fact that all entries of p are polynomials follows from our first assumption. Proving that they are S λ -invariant requires more work, as we have to deal with numerous cases. While most are straightforward, the last case does involve nontrivial calculations. Fix k ∈ {0, . . . , r -1}. We first prove that for s in {1, . . . , ℓ k+1 }, i in {τ k + 1, . . . , τ k + s}, and m in {0, . . . , r -1}, with m = k, then the term q {i,τ k +s+1,...,τr} is symmetric in {z τm+1 , . . . , z τ m+1 }. Indeed, consider a permutation σ ∈ S λ that acts on {z τm+1 , . . . , z τ m+1 } only. By Lemma A.1, σ(q {i,τ k +s+1,...,τr} ) is equal to q {σ(i),σ(τ k +s+1),...,σ(τr )} . If m < k, then all indices i, τ k +s+1, . . . , τ r are left invariant by σ while for m > k, [σ(i), σ(τ k +s+1), . . . , σ(τ r )] is a permutation of [i, τ k + s + 1, . . . , τ r ]. In both cases, q {σ(i),σ(τ k +s+1),...,σ(τr )} = q {i,τ k +s+1,...,τr} , as claimed.

Consider first the invariance of p τ k+1 . By Lemma A.2, the sum

i=τ k +1 q {i,τ k+1 +1,...,τr} is symmetric in {z τ k +1 , . . . , z τ k+1 }. Next, for i in {τ k + 1, . . . , τ k+1 } and m in {0, . . . , r -1}, with m = k, each term q {i,τ k+1 +1,...,τr} is symmetric in {z τm+1 , . . . , z τ m+1 }, making use of the previous paragraph with s = ℓ k+1 . As a result, p τ k+1 is S λ -invariant.

Next, for j in {1, . . . , ℓ k+1 -1} and σ in S λ , we prove that σ(p τ k +j ) = p τ k +j . Assume first that σ acts only on {z τm+1 , . . . , z τ m+1 }, for some m in {0, . . . , r -1} with m = k. For s in {1, . . . , j}, the polynomial η j-s (z τ k +s+2 , . . . , z τ k+1 ) depends only on {z τ k +1 , . . . , z τ k+1 } and so is σ-invariant. Using our earlier argument we see that for i in {τ k + 1, . . . , τ k + s} the divided difference q {i,τ k +s+1,...,τr} is σ-invariant. As a result, p τ k +j itself is σ-invariant.

It remains to prove that p τ k +j is σ-invariant for a permutation σ of {τ k + 1, . . . , τ k+1 }. We do this first for σ = (τ k + 1, τ k + 2), by proving that all summands in the definition of p τ k +j are σ-invariant. For any s in {2, . . . , j}, η j-s (z τ k +s+2 , . . . , z τ k +1 ) does not depend on (z τ k +1 , z τ k +2 ), so it is σ-invariant. For s in {2, . . . , j}, the sum τ k +s i=τ k +1 q {i,τ k +s+1,...,τr} is symmetric in (τ k + 1, τ k + 2), since σ just permutes two terms in the sum while for s = 1, q {τ k +1,τ k +2,...,τr} is symmetric in (z τ k +1 , z τ k +2 ) by Lemma A.1. Thus, our claim is proved for σ = (τ k + 1, τ k + 2).

It remains to prove that p τ k +j is invariant in (z τ k +2 , . . . , z τ k+1 ). For any t = 1, . . . , j, set

Then p τ k +j = p τ k +j,1 and we have the recursive identity

q {i,τ k +t,...,τr} .

For any t, set z :t = (z τ k +1 , . . . , z τ k +t ) and z t: = (z τ k +t , . . . , z τ k+1 ). We will show that for t = 1, . . . , j, the polynomial p τ k +j,t satisfies: p τ k +j,t is block symmetric in z :t and z t+1: [START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF] Taking t = 1 implies that p τ k +j = p τ k +j,1 is symmetric in z 2: = (z τ k +2 , . . . , z τ k+1 ), as claimed.