# Bounds on the infimum of polynomials over a generic semi-algebraic set using
asymptotic critical values

Boulos El Hilany Institut für Analysis und Algebra, TU Braunschweig, Germany,
<EMAIL_ADDRESS><EMAIL_ADDRESS>Elias Tsigaridas Inria
Paris and Institut de Mathématiques de Jussieu–Paris Rive Gauche, Sorbonne
Université and Paris Université<EMAIL_ADDRESS>
###### Abstract

We present precise bit and degree estimates for the optimal value of the
polynomial optimization problem
$f^{*}:=\inf_{x\in\mathscr{X}}\leavevmode\nobreak\ f(x)$, where $\mathscr{X}$
is a semi-algebraic set satisfying some non-degeneracy conditions. Our bounds
depend on the degree, the bitsize of $f$, and the polynomials defining
$\mathscr{X}$, and are single exponential with respect to the number of
variables. They generalize the single exponential bounds from Jeronimo,
Perrucci, and Tsigaridas (SIAM Journal on Optimization, 23(1):241–255, 2013)
for the minimum of a polynomial function on a compact connected component of a
basic closed semi-algebraic set.

The tools that we use allow us to obtain specialized bounds and dedicated
algorithms for two large families of polynomial optimization problems in which
the optimum value might not be attained. The first family forms a dense set of
real polynomial functions with a fixed collection of Newton polytopes; we
provide the best approximation yet for the bifurcation set, which contains the
optimal value, and we deduce an effective method for computations. As for the
second family, we consider any unconstrained polynomial optimization problem;
we present more precise bounds, together with a better bit complexity estimate
of an algorithm to compute the optimal value.

_K_ eywords asymptotic critical value $\cdot$ bifurcation set $\cdot$
polynomial optimization $\cdot$ unconstrained polynomial optimization $\cdot$
Newton polytope $\cdot$ bit complexity

###### Contents

  1. 1 Introduction
    1. 1.1 Presentation of the main results
    2. 1.2 Organization of the paper and proof strategies
    3. 1.3 Notation
  2. 2 Critical values at infinity and bounds on the infimum
    1. 2.1 The bifurcation and Rabier sets
    2. 2.2 A decomposition of a (complete) semi-algebraic set
  3. 3 Constrained optimization and asymptotic critical values
    1. 3.1 Asymptotic critical values over a smooth variety $X\subset\mathbb{C}^{n}$
      1. 3.1.1 Resultant systems using determinants
      2. 3.1.2 Bounding the asymptotic critical values using resultant systems
  4. 4 The Newton non-degenerate case
    1. 4.1 Preliminaries on polytopes
    2. 4.2 Application to polynomial functions
    3. 4.3 Bounding the infimum
  5. 5 Unconstrained optimization and asymptotic critical values
    1. 5.1 Asymptotic critical values over $\mathbb{C}^{n}$
    2. 5.2 Polynomial optimization over $\mathbb{R}^{n}$
  6. A Useful results and bounds
    1. A.1 Multivariate polynomial multipication
    2. A.2 Intersecting a variety
    3. A.3 Reduction to a square system

##  1 Introduction

Let $f:\mathscr{X}\longrightarrow\mathbb{R}$ be a semi-algebraic function over
a basic semi-algebraic set $\mathscr{X}\subset\mathbb{R}^{n}$. We consider the
problem of computing effective bounds on the infimum
$f^{*}:=\inf_{x\in\mathscr{X}}f(x)$, assuming it lies in $\mathbb{R}$, as a
function of the number of variables, the number of polynomials defining the
semialgebraic set, their degrees and bitsize.

######  Problem 1.

The optimal value of the polynomial optimization problem
$f^{*}=\inf_{x\in\mathscr{X}}f(x)$ is a real algebraic number, when the
defining polynomials have rational coefficients. Provide an effective lower
bound on its value and an upper bound on degree of the defining polynomial
that depend on the number of variables $n$, the degrees, and the coefficient
(bit)size of $f$ and the polynomials defining $\mathscr{X}$.

The computation of effective, explicit, and if possible (asymptotically)
optimal bounds on the size and degree of the optimal value is an important
problem on its own, as these are intrinsic quantities of the polynomial
optimization problem that characterize and measure its difficulty.
Furthermore, they are fundamental quantities for the analysis of various
symbolic and numerical algorithms, with a wide range of applications, e.g.,
[44, 40, 5, 28]. As the optimal value is an algebraic number, the degree of
the defining polynomial is essential in complexity statements, as it measures
the algebraic complexity of the problem, e.g., [10, 1].

If the semi-algebraic subset $\mathscr{X}$ is compact, then the infimum of $f$
is attained at $\mathscr{X}$. In this case, explicit bounds for Problem 1 and
an effective method for computing the infimum already exist. Namely, if
$\mathscr{X}$ is defined by $r$ equalities, $s$ inequalities with polynomials
in $\mathbb{Z}[x_{1},\ldots,x_{n}]$, having degrees at most $d$, and
coefficients of absolute values at most $H$, then either $f^{*}$ is not
reached over $\mathscr{X}$, or is an algebraic number of degree at most

$\max_{0\leq i\leq\min\\{r+s,n\\}}{n\choose i}d^{i}(d-1)^{n-i}\leq
2^{n-1}d^{n},$ (1)

and if it is not zero, then

$|f^{*}|\geq(2^{5-\frac{n}{2}}\tilde{H}d^{n})^{-n2^{n}d^{n}},$ (2)

where $\tilde{H}:=\max(H,\leavevmode\nobreak\ n+r+s)$ [24, Theorem 1.1]. If we
let $H\leq 2^{\tau}$, then $|f^{*}|\geq
2^{-\widetilde{\mathcal{O}}(nd^{n}\tau)}$. We notice that the bound is single
exponential with respect to the number of variables; hence polynomial when the
number of variables is fixed. Even more, it is (asymptotically) optimal.
Jeronimo et al [24] proved the inequality in (2) by bounding the isolated
roots of carefully deformed polynomial systems; this was the first precise
bound for the optimum value of the polynomial optimization problem. While the
initial motivation in [24] was to approximate the minimum distance between two
semi-algebraic sets, the bounds has already several other applications, e.g.,
[44, 40]. Let us also mention that there is also an efficient (symbolic)
algorithm to compute it due to Jeronimo and Perrucci [23].

While the bound of (2) is quite important, the assumption that the optimum
value is attained is rather restrictive in several problems and applications.
Not all semi-algebraic functions attain their infima; as an example, consider
the infimum of the function $x\mapsto 1/x$ over $\\{x>0\\}$ is $0$. We make a
step towards closing this gap in the literature by considering the Problem 1
where $f$ admits a non-trivial infimum $f^{*}\in\mathbb{R}$, but it is not
attained on $\mathscr{X}$; under some assumptions on $\mathscr{X}$ that we
detail in the sequel. The computation of the optimum value, both in the
_”attained”_ and in the _”unattained”_ case, appears frequently in science and
engineering. Namely, systems and problems in applications, e.g., computer
aided design [16], robotics [43], control systems [26], to mention a few, are
modeled as semi-algebraic subsets, and so a recurring task is to decide
whether two semi-algebraic subsets are disjoint, e.g., [41]. One approach to
solve this problem is to figure out whether the images (under the same
function) of the two semi-algebraic sets are disjoint or not. Accordingly, if
the infimum of one function is larger than the maximum of the other, the two
semi-algebraic sets are disjoint.

A straightforward algorithm to compute the optimum value of Problem 1 is to
use (the general purpose approach of) cylindrical algebraic decomposition
(CAD) for stratifying semi-algebraic projections, e.g. [7]. However, this
approach requires us to compute many algebraic objects that are possibly
unnecessary, as it relies on repeated projections. Even more, it has a worst-
case complexity that is double exponential in the number of variables [3, 4].
It will also result double exponential bounds for the optimal value(s),
$f^{*}$. Another approach consists in describing the problem as a general
decision problem for the theory of reals and then perform quantifier
elimination [2]. However, it is not clear, at least to us, what is the optimal
formulation in this setting and how to obtain precise bit and degree
estimates. We opt for a different approach.

We provide effective bounds on the infimum $f^{*}$ of a semi-algebraic
function $\mathscr{X}\longrightarrow\mathbb{R}$, when the polynomials involved
in $\mathscr{X}$ satisfy a non-degeneracy condition. The bound is single
exponential with respect to the number of variables (Theorem 1). Up to the
non-degeneracy assumptions, our contribution fills the gap in the literature
for Problem 1 and to the best of our knowledge is the first bound for when the
optimal value is not attained.

Our approach builds on the works of Jelonek and Kurdyka [21, 20] and Jelonek
and Tibăr [22] for approximating the _bifurcation set at infinity_ ,
$\mathcal{B}^{\infty}_{f}$ of a polynomial function $f$ [45, 47, 51]. The set
$\mathcal{B}^{\infty}_{f}$ is the smallest set of values, outside of which $f$
is a locally trivial $\mathcal{C}^{\infty}$-fibration “at infinity” (i.e.,
outside a large ball), and has been a subject of intensive study in the last
fifty years, e.g., [47]. Clearly, the set $\mathcal{B}^{\infty}_{f}$ contains
the infimum $f^{*}$ of a real polynomial function. Consequently, and for a
plethora of other reasons, it remains an important open problem to derive an
efficient algorithm to compute $\mathcal{B}^{\infty}_{f}$ for any polynomial
function $f$ [47, 51]. The results of Jelonek, Kurdyka, and Tibăr lead to an
efficient computation of the set of points, $\mathcal{K}^{\infty}_{f}$, called
_Rabier set_ of $f$, or the _asymptotic critical values_ of $f$, as

$\displaystyle\mathcal{K}^{\infty}_{f}:=$ $\displaystyle\leavevmode\nobreak\
\big{\\{}z\in\mathbb{R}\leavevmode\nobreak\ |\leavevmode\nobreak\
\exists\\{\bm{x}_{\ell}\\}_{\ell\in\mathbb{N}}\subset X,\leavevmode\nobreak\
\|\bm{x}_{\ell}\|\underset{\ell\rightarrow\infty}{\longrightarrow}\infty,\leavevmode\nobreak\
\|\bm{x}_{\ell}\|\cdot\|\operatorname{grad}f(\bm{x}_{\ell})\|\longrightarrow
0,\leavevmode\nobreak\ f(\bm{x}_{\ell})\longrightarrow z\big{\\}}.$ (3)

This is a finite set that contains $\mathcal{B}^{\infty}_{f}$, that is
$\mathcal{B}^{\infty}_{f}\subseteq\mathcal{K}^{\infty}_{F}$ [35]. Therefore,
these important results provide new computational tools for $f^{*}$. There are
several related methods dedicated in computing $\mathcal{B}^{\infty}_{f}$ for
large families of polynomial functions (e.g., [31, 54, 34]). We build on
methods that require the fewer possible assumptions on the input (polynomial)
functions.

One of our contributions is generalize the previous techniques from polynomial
functions to semi-algebraic functions. In this way, we derive the best known
estimates for bounds on $f^{*}$, and develop algorithms to compute $f^{*}$ in
two important special cases of Problem 1.

The first (special) case considers the semi-algebraic set $\mathscr{X}$ of
Problem 1 to be a real affine variety that satisfies a mild non-degeneracy
condition. This condition (Theorem 18) applies for a dense family of functions
sharing the same collection of Newton polytopes and gives rise to functions
having a non-trivial bifurcation set. We present single exponential bit and
degree bounds for $f^{*}$ and we introduce an algorithm to compute it with
precise (single exponential) bit complexity estimates. This algorithm computes
directly the bifurcation set and exploits the collection of Newton polytopes
of the input polynomials. In this way, we avoid to compute the larger set of
critical values at infinity and we also exploit the sparsity of the input
polynomials. To the best of our knowledge, prior to our work, there was no
dedicated algorithm to compute the infimum of real polynomial functions above.

The second (special) case is the unconstrained polynomial optimization
problem, that is when $\mathscr{X}=\mathbb{R}^{n}$. An effective algorithm for
approximating $\mathcal{K}^{\infty}_{f}$ (together with its arithmetic
complexity analysis, and a method for computing $f^{*}$) was developed by
Safey El Din [38]. As was pointed out by Jelonek and Tibăr [22], this would
only provide a subset of $\mathcal{K}^{\infty}_{f}$. We present single
exponential (bit and degree) bounds for $f^{*}$ and a probabilistic algorithm
to compute it, that is based on [20] and makes no assumptions on the input
(Theorem 25) along with precise (single exponential) bit complexity estimates.
Even though a method for computing $f^{*}$ exists [38], to the best of our
knowledge, neither bit/degree bounds were known before, nor precise bit
complexity estimates for an algorithm to compute it; without any assumptions
on the input.

In the rest of this section we present in detail the theorems that support our
bounds for $f^{*}$ and the corresponding algorithms, along with a bird’s eye
view of the proof techniques that we employ.

###  1.1 Presentation of the main results

We denote by $\mathcal{O}$, resp. $\mathcal{O}_{B}$, the arithmetic, resp.
bit, complexity and we use the soft-O notations, $\widetilde{\mathcal{O}}$,
respectively $\widetilde{\mathcal{O}}_{B}$, to ignore (poly-)logarithmic
factors. We refer to § 1.3 for further details on the notation that we use.

Let $\mathscr{X}\subset\mathbb{R}^{n}$ be a semi-algebraic defined by a set of
polynomials $\bm{f}\subset\mathbb{R}[x_{1},\ldots,x_{n}]$. We call
$\mathscr{X}$ _complete_ if it is closed, connected, and for each subset
$\bm{g}\subseteq\bm{f}$, the variety
$\mathbb{V}(\bm{g})=\left\\{\bm{x}\in\mathbb{C}^{n}\mathrel{\left|\vphantom{\bm{x}\in\mathbb{C}^{n}g(\bm{x})=0,\text{
for all }g\in\bm{g}}\right.}g(\bm{x})=0,\text{ for all
}g\in\bm{g}\right\\}\subset\mathbb{C}^{n}$ is a complete intersection and
smooth; the latter conditions means that the Jacobian of $\bm{g}$ evaluated at
the points of $\mathbb{V}(\bm{g})$ has full rank.

The following theorem provides bit and degree bounds for the infimum of
Problem 1 when $\mathscr{X}$ is complete.

######  Theorem 1.

Let $\mathscr{X}$ be a complete semi-algebraic set given by polynomial
(in)equalities

$\mathscr{X}:=\\{g_{1}=\cdots=g_{r}=0,\leavevmode\nobreak\
g_{r+1},\ldots,g_{s}\geq 0,\leavevmode\nobreak\ g_{1},\ldots
g_{s}\in\mathbb{R}[x_{1},\ldots,x_{n}]\\},$

let $F:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ be a polynomial function of
degree $d_{1}$, and assume that the infimum $f^{*}$ of the function
$f:=\left.F\right|_{\mathscr{X}}:\mathscr{X}\longrightarrow\mathbb{R}$ is not
attained. Then $f^{*}$ is an algebraic number of degree
$\mathcal{O}((nrd_{1})^{n^{2}})$, such that $2^{-\eta}\leq|f^{*}|\leq
2^{\eta}$, where $d=\max\\{\deg g_{1},\ldots,\deg g_{s}\\}$ and

$\displaystyle\eta:=$ $\displaystyle\leavevmode\nobreak\
\widetilde{\mathcal{O}}(r(d+n+\tau)+d_{1})(nrd_{1})^{n^{2}}).$

If we compare the bounds of the minimum induced by Eq. (1) and (2) with the
bounds on the infimum of the previous theorem, then we notice that both bounds
are single exponential with respect to the number of variables. However, the
bound of Theorem 1 admits a worse exponent, $n^{2}$ instead of $n$. It is
worth noting that the dependence, in both cases, in the number of polynomials
and the degrees is polynomial.

To give an overview of the approach that we follow to prove Theorem 1, let
$X\subset\mathbb{R}^{n}$ be a real affine variety. Then, for every
$z\in\mathbb{R}$ close enough to $f^{*}$, the preimage $f^{-1}(z)$ is empty if
$z<f^{*}$. Hence, the infimum $f^{*}$ is a point in
$\mathcal{B}^{\infty}_{f}$. Since we have the inclusion

$\mathcal{B}^{\infty}_{f}\subseteq\mathcal{K}^{\infty}_{f},$ (4)

we can compute $\mathcal{K}^{\infty}_{f}$ instead. Notice that the previous
inclusion can be sharp for some functions [51, Example 3.8].

A straightforward analogue of the bifurcation set at infinity does not exist
for arbitrary semi-algebraic sets $\mathscr{X}$. Because of this, we decompose
$\mathscr{X}$ from Theorem 1 into finitely-many semi-algebraic subsets and
consider their real Zariski closures, which we assume to be smooth and
irreducible. For each such algebraic $X\subset\mathbb{R}^{n}$, we show that
the infimum $f^{*}$ belongs to the bifurcation set of the restricted
polynomial function $\left.F\right|_{X}$, where $F$ is the canonical extension
of $f$ to the space $\mathbb{R}^{n}$ (Theorem 8). Then, we can approximate the
bifurcation set at infinity by the Rabier set of $\left.F\right|_{X}$. This
way, we can then use effective methods developed in [21], to compute a
superset of the Rabier set.

Using the above description, one can extract lower bounds on the infimum;
roughly speaking, following [21], we express the Rabier set as the
intersection of (the closure of) the image of a polynomial map with a linear
subspace. This results in a univariate polynomial whose real roots include the
infimum. Since the number of polynomials in the process is much larger than
the number of variables, we should avoid using Gröbner basis computations,
because it is difficult to bound their (bit) complexity and, even worse, they
might induce double exponential bounds on the degree and bitsize of the
resulting polynomial. Instead, we use resultant systems, e.g. [48, 53] which
can express the image of the polynomial map using minors of a Macaulay-type
matrix whose size exploits the single exponential bounds of the effective
Nullstellensatz. In this way, we bound the degree and bitsize of the
univariate polynomial that has the infimum among its real roots. A
straightforward algorithm based on this approach still has double exponential
complexity. However, our goal is not to compute the infimum, but to bound it.

The algorithms tailored for $\mathcal{K}^{\infty}_{f}$ [21] have prohibitive
complexity, mainly because the require the computation of exponentially many
minors of a Jacobian matrix (see §3 for details). This will result in double
exponential complexity bound for an algorithm to compute $f^{*}$. However, if
we impose some conditions on the semi-algebraic function, then might be able
to overcome this computational obstacle. Indeed we present two such important
special cases where this is possible and where not only we present improved
(compared to Theorem 1) lower bounds, but also efficient algorithms for
$f^{*}$, supported by precise bit complexity estimates.

#### Unconstrained polynomial optimization

Consider $\mathscr{X}=\mathbb{R}^{n}$. Then, we can approximate the Rabier set
by considering the _complexification_
$\mathbb{C}f:\mathbb{C}^{n}\longrightarrow\mathbb{C}$ of the polynomial
function $f:\mathbb{R}^{n}\longrightarrow\mathbb{R}$, which simply extends the
domain of $f$. Jelonek and Kurdyka in [20] presented one of the first methods
for computing $\mathcal{K}^{\infty}_{f}$, while there are also other similar
approaches and implementations [21, 37, 22]. Based on [20], we present an
algorithm (Alg. 1) in §5, where we exploit resultants instead of Gröbner basis
to perform algebraic elimination. Note that, once we compute
$\mathcal{K}^{\infty}_{f}$, then we can identify the infimum by testing the
non-emptiness of fibers in generic points of the intervals
$\mathbb{R}\setminus\mathcal{K}^{\infty}_{f}$ [38]. A precise analysis of the
degenerate conditions and bound on the bitsize of the algebraic objects
involved in the computation of Alg. 1 lead to the following theorem for
bounding and computing $f^{*}\in\mathcal{K}^{\infty}_{f}$.

######  Theorem 2 (Theorem 25).

Let $f\in\mathbb{Z}[x]$ be of degree $d$ and bitsize $\tau$. Then,
$f^{*}=\min_{\bm{x}\in\mathbb{R}^{n}}f(\bm{x})$ is an algebraic number of
degree $\mathcal{O}(d^{n-1})$, such that

$2^{-\eta}\leq|f^{*}|\leq 2^{\eta},\quad\text{ where
}\eta:=\leavevmode\nobreak\ \widetilde{\mathcal{O}}(nd^{n-1}\tau+n^{2})).$

There is an randomized algorithm that approximate $f^{*}$ in
$\widetilde{\mathcal{O}}_{B}(d^{3n}\lg(\tfrac{1}{\epsilon})(nd^{2n-2}\tau+\lg(\tfrac{1}{\epsilon})))$
bit operations, with probability of success $1-\tfrac{1}{\epsilon}$.

Notice the lower bound on $f^{*}$ in the unconstrained case, has an exponent
$n$ instead of $n^{2}$. This is similar to the bounds in Eqs. (1) and (2)
where the infimum is attained, and hence it is asymptotically optimal. We
emphasize that Theorem 2 holds without any assumptions on the input. If the
infimum is attained, then it is among the critical values of $f$, which we can
compute by solving the system of the partial derivatives of $f$. The
complexity of this step is dominated by the complexity of the computation of
the asymptotic critical value; hence we do not detail on this further.

#### Newton non-degenerate polynomial functions

Whenever $\mathscr{X}=:X$ is a (real) algebraic set, we present an algorithm
for computing the optimal value $f^{*}$, under some genericity conditions on
the input polynomials with respect to their Newton polytopes. We refer the
reader to §4.1 for detailed presentation of polynomial sparsity and Newton
polytopes.

A polynomial $f\in\mathbb{K}[x_{1},\ldots,x_{n}]$ is a linear combination
$\sum c_{\bm{a}}\leavevmode\nobreak\ \bm{x}^{\bm{a}}$ of monomials
$\bm{x}^{\bm{a}}:=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$, where the exponent
vectors $\bm{a}$ run over a finite subset $A$ of $\mathbb{N}^{n}$, and
$c_{\bm{a}}\in\mathbb{K}^{*}$. Then $A$ is the _support_ of $f$ and the
_Newton polytope_ , $\mathsf{NP}(f)$, of $f$ is the convex hull of $A$ in
$\mathbb{R}^{n}$. Given a collection
$\bm{\Delta}:=(\Delta_{0},\Delta_{1},\ldots,\Delta_{k})$ of integer polytopes
in $\mathbb{R}^{n}_{\geq 0}$, we use $\mathbb{R}^{\bm{\Delta}}$ to denote the
space of all tuples of polynomials whose _Newton tuple_ is $\bm{\Delta}$:

$\displaystyle\mathbb{R}^{\bm{\Delta}}:=$
$\displaystyle\left\\{(f_{0},f_{1},\ldots,f_{k})\leavevmode\nobreak\
\mid\leavevmode\nobreak\
f_{i}\in\mathbb{K}[z_{1},\ldots,z_{n}],\leavevmode\nobreak\
\mathsf{NP}(f_{i})=\Delta_{i},\leavevmode\nobreak\ i=0,1,\ldots,k\right\\}.$

We can identify this space with the space of polynomial functions
$X\longrightarrow\mathbb{R}$, with $\bm{x}\longmapsto f_{0}(\bm{x})$, where
$X$ is the real algebraic set
$\mathbb{V}_{\\!\mathbb{R}}(f_{1},\ldots,f_{k})\subset\mathbb{R}^{n}$, and
$\mathsf{NP}(f_{i})=\Delta_{i}$, $i=0,1,\ldots,k$.

The following theorem states that, for polynomials belonging to a Zariski open
set, we can compute their bifurcation set at infinity
$\mathcal{B}^{\infty}_{f}$ by exploiting their Newton polytopes.

######  Theorem 3 (Theorem 18).

For every collection $\bm{\Delta}$ of lattice polytopes in $(\mathbb{R}_{\geq
0})^{n}$, there is a Zariski open subset
$\Omega\subset\mathbb{K}^{\bm{\Delta}}$, such that for every
$\bm{f}\in\Omega$, corresponding to a real polynomial function
$f:X\longrightarrow\mathbb{R}$, the set $\mathcal{B}^{\infty}_{f}$ can be
computed effectively. Furthermore, the values in $\mathcal{B}^{\infty}_{f}$
depend only on the coefficients of the polynomials whose exponent vectors
appear at the faces of polytopes in $\bm{\Delta}$.

The polynomial functions belonging to the open set $\Omega$ of the previous
theorem are called _Newton non-degenerate_. Theorem 18 supports an algorithm
for computing $\mathcal{B}^{\infty}_{f}$ that has several advantages compared
with other ”classical” methods. First, we compute a smaller superset of the
bifurcation set at infinity. Secondly, the resulting algorithm applies for a
dense family of polynomial functions sharing a collection of Newton polytopes.
Finally, since the theorem and the supporting algorithms depends on the Newton
polytopes of the input polynomials, we exploit the sparsity of the input and
on our way to estimate the bifurcation set we compute with smaller polynomial
systems. Ultimately, we obtain the following result.

######  Theorem 4 (§4.3).

Let $\bm{\Delta}$ be a tuple of integer polytopes in
$(\mathbb{R}_{\geq})^{n}$, and let $\bm{f}\in\mathbb{R}^{\bm{\Delta}}$ be a
Newton non-degenerate element corresponding to a real polynomial function
$f:X\longrightarrow\mathbb{R}$. Assume furthermore that all polynomials
involved in $X$ have degree at most $d$. Then,

$2^{-\eta}\leq|f^{*}|\leq 2^{\eta},\quad\text{ where
}\eta:=\leavevmode\nobreak\ \mathcal{O}(n^{2}d^{n-1}(n+\tau)).$

Similarly to Theorem 2, the bound on the infimum for Newton non-degenerate
functions is single exponential in $n$ and matches the bounds in Eqs. (1) and
(2); hence it is asymptotically optimal.

###  1.2 Organization of the paper and proof strategies

The rest of the paper is structured as follows. The next section presents
(some of) the notation that we use in throughout and some necessary
preliminaries.

In §2, we will describe a decomposition $\mathcal{S}(\mathscr{X})$ of a
complete semi-algebraic set, which we call _algebraic stratification_. We then
show Theorem 8: For any semi-algebraic function
$f:\mathscr{X}\longrightarrow\mathbb{R}$, one can construct a finite set of
complex polynomial functions $\\{f_{s}:\leavevmode\nobreak\
V_{s}\longrightarrow\mathbb{C}\\}_{s\in\mathcal{S}(\mathscr{X})}$ such that
for each $s\in\mathcal{S}(\mathscr{X})$, we have $s\subset V_{s}$, and
$f^{*}\in\mathcal{K}_{f_{t}}$ for some stratum $t$ above. Now, since the
subsets $V_{s}$ are algebraic, the values in $\mathcal{K}_{f_{s}}$ can be
computed effectively thanks to results of Jelonek and Kurdyka in [21]. These
effective expressions will become useful in §3 for showing Theorem 1.

In §3 we consider the constrained optimization problem, Problem 1, under the
assumption that the feasible region is a _complete_ semi-algebraic set. We
employ various tools to obtains precise bitsize and degree estimates for the
infimum.

§4 is devoted to proving Theorem 4; we first describe the types of coherent
faces in the tuple $\bm{\Delta}$ that are key for computing the bifurcation
set. The proof relies on classical results on $A$-discriminants and face-
resultants of polynomial tuples over the real and complex fields [18, 14, 15].
Once the expressions of the infimum are well-established in terms of an
elimination ideal, we can then prove upper bounds on its absolute value.

In §5 we consider the unconstrained polynomial optimization problem. We
present bounds on the infimum, an algorithm to compute it, and precise bit
complexity estimates; under no assumptions on the input.

We mention auxiliary results that we need for the proofs of various results in
the Appendix.

###  1.3 Notation

We denote by $\mathcal{O}$, resp. $\mathcal{O}_{B}$, the arithmetic, resp.
bit, complexity and we use the soft-O notations, $\widetilde{\mathcal{O}}$,
respectively $\widetilde{\mathcal{O}}_{B}$, to ignore (poly-)logarithmic
factors. We denote by $\mathbb{R}^{n}_{\geq 0}$ the positive orthant and we
use the abbreviation $[n]$ for $\\{1,2,\dots,n\\}$. We use bold letters to
denote vectors.

A Monte Carlo algorithm is a randomized algorithm that its output might not be
correct with a certain probability. A Las Vegas randomized algorithm always
outputs the correct result, but its runtime is not always the same, even for
the same input.

##### Algebraic varieties and smooth maps

Consider $\bm{x}=(x_{1},\dots,x_{n})$ and let $\bm{x}_{-i}$ denote all the
variables except the variable $x_{i}$. For a polynomial
$f\in\mathbb{K}[x_{1},\ldots,x_{n}]=\mathbb{K}[\bm{x}]$, where
$\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$, we denote its zero set by
$\mathbb{V}_{\mathbb{K}}(f)\subset\mathbb{K}^{n}$ and by
$\mathbb{V}_{\mathbb{K}^{*}}(f)\subset(\mathbb{K}^{*})^{n}$ its zero set over
the corresponding torus. We use the same notation after replacing $f$ by its
bold form $\bm{f}$ if it is a tuple of polynomials, that is
$\bm{f}=(f_{i})_{i\in I}$ for some finite subset $I\subset\mathbb{N}$.

Let $f:X\longrightarrow Y$ be any smooth, or analytic, map between two
manifolds. Let $\mathcal{G}$ be the graph in $X\times Y$ of $f$ and consider
the map

$\begin{array}[]{cccc}P:=\pi_{\mathcal{G}}:&\leavevmode\nobreak\
\mathcal{G}&\longrightarrow&Y\\\ &(\bm{x},\leavevmode\nobreak\
\bm{y})&\longmapsto&\bm{y}\enspace,\end{array}$

where $\pi_{\mathcal{G}}$ is the restriction of $\pi:X\times Y\longrightarrow
Y$, $(\bm{x},\leavevmode\nobreak\ \bm{y})\longmapsto\bm{y}$ on $\mathcal{G}$.
We say that $f$ is a _$\mathcal{C}^{\infty}$ -fibration_, if for every
$\bm{y}\in\pi(\mathcal{G})$, the set $Y\times f^{-1}(\bm{y})$ is diffeomorfic
to $P^{-1}(\pi(\mathcal{G}))$. The map $f$ is said to be a _locally trivial
fibration_ if, for each $\bm{x}\in X$, there exists a neighborhood $U$ of $x$
for which the restricted map $\left.f\right|_{U}:U\longrightarrow Y$ is a
$\mathcal{C}^{\infty}$-fibration.

A point $\bm{x}\in X$ is said to be a _critical point of $f$_ if the _co-rank_
$\text{corank}(df)_{\bm{x}}:=\min(\dim X,\leavevmode\nobreak\ \dim
Y)-\text{rank}(df)_{\bm{x}}$ is positive. We denote by
$\operatorname{Crit}(f)$ the set of critical points of $f$ and by
$\mathcal{K}^{0}_{f}(f)$ the corresponding critical values.

If, instead, $X$ is a smooth variety defined by polynomials
$g_{1},\ldots,g_{p}\in\mathbb{K}[x_{1},\ldots,x_{n}]$, then the critical locus
of $f$ consists of all points $\bm{x}\in X$ for which the rank of the
following _Jacobian matrix_

$\operatorname{Jac}\bm{f}:=\begin{bmatrix}{\partial f_{1}}/{\partial
x_{1}}&\cdots&{\partial f_{k}}/{\partial x_{1}}&{\partial g_{1}}/{\partial
x_{1}}&\cdots&{\partial g_{p}}/{\partial x_{1}}\\\
\vdots&&\vdots&\vdots&&\vdots\\\ {\partial f_{1}}/{\partial
x_{n}}&\cdots&{\partial f_{k}}/{\partial x_{n}}&{\partial g_{1}}/{\partial
x_{n}}&\cdots&{\partial g_{p}}/{\partial x_{n}}\end{bmatrix}$

is lower than the codimension of $X$.

##### About polynomials and their roots

For a polynomial $f\in\mathbb{Z}[\bm{x}]=\mathbb{Z}[x_{1},\dots,x_{n}]$ its
infinity norm $\|f\|_{\infty}$ equals the maximum of absolute values of its
coefficients. The bitsize of a polynomial is the logarithm of its infinity
norm. We also call the latter the bitsize of the polynomial, that is a
shortcut for the maximum bitsize of all its coefficients. A univariate
(multivariate) polynomial is of size $(d,\tau)$ when its (total) degree is at
most $d$ and has bitsize $\tau$. We represent a real algebraic number
$\alpha\in\mathbb{R}$ using the isolating interval representation; it includes
a square-free polynomial, $A$, which vanishes at $\alpha$ and an interval with
rational endpoints that contains $\alpha$ and no other root of $A$. If
$\alpha\in\mathbb{C}$, then instead of an interval we use a rectangle in
$\mathbb{R}^{2}$ where the coordinates of its vertices are rational numbers.

##  2 Critical values at infinity and bounds on the infimum

We present a decomposition of a semi-algebraic set, under some transversality
conditions. Then, we relate the infimum of a polynomial function, say $f$,
restricted on this semi-algebraic set, with the bifurcation set(s) of $f$,
restricted to the strata of the decomposition.

###  2.1 The bifurcation and Rabier sets

Let $X\subset\mathbb{K}^{n}$ be a smooth affine variety, where
$\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$, and let
$f:X\longrightarrow\mathbb{K}$ be a polynomial function on $X$. That is, if
$X=\mathbb{V}_{\mathbb{K}}(\mathcal{I})$ for some ideal $\mathcal{I}$, then
$f\in\mathbb{K}[x_{1},\ldots,x_{n}]/\mathcal{I}$. A generalization [52, 49,
50, 46] of Thom’s result [45] indicates that outside a finite set
$S\subset\mathbb{K}$, the following restricted function is a
$\mathcal{C}^{\infty}$-fibration:

$\displaystyle\left.f\right|_{f^{-1}(\mathbb{K}\setminus S)}:$ $\displaystyle
f^{-1}(\mathbb{K}\setminus S)\longrightarrow\mathbb{K}\setminus S.$ (5)

The smallest subset $S\subset\mathbb{K}$ for which the function in (5) is a
$\mathcal{C}^{\infty}$-fibration is the _bifurcation set_ of $f$ and we denote
it by $\mathcal{B}_{f}$. The _bifurcation values_ $z\in\mathcal{B}_{f}$ are of
two types: (i) $z=f(\bm{x})$ for some $\bm{x}\in\operatorname{Crit}(f)$; we
denote this set by $\mathcal{B}^{0}_{f}$ (also $\mathcal{K}^{0}_{f}$), or (ii)
$z$ is such that for an arbitrarily large compact subset
$K\subset\mathbb{C}^{n}$ and any small disc $D$ containing $z$, the restricted
map

$\displaystyle\left.f\right|_{{f^{-1}(D)\setminus K}}:f^{-1}(D)\setminus
K\longrightarrow D$

is not a $\mathcal{C}^{\infty}$-fibration (see e.g., [46, Definition 2.1]).
The set of all such values is denoted by $\mathcal{B}^{\infty}_{f}$, and we
call it the _bifurcation set at infinity_. Then, we get
$\mathcal{B}^{0}_{f}=\mathcal{B}^{\infty}_{f}\cup\mathcal{B}^{0}_{f}$. We
notice that the inclusion $\mathcal{B}^{0}_{f}\subset\mathcal{B}_{f}$ can be
strict. For example, the function $(x,\leavevmode\nobreak\ y)\longmapsto
x+x^{2}y$ has no critical points [11], whereas $0$ is a bifurcation value as
$f^{-1}(0)$ is the only fiber with more than one connected component in
$\mathbb{K}^{2}$.

Recall the Rabier set defined at the beginning in (3). We define
$\mathcal{K}_{f}:=\mathcal{K}^{\infty}_{f}\cup\mathcal{K}^{0}_{f}$ to be the
set of _generalized critical values_ of $f$. Consequently, $f$ is locally
trivial fibration over the $\mathbb{K}\setminus\mathcal{K}_{f}$.

In §3 and §5 we compute $\mathcal{K}_{f}$ using algebraic elimination.

###  2.2 A decomposition of a (complete) semi-algebraic set

Consider a basic closed semi-algebraic set

$\mathscr{X}:=\\{g_{1}=0,\dots,g_{r}=0,\leavevmode\nobreak\ g_{r+1}\geq
0,\ldots,g_{s}\geq 0,\leavevmode\nobreak\ g_{1},\ldots
g_{s}\in\mathbb{R}[x_{1},\ldots,x_{n}]\\},$ (6)

and let $f:\mathscr{X}\longrightarrow\mathbb{R}$ be a semi-algebraic function
given as the restriction of a polynomial function
$F:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ on $\mathscr{X}$, that is

$\displaystyle f:=\leavevmode\nobreak\ \left.F\right|_{\mathscr{X}}:$
$\displaystyle\leavevmode\nobreak\ \mathscr{X}\longrightarrow\mathbb{R}.$

Theorem 8 demonstrates that the infimum $f^{*}$ of $f$ over $\mathscr{X}$ is
in the union of bifurcation sets of restricted functions $\left.F\right|_{S}$,
for some algebraic sets $S\subset\mathbb{R}^{n}$.

This leads us to consider the _complexification_ of these functions
$\mathbb{C}\\!\left.F\right|_{\mathbb{C}S}:\mathbb{C}S\longrightarrow\mathbb{C}$,
where we extend the domain and range of $\left.F\right|_{S}$ to
$\mathbb{C}S\subset\mathbb{C}^{n}$ and $\mathbb{C}$, respectively.
Subsequently, we use the inclusion of Eq. (4) to show that $f^{*}$ lies in the
union of the corresponding Rabier sets (Corollary 9). In this way we can
compute and/or approximate $f^{*}$.

Let $I=\\{1,\dots,r\\}\cup I_{0}$, where $I_{0}$ is a subset of $s+[r-s]$;
that is $I$ is a subset of $[r]$ that always contains the set
$\\{1,\dots,r\\}$. For any such $I$, we denote by
$\mathbb{V}_{\\!\mathbb{K}}(\bm{g}_{I})$ the common zero locus in
$\mathbb{K}^{n}$ of $g_{i}$, for all $i\in I$, where
$\mathbb{K}\in\\{\mathbb{C},\mathbb{R}\\}$.

######  Definition 5 (Complete semialgebraic set).

A semialgebraic set $\mathscr{X}$, as in (6), is _complete_ if, for every set
of indices $I$, as above, the set $\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})$ is
a smooth complete intersection of codimension $\\#I$. Then, there exists
$\alpha\in\mathbb{N}$ and a filtration

$\varnothing=:\mathscr{X}_{-1}\subset\mathscr{X}_{\alpha}\subset\mathscr{X}_{\alpha+1}\subset\cdots\subset\mathscr{X}_{n-r}:=\mathscr{X},$
(7)

satisfying the following properties for every $i=\alpha,\ldots,n-r$:

  1. ($\Pi_{1}$)

The set $\mathscr{X}_{i}$ is a basic closed semi-algebraic set with pure
dimension $i$, and

  2. ($\Pi_{2}$)

the Zariski closure of any connected component of
$\mathscr{X}_{i}\setminus\mathscr{X}_{i-1}$, is
$\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})$, where $I$ is a subset of $[s]$, such
that $[r]\subset I$ and $\\#I=n-i$.

Since $\mathscr{X}$ is complete, we have $\alpha=\max(0,n-s)$.

######  Definition 6 (Stratification of a complete set $\mathscr{X}$).

If $\mathscr{X}$ is complete semi-algebraic subset, then
$\mathcal{S}(\mathscr{X}):=\left\\{\mathscr{X}_{i}\mathrel{\left|\vphantom{\mathscr{X}_{i}\alpha\leq
i\leq n-r}\right.}\alpha\leq i\leq n-r\right\\}$ is called an _algebraic
stratification_ of $\mathscr{X}$; we call the elements of
$\mathcal{S}(\mathscr{X})$ _strata_.111To the best of our knowledge, in its
current form, the definition of a complete stratification does not appear in
the literature.

######  Notation 7.

For each such $I\subset[s]$, we use the shorthand notation
$\left.F\right|_{I}$ for the restricted function

$\displaystyle\left.F\right|_{\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})}:$
$\displaystyle\leavevmode\nobreak\
\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})\longrightarrow\mathbb{R}.$

######  Theorem 8.

Let $\mathscr{X}$, as in Eq. (6), be a complete semialgebraic subset of
$\mathbb{R}^{n}$. Let $F:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ be a
polynomial function, and assume that the infimum $f^{*}$ of the function
$f:=\left.F\right|_{\mathscr{X}}:\mathscr{X}\longrightarrow\mathbb{R}$ is not
attained. Then, there exists a set of indices $I$, such that $[r]\subset
I\subset[s]$, for which

$f^{*}\in\mathcal{B}_{\left.F\right|_{I}}.$ (8)

###### Proof.

Assume without loss of generality that $f^{*}=0$. We will prove (8) by finding
$I$ above for which the zero betti number of $\left.F\right|_{I}^{-1}(0)$
differs from that of any $\left.F\right|_{I}^{-1}(z)$ with $z\in\mathbb{R}$
close enough to $0$.

We start by choosing $I$ above. Since $f^{*}$ is not attained, and
$\mathscr{X}$ is closed (in the Euclidean topology), there exists
$\varepsilon>0$ such that all components of $f^{-1}(]0,\leavevmode\nobreak\
\varepsilon[)$ are unbounded. We choose $\varepsilon$ small enough so that
$f^{-1}(]0,\leavevmode\nobreak\ z[)$ has the same number of connected
components in $\mathbb{R}^{n}$ for any $z\in\leavevmode\nobreak\
]0,\leavevmode\nobreak\ \varepsilon[$. Furthermore, one can set $\varepsilon$
even smaller if necessary so that each connected component $C$ of
$f^{-1}(]0,\leavevmode\nobreak\ \varepsilon[)$ coincides with a connected
component of $\sigma\cap F^{-1}(]0,\leavevmode\nobreak\ \varepsilon[)$ for
some stratum $\sigma\in\mathcal{S}(X)$.

Pick one such stratum $\sigma$ above, together with a component $C$, and let
$J\subset[s]$ be the index set containing $[r]$ such that
$\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{J})$ is the Zariski closure of $\sigma$
(c.f. 2). Since $\mathscr{X}$ is complete, we can choose a sub-stratum
$\delta\subset\sigma$ and a superset $I$ containing $J$ such that a connected
component of $\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})\cap
F^{-1}(]0,\leavevmode\nobreak\ \varepsilon[)$ coincides with $\delta\cap
F^{-1}(]0,\leavevmode\nobreak\ \varepsilon[)$. In what follows, we set
$Z:=\mathbb{V}_{\\!\mathbb{R}}(\bm{g}_{I})$ and $S:=\delta\cap
F^{-1}(]0,\leavevmode\nobreak\ \varepsilon[)$.

Now, we use betti numbers counting of preimages under $\left.F\right|_{Z}$ to
finish the proof. Recall that $\mathcal{B}_{\left.F\right|_{Z}}$ is finite in
$\mathbb{R}$. Then, we may take a smaller $\varepsilon>0$ if necessary so that

$]0,\leavevmode\nobreak\ \varepsilon[\leavevmode\nobreak\
\cap\leavevmode\nobreak\ \mathcal{B}_{\left.F\right|_{Z}}=\varnothing$ (9)

is satisfied. Hence, there exists $k\in\mathbb{N}$, such that for every
$z\in\leavevmode\nobreak\ ]0,\leavevmode\nobreak\ \varepsilon[$, the zero
betti number satisfies

$b_{0}\big{(}\\!\left.F\right|_{Z}^{-1}(z)\big{)}=k.$ (10)

We finish the proof by contradiction; assume that
$0\not\in\mathcal{B}_{\left.F\right|_{Z}}$. Then, we have
$b_{0}\big{(}\\!\left.F\right|_{Z}^{-1}(0)\big{)}=k$. Since $S$ is a connected
component of $\left.F\right|_{Z}^{-1}([0,\leavevmode\nobreak\ \varepsilon[)$,
for each $z$ in the half-closed interval $[0,\leavevmode\nobreak\
\varepsilon[$, we get

$b_{0}\big{(}\\!\left.F\right|_{Z}^{-1}(z)\big{)}=b_{0}\big{(}\\!\left.F\right|_{Z\setminus
S}^{-1}(z)\big{)}+b_{0}\big{(}\\!\left.F\right|_{S}^{-1}(z)\big{)}.$

Then, Equality (10) implies that

$b_{0}\big{(}\\!\left.F\right|_{Z\setminus
S}^{-1}(z)\big{)}+b_{0}\big{(}\\!\left.F\right|_{S}^{-1}(z)\big{)}=b_{0}\big{(}\\!\left.F\right|_{Z\setminus
S}^{-1}(0)\big{)}+b_{0}\big{(}\\!\left.F\right|_{S}^{-1}(0)\big{)}.$

Since $\left.F\right|_{S}^{-1}(0)=\left.f\right|_{S}^{-1}(0)=\varnothing$, we
get that for each $z\in\leavevmode\nobreak\ ]0,\leavevmode\nobreak\
\varepsilon[$, the below equality holds:

$\displaystyle b_{0}\big{(}\\!\left.F\right|_{Z\setminus
S}^{-1}(0)\big{)}>b_{0}\big{(}\\!\left.F\right|_{Z\setminus
S}^{-1}(z)\big{)}.$ (11)

Furthermore, from the definitions of $S$ and $Z$, we get that
$\left.F\right|_{Z\setminus S}^{-1}(z)$ is algebraic for each
$z\in\leavevmode\nobreak\ [0,\leavevmode\nobreak\ \varepsilon[$. Therefore,
inequality (11) implies that there exists $\bm{x}\in\left.F\right|_{Z\setminus
S}^{-1}(0)$ such that $\bm{x}\in\operatorname{Crit}(\left.F\right|_{Z})$. This
contradicts $0\not\in\mathcal{B}_{\left.F\right|_{Z}}$. ∎

In what follows, for every $I\subset[s]$, we use the shorthand notation
$\left.F\right|_{\mathbb{C}I}$ for the complexification of the real restricted
map $\left.F\right|_{I}$. That is,

$\displaystyle\left.F\right|_{\mathbb{C}I}:=\mathbb{C}\\!\left.F\right|_{\mathbb{V}_{\\!\mathbb{C}}(\bm{g}_{I})}:$
$\displaystyle\leavevmode\nobreak\
\mathbb{V}_{\\!\mathbb{C}}(\bm{g}_{I})\longrightarrow\mathbb{C}.$

######  Corollary 9.

Let $\mathscr{X}$, $F$, and $f$ be as in Theorem 8. Then, there exists a set
of indices $I$, such that $[r]\subset I\subset[s]$, for which it holds

$f^{*}\in\mathcal{K}_{\left.F\right|_{\mathbb{C}I}}.$

###### Proof.

Theorem 8, together with the Rabier property (3) imply that

$f^{*}\in\mathcal{B}_{\left.F\right|_{I}}\subset\mathcal{K}_{\left.F\right|_{I}},$

for some $I$ satisfying $[r]\subset I\subset[s]$. Finally, since we have
$\|z\|_{\mathbb{C}}=\|z\|_{\mathbb{R}}$ for any $z\in\mathbb{R}^{n}$, we get

$\mathcal{K}_{\left.F\right|_{I}}\subset\mathcal{K}_{\left.F\right|_{\mathbb{C}I}},$
(12)

for every $I\subset[s]$. This completes the proof. ∎

##  3 Constrained optimization and asymptotic critical values

We provide bounds on the absolute values of points in the Rabier set of
polynomial functions $f:X\longrightarrow\mathbb{C}$ over smooth affine
varieties $X\subset\mathbb{C}^{n}$. Whenever $f$ is given by real polynomials,
this eventually leads to bounds for the optimization problem $\inf_{\bm{x}\in
X\cap\mathbb{R}^{n}}f(\bm{x})$.

###  3.1 Asymptotic critical values over a smooth variety
$X\subset\mathbb{C}^{n}$

Consider a polynomial $F\in\mathbb{Q}[x_{1},\ldots,x_{n}]$ and a smooth
algebraic variety $X\subseteq\mathbb{C}^{n}$ of dimension $\delta=n-r$, that
is the zero set of the polynomials
$\bm{g}=\\{g_{1},\dots,g_{r}\\}\in\mathbb{Q}[\bm{x}]$. As our goal is to bound
the asymptotic critical values of the function $f:=\left.F\right|_{X}$, it is
without loss of generality to consider $X$ to be complete intersection; see
Theorem 29 and Remark 4. If we have more than $r$ polynomials, then we can
consider $r$ generic linear combinations of them to construct a ”complete
intersection” system, at the expense of adding some additional component(s) in
$X$. The original components of the initial system can be identified by
considering several generic linear combinations if necessary. As this
technique does not change a lot the bitsize of the polynomial to compute with,
and we only interested to bound (and not compute) the related quantities, we
do not detail further. We refer the reader to [9] for additional details and
an application in computing the Chow form of a variety.

Consider the $(r+1)\times n$ matrix

$C=\left(\begin{array}[]{cc}\nabla F\\\
\operatorname{Jac}(\bm{g})\end{array}\right),$

where $\nabla F$ is the gradient of $F$ and has dimension $1\times n$, while
$\operatorname{Jac}(\bm{g})$ is the Jacobian matrix of $\bm{g}$ and has
dimension $r\times n$. Consider the set of all subsets of $[n]$ of cardinality
$r+1$; we denoted by $\left[\begin{smallmatrix}n\\\
r+1\end{smallmatrix}\right]$. Then, $I\in\left[\begin{smallmatrix}n\\\
r+1\end{smallmatrix}\right]$ $\Leftrightarrow$ $I\subseteq[n]$ and $|I|=r+1$.
There are $s={n\choose r+1}$ such subsets $I$ and to each of them, we
associate an integer $i$, where $1\leq i\leq s$.

Let $M_{i}$ be the $(r+1)\times(r+1)$ square submatrix of $C$, obtained by
selecting the columns of $C$ with indices in $I$. For $j\in I$, let $M_{i,j}$
be the square $r\times r$ submatrix of $M_{i}$, obtained by omitting the first
row (which corresponds to $\nabla F$) and the $j$-th column; there are $r+1$
such matrices, for every $i$.

For a specific $i$ and $j\in I$, let $m_{i}$ and $m_{i,j}$ be the determinants
of $M_{i}$ and $M_{i,j}$, respectively; they are polynomials in
$\mathbb{Z}[\bm{x}]$. We also need the definition of the rational function

$w_{i,j}=\frac{m_{i}}{m_{i,j}}=\frac{\det M_{i}}{\det M_{i,j}}\enspace.$

Consider the vector $\bm{j}=(j_{1},\dots,j_{s})\in\mathbb{N}^{s}$, where
$j_{i}\in I$. There are $(r+1)^{s}$ such vectors. For each $\bm{j}$, we
consider the map $\Phi_{\bm{j}}$, which is

$\begin{array}[]{cccclll}\Phi_{\bm{j}}&:&X&\longrightarrow&\mathbb{C}^{n}\times\mathbb{C}^{(n+1)s}\\\
&&\bm{x}&\longmapsto&(F(\bm{x}),\\{w_{i,j_{i}}(\bm{x}),x_{1}w_{i,j_{i}}(\bm{x}),\dots,x_{n}w_{i,j_{i}}(\bm{x})\\}_{i\in[s]}).\end{array}$
(13)

If $\mathcal{G}_{\bm{j}}:=\overline{\mathtt{Im}(\Phi_{\bm{j}})}$, and
$\mathcal{G}=\bigcup_{\bm{j}}\mathcal{G}_{\bm{j}}$, then
$\mathcal{K}(f)=L\cap\Gamma$, where $L=\underbrace{(0,\dots,0)}_{(n+1)s\text{
times}}\times\mathbb{C}$ (see [21]).

Upper and lower bounds on the roots of these polynomials, will also hold truer
for the asymptotic critical values.

####  3.1.1 Resultant systems using determinants

Our presentation is based on van der Waerden [48] and Yap [53]. Let
$\bm{A}=\\{A_{1},\dots,A_{p}\\}\subseteq(\mathbb{Z}[\bm{c}])[\bm{x}]$ be a
system of polynomial equations in the variables $\bm{x}$, the coefficients of
which are polynomials with integer coefficients in the additional set of
variables $\bm{c}$. Let the degree of each polynomial $A_{i}$ with respect to
$\bm{x}$ be $d_{i}$ and $d=\max_{i\in[p]}d_{i}$.

The resultant system is a set of polynomials in the coefficients $\bm{c}$
having the property that all of them vanish if the polynomials in $\bm{A}$
have a common non-trivial solution. In the case where $p=n$, then the
resultant system consists of a single polynomial, which we call the
(homogeneous) resultant of the system.

Let $\nu_{m}={m+n-1\choose n-1}\leq m^{n-1}$, where $m$ is a positive integer
that we will specify in the sequel. Let
$\mathtt{P}^{m}=\\{\bm{x}^{\bm{\alpha}}\,|\,|\bm{\alpha}|=m\\}$, that is the
set of all monomials in $\bm{x}$ of degree $m$. Next, we consider the set

$\bm{A}_{m}=\left\\{\bm{x}^{\bm{\alpha}}A\mathrel{\left|\vphantom{\bm{x}^{\bm{\alpha}}A\deg(\bm{x}^{\bm{\alpha}}A)=m,A\in\bm{A},\bm{x}^{\bm{\alpha}}\in\mathtt{P}^{m}}\right.}\deg(\bm{x}^{\bm{\alpha}}A)=m,A\in\bm{A},\bm{x}^{\bm{\alpha}}\in\mathtt{P}^{m}\right\\}\enspace.$

It holds $|\bm{A}_{m}|\geq\nu_{m}$. Let $M_{m}$ be the
$\left(|\bm{A}_{m}|\times\nu_{m}\right)$-matrix, the rows of which correspond
to the polynomials in $\bm{A}_{m}$ and its columns correspond to the elements
of $\mathtt{P}^{m}$.

Let $R_{m}\subseteq\mathbb{Z}[\bm{c}]$ be the set of all the
$\left(\nu_{m}\times\nu_{m}\right)$-minors of the matrix $M_{m}$.

######  Theorem 10 ([53, XI Thm. 9 & 13]).

If $m\geq 1+n(13\leavevmode\nobreak\ d^{n}-1)$, then $R_{m}$ is a resultant
system for $\bm{A}$.

The $13\leavevmode\nobreak\ d^{n}$ factor in the bound for $m$ corresponds to
an effective bound on the Nullstellensatz. We note that we can also use
improved bounds of effective Nullstellensatz, but this bound suffices for our
purposes. For our purposes, we do not need to count or manipulate with the
polynomials in $R_{m}$. We just need to bound their degree, as polynomials in
$\bm{c}$, and their bitsize.

####  3.1.2 Bounding the asymptotic critical values using resultant systems

To obtain worst case bound on the asymptotic critical values, it suffices to
consider worst case bounds for $\mathcal{G}_{\bm{j}}$, for a fixed pair
$(\bm{j},I)$, with $I\in\left[\begin{smallmatrix}n\\\
r+1\end{smallmatrix}\right]$ and $\bm{j}=(j_{1},\dots,j_{s})\in\mathbb{N}^{s}$
satisfying $j_{i}\in I$. We emphasize that our goal is _not_ to compute these
values, but rather to bound them effectively.

Let
$X_{\bm{j}}=\mathbb{V}(\\{m_{i,j_{i}}\\}_{i\in[s]})\subseteq\mathbb{C}^{n}$ be
the zero set of all denominators in $\Phi_{\bm{j}}$, Eq. (13). Let
$\delta_{i}=\dim(X_{\bm{j}})$ be the dimension $X_{\bm{j}}$. As it is not a
complete intersection, we can consider $n-\delta_{i}$ generic linear
combinations of the polynomials $m_{i,j_{i}}$. Let these new polynomials be
$\\{h_{1},\dots,h_{n-\delta_{i}}\\}$.

Consider the set of polynomials

$J=\Big{\\{}\\{g_{i}(\bm{x})\\}_{i\in[r]},F(\bm{x})-z,\\\
\\{m_{i,j_{i}}(\bm{x})y_{i}-m_{i}(\bm{x}),m_{i,j_{i}}(\bm{x})y_{i}-x_{1}m_{i}(\bm{x}),\dots,m_{i,j_{i}}(\bm{x})y_{i}-x_{n}m_{i}(\bm{x})\\}_{i\in[s]},\\\
t\,h(\bm{x})-1\Big{\\}}\subseteq\mathbb{Z}[\bm{x},t,y_{1},\dots,y_{s},z],$
(14)

where $h(\bm{x})=\prod_{i\in[n-\delta_{i}]}h_{i}(\bm{x})$.

This set contains $r+1+(n+1){n\choose r+1}+1$ equations. We should eliminate
the variable $(\bm{x},t)$; this would result in polynomials in
$\mathbb{Z}[y_{1},\dots,y_{s},z]$. Then, if we set $y_{i}=0$, we obtain
univariate polynomials in $z$, the roots of which contains the asymptotic
critical values of $f$.

Let $F$ be of size $(d,\tau)$ and $g_{i}$ of size $(d_{1},\tau)$. Standard
calculations based on Claim 26 result that $m_{i,j}$ is of size
$(\mathcal{O}(rd_{1}),\widetilde{\mathcal{O}}(r(d+n+\tau)))$, $m_{i}$ is of
size $(\mathcal{O}(d+rd_{1}),\widetilde{\mathcal{O}}(r(d+n+\tau)+d_{1}))$.

Based on the results in the appendix, the polynomials $h_{i}$ have the same
size as the polynomials $m_{i,j}$. Thus, $h(\bm{x})$ is of size
$(\mathcal{O}(nrd_{1}),\widetilde{\mathcal{O}}(nr(d+n+\tau)))$,

To eliminate the variables $\bm{x}$ from the polynomials in $J$, we will use
resultant systems from Sec. 3.1.1. The maximum degree of the involved
polynomials is $\mathcal{O}(nrd_{1})$, thus the Nullstellensatz bound becomes
$\mathcal{O}((nrd_{1})^{n})$ which in turn implies that the various matrices
are of dimension $\mathcal{O}((nrd_{1})^{n^{2}})$.

The elements of the matrix (or matrices) are polynomials in the variables
$y_{1},\dots,y_{s},z$. Their degree with respect to $y_{i}$ and $z$ is one.
Their maximum bitsize is $\widetilde{\mathcal{O}}(r(d+n+\tau)+d_{1}))$. Hence,
their determinant is a polynomial in $(\mathbb{Z}[y_{1},\dots,y_{s}])[z]$ of
degree $\mathcal{O}((nrd_{1})^{n^{2}})$. and bitsize

$\eta=\widetilde{\mathcal{O}}(r(d+n+\tau)+d_{1})(nrd_{1})^{n^{2}}).$

If we set the variables $y_{i}$ to zero, then we obtain a univariate
polynomial in $\mathbb{Z}[z]$ of the same size, the roots of which contain the
asymptotic critical values.

The arguments above yield the following result.

######  Theorem 11.

Let $F\in\mathbb{Z}[\bm{x}]$ be of degree $d$ and bitsize $\tau$. Let
$X=\mathbb{V}(g_{1},\dots,g_{r})\cap\mathbb{R}^{n}$ be a smooth real algebraic
variety and $g_{i}$ be of size $(d_{1},\tau)$. The optimum value of the
problem $f^{*}=\inf_{\bm{x}\in X}F(\bm{x})$ is an algebraic number of degree
$\mathcal{O}((nrd_{1})^{n^{2}})$ such that $2^{-\eta}\leq|f^{*}|\leq
2^{\eta}$, where
$\eta=\widetilde{\mathcal{O}}(r(d+n+\tau)+d_{1})(nrd_{1})^{n^{2}})$.

Finally, thanks to Corollary 9, we deduce our min Theorem 1.

##  4 The Newton non-degenerate case

As Theorem 8 presents, in order to locate the infimum of a semi-algebraic
function, one can consider a polynomial function instead, and compute its
bifurcation set. The latter, however, is intractable for arbitrary functions.
Accordingly, we can use the Rabier set to effectively compute a superset
containing it. Albeit the computation itself has high complexity as we will
see in §3.

In this section, we introduce a large family of polynomial functions, and show
that one can effectively approximate their bifurcation set using less
expensive methods than the Rabier set.

###  4.1 Preliminaries on polytopes

A subset $\Pi\subset\mathbb{R}^{n}$ is called a _polyhedron_ if it is the
intersection of finitely-many closed half-spaces. The boundary of one such
half-space is called a _supporting hyperplane_ of $\Pi$. We say that a set
$\Phi$ is a _face_ of $\Pi$, we indicate this using the notation
$\Phi\prec\Pi$, if it is the intersection of a supporting hyperplane $H$ of
$\Pi$ with its boundary, i.e., $\Phi=H\cap\partial\Pi$. We say that $\Phi$ is
_origin_ if $\Phi$ contains the point $\bm{0}:=(0,\ldots,0)\in\mathbb{R}^{n}$.
A _polytope_ is a bounded polyhedron.

A _tuple of polytopes_ , or a _tuple_ for short, is a map $\bm{\Delta}$ from a
finite set $K\subset\mathbb{N}$ to the set of polytopes in $\mathbb{R}^{n}$.
We call $K$ the _support_ of $\bm{\Delta}$ and we denote it by
$[\bm{\Delta}]$. The Minkowski sum of elements in $\bm{\Delta}$

$\left\\{\sum\nolimits_{k\in
K}\bm{a}_{k}\,|\,\bm{a}_{k}\in\Delta_{k}\right\\},$

is also a polytope; we denote it by $\sum\bm{\Delta}$. In our setting, the
_Minkowski sum_ of any two subsets $X,Y\subset\mathbb{R}^{n}$ is the
coordinate-wise sum $X+Y:=\\{x+y\leavevmode\nobreak\ |\leavevmode\nobreak\
x\in X,\leavevmode\nobreak\ y\in Y\\}$. The _dimension_ of $\bm{\Delta}$ is
defined as

$\displaystyle\dim\bm{\Delta}:=$
$\displaystyle\dim(\sum\bm{\Delta})-\\#[\bm{\Delta}].$ (15)

For any $i\in[\bm{\Delta}]$, the $i$-th polytope in the tuple is $\Delta_{i}$.
For any $I\subset[\bm{\Delta}]$,
$\bm{\Delta}_{I}:=\left\\{\Delta_{i}\mathrel{\left|\vphantom{\Delta_{i}i\in
I}\right.}i\in I\right\\}$ is the _sub-tuple_ (of $\bm{\Delta}$ associated to
$I$). A tuple $\bm{\Gamma}$ is a _tuple-face_ of $\bm{\Delta}$ (or, simply,
_face_ whenever it is clear from the context) if
$[\bm{\Gamma}]=[\bm{\Delta}]$, $\Gamma_{i}\prec\Delta_{i}$, for each
$i\in[\bm{\Gamma}]$, and $\sum\bm{\Gamma}\prec\sum\bm{\Delta}$.

We say that $\bm{\Gamma}$ is a _facing_ of $\bm{\Delta}$, if there is a face
$\bm{\Gamma}^{\prime}$ of $\bm{\Delta}$ such that
$\bm{\Gamma}=\bm{\Gamma}^{\prime}_{I}$ and $I=[\bm{\Gamma}]$. We also use the
notation $\bm{\Gamma}\prec\bm{\Delta}$ for the facings.

######  Definition 12.

A facing $\bm{\Gamma}\prec\bm{\Delta}$ is said to be _important_ , if there
exists a face $\bm{\Gamma}^{\prime}\prec\bm{\Delta}$ such that
$\bm{\Gamma}=\bm{\Gamma}^{\prime}_{[\bm{\Gamma}]}$ and

$\dim\bm{\Gamma}\leq\dim\bm{\Gamma}^{\prime}_{I},\quad\forall\leavevmode\nobreak\
I\supset[\bm{\Gamma}].$

$(2,0,0)$$(0,2,0)$$(0,1,0)$$(1,0,0)$$(0,0,1)$$\Delta_{1}$$\Delta_{2}$$\Delta_{3}$$(1,0,0)$BottomFrontSideFront-
bottom$1-3=-2$$1-2=-1$$0-1=-1$$2-3=-1$$2-3=-1$$1-2=-1$ Figure 1: An example of
a triple $\bm{\Delta}$. For each of the four selected faces of $\bm{\Delta}$,
we indicate which are the important facings, and we compute their dimensions
according to the formula (15).

For any polytope $\Pi\subset\mathbb{R}^{n}_{\geq 0}$, either $\\{\bm{0}\\}$ is
a vertex of $\Pi$, or $\bm{0}\not\in\Pi$.

######  Definition 13.

A tuple $\bm{\Delta}$ is said to be _origin_ if its support $[\bm{\Delta}]$
contains the index $0$ and the polytope $\Delta_{0}$ contains the origin
$\\{\bm{0}\\}$.

For example, all important facings illustrated in Figure 1 are origin.

###  4.2 Application to polynomial functions

Let $\mathbb{K}\in\\{\mathbb{C},\mathbb{R}\\}$. We consider the polynomial
function $f:X\longrightarrow\mathbb{K}$, for some
$X:=\mathbb{V}_{\\!\mathbb{K}}(g_{1},\ldots,g_{r})=\mathbb{V}_{\\!\mathbb{K}}(\bm{g})$.
If $f$ is obtained as the restriction $\left.F\right|_{X}=f$, for some
polynomial $F:\mathbb{K}^{n}\longrightarrow\mathbb{K}$, then, we identify $f$
with the collection of polynomials
$\bm{f}:=(F,g_{1},\ldots,g_{r})=(F,\bm{g})$.

Let $\bm{\Delta}$ denote the tuple of lattice polytopes given by
$(\Delta_{0},\Delta_{1},\ldots,\Delta_{r})$, where

$\Delta_{i}:=\mathsf{NP}(g_{i}),\leavevmode\nobreak\ i=1,\ldots,r,$

and $\Delta_{0}:=\mathsf{NP}(F-t)$ for some generic $t\in\mathbb{K}$. That is,
it holds that

$\Delta_{0}:=\operatorname{conv}(\operatorname{supp}(F)\cup\\{\bm{0}\\}).$

######  Notation 14.

For any subset $\sigma\subset\mathbb{R}^{n}$ and for any polynomial
$P\in\mathbb{K}[x_{1},\ldots,x_{n}]$ the _restriction of $P$ to $\sigma$_,
denoted by $P_{\sigma}$, is the polynomial

$\sum_{\bm{a}\in\sigma\cap\operatorname{supp}(P)}c_{\bm{a}}\leavevmode\nobreak\
\bm{x}^{\bm{a}}.$

For any facing $\bm{\Gamma}\prec\bm{\Delta}$, and any
$\bm{f}\in\mathbb{K}^{\bm{\Delta}}$, we define the collection of polynomials
$\bm{g}_{\bm{\Gamma}}:=(\bm{g}_{\Gamma_{i}})_{i\in[\bm{\Gamma}]\setminus\\{0\\}}$,
where for any $i\in[\bm{\Gamma}]\setminus\\{0\\}$, the expression
$\bm{g}_{\Gamma_{i}}$ denotes the restricted polynomial $g_{i,\Gamma_{i}}$.
Similarly, we use the notation $\bm{f}_{\bm{\Gamma}}$ to refer to the tuple
$(\bm{f}_{\Gamma_{i}})_{i\in[\bm{\Gamma}]}$ which includes $F_{\Gamma_{0}}$
whenever $0\in[\Gamma]$.

Let $\bm{\Gamma}$ be an origin facing for which
$\mathbb{V}_{\mathbb{K}^{*}}(\bm{g}_{\bm{\Gamma}})$ is non-empty. Then it
defines a function

$f_{\Gamma}:=\left.F_{\Gamma_{0}}\right|_{\mathbb{V}^{*}_{\\!\mathbb{K}}(\bm{g}_{\bm{\Gamma}})}:\mathbb{V}^{*}_{\\!\mathbb{K}}(\bm{g}_{\bm{\Gamma}})\longrightarrow\mathbb{K},$

where for any subset $S\subset\mathbb{K}^{n}$, we use the notation $S^{*}$ to
denote the intersection $S\cap(\mathbb{K}^{*})^{n}$. We use this notation to
define the set $\mathcal{D}_{\Gamma}(f)\subset\mathbb{K}$, called the _face-
discriminant_ of $f$, defined as

$\mathcal{D}_{\Gamma}(f):=f_{\Gamma}(\operatorname{Crit}(f_{\Gamma}))$ (16)

In other words, the locus $\mathcal{D}_{\Gamma}(f)$ is the discriminant of the
function $f_{\Gamma}$. By Bertini Theorem [25], face-resultants are finite
sets in $\mathbb{K}$.

######  Example 15.

Consider the polynomial function $F:\mathbb{R}^{3}\longrightarrow\mathbb{R}$,
$(x,y,z)\longmapsto 1+x+x^{2}$, and let $X\subset\mathbb{R}^{3}$ be the curve
$\mathbb{V}_{\\!\mathbb{R}}(g_{1},\leavevmode\nobreak\ g_{2})$, where
$g_{1}:=-2+x+2y-y^{2}$ and $g_{2}:=1+2x-3y+4z$. The triple
$\bm{f}:=(F,g_{1},g_{2})$ has Newton tuple $\bm{\Delta}$ illustrated in Figure
1. Let us compute some of the face-discriminants of $f$.

If $\bm{\Gamma}=\bm{\Delta}$, then we have
$\mathcal{D}_{\Gamma}(f)=F(\operatorname{Crit}\left.F\right|_{X^{*}})=\mathbb{V}_{\\!\mathbb{R}}(h)$,
where $h=\langle F-t,\leavevmode\nobreak\ g_{1},\leavevmode\nobreak\
g_{2},\leavevmode\nobreak\ \det\operatorname{Jac}_{(x,y,z)}\bm{f}\rangle$.
Another trivial case is whenever $\bm{\Gamma}$ is any one of the important
facings of the “Side” face of $\bm{\Delta}$ (see Figure 1); since
$\Gamma_{0}=\\{(0,0,0)\\}$, we always get $F_{\Gamma_{0}}\equiv 1$, and thus
$\mathcal{D}_{\Gamma}(f)=\\{1\\}$.

Now let $\bm{\Gamma}\prec\bm{\Delta}$ be the important origin face that is the
“Bottom” triple of Figure 1. Hence, we have $F_{\Gamma_{0}}=F_{\Delta_{0}}=F$.
Then, the domain of $\bm{f}_{\bm{\Gamma}}$ is the union of two veritcal lines
$\mathbb{V}_{\\!\mathbb{R}}(g_{1},\leavevmode\nobreak\ 1+2x-3y)$. A generic
$t\in\mathbb{R}$, has no preimages under $\bm{f}_{\bm{\Gamma}}$. This shows
that

$\mathcal{D}_{\Gamma}(f)=F(\mathbb{V}_{\\!\mathbb{R}}(g,1+2x-3y))=\\{1,\leavevmode\nobreak\
205/16\\}.$

######  Remark 1.

Note that, if $X=\mathbb{K}^{n}$, then we set $[\bm{\Delta}]=\\{0\\}$. Hence,
every facing $\bm{\Gamma}\prec\bm{\Delta}$ corresponds to the first polytope
$\Gamma_{0}$ that is a face of $\Delta_{0}$. By definition, we get

$\mathcal{D}_{\Gamma}(f)=F_{\Gamma_{0}}(\operatorname{Crit}F_{\Gamma_{0}}).$

######  Notation 16.

Let $\mathcal{I}(\bm{\Delta})$ and $\mathcal{O}(\bm{\Delta})$ denote the set
of all important facings of $\bm{\Delta}$ and origin ones respectively. The
intersection of the above two sets is denoted by
$\mathcal{I}\\!\mathcal{O}(\bm{\Delta})$.

We have the following classical result.

######  Theorem 17 ([32]).

Let $\bm{\Delta}$ be a tuple consisting of a single integer polytope in
$\mathbb{R}^{n}_{\geq 0}$. Then, there exists a Zariski open subset
$\Upsilon\subset\mathbb{C}^{\bm{\Delta}}$, such that for every polynomial
$f\in\Upsilon$ it holds that

$\mathcal{B}_{f}\setminus\\{f(\bm{0})\\}\subset\bigcup_{\bm{\Gamma}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})}\mathcal{D}_{\Gamma}(f).$

The detailed version of Theorem 17 illustrates a description of the set
$\Upsilon$, together with all the origin faces of $\Delta$ that do not
contribute to the infinity bifurcation set. This demonstrates that face-
resultants are useful for effectively computing the bifurcation set of a large
family of complex polynomials.

Let us state a generalization of Theorem 17, and postpone its proof to the end
of this section.

######  Theorem 18.

Let $\bm{\Delta}$ be a tuple of lattice polytopes in $\mathbb{R}^{n}_{\geq 0}$
satisfying $[\bm{\Delta}]=\\{0,1,\ldots,r\\}$, and assume that $\\{\bm{0}\\}$
is a vertex of $\Delta_{0}$. Then, there exists a Zariski open subset
$\Omega\subset\mathbb{K}^{\bm{\Delta}}$, such that for every
$\bm{f}\in\Omega$, the set $\mathbb{V}_{\\!\mathbb{K}}(g_{1},\ldots,g_{r})$ is
smooth, and the correcponding polynomial function
$f:\mathbb{V}_{\\!\mathbb{K}}(g_{1},\ldots,g_{r})\longrightarrow\mathbb{K}$
satisfies

$\mathcal{B}_{f}\setminus\\{f(\bm{0})\\}\subset\bigcup_{\bm{\Gamma}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})}\mathcal{D}_{\Gamma}(f).$
(17)

In what follows, we use $\left.f\right|_{*}$ to denote the function

$\displaystyle\left.f\right|_{*}:=\left.f\right|_{X^{*}}:$
$\displaystyle\leavevmode\nobreak\ X^{*}\longrightarrow\mathbb{K}.$

Similarly to $\mathcal{B}_{f}$, the set $B_{\left.f\right|_{*}}$ is also
finite [45].

######  Lemma 19.

We have

$\displaystyle\mathcal{B}_{f}$
$\displaystyle=\bigcup_{H}\mathcal{B}_{\left.f\right|_{H}}\leavevmode\nobreak\
\cup\mathcal{B}^{\infty}_{\left.f\right|_{*}}\cup\mathcal{B}^{0}_{f},$ (18)

where $H$ runs over all coordinate hyperplanes in
$\mathbb{K}^{n}\setminus(\mathbb{K}^{*})^{n}$, and $\left.f\right|_{H}$ are
the restricted functions $X\cap H\longrightarrow\mathbb{K}$.

###### Proof.

We consider only the case where $X\neq(\mathbb{K}^{*})^{n}$ as the
complementary case is similar. Let $\lambda\in\mathcal{B}_{f}$, and assume
that
$\lambda\not\in\mathcal{B}^{\infty}_{\left.f\right|_{*}}\cup\mathcal{B}^{0}_{f}$.
Without loss of generality we set $\lambda=0$. Then, for every arbitrary large
compact subset $K\subset\mathbb{K}^{n}$, there is a small enough neighborhood
$U\ni 0$, for which the function $h:\left.f\right|_{*}^{-1}(U)\setminus
K\longrightarrow U$, obtained by restricting $\left.f\right|_{*}$ to
$\left.f\right|_{*}^{-1}(U)\setminus K$, is a
$\mathcal{C}^{\infty}$-fibration. Consequently, for each $z\in U$, we have
$h^{-1}(0)$ and $h^{-1}(z)$ are diffeomorphic. Then, from
$0\not\in\mathcal{B}^{0}_{f}:=f(\operatorname{Crit}f)$, the two preimages are
diffeomorphic:

$\displaystyle\overline{h^{-1}}^{{}_{X}}(0)\cong$
$\displaystyle\leavevmode\nobreak\ \overline{h^{-1}}^{{}_{X}}(z),$ (19)

where the closures are taken in the Eucludean topology induced on $X$.
However, there exists a value $z\in U$ for which the following holds

$\displaystyle f^{-1}(0)\setminus K\not\cong$
$\displaystyle\leavevmode\nobreak\ f^{-1}(z)\setminus K.$ (20)

We deduce from (19) and (20) that for some coordinate hyperplane $H$, the
preimage $(f^{-1}(0)\setminus K)\cap H$ is not diffeomorphic to
$(f^{-1}(z)\setminus K)\cap H$ for $K$ large enough. This shows that
$z\in\mathcal{B}_{h}$. ∎

In order to prove Theorem 18, we furthermore require the following notion for
tuples $\bm{f}\in\mathbb{K}^{\bm{\Delta}}$. Taking the coefficients of
$\bm{f}$ in the parameter space $\mathbb{K}^{\bm{\Delta}}$ as additional
variables, we denote by $\\{\bm{f}=0\\}$ the locus
$\\{F=g_{1}=\cdots=g_{r}=0\\}\subset(\mathbb{K}^{*})^{n}\times\mathbb{K}^{\bm{\Delta}}$.
The _Bertini discriminant_ $\bm{B}$ of $\bm{\Delta}$ (see e.g., [15,
Definition 3.5]) is the bifurcation set of the map
$\left.\pi\right|_{\\{\bm{f}=\bm{0}\\}}$ by restricting to
$\\{F=g_{1}=\cdots=g_{r}=0\\}$ the projection

$\pi:(\mathbb{K}^{*})^{n}\times\mathbb{K}^{\bm{\Delta}}\longrightarrow\mathbb{K}^{\bm{\Delta}}.$

The Bertini discriminant can be computed as follows. For any facing
$\bm{\Gamma}\prec\bm{\Delta}$, we define
$D_{\bm{\Gamma}}\subset\mathbb{K}^{\bm{\Delta}}$ as the closure of

$\displaystyle\left\\{\bm{f}\leavevmode\nobreak\ \left|\leavevmode\nobreak\
\exists\bm{x}_{0}\in\mathbb{V}^{*}_{\\!\mathbb{K}}(\bm{f}_{\bm{\Gamma}}),\leavevmode\nobreak\
\left.\operatorname{Jac}_{\bm{x}}(\bm{f}_{\bm{\Gamma}})\right|_{\bm{x}=\bm{x}_{0}}\text{
does not have full rank}\right\\}\right.$ (21)

In other words, the set $D_{\bm{\Gamma}}$ consists of all
$\bm{f}\in\mathbb{K}^{\bm{\Delta}}$ for which there exists a point
$\bm{x}_{0}\in(\mathbb{K}^{*})^{n}$ at which
$\mathbb{V}^{*}_{\\!\mathbb{K}}(\bm{f}_{\bm{\Gamma}})$ is not a complete
intersection. It was shown in [15, Theorem 1.1 and Proposition 4.10] (see also
[18, Section 5]) that $\operatorname{cdim}\bm{B}=1$, and it holds that

$\displaystyle\bm{B}=$ $\displaystyle\leavevmode\nobreak\
\bigcup_{\bm{\Gamma}\in\mathcal{I}(\bm{\Delta})}D_{\bm{\Gamma}}.$ (22)

######  Remark 2.

The mentioned results in [15] are formulated for the case where
$\mathbb{K}=\mathbb{C}$. For the real case, the statement assumes that
$\bm{f}$ consists of only one polynomial $F$ [18, Section 5.A]. Transitioning
to arbitrary tuples $\bm{f}$ with $\mathbb{K}=\mathbb{R}$ can be done via the
Cayley Trick (see e.g., [14, Section 6.2]).

###### Proof of Theorem 18.

Let $\bm{f}\in\mathbb{K}^{\bm{\Delta}}\setminus\bm{B}$, and let
$\Lambda(\bm{f})\subset\mathbb{K}^{\bm{\Delta}}$ be the line passing through
$\bm{f}$ with direction $(1,0,\ldots,0)$, where the first coordinate
corresponds to the constant term of $F$. In other words, we have

$\displaystyle\Lambda(\bm{f}):=$
$\displaystyle\left\\{(F-z,g_{1},\ldots,g_{r})\leavevmode\nobreak\
|\leavevmode\nobreak\ z\in\mathbb{K}\right\\}.$

On the one hand, if $\Theta\subset\mathbb{K}^{\Delta}$ is the set of all
$\bm{f}$ at which $\Lambda(\bm{f})$ intersects $\bm{B}$ transversally, then
for each $\bm{f}\in\Theta$, the relation

$\displaystyle\mathcal{B}_{\left.f\right|_{*}}=$
$\displaystyle\leavevmode\nobreak\ \bm{B}\cap\Lambda(\bm{f}),$ (23)

follows from the definition of $\bm{B}$. Note that if
$\widetilde{\bm{\Delta}}$ is the tuple of polytopes
$(\widetilde{\Delta}_{0},\Delta_{1},\ldots,\Delta_{r})$, where

$\displaystyle\widetilde{\Delta}_{0}:=$
$\displaystyle\operatorname{conv}\left(\Delta_{0}\cap\mathbb{N}^{n}\setminus\\{\bm{0}\\}\right),$

then $\Theta$ is the preimage, under $\Pi$, of the bifurcation set of the map
$\left.\Pi\right|_{\bm{B}}$, where
$\Pi:=\mathbb{K}^{\bm{\Delta}}\longrightarrow\mathbb{K}^{\widetilde{\bm{\Delta}}}$
is the projection taking a tuple $\bm{f}$ to $\tilde{\bm{f}}$ by forgetting
the constant term of the first polynomial $F$. Thanks to a theorem of Verdier
[50], the set $\Theta$ contains a Zariski open subset
$\Omega\subset\mathbb{K}^{\Delta}$.

On the other hand, for any $\bm{f}\in\mathbb{K}^{\Delta}$, and each facing
$\bm{\Gamma}\prec\bm{\Delta}$, we have

$\displaystyle\mathcal{D}_{\Gamma}(f)=$ $\displaystyle\leavevmode\nobreak\
D_{\bm{\Gamma}}\cap\Lambda(\bm{f}).$ (24)

Therefore, since $\mathcal{I}(\bm{\Delta})$ contains the tuple $\bm{\Delta}$,
it follows from (22), (23), and (24) that

$\displaystyle\mathcal{B}_{\left.f\right|_{*}}=$
$\displaystyle\leavevmode\nobreak\
\bigcup_{\bm{\Gamma}\in\mathcal{I}(\bm{\Delta})}\mathcal{D}_{\Gamma}(f).$ (25)

Next, we show that we can replace the set $\mathcal{I}(\bm{\Delta})$ in (25)
by $\mathcal{I}\\!\mathcal{O}(\bm{\Delta})$. Recall that
$\bm{g}_{\bm{\Gamma}}$ refers to
$(\bm{g}_{\Gamma_{i}})_{i\in[\bm{\Gamma}]\setminus\\{0\\}}$, and
$\bm{f}_{\bm{\Gamma}}$ to $(\bm{f}_{\Gamma_{i}})_{i\in[\bm{\Gamma}]}$ which
includes $F_{\Gamma_{0}}$ whenever $0\in[\Gamma]$.

The set $D_{\bm{\Gamma}}$ is a fiber bundle
$\operatorname{Proj}^{-1}(\operatorname{Proj}(D_{\bm{\Gamma}}))$, where
$\operatorname{Proj}:\mathbb{K}^{\bm{\Delta}}\longrightarrow\mathbb{K}^{\bm{\Gamma}}$,
$\bm{f}\longmapsto\bm{f}_{\bm{\Gamma}}$. Hence, since $\bm{f}\not\in
D_{\bm{\Gamma}}$, we have
$\bm{f}_{\bm{\Gamma}}\not\in\operatorname{Proj}(D_{\bm{\Gamma}})$. This shows
that $\operatorname{Proj}^{-1}(\bm{f}_{\bm{\Gamma}})\cap
D_{\bm{\Gamma}}=\varnothing$. Then, if $\bm{\Gamma}$ is not origin, we get
$\Lambda(\bm{f})\subset\operatorname{Proj}^{-1}(\bm{f}_{\bm{\Gamma}})$. We
conclude that $\mathcal{D}_{\Gamma}(f)=\varnothing$ if $\bm{\Gamma}$ is not
origin, and thus we get

$\displaystyle\mathcal{B}_{\left.f\right|_{*}}=$
$\displaystyle\leavevmode\nobreak\
\bigcup_{\bm{\Gamma}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})}\mathcal{D}_{\Gamma}(f).$
(26)

It remains to prove that for any
$z\in\mathcal{B}_{f}\setminus(\mathcal{B}^{\infty}_{\left.f\right|_{*}}\cup\mathcal{B}^{0}_{f})$,
we have $z\in\mathcal{D}_{\Gamma}(f)$ for some
$\bm{\Gamma}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})$. By Lemma 19, we have
$z\in\mathcal{B}_{h}^{\infty}$ for the restricted function
$h:=\left.f\right|_{\\{x_{i}=0\\}}:X\cap\\{x_{i}=0\\}\longrightarrow\mathbb{K}$
for some $i\in[n]$. Without loss of generality, we assume that $i=n$. Notice
that $g$ can also be expressed as the function

$\displaystyle
f_{\Gamma^{\prime}}:=\left.F_{\Gamma_{0}^{\prime}}\right|_{{}_{X\cap\\{x_{n}=0\\}}}\mathbb{V}_{\mathbb{K}}(\bm{g}_{\bm{\Gamma}^{\prime}})\longrightarrow\mathbb{K},$
(27)

where $\bm{\Gamma}^{\prime}\prec\bm{\Delta}$ is the facing whose Minkowski sum
spans the coordinate hyperplane $\\{x_{n}=0\\}\subset\mathbb{R}^{n}$. Indeed,
we deduce this by plugging $x_{n}=0$ into the equations of $\bm{f}$.

By computing the Jacobian matrix, we deduce that
$z\not\in\mathcal{B}_{f}^{0}\Longrightarrow z\not\in\mathcal{B}_{h}^{0}$.
Then, thanks to Lemma 19 and (26) applied to $h$, if
$z\not\in\mathcal{R}_{\Gamma}(h)$ for some important origin facing
$\bm{\Gamma}\prec\bm{\Gamma}^{\prime}$, then $z\in\mathcal{B}_{\ell}$, where
$\ell:=\left.h\right|_{{}_{\\{x_{j}=0\\}}}:X\cap\\{x_{j}x_{n}=0\\}\longrightarrow\mathbb{K}$
for some $j\in[n-1]$. Notice that $\bm{\Gamma}$ is an important facing of
$\bm{\Delta}$, and that $\mathcal{D}_{\Gamma}(f)=\mathcal{D}_{\Gamma}(h)$.

Applying recursively the above arguments, we deduce that either
$z\in\mathcal{D}_{\Gamma}(f)$ for some
$\bm{\Gamma}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})$, or there exists
$\widetilde{\bm{\Gamma}}\in\mathcal{I}\\!\mathcal{O}(\bm{\Delta})$ such that
$z\in\mathcal{B}_{f_{\widetilde{\Gamma}}}$, where
$\widetilde{\Gamma}_{0}=\\{\bm{0}\\}$, and

$\displaystyle
f_{\widetilde{\Gamma}}:=\left.F_{\widetilde{\Gamma}_{0}}\right|_{{}_{X\cap\\{x_{1}\cdots
x_{n}=0\\}}}\mathbb{V}_{\mathbb{K}}(\bm{g}_{\widetilde{\bm{\Gamma}}})\longrightarrow\mathbb{K}.$
(28)

Clearly, we have $f_{\widetilde{\Gamma}}$ is the trivial map whose target
space is the point $\\{F(\bm{0})\\}$. This finishes the proof. ∎

######  Remark 3.

From the proof of Theorem 18, in combination with Eq. (26), we can deduce that
$\mathcal{B}_{f}\subset\mathcal{B}_{\left.f\right|_{*}}$ if $\bm{f}\in\Omega$.

###  4.3 Bounding the infimum

To obtain all the asymptotic critical values it suffices to go through all the
face lattice of $\bm{\Delta}$ and compute the corresponding face discriminant
of $f$, see Eq. (16). As we aim for worst case bounds, we consider the worst
case where all the polynomials are of degree $d$. That is we ignore their
restriction to facings. We emphasize, once more, that is suffices for our
purposes as we are targeting an algorithm but bounds on the bitsize on the
corresponding quantities.

The face discriminant results in a polynomial system of at most
$\mathcal{O}(s+n^{n})$ polynomials; that is the $s$ polynomials $g_{i}$, the
$\mathcal{O}(n^{n})$ polynomials coming from the rank condition on the
Jacobian, and the polynomial $F-z$. The bitsize of the polynomials is at most
$\widetilde{\mathcal{O}}(n\tau)$; dominated by the polynomials from the rank
condition on the Jacobian. Our goal is to bound the roots of this system,
which is 0-dimensional, due to Bertini’s theorem. In particular, we want to
bound $z$, that corresponds to the asymptotic critical values and consequently
to $f^{*}$. Following [13], the bounds appearing in Theorem 4 hold true for
any coordinate of the roots of the system and for $f^{*}$.

##  5 Unconstrained optimization and asymptotic critical values

We present an algorithm (Alg. 1) to compute (and to obtain precise bounds on)
the elements of the Rabier set $\mathcal{K}(f)$, that is the set of
generalized critical values, of a polynomial function
$f:\mathbb{C}^{n}\to\mathbb{C}$, where $f\in\mathbb{Z}[\bm{x}]$. One of these
values corresponds to the global infimum of the (polynomial) optimization
problem $f^{*}=\inf_{\bm{x}\in\mathbb{R}^{n}}f(\bm{x})$. We assume that $f$
has degree $d$ and maximum coefficient bitsize $\tau$, or in short that $f$ is
of size $(d,\tau)$.

###  5.1 Asymptotic critical values over $\mathbb{C}^{n}$

The (pseudo-code of the) algorithm in Alg. 1 supports the computations of the
asymptotic critical values of $f$ and is based on [22]. The main difference is
the way that we perform the elimination. Instead of Gröbner basis we use
resultant matrices to control better the bitsize of the various objects and
the complexity of the overall algorithm. The algorithm relies on the following
notion.

######  Definition 20.

For any $f\in\mathbb{C}[x_{1},\ldots,x_{n}]$, we define a set
$\\{g_{1},\ldots,g_{n-1}\\}\subset\mathbb{C}[x_{1},\ldots,x_{n}]$ of
polynomials given by

$g_{k}:=\sum_{i=1}^{n}a^{(k)}_{i}\frac{\partial f}{\partial
x_{i}}+\sum_{i,j=1}^{n}b^{(k)}_{i,j}x_{i}\frac{\partial f}{\partial
x_{j}},\quad\text{for }k\in[n-1],$

for some choice of coefficients
$(\bm{a},\bm{b}):=(\bm{a}^{(1)},\bm{b}^{(1)},\ldots,\bm{a}^{(n-1)},\bm{b}^{(n-1)})\in\mathbb{C}^{n^{3}-n}$.
Then, the _super polar curve_ of $f$ is the set

$\displaystyle\mathcal{G}_{f}(\bm{a},\bm{b}):=$
$\displaystyle\overline{\mathbb{V}(g_{1},\ldots,g_{n-1})\setminus\operatorname{Crit}(f)},$

where we use here the Zariski closure. The super polar curve is said to be
_non-degenerate_ if $\mathcal{G}_{f}(\bm{a},\bm{b})\subset\mathbb{C}^{n}$ is
indeed a curve, i.e., of dimension 1.

Roughly speaking, super polar curves encapsulate the behaviour at infinity of
the image of (sequence of) points in $\mathbb{C}^{n}$ under $f$ when their
norm tends to infinity. A key point of the algorithm is to ensure that the
linear combinations $g_{k}$ are such that the resulting set
$\mathcal{G}_{f}(\bm{a},\bm{b})$ is non-degenerate.

Input : $f\in\mathbb{Z}[x_{1},\ldots,x_{n}]$

Output : A set $K\in\mathbb{C}$ such that $\mathcal{K}_{\infty}(f)\subset K$.

1

2Choose generic $a^{(k)}_{i}$ and $b^{(k)}_{i,j}$, for $k\in[n-1]$ and
$i,j\in[n]$

3for  _$k\in[n-1]$_ do

4 $g_{k}(\bm{x})=\sum_{i=1}^{n}a^{(k)}_{i}\frac{\partial}{\partial
x_{i}}f(\bm{x})+\sum_{i,j=1}^{n}b^{(k)}_{i,j}x_{i}\frac{\partial}{\partial
x_{j}}f(\bm{x})$ ;

5

6

7for  _$i\in[n]$_ do

8
$\bar{h}_{i}\leftarrow\mathtt{Elim}(\\{g_{1}(\bm{x}),\dots,g_{n-1}(\bm{x}),f(\bm{x})-z\\},\bm{x}_{-i})\in\mathbb{Z}[x_{i},z]$
;

9 $h_{i}\leftarrow\mathtt{lc}(\bar{h}_{i},x_{i})$ ;

10

11

12$h\leftarrow\prod_{i=1}^{n}h_{i}(z)\in\mathbb{Z}[z]$ ;

13

return $K:=\\{\gamma\in\mathbb{C}\,|\,h(\gamma)=0\\}$ /* The distinct roots of
$h\in\mathbb{Z}[z]$ */

Algorithm 1 AsymptoticCriticalValues$(f)$

To study the complexity of Alg. 1, the bitsize of the elements of a linear
transformation that we can apply to $f$ and its derivatives to obtain the
polynomials $g_{k}$, such that the corresponding super-polar curve is non-
degenerate. This bound permits us to estimate the probability of success when
we perform random linear combinations.

Nevertheless, if needed, we can always obtain a Las Vegas algorithm, that is
an algorithm that always returns a correct output, if we allow ourselves the
cost of certifying the result; that is to check if the resulting super-polar
curve is indeed non-degenerate. It was shown in [22] that Alg. 1 computes
correctly the Rabier set of a polynomial $f$. Proving our main result, Theorem
25, relies on the complexity analysis of Alg. 1. For this we need two
technical results. The first is the following proposition, the proof of which
is in the Appendix (Lemma 28).

######  Proposition 21.

Consider an affine variety $V\in\mathbb{C}^{n}$ of dimension $\delta$ and
degree $D$. Let $S$ be finite set of numbers such that $0\not\in S$. Also
consider the linear form $h(\bm{x})=c_{0}+\sum_{i=1}^{n}c_{i}x_{i}$ and
$H=\mathbb{V}(h)$. If we choose the $c_{i}$’s independently and uniformly at
random from $S$, then

$\Pr[\dim(V\cap H)=\delta-1]\geq 1-\tfrac{D}{|S|}.$

Moreover, there is a specialization of the $c_{i}$’s to integers such that
their bitsize is $\lceil\lg(2\kappa D)\rceil+1$, where $\kappa\geq 2$ is a
constant, so that it holds $\dim(V\cap H)=\delta-1$.

The the second technical result is as follows.

######  Lemma 22 (Genericity of the super polar curve).

For any $f\in\mathbb{Z}[x_{1},\ldots,x_{n}]$, there are integers
$(\bm{a},\bm{b})\in\mathbb{Z}^{n^{3}-n}$ of bitsize
$\mathcal{O}(n^{2}+\lg{d})$ such that the super-polar curve
$\mathcal{G}_{f}(\bm{a},\bm{b})$ is non-degenerate.

In addition, if we pick the elements of $(\bm{a},\bm{b})$ uniformly at random
from a set $S$ containing $2\leavevmode\nobreak\ cnd^{n-1}$ elements, where
$c$ is a constant, then the super-polar curve is non-degenerate with
probability $\geq 1-\tfrac{1}{c}$.

###### Proof.

Assume that each of the polynomials The polynomials
$g_{1},\ldots,g_{n-1}\in(\mathbb{Z}[\bm{a},\bm{b}])[\bm{x}]$ are of degree at
most $d$ with respect to $\bm{x}$.

Following [22], we know that if $(\bm{a},\bm{b})$ lies in a Zariski open set
$\mathcal{Z}\subset\mathbb{C}^{n^{3}-n}$, then
$\mathcal{G}_{f}(\bm{a},\bm{b})$ is non-degenerate.

Then, thanks to Proposition 21, there are linear polynomials, say
$L_{0},L_{n}\in\mathbb{Z}[\bm{x}]$, where
$L_{i}=\ell_{i,0}+\sum_{j=1}^{n}\ell_{i,j}x_{j}$ for $i\in\\{0,n\\}$, such
that zero set of the following polynomial system

$\\{L_{0}=g_{1}=\dots=g_{n-1}=L_{n}=0\\},$ (29)

has no solutions for any $(\bm{a},\bm{b})\in\mathcal{Z}$.

The coefficients of the linear polynomials $L_{0}$ and $L_{n}$ are integers,
but for the moments we consider them as (new) parameters. The system (29)
consists of $n+1$ polynomials in $n$ variables, i.e.,
$\\{x_{1},\dots,x_{n}\\}$.

Let $\bm{\ell}$ denote the set of cofficients of $L_{0}$ and $L_{n}$.
Eliminating the variables $\bm{x}$ from the system (29) we obtain an ideal
generated by a polynomial $R\in\mathbb{C}[\bm{\ell},\bm{a},\bm{b}]$, called
the _resultant_. Note that $R$ is not identically zero. Indeed, from
$(\bm{a},\bm{b})\in\mathcal{Z}$, we get
$\dim(\mathcal{G}_{f}(\bm{a},\bm{b}))=1$ and thus Proposition 21 guarantees
that there are (two) linear polynomials, hence a specialization of
$\bm{\ell}$, such that the system in (29) has no solutions. Therefore, for any
choice $(\bm{\ell},\bm{a},\bm{b})$ such that $(\bm{a},\bm{b})\in\mathcal{Z}$
and $R(\bm{\ell},\bm{a},\bm{b})\neq 0$, we have
$\dim\mathcal{G}_{f}(\bm{a},\bm{b})=1$ and (29) has no solutions.

Notice that $R\in(\mathbb{Z}[\bm{c},\bm{\ell}])[\bm{a},\bm{b}]$ and as a
polynomials in $\bm{a}$, or $\bm{b}$ it has at most $n^{3}-n$ variables and
its total degree is at most $nd^{n-1}$.

Following the DeMillo-Lipton-Schwartz-Zippel (DLSZ) lemma [29, 39, 36], if $S$
is a finite set of integers, then $R$ has at most $2nd^{n-1}|S|^{n^{3}-n-1}$
solutions in the grid $S^{n^{3}-n}$.

If $S$ contains the first $2\leavevmode\nobreak\ cnd^{n-1}$ integers (where
$c$ is a constant greater than 2), then we deduce that there is a
specialization of $(\bm{a},\bm{b})$ such that $\dim(\Gamma)=1$. Also the
bitsize of the elements of $\bm{a}$ and $\bm{b}$ is
$\mathcal{O}(n^{2}+\lg(d))$.

Moreover, thanks to (DLSZ), if we pick a specialization for $(\bm{a},\bm{b})$
uniformly at random in the grid $S^{n^{3}-n}$, then $\dim(\Gamma)=1$ with
probability $\geq 1-\tfrac{1}{c}$. ∎

######  Theorem 23.

Let $f\in\mathbb{Z}[\bm{x}]$ be of (total) degree at most $d$ and bitsize
$\tau$. Then, Alg. 1 is a Monte Carlo algorithm that computes the asymptotic
critical values in $\widetilde{\mathcal{O}}_{B}(n^{\omega
n-\omega+1}d^{(\omega+3)n-\omega-1}\tau)$ bit operations, where $\omega$ is
the exponent of the complexity of matrix multiplication.

The asymptotic critical values are algebraic numbers of degree
$\mathcal{O}(d^{n-1})$ and the (sum of the) bitsize(s) of their isolating
intervals (or boxes) is $\widetilde{\mathcal{O}}(nd^{2n-2}\tau+n^{2}d^{n-1})$.

###### Proof.

First we construct the polynomials $g_{k}$, for $k\in[n-1]$; they are of
degree $d$. Following Lemma 22 the bitsize of elements of $\bm{a}$ and
$\bm{b}$ is $\mathcal{O}(n^{2}+\lg{d})$, hence the bitsize of $g_{k}$ is
$\mathcal{O}(\tau+n^{2}+\lg{d})$.

Then we consider the set of polynomials

$\\{g_{1},\dots,g_{n-1},f-z\\},$ (30)

and we eliminate the variables $x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n}$, for
$i\in[n]$. Thus, we perform the elimination $n$ times.

Without loss of generality, we may assume that $i=n$.

After eliminating the variables $x_{1},\dots,x_{n-1}$ from the set of
polynomials in (30), we obtain a polynomial $R_{n}\in\mathbb{Z}[x_{n},z]$;
this is the resultant of the polynomials in (30). We compute $R_{n}$ using the
Macaulay matrix, say $M$, corresponding to the system in (30). In particular
we express $R_{n}$ as the ratio of two determinant of (sub)matrices of $M$. It
might happen that the determinant in the denominator is zero. To avoid this
problem and still compute $R_{n}$ we use the technique of generalized
characteristic polynomial [6]. For this we perturb symbolically the
polynomials $g_{i}$ to become $G_{i}=g_{i}+sx_{i}^{d}$, where $s$ is a new
variable and $i\in[n-1]$; and $G_{n}=f-z$. In this way, the ratio of
determinants from $M$ result in a polynomial $S_{n}\in\mathbb{Z}[x_{n},z][s]$.
The non-vanishing coefficient of $S_{n}\in\mathbb{Z}[s]$, in front of the
monomial with the smallest degree in $s$, is a power of $R_{n}$.

To obtain bounds on $S_{n}$ and $R_{n}$ we rely on [13]. Following [8],
$S_{n}$ is homogeneous in the coefficients of the each polynomial $G_{i}$. In
particular, each term of $S_{n}$ is as follows

$\varrho_{k}|\bm{c}_{1}|^{d^{n-1}}\cdots|\bm{c}_{n}|^{d^{n-1}},$

where the semantics of $|\bm{c}_{i}|^{d^{n-1}}$ are that it represents a
product of coefficients of the polynomial $G_{i}$ all of which have total
degree $d^{n-1}$. The coefficients of $G_{i}$ are in $\mathbb{Z}[x_{n},z,s]$,
they have multidegree $(d,0,1)$, for $i\in[n-1]$ and $G_{n}$ has multidegree
$(d,1,0)$; their bitsize $\tau$. Hence, $|c_{i}|^{d^{n-1}}$ is of multidegree
$(d^{n},0,d^{n-1})$ for $i\in[n-1]$ and $G_{n}$ has multidegree
$(d^{n},d^{n-1},0)$; their bitsize $\mathcal{O}(d^{n-1}\tau+d^{n-1}\lg(d))$.
Also $\lg|\varrho_{k}|=\mathcal{O}(nd^{n-1}\lg(d))$. Consequently, each term
is a polynomial in $\mathbb{Z}[x_{n},z,s]$ of multidegreee
$(d^{n},d^{n-1},d^{n-1})$ and bitsize
$\mathcal{O}(nd^{n-1}\tau+nd^{n-1}\lg(d)+n^{2}\lg(nd))$, using Claim 26. As
there are at most $\mathcal{O}(d^{3n})$ terms, the bitsize of $S_{n}$ and
$R_{n}$ is $\mathcal{O}(nd^{n-1}\tau+nd^{n-1}\lg(d)+n^{2}\lg(nd))$.

To actually compute $S_{n}$ and $R_{n}$ we use perform the elimination using
the Macaulay matrix. We consider the homogenization of the polynomials
$G_{1},\dots,G_{n}$. be introducing a new variable $x_{0}$.

Let $m=\sum_{i=1}^{m}(d-1)+1=n(d-1)+1\leq nd$ and $N={m+n-1\choose
n-1}\leq(nd)^{d-1}$. The latter corresponds to all monomials in $n$ variables
of degree $\leq m$.

As the elements of $M$ are polynomials in $\mathbb{Z}[x_{n},z,s]$ we apply
Kronecker’s trick to obtain univariate polynomials. In particular, we perform
the transformation $x_{n}\leftarrow s^{d^{n-1}+1}$ and $z\leftarrow
s^{(d^{n-1}+1)d^{n}}$. Then, the elements of $M$ become polynomials in
$\mathbb{Z}[s]$ of degree $\leq d^{2n-1}+d^{n}+1=\mathcal{O}(d^{2n})$. Now, we
can compute the determinants
$\mathcal{O}(N^{\omega}d^{2n})=n^{\omega(n-1)}d^{(\omega+2n)-\omega}$
arithmetic operations.

If we account on the bitsize of $S_{n}$ (and $R_{n}$) we deduce that we can
compute them $\widetilde{\mathcal{O}}_{B}(n^{\omega
n-\omega+1}d^{(\omega+3)n-\omega-1}\tau)$ bit operations.

Hence, after we arrange the terms of the resultant, we can recover the
polynomial and $\bar{h}_{n}$ and thus $h_{n}\in\mathbb{Z}[z]$. The latter has
size $(d^{n-1},\widetilde{\mathcal{O}}(nd^{n-1}\tau+n^{2}))$.

We isolate its real (or complex) real roots in
$\widetilde{\mathcal{O}}_{B}(nd^{3n-3}\tau+n^{2}d^{2n-2})$ [33]. The (sum of
the) bitsize of the isolating interval(s) (or boxes if we consider the complex
roots) of the roots is $\widetilde{\mathcal{O}}(nd^{2n-2}\tau+n^{2}d^{n-1})$,
e.g., [13]. ∎

###  5.2 Polynomial optimization over $\mathbb{R}^{n}$

In this part, we show how to use the Rabier set of $f$ (3), together with Alg.
1, for computing the global infimum over $\mathbb{R}^{n}$. Following Theorem 8
(see also, [38]), it holds that

$\inf_{x\in\mathbb{R}^{n}}f(x)\subset\mathcal{K}(f)\cap\mathbb{R},$ (31)

where $\mathcal{K}(f)=\mathcal{K}_{0}(f)\cup\mathcal{K}_{\infty}(f)$ is the
Rabier set of critical values of $f$. It remains to identify which of these
values corresponds to the infimum of $f$.

If the Rabier values are $e_{1},\dots,e_{m}$, then we need to compute rational
numbers that interlace them [38], that is $r_{i}$ for $0\leq i\leq m$, such
that

$r_{0}<e_{1}<r_{1}<\dots<r_{m-1}<e_{m}<r_{m}$

and test if the real hypersurfaces $H_{i}:=f^{-1}(r_{i})\cap\mathbb{R}^{n}$
are empty or not. The bitsize of corresponding polynomial defining $H_{i}$ is
dominated by the bitsize of $r_{i}$, let it be $\sigma_{i}$. Thanks to Theorem
23, we have

$\sum_{i=0}^{m}\sigma_{i}=\widetilde{\mathcal{O}}(nd^{2n-2}\tau+n^{2}d^{n-1}).$

Next, we need the following theorem.

######  Theorem 24 ([12]).

For $f\in\mathbb{Z}[\bm{x}]$ of size $(d,\tau)$ there is a randomized
algorithm that with probability $1-\epsilon$ decides if
$\mathbb{V}(f)\cap\mathbb{R}^{n}$ is empty or not using
$\widetilde{\mathcal{O}}_{B}(d^{3n}\lg(\tfrac{1}{\epsilon})(\tau+\lg(\tfrac{1}{\epsilon})))$
bit operations.

Using Theorem 24 we can test the emptiness of all the real hypersurfaces in

$\sum_{i=0}^{m}\widetilde{\mathcal{O}}_{B}(d^{3n}\lg(\tfrac{1}{\epsilon})(\sigma_{i}+\lg(\tfrac{1}{\epsilon})))=\widetilde{\mathcal{O}}_{B}(d^{3n}\lg(\tfrac{1}{\epsilon})(nd^{2n-2}\tau+\lg(\tfrac{1}{\epsilon})))$

bit operations with probability of success $1-\tfrac{1}{\epsilon}$.

This bounds is the complexity of a Monte Carlo algorithm for optimizing a
multivariate polynomial over $\mathbb{R}^{n}$.

By combining all the previous results, we have the following theorem.

######  Theorem 25.

Let $f\in\mathbb{Z}[x]$ be of degree $d$ and bitsize $\tau$. We can compute
the optimum value of the problem
$f^{*}=\inf{\bm{x}\in\mathbb{R}^{n}}f(\bm{x})$ in
$\widetilde{\mathcal{O}}_{B}(d^{3n}\lg(\tfrac{1}{\epsilon})(nd^{2n-2}\tau+\lg(\tfrac{1}{\epsilon})))$
bit operations, with probability of success $1-\tfrac{1}{\epsilon}$.

In addition, it holds $2^{-\eta}\leq|f^{*}|\leq 2^{\eta}$, where
$\eta=\widetilde{\mathcal{O}}(nd^{n-1}\tau+n^{2}))$. To distinguish $f^{*}$
from the other generalized critical values, we need approximate it with up to
precision of at most $\widetilde{\mathcal{O}}(nd^{2n-2}\tau+n^{2}d^{n-1})$
bits.

## References

  * [1] C. Bajaj.  The algebraic degree of geometric optimization problems.  Discrete & Computational Geometry, 3:177–191, 1988.
  * [2] S. Basu, R. Pollack, and M-F.Roy.  Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics.  Springer-Verlag, 2003.
  * [3] S. Basu, R. Pollack, and M.-F. Roy.  Algorithms in Real Algebraic Geometry.  Springer Berlin Heidelberg, 2006.
  * [4] C. W. Brown and J. H. Davenport.  The complexity of quantifier elimination and cylindrical algebraic decomposition.  In Proceedings of the 2007 international symposium on Symbolic and algebraic computation, pages 54–60, 2007.
  * [5] M. Burr, S. Gao, and E. Tsigaridas.  The complexity of subdivision for diameter-distance tests.  Journal of Symbolic Computation, 101:1–27, 2020.
  * [6] J. Canny.  Generalised characteristic polynomials.  Journal of Symbolic Computation, 9(3):241–250, Mar. 1990.
  * [7] B. F. Caviness and J. R. Johnson.  Quantifier elimination and cylindrical algebraic decomposition.  Springer Science & Business Media, 2012.
  * [8] D. A. Cox, J. Little, and D. O’shea.  Using algebraic geometry, volume 185.  Springer, 2006.
  * [9] M. L. Dogan, A. A. Ergür, and E. Tsigaridas.  On the complexity of chow and hurwitz forms.  ACM Communications in Computer Algebra, 57(4):167–199, 2024.
  * [10] J. Draisma, E. Horobeţ, G. Ottaviani, B. Sturmfels, and R. R. Thomas.  The euclidean distance degree of an algebraic variety.  Foundations of Computational Mathematics (FoCM), 16:99–149, 2016\.
  * [11] A. H. Durfee.  Five definitions of critical point at infinity.  pages 345–360. Springer, 1998.
  * [12] J. Elliott, M. Giesbrecht, and É. Schost.  On the bit complexity of finding points in connected components of a smooth real hypersurface.  In Proc. 45th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 170–177, 2020.
  * [13] I. Emiris, B. Mourrain, and E. Tsigaridas.  Separation bounds for polynomial systems.  Journal of Symbolic Computation, 101:128–151, 2020.
  * [14] A. Esterov.  Newton polyhedra of discriminants of projections.  Discrete Comput. Geom., 44(1):96–148, 2010.
  * [15] A. Esterov.  The discriminant of a system of equations.  Advances in Mathematics, 245:534–572, 2013.
  * [16] G. Farin and D. Hansford.  Curves and surfaces for CAGD: a practical guide.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5 edition, 2002\.
  * [17] A. Garg.  Special case algorithms for Nullstellensatz and transcendence degree.  Master’s thesis, IIT Kanpur, 2020.
  * [18] I. M. Gel’fand, M. M. Kapranov, and A. V. Zelevinsky.  Discriminants, resultants, and multidimensional determinants.  Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1994.
  * [19] M. Giusti and J. Heintz.  La détermination de la dimension et des points isolées d’une variété algébrique peuvent s’ effectuer en temps polynomial.  In Computational Algebraic Geometry and Commutative Algebra, Cortona, volume 34, pages 216–256, 1991.
  * [20] Z. Jelonek and K. Kurdyka.  On asymptotic critical values of a complex polynomial.  J. Reine Angew. Math., 565:1–11, 2003.
  * [21] Z. Jelonek and K. Kurdyka.  Quantitative generalized bertini-sard theorem for smooth affine varieties.  Discrete Comput. Geom., 34(4):659–678, 2005.
  * [22] Z. Jelonek and M. Tibăr.  Detecting asymptotic non-regular values by polar curves.  International Mathematics Research Notices, 2017(3):809–829, 2017\.
  * [23] G. Jeronimo and D. Perrucci.  A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set.  Discrete & Computational Geometry, 52(2):260–277, 2014.
  * [24] G. Jeronimo, D. Perrucci, and E. Tsigaridas.  On the minimum of a polynomial function on a basic closed semialgebraic set and applications.  SIAM Journal on Optimization, 23(1):241–255, 2013.
  * [25] J.-P. Jouanolou.  Théorèmes de Bertini et applications.  Birkhäuser, Boston, 1983.
  * [26] H. K. Khalil.  Nonlinear systems, volume 3.  Prentice hall Upper Saddle River, NJ, 2002.
  * [27] E. Kunz.  Introduction to commutative algebra and algebraic geometry.  Springer Science & Business Media, 1985.
  * [28] C. La Valle and J. Tonelli-Cueto.  Some lower bounds on the reach of an algebraic variety.  arXiv e-prints, pages arXiv–2402, 2024.
  * [29] R. J. Lipton.  The curious history of Schwarz-Zippel Lemma.  https://rjlipton.wordpress.com /2009/11/30/the-curious-history-of -the-schwartz-zippel-lemma/, 2009.
  * [30] A. Mantzaflaris, É. Schost, and E. Tsigaridas.  Sparse rational univariate representation.  In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 301–308, 2017.
  * [31] A. Némethi.  Theorie de Lefschetz pour variétés algebriques affines.  CR Acad. Sc. Paris, 303:567–570, 1986.
  * [32] A. Némethi and A. Zaharia.  On the bifurcation set of a polynomial function and newton boundary.  Publications of the Research Institute for Mathematical Sciences, 26(4):681–689, 1990.
  * [33] V. Y. Pan.  Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding.  Journal of Symbolic Computation, 33(5):701–733, 2002.
  * [34] T. S. Pham and H. H. Vui.  Genericity in polynomial optimization, volume 3.  World Scientific, 2016.
  * [35] P. J. Rabier.  Ehresmann fibrations and Palais–Smale conditions for morphisms of Finsler manifolds.  Ann. of Math., pages 647–691, 1997.
  * [36] O. E. Raz, M. Sharir, and J. Solymosi.  ”Polynomials vanishing on grids: The Elekes-Rónyai problem revisited”.  In Proceedings of the thirtieth annual symposium on Computational geometry, page 251. ACM, 2014.
  * [37] M. Safey El Din.  Testing sign conditions on a multivariate polynomial and applications.  Mathematics in Computer Science, 1(1):177–207, 2007.
  * [38] M. Safey El Din.  Computing the global optimum of a multivariate polynomial over the reals.  In Proc. ACM 21st International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 71–78, 2008.
  * [39] N. Saxena.  Progress on polynomial identity testing.  Bulletin of the EATCS, 99:49–79, 2009.
  * [40] M. Schaefer and D. Štefankovič.  Fixed points, nash equilibria, and the existential theory of the reals.  Theory of Computing Systems, 60(2):172–193, 2017.
  * [41] J. T. Schwartz and M. Sharir.  On the “piano movers’” problem i. the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers.  Communications on pure and applied mathematics, 36(3):345–398, 1983\.
  * [42] I. R. Shafarevich and M. Reid.  Basic algebraic geometry, volume 2.  Springer, 1994.
  * [43] B. Siciliano, L. Sciavicco, L. Villani, and G. Oriolo.  Robotics: modelling, planning and control.  Springer Science and Business Media, 2009.
  * [44] Z. Song, D. P. Woodruff, and P. Zhong.  Low rank approximation with entrywise l1-norm error.  In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 688–701, 2017.
  * [45] R. Thom.  Ensembles et morphismes stratifiés.  Bull. Am. Math. Soc., 75(2):240–284, 1969.
  * [46] M. Tibăr.  Regularity at infinity of real and complex polynomial functions.  London Mathematical Society Lecture Note Series, pages 249–264, 1999.
  * [47] M. Tibăr.  Polynomials and vanishing cycles, volume 170.  Cambridge University Press, 2007.
  * [48] B. L. Van der Waerden.  Moderne algebra.  1937\.
  * [49] A. N. Varchenko.  Theorems on the topological equisingularity of families of algebraic varieties and families of polynomial mappings.  Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 36(5):957–1019, 1972.
  * [50] J.-L. Verdier.  Stratifications de Whitney et théoreme de Bertini-Sard.  Invent. Math., 36(1):295–312, 1976.
  * [51] H. H. Vui and P. T. Son.  Critical values of singularities at infinity of complex polynomials.  Vietnam Journal of Mathematics, 36(1):1–38, 2008.
  * [52] A. Wallace.  Linear sections of algebraic varieties.  Indiana Univ. Math. J., 20(12):1153–1162, 1971.
  * [53] C.-K. Yap.  Fundamental problems of algorithmic algebra.  Oxford University Press, New York, 2000.
  * [54] A. Zaharia.  On the bifurcation set of a polynomial function and Newton boundary. II.  Kodai Math. J., 19(2):218–233, 1996.

##  Appendix A Useful results and bounds

###  A.1 Multivariate polynomial multipication

We need the following result(s) on multivariate polynomial multiplication. For
the rather straightforward proofs we refer the reader to [30].

######  Claim 26 (Output bounds on polynomial multiplication).

The following bounds holds:

  1. (i)

Consider two multivariate polynomials, $f_{1}$ and $f_{2}$, in $\nu$ variables
of total degrees $\delta$, having bitsize $\tau_{1}$ and $\tau_{2}$,
respectively. Then $f=f_{1}f_{2}$ is a polynomial in $\nu$ variables, of total
degree $2\delta$ and bitsize $\tau_{1}+\tau_{2}+2\,\nu\,\lg(\delta)$.

  2. (ii)

Using induction, the product of $m$ polynomials in $\nu$ variables,
$f=\prod_{i=1}^{m}f_{i}$, each of total degree $\delta_{i}$ and bitsize
$\tau_{i}$, is a polynomial of total degree $\sum_{i=1}^{m}{\delta_{i}}$ and
bitsize
$\sum_{i=1}^{m}\tau_{i}+12\,\nu\,m\,\lg(m)\,\lg(\sum_{i=1}^{m}{\delta_{i}})$.

  3. (iii)

Let $f$ be a polynomial in $\nu$ variables of total degree $\delta$ and
bitsize $\tau$. The $m$-th power of $f$, $f^{m}$, is a polynomial of total
degree $m\delta$ and bitsize $m\tau+12\nu m\lg(\delta)$.

###  A.2 Intersecting a variety

######  Theorem 27 ([42, Cor. 1.13, Sec. 6, Chapter 1]).

Consider an irreducible projective variety $V\subset\mathbb{P}^{n}$ of
dimension $\delta$. If a homogeneous polynomial $f$ does not vanish on $V$,
then $\dim(V\cap\mathbb{V}(f))=\delta-1$. In addition, all the components of
the intersection have the same dimension.

The following lemma is similar to the ones in [17, Chapter 3].

######  Lemma 28.

Consider a projective variety $V\in\mathbb{P}^{n}$ of dimension $\delta$ and
degree $D$. Let $S$ be finite set of integers such that $0\not\in S$. Also
consider the linear form $h(\bm{x})=\sum_{i=0}^{n}c_{i}x_{i}$ and
$H=\mathbb{V}(h)$. If we choose the $c_{i}$’s independently and uniformly at
random from $S$, then

$\Pr[\dim(V\cap H)=\delta-1]\geq 1-\tfrac{D}{|S|}.$

Moreover, there is a specialization of the $c_{i}$’s such that their bitsize
is $\lceil\lg(\kappa D)\rceil+1$, where $\kappa\geq 2$ is a constant, so that
it holds $\dim(V\cap H)=\delta-1$.

###### Proof.

Let $V=\bigcup_{j=1}^{r}V_{j}$ be the irreducible decomposition of $V$, where
$\deg(V_{j})\geq 1$ and $\dim(V_{j})=\delta_{j}$. Notice that $r\leq D$, as
the number of components is bounded by the degree of the variety; in addition,
$D=\sum_{i=j}^{r}\deg(V_{j})$. Let $h(\bm{x})=\sum_{i=0}^{n}c_{i}x_{i}$, where
we consider the $c_{i}$’s as intermediates that we will specialize in the
sequel.

First, we consider the component $V_{j}$. Due to Theorem 27, $\dim(V_{j}\cap
H)=\delta_{j}-1$ or $\dim(V_{j}\cap H)=\delta_{j}$. In the latter case
$V_{j}\subseteq H$ and so if $\bm{p}_{j}=(p_{j0},\dots,p_{jn})\in V_{j}$, then
it holds $\bm{p}_{j}\in H$.

We evaluate $h$ at $\bm{p}_{j}$, that is $h_{j}=\sum_{i=0}^{n}c_{i}p_{ji}$ and
we consider $h_{j}$ as a polynomial in the $c_{i}$’s. Then $h_{j}$ has at most
$|S|^{n}$ solutions in the grid $\underbrace{S\times\cdots\times
S}_{n+1}=S^{n+1}$. In other words there, are at most $|S|^{n}$ specializations
of the $c_{i}$’s in the grid $S^{n+1}$ such that $\dim(V_{j}\cap
H)=\delta_{j}$. Consequently,

$\Pr[\dim(V_{j}\cap H)=\delta_{j}]\leq\tfrac{|S|^{n}}{|S|^{n+1}}=1/|S|.$

Thus

$\Pr[\bigcup_{j=1}^{r}\\{\dim(V_{j}\cap
H)=\delta_{j}\\}]\leq\sum_{j=1}^{r}\Pr[\dim(V_{j}\cap
H)=\delta_{j}]\leq\tfrac{r}{|S|}\leq\tfrac{D}{|S|},$

which implies

$\Pr[\dim(V\cap H)=\delta-1]=1-\Pr[\bigcup_{j=1}^{r}\\{\dim(V_{j}\cap
H)=\delta_{j}\\}]\geq 1-\frac{D}{|S|}.$

If we choose as $S$ the first $\kappa D$ positive integers, where $\kappa\geq
2$ is a constant, then there is at least one specialization of the $c_{i}$’s
in the grid $S^{n+1}$ such that $\dim(V_{j}\cap H)=\delta_{j}-1$, for all
$j\in[r]$; and so the bound on the bitsize follows. ∎

###### Proof of Proposition 21.

In the affine case, we have to also consider the case $V\cap H=\varnothing$,
in addition to the two cases of Theorem. 27. Let $\bar{V}$ and $\bar{H}$ be
the projective closures of $V$ and $H$, respectively. It holds
$\dim(\bar{V})=\delta$ and $\deg(\bar{V})=D$; also
$\bar{V}\cap\bar{H}\not=\varnothing$, expect if $\dim(\bar{V})=0$.

If $V\cap H=\varnothing$, then intersection $\bar{V}\cap\bar{H}$ occurs at the
hyperplane at infinity, say $L_{\infty}$.

If we want to hold $\dim(V\cap H)=\delta=1$, then (i)
$\dim(\bar{V}\cap\bar{H})=\delta-1$ and (ii) $\bar{V}\cap\bar{H}\not\subseteq
L_{\infty}$, unless $\bar{V}\cap\bar{H}=\varnothing$.

_The second condition implies if $V\cap H=\varnothing$, then
$\bar{V}\cap\bar{H}$ is contained at infinity. Thus, the dimension of
$\bar{V}\cap\bar{H}$ is $\dim(\bar{V})$ and because affine varieties and their
projective closures have the same dimension, it also holds that $\dim(V\cap
H)=\delta$. We want to avoid this situation. _

For the first condition, as $\bar{V}$ and $\bar{H}$ are projective varieties,
we can use Lemma 28. Thus

$\Pr\geq 1-\frac{D}{|S|}$

and we can also select $c_{i}$’s.

For the second condition, we notice that $\bar{V}\not\subseteq L_{\infty}$.
Hence, by Theorem 27, $\dim(\bar{\cap}L_{\infty})=\delta-1$. Now, consider the
projective varieties $\bar{V}\cap L_{\infty}$ and $\bar{H}$.

If it happens, following Lemma 28 that

$\Pr[\dim(\bar{V}\cap L_{\infty}\cap\bar{H})=\delta-2]\geq 1-\frac{D}{|S|}$

and we can also find appropriate $c_{i}$’s.

If it happens that $\dim(\bar{V}\cap L_{\infty}\cap\bar{H})=\delta-2$, then
$\bar{V}\cap\bar{H}\not\subseteq L_{\infty}$. This is so, because otherwise
$\bar{V}\cap L_{\infty}\cap\bar{H}=\bar{V}\cap\bar{H}$, where the dimensions
are $\delta-2$ and $\delta-1$, respectively. This is a contradiction.

Using the union bound, we deduce the required probability bound. ∎

###  A.3 Reduction to a square system

Our techniques on bounding the bitsize and the degrees of the various
polynomials appearing in the polynomial optimization problems rely on
exploiting the properties of the resultant. However, to use the resultant the
corresponding polynomial systems have to have as many equations as variables;
that is we need to compute with square systems. In the optimization problems
that we are interested in, in almost all the cases, the number of polynomials
is bigger than the number of unknowns.

We are able to treat this case using a result due to Giusti and Heinz [19].
Let $f_{1},\dots,f_{p}\in\mathbb{Q}\left[x_{1},\dots,x_{n}\right]$ be
polynomials of positive degree, bounded by $d$. Denote by $V$ the algebraic
variety $\mathbb{V}(f_{1},\dots,f_{p})\subseteq\mathbb{C}^{n}$. Given
$\eta\in\overline{\mathbb{Q}}$, we denote by $\hat{f}_{\eta}$ the linear
combination $f_{1}+\eta^{1}f_{2}+\dots+\eta^{p-1}f_{p}$.

######  Theorem 29.

[19, Section 3.4.1] Let $\Gamma\subset\mathbb{Z}$ of cardinal $p\,d^{n}+1$.
There exists $\gamma=\left(\gamma_{1},\dots,\gamma_{n}\right)\in\Gamma^{n}$
such that each irreducible component of
$\hat{V}=\mathbb{V}(\hat{f}_{\gamma_{1}},\dots,\hat{f}_{\gamma_{n}})$ is
either a component of $V$ or a point.

###### Proof.

First, it is clear that for all $x\in V$, any linear combination of the
polynomials $f_{1},\dots,f_{p}$ vanishes at $x$.

Then for $1\leq i\leq n$ and
$\left(\gamma_{1},\dots,\gamma_{i}\right)\in\Gamma^{i}$, let us denote by
$\hat{V}_{i}$ the variety
$\mathbb{V}(\hat{f}_{\gamma_{1}},\dots,\hat{f}_{\gamma_{i}})$. We prove by
induction that for $1\leq i\leq n$, there exist points
$\gamma_{1},\dots,\gamma_{i}\in\Gamma$ such that the dimension of any
irreducible component of $\hat{V}_{i}$ not contained in $V$ is $n-i$.

The case $i=1$ is obvious. Let $i>1$ and assume that the result is proved for
$i-1$. Let
$\hat{V}_{i-1}=\mathbb{V}(\hat{f}_{\gamma_{1}},\dots,\hat{f}_{\gamma_{i-1}})$
and let $C$ be an irreducible component of $\hat{V}_{i-1}$ such that
$C\not\subset V$. Let $x_{C}$ be a point in $C\setminus V$, so that at least
one polynomial among $f_{1},\dots,f_{p}$ does not vanish at $x_{C}$. Let $T$
be a new indeterminate and let

$w_{C}\left(T\right)=f_{1}\left(x_{C}\right)+Tf_{2}\left(x_{C}\right)+\dots+T^{p-1}f_{p}\left(x_{C}\right)\in\overline{\mathbb{Q}}\left[T\right].$

By construction, $w_{C}$ is not identically zero. Hence, so is the product
$P_{i}\left(T\right)=\prod_{C}w_{C}\left(T\right)$, for all irreducible
component $C$ of $\hat{V}_{i-1}$ not included in $V$. By the Bézout bound,
there are at most $d^{n}$ such components. Hence, the polynomial
$P_{i}\left(T\right)$ has degree at most $pd^{n}$ so that it has at most
$pd^{n}$ roots. Since $\Gamma$ has cardinal $pd^{n}+1$, there exists
$\gamma_{i}\in\Gamma$ such that $P_{i}\left(\gamma_{i}\right)\neq 0$. Let
$\hat{f}_{\gamma_{i}}=f_{1}+\gamma_{i}f_{2}+\dots+\gamma_{i}^{s-1}f_{p}$.

Then for any $x_{C}$ as above, $\hat{f}_{\gamma_{i}}\left(x_{C}\right)\neq 0$.
In particular, this means that $C\not\subset\mathbb{V}(\hat{f}_{\gamma_{i}})$.

By Krull’s Principal Ideal Theorem [27, Corollary 3.2 p. 131], this implies
that the intersection $C\cap\mathbb{V}(\hat{f}_{\gamma_{i}})$ is either empty
or equidimensional of dimension $\dim C-1$. By induction assumption, $C$ has
dimension $n-i+1$. Hence, $C\cap\mathbb{V}(\hat{f}_{\gamma_{i}})$ is either
empty or of equidimensional of dimension $n-i$. Since this is true for any
irreducible component $C$ of $\hat{V}_{i-1}$ not contained in $V$, this proves
that the dimension of any irreducible component of $\hat{V}_{i}$ not contained
in $V$ is $n-i$.

In particular for $i=n$, this proves that the irreducible components of
$\hat{V}=\hat{V}_{n}$ not contained in $V$ have dimension $0$, so that it is
necessarily a point. ∎

######  Remark 4.

The previous theorem implies that if we are given a polynomial system that it
is not necessarily square, then we can make square by considering a generic
linear combination. The price that we pay for this is that the bitsize of the
polynomials becomes
$\mathcal{O}(\tau+n\lg(pd))=\widetilde{\mathcal{O}}(\tau+n)$ from $\tau$ and
that we add additional points to the variety. For out purposes, the increase
in the in bitsize is negligible.