# Faster real root decision algorithm for symmetric polynomials

George Labahn  Cheriton School of Computer ScienceUniversity of
WaterlooOntario, Canada ,  Cordian Riener  Department of Mathematics and
StatisticsUiT, The Arctic University of Norway, TromsøN-9037Norway ,  Mohab
Safey El Din  Sorbonne Université, CNRS, LIP6F-75005 Paris75252France ,  Éric
Schost  Cheriton School of Computer ScienceUniversity of WaterlooOntario,
Canada and  Thi Xuan Vu  Department of Mathematics and StatisticsUiT, The
Arctic University of Norway, TromsøN-9037Norway

(2023; 2023)

###### Abstract.

In this paper, we consider the problem of deciding the existence of real
solutions to a system of polynomial equations having real coefficients, and
which are invariant under the action of the symmetric group. We construct and
analyze a Monte Carlo probabilistic algorithm which solves this problem, under
some regularity assumptions on the input, by taking advantage of the symmetry
invariance property.

The complexity of our algorithm is polynomial in $d^{s},{{n+d}\choose d}$, and
${{n}\choose{s+1}}$, where $n$ is the number of variables and $d$ is the
maximal degree of $s$ input polynomials defining the real algebraic set under
study. In particular, this complexity is polynomial in $n$ when $d$ and $s$
are fixed and is equal to $n^{O(1)}2^{n}$ when $d=n$.

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
2023 International Symposium on Symbolic and Algebraic Computation; July
24–27, 2023; Tromsø, Norway††price: 15.00††doi: ??††isbn: ??††journalyear:
2023††copyright: rightsretained††conference: International Symposium on
Symbolic and Algebraic Computation 2023; July 24–27, 2023; Tromsø,
Norway††booktitle: International Symposium on Symbolic and Algebraic
Computation 2023 (ISSAC 2023), July 24–27, 2023, Tromsø, Norway††doi:
10.1145/3597066.3597097††isbn: 979-8-4007-0039-2/23/07

##  1\. Introduction

Let $\bm{f}=(f_{1},\dots,f_{s})$ be polynomials in the multivariate polynomial
ring $\mathbb{Q}[x_{1},\ldots,x_{n}]$ and let $V(\bm{f})\subset\mathbb{C}^{n}$
be the algebraic set defined by $\bm{f}$. We denote by
$V_{\mathbb{R}}(\bm{f}):=V(\bm{f})\cap\mathbb{R}^{n}$ the set of solutions in
$\mathbb{R}^{n}$ to the system $\bm{f}$. In addition we assume that all
$f_{i}$’s are invariant under the action of the symmetric group $S_{n}$, that
is, are symmetric polynomials (or equivalently, $S_{n}$-invariant
polynomials).

Under this invariance property, we design an algorithm which, on input
$\bm{f}$, decides whether $V_{\mathbb{R}}(\bm{f})$ is empty or not. As is
typical for such problems, we assume that the Jacobian matrix of $\bm{f}$ with
respect to $x_{1},\dots,x_{n}$ has rank $s$ at any point of $V(\bm{f})$. In
this case the Jacobian criterion (Eisenbud, 2013, Thm 16.19) implies that the
complex algebraic set $V(\bm{f})$ is smooth and $(n-s)$-equidimensional (or
empty).

Previous work. The real root decision problem for polynomial systems of
equations (and more generally systems of inequalities) lies at the foundations
of computational real algebraic geometry. Algorithms for solving polynomial
systems over the real numbers start with Fourier (Fourier, 1826) who provided
a first algorithm for solving linear systems of inequalities (rediscovered in
1919 by Dines (Dines, 1919)). These algorithms are important because they make
the first connection with elimination theory. Tarski’s theorem (Tarski, 1948)
states that the projection of a semi-algebraic set on a coordinate subspace is
a semi-algebraic set. This theorem, and its algorithmic counterpart which
relies on Sturm’s theorem for real root counting in the univariate case,
enable recursive algorithmic patterns (eliminating variables one after
another). The first algorithm with an elementary recursive complexity,
Cylindrical Algebraic Decomposition, is due to Collins (see (Collins, 1975)
and references in (McCallum, 1984, 1999; Hong, 1992; Strzeboński, 2006, 2014;
Chen et al., 2009; England et al., 2020; Chen et al., 2010) for various
further improvements).

It turns out that these algorithms run in time doubly exponential in $n$
(Davenport and Heintz, 1988; Brown and Davenport, 2007). Note that some
variants actually solve the quantifier elimination problem, a much more
general and difficult computational problem than the real root decision
problem.

Algorithms which solve the real root decision problem in time singly
exponential in $n$ and polynomial in the maximum degree of the input were
pioneered by Grigoriev and Vorobjov (Grigoriev and Vorobjov, 1988) and Renegar
(Renegar, 1992), and further improved by Canny (Canny, 1987), Heintz, Roy and
Solernó (Heintz et al., 1993) and Basu, Pollack and Roy (Basu et al., 1996).
The method used in this framework is referred to as the critical point method.
It reduces the real root decision problem to the computation of finitely many
complex critical points of a polynomial map which reaches extrema at each
connected component of the semi-algebraic set under study.

The algorithm proposed here for solving the real root decision problem for
systems of symmetric polynomial equations also builds on the critical point
method. It borrows ideas from probabilistic algorithms which have been
designed to obtain sharper complexity estimates (e.g. cubic either in some
Bézout bound attached to some critical point system or in some geometric
intrinsic degree) and obtain practical performances that reflect the
complexity gains (Bank et al., 2001, 1997, 2005, 2004, 2009; Safey El Din and
Schost, 2003; Bank et al., 2014). These algorithms make use of geometric
resolution or symbolic homotopy techniques to control the complexity of the
algebraic elimination step (see e.g. (Giusti et al., 2001; Safey El Din and
Schost, 2018) and references therein), and of regularity assumptions to easily
derive critical point systems from the input polynomials.

Under the Jacobian criterion assumptions, critical points are defined as the
intersection of the affine variety $V(\bm{f})$ with a determinantal variety
derived from a certain Jacobian matrix. The design of dedicated algebraic
elimination algorithms for this particular setting has attracted some
attention already (Faugère et al., 2012; Bank et al., 2015; Spaenlehauer,
2014; Safey El Din and Spaenlehauer, 2016; Hauenstein et al., 2021). When
adding the symmetry property to polynomials defining the variety and the
polynomial map for which one computes the critical points, significant
improvements have been achieved recently in (Faugère et al., 2023) by using
the symbolic homotopy algorithms in (Labahn et al., 2021).

These improvements, which allows one to obtain complexity gains related to the
combinatorial complexity of the symmetric group, also borrow ideas from
algebraic algorithms working with data which are invariant by the action of
this group (Faugère and Svartz, 2012). We emphasize that taking advantage of
symmetries in data is a topical and difficult issue, which involves a variety
of methodologies (Perminov and Shakirov, 2009; Busé and Karasoulou, 2016;
Colin, 1997; Sturmfels, 2008; Faugère and Rahmany, [n. d.]).

In (Timofte, 2003), Timofte proves a breakthrough result which is now known as
the degree principle. It states that a symmetric polynomial of degree $d$ with
real coefficients has real solutions if and only if one of these solutions has
at most $d$ distinct coordinates.

This shows that when $d$ is fixed and $n$ grows, the real root decision
problem can be solved in polynomial time. This is far better than computing at
least one sample point per connected component (see also (Basu and Riener,
2017a, b, 2022)), and is one of the rare interesting cases where the best
known algorithms for these two problems admit different complexities. This is
also the starting point of several results which enhance the real root
decision problem and polynomial optimization under some $S_{n}$-invariance
property for classes of problems where $d$ remains fixed and $n$ grows (see
(Riener et al., 2013; Riener, 2012, 2016; Gatermann and Parrilo, 2004) and
(Riener and Safey el Din, 2018) for equivariant systems).

Main contributions. Being able to leverage $S_{n}$-invariance for critical
point computations is not sufficient to solve root decision problems more
efficiently using the critical point method. Additional techniques are needed.

Indeed, to solve the real root decision problem by finding the critical points
of a polynomial map $\phi$, one typically defines $\phi$ as the distance from
points on the variety to a generic point. This map reaches extrema at each
connected component of the semi-algebraic set under study. However, the map
$\phi$ is not symmetric. If it was, our problem would be solved by the
critical point algorithm of (Faugère et al., 2023). Unfortunately there does
not appear to be an obvious symmetric map that fits the bill.

Instead, our approach is to apply the critical point method on individual
$S_{n}$-orbits, with suitable $\phi$ found for each orbit. Thus while we
cannot use the critical point algorithm of (Faugère et al., 2023) directly we
can make use of the various subroutines used in it to construct a fast
decision procedure. Intuitively, working with $S_{n}$-orbits is the same as
separately searching for real points having distinct coordinates, or real
points having two or more coordinates which are the same, or groups of
coordinates each of which has equal coordinates and so on. In each case an
orbit can be described by points having $n$ or fewer pairwise distinct
coordinates, a key observation in constructing generic maps invariant for each
orbit.

###### Theorem 1.1.

Let $\bm{f}=(f_{1},\dots,f_{s})$ be symmetric polynomials in
$\mathbb{Q}[x_{1},\ldots,x_{n}]$ having maximal degree $d$. Assume that the
Jacobian matrix of $\bm{f}$ with respect to $x_{1},\dots,x_{n}$ has rank $s$
at any point of $V(\bm{f})$. Then there is a Monte Carlo algorithm ${\sf
Real\\_emptiness}$ which solves the real root decision problem for $\bm{f}$
with

${O}{\,\tilde{}\,}\left(d^{6s+2}n^{11}{{n+d}\choose n}^{6}\left({{n+d}\choose
n}+{{n}\choose{s+1}}\right)\right)\\\ \subset\left(d^{s}{{n+d}\choose
n}{{n}\choose{s+1}}\right)^{O(1)}$

operations in $\mathbb{Q}$. Here the notion ${O}{\,\tilde{}\,}$ indicates that
polylogarithmic factors are omitted.

The remainder of the paper proceeds as follows. The next section reviews known
material, on invariant polynomials over products of symmetric groups, the
tools we use to work with $S_{n}$-orbits, and our data structures. Section 3
discusses our smoothness requirement and shows that it is preserved by
alternate representations of invariant polynomials. Section 4 shows how we
construct critical point functions along with their critical point set. This
is followed in Section 5 by a description of our algorithm along with a proof
of correctness and complexity. The paper ends with a section on topics for
future research.

##  2\. Preliminaries

###  2.1. Invariant Polynomials

We briefly review some properties of polynomials invariant under the action of
$S_{t_{1}}\times\cdots\times S_{t_{k}}$, with $S_{t_{i}}$ the symmetric group
on $t_{i}$ elements, for all $i$. In this paragraph, we work with variables
${\bm{z}}=({\bm{z}}_{1},\ldots,{\bm{z}}_{k})$, with each
${\bm{z}}_{i}~{}=~{}(z_{1,i},\ldots,z_{t_{i},i})$; for all $i$, the group
$S_{t_{i}}$ permutes the variables ${\bm{z}}_{i}$. For $j\geq 0$, we denote by

$E_{j,i}=\sum_{1\leq m_{1}<m_{2}<\cdots<m_{j}\leq
t_{i}}z_{m_{1},i}z_{m_{2},i}\cdots z_{m_{j},i},$

the elementary polynomial in the variables $\bm{z}_{i}$, with each $E_{j,i}$
having degree $j$, and by

${P}_{j,i}=z_{1,i}^{j}+\cdots+z_{t_{i},i}^{j}$

the $j$-th Newton sum in the variables ${\bm{z}}_{i}$, for $i=1,\dots,k$. The
following two results are well-known.

For $i=1,\dots,k$, let $\bm{e}_{i}=(e_{1,i},\dots,e_{t_{i},i})$ be a set of
$t_{i}$ new variables and let $\bm{E}_{i}=(E_{1,i},\dots,E_{t_{i},i})$; we
write $\bm{e}=(\bm{e}_{1},\dots,\bm{e}_{k})$ and
$\bm{E}=(\bm{E}_{1},\dots,\bm{E}_{k})$.

###### Lemma 2.1.

Let $g\in[{\bm{z}}_{1},\dots,{\bm{z}}_{k}]$ be invariant under the action of
$S_{t_{1}}\times\cdots\times S_{t_{k}}$. Then there exists a unique
$\gamma_{g}$ in $\mathbb{Q}[\bm{e}]$ such that $g=\zeta_{g}(\bm{E})$.

Similarly, let ${p}_{j,i}$ be new variables, and consider the sequences
${\bm{p}}_{i}=({p}_{1,i},\ldots,{p}_{t_{i},i})$ and
${\bm{p}}=({\bm{p}}_{1},\ldots,{\bm{p}}_{k})$, together with their polynomial
counterparts ${\bm{P}}_{i}=({P}_{1,i},\ldots,{P}_{t_{i},i})$ and
${\bm{P}}=({\bm{P}}_{1},\ldots,{\bm{P}}_{k})$.

###### Lemma 2.2.

Let $g\in[{\bm{z}}_{1},\dots,{\bm{z}}_{k}]$ be invariant under the action of
$S_{t_{1}}\times\cdots\times S_{t_{k}}$. Then there exists a unique
$\zeta_{g}$ in $\mathbb{Q}[{\bm{p}}]$ such that $g=\gamma_{g}({\bm{P}})$.

###### Example 2.3.

Let

$g=2(z_{1,1}z_{2,1}+z_{1,1}^{2}+2z_{1,1}z_{2,1}+z_{2,1}^{2})(z_{1,2}^{2}+z_{2,2}^{2}),$

a polynomial invariant under $S_{2}\times S_{2}$, with
${\bm{z}}_{1}=(z_{1,1},z_{2,1})$, ${\bm{z}}_{2}=(z_{1,2},z_{2,2})$, $k=2$ and
$t_{1}=t_{2}=2$. In this case, we have

$g=(3{P}_{1,1}^{2}-{P}_{1,2}){P}_{2,2}$

and hence
$\gamma_{g}=(3{p}_{1,1}^{2}-{p}_{1,2}){p}_{2,2}\in\mathbb{Q}[{p}_{1,1},{p}_{1,2},{p}_{2,1},{p}_{2,2}].$

###  2.2. Describing $S_{n}$-orbits via Partitions

$S_{n}$-orbits are subsets of $\mathbb{C}{}^{n}$ that play a central role in
our algorithm. In this section, we review notation and description of
$S_{n}$-orbits, along with the form of the output used in (Faugère et al.,
2023).

A simple way to parameterize $S_{n}$-orbits is through the use of partitions
of $n$. A sequence $\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$, where
$n_{1}<\cdots<n_{k}$ and $n_{i}$’s and $t_{i}$’s are positive integers, is
called a partition of $n$ if $n_{1}t_{1}+\cdots+n_{k}t_{k}=n$. The length of
the partition $\lambda$ is defined as $\ell:=t_{1}+\cdots+t_{k}$.

For a partition $\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ of $n$, we use
the notation from (Faugère et al., 2023, Section 2.3) and let $U_{\lambda}$
denote the set of all points $\bm{u}$ in $\mathbb{C}{}^{n}$ that can be
written as

(1)
$\bm{u}=(\underbrace{u_{1,1},\dots,u_{1,1}}_{n_{1}},~{}\dots,~{}\underbrace{u_{t_{1},1},\dots,u_{t_{1},1}}_{n_{1}},~{}\dots,\\\
~{}\underbrace{u_{1,k},\dots,u_{1,k}}_{n_{k}},~{}\dots,~{}\underbrace{u_{t_{k},k},\dots,u_{t_{k},k}}_{n_{k}}).$

For any point $\bm{u}$ in $\mathbb{C}{}^{n}$, we define its type as the unique
partition $\lambda$ of $n$ such that there exists $\sigma\in S_{n}$ such that
$\sigma(\bm{u})\in U_{\lambda}$, with the $u_{i,j}$’s in (1) pairwise
distinct. Points of a given type
$\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ are stabilized by the action
of $S_{\lambda}:=S_{t_{1}}\times\cdots\times S_{t_{k}}$, the cartesian product
of symmetric groups $S_{t_{i}}$.

For a partition $\lambda$ as above, we can then define a mapping
$F_{\lambda}:U_{\lambda}\rightarrow\mathbb{C}{}^{\ell}$ as

$\bm{u}{~{}\rm as~{}in~{}}\eqref{eq:type}\mapsto\\\
(E_{1,i}(u_{1,i},\dots,u_{t_{i},i}),\dots,E_{t_{i},i}(u_{1,i},\dots,u_{t_{i},i}))_{1\leq
i\leq k},$

where $E_{j,i}(u_{1,i},\dots,u_{t_{i},i})$ is the $j$-th elementary symmetric
function in $u_{1,i},\dots,u_{t_{i},i}$ for $i=1,\dots,k$ and
$j=1,\dots,t_{i}$. One can think of the map $F_{\lambda}$ as a compression of
orbits. By applying this map, we can represent an $S_{n}$-orbit $\mathcal{O}$
of type $\lambda$ by the single point $F_{\lambda}(\mathcal{O}\cap
U_{\lambda}).$

Furthermore, the map $F_{\lambda}$ is onto: for any $\bm{c}=(c_{1,1},\dots,$
$c_{t_{k},k})\in\mathbb{C}{}^{\ell}$, we define polynomials
$\rho_{1}(u),\dots,\rho_{k}(u)$ by

$\rho_{i}(T)=T^{t_{i}}-c_{1,i}T^{t_{i}-1}+\cdots+(-1)^{t_{i}}c_{t_{i},i}.$

We can then find a point $\bm{u}\in\mathbb{C}{}^{n}$ in the preimage
$F_{\lambda}^{~{}-1}(\bm{c})$ by finding the roots $u_{1,i},\dots,u_{t_{i},i}$
of $\rho_{i}(T)$.

###  2.3. Zero-Dimensional Parametrizations

The subroutines we use from (Faugère et al., 2023) give their output in terms
of zero-dimensional parametrizations, which are defined as follows. Let
$W\subset\mathbb{C}{}^{n}$ be a variety of dimension zero, defined over
$\mathbb{Q}$. A zero-dimensional parametrization
$\mathscr{R}=((v,v_{1},\dots,v_{n}),\mu)$ of $W$ is

  * (i)

a squarefree polynomial $v$ in $\mathbb{Q}[t]$, where $t$ is a new
indeterminate, and $\deg(v)=|W|$,

  * (ii)

polynomials $v_{1},\dots,v_{n}$ in $\mathbb{Q}[t]$ such that
$\deg(v_{i})<\deg(v)$ for all $i$ and

$W=\left\\{\left(\frac{v_{1}(\tau)}{v^{\prime}(\tau)},\dots,\frac{v_{n}(\tau)}{v^{\prime}(\tau)}\right)\in\mathbb{C}{}^{n}\,:\,v(\tau)=0\right\\},$

  * (iii)

a linear form $\mu$ in $n$ variables such that
$\mu(v_{1},\dots,v_{n})=tv^{\prime}$ (so the roots of $v$ are the values taken
by $\mu$ on $W$).

When these conditions hold, we write $W=Z(\mathscr{R})$. Representing the
points of $W$ by means of rational functions with $v^{\prime}$ as denominator
is not necessary, but allows for a sharp control of the bit-size of the
output.

##  3\. Preserving smoothness

In our main algorithm, we assume that our input system
$\bm{f}=(f_{1},\dots,f_{s})$ satisfies the following smoothness condition

  * (A)

: the Jacobian matrix of $\bm{f}$ has rank $s$ at any point of $V(\bm{f})$.

In this section, we discuss consequences of this assumption for symmetric
polynomials.

Mapping to orbits: the map $\mathbb{T}_{\lambda}$. For a partition
$\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ of $n$, we define the
$\mathbb{Q}$-algebra homomorphism
$\mathbb{T}_{\lambda}:\mathbb{Q}[x_{1},\dots,x_{n}]\rightarrow\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$,
with ${\bm{z}}_{i}=(z_{1,i},\ldots,z_{t_{i},i})$ for all $i$, which maps the
variables $x_{1},\dots,x_{n}$ to

(2)
$\underbrace{z_{1,1},\dots,z_{1,1}}_{n_{1}},~{}\dots,~{}\underbrace{z_{t_{1},1},\dots,z_{t_{1},1}}_{n_{1}},~{}\dots,\\\
~{}\underbrace{z_{1,k},\dots,z_{1,k}}_{n_{k}},~{}\dots,~{}\underbrace{z_{t_{k},k},\dots,z_{t_{k},k}}_{n_{k}}.$

The operator $\mathbb{T}_{\lambda}$ extends to vectors of polynomials and
polynomial matrices entry-wise. The key observation here is that if $f$ is
symmetric, then its image through $\mathbb{T}_{\lambda}$ is
$S_{t_{1}}\times\cdots\times S_{t_{k}}$-invariant.

Fix a partition $\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ of $n$, and
let $\ell$ be its length. Set

$I_{j,i}:=\\{\sigma_{j,i}+1,\dots,\sigma_{j,i}+n_{i}\\},1\leq i\leq k;1\leq
j\leq t_{i}$

with $\sigma_{j,i}:=\sum_{r=1}^{i-1}t_{r}n_{r}+(j-1)n_{i}$. Variables $x_{m}$,
for $m$ in $I_{j,i}$, are precisely those that map to $z_{j,i}$ under
$\mathbb{T}_{\lambda}$. Define further the matrix
$\bm{Z}\in\mathbb{Q}^{\ell\times n}$ with $\ell=t_{1}+\cdots+t_{k}$, where
rows are indexed by pairs $(j,i)$ as above and columns by
$m\in\\{1,\dots,n\\}$. For all such $(j,i)$, the entry of row index $(j,i)$
and column index $m\in I_{j,i}$ is set to $1/n_{i}$, all others are zero. In
other words, $\bm{Z}={\rm diag}(\bm{Z}_{1},\dots,\bm{Z}_{k})$, where

$\bm{Z}_{i}=\left(\begin{matrix}\begin{matrix}\frac{1}{n_{i}}&\cdots&\frac{1}{n_{i}}\end{matrix}&{\bf
0}&\cdots&{\bf 0}\\\ {\bf
0}&\begin{matrix}\frac{1}{n_{i}}&\cdots&\frac{1}{n_{i}}\end{matrix}&\cdots&{\bf
0}\\\ \vdots&&\ddots&\vdots\\\ {\bf 0}&{\bf
0}&\cdots&\begin{matrix}\frac{1}{n_{i}}&\cdots&\frac{1}{n_{i}}\end{matrix}\end{matrix}\right)$

is a matrix in $\mathbb{Q}^{t_{i}\times n_{i}t_{i}}$.

###### Example 3.1.

Consider the partition $\lambda=(2^{2}\,3^{1})$ of $n=7$. Then
$n_{1}=2,t_{1}=2$, $n_{2}=3$, $t_{2}=1$ and the length of $\lambda$ is $3$. In
this case,

$\bm{Z}=\left(\begin{matrix}\frac{1}{2}&\frac{1}{2}&\\\
&&\frac{1}{2}&\frac{1}{2}\\\
&&&&\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\end{matrix}\right).$

###### Lemma 3.2.

Let $\bm{f}=(f_{1},\dots,f_{s})\subset\mathbb{Q}[x_{1},\dots,x_{n}]$ be a
sequence of symmetric polynomials, and let $\lambda$ be a partition of $n$.
Then

$\mathbb{T}_{\lambda}({\rm Jac}_{x_{1},\dots,x_{n}}(\bm{f}))={\rm
Jac}_{\bm{z}_{1},\dots,\bm{z}_{k}}(\mathbb{T}_{\lambda}(\bm{f}))\cdot\bm{Z},$

where $\bm{Z}$ is the matrix defined above.

###### Proof.

For any polynomial $f$ in $\mathbb{Q}[x_{1},\dots,x_{n}]$, applying the
operator $\mathbb{T}_{\lambda}$ on $f$ evaluates $f$ at $x_{m}=z_{j,i}$ for
$1\leq i\leq k$, $1\leq j\leq t_{i}$ and $m$ in $I_{j,i}$. By the
multivariable chain rule,

$\displaystyle\frac{\partial\mathbb{T}_{\lambda}(f)}{\partial z_{j,i}}$
$\displaystyle=\sum_{m\in I_{j,i}}\mathbb{T}_{\lambda}\left(\frac{\partial
f}{\partial x_{m}}\right).$

If $f$ is symmetric, for $m,m^{\prime}$ in $I_{j,i}$, we then have

$\mathbb{T}_{\lambda}\left(\frac{\partial f}{\partial
x_{m}}\right)=\mathbb{T}_{\lambda}\left(\frac{\partial f}{\partial
x_{m^{\prime}}}\right),$

so that, for $m$ in $I_{j,i}$,

$\mathbb{T}_{\lambda}\left(\frac{\partial f}{\partial
x_{m}}\right)=\frac{1}{n_{i}}\frac{\partial\mathbb{T}_{\lambda}(f)}{\partial
z_{j,i}}.$

This argument can be extended to a sequence of polynomials to obtain our
claim. ∎

###### Example 3.3.

We continue Example 3.1 with a single $S_{7}$-invariant polynomial
$f=\sum_{1\leq i\leq j\leq 7}x_{i}x_{j}$. Then

$\mathbb{T}_{\lambda}(f)=3z_{1,1}^{2}+3z_{2,1}^{2}+6z_{1,2}^{2}+6z_{1,1}z_{1,2}+4z_{1,1}z_{2,1}+6z_{1,2}z_{2,1},$

and so

${\rm
Jac}(\mathbb{T}_{\lambda}(f))=(6z_{1,1}+6z_{1,2}+4z_{2,1},4z_{1,1}+6z_{1,2}+6z_{2,1},6z_{1,1}+12z_{1,2}+6z_{2,1}).$

This implies that ${\rm Jac}(\mathbb{T}_{\lambda}(f))\cdot\bm{Z}$ is equal to
$(u,u,v,v,w,w,w)$, with

$u=3z_{1,1}+3z_{1,2}+2z_{2,1},v=2z_{1,1}+3z_{1,2}+3z_{2,1},w=2z_{1,1}+4z_{1,2}+2z_{2,1}.$

This is precisely $\mathbb{T}_{\lambda}({\rm Jac}(f))$.

###### Corollary 3.4.

Under the assumptions of the previous lemma, if $\bm{f}$ satisfies condition
$({\sf A})$, then
$\mathbb{T}_{\lambda}(\bm{f})\subset\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$
does as well.

###### Proof.

Let
$\bm{\alpha}=(\alpha_{1,1},\dots,\alpha_{t_{1},1},\dots,\alpha_{1,k},\dots,\alpha_{t_{k}k})$
be a zero of $\mathbb{T}_{\lambda}(\bm{f})$ in $\mathbb{C}^{\ell}$. We have to
prove that ${\rm
Jac}_{\bm{z}_{1},\dots,\bm{z}_{k}}(\mathbb{T}_{\lambda}(\bm{f}))(\bm{\alpha})$
has a trivial left kernel.

Consider the point

(3)
$\bm{\varepsilon}=\big{(}\underbrace{\alpha_{1,1},\dots,\alpha_{1,1}}_{n_{1}},\dots,\underbrace{\alpha_{t_{1},1},\dots,\alpha_{t_{1},1}}_{n_{1}},\dots,\\\
\underbrace{\alpha_{1,k},\dots,\alpha_{1,k}}_{n_{k}},\dots,\underbrace{\alpha_{t_{k},k},\dots,\alpha_{t_{k},k}}_{n_{k}}\big{)}\in\mathbb{C}^{n},$

which lies in $V(\bm{f})$. In particular, for any $g$ in
$\mathbb{Q}[x_{1},\dots,x_{n}]$, we have
$\mathbb{T}_{\lambda}(g)(\bm{\alpha})=g(\bm{\varepsilon})$. Applying this to
the Jacobian matrix of $\bm{f}$, we obtain $\mathbb{T}_{\lambda}({\rm
Jac}(\bm{f}))(\bm{\alpha})={\rm Jac}(\bm{f})(\bm{\varepsilon}).$ Since by
assumption $\bm{f}$ is symmetric, the previous lemma implies that

${\rm Jac}(\bm{f})(\bm{\varepsilon})={\rm
Jac}_{\bm{z}_{1},\dots,\bm{z}_{k}}(\mathbb{T}_{\lambda}(\bm{f}))(\bm{\alpha})\cdot\bm{Z}.$

Since ${\rm Jac}(\bm{f})(\bm{\varepsilon})$ has rank $s$ (by condition ${\sf
A}$), the left kernel of ${\rm Jac}(\bm{f})(\bm{\varepsilon})$ is trivial.

It follows that the left kernel of ${\rm
Jac}_{\bm{z}_{1},\dots,\bm{z}_{k}}(\mathbb{T}_{\lambda}(\bm{f}))(\bm{\alpha})$
is also trivial. ∎

When we represent $S_{t_{1}}\times\cdots\times S_{t_{k}}$-invariant functions
in terms of Newton sums, we can show that the new representation also
preserves condition (A).

###### Lemma 3.5.

Assume $(g_{1},\ldots,g_{s})\subset\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$ is
$S_{t_{1}}\times\cdots\times S_{t_{k}}$\- invariant and satisfies condition
$({\sf A})$. If we set $h_{i}=\gamma_{g_{i}}$ for all $i$, then
$(h_{1},\ldots,h_{s})$ also satisfies condition $({\sf A})$.

###### Proof.

The Jacobian matrix ${\rm Jac}(\bm{g})$ of $(g_{1},\ldots,g_{s})$ factors as

${\rm Jac}(\bm{g})={\rm Jac}(\bm{h})({\bm{P}})\cdot{\bm{V}},\ {\rm where}\
{\bm{V}}={\rm diag}(V_{1},\dots,V_{k})$

with each $V_{i}$ a row-scaled Vandermonde matrix given by

(4) $V_{i}={\small\left(\begin{matrix}1&&&\\\ &2&&\\\ &&\ddots&\\\
&&&{t_{i}}\end{matrix}\right)\left(\begin{matrix}1&1&\cdots&1\\\
z_{1,i}&z_{2,i}&\cdots&z_{t_{i},i}\\\ \vdots&&&\vdots\\\
z_{1,i}^{t_{i}-1}&z_{2,i}^{t_{i}-1}&\cdots&z_{t_{i},i}^{t_{i}-1}\end{matrix}\right)}.$

Let $\bm{\eta}$ be a point in the vanishing set of $(h_{1},\ldots,h_{s})$ and
let $\bm{\varepsilon}$ be in ${\bm{P}}^{-1}(\bm{\eta})$. If ${\rm
Jac}(\bm{h})$ is rank deficient at $\bm{\eta}$ then ${\rm
Jac}(\bm{h})({\bm{P}})(\bm{\varepsilon})$ is also rank deficient. This implies
that the rank of ${\rm Jac}(\bm{g})(\bm{\varepsilon})$, which is bounded above
by those of ${\rm Jac}(\bm{h})({\bm{P}})(\bm{\varepsilon})$ and
${\bm{V}}(\bm{\varepsilon})$, is deficient. ∎

Similarly, instead of using a row-scaled Vandermonde matrix $V_{i}$ as in (4),
we can use $V_{i}$ as the Jacobian matrix of elementary symmetric functions in
$\bm{z}_{i}$. This gives a similar result but for the polynomials
$\zeta_{g_{1}},\dots,\zeta_{g_{s}}$.

###### Lemma 3.6.

Assume $(g_{1},\ldots,g_{s})\subset\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$ is
$S_{t_{1}}\times\cdots\times S_{t_{k}}$\- invariant and satisfies condition
$({\sf A})$. Then the sequence of polynomials
$(\zeta_{g_{1}},\ldots,\zeta_{g_{s}})$ also satisfies condition $({\sf A})$.

##  4\. Critical loci

If $W\subset\mathbb{C}^{\ell}$ is an equidimensional algebraic set, and $\phi$
a polynomial function defined on $W$, a non-singular point $\bm{w}\in W$ is
called a critical point of $\phi$ on $W$ if the gradient of $\phi$ at $\bm{w}$
is normal to the tangent space $T_{\bm{w}}W$ of $W$ at $\bm{w}$.

If $\bm{g}=(g_{1},\dots,g_{s})$ are generators of the ideal associated to $W$,
then $T_{\bm{w}}W$ is the right kernel of the Jacobian matrix ${\rm
Jac}(\bm{g})$ of $\bm{g}$ evaluated at $\bm{w}$. In the cases we will
consider, this matrix will have rank $s$ at all points of $W$ (that is,
$\bm{g}$ satisfies condition ${\sf A}$). The set of critical points of the
restriction of $\phi$ to $W$ is then defined by the vanishing of $\bm{g}$, and
of the $(s+1)$-minors of the Jacobian matrix ${\rm Jac}({\bm{g},\phi})$ of
$\bm{g}$ and $\phi$.

###  4.1. Finiteness through genericity

Let $\bm{g}=(g_{1},\ldots,g_{s})$ in $\mathbb{Q}[\bm{z}_{1},\dots.\bm{z}_{k}]$
with each $g_{i}$ invariant under the action of $S_{t_{1}}\times\cdots\times
S_{t_{k}}$; we write $\ell=t_{1}+\cdots+t_{k}$. We introduce some useful
$S_{t_{1}}\times\cdots\times S_{t_{k}}$-invariant mappings and discuss the
properties of their critical points on $V(\bm{g})\subset\mathbb{C}{}^{\ell}$.

For $1\leq i\leq k$, let
${\mathfrak{a}}_{i}=({\mathfrak{a}}_{1,i},\ldots,{\mathfrak{a}}_{t_{i},i})$ be
new indeterminates, and recall that $P_{j,i}$ is the $j$-th Newton sum for the
variables $\bm{z}_{i}$. Set

(5)
${\phi}_{{\mathfrak{a}}}=\sum_{i=1}^{k}c_{i}{P}_{t_{i}+1,i}+\sum_{i=1}^{k}\sum_{j=1}^{t_{i}}{\mathfrak{a}}_{j,i}{P}_{j,i}$

where $c_{i}=1$ if $t_{i}$ is odd and $c_{i}=0$ if $t_{i}$ is even. So
${\phi}_{{\mathfrak{a}}}$ has even degree and is invariant under the action of
$S_{t_{1}}\times\cdots\times S_{t_{k}}$. For
$\bm{a}=(\bm{a}_{1},\dots,\bm{a}_{k})$ in
$\mathbb{C}^{t_{1}}\times\cdots\times\mathbb{C}^{t_{k}}$, with each
$\bm{a}_{i}$ in $\mathbb{C}^{t_{i}}$, we denote by ${\phi}_{\bm{a}}$ the
polynomials in $\mathbb{C}[\bm{z}_{1},\dots,\bm{z}_{k}]$ obtained by
evaluating the indeterminates ${\mathfrak{a}}_{i}$ at $\bm{a}_{i}$ in
${\phi}_{{\mathfrak{a}}}$, for all $i$.

Further, we denote by ${\mathcal{U}}\subset{\mathbb{C}}{}^{\ell}$ the open set
consisting of points $\bm{w}=(\bm{w}_{1},\dots,\bm{w}_{k})$ such that the
coordinates of $\bm{w}_{i}$ are pairwise distinct for $i=1,\dots,k$. Note that
${\mathcal{U}}$ depends on the partition $\lambda=(n_{1}^{t_{1}}\dots
n_{k}^{t_{k}})$; when needed because of the use of different partitions, we
will denote it by ${\mathcal{U}}_{\lambda}$.

###### Proposition 4.1.

Let $\bm{g}=(g_{1},\dots,g_{s})$ be $S_{t_{1}}\times\cdots\times
S_{t_{k}}$-invariant polynomials in $\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$.
Suppose further that $\bm{g}$ satisfies condition (A). Then there exists a
non-empty Zariski open set
${\mathcal{A}}\subset{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$
such that for $\bm{a}\in{\mathcal{A}}$, the restriction of ${\phi}_{\bm{a}}$
to $V(\bm{g})$ has finitely many critical points in ${\mathcal{U}}$.

###  4.2. Proof of Proposition 4.1

For new variables ${L}_{1},\ldots,{L}_{s}$, we denote by
${\mathcal{S}}_{{\mathfrak{a}}}$ the polynomials

${\mathcal{S}}_{{\mathfrak{a}}}=\big{(}g_{1},\ldots,g_{s},\quad[{L}_{1}\cdots{L}_{s}~{}1]\cdot{\rm
Jac}(\bm{g},{\phi}_{{\mathfrak{a}}})\big{)}.$

For $\bm{a}=(\bm{a}_{1},\dots,\bm{a}_{k})$ in
$\mathbb{C}^{t_{1}}\times\cdots\times\mathbb{C}^{t_{k}}$, with each
$\bm{a}_{i}$ in $\mathbb{C}^{t_{i}}$, we denote by ${\mathcal{S}}_{\bm{a}}$
the polynomials in
$\mathbb{C}[{L}_{1},\dots,{L}_{s},\bm{z}_{1},\dots.\bm{z}_{k}]$ obtained by
evaluating ${\mathfrak{a}}_{i}$ at $\bm{a}_{i}$ in
${\mathcal{S}}_{{\mathfrak{a}}}$, for all $i$. Finally, denote by $\pi$ the
projection from the $(L,\bm{z})$-space $\mathbb{C}^{s+\ell}$ to the
$\bm{z}$-space $\mathbb{C}^{\ell}$.

###### Lemma 4.2.

Suppose that $\bm{g}$ satisfies condition (A). Then for
$\bm{a}\in{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$,
$\pi(V({\mathcal{S}}_{\bm{a}}))$ is the critical locus of the restriction of
the map ${\phi}_{\bm{a}}$ to $V(\bm{g})$.

###### Proof.

For any
$\bm{a}\in{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$, we
denote by $W({\phi}_{\bm{a}},\bm{g})$ the set of critical points of the
restriction of ${\phi}_{\bm{a}}$ to $V(\bm{g})$. Since $\bm{g}$ satisfies
condition (A), the set $W({\phi}_{\bm{a}},\bm{g})$ is given by

$\\{\bm{w}~{}|g_{1}(\bm{w})=\cdots=g_{s}(\bm{w})=0,\quad{\rm rank}({\rm
Jac}(\bm{g},{\phi}_{\bm{a}})(\bm{w}))\leq s\\}.$

Consider $\bm{w}$ in $W({\phi}_{\bm{a}},\bm{g})$ and a nonzero vector $\bm{c}$
in the left kernel of ${\rm Jac}(\bm{g},{\phi}_{\bm{a}})(\bm{w})$, of the form
$\bm{\bm{c}}=(c_{1},\dots,c_{s},c_{s+1})$. The last coordinate $c_{s+1}$
cannot vanish, as otherwise $(c_{1},\dots,c_{s})$ would be a nonzero vector in
the left kernel of ${\rm Jac}(\bm{g})(\bm{w})$ (which is ruled out by
condition (A)). Dividing through by $c_{s+1}$, the point
$(\bm{c}^{\prime},\bm{w})$, with $c^{\prime}_{i}=c_{i}/c_{s+1}$ for
$i=1,\dots,s$, is a solution of ${\mathcal{S}}_{\bm{a}}$.

Conversely, take $(\bm{\ell},\bm{w})$ in $V({\mathcal{S}}_{\bm{a}})$. Thus,
$\bm{w}$ cancels $\bm{g}$, and ${\rm Jac}(\bm{g},{\phi}_{\bm{a}})$ has rank
less than $s+1$ at $\bm{w}$, so that $\pi(V({\mathcal{S}}_{a}))$ is in
$W({\phi}_{\bm{a}},\bm{g})$. ∎

Let ${\phi}_{{\mathfrak{a}}}$ and $\gamma_{{\phi}_{{\mathfrak{a}}}}$ be
defined as in (5) and Lemma 2.2, respectively. For $i=1,\dots,k$, set
$Q_{i}=\gamma_{{P}_{t_{i}+1,i}}$, and let
$h_{1},\dots,h_{s}=\gamma_{g_{1}},\dots,\gamma_{g_{s}}$. In particular, Lemma
2.2 implies that $\gamma_{{\phi}_{{\mathfrak{a}}}}$ is given by

$\sum_{i=1}^{k}c_{i}Q_{i}+\sum_{i=1}^{k}\sum_{j=1}^{t_{i}}{\mathfrak{a}}_{j,i}{p}_{j,i}.$

The sequence ${\mathcal{S}}_{{\mathfrak{a}}}$ can be rewritten as

$h_{1}\circ{\bm{P}},\ldots,h_{s}\circ{\bm{P}},\\\
[{L}_{1}~{}\ldots~{}{L}_{s}~{}1]\left(\begin{matrix}\frac{\partial
h_{1}}{\partial{p}_{1,1}}&\cdots&\frac{\partial
h_{1}}{\partial{p}_{t_{k},k}}\\\ \vdots&&\vdots\\\ \frac{\partial
h_{s}}{\partial{p}_{1,k}}&\cdots&\frac{\partial
h_{s}}{\partial{p}_{t_{k},k}}\\\ {c_{1}\frac{\partial
Q_{1}}{\partial{p}_{1,1}}+}{\mathfrak{a}}_{1,1}&\cdots&{c_{k}\frac{\partial
Q_{k}}{\partial{p}_{t_{k},k}}+}{\mathfrak{a}}_{t_{k},k}\end{matrix}\right)_{{\bm{P}}(\bm{z})}\cdot{\bm{V}},$

where ${\bm{V}}$ is a multi-row-scaled Vandermonde matrix which is the
Jacobian matrix of ${\bm{P}}$ with respect to $\bm{z}$. This matrix has full
rank at any point $\bm{w}$ in the open set ${\mathcal{U}}$ defined in
Subsection 4.1.

In particular, for any
$\bm{a}\in{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$, the
intersection of $V({\mathcal{S}}_{\bm{a}})$ with
$\mathbb{C}^{s}\times{\mathcal{U}}$ is contained in the preimage by the map
${\rm Id}\times{\bm{P}}$ of the vanishing set of the sequence

${\bm{H}}_{\bm{a}}:\quad h_{1},\ldots,h_{s},\\\
[{L}_{1}~{}\cdots~{}{L}_{s}~{}1]\left(\begin{matrix}\frac{\partial
h_{1}}{\partial{p}_{1,1}}&\cdots&\frac{\partial
h_{1}}{\partial{p}_{t_{k},k}}\\\ \vdots&&\vdots\\\ \frac{\partial
h_{s}}{\partial{p}_{1,1}}&\cdots&\frac{\partial
h_{s}}{\partial{p}_{t_{k},k}}\\\ {c_{1}\frac{\partial
Q_{1}}{\partial{p}_{1,1}}+}a_{1,1}&\cdots&{c_{k}\frac{\partial
Q_{k}}{\partial{p}_{t_{k},k}}+}a_{t_{k},k}\\\ \end{matrix}\right).$

Since for all $1\leq i\leq k$, ${\bm{P}}_{i}$ defines a map with finite fibers
(by Newton identities and Vieta’s formula, the preimage by ${\bm{P}}$ of some
point is the set of roots of some polynomial of degree $t_{i}$), we deduce
that ${\bm{P}}$ and consequently ${\rm Id}\times{\bm{P}}$ define maps with
finite fibers. Thus

###### Lemma 4.3.

If $V({\bm{H}}_{\bm{a}})$ is finite, then
$V({\mathcal{S}}_{\bm{a}})\cap(\mathbb{C}^{s}\times{\mathcal{U}})$ is finite.

It remains to investigate finiteness properties of $V({\bm{H}}_{\bm{a}})$.

###### Proposition 4.4.

Suppose that $\bm{h}$ satisfies condition (A). Then, there exists a non-empty
Zariski open set
${\mathcal{A}}\subset{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$
such that for any $\bm{a}\in{\mathcal{A}}$,
$\langle{\bm{H}}_{\bm{a}}\rangle\subset{\mathbb{C}}[{L}_{1},\dots,{L}_{s},\bm{z}_{1},\dots,\bm{z}_{k}]$
is a radical ideal whose zero-set is finite.

###### Proof.

Let $W\subset{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$
be the vanishing set of $(h_{1},\ldots,h_{s})$. Consider now the map

$(\bm{\eta},\bm{w})\in{\mathbb{C}}{}^{s}\times W\to\\\
-\left(\sum_{i=1}^{s}\bm{\eta}_{i}\frac{\partial
h_{i}}{\partial{p}_{1,1}}{+c_{1}\frac{\partial
Q_{1}}{\partial{p}_{1,1}}}\right)_{(\bm{w})},\ldots,-\left(\sum_{i=1}^{s}\bm{\eta}_{i}\frac{\partial
h_{i}}{\partial{p}_{t_{k},k}}{+c_{k}\frac{\partial
Q_{k}}{\partial{p}_{t_{k},k}}}\right)_{(\bm{w})}.$

By Sard’s theorem (Shafarevich and Reid, 1994, Chap. 2, Sec. 6.2, Thm 2), the
set of critical values of this map is contained in a proper Zariski closed set
$\mathcal{B}$ of
${\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{k}}$. Since
$\bm{h}$ satisfies condition ${\sf(A)}$, for $\bm{a}$ outside $\mathcal{B}$,
the Jacobian matrix of ${\bm{H}}_{\bm{a}}$ has full rank at any
$(\bm{\eta},\bm{w})$ with $\bm{w}$ in $W$. Hence, by the Jacobian criterion
(Eisenbud, 2013, Thm 16.19), the ideal generated by ${\bm{H}}_{\bm{a}}$ in
${\mathbb{C}}[{L}_{1},\dots,{L}_{s},\bm{z}_{1},\dots,\bm{z}_{k}]$ is radical
and is of dimension at most zero. ∎

###### Proof of Prop 4.1.

Let ${\mathcal{A}}$ be the non-empty Zariski open set defined in Prop 4.4.
Since $\bm{g}$ satisfies condition $({\sf A})$, Lemma 4.2 implies that, for
any $\bm{a}\in{\mathcal{A}}$, the critical locus of the map ${\phi}_{\bm{a}}$
restricted to $V(\bm{g})$ is equal to $\pi(V({\mathcal{S}}_{\bm{a}}))$. In
addition, the sequence $(\bm{h})$ also satisfies condition $({\sf A})$ by
Lemma 3.5. Then, by Prop. 4.4, for any $\bm{a}\in{\mathcal{A}}$, the algebraic
set defined by ${\bm{H}}_{\bm{a}}$ is finite.

By Lemma 4.3, this implies that $V({\mathcal{S}}_{\bm{a}})$ contains finitely
many points in $\mathbb{C}^{s}\times\mathcal{U}$. This finishes our proof of
Prop. 4.1. ∎

Using techniques from (Elliott et al., 2020), one could give a simple
exponential upper bound the degree of a hypersurface containing the complement
of ${\mathcal{A}}$.

###  4.3. Finding extrema using proper maps

A real valued function $\psi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is proper at
$x\in\mathbb{R}$ if there exists an $\varepsilon>0$ such that
$\psi^{-1}([x-\varepsilon,x+\varepsilon])$ is compact. Such functions are of
interest because a proper polynomial restricted to a real algebraic set $W$
reaches extrema on each connected component of $W$. Using (Sakkalis, 2005, Thm
2.1 and Cor 2.2) one can construct proper polynomials in the following way.

Let
$F=F_{k}(x_{1},\dots,x_{n})+F_{k-1}(x_{1},\dots,x_{n})+\cdots+F_{0}(x_{1},\dots,x_{n}):\mathbb{R}^{n}\rightarrow\mathbb{R}$
be a real polynomial, where $F_{i}$ is the homogeneous component of degree $i$
of $F$. Assume further that the leading form $F_{k}$ of $F$ is positive
definite; then, $F$ is proper. In particular, the map
$P_{2m}+\sum_{i=0}^{2m-1}\lambda_{i}P_{i}$, with $P_{i}$ the Newton sums in
$x_{1},\dots,x_{n}$ and all $\lambda_{i}$ in $\mathbb{Q}$, is proper. We can
extend this to blocks of variables.

###### Lemma 4.5.

Let $\bm{z}_{1},\dots,\bm{z}_{k}$ be blocks of $t_{1},\dots,t_{k}$ variables,
respectively. If $P_{j,i}:=z_{1,i}^{j}+\cdots+z_{t_{i},i}^{j}$, then for any
$m_{1},\dots,m_{k}\geq 1$ and coefficients $\lambda_{i,j}$ in $\mathbb{Q}$,
the map

$\sum_{i=1}^{k}P_{2m_{i},i}+\sum_{i=1}^{k}\sum_{j=0}^{2m_{i}-1}\lambda_{j,i}P_{j,i}$

is proper.

##  5\. Main result

Let $\bm{f}=(f_{1},\ldots,f_{s})$ be a sequence of symmetric polynomials in
$\mathbb{Q}[x_{1},\dots,x_{n}]$ that satisfies condition (A). In this section
we present an algorithm and its complexity to decide whether the real locus of
$V(\bm{f})$ is empty or not.

To exploit the symmetry of $\bm{f}$ and to decide whether the set
$V_{\mathbb{R}}(\bm{f})$ is empty or not, our main idea is slicing the variety
$V(\bm{f})$ with hyperplanes which are encoded by a partition $\lambda$ of
$n$. This way, we obtain a new polynomial system which is invariant under the
action $S_{\lambda}:=S_{t_{1}}\times\cdots\times S_{t_{k}}$ of symmetric
groups. We proved in Lemma 3.4 that this new system also satisfies condition
(A). We then use the critical point method to decide whether the real locus of
the algebraic variety defined by this new system is empty or not by taking a
$S_{\lambda}$-invariant map as defined in the previous section.

###  5.1. Critical points along $S_{n}$-orbits

Let $\bm{g}=(g_{1},\dots,g_{s})$ be a sequence of $S_{\lambda}$-invariant
polynomials and $\phi$ be a $S_{\lambda}$-invariant map in
$\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$, with
$\bm{z}_{i}=(z_{1,i},\dots,z_{t_{i},i})$ for all $i$. As before, we set
$\ell=t_{1}+\cdots+t_{k}$, and we assume that $s\leq\ell$. Assume further that
the sequence $\bm{g}$ satisfies condition $({\sf A})$. Let $\phi$ be a
$S_{\lambda}$-invariant map in $\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$.

Let $\zeta_{\phi}$ and $\zeta_{\bm{g}}$ in
$\mathbb{Q}[\bm{e}_{1},\dots,\bm{e}_{k}]$, where
$\bm{e}_{i}=(e_{1,i},\dots,e_{t_{i},i})$ is a set of $t_{i}$ new variables, be
such that

$\phi=\zeta_{\phi}(\bm{E}_{1},\dots,\bm{E}_{k})\quad{\rm
and}\quad\bm{g}=\zeta_{\bm{g}}(\bm{E}_{1},\dots,\bm{E}_{k}).$

Here $\bm{E}_{i}=(E_{1,i},\dots,E_{t_{i},i})$ denotes the vector of elementary
symmetric polynomials in variables $\bm{z}_{i}$, with each $E_{j,i}$ having
degree $j$ for all $j,i$.

###### Lemma 5.1.

Let $\bm{g},\phi$, and $\lambda$ as above. Assume further that $\zeta_{\phi}$
has finitely many critical points on $V(\zeta_{\bm{g}})$. Then there exists a
randomized algorithm ${\sf Critical\\_points}$ $(\bm{g},\phi,\lambda)$ which
returns a zero-dimensional parametrization of the critical points of
$\zeta_{\phi}$ restricted to $V(\zeta_{\bm{g}})$. The algorithm uses

${O}{\,\tilde{}\,}\left(\delta^{2}c_{\lambda}(e_{\lambda}+c_{\lambda}^{5})n^{4}\Gamma\right)$

operations in $\mathbb{Q}$, where

$\displaystyle c_{\lambda}=\frac{\deg(g_{1})\cdots\deg(g_{s})\cdot
E_{\ell-s}(\delta-1,\dots,\delta-\ell)}{t_{1}!\cdots t_{k}!},$
$\displaystyle\Gamma=n^{2}{{n+\delta}\choose\delta}+n^{4}{{n}\choose{s+1}},\
{\rm and}$ $\displaystyle
e_{\lambda}=\frac{n(\deg(g_{1})+1)\cdots(\deg(g_{s})+1)\cdot
E_{\ell-s}(\delta,\dots,\delta-\ell+1)}{t_{1}!\cdots t_{k}!},$

with $\delta=\max(\deg(\bm{g}),\deg(\phi))$. The number of solutions is at
most $c_{\lambda}$.

###### Proof.

The ${\sf Critical\\_points}$ procedure contains two steps: first finding
$\zeta_{\bm{g}}$ and $\zeta_{\phi}$ from $\bm{g}$ and $\phi$ and then
computing a representation for the set $W(\zeta_{\phi},\zeta_{\bm{g}})$ of
critical points of $\zeta_{\phi}$ on $V(\zeta_{\bm{g}})$. The first step can
be done using the algorithm ${\sf Symmetric\\_Coordinates}$ from (Faugère et
al., 2023, Lemma 9), which uses
${O}{\,\tilde{}\,}\left({{\ell+\delta}\choose\delta}^{2}\right)$ operations in
$\mathbb{Q}$.

Since the sequence $\bm{g}$ satisfies condition $({\sf A})$, Lemma 3.6 implies
that $\zeta_{\bm{g}}$ also satisfies condition $({\sf A})$. Then, the set
$W(\zeta_{\phi},\zeta_{\bm{g}})$ is the zero set of $\zeta_{\bm{g}}$ and all
the $(s+1)$-minors of ${\rm Jac}(\zeta_{\bm{g}},\zeta_{\phi})$. In particular,
when $\ell=s$, $W(\zeta_{\phi},\zeta_{\bm{g}})=V(\zeta_{\bm{g}})$.

Since each $E_{j,i}$ has degree $j$, it is natural to assign a weight $j$ to
the variable $e_{j,i}$, so that the polynomial ring
$\mathbb{Q}[\bm{e}_{1},\dots,\bm{e}_{k}]$ is weighted of weights
$(1,\dots,t_{1},\dots,1,\dots,t_{k})$. The weighted degrees of
$\zeta_{\bm{g}}$ and $\zeta_{\phi}$ are then equal to those of $\bm{g}$ and
$\phi$, respectively. To compute a zero-dimensional parametrization for
$W(\zeta_{\phi},\zeta_{\bm{g}})$ we use the symbolic homotopy method for
weighted domain given in (Labahn et al., 2021, Thm 5.3) (see also (Faugère et
al., 2023, Sec 5.2) for a detailed complexity analysis). This procedure is
randomized and requires

${O}{\,\tilde{}\,}\left(\delta^{2}c_{\lambda}(e_{\lambda}+c_{\lambda}^{5})n^{4}\Gamma\right)\
{\rm operations\ in\ \mathbb{Q}}.$

Furthermore, results from (Labahn et al., 2021, Thm 5.3) also imply that the
number of points in the output is at most $c_{\lambda}$.

Thus, the total complexity of the ${\sf Critical\\_points}$ algorithm is then
${O}{\,\tilde{}\,}\left(\delta^{2}c_{\lambda}(e_{\lambda}+c_{\lambda}^{5})n^{4}\Gamma\right)$
operations in $\mathbb{Q}$. ∎

###  5.2. The Decide procedure

Consider a partition $\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ of $n$,
and let

$\mathscr{R}_{\lambda}=(v,v_{1,1},\dots,v_{t_{1},1},\dots,v_{1,k},\dots,v_{t_{k},k},\mu)$

be a parametrization which encodes a finite set
$W_{\lambda}\subset\mathbb{C}^{\ell}$. This set lies in the target space of
the algebraic map $F_{\lambda}:U_{\lambda}\rightarrow{\mathbb{C}}{}^{\ell}$
defined in Subsection 2.2 as

(6)
$\bm{u}=(\underbrace{u_{1,1},\dots,u_{1,1}}_{n_{1}},~{}\dots,~{}\underbrace{u_{t_{k},k},\dots,u_{t_{k},k}}_{n_{k}})\\\
\mapsto(E_{1,i}(u_{1,i},\dots,u_{t_{i},i}),\dots,E_{t_{i},i}(u_{1,i},\dots,u_{t_{i},i}))_{1\leq
i\leq k},$

where $E_{j,i}(u_{1,i},\dots,u_{t_{i},i})$ is the $j$-th elementary symmetric
function in $u_{1,i},\dots,u_{t_{i},i}$ for $i=1,\dots,k$ and
$j=1,\dots,t_{i}$.

Let $V_{\lambda}$ be the preimage of $W_{\lambda}$ by $F_{\lambda}$. In this
subsection we present a procedure called ${\sf Decide}(\mathscr{R}_{\lambda})$
which takes as input $\mathscr{R}_{\lambda}$, and decides whether the set
$V_{\lambda}$ contains real points.

In order to do this, a straightforward strategy consists in solving the
polynomial system to invert the map $F_{\lambda}$. Because of the group action
of $S_{t_{1}}\times\cdots\times S_{t_{k}}$, we would then obtain $t_{1}!\cdots
t_{k}!$ points in the preimage of a single point in $W_{\lambda}$: we would
lose the benefit of all that had been done before.

This difficulty can be bypassed by encoding one single point per orbit in the
preimage of the points in $W_{\lambda}$. This can be done via the following
steps.

  * (i)

Group together the variables $\bm{e}_{i}=(e_{1,i},\ldots,e_{t_{i},i})$ which
encode the values taken by the elementary symmetric functions
$E_{i,1},\ldots,E_{i,t_{i}}$ (see Sec. 2.2) and denote by
$v_{i,1},\ldots,v_{i,t_{i}}$ the parametrizations corresponding to
$e_{1,i},\ldots,e_{t_{i},i}$;

  * (ii)

Make a reduction to a bivariate polynomial system by considering the
polynomial with coefficients in $\mathbb{Q}[t]$

$\rho_{i}=v^{\prime}u^{t_{i}}-v_{1,i}u^{t_{i}-1}+\cdots+(-1)^{t_{i}}v_{t_{i},i}\in\mathbb{Q}[t][u]$

and “solving” the system $\rho_{i}=v=0$. Here we recall that
$v\in\mathbb{Q}[t]$ and is square-free, so that $v$ and $v^{\prime}$ are
coprime.

  * (iii)

It remains to decide whether, for all $1\leq i\leq k$, there is a real root
$\vartheta$ of $v$ such that when replacing $t$ by $\vartheta$ in $\rho_{i}$,
the resulting polynomial has all its roots real. To do this we proceed by
performing the following steps for $1\leq i\leq k$:

    1. (1)

first we compute the Sturm-Habicht sequence associated to
$\left(\rho_{i},\frac{\partial\rho_{i}}{\partial u}\right)$ in $\mathbb{Q}[t]$
(the Sturm-Habicht sequence is a signed subresultant sequence, see (Basu et
al., 2006, Chap. 9, Algo. 8.21));

    2. (2)

next, we compute Thom-encodings of the real roots of $v$, which is a way to
uniquely determine the roots of a univariate polynomial with real coefficients
by means of the signs of its derivatives at the considered real root (see e.g.
(Basu et al., 2006, Chap. 10, Algo. 10.14));

    3. (3)

finally, for each real root $\vartheta$ of $v$, evaluate the signed
subresultant sequence at $\vartheta$ (Basu et al., 2006, Chap. 10, Algo.
10.15) and compute the associated Cauchy index to deduce the number of real
roots of $\rho_{i}$ (see (Basu et al., 2006, Cor. 9.5)).

  * (iv)

For a given real root $\vartheta$ of $v$, it holds that, for all $1\leq i\leq
k$, the number of real roots of $\rho_{i}$ equals its degree, if and only if
$V_{\lambda}$ is non-empty.

The above steps describe our Decide, which returns false if $V_{\lambda}$
contains real points, else true.

###  5.3. The main algorithm

Our main algorithm ${\sf Real\\_emptiness}$ takes symmetric polynomials
$\bm{f}=(f_{1},\dots,f_{s})$ in $\mathbb{Q}[x_{1},\dots,x_{n}]$, with $s<n$,
which satisfy condition $({\sf A})$, and decides whether $V_{\mathbb{R}}(f)$
is empty.

For a partition $\lambda$, we first find the polynomials
$\bm{f}_{\lambda}:=\mathbb{T}_{\lambda}(\bm{f})$, which are
$S_{\lambda}$-invariant in $\mathbb{Q}[\bm{z}_{1},\dots,\bm{z}_{k}]$, where
$\mathbb{T}_{\lambda}$ is defined as in (2). By Corollary 3.4,
$\bm{f}_{\lambda}$ satisfies condition (A), so we can apply the results of
Section 4.

Let ${\phi}_{\mathfrak{a}}$ be the map defined in (5) and
${\mathcal{A}}_{\lambda}\subset{\mathbb{C}}{}^{t_{1}}\times\cdots\times{\mathbb{C}}{}^{t_{1}}$
be the non-zero Zariski open set defined in Proposition 4.1. Assume $\bm{a}$
is chosen in ${\mathcal{A}}_{\lambda}$ (this is one of the probabilistic
aspects of our algorithm) at step 1b. By Corollary 3.4, $\bm{f}_{\lambda}$
satisfies condition $({\sf A})$. Then, the critical locus of the restriction
of ${\phi}_{\bm{a}}$ to $V(\bm{f}_{\lambda})$ is of dimension at most zero (by
Proposition 4.1). In addition, the map ${\phi}_{\bm{a}}$ is invariant under
the action of the group $S_{\lambda}$.

Let $\zeta_{{\phi}_{\bm{a}}}$ and $\zeta_{\bm{f}_{\lambda}}$ in
$\mathbb{Q}[\bm{e}_{1},\dots,\bm{e}_{k}]$ such that

${\phi}_{\bm{a}}=\zeta_{{\phi}_{\bm{a}}}(\bm{E}_{1},\dots,\bm{E}_{k})\quad{\rm
and}\quad\bm{f}_{\lambda}=\zeta_{\bm{f}_{\lambda}}(\bm{E}_{1},\dots,\bm{E}_{k}).$

Here $\bm{E}_{i}=(E_{1,i},\dots,E_{t_{i},i})$ denotes the vector of elementary
symmetric polynomials in variables $\bm{z}_{i}$. In the next step, we compute
a zero-dimensional parametrization $\mathscr{R}_{\lambda}$ of the critical set
$W_{\lambda}:=W(\zeta_{{\phi}_{\bm{a}}},\zeta_{\bm{f}_{\lambda}})$ of
$\zeta_{{\phi}_{\bm{a}}}$ restricted to $V(\zeta_{\bm{f}_{\lambda}})$ by using
the ${\sf Critical\\_points}$ algorithm from Lemma 5.1. The parametrization
$\mathscr{R}_{\lambda}$ is given by a sequence of polynomials
$(v,v_{1,1},\dots,v_{t_{1},1},\dots,v_{1,k},\dots,v_{t_{k},k})$ in
$\mathbb{Q}[t]$ and a linear form $\mu$.

At the final step, we run the ${\sf Decide}(\mathscr{R}_{\lambda})$ in order
to determine whether the preimage of $W_{\lambda}$ by the map $F_{\lambda}$
contains real points.

Algorithm 1 ${\sf Real\\_emptiness}(\bm{f})$

  * Input: symmetric polynomials $\bm{f}=(f_{1},\dots,f_{s})$ in $\mathbb{Q}[x_{1},\dots,x_{n}]$ with $s<n$ such that $\bm{f}$ satisfies $({\sf A})$

  * Output: false if $V(\bm{f})\cap\mathbb{R}^{n}$ is non-empty; true otherwise

  1. (1)

for all partitions $\lambda=(n_{1}^{t_{1}}\,\dots\,n_{k}^{t_{k}})$ of $n$ of
length at least $s$, do

    1. (a)

compute $\bm{f}_{\lambda}=\mathbb{T}_{\lambda}(\bm{f})$, where
$\mathbb{T}_{\lambda}$ is defined in (2)

    2. (b)

using a chosen $\bm{a}\in{\mathcal{A}}$, where ${\mathcal{A}}$ is defined as
in Prop 4.1 , we construct ${\phi}_{\mathfrak{a}}$ as in (5) and then compute
${\phi}_{\bm{a}}$

    3. (c)

compute $\mathscr{R}_{\lambda}={\sf
Critical\\_points}({\phi}_{\bm{a}},\bm{f}_{\lambda})$

    4. (d)

run ${\sf Decide}(\mathscr{R}_{\lambda})$

    5. (e)

if ${\sf Decide}(\mathscr{R}_{\lambda})$ is false return false

  2. (2)

return true.

###### Proposition 5.2.

Assume that, on input symmetric $\bm{f}$ as above, and satisfying condition
(A), for all partitions $\lambda$ of length at least $s$, $\bm{a}$ is chosen
in ${\mathcal{A}}_{\lambda}$ and that all calls to the randomized algorithm
Critical_points return the correct result. Then Algorithm ${\sf
Real\\_emptiness}$ returns true if $V(\bm{f})\cap\mathbb{R}^{n}$ is empty and
otherwise it returns false.

###### Proof.

Since $\bm{f}$ satisfies condition $({\sf A})$, Lemma 3.4 implies that
$\bm{f}_{\lambda}$ also satisfies this condition. Then, by the Jacobian
criterion (Eisenbud, 2013, Thm 16.19), $V(\bm{f}_{\lambda})$ is smooth and
equidimensional of dimension $(\ell-s)$, where $\ell$ is the length of
$\lambda$. Therefore, if $\ell<s$, then the algebraic set
$V(\bm{f}_{\lambda})$ is empty. Thus, the union of
$V(\bm{f}_{\lambda})\cap{\mathcal{U}}_{\lambda}$ where
${\mathcal{U}}_{\lambda}$ is the open set defined in Subsection 4.1 and
$\lambda$ runs over the partitions of $n$ of length at least $s$, forms a
partition of $V(\bm{f})$. Hence, $V(\bm{f})\cap\mathbb{R}^{n}$ is non-empty if
and only if there exists at least one such partition for which
$V(\bm{f}_{\lambda})\cap{\mathcal{U}}_{\lambda}\cap\mathbb{R}^{n}$ is non-
empty.

We already observed that for all $\lambda$, $\bm{f}_{\lambda}$ does satisfy
condition $({\sf A})$. Since we have assumed that each time Step 1b is
performed, $\bm{a}$ is chosen in ${\mathcal{A}}_{\lambda}$, we apply
Proposition 4.4 to deduce that the conditions of Lemma 5.1 are satisfied.
Hence, all calls to Critical_points are valid.

Note that since we assume that all these calls return the correct result, we
deduce that their output encodes points which all lie in $V(\bm{f})$. Hence,
if $V(\bm{f})\cap\mathbb{R}^{n}$ is empty, applying the routine Decide on
these outputs will always return true and, all in all, our algorithm returns
true when $V(\bm{f})\cap\mathbb{R}^{n}$ is empty.

It remains to prove that it returns false when $V(\bm{f})\cap\mathbb{R}^{n}$
is non-empty. Note that there is a partition $\lambda$ such that
$V(\bm{f}_{\lambda})\cap\mathbb{R}^{n}$ is nonempty and has an empty
intersection with the complement of ${\mathcal{U}}_{\lambda}$. That is, all
connected components of $V(\bm{f}_{\lambda})\cap\mathbb{R}^{n}$ are in
${\mathcal{U}}_{\lambda}$.

Let $C$ be such a connected component. By Lemma 4.5, the map ${\phi}_{\bm{a}}$
is proper, and non-negative. Hence, its restriction to
$V(\bm{f}_{\lambda})\cap\mathbb{R}^{n}$ reaches its extremum at all connected
components of $V(\bm{f}_{\lambda})\cap\mathbb{R}^{n}$. This implies that the
restriction of ${\phi}_{\bm{a}}$ to $V(\bm{f}_{\lambda})$ has real critical
points which are contained in $C$ (and by Proposition 4.1 there are finitely
many). Those critical points are then encoded by the output of the call to
Critical_points (Step 1c) and false is returned. ∎

###  5.4. Complexity analysis

Let $d=\max(\deg(\bm{f}))$. First for a partition $\lambda$, applying
$\mathbb{T}_{\lambda}$ to $\bm{f}$ takes linear time in $O(n{{n+d}\choose
d})$, the number of monomials of $\bm{f}$ and the cost of Step 1b is nothing.
At the core of the algorithm, computing $\mathscr{R}_{\lambda}$ at Step 1c
requires
${O}{\,\tilde{}\,}\left(\delta^{2}c_{\lambda}(e_{\lambda}+c_{\lambda}^{5})n^{4}\Gamma\right)$
operations in $\mathbb{Q}$ by Lemma 5.1, where
$\delta=\max(d,\deg(\phi_{\bm{a}}))$. Also, the degree of
$\mathscr{R}_{\lambda}$ is at most $c_{\lambda}$.

In order to determine the cost of the Decide process at Step 1d, let $a$ be
the degree of $v$ and $b$ be the maximum of the partial degrees of
$\rho_{i}$’s w.r.t. $u$. By the complexity analysis of (Basu et al., 2006,
Algo. 8.21 ; Sec. 8.3.6), Step (1) above is performed within
$O\left(b^{4}a\right)$ arithmetic operations in $\mathbb{Q}[t]$ using a
classical evaluation interpolation scheme (there are $b$ polynomials to
interpolate, all of them being of degree $\leq 2ab$). Step (2) above requires
$O\left(a^{4}\log(a)\right)$ arithmetic operations in $\mathbb{Q}$ (see the
complexity analysis of (Basu et al., 2006, Algo 10.14; Sec. 10.4)). Finally,
in Step (3), we evaluate the signs of $b$ polynomials of degree $\leq 2ab$ at
the real roots of $v$ (of degree $a$) whose Thom encodings were just computed.
This is performed using $O\left(ba^{3}\left((\log(a)+b)\right)\right)$
arithmetic operations in $\mathbb{Q}$ following the complexity analysis of
(Basu et al., 2006, Algo 10.15; Sec. 10.4). The sum of these estimates lies in
$O\left(b^{4}a+ba^{4}\left((\log(a)+b)\right)\right)$.

Now, recall that the degree of $v$ is the degree of $\mathscr{R}_{\lambda}$,
so $a\leq c_{\lambda}$. The degree of $\rho_{i}$ w.r.t. $u$ equals $t_{i}$ and
$t_{i}\leq n$. This means $b\leq n$. All in all, we deduce that the total cost
of this final step lies in $O\left(n^{4}c_{\lambda}+n^{2}c_{\lambda}\right)$,
which is negligible compared to the previous costs.

In the worst case, one need to consider all the partitions of $n$ of length at
least $s$. Thus the total complexity of ${\sf Real\\_emptiness}$ is

$\sum_{\lambda,\ell\geq
s}{O}{\,\tilde{}\,}\left(\delta^{2}c_{\lambda}(e_{\lambda}+c_{\lambda}^{5})n^{4}\Gamma\right)$

operations in $\mathbb{Q}$. In addition, Lemma 34 in (Faugère et al., 2023)
implies that

$\sum_{\lambda,\ell\geq s}c_{\lambda}\leq c\ {\rm and}\ \sum_{\lambda,\ell\geq
s}e_{\lambda}\leq e,$

where $c=\deg(\zeta_{\bm{f}_{\lambda}})^{s}{{n+\delta-1}\choose n}\ {\rm and}\
e=n(\deg(\zeta_{\bm{f}_{\lambda}})+1)^{s}{{n+\delta}\choose n}$. Notice
further that ${{n+\delta}\choose\delta}\leq(n+1){{n+\delta-1}\choose d}$ and
$e=n(d+1)^{s}{{n+\delta}\choose n}\leq n(n+1)c^{5}$ for $\delta\geq 2$. In
addition, since $\deg(\phi_{\bm{a}})\leq\max(t_{i})+1\leq n$, the total cost
of our algorithm is

${O}{\,\tilde{}\,}\left(d^{2}n^{6}c^{6}\Gamma\right)={O}{\,\tilde{}\,}\left(d^{6s+2}n^{11}{{n+d}\choose
n}^{6}\left({{n+d}\choose n}+{{n}\choose{s+1}}\right)\right)$

operations in $\mathbb{Q}$.

###  5.5. An example

Let $n=4$ and $s=1$ with $\bm{f}=(f)$ where

$f=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}-6x_{1}x_{2}x_{3}x_{4}-1.$

Consider first the partition $\lambda=(4^{1})$. Then
$f_{\lambda}:=\mathbb{T}_{\lambda}(f)=-6z_{1,1}^{4}+4z_{1,1}^{2}-1$ which has
no real solution as $f_{\lambda}=-2z_{1,1}^{4}-(2z_{1,1}^{2}-1)^{2}<0$ for all
$z_{1,1}\in\mathbb{R}$.

Next we consider $\lambda=(2^{2})$. Then

$f_{(2^{2})}=2z_{1,1}^{2}+2z_{2,1}^{2}-6z_{1,1}^{2}z_{2,1}^{2}-1$

and we take $\phi=5(z_{1,1}^{2}+z_{2,1}^{2})-9(z_{1,2}+z_{2,1})-3$. In this
case $\zeta_{f_{(2^{2})}}~{}=~{}2e_{1,1}^{2}-6e_{2,1}^{2}-4e_{2,1}-1$ and
$\zeta_{\phi}=5e_{1,1}^{2}-9e_{1,1}-10e_{2,1}-3$. The critical points of
$\zeta_{\phi}$ restricted to $V(\zeta_{f_{(2^{2})}})$ are solutions to

$\zeta_{f_{(2^{2})}}=\det\big{(}{\rm
Jac}(\zeta_{f_{(2^{2})}},\zeta_{\phi})\big{)}=0,$

that is
$2e_{1,1}^{2}-6e_{2,1}^{2}-4e_{2,1}-1=120e_{1,1}e_{2,1}-108e_{2,1}-36=0$. A
zero-dimensional parametrization of these critical points is given by
$((v,v_{1,1},v_{2,1}),\mu)$, where

$\displaystyle v=200t^{4}-360t^{3}+62t^{2}+60t-27,$ $\displaystyle
v_{1,1}=t,{~{}\rm and~{}}$ $\displaystyle
v_{2,1}=-\frac{1}{6}t^{3}+\frac{9}{20}t^{2}-\frac{31}{600}t-1/20.$

At the final step, we check that the system

$\rho_{1}=v=0,\quad{\rm
with}\quad\rho_{1}=v^{\prime}u^{2}-v_{1,1}u+v_{2,1}\in\mathbb{Q}[t,u],$

has real solutions. This implies that $V_{\mathbb{R}}(f)$ is non-empty.

The output of our algorithm is consistent with the fact that the point
$(1,1,1/2,1/2)$ is in $V_{\mathbb{R}}(f)$.

##  6\. Topics for Future Research

Determining topological properties of a real variety $V_{\mathbb{R}}(\bm{f})$
is an important algorithmic problem. Here we have presented an efficient
algorithm to determine if $V_{\mathbb{R}}(\bm{f})$ is empty or not. More
generally, we expect that the ideas presented here may lead to algorithmic
improvements also in more refined questions, like computing one point per
connected component or the Euler characteristic for a real symmetric variety.
Furthermore, while our complexity gains are significant for symmetric input we
conjecture that we can do better in certain cases. In particular, when the
degree of the polynomials is at most $n$ then we expect we that a combination
with the topological properties of symmetric semi algebraic sets found in
(Basu and Riener, 2022, Prop 9) can reduce the number of orbits considered,
for example, instead of $n^{d}$ we might only need $n^{d/2}$ for fixed $d$.
Finally, a generalization to general symmetric semi algebraic sets should be
possible.

## References

  * (1)
  * Bank et al. (2015) B. Bank, M. Giusti, J. Heintz, G. Lecerf, G. Matera, and P. Solernó. 2015\.  Degeneracy loci and polynomial equation solving.  _Foundations of Computational Mathematics_ 15, 1 (2015), 159–184.
  * Bank et al. (1997) B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. 1997\.  Polar varieties and efficient real equation solving: the hypersurface case.  _Journal of Complexity_ 13, 1 (1997), 5–27.
  * Bank et al. (2001) B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. 2001\.  Polar varieties and efficient real elimination.  _Mathematische Zeitschrift_ 238, 1 (2001), 115–144.
  * Bank et al. (2009) B. Bank, M. Giusti, J. Heintz, and L.M. Pardo. 2009\.  On the intrinsic complexity of point finding in real singular hypersurfaces.  _Inform. Process. Lett._ 109, 19 (2009), 1141–1144.
  * Bank et al. (2004) B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. 2004\.  Generalized polar varieties and efficient real elimination procedure.  _Kybernetika_ 40, 5 (2004), 519–550.
  * Bank et al. (2005) B. Bank, M. Giusti, J. Heintz, and L.-M. Pardo. 2005\.  Generalized polar varieties: Geometry and algorithms.  _Journal of complexity_ (2005).
  * Bank et al. (2014) B. Bank, M. Giusti, J. Heintz, and M. Safey El Din. 2014\.  Intrinsic complexity estimates in polynomial optimization.  _Journal of Complexity_ 30, 4 (2014), 430–443.  https://doi.org/10.1016/j.jco.2014.02.005
  * Basu et al. (1996) S. Basu, R. Pollack, and M.-F. Roy. 1996.  On the combinatorial and algebraic complexity of quantifier elimination.  _Journal of ACM_ 43, 6 (1996), 1002–1045.
  * Basu et al. (2006) S. Basu, R. Pollack, and M.-F. Roy. 2006.  _Algorithms in real algebraic geometry_ (second edition ed.).  Springer-Verlag.  online version (2008).
  * Basu and Riener (2017a) S. Basu and C. Riener. 2017a.  Bounding the equivariant Betti numbers of symmetric semi-algebraic sets.  _Advances in Mathematics_ 305 (2017), 803–855.  https://doi.org/10.1016/j.aim.2016.09.015
  * Basu and Riener (2017b) S. Basu and C. Riener. 2017b.  Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets. In _Ordered Algebraic Structures and Related Topics: International Conference on Ordered Algebraic Structures and Related Topics, October 12–16, 2015, Centre International de Rencontres Mathématiques (CIRM), Luminy, France_ , Vol. 697. American Mathematical Soc. Providence, Rhode Island, 53–81.
  * Basu and Riener (2022) S. Basu and C. Riener. 2022\.  Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets.  _Foundations of Computational Mathematics_ 22, 5 (2022), 1395–1462.
  * Brown and Davenport (2007) C. W. Brown and J. H. Davenport. 2007.  The complexity of quantifier elimination and cylindrical algebraic decomposition. In _Proceedings of the 2007 international symposium on Symbolic and algebraic computation_. 54–60.
  * Busé and Karasoulou (2016) L. Busé and A. Karasoulou. 2016.  Resultant of an equivariant polynomial system with respect to the symmetric group.  _Journal of Symbolic Computation_ 76 (2016), 142–157.
  * Canny (1987) J. Canny. 1987.  _The complexity of robot motion planning_.  MIT Press.
  * Chen et al. (2010) C. Chen, J. H. Davenport, J. P. May, M. M. Maza, B. Xia, and R. Xiao. 2010\.  Triangular decomposition of semi-algebraic systems. In _Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation_. 187–194.
  * Chen et al. (2009) C. Chen, M. M. Maza, B. Xia, and L. Yang. 2009\.  Computing cylindrical algebraic decomposition via triangular decomposition. In _Proceedings of the 2009 international symposium on Symbolic and algebraic computation_. 95–102.
  * Colin (1997) A. Colin. 1997.  Solving a system of algebraic equations with symmetries.  _Journal of Pure and Applied Algebra_ 117-118 (1997), 195 – 215\.  https://doi.org/10.1016/S0022-4049(97)00011-X
  * Collins (1975) G. E. Collins. 1975\.  Quantifier elimination for real closed fields by cylindrical algebraic decomposition.  _Lecture notes in computer science_ 33 (1975), 515–532.
  * Davenport and Heintz (1988) J. H. Davenport and J. Heintz. 1988.  Real quantifier elimination is doubly exponential.  _Journal of Symbolic Computation_ 5, 1-2 (1988), 29–35.
  * Dines (1919) L. L. Dines. 1919\.  Systems of linear inequalities.  _Annals of Mathematics_ (1919), 191–199.
  * Eisenbud (2013) D. Eisenbud. 2013\.  _Commutative algebra: with a view toward algebraic geometry_. Vol. 150.  Springer Science & Business Media.
  * Elliott et al. (2020) J. Elliott, M. Giesbrecht, and É. Schost. 2020\.  On the bit complexity of finding points in connected components of a smooth real hypersurface. In _Proceedings of ISSAC 2020_. ACM, 170–177.
  * England et al. (2020) M. England, R. Bradford, and J. H. Davenport. 2020.  Cylindrical algebraic decomposition with equational constraints.  _Journal of Symbolic Computation_ 100 (2020), 38–71.
  * Faugère et al. (2023) J.-C. Faugère, G. Labahn, M. Safey El Din, É. Schost, and T. X. Vu. 2023.  Computing critical points for invariant algebraic systems.  _Journal of Symbolic Computation_ 116 (2023), 365–399.
  * Faugère and Rahmany ([n. d.]) J.-C. Faugère and S. Rahmany. [n. d.].  Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases. In _Proceedings of ISSAC 2009_.  https://hal.archives-ouvertes.fr/hal-01294702
  * Faugère et al. (2012) J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. 2012\.  Critical Points and Gröbner Bases: The Unmixed Case. In _Proceedings of ISSAC 2012_. ACM, 162–169.  https://doi.org/10.1145/2442829.2442855
  * Faugère and Svartz (2012) J.-C. Faugère and J. Svartz. 2012.  Solving Polynomial Systems Globally Invariant Under an Action of the Symmetric Group and Application to the Equilibria of N Vortices in the Plane. In _Proceedings of ISSAC 2012_. ACM, 170–178.  https://doi.org/10.1145/2442829.2442856
  * Fourier (1826) J. B. J. Fourier. 1826\.  Solution d’une question particuliere du calcul des inégalités.  _Nouveau Bulletin des Sciences par la Société philomatique de Paris_ 99 (1826), 100.
  * Gatermann and Parrilo (2004) K. Gatermann and P. A. Parrilo. 2004.  Symmetry groups, semidefinite programs, and sums of squares.  _Journal of Pure and Applied Algebra_ 192, 1-3 (2004), 95–128.
  * Giusti et al. (2001) M. Giusti, G. Lecerf, and B. Salvy. 2001.  A Gröbner Free Alternative for Polynomial System Solving.  _Journal of Complexity_ 17, 1 (2001), 154–211.
  * Grigoriev and Vorobjov (1988) D. Grigoriev and N. Vorobjov. 1988.  Solving systems of polynomials inequalities in subexponential time.  _Journal of Symbolic Computation_ 5 (1988), 37–64.
  * Hauenstein et al. (2021) J. D. Hauenstein, M. Safey El Din, É. Schost, and T. X. Vu. 2021.  Solving determinantal systems using homotopy techniques.  _Journal of Symbolic Computation_ 104 (2021), 754–804.  https://doi.org/10.1016/j.jsc.2020.09.008
  * Heintz et al. (1993) J. Heintz, M.-F. Roy, and P. Solernò. 1993.  On the theoretical and practical complexity of the existential theory of the reals.  _Comput. J._ 36, 5 (1993), 427–431.
  * Hong (1992) H. Hong. 1992.  Heuristic Search Strategies for Cylindrical Algebraic Decomposition. In _Proceedings of Artificial Intelligence and Symbolic Mathematical Computing, Springer Lecture Notes in Computer Science 737_. 152–165.
  * Labahn et al. (2021) G. Labahn, M. Safey El Din, É. Schost, and T. X. Vu. 2021\.  Homotopy techniques for solving sparse column support determinantal polynomial systems.  _Journal of Complexity_ 66 (2021), 101557.
  * McCallum (1984) S. McCallum. 1984\.  _An improved projection operator for Cylindrical Algebraic Decomposition_.  Ph. D. Dissertation. University of Wisconsin-Madison.
  * McCallum (1999) S. McCallum. 1999\.  On projection in CAD-based quantifier elimination with equational constraint. In _Proceedings of ISSAC 1999_. ACM, 145–149.
  * Perminov and Shakirov (2009) N. Perminov and Sh. Shakirov. 2009.  Discriminants of symmetric polynomials.  _arXiv preprint arXiv:0910.5757_ (2009).
  * Renegar (1992) J. Renegar. 1992\.  On the computational complexity and geometry of the first order theory of the reals.  _Journal of Symbolic Computation_ 13, 3 (1992), 255–352.
  * Riener (2012) C. Riener. 2012\.  On the degree and half-degree principle for symmetric polynomials.  _Journal of Pure and Applied Algebra_ 216, 4 (2012), 850 – 856.  https://doi.org/10.1016/j.jpaa.2011.08.012
  * Riener (2016) C. Riener. 2016\.  Symmetric semi-algebraic sets and non-negativity of symmetric polynomials.  _Journal of Pure and Applied Algebra_ 220, 8 (2016), 2809 – 2815.  https://doi.org/10.1016/j.jpaa.2015.12.010
  * Riener and Safey el Din (2018) C. Riener and M. Safey el Din. 2018.  Real Root Finding for Equivariant Semi-Algebraic Systems. In _Proceedings of ISSAC 2018_. ACM, 335–342.  https://doi.org/10.1145/3208976.3209023
  * Riener et al. (2013) C. Riener, T. Theobald, L. J. Andrén, and J. B. Lasserre. 2013\.  Exploiting symmetries in SDP-relaxations for polynomial optimization.  _Mathematics of Operations Research_ 38, 1 (2013), 122–141.
  * Safey El Din and Schost (2003) M. Safey El Din and É. Schost. 2003.  Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In _Proceedings of ISSAC 2003_. ACM, 224–231.
  * Safey El Din and Schost (2018) M. Safey El Din and É. Schost. 2018.  Bit complexity for multi-homogeneous polynomial system solving - Application to polynomial minimization.  _Journal of Symbolic Computation_ 87 (2018), 176–206.  https://doi.org/10.1016/j.jsc.2017.08.001
  * Safey El Din and Spaenlehauer (2016) M. Safey El Din and P.-J. Spaenlehauer. 2016.  Critical Point Computations on Smooth Varieties: Degree and Complexity Bounds. In _Proceedings of ISSAC 2016_. ACM, 183–190.  https://doi.org/10.1145/2930889.2930929
  * Sakkalis (2005) T. Sakkalis. 2005\.  A note on proper polynomial maps.  _Communications in Algebra_ 33, 9 (2005), 3359–3365.
  * Shafarevich and Reid (1994) I. R. Shafarevich and M. Reid. 1994.  _Basic algebraic geometry_. Vol. 2.  Springer.
  * Spaenlehauer (2014) P.-J. Spaenlehauer. 2014\.  On the Complexity of Computing Critical Points with Gröbner Bases.  _SIAM Journal on Optimization_ 24, 3 (2014), 1382–1401.
  * Strzeboński (2006) A. W. Strzeboński. 2006\.  Cylindrical algebraic decomposition using validated numerics.  _Journal of Symbolic Computation_ 41, 9 (2006), 1021–1038.
  * Strzeboński (2014) A. W. Strzeboński. 2014\.  Cylindrical algebraic decomposition using local projections. In _Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation_. 389–396.
  * Sturmfels (2008) B. Sturmfels. 2008\.  _Algorithms in Invariant Theory (Texts and Monographs in Symbolic Computation)_ (2nd ed.; vii, 197 pp.; 5 figs. ed.).  Springer Publishing Company, Incorporated.
  * Tarski (1948) A. Tarski. 1948\.  _A Decision Method for Elementary Algebra and Geometry_.  The Rand Corporation, Santa Monica, Calif. iii+60 pages.
  * Timofte (2003) V. Timofte. 2003\.  On the positivity of symmetric polynomial functions.: Part I: General results.  _J. Math. Anal. Appl._ 284, 1 (2003), 174 – 190.  https://doi.org/10.1016/S0022-247X(03)00301-9