Improved effective Łojasiewicz inequality and applications

Saugata Basu Department of Mathematics, Purdue University, West Lafayette, IN 47906, U.S.A. [email protected] and Ali Mohammad-Nezhad Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15123, U.S.A. [email protected]

Abstract.

Let $\mathrm{R}$ be a real closed field. Given a closed and bounded semi-algebraic set $A\subset\mathrm{R}^{n}$ and semi-algebraic continuous functions $f,g:A\rightarrow\mathrm{R}$ , such that $f^{-1}(0)\subset g^{-1}(0)$ , there exist $N$ and $c\in\mathrm{R}$ , such that the inequality (Łojasiewicz inequality) $|g(x)|^{N}\leq c\cdot|f(x)|$ holds for all $x\in A$ . In this paper we consider the case when $A$ is defined by a quantifier-free formula with atoms of the form $P=0,P>0,P\in\mathcal{P}$ for some finite subset of polynomials $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ , and the graphs of $f,g$ are also defined by quantifier-free formulas with atoms of the form $Q=0,Q>0,Q\in\mathcal{Q}$ , for some finite set $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]_{\leq d}$ . We prove that the Łojasiewicz exponent $N$ in this case is bounded by $(8d)^{2(n+7)}$ . Our bound depends on $d$ and $n$ , but is independent of the combinatorial parameters, namely the cardinalities of $\mathcal{P}$ and $\mathcal{Q}$ . The previous best known upper bound in this generality appeared in P. Solernó, Effective Łojasiewicz Inequalities in Semi-algebraic Geometry, Applicable Algebra in Engineering, Communication and Computing (1991) and depended on the sum of degrees of the polynomials defining $A,f,g$ and thus implicitly on the cardinalities of $\mathcal{P}$ and $\mathcal{Q}$ . As a consequence we improve the current best error bounds for polynomial systems under some conditions. Finally, as an abstraction of the notion of independence of the Łojasiewicz exponent from the combinatorial parameters occurring in the descriptions of the given pair of functions, we prove a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We prove the existence of a common Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions. This improves a prior result of Chris Miller (C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic (1994)).

Key words and phrases:

Łojasiewicz inequality, combinatorial complexity, error bounds, polynomially bounded o-minimal structures

2000 Mathematics Subject Classification:

Primary 14P10; Secondary 03C64, 90C23

1. Introduction

L. Schwartz conjectured that if $f$ is a real analytic function and $T$ a distribution in some open subset $\Omega\subset\mathrm{R}^{n}$ , then there exists a distribution $S$ satisfying $fS=T$ . As a main tool in proving this conjecture, Łojasiewicz [31] proved that if $V$ is the set of real zeros of $f$ , and $x$ in a sufficiently small neighborhood of a point $x_{0}$ in $V$ , there exists a constant $d$ such that

|f(x)|\geq d\cdot{\rm dist}(x,V)^{d},

where ${\rm dist}(x,V)$ denotes the distance of $x$ from $V$ . In case $f$ is a polynomial the result was obtained by Hörmander [18].

Several variants of Łojasiewicz inequality have appeared in the literature both in the semi-algebraic and analytic categories. In the semi-algebraic category, the following slightly more general version of the above inequality appears in [10, Corollary 2.6.7].

Unless otherwise specified $\mathrm{R}$ is a fixed real closed field for the rest of the paper.

Let $A\subset\mathrm{R}^{n}$ be a closed and bounded semi-algebraic set and let $f,g:A\to\mathrm{R}$ be continuous semi-algebraic functions. Furthermore, suppose that $f^{-1}(0)\subset g^{-1}(0)$ . Then there exist $c\in\mathrm{R}$ and a rational number $\rho$ depending on $A$ , $f$ , and $g$ , such that

(1.1)

|g(x)|^{\rho}\leq c\cdot|f(x)|,\quad\forall x\in A.

We denote the infimum of $\rho$ by $\mathcal{L}(f,g\mid A)$ which is called the Łojasiewicz exponent.

The inequality (1.1) is usually called the Łojasiewicz inequality and has found many applications (independent of the division problem of L. Schwartz) – for example, in singularity theory, partial differential equations, and optimization. We survey some of these applications later in the paper and improve some of these results using the version of Łojasiewicz inequality proved in the current paper.

Driven by the applications mentioned above there has been a lot of interest in obtaining effective bounds on $\mathcal{L}(f,g\mid A)$ .

2. Main results

In this paper we prove new quantitative versions of the inequality (1.1) in the semi-algebraic (and more generally in the o-minimal context). Before stating our results we introduce a few necessary definitions.

Definition 2.1 ( $\mathcal{P}$ -formulas and semi-algebraic sets).

Let $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$ , $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]$ be a finite sets of polynomials. We will call a quantifier-free first-order formula (in the theory of the reals) with atoms $P=0,P>0,P<0,P\in\mathcal{P}$ to be a $\mathcal{P}$ -formula. Given any first-order formula $\Phi(X_{1},\ldots,X_{n})$ in the theory of the reals (possibly with quantifiers), we will denote by ${\mathcal{R}}(\Phi,\mathrm{R}^{n})$ the set of points of $\mathrm{R}^{n}$ satisfying $\Phi$ , and call ${\mathcal{R}}(\Phi,\mathrm{R}^{n})$ the realization of $\Phi$ . We will call the realization of a $\mathcal{P}$ -formula a $\mathcal{P}$ -semi-algebraic set. A $\mathcal{Q}$ -semi-algebraic function is a function whose graph is a $\mathcal{Q}$ -semi-algebraic set.

We denote by $\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ the subset of polynomials in $\mathrm{R}[X_{1},\ldots,X_{n}]$ with degrees $\leq d$ .

2.1. Semi-algebraic case

We prove the following theorem in the semi-algebraic setting which improves the currently the best known upper bound [45] in a significant way (see Section 4 below).

Theorem 1.

Let $d\geq 2$ , $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d},\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]_{\leq d}$ , $A\subset\mathrm{R}^{n}$ a closed and bounded $\mathcal{P}$ -semi-algebraic set, and $f,g:A\rightarrow\mathrm{R}$ continuous $\mathcal{Q}$ -semi-algebraic functions, satisfying $f^{-1}(0)\subset g^{-1}(0)$ .

Then there exist $c=c(A,f,g)\in\mathrm{R}$ and $N\leq(8d)^{2(n+7)}$ such that for all $x\in A$ ,

(2.1)

|g(x)|^{N}\leq c\cdot|f(x)|.

In other words,

(2.2)

\mathcal{L}(f,g\mid A)\leq(8d)^{2(n+7)}=d^{O(n)}.

In the special case where $\mathrm{R}=\mathbb{R}$ and

\mathcal{P}\subset\mathbb{Z}[X_{1},\ldots,X_{n}]_{\leq d},\mathcal{Q}\subset\mathbb{Z}[X_{1},\ldots,X_{n},Y]_{\leq d},

and the bit-sizes of the coefficients of the polynomials in $\mathcal{P},\mathcal{Q}$ are bounded by $\tau$ , there exists

(2.3)

c\leq\min\{2^{\tau d^{O(n^{2})}},2^{\tau d^{O(n\log d)}}\}

such that the inequality (2.1) holds with $N=(8d)^{2(n+7)}$ .

Remark 1 (Sharpness).

The inequality (2.2) is nearly tight. The following slight modification of examples given in [45, Page 2] or [20, Example 15] shows that right hand side of inequality (2.2) cannot be made smaller than $d^{n}$ . The constants ( $8$ in the base and $14$ in the exponent) in our bound can possibly be improved (for example by using a better estimation in the inequality (5.1) in Proposition 5.1 and using a slightly more accurate degree bound). However, this would lead to a much more unwieldy statement which we prefer to avoid. The coefficient $2$ of $n$ in the exponent however seems inherent to our method.

Example 1.

Let $A:=\{x\in\mathbb{R}^{n}\mid x_{1}^{2}+\cdots+x_{n}^{2}\leq 1\}$ be the compact semi-algebraic set and consider the semi-algebraic functions $f,g:A\to\mathbb{R}$ defined by

	$\displaystyle f$	$\displaystyle:=\|X_{2}-X_{1}^{d_{1}}\|+\cdots+\|X_{n}-X_{n-1}^{d_{n-1}}\|+\|X_{n}^{d_{n}}\|,$
	$\displaystyle g$	$\displaystyle:=\sqrt{X_{1}^{2}+\cdots+X_{n}^{2}}.$

It is easy to see that $f^{-1}(0)=g^{-1}(0)=\{0\}$ . Then for sufficiently small $|t|$ the vector $x(t):=(t,t^{d_{1}},\ldots,t^{d_{1}\cdots d_{n-1}})$ belongs to $A$ and we have

\displaystyle f(x(t))=|t|^{d_{1}\cdots d_{n}},\qquad g(x(t))=\sqrt{t^{2}+\cdots+t^{2d_{1}\cdots d_{n-1}}},

which implies $|g(x(t))|^{d_{1}\cdots d_{n}}\leq c\cdot|f(x(t))|$ for some positive constant $c$ . Letting $d_{1}=\cdots=d_{n}=d$ , then it follows that $\mathcal{L}(f,g\mid A)\geq d^{n}$ .

Remark 2 (Independence from the combinatorial parameter).

An important feature of the bound in Theorem 1 is that the right hand side of inequality (2.2) depends only on the maximum degree of the polynomials in $\mathcal{P}\cup\mathcal{Q}$ and is independent of the cardinalities of the sets $\mathcal{P},\mathcal{Q}$ . This is not the case for the previous best known general bound due to Solernó [45] which depended on the sum of the degrees of the polynomials appearing in the descriptions of $A$ , $f$ and $g$ and thus implicitly on the number of polynomials involved in these descriptions. This fact, that our bound is independent of the number of polynomials, plays an important role in the applications that we discuss later in the paper. For example, it is exploited crucially in the proof of Theorem 2 (see below). Also note that the feature of being independent of combinatorial parameters is also present in some prior work that we discuss in detail in Section 3.1. But these results (notably that of Kollár [21] and also [42]) come with certain important restrictions and/or with a worse bound. In contrast, our result is completely general and nearly optimal.

Remark 3 (Separation of combinatorial and algebraic parts).

Separating the roles of combinatorial and algebraic parameters has a long history in quantitative real algebraic geometry. We include (see Section 4 below) a discussion and several prior examples of such results. The Łojasiewicz inequality is clearly a foundational result in real algebraic geometry. Hence, asking for a similar distinction in quantitative bounds on the Łojasiewicz exponent is a very natural question. Finally, the underlying idea behind making this distinction allows us to formulate and prove a version of the Łojasiewicz inequality valid over polynomially bounded o-minimal structures (see Theorem 3) which is stronger than the one known before.

Remark 4.

It is not possible to obtain a uniform bound (i.e. a bound only in terms of $d$ , $n$ and possibly the combinatorial parameters) on the constant $c$ in Theorem 1.

As mentioned earlier Theorem 1 leads to improvements in several applications where Łojasiewicz inequality plays an important role. We discuss some of these applications in depth in Section 6, but mention an important one right away.

2.2. Application to error bounds

Study of error bounds (defined next) is a very important topic in optimization theory and computational optimization (see for example [43] and the references cited therein).

Definition 2.2 (Error bounds and residual function).

Let $M,E\subset\mathrm{R}^{n}$ . An error bound on $E$ with respect to $M$ is an inequality

(2.4)

\displaystyle\operatorname{dist}(x,M)^{\rho}\leq\kappa\cdot\psi(x),\qquad\forall x\in E,

where $\rho,\kappa>0$ , and $\psi:M\cup E\to\mathrm{R}_{\geq 0}$ is some function (called a residual function) such that $\psi(x)=0$ iff $x\in M$ .

The study of error bounds was motivated by the implementation of iterative numerical optimization algorithms and the proximity of solutions to the feasible or optimal set. Thus, from the optimization point of view, the set $M$ in (2.4) can be the feasible set (polyhedron, a slice of the positive semi-definite cone, a basic semi-algebraic set, etc.) or the optimal set of an optimization problem, see (6.4), $E$ is a set of interest (e.g., iterates of an iterative algorithm or central solutions [5]), and a residual function $\psi$ measures the amount of violation of the inequalities defining $M$ at a given solution of $E$ . See [43] for other applications of error bounds in optimization.

If $M$ and $\psi$ are semi-algebraic and $E$ is a closed and bounded semi-algebraic set, then (2.4) is a special case of (1.1), and by Theorem 1, the error bound (2.4) exists with an integer $\rho\geq 1$ .

We prove the following quantitative result.

Theorem 2.

Let $M$ be a basic closed semi-algebraic set defined by

(2.5)

\displaystyle M:=\{x\in\mathrm{R}^{n}\mid g_{i}(x)\leq 0,\ h_{j}(x)=0,\ i=1,\ldots,r,\ j=1,\ldots,s\},

where $g_{i},h_{j}\in\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ , and let $E$ be a closed and bounded $\mathcal{P}$ -semi-algebraic subset of $\mathrm{R}^{n}$ with $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ . Let $\psi:M\cup E\rightarrow\mathrm{R}_{\geq 0}$ be the semi-algebraic function defined by

(2.6)

\displaystyle\psi(x)=\sum_{j=1}^{s}|h_{j}(x)|+\sum_{i=1}^{r}\max\{g_{i}(x),0\}.

Then there exist a positive constant $\kappa$ and an integer $\rho\geq 1$ such that (2.4) holds, with $\rho=d^{O(n^{2})}$ .

Moreover, if $\dim M=0$ (i.e. $M$ is a finite subset of $\mathrm{R}^{n}$ ), then (2.4) holds with $\rho\leq(8d)^{2(n+7)}=d^{O(n)}$ .

Remark 5.

Example 1 indicates that the upper bound on $\rho$ cannot be better than $d^{n}$ .

Remark 6.

The error bounds of Theorem 2 have been stated, for the purpose of applications to optimization, only in reference to the basic semi-algebraic set (2.5) and the residual function (2.6). However, the results of Theorem 2 are still valid if we replace (2.5) by any $\mathcal{Q}$ -semi-algebraic set $M$ and (2.6) by any $\mathcal{Q}^{\prime}$ -semi-algebraic residual function, where $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ and $\mathcal{Q}^{\prime}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]_{\leq d^{O(n)}}$ , see Corollary 1.

Theorem 1 significantly improves the bound $D^{n^{c_{1}}}$ in [45, Theorem 7] in which $D$ is the sum of degrees of polynomials and $c_{1}$ is universal positive integer. Furthermore, the upper bound on $\rho$ in Theorem 2 is independent of $r$ and $s$ (the number of polynomial equations and inequalities in (2.5)), which is particularly important for optimization purposes. Thus, if $r,s=\omega(n^{2})$ , the first part of Theorem 2 improves the best current upper bound [30, Corollary 3.8], where

(2.7)

\displaystyle\rho\leq\min\big{\{}(d+1)(3d)^{n+r+s-1},d(6d-3)^{n+r-1}\big{\}}.

Furthermore, when $M$ is a finite subset of $\mathrm{R}^{n}$ and $r=\omega(n)$ , the second part of Theorem 2 improves the upper bound [30, Theorem 4.1], where

(2.8)

\displaystyle\rho\leq\frac{(2d-1)^{n+r}+1}{2}.

The improvements mentioned above are particularly relevant to non-linear semi-definite systems, non-linear semi-definite optimization, and semi-definite complementarity problems, see e.g., [28, 40], where the application of (2.7) and (2.8) would result in a doubly exponential bound since the number of inequalities needed to define the cone of positive semi-definite matrices in the vector space $\mathbb{S}^{n}$ of symmetric $n\times n$ matrices with entries in $\mathrm{R}$ is exponential in $n$ . The problem of estimation of the exponent $\rho$ in the error bounds of positive semi-definite systems failing the Slater condition [15, Page 23] is posed in [28, Page 106] where it is stated “Presently, we have no idea of what this exponent ought to be except in trivial cases”. Corollary 1 quantifies the error bound exponent in [28, Proposition 6] and gives an answer to this question in the special case of polynomial mappings.

Corollary 1.

Let $\mathbb{S}_{+}^{p}$ be the cone of symmetric $p\times p$ positive semidefinite matrices (with entries in $\mathrm{R}$ ), let $M$ be defined as

\displaystyle M:=\{X\in\mathbb{S}^{p}\mid\ g_{i}(X)\leq 0,\ i=1,\ldots,r\},

where $g_{i}:\mathbb{S}^{p}\to\mathrm{R}$ is a polynomial function of degree $d$ , and let $E$ be a closed and bounded $\mathcal{P}$ -semi-algebraic subset of $\mathrm{R}^{p^{2}}$ with $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{p^{2}}]_{\leq d}$ . Then there exist $\kappa\in\mathrm{R}$ and $\rho=\max\{d,p\}^{O(p^{4})}$ such that

\displaystyle\operatorname{dist}(x,M\cap\mathbb{S}_{+}^{p})^{\rho}\leq\kappa\cdot\max\Big{\{}\operatorname{dist}(x,M),\max\{-\lambda_{\min}(x),0\}\Big{\}},\quad\mbox{ for all }x\in E.

2.3. O-minimal case

Many finiteness results of semi-algebraic geometry generalize to arbitrary o-minimal expansions of $\mathbb{R}$ (we refer the reader to [47] and [13] for the definition of o-minimal structures and the corresponding finiteness results). Łojasiewicz inequality does not extend to arbitrary o-minimal expansions of $\mathbb{R}$ (for example, o-minimal expansions in which the exponential function is definable). However, Miller proved in [38, Theorem 5.4, page 94] that in a polynomially bounded o-minimal expansion of $\mathbb{R}$ , Łojasiewicz inequality holds for every compact definable set $A$ and definable functions $f,g:A\rightarrow\mathbb{R}$ with $f^{-1}(0)\subset g^{-1}(0)$ (using the same notation as in Theorem 1 above). (An o-minimal expansion of $\mathbb{R}$ is polynomially bounded if for every definable function $f:\mathbb{R}\rightarrow\mathbb{R}$ , there exist $N\in\mathbb{N},c\in\mathbb{R}$ , such that $|f(x)|<x^{N}$ for all $x>c$ .) However, it is not possible to give a meaningful quantitative version of Miller’s result in such a general context.

2.3.1. Extension of the notion of combinatorial complexity to arbitrary o-minimal structures

Although the notion of algebraic complexity in the context of general o-minimal structure does not make sense in general – one can still talk of combinatorial complexity [3]. The following result is illustrative (see also Proposition 5.4 for another example) and can be obtained by combining [3, Theorem 2.3] and the approximation theorem proved in [16].

Fix an o-minimal expansion of the $\mathbb{R}$ and suppose that $\mathcal{A}$ is a definable family of closed subsets of $\mathbb{R}^{n}$ . Then there exists a constant $C=C(\mathcal{A})>0$ having the following property. Suppose that $\mathcal{S}\subset\mathcal{A}$ is a finite subset and $S$ a subset of $\mathbb{R}^{n}$ belonging to the Boolean algebra of subsets of $\mathbb{R}^{n}$ generated by $\mathcal{S}$ such that

(2.9)

\sum_{i}b_{i}(S)\leq C\cdot s^{n},

where $s=\mathrm{card}(\mathcal{S})$ and $b_{i}(\cdot)$ denotes the $i$ -th Betti number [7]. Notice that this bound does depend on the combinatorial parameter $s$ . Note also that it follows from Hardt’s triviality theorem for o-minimal structures [13] that the Betti numbers of the sets appearing in any definable family are bounded by a constant (depending on the family). However, the family of sets $S$ to which the inequality (2.9) applies is not necessarily a definable family.

In view of the inequality (2.9) it is an interesting question whether one can prove a quantitative version of Miller’s result with a uniform bound on the Łojasiewicz exponent in the same setting as above – so that the bound applies to a family (not necessarily definable) of definable sets $S$ and functions $f,g$ simultaneously – as in inequality (2.9).

2.3.2. Łojasiewicz inequality in polynomially bounded o-minimal structures

For the rest of this section we fix a polynomially bounded o-minimal expansion of $\mathbb{R}$ . Before stating our theorem we need to use a notation and a definition.

Notation 1.

A definable family of subsets of $\mathbb{R}^{n}$ parametrized by a definable set $A$ , is a definable subset $\mathcal{A}\subset A\times\mathbb{R}^{n}$ . For $a\in A$ , we will denote by $\mathcal{A}_{a}=\pi_{2}(\pi_{1}^{-1}(a)\cap\mathcal{A})$ , where $\pi_{1}:A\times\mathbb{R}^{n}\rightarrow A$ , $\pi_{2}:A\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ are the two projection maps. We will often abuse notation and refer to the definable family by $\mathcal{A}$ .

Definition 2.3.

Given a definable family $\mathcal{A}$ of subsets of $\mathbb{R}^{n}$ parametrized by a definable set $A$ , and a finite subset $A^{\prime}\subset A$ , we call a subset $S\subset\mathbb{R}^{n}$ to be a $(\mathcal{A},A^{\prime})$ -set if it belongs to the Boolean algebra of subsets of $\mathbb{R}^{n}$ generated by the tuple $(\mathcal{A}_{a})_{a\in A^{\prime}}$ . We will call a subset $S\subset\mathbb{R}^{n}$ , a $\mathcal{A}$ -set if $S$ is a $(\mathcal{A},A^{\prime})$ -set for some finite set $A^{\prime}\subset A$ . If the graph of a definable function $f$ is a $\mathcal{A}$ -set we will call $f$ a $\mathcal{A}$ -function. (Note that the family of $\mathcal{A}$ -sets is in general not a definable family of subsets of $\mathbb{R}^{n}$ .)

Example 2.

If we take the o-minimal structure $\mathbb{R}_{\mathrm{sa}}$ of semi-algebraic sets, then for each fixed $d$ , the family of semi-algebraic sets which are $\mathcal{P}$ -semi-algebraic sets where $\mathcal{P}$ varies over all finite subsets of $\mathbb{R}[X_{1},\ldots,X_{n}]_{\leq d}$ is an example of a family of $\mathcal{A}$ -sets for an appropriately chosen $\mathcal{A}$ . Note that this family is not a semi-algebraic family.

Example 2 suggests a way to obtain a quantitative Łojasiewicz inequality valid over any polynomially bounded o-minimal structure.

Theorem 3 (Łojasiewicz inequality for $\mathcal{A}$ -sets and $\mathcal{B}$ -functions for any pair of definable families $\mathcal{A}$ and $\mathcal{B}$ ).

Let $\mathcal{A}$ be a definable family of subsets of $\mathbb{R}^{n}$ parametrized by the definable set $A$ , and let $\mathcal{B}$ be a definable family of subsets of $\mathbb{R}^{n+1}$ parametrized by the definable set $B$ .

Then there exists $N=N(\mathcal{A},\mathcal{B})>0$ having the following property. For any triple of finite sets $(A^{\prime},B^{\prime},B^{\prime\prime})$ with $A^{\prime}\subset A,B^{\prime},B^{\prime\prime}\subset B$ , there exists $c=c(A,B^{\prime},B^{\prime\prime})\in\mathbb{R}$ such that for each closed and bounded $(\mathcal{A},A^{\prime})$ -set $S$ , a $(\mathcal{B},B^{\prime})$ -set $F$ , and a $(\mathcal{B},B^{\prime\prime})$ -set $G$ , such that $F,G$ are graphs of definable functions $f,g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ continuous on $S$ with $f|_{S}^{-1}(0)\subset g|_{S}^{-1}(0)$ , and for all $x\in S$ ,

|g(x)|^{N}\leq c\cdot|f(x)|.

Remark 7 (Theorem 3 generalizes Theorem 5.4 (page 94) in [38]).

Notice that as in Theorem 1, the combinatorial parameter (namely, $\mathrm{card}(A^{\prime}\cup B^{\prime}\cup B^{\prime\prime})$ ) plays no role. It is also more general than the Łojasiewicz inequality in [38] as the inequality holds with the same value of $N$ for a large, potentially infinite family (not necessarily definable) of triples $(S,f,g)$ and not just for one triple as in the result in [38].

2.4. Outline of the proofs of the main theorems

We now outline the key ideas behind the proofs of the theorems stated in the previous section.

Our proof of Theorem 1 follows closely the proof of the similar qualitative statement in [10] with certain important modifications. One main tool that we use to obtain our quantitative bound is a careful analysis of the degrees of certain polynomials appearing in the output of an algorithm (Algorithm 14.6 (Block Elimination) described in the book [7]. ¹¹1We refer to the posted online version of the book because it contains certain degree estimates which are more precise than in the printed version. This algorithm is an intermediate algorithm for the effective quantifier elimination algorithm described in [7], and takes as input a finite set of polynomials $\mathcal{P}\subset\mathrm{R}[Y,X]$ , and produces as output a finite set $\mathrm{BElim}_{X}(\mathcal{P})\subset\mathrm{R}[Y]$ having the property that for each connected component $C$ of the realization of each realizable sign condition (see Notation 2) the set of sign conditions realized by $\mathcal{P}(y,X))$ is constant as $y$ varies over $C$ . The precise mathematical statement describing the above property of the output of the Block Elimination algorithm (including a bound on the degrees of the polynomials output) is summarized in Proposition 5.1. The proof of the bound on degrees borrows heavily from the complexity analysis of the algorithm that already appears in [7] but with an added part corresponding to the last step of the algorithm. This last step uses another algorithm (namely, Algorithm 11.54 (Restricted Elimination) in [7]) and we use the complexity analysis of this algorithm as well.

We also need a quantitative statement on the growth of a semi-algebraic function of one variable at infinity whose graph is defined by polynomials of a given degree. It is important for us that the growth is bounded only by the upper bound on the degree and not on the size of the formula describing the graph. This is proved in Lemma 5.1.

Note that the technique of utilizing complexity estimates of algorithms to prove quantitative bounds in real algebraic geometry is not altogether new. For example, similar ideas have been used to prove a quantitative curve selection lemma [9], and bounds on the radius of a ball guaranteed to intersect every connected component of a given semi-algebraic set [8], amongst other such results.

Theorem 2 is an application of Theorem 1 with one key extra ingredient. We prove (see Lemma 5.3) that if $M$ is a $\mathcal{P}$ -semi-algebraic set with $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ , then the graph of the distance function, ${\rm dist}(\cdot,M)$ , can be described by a quantifier-free formula involving polynomials having degrees at most $d^{O(n)}$ . A more naive approach (for example that in [45]) involving quantifier elimination would involve elimination of two blocks of quantified variables with a quantifier alternation and would lead to a degree bound of $d^{O(n^{2})}$ . The formula describing the graph of ${\rm dist}(\cdot,M)$ that we obtain is very large from the point of view of combinatorial complexity (compared to the more naive approach), but with a better degree bound. We leverage now the fact that our bound on the Łojasiewicz exponent is independent of the combinatorial parameter, and apply Theorem 1 to obtain the stated result.

The proof of Theorem 3 is similar to that of proof Theorem 1 with the following important difference. Proposition 5.1 which plays a key role in the proof of Theorem 1 is replaced by a quantitative version of the existence theorem for cylindrical definable decomposition adapted to finite sub-families of a family $\mathcal{F}$ of definable subsets of $\mathrm{R}^{n}$ in any o-minimal structure. The important quantitative property that we need is not the size of the decomposition but the fact that each cell of the decomposition is determined in a certain fixed definable way from a certain finite number, $N(n)$ , of the sets of the given finite sub-family of $\mathcal{F}$ (the key point being that the number $N(n)$ is independent of the cardinality of the finite sub-family). The existence of such decompositions in o-minimal structures was first observed in [3, Theorem 2.5] (see Proposition 5.5 below) and it is closely related (in fact equivalent) to the fact that o-minimal structures are distal in the sense of model theory (see [46]).

The rest of the paper is organized as follows. In Section 3 we survey prior work on proving bounds on the Łojasiewicz exponent at various levels of generality, and also survey prior work on proving error bounds. In Section 4, in order to put the current paper in context, we include a discussion of the role that the separation of combinatorial and algebraic complexity has played in quantitative real algebraic geometry. In Section 5 we prove the main theorems after introducing the necessary definitions and preliminary results. In Section 6, we discuss some further applications of our main theorem. Finally, in Section 7 we end with some open problems.

3. Prior and related work

3.1. Prior results on Łojasiewicz inequality

Solernó [45, Theorem 3] proved that (1.1) holds with $\rho=D^{c_{1}n}$ , in which $c_{1}$ is a universal constant and $D$ is an upper bound on the sum of the degrees of polynomials in $\mathcal{P}$ and $\mathcal{Q}$ . Since $D$ is an upper bound on the sum of the degrees of polynomials in $\mathcal{P}$ and $\mathcal{Q}$ , the bound in [45, Theorem 3] depends implicitly on the cardinalities of $\mathcal{P}$ and $\mathcal{Q}$ (unlike Theorem 1). In the case of polynomials with integer coefficients, Solernó [45, Theorem 3 (ii)] also proves an upper bound of $2^{\tau{D^{c_{2}\cdot n^{2}}}}$ on the constant $c$ (following the same notation as in (1.1)) where $D$ is an upper bound on the sum of the degrees of polynomials in $\mathcal{P}$ and $\mathcal{Q}$ and $c_{2}$ is a universal constant. This bound should be compared with inequality (2.3) in Theorem 1.

In a series of papers [22, 24, 25] Kurdyka, Spodzieja and Szlachcińska proved several quantitative results on Łojasiewicz inequality. We summarize them as follows. Let $S\subset\mathbb{R}^{n}$ be a closed semi-algebraic set, and let

\displaystyle S=S_{1}\cup\cdots\cup S_{k}

be a decomposition [10] of $S$ into $k$ closed basic $\mathcal{P}_{i}$ -semi-algebraic subsets $S_{i}$ with $\mathcal{P}_{i}\subset\mathbb{R}[X_{1},\ldots,X_{n}]_{\leq d_{i}}$ , each involving $r_{i}$ polynomial inequalities. Let $r(S)$ be the minimum of $\max\{r_{1},\ldots,r_{k}\}$ over all possible decompositions of $S$ and let $\deg(S)$ denote the minimum of $\max\{d_{1},\ldots,d_{k}\}$ over all decompositions for which $r_{i}\leq r(S)$ . Further, let $F:S\to\mathbb{R}^{s}$ be a continuous semi-algebraic mapping and suppose that $\mathbf{0}\in S$ and $F(\mathbf{0})=\mathbf{0}$ . Then for every $\varepsilon>0$ there exist [24, Corollary 2.2] (see also [25]) $c>0$ and an integer

(3.1)

\displaystyle 1\leq\rho\leq\bar{d}(6\bar{d}-3)^{n+s+\bar{r}-1}

such that

(3.2)

\displaystyle\|F(x)\|\geq c\cdot\operatorname{dist}\big{(}x,F^{-1}(\mathbf{0})\cap S\big{)}^{\rho},\quad\forall x\in S,\ \|x\|<\varepsilon,

where

	$\displaystyle\bar{d}$	$\displaystyle=\max\big{\{}\deg(S),\deg(\mathrm{graph}(F))\big{\}},$
	$\displaystyle\bar{r}$	$\displaystyle=r(S)+r(\mathrm{graph}(F)).$

If $x=\mathbf{0}$ is an isolated zero of $F$ , then $\rho\leq((2\bar{d}-1)^{n+s+\bar{r}}+1)/2$ .

Note that the above bounds do depend on the number of polynomials. Also, notice that $\bar{d}$ and $\bar{r}$ in the upper bound (3.1) are both different from $d$ and the number of inequalities in the semi-algebraic description of $f$ , $g$ , and $A$ in Theorem 1. In fact, $\bar{r}$ and $\bar{d}$ is the number of inequalities and the maximum degree of polynomials in the minimal semi-algebraic description of $\mathrm{graph}(F)$ and $S$ . It was proved in [12] that $\bar{r}$ is bounded by $n(n+1)/2$ , but it is not clear how $d$ blows up for a minimal decomposition. Because of this we cannot directly compare the bound in (3.1) to that of Theorem 1 proved in the current paper.

Let $f:S\to\mathbb{R}$ be a Nash function [10, Definition 2.9.3], where $S$ is a compact semi-algebraic subset of $\mathbb{R}^{n}$ . Osińska-Ulrych et al. [41] showed that

\displaystyle|f(x)|\geq c\cdot\operatorname{dist}\big{(}x,f^{-1}(0)\big{)}^{2(2\bar{d}-1)^{3n+1}},\quad\forall x\in S,

in which $\bar{d}=\deg_{S}(f):=\max\{\deg_{a}(f)\mid a\in S\}$ , and $\deg_{a}(f)$ is the degree of the unique irreducible $P\in\mathbb{R}[X_{1},\ldots,X_{n},Y]$ such that $P(x,f(x))=0$ for all $x$ in a connected neighborhood of $a$ .

Kollár [21] considered the problem of improving Solernó’s results [45]. He obtained significant improvements but under certain restrictions. More precisely, given a semi-algebraic set $M$ as in (2.5), with $\max_{i}\{f_{i}(x)\}>0$ for all $x\in M$ for $0<\|x\|\ll 1$ , and $\max_{i}\{f_{i}(\mathbf{0})\}=0$ , he proved that ([21, Theorem 4]) there exist constants $c,\varepsilon>0$ such that

(3.3)

\displaystyle\max_{i}\{f_{i}(x)\}\geq c\cdot\|x\|^{B(n-1)d^{n}}\ \ \text{for all}\ x\in M\ \text{with}\ \|x\|<\varepsilon,

where $B(n):=\binom{n}{\lfloor(n/2)\rfloor}$ . Notice that the bound $B(n-1)d^{n}\leq(2d)^{n}$ on the exponent in (3.3) is a little better than the bound in Theorem 1. It is also the case that similar to our result, Kollár’s bound is independent of the combinatorial parameters (i.e. number of polynomials occurring in the definition of $M$ and the number of $f_{i}$ ’s). However, unlike Theorem 1, the pair of functions $\max_{i}\{f_{i}(x)\},||\cdot||$ in Kollár’s theorem is quite restrictive and so inequality (3.3) is difficult to apply directly – for instance, in applications to error bounds considered in this paper (Theorem 2). Moreover, the restriction that $\mathbf{0}$ has to be an isolated zero of $\max_{i}\{f_{i}(x)\}$ may not be satisfied in many applications, restricting the utility of (3.3).

More recently, Osińska-Ulrych et al. [42] proved that $\mathcal{L}(f,g\mid\mathbb{B}^{n})\leq\bar{d}^{4n+1}$ in which $\bar{d}$ is the degree of polynomials describing $f$ and $g$ , $\mathbb{B}^{n}$ is the unit ball in $\mathbb{R}^{n}$ , and $\bar{d}$ is a bound on the degrees of polynomials defining the graphs of $f,g$ as well as on certain polynomials giving a suitable semi-algebraic decomposition of $\mathbb{B}^{n}$ adapted to $f,g$ . Note that $\bar{d}$ could be larger than the degrees of the polynomials defining $f,g$ . This bound is also independent of the combinatorial parameters but asymptotically weaker than the one in Theorem 1, and the setting is more restrictive (since the bound is not directly in terms of the degrees of the polynomials appearing in the definition of $f,g$ ).

3.2. Other forms of Łojasiewicz inequality

Several other forms of Łojasiewicz inequality have appeared in the literature. Let $f:U\to\mathbb{R}$ be a real analytic function, where $U\subset\mathbb{R}^{n}$ is neighborhood of $\mathbf{0}\in\mathbb{R}^{n}$ . If $f(\mathbf{0})=0$ and $\nabla f(\mathbf{0})=\mathbf{0}$ , then there exist a neighborhood $U^{\prime}$ of $0$ , a rational number $\varrho<1$ , and $c>0$ such that

(3.4)

|\nabla f(x)|\geq c\cdot|f(x)|^{\varrho},\quad\forall x\in U^{\prime},

which is known as Łojasiewicz gradient inequality. The infimum of $\varrho$ satisfying (3.4) is called the Łojasiewicz exponent of $f$ , and it is denoted by $\varrho(f)$ . If $f\in\mathbb{R}[X_{1},\ldots,X_{n}]_{\leq d}$ and has a isolated singularity at zero, then there exists an upper bound [17]

\displaystyle\varrho(f)\leq 1-\frac{1}{(d-1)^{n}+1}.

Under a weaker condition of having non-isolated singularity at the origin, D’Acunto and Kurdyka showed [14] that

(3.5)

\displaystyle\varrho(f)\leq 1-\frac{1}{\max\{d(3d-4)^{n-1},2d(3d-3)^{n-2}\}}.

A more general result is given by [41] for a Nash function $f:U\to\mathbb{R}$ , where $U$ is a connected neighborhood of $\mathbf{0}\in\mathbb{R}^{n}$ . If $f(\mathbf{0})=0$ and $\nabla f(\mathbf{0})=\mathbf{0}$ , then (3.4) holds with

\displaystyle\varrho(f)\leq 1-\frac{1}{2(2d-1)^{3n+1}},

where $d$ is the degree of the unique irreducible $P\in\mathbb{R}[X_{1},\ldots,X_{n},Y]$ such that $P(x,f(x))=0$ for all $x\in U$ . If, in addition to the latter condition, $\frac{\partial P}{\partial y}(x,f(x))\neq 0$ for all $x\in U$ , then there exists a stronger upper bound

\displaystyle\varrho(f)\leq 1-\frac{1}{\max\{2d(2d-1),d(3d-2)^{n}\}+1}.

3.3. Prior work on error bounds

Error bounds were generalized to analytic systems and basic semi-algebraic sets in [37, Theorem 2.2] and [35, Theorem 2.2] based on the analytic form of Łojasiewicz inequality and Hörmander’s results [19] but without explicit information about the exponent. Recently, an explicit upper bound with respect to $M$ , defined in (2.5), was given in [30] which depends exponentially on the dimension and the number of polynomial equations and inequalities, see (2.7). The upper bound (2.7) follows from the bound (3.5) and the generalized differentiation in variational analysis.

In case that $M$ is defined by a single convex polynomial inequality, i.e., $r=1$ , $s=0$ , then (2.4) holds with $\rho\leq(d-1)^{n}+1$ [29, Theorem 4.2]. Additionally, if there exists an $x\in M$ such that $g(x)<0$ , then $\rho=1$ with $E=\mathbb{R}^{n}$ [29, Theorem 4.1]. More generally, there exists [11, Corollary 3.4]

(3.6)

\displaystyle\rho\leq\min\Bigg{\{}\frac{(2d-1)^{n}+1}{2},\binom{n-1}{[(n-1)/2]}d^{n}\Bigg{\}}

such that the error bound (2.4) holds, where

\displaystyle\psi(x)=\max_{i\in\{1,\ldots,r\}}(\max\{g_{i}(x),0\}).

A complete survey of error bounds in optimization and their applications to algorithms and sensitivity analysis can be found in [28, 43].

4. Combinatorial and algebraic complexity

A key feature of the bound in Theorem 1 is that it is independent of the cardinality of $\mathcal{P}$ and $\mathcal{Q}$ and depends only on the bound on the maximum degree of the polynomials in $\mathcal{P}\cup\mathcal{Q}$ and $n$ . In fact in many quantitative results (upper bounds on various quantities) in real algebraic geometry involving a $\mathcal{P}$ -semi-algebraic set a fruitful distinction can be made between the dependence of the bound on the cardinality of the set $\mathcal{P}$ and on the maximum degrees (or some other measure of the complexity) of the polynomials in $\mathcal{P}$ . The former is referred to as the combinatorial part and the latter as the algebraic part of the bound (see [4]). This distinction is important in many applications (such as in discrete and computational geometry) where the algebraic part of the bounds are treated as bounded by a fixed constant and only the combinatorial part is considered interesting.

The following examples illustrate the different nature of the dependencies on the combinatorial and the algebraic parameters in quantitative bounds appearing in real algebraic geometry and put in context the key property of Theorem 1 stated in the beginning of this subsection.

1.

(Bound on Betti numbers.) Suppose that $S\subset\mathrm{R}^{n}$ is a $\mathcal{P}$ - semi-algebraic set and $V={\rm Z}(Q,\mathrm{R}^{n})$ a real algebraic set. Suppose that $\dim_{\mathrm{R}}V=p$ , and the degrees of $Q$ and the polynomials in $\mathcal{P}$ is bounded by $d$ . Then,

(4.1) $\sum_{i}b_{i}(S\cap V)\leq s^{p}(O(d))^{n},$

where $s=\mathrm{card}(\mathcal{P})$ and $b_{i}(\cdot)$ denotes the $i$ -th Betti number [7]. Notice the different dependence of the bound on $s$ and $d$ .
2.

(Quantitative curve selection lemma.) The curve selection lemma [33, 34] (see also [39]) is a fundamental result in semi-algebraic geometry. The following quantitative version of this lemma was proved in [9].

Theorem (Quantitative Curve Selection Lemma).

Let $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ be a finite set, $S$ a $\mathcal{P}$ -semi-algebraic set, and $x\in\overline{S}$ . Then, there exist $t_{0}\in\mathrm{R},t_{0}>0$ , a semi-algebraic path $\varphi:[0,t_{0})\rightarrow\mathrm{R}^{n}$ with

$\varphi(0)=x,\ \varphi((0,t_{0}))\subset S,$

such that the degree of the Zariski closure of the image of $\varphi$ is bounded by

$(O(d))^{4n+3}.$

Notice that the bound on the degree of the image of the curve $\varphi$ in the above theorem has no combinatorial part, i.e., there is no dependence on the cardinality of $\mathcal{P}$ (unlike the bound in (4.1)).

(Effective quantifier elimination) Quantifier elimination is a key property of the theory of the reals, and has been studied widely from the complexity view-point. The following quantitative version appears in [6].

Theorem 4 (Quantifier Elimination).

Let $\mathcal{P}\subset\mathrm{R}[X_{[1]},\ldots,X_{[\omega]},Y]_{\leq d}$ be a finite set of $s$ polynomials, where $X_{[i]}$ is a block of $k_{i}$ variables, and $Y$ a block of $\ell$ variables. Let

\Phi(Y)=(Q_{1}X_{[1]})\cdots(Q_{\omega}X_{[\omega]})\Psi(X_{[1]},\ldots,X_{[\omega]},Y)

be a quantified-formula, with $Q_{i}\in\{\exists,\forall\}$ and $\Psi$ a $\mathcal{P}$ -formula. Then there exists a quantifier-free formula

\Psi(Y)=\bigvee_{i=1}^{I}\bigwedge_{j=1}^{J_{i}}(\bigvee_{n=1}^{N_{ij}}\mbox{\bf sign}(P_{ijn}(Y))=\sigma_{ijn}),

where $P_{ijn}(Y)$ are polynomials in the variables $Y$ , $\sigma_{ijn}\in\{0,1,-1\}$ ,

$\displaystyle I$	$\displaystyle\leq$	$\displaystyle s^{(k_{\omega}+1)\cdots(k_{1}+1)(\ell+1)}d^{O(k_{\omega})\cdots O(k_{1})O(\ell)},$
$\displaystyle J_{i}$	$\displaystyle\leq$	$\displaystyle s^{(k_{\omega}+1)\cdots(k_{1}+1)}d^{O(k_{\omega})\cdots O(k_{1})},$
$\displaystyle N_{ij}$	$\displaystyle\leq$	$\displaystyle d^{O(k_{\omega})\cdots O(k_{1})},$

equivalent to $\Phi$ , and the degrees of the polynomials $P_{ijk}$ are bounded by $d^{O(k_{\omega})\cdots O(k_{1})}$ .

Moreover, if the polynomials in $\mathcal{P}$ have coefficients in $\mathbb{Z}$ with bit sizes bounded by $\tau$ , the polynomials $P_{ijk}$ also have integer coefficients with bit-sizes bounded by $\tau d^{O(k_{\omega})\cdots O(k_{1})}$ .

Notice that the bound on the degrees of the polynomials appearing in the quantifier-free formula is independent of the combinatorial parameter $s=\mathrm{card}(\mathcal{P})$ . This fact will play a key role in the proof of the main theorem (Theorem 1) below.

5. Proofs of the main results

5.1. Proof of Theorem 1

Before proving Theorem 1 we need some preliminary results.

5.1.1. Cylindrical definable decomposition

The notion of cylindrical definable decomposition (introduced by Łojasiewicz [33, 32]) plays a very important in semi-algebraic and more generally o-minimal geometry [13]. We include its definition below for the sake of completeness and also for fixing notation that will be needed later.

Definition 5.1 (Cylindrical definable decomposition).

Fixing the standard basis of $\mathrm{R}^{n}$ , we identify for each $i,1\leq i\leq n$ , $\mathrm{R}^{i}$ with the span of the first $i$ basis vectors. Fixing an o-minimal expansion of $\mathrm{R}$ , a cylindrical definable decomposition of $\mathrm{R}$ is an $1$ -tuple $(\mathcal{D}_{1})$ , where $\mathcal{D}_{1}$ is a finite set of subsets of $\mathrm{R}$ , each element being a point or an open interval, which together gives a partition of $\mathrm{R}$ . A cylindrical definable decomposition of $\mathrm{R}^{n}$ is an $n$ -tuple $(\mathcal{D}_{1},\ldots,\mathcal{D}_{n})$ , where each $\mathcal{D}_{i}$ is a decomposition of $\mathrm{R}^{i}$ , $(\mathcal{D}_{1},\ldots,\mathcal{D}_{n-1})$ is a cylindrical decomposition of $\mathrm{R}^{n-1}$ , and $\mathcal{D}_{n}$ is a finite set of definable subsets of $\mathrm{R}^{n}$ (called the cells of $\mathcal{D}_{n}$ ) giving a partition of $\mathrm{R}^{n}$ consisting of the following: for each $C\in\mathcal{D}_{n-1}$ , there is a finite set of definable continuous functions $f_{C,1},\ldots,f_{C,N_{C}}:C\rightarrow\mathrm{R}$ such that $f_{C_{1}}<\cdots<f_{C,N_{C}}$ , and each element of $\mathcal{D}_{n}$ is either the graph of a function $f_{C,i}$ or of the form

(a)

$\{(x,t)\;\mid\;x\in C,t<f_{C,1}(x)\}$ ,
(b)

$\{(x,t)\;\mid\;x\in C,f_{C,i}(x)<t<f_{C,i+1}(x)\}$ ,
(c)

$\{(x,t)\;\mid\;x\in C,f_{C,N_{C}}(x)<t\}$ ,
(d)

$\{(x,t)\;\mid\;x\in C\}$

(the last case arising is if the set of functions $\{f_{C,i}|1\leq i\leq N_{C}\}$ is empty).

We will say that the cylindrical definable decomposition $(\mathcal{D}_{1},\ldots,\mathcal{D}_{n})$ is adapted to a definable subset $S$ of $\mathrm{R}^{n}$ , if for each $C\in\mathcal{D}_{n}$ , $C\cap S$ is either equal to $C$ or empty.

In the semi-algebraic case we will refer to a cylindrical definable decomposition by cylindrical algebraic decomposition.

In the semi-algebraic case we will use the following extra notion.

5.1.2. Sign conditions

Notation 2 (Sign conditions and their realizations).

Let $\mathcal{P}$ be a finite subset of $\mathrm{R}[X_{1},\ldots,X_{n}]$ . For $\sigma\in\{0,1,-1\}^{\mathcal{P}}$ , we call the formula $\bigwedge_{P\in\mathcal{P}}(\mbox{\bf sign}(P)=\sigma(P))$ to be a sign condition on $\mathcal{P}$ and call its realization the realization of the sign condition $\sigma$ . We say that a sign condition is realizable if its realization is not empty.

We denote by $\mathrm{Cc}(\mathcal{P})$ the set of semi-algebraically connected components of the realizations of each realizable sign condition on $\mathcal{P}$ .

We say that a cylindrical algebraic decomposition $\mathcal{D}=(\mathcal{D}_{1},\ldots,\mathcal{D}_{n})$ of $\mathrm{R}^{n}$ is adapted to $\mathcal{P}$ if for each cell $C$ of $\mathcal{D}_{n}$ , and each $P\in\mathcal{P}$ , $\mbox{\bf sign}(P(x))$ is constant for $x\in C$ . (This implies in particular each element of $\mathrm{Cc}(\mathcal{P})$ is a union of cells of $\mathcal{D}_{n}$ .)

Lemma 5.1.

Let $\mathcal{F}\subset\mathrm{R}[X_{1},X_{2}]_{\leq p}$ be a finite set of non-zero polynomials. Let $f:\mathrm{R}\rightarrow\mathrm{R}$ be a semi-algebraic map, such that

\mathrm{graph}(f)=\{(x,f(x))\mid x\in\mathrm{R}\}=\bigcup_{C\in\mathcal{C}}C

for some subset $\mathcal{C}\subset\mathrm{Cc}(\mathcal{F})$ .

Then, there exist $a,c\in\mathrm{R}$ such that for all $x\geq a$ ,

|f(x)|\leq c\cdot x^{p}.

Proof.

Consider a cylindrical algebraic decomposition $\mathcal{D}=(\mathcal{D}_{1},\mathcal{D}_{2})$ of $\mathrm{R}^{2}$ (with coordinates $X_{1},X_{2}$ ) adapted to the set $\mathcal{F}$ .

This implies that each $C\in\mathrm{Cc}(\mathcal{F})$ is a union of cells of $\mathcal{D}_{2}$ . Let $a_{0}<a_{1}<\cdots<a_{n}=a$ be the end-points of the intervals giving the partition of $\mathrm{R}$ (corresponding to the $X_{1}$ coordinate) in the decomposition $\mathcal{D}_{1}$ .

Since the cylindrical decomposition $\mathcal{D}$ is adapted to $\mathcal{F}$ , and $\mathrm{graph}(f)=\bigcup_{C\in\mathcal{C}}C$ for some subset $\mathcal{C}\subset\mathrm{Cc}(\mathcal{F})$ , $\dim(C)\leq 1$ for each $C\in\mathcal{C}$ , since

\dim(C)\leq\dim(\mathrm{graph}(f))=1.

Hence, there exists for each $C\in\mathcal{C}$ a polynomial $F\in\mathcal{F}$ , such that $F(x)=0$ for all $x\in C$ .

Also, since $\mathrm{graph}(f)=\bigcup_{C\in\mathcal{C}}C$ and each $C\in\mathcal{C}$ is a union of cells of $\mathcal{D}$ , there exists a continuous semi-algebraic function $\gamma:(a,\infty)\rightarrow\mathrm{R}$ , such that $\mathrm{graph}(\gamma)\subset\mathrm{graph}(f)$ , and $\mathrm{graph}(\gamma)$ is a cell of $\mathcal{D}_{2}$ .

Let $C\in\mathrm{Cc}(\mathcal{C})$ be the unique element of $\mathcal{C}$ which contains $\mathrm{graph}(\gamma)$ , and $F\in\mathcal{F}$ such that $F(x)=0$ for all $x\in C$ .

The lemma now follows from [10, Proposition 2.6.1] noting that

\deg(F)\leq p.

∎

Notation 3 (Realizable sign conditions).

For any finite set of polynomials $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{k}]$ we denote by

\mathrm{SIGN}(\mathcal{P})\subset\{0,1,-1\}^{\mathcal{P}}

the set of all realizable sign conditions for $\mathcal{P}$ over $\mathrm{R}^{k}$ , i.e.

\mathrm{SIGN}(\mathcal{P})=\{\sigma\in\{0,1,-1\}^{\mathcal{P}}\;\mid\;{\mathcal{R}}(\sigma,\mathrm{R}^{n})\neq\emptyset\}.

Proposition 5.1.

Let $\mathcal{P}\subset\mathrm{R}[Y,X]$ , with $Y=(Y_{1},\ldots,Y_{\ell}),X=(X_{1},\ldots,X_{k})$ be a finite set of polynomials. Then there exists a finite subset $\mathrm{BElim}_{X}(\mathcal{P})\subset\mathrm{R}[Y]$ such that for each $C\in\mathrm{Cc}(\mathrm{BElim}_{X}(\mathcal{P}))$ , $\mathrm{SIGN}(\mathcal{P}(y,X)$ is fixed as $y$ varies over $C$ .

If the degrees of the polynomials in $\mathcal{P}$ are bounded by $d\geq 2$ , then the degrees of the polynomials in $\mathrm{BElim}_{X}(\mathcal{P})$ is bounded by

(5.1)

8d^{2}(2k(2d+2)+2)(2d+3)(2d+6)^{2}(2d+5)^{2k-2}<(8d)^{2k+4}.

Proof.

Let $\mathrm{BElim}_{X}(\mathcal{P})$ be the set of polynomials denoted by the same formula in the output of Algorithm 14.6 (Block Elimination) in [7]. The fact that for each $C\in\mathrm{Cc}(\mathrm{BElim}_{X}(\mathcal{P}))$ , $\mathrm{SIGN}(\mathcal{P}(y,X)$ is fixed as $y$ varies over $C$ is a consequence of Proposition 14.10 in [7].

To obtain the upper bound on the degrees of the polynomials in $\mathrm{BElim}_{X}(\mathcal{P})$ , we follow the complexity analysis of Algorithm 14.6 (Block Elimination) in [7] using the same notation as in the algorithm. The algorithm first computes a set $\mathrm{UR}_{X}(\mathcal{P})$ whose elements are tuples $v=(f,g_{0},\ldots,g_{k})$ of polynomials in $T,Y,{\varepsilon},\delta$ (here ${\varepsilon}$ and $\delta$ are infinitesimals and $T$ is one variable). It is proved in the complexity analysis of the algorithm that the degrees of the polynomials in $T$ appearing in the various tuples $v\in\mathrm{UR}_{X}(\mathcal{P})$ are bounded by

D=(2d+6)(2d+5)^{k-2},

and their degrees in $Y$ (as well as in ${\varepsilon},\delta$ ) are bounded by

D^{\prime}=(2k(2d+2)+2)(2d+3)(2d+6)(2d+5)^{k-2}.

It follows that for each $P\in\mathcal{P}$ , and $v=(f,g_{0},\ldots,g_{k})\in\mathrm{UR}_{X}(\mathcal{P})$ , the degree in $T$ of the polynomial

P_{v}=g_{0}^{e}P(\frac{g_{1}}{g_{0}},\ldots,\frac{g_{k}}{g_{0}}),

where $e$ is the least even integer greater than $\deg(P)\leq d$ , is bounded by $(d+1)D\leq 2dD$ , and similarly the degree in $Y$ of $P_{v}$ is bounded by $2dD^{\prime}$ . The same bounds apply to all polynomials in the set $\mathcal{F}_{v}$ introduced in the algorithm.

It now follows from the complexity analysis of Algorithm 11.54 (Restricted Elimination) in [7], that the degrees in $Y$ of the polynomials in $\mathrm{RElim}_{T}(f,\mathcal{F}_{v})$ are bounded by

$\displaystyle 2(2dD)(2dD^{\prime})$	$\displaystyle=$	$\displaystyle 8d^{2}DD^{\prime}$
	$\displaystyle=$	$\displaystyle 8d^{2}(2k(2d+2)+2)(2d+3)(2d+6)^{2}(2d+5)^{2k-2}$
	$\displaystyle\leq$	$\displaystyle(8d^{2})\cdot(6kd)\cdot(4d)\cdot(5d)^{2}\cdot(4d)^{2k-2}$
	$\displaystyle=$	$\displaystyle 8\cdot 6\cdot 4\cdot 5^{2}\cdot k\cdot d^{6}\cdot(4d)^{2k-2}$
	$\displaystyle=$	$\displaystyle\frac{3\cdot 5^{2}}{4^{3}}\cdot k\cdot(4d)^{2k+4}$
	$\displaystyle<$	$\displaystyle(8d)^{2k+4}.$

Denoting $\mathcal{B}_{v}\subset\mathrm{R}[Y]$ the set of coefficients of the various polynomials in $\mathrm{RElim}_{T}(f,\mathcal{F}_{v})$ written as polynomials in ${\varepsilon},\delta$ , we have immediately obtain that the degrees in $Y$ of polynomials in $\mathcal{B}_{v}$ are bounded by

8d^{2}(2k(2d+2)+2)(2d+3)(2d+6)^{2}(2d+5)^{2k-2}<(8d)^{2k+4}.

The proposition follows since according to the algorithm

\mathrm{BElim}_{X}(\mathcal{P})=\bigcup_{v\in\mathrm{UR}_{X}(\mathcal{P})}\mathcal{B}_{v}.

∎

Lemma 5.2.

Suppose that $\mathcal{P}\subset\mathrm{R}[Y,X]$ , with $Y=(Y_{1},\ldots,Y_{\ell}),X=(X_{1},\ldots,X_{k})$ and $\Phi$ is $\mathcal{P}$ -formula. Then there exist subsets $\mathcal{C}_{\exists},\mathcal{C}_{\forall}\subset\mathrm{Cc}(\mathrm{BElim}_{X}(\mathcal{P}))$ , such that

	$\displaystyle{\mathcal{R}}((\exists X)\Phi,\mathrm{R}^{\ell})$	$\displaystyle=$	$\displaystyle\bigcup_{C\in\mathcal{C}_{\exists}}C,$
(5.2)		$\displaystyle{\mathcal{R}}((\forall X)\Phi,\mathrm{R}^{\ell})$	$\displaystyle=$	$\displaystyle\bigcup_{C\in\mathcal{C}_{\forall}}C.$

Proof.

The lemma follows from the fact that for each $C\in\mathrm{Cc}(\mathrm{BElim}_{X}(\mathcal{P}))$ , the set $\mathrm{SIGN}(\mathcal{P}(y,X)$ is fixed as $y$ varies over $C$ (Proposition 5.1), and the observation that for each $y\in\mathrm{R}^{\ell}$ , the truth or falsity of each of the formulas $(\exists X)\Phi(y,X),(\forall X)\Phi(y,X)$ is determined by the set $\mathrm{SIGN}(\mathcal{P}(y,X)$ . ∎

The following proposition is the key ingredient in the proof of Theorem 1. It can be viewed as a quantitative version of Proposition 2.6.4 in [10] (which is not quantitative). Our proof is similar in spirit to the proof of Proposition 2.6.4 in [10] but differs at certain important points making it possible to achieve the quantitative bound claimed in the proposition.

Proposition 5.2.

Let $d\geq 2$ , $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ and

\mathcal{P}_{f},\mathcal{P}_{g}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]_{\leq d}

be finite sets of polynomials. Let $A\subset\mathrm{R}^{n}$ be a closed $\mathcal{P}$ -semi-algebraic set, $f:A\rightarrow\mathrm{R}$ a continuous semi-algebraic function whose graph is a $\mathcal{P}_{f}$ -semi-algebraic set, and $g:\{x\in A\;\mid\;f(x)\neq 0\}\rightarrow\mathrm{R}$ a continuous semi-algebraic function whose graph is a $\mathcal{P}_{g}$ -semi-algebraic set. Then there exists $N\leq(8d)^{2n+10}$ such that the function $f^{N}g$ extended by $0$ on $\{x\in A\;\mid\;f(x)=0\}$ is semi-algebraic and continuous on $A$ .

Proof.

Suppose that $A={\mathcal{R}}(\Phi,\mathrm{R}^{n})$ $\mathrm{graph}(f)={\mathcal{R}}(\Phi_{f},\mathrm{R}^{n+1})$ , and $\mathrm{graph}(g)={\mathcal{R}}(\Phi_{g},\mathrm{R}^{n+1})$ , where where $\Phi$ is a $\mathcal{P}$ -formula, $\Phi_{f}$ is a $\mathcal{P}_{f}$ -formula, and $\Phi_{g}$ is a $\mathcal{P}_{g}$ -formula.

For each $x\in A,u\in\mathrm{R}$ , we define

A_{x,u}=\{y\in A\;\mid\;||y-x||\leq 1,u|f(y)|=1\}.

We define $\Theta(X,U,Y,V)$ to be the quantifier-free formula

\halign{\hbox to\displaywidth{$\hfil\displaystyle#\hfil$}\cr 0.0pt{\hfil$\displaystyle\Phi(Y)\;\wedge\;(||Y-X||^{2}-1\leq 0)\cr 0.0pt{\hfil$\displaystyle\;\wedge\;\cr 0.0pt{\hfil$\displaystyle((V>0\;\wedge\;(UV-1=0))\;\vee\;((V<0)\;\wedge\;(UV+1=0)))\cr 0.0pt{\hfil$\displaystyle\;\wedge\;\cr 0.0pt{\hfil$\displaystyle\phi_{f}(Y,V).\crcr}}}}}}

Observe that for each $x\in A$ and $u\in\mathrm{R}$ ,

{\mathcal{R}}(\Theta(x,u,\cdot,\cdot),\mathrm{R}^{n+1})=\mathrm{graph}(f|_{A_{x,u}}).

The semi-algebraic set $A_{x,u}$ is closed and bounded, and we define the semi-algebraic function

v(x,u)=\begin{cases}0\mbox{ if }A_{x,u}=\emptyset,\\ \sup\{|g(y)|\;\mid\;y\in A_{x,u}\}\mbox{ otherwise}.\end{cases}

Let $\Lambda_{0}(X,U,W)$ denote the following the first-order (quantified) formula:

\forall(Y,V,Z)(W\geq 0)\;\wedge\;(\Theta(X,U,Y,V)\;\wedge\;\phi_{g}(Y,Z))\;\Longrightarrow\\ ((Z\geq 0)\;\wedge\;(W\geq Z))\;\vee\;((Z\leq 0)\;\wedge\;(W\geq-Z))).

Finally, let $\Lambda(X,U,W)$ denote the formula

(\forall W^{\prime})\;\Lambda_{0}(X,U,W^{\prime})\;\Longrightarrow\;(0\leq W\leq W^{\prime}).

Notice that for $\Lambda(x,u,w)$ is true if and only if $w=v(x,u)$ . Also notice that for each $x\in A$ , $\Lambda(x,U,W)$ is equivalent to a formula

\forall(Y,V,W^{\prime},Z)\;\Psi_{x}(Y,V,Z,U,W,W^{\prime})

to a $(n+5)$ -ary $\mathcal{P}_{x}$ -formula $\Psi_{x}$ , for some finite set $\mathcal{P}_{x}\subset\mathrm{R}[Y,V,Z,U,W,W^{\prime}]_{\leq\max(d,2)}$ (since we assume $d\geq 2$ ).

Let

\mathcal{Q}_{x}=\mathrm{BElim}_{Y,V,W^{\prime},Z}(\mathcal{P}_{x})\subset\mathrm{R}[U,W]

(see Proposition 5.1).

Then, using the degree bound in Proposition 5.1 we have that for each $Q\in\mathcal{Q}_{x}$ , $\deg(Q)<(8d)^{2(n+3)+4}=(8d)^{2n+10}$ .

It now follows from Lemma 5.1 that there exists $c=c(x)$ , such that for all $u\geq c(x)$ ,

|v(x,u)|\leq c\cdot u^{p},

with $p<(8d)^{2n+10}$ .

This means that

|f(y)|^{p}|g(y)|\leq c(x)

on $\{y\in A\;\mid\;f(y)\neq 0\ \mbox{ and }\ ||y-x||\leq 1\}$ for $|f(y)|$ sufficiently small. The function $f^{N}g$ extended by $0$ is then semi-algebraic and continuous at $x$ , where $N=p+1\leq(8d)^{2n+10}$ . This completes the proof. ∎

Theorem 5.

Let $d\geq 2$ , and

\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d},\mathcal{P}_{f},\mathcal{P}_{g}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y]_{\leq d}.

Let $A\subset\mathrm{R}^{n}$ be a closed $\mathcal{P}$ -semi-algebraic set, $f,g:A\rightarrow\mathrm{R}$ be continuous semi-algebraic functions whose graphs are $\mathcal{P}_{f}$ -semi-algebraic respectively $\mathcal{P}_{g}$ -semi-algebraic set, and such that $f^{-1}(0)\subset g^{-1}(0)$ . Then there exist $N=(8d)^{2(n+7)}$ and a continuous semi-algebraic function $h:A\rightarrow\mathrm{R}$ such that $g^{N}=hf$ on $A$ .

Proof.

Let $\widetilde{A}=\{(x,f(x),g(x))|x\in A\}\subset\mathrm{R}^{n+2}$ . The function $1/f$ is continuous semi-algebraic on $\{(x,u,v)\in\widetilde{A}\;\mid\;g(x)\neq 0\}$ , and its graph is defined by the formula

\Phi_{g}(X,V)\wedge(V\neq 0)\wedge\Phi_{f}(X,U)\wedge(UW-1=0)

Moreover using Proposition 5.2 there exists $N\leq(8d)^{2(n+2)+10}=(8d)^{2(n+7)}$ such that the function $\widetilde{h}:\widetilde{A}\rightarrow\mathrm{R}$ defined by

\widetilde{h}(x,u,v)=\begin{cases}0\mbox{ if }f(x)=0,\\ g^{N}(x)/f(x)\mbox{ if }f(x)\neq 0.\end{cases}

Since $\widetilde{h}$ does not depend on $u,v$ , we get a continuous and semi-algebraic function $h(x)=\widetilde{h}(x,f(x),g(x))$ on $A$ , and $g^{N}=hf$ . ∎

Proof of Theorem 1.

In order to prove inequality (2.2), use Theorem 5 with $c=\sup_{x\in A}|h(x)|$ , noticing that $c$ exists since $A$ is assumed to be closed and bounded.

We now prove inequality (2.3). The set of $c\subset\mathbb{R},c>0$ for which inequality (2.1) holds for all $x\in A$ is defined by

\Theta(C):=(C>0)\wedge\left(\forall X,U,V)\left(\phi(X)\wedge\phi_{f}(X,U)\wedge\phi_{g}(X,V)\right)\Longrightarrow(V^{2N}\leq C^{2}\cdot U^{2})\right),

where $\phi$ is a $\mathcal{P}$ -formula describing $A$ , and $\phi_{f},\phi_{g}$ are $\mathcal{Q}$ -formulas describing the graphs of $f$ and $g$ and $N=(8d)^{2(n+7)}$ .

Using Theorem 4 we obtain that $\Theta(C)$ is equivalent to a quantifier-free formula $\widetilde{\Theta}(C)$ such that the bit sizes of the coefficients of the polynomials appearing in $\widetilde{\Theta}(C)$ is bounded by $\tau d^{O(n^{2})}$ and their degrees are bounded by $d^{O(n^{2})}$ . Now using Cauchy’s bound ([7, Lemma 10.2]), the largest real root amongst the real roots of the polynomials appearing in $\widetilde{\Theta}(C)$ is bounded by $2^{\tau d^{O(n^{2})}}$ . It follows that there exists $c=2^{\tau d^{O(n^{2})}}$ for which the inequality (2.1) holds.

Using the repeated squaring technique (see below) at the cost of introducing $O(n\log d)$ new variables, it is possible write another universally quantified formula, namely

\Theta^{\prime}(C):=(C>0)\wedge(\forall T_{1},\ldots,T_{M},,X,U,V)(\phi(X)\wedge\phi_{f}(X,U)\wedge\phi_{g}(X,V)\wedge\cr(T_{1}=V)\wedge(T_{2}=T_{1}^{2})\wedge\cdots\wedge(T_{M}=T_{M-1}^{2}))\Longrightarrow(T_{M}^{2}\leq C^{2}\cdot U^{2})),

equivalent to $\Theta(C)$ in which all the polynomials appearing have degrees bounded by $d$ (instead of $d^{O(n)}$ as in the formula $\Theta$ ). The number of quantifier variables in the formula $\Theta^{\prime}$ equals $M+n+2$ , where $M=O(\log N)=O(n\log d)$ .

Now using Theorem 4 and Cauchy’s bound as before we obtain a bound of $2^{\tau d^{O(n\log d)}}$ on $c$ . ∎

5.2. Proof of Theorem 2

First, we need the following lemma.

Lemma 5.3.

Let $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ and $S\subset\mathrm{R}^{n}$ a $\mathcal{P}$ -semi-algebraic set. Then there exists $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},U]$ such that the graph of the function $\operatorname{dist}(\cdot,S):\mathrm{R}^{n}\rightarrow\mathrm{R}$ is a $\mathcal{Q}$ -semi-algebraic set and $\max_{Q\in\mathcal{Q}}\deg(Q)=d^{O(n)}$ .

Before proving Lemma 5.3 we need a new notion (that of Thom encoding of real roots of a polynomial) that will be needed in the proof. The following proposition appears in [7, Proposition 2.36].

Proposition 5.3 (Thom’s Lemma).

[7, Proposition 2.36] Let $P\subset\mathrm{R}[X]$ be a univariate polynomial, ${\rm Der}(P)$ the set of derivatives of $P$ and $\sigma\in\{-1,0,1\}^{{\rm Der}(P)}$ . Then ${\mathcal{R}}(\sigma,\mathrm{R})$ is either empty, a point, or an open interval.

Note that it follows immediately from Proposition 5.3, that for any $P\in\mathrm{R}[X]$ and $x\in\mathrm{R}$ such that $P(x)=0$ , the sign condition $\sigma$ realized by ${\rm Der}(P)$ at $x$ characterizes the root $x$ . We call $\sigma$ the Thom encoding of the root $x$ of $P$ .

Proof of Lemma 5.3.

Let $\Phi$ be a $\mathcal{P}$ -formula such that ${\mathcal{R}}(\Phi,\mathrm{R}^{n})=S$ . Let

W=\{(x,t)\;\mid\;\exists y\in S\mbox{ with }t=||x-y||\}.

Then for each $x\in\mathrm{R}^{n}$ ,

\operatorname{dist}(x,S)=\inf W_{x},

where $W_{x}$ denotes the one-dimensional fiber of $W$ over $x$ with respect to the projection along the $t$ coordinate.

It is also clear from the definition that $W$ is the image under projection along the $y$ coordinates) of the semi-algebraic set $V\subset\mathrm{R}^{n}\times\mathrm{R}^{n}\times\mathrm{R}$ defined by

V=\{(x,y,t)\;\mid\;y\in S\mbox{ and }t=||x-y||\}.

Let $\Theta(X,Y,T)$ be the formula

\Phi(Y)\wedge(T^{2}=||X-Y||^{2})\wedge(T\geq 0).

Then, it is clear that $\Theta$ is a $\mathcal{P}^{\prime}$ -formula for some finite subset $\mathcal{P}^{\prime}\subset\mathrm{R}[X,Y,T]_{\leq d}$ (assuming $d\geq 2$ ), and moreover ${\mathcal{R}}(\Theta,\mathrm{R}^{2n+1})=V$ .

Now apply Theorem 4 to the quantified formula $(\exists Y)\Theta(X,Y,T)$ and obtain a quantifier-free $\mathcal{F}$ -formula, $\widetilde{\Theta}$ equivalent to $\Theta$ , where $\mathcal{F}$ is some finite subset of $\mathrm{R}[X,T]$ and

D=\max_{F\in\mathcal{F}}\deg(F)=d^{O(n)}.

Notice that ${\mathcal{R}}(\widetilde{\Theta},\mathrm{R}^{n+1})=W$ , and for each $x\in\mathrm{R}^{n}$ ,

\inf W_{x}=\operatorname{dist}(x,S)

is a real root of some polynomial in $\mathcal{F}$ .

Let $\mathcal{F}=\{F_{1},\ldots,F_{N}\}$ . We denote

{\rm Der}_{T}(F_{i})=\{F_{i},F_{i}^{\prime},\ldots,F_{i}^{(D)}\}

the set of derivatives of $F_{i}$ with respect to $T$ .

For $1\leq i\leq N$ , and $\sigma\in\{-1,0,1\}^{{\rm Der}_{T}(F_{i})}$ , denote by $\Psi_{i,\sigma}$ the quantifier-free formula,

(\forall T)\left(\bigwedge_{0\leq j\leq D}(\mbox{\bf sign}(F_{i}^{(j)})=\sigma(F_{i}^{(j)}))\right)\Longrightarrow\left((\forall T^{\prime})\widetilde{\Theta}(X,T^{\prime})\Longrightarrow(T\leq T^{\prime})\right).

Using Theorem 4 one more time, let $\widetilde{\Psi}_{i,\sigma}$ be a quantifier-free formula equivalent to $\Psi_{i,\sigma}$ and let the set of polynomials appearing in $\widetilde{\Psi}_{i,\sigma}$ be denoted by $\mathcal{Q}_{i,\sigma}$ .

The semi-algebraic set ${\mathcal{R}}(\widetilde{\Psi}_{i,\sigma},\mathrm{R}^{n})$ is the set consisting of points $x\in\mathrm{R}^{n}$ , such that the $\operatorname{dist}(x,S)$ equals the (at most one) real root of the polynomial $F_{i}(x,T)$ with Thom encoding $\sigma$ . Notice that the maximum degree of polynomials in $\mathcal{Q}_{i,\sigma}$ is bounded by $D^{O(1)}=d^{O(n)}$ .

Finally, let

\Psi=\bigwedge_{i,\sigma}\left(\widetilde{\Psi}_{i,\sigma}\Longrightarrow\left(\bigwedge_{0\leq j\leq D}(\mbox{\bf sign}(F_{i}^{(j)})=\sigma(F_{i}^{(j)}))\right)\right),

and

\mathcal{Q}=\bigcup_{1\leq i\leq N}\left({\rm Der}_{T}(F_{i})\cup\bigcup_{\sigma\in\{-1,0,1\}^{{\rm Der}_{T}(F_{i})}}\mathcal{Q}_{i,\sigma}\right).

It is clear from the above construction that, $\Psi$ is a $\mathcal{Q}$ -formula, and ${\mathcal{R}}(\Psi,\mathrm{R}^{n+1})$ is the graph of the function $\operatorname{dist}(\cdot,S)$ , and the degrees of the polynomials in $\mathcal{Q}$ are bounded by $d^{O(n)}$ . This proves the lemma. ∎

Remark 8.

In [10, Proposition 2.2.8] and [45, Theorem 7], the graph of the semi-algebraic function $\operatorname{dist}(x,\mathcal{M})$ is described by the following quantified formula with two blocks of quantifiers

(5.3)

(\exists Y)\ (\forall Y^{\prime})\ \ (\neg\Psi(Y^{\prime})\vee(\Psi(Y)\wedge(||X-Y||^{2}=T^{2})\wedge(T\geq 0)\wedge(||X-Y^{\prime}||^{2}\geq T^{2})),

where $(\exists Y)$ and $(\forall Y^{\prime})$ are two blocks of variables each of size $n$ with different quantifiers. The effective quantifier elimination (Theorem 4) applied to (5.3) yields a quantifier-free formula with polynomials having degrees bounded by $d^{O(n^{2})}$ , where $d$ is an upper bound on the degrees of the polynomials in $\Psi$ . The formula given in Lemma 5.3 describing the graph of the same function involves polynomials of degrees at most $d^{O(n)}$ (though it may involve many more polynomials than the one in (5.3)) which is an improvement over the bound of $d^{O(n^{2})}$ obtained by the above argument. Note that for our purposes, the degrees of the polynomials appearing in the formula is the important quantity – the number of polynomials appearing is not relevant.

Proof of Theorem 2.

It is easy to see that the residual function $\psi(x)$ defined in (2.6) satisfies

\displaystyle\operatorname{dist}(x,M)=0\ \ \Longleftrightarrow\ \ \psi(x)=\sum_{j=1}^{s}|h_{j}(x)|+\sum_{i=1}^{r}\max\{g_{i}(x),0\}=0.

The graph of $\psi(x)$ can be described using a quantifier-free $\mathcal{P}$ -formula with $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ as follows (note that we do not care about the cardinality of $\mathcal{P}$ ).

To see this first observe that for all $x\in\mathrm{R}^{n}$ , and $\sigma\in\{0,1,-1\}^{[1,s]}$ if $\mbox{\bf sign}(h_{j}(x))=\sigma(j),j\in[1,s]$ , then

\sum_{j=1}^{s}|h_{j}(x)|=\sum_{j=1}^{s}\sigma(j)h_{j}(x).

Similarly, for all $x\in\mathrm{R}^{n}$ , and $\tau\in\{0,1,-1\}^{[1,r]}$ if $\mbox{\bf sign}(g_{i}(x))=\tau(i),i\in[1,r]$ , then

\sum_{i=1}^{r}\max\{g_{i}(x),0\}=\frac{1}{2}\sum_{i=1}^{r}\tau(i)(1+\tau(i))g_{i}(x).

It is now easy to verify that the following quantifier-free formula in $n+1$ variables:

(5.4)

\bigvee_{\begin{subarray}{c}\sigma\in\{0,1,-1\}^{[1,s]}\\ \tau\in\{0,1,-1\}^{[1,r]}\end{subarray}}\left(\bigwedge_{j=1}^{s}(\mbox{\bf sign}(h_{j})=\sigma(j))\wedge\bigwedge_{i=1}^{r}(\mbox{\bf sign}(g_{i})=\tau(i))\right)\Longrightarrow\\ \left(T-\sum_{j=1}^{s}\sigma(j)h_{j}-\frac{1}{2}\sum_{i=1}^{r}\tau(i)(1+\tau(i))g_{i}=0\right)

describes the graph of $\psi$ and all polynomials occurring in it have degrees at most $d$ .

Moreover, it follows from Lemma 5.3 that the graph of $\operatorname{dist}(\cdot,M)$ can be defined by a quantifier-free formula involving polynomials in $n+1$ variables having degrees bounded by $d^{O(n)}$ . The first part of the theorem now follows from Theorem 1 after setting $f(x)=\psi(x)$ , and $g(x)=\operatorname{dist}(x,M)$ .

In case that the $M$ is finite, it is possible to derive a sharper estimate of the error bound exponent. Suppose $M=\{p_{1},\ldots,p_{N}\}\subset\mathrm{R}^{n}$ . In this case the graph of the distance function, $\operatorname{dist}(X,M)$ , is described by the following formula

\Theta(X,T):=(T\geq 0)\wedge\left(\bigwedge_{i=1}^{N}(T^{2}\geq||X-p_{i}||^{2})\right)\wedge\left(\bigvee_{i=1}^{N}(T^{2}=||X-p_{i}||^{2})\right).

Notice that the degrees of the polynomials appearing in the quantifier-free formula $\Theta$ are bounded by $2$ . Furthermore, the graph of the residual function $\psi$ is defined by quantifier-free formula involving polynomials of degrees bounded by $d$ . The second part of the theorem is now immediate from Theorem 1. ∎

Remark 9.

A weaker version of Theorem 2 can be directly obtained using the quantifier elimination. Let us define

\displaystyle M_{\varepsilon}:=\{x\in\mathrm{R}^{n}\mid\psi(x)=\varepsilon,\ x\in E\}.

Then it suffices to describe the graph of the semi-algebraic function

\displaystyle\varphi:\varepsilon\mapsto\sup_{x\in M_{\varepsilon}}\operatorname{dist}(x,M).

Let $\Phi(X,\varepsilon)$ be a quantifier-free formula describing $M_{\varepsilon}$ and $\Psi(X,T)$ be the quantifier-free formula describing the graph of $\operatorname{dist}(x,M)$ in the proof of Lemma 5.3. Then the graph of $\varphi$ is the lower envelope of the realization of the formula (5.5):

(5.5)

\displaystyle(\forall X)\ (\exists T)\quad\neg(\Phi(X,\varepsilon)\wedge\Psi(X,T))\vee(\varphi\geq T).

By Lemma 5.3 and the application of Theorem 4 to (5.5), the graph of $\varphi$ can be described by a quantifier-free $\mathcal{P}$ -formula with $\mathcal{P}\subset\mathrm{R}[\varphi,\varepsilon]_{\leq d^{O(n^{2})}}$ , which implies the existence of $P\in\mathcal{P}$ such that $P(\varphi,\varepsilon)=0$ for sufficiently small positive $\varepsilon$ . By the Newton-Puiseux theorem [48, Theorems 3.2 and 4.1 of Chapter IV], $\psi$ near $\varepsilon=0$ can be expanded as

\displaystyle\varphi(\varepsilon)=a_{1}\varepsilon^{\gamma_{1}}+a_{2}\varepsilon^{\gamma_{2}}+\ldots

where $0<\gamma_{1}<\gamma_{2}<\ldots$ , and $a_{i}\in\mathrm{R}$ . Furthermore, it follows from the Newton-Puiseux algorithm [48, Section 3.2 of Chapter IV] that $\gamma_{1}\leq 1/\deg(P)$ , where $\deg(P)=d^{O(n^{2})}$ . All this implies $\varphi^{\deg(P)}=O(\varepsilon)$ for sufficiently small positive $\varepsilon$ , and thus

\displaystyle\operatorname{dist}(x,M)^{\deg(P)}\leq\kappa\cdot\psi(x),\quad\mbox{for all }x\in E\mbox{ with sufficiently small }\psi(x).

The case with $\dim M=0$ is analogous.

Proof of Corollary 1.

Notice that $M\cap\mathbb{S}^{p}_{+}$ can be redefined as a basic $\mathcal{Q}$ -semi-algebraic set with $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{p^{2}}]_{\leq\max\{d,p\}}$ and $|\mathcal{Q}|=2^{p}+r-1$ as follows:

\displaystyle\big{\{}X\in\mathbb{S}^{p}\mid g_{i}(X)\leq 0,\ i=1,\ldots,r,\ \det(X_{I})\geq 0,\ \forall I\subseteq\{1,\ldots,p\}\big{\}},

where $X_{I}$ is a principal submatrix of $X$ indexed by $I$ . We also define the residual function

\displaystyle\psi(x):=\max\Big{\{}\operatorname{dist}(x,M),\max_{I\subseteq\{1,\ldots,p\}}\big{(}\max\{-\det(X_{I}),0\}\big{)}\Big{\}},

which is a $\mathcal{Q}^{\prime}$ -semi-algebraic function with $\mathcal{Q}^{\prime}\subset\mathrm{R}[X_{1},\ldots,X_{p^{2}},Y]_{\leq d^{O(p^{2})}}$ , see Lemma 5.3 and the proof of Theorem 2. Then by applying Theorem 2, Lemma 5.3, and Remark 6 to $M\cap\mathbb{S}^{p}_{+}$ , $E$ , and $\psi(x)$ we get

\operatorname{dist}(x,M\cap\mathbb{S}_{+}^{p})^{\rho}\leq\kappa^{\prime}\cdot\max\Big{\{}\operatorname{dist}(x,M),\max_{I\subseteq\{1,\ldots,p\}}\big{(}\max\{-\det(X_{I}),0\}\big{)}\Big{\}},\\ \mbox{ for all }x\in E,

for some $\kappa^{\prime}>0$ and $\rho=\max\{d,p\}^{O(p^{4})}$ . The rest of the proof follows from the arguments in [28]. Let $\lambda_{i}(X_{I})$ be the $i$ th smallest eigenvalue of $X_{I}$ . By the boundedness of $E$ , there exists some positive $r$ such that $|\lambda_{i}(X_{I})|\leq r$ for all $i=1,\ldots,|I|$ . Furthermore, by the interlacing property of eigenvalues of $X$ , we have

\displaystyle\lambda_{\min}(X_{I}):=\lambda_{1}(X_{I})\geq\lambda_{\min}(X),

which yields

\displaystyle\det(X_{I})=\prod_{i=1}^{|I|}\lambda_{i}(X_{I})\geq r^{|I|-1}\lambda_{\min}(X_{I})\geq r^{|I|-1}\lambda_{\min}(X).

Consequently,

\displaystyle\max\{-\det(X_{I}),0\}\leq r^{|I|-1}\cdot\max\{-\lambda_{\min}(X),0\}

for every $I\subseteq\{1,\ldots,p\}$ , which completes the proof. ∎

5.3. Proof of Theorem 3

In the proof of Theorem 3 we need the following ingredient which is proved in [3, Theorem 2.5].

Proposition 5.4 (Quantitative cylindrical definable cell decomposition).

Fix an o-minimal expansion of the real closed field $\mathrm{R}$ . Let $\mathcal{A}$ be a definable family of subsets of $\mathrm{R}^{n}$ parametrized by the definable set $A$ . Then there exist a finite set $J$ and definable families $(\mathcal{C}_{j})_{j\in J}$ of subsets of $\mathrm{R}^{n}$ each parametrized by $A^{N(n)}$ where $N(n)=2(2^{n}-1)$ having the following property. Suppose, $A^{\prime}\subset A$ is a finite subset. Then, there exists a cylindrical decomposition $\mathcal{D}=(\mathcal{D}_{1},\ldots,\mathcal{D}_{n})$ of $\mathrm{R}^{n}$ , such that for each $i,1\leq i\leq n$ , the set of cells of the cylindrical decomposition $(\mathcal{D}_{1},\ldots,\mathcal{D}_{i})$ of $\mathrm{R}^{i}$ is a subset of the set of definable sets

\{(\mathcal{C}_{j})_{\overline{a}}\;\mid\;\overline{a}\in A^{\prime N(n)}\}.

For the rest of this section we fix a polynomially bounded o-minimal expansion of $\mathbb{R}$ .

Proposition 5.5 (o-minimal quantitative version of Proposition 2.6.4 in [10]).

Let $\mathcal{A}$ be a definable family of subsets of $\mathbb{R}^{n}$ parametrized by the definable set $A$ , and let $\mathcal{B}$ be a definable subset of $\mathbb{R}^{n+1}$ parametrized by the definable set $B$ .

Then there exists $N=N(\mathcal{A},\mathcal{B})>0$ having the following property. For any triple of finite sets $(A^{\prime},B^{\prime},B^{\prime\prime})$ with $A^{\prime}\subset A,B^{\prime},B^{\prime\prime}\subset B$ , a closed $(\mathcal{A},A^{\prime})$ -set $S$ , a $(\mathcal{B},B^{\prime})$ -set $F$ , $(\mathcal{B},B^{\prime\prime})$ -set $G$ , such that $F,G$ are graphs of definable functions $f:\mathbb{R}^{n}\rightarrow\mathbb{R},g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , such that $f|_{S}$ and $g|_{S_{f\neq 0}}$ (where $S_{f\neq 0}=\{x\in S\;\mid\;f(x)\neq 0\}$ ) are continuous, the function $f^{N}g|_{S_{f\neq 0}}$ extended by $0$ on $\{x\in S\;\mid\;f(x)=0\}$ is continuous on $S$ .

Proof.

We follow closely the proof of the corresponding proposition (Proposition 5.2) in the semi-algebraic case.

For each $x\in S,u\in\mathbb{R}$ , we define

S_{x,u}=\{y\in S\;\mid\;||y-x||\leq 1,u|f(y)|=1\}.

The set $S_{x,u}$ is definable, closed and bounded, and we define the function

v(x,u)=\begin{cases}0\mbox{ if }A_{x,u}=\emptyset,\\ \sup\{|g(y)|\;\mid\;y\in A_{x,u}\}\mbox{ otherwise}.\end{cases}

Clearly, $v:S\times\mathbb{R}\rightarrow\mathbb{R}$ is a definable function.

We define

\halign{\hbox to\displaywidth{$\hfil\displaystyle#\hfil$}\cr 0.0pt{\hfil$\displaystyle T=\{(x,u,y,v)\mid y\in S\wedge(||y-x||^{2}-1\leq 0)\cr 0.0pt{\hfil$\displaystyle\;\wedge\;\cr 0.0pt{\hfil$\displaystyle((v>0\;\wedge\;(uv-1=0))\;\vee\;((v<0)\;\wedge\;(uv+1=0)))\cr 0.0pt{\hfil$\displaystyle\;\wedge\;\cr 0.0pt{\hfil$\displaystyle(y,v)\in F\}.\crcr}}}}}}

Notice that $T$ is definable and for each fixed $x$ , $T_{x}\subset\mathrm{R}^{n+2}$ is a $(\mathcal{C},A^{\prime}\times B^{\prime})$ -set where $\mathcal{C}$ is a definable family of subsets of $\mathrm{R}^{n+2}$ parametrized by $(A\times B)$ , and $\mathcal{C}$ depends only on the definable families $\mathcal{A},\mathcal{B}$ .

Observe also that for each $x\in A$ and $u\in\mathrm{R}$ ,

T_{x,u}=\mathrm{graph}(f|_{S_{x,u}}).

We also define the set $L_{0}$ by

\halign{\hbox to\displaywidth{$\hfil\displaystyle#\hfil$}\cr 0.0pt{\hfil$\displaystyle L_{0}=\{(x,u,w)\;\mid\;\forall(y,v,z)\cr 0.0pt{\hfil$\displaystyle(w\geq 0)\cr 0.0pt{\hfil$\displaystyle\wedge\cr 0.0pt{\hfil$\displaystyle((x,u,y,v)\in T\wedge(y,z)\in G)\Longrightarrow\cr 0.0pt{\hfil$\displaystyle((z\geq 0)\wedge(w\geq z))\vee((z\leq 0)\wedge(w\geq-z)))\}.\crcr}}}}}}

Finally, let

L=\{(x,u,w)\;\mid\;(\forall w^{\prime})(x,u,w^{\prime})\in L_{0}\Longrightarrow(0\leq w\leq w^{\prime})\}.

Notice that for $x\in S$ , $(x,u,w)\in L$ if and only if $w=v(x,u)$ .

Also notice that the set $L\subset S\times\mathbb{R}^{2}$ is a definable set which is the complement of a projection of an $(\mathcal{D},D^{\prime})$ -set $P\subset\mathbb{R}^{2n+5}$ , where $\mathcal{D}$ is a definable family of sets parametrized by $A\times A\times B\times B$ and $D^{\prime}=A^{\prime}\times A^{\prime}\times B^{\prime}\times B^{\prime\prime}$ , and $\mathcal{D}$ depends only on the definable families $\mathcal{A},\mathcal{B}$ .

We now apply Proposition 5.4 to the definable family $\mathcal{D}$ . There exist a set of definable families $(\mathcal{C}_{j})_{j\in J}$ and a cylindrical decomposition $(\mathcal{D}_{1},\ldots,\mathcal{D}_{2n+5})$ of $\mathbb{R}^{2n+5}$ adapted to the set $P$ whose cells are of the form $(\mathcal{C}_{j})_{w}$ with $j\in J,w\in(D^{\prime})^{N(2n+5)}$ .

For $x\in S$ , there exists a unique cell, $C=(\mathcal{C}_{j})_{w}$ , $j\in J,w\in(D^{\prime})^{N(2n+5)}$ , of the decomposition $\mathbb{R}^{n}$ containing $x$ .

The definable functions $v(x,\cdot)$ as $x$ varies over $(\mathcal{C}_{j})_{w}$ and $w$ varies over $(A\times A\times B\times B)^{N(2n+5)}$ and $j\in J$ form a definable family, and using Proposition 5.2 in [38] there exists $p=p(\mathcal{A},\mathcal{B})$ such that

|v(x,u)|\leq c(x)\cdot u^{p},

for all $u$ large enough.

Now for each $x\in S$ , there exists a cell, $C=(\mathcal{C}_{j})_{w}$ $j\in J,w\in(D^{\prime})^{N(2n+5)}$ , of the decomposition $\mathbb{R}^{n}$ containing $x$ .

This proves the proposition taking $N=p+1$ . ∎

Theorem 6.

Let $\mathcal{A}$ be a definable family of subsets of $\mathrm{R}^{n}$ parametrized by the definable set $A$ , and let $\mathcal{B}$ be a definable subset of $\mathrm{R}^{n+1}$ parametrized by the definable set $B$ . Then there exists $N=N(\mathcal{A},\mathcal{B})>0$ having the following property. For any triple of finite sets $(A^{\prime},B^{\prime},B^{\prime\prime})$ with $A^{\prime}\subset A,B^{\prime},B^{\prime\prime}\subset B$ , a closed $(\mathcal{A},A^{\prime})$ -set $S$ , a $(\mathcal{B},B^{\prime})$ -set $F$ , $(\mathcal{B},B^{\prime\prime})$ -set $G$ , such that $F,G$ are graphs of definable functions $f:\mathbb{R}^{n}\rightarrow\mathbb{R},g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ continuous on $S$ , such that $f|_{S}^{-1}(0)\subset g|_{S}^{-1}(0)$ . Then there exists a continuous definable function $h:S\rightarrow\mathrm{R}$ such that $g|_{S}^{N}=hf|_{S}$ on $S$ .

Proof.

Similar to the proof of Theorem 5 replacing semi-algebraic by definable. ∎

Proof of Theorem 3.

Use Theorem 6 with $c=\sup_{x\in S}|h(x)|$ . ∎

6. Applications to optimization

As an illustration of the improvement one obtains by applying the improved bound on the Łojasiewicz exponent proved in Theorem 1 and the error bound in Theorem 2 we consider the following application in the theory of optimization. Clearly, Theorem 2 can be applied to other situations as well where error bounds are important, for example in the study of Hölderian continuity of the set-valued map defined by (2.5) as stated in [37, Theorem 3.1].

6.1. Binary feasibility problems

We can use Theorem 2 and its independence from the number of constraints to derive an error bound for a binary feasibility problem, where the feasible set is defined by

(6.1)		$\displaystyle M=\{x\in\mathrm{R}^{n}\mid g_{i}(x)\leq 0,\ h_{j}(x)$	$\displaystyle=0,\ i=1,\ldots,r,\ j=1,\ldots,s,$
	$\displaystyle x_{k}$	$\displaystyle\in\{0,1\},\ k=1,\ldots,n\},$

where $g_{i},h_{j}\in\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ . The following result is a quantified version of [37, Theorem 5.6] specialized for polynomials.

Corollary 2.

Let $M$ be defined in (6.1) and let $E$ be a closed and bounded $\mathcal{P}$ -semi-algebraic subset of $\mathrm{R}^{n}$ with $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d}$ . Then there exist $\kappa>0$ and $\rho=(O(d))^{2n+14}$ such that

\displaystyle\operatorname{dist}(x,M)^{\rho}\leq\kappa\cdot\psi(x),\quad\mbox{for all }x\in E,

where

\displaystyle\psi(x)=\sqrt{\sum_{j=1}^{s}(h_{j}(x))^{2}}+\sqrt{\sum_{i=1}^{r}(\max\{g_{i}(x),0\})^{2}}+\sum_{k=1}^{n}\lvert x_{k}(1-x_{k})\rvert.

Proof.

Note that for every $k=1,\ldots,n$ , the binary constraint on $x_{k}$ can be enforced by

\displaystyle x_{k}(1-x_{k})=0,\quad x_{k}\in[0,1]\subset\mathrm{R}.

Then $M$ can be redefined as

(6.2)		$\displaystyle M:=\Big{\{}x\in\mathrm{R}^{n}\mid g_{i}(x)\leq 0,\ h_{j}(x)$	$\displaystyle=0,$	$\displaystyle i$	$\displaystyle=1,\ldots,r,\ j=1,\ldots,s,$
	$\displaystyle x_{k}(1-x_{k})$	$\displaystyle=0,$	$\displaystyle k$	$\displaystyle=1,\ldots,n,\Big{\}},$

which is a finite subset of $\mathrm{R}^{n}$ .

Also observe that defining

\displaystyle\widetilde{\psi}(x)=\sum_{j=1}^{s}|h_{j}(x)|+\sum_{i=1}^{r}\max\{g_{i}(x),0\}+\sum_{k=1}^{n}\lvert x_{k}(1-x_{k})\rvert,

it follows from the Cauchy-Schwarz inequality that

\widetilde{\psi}(x)\leq c\cdot\psi(x),

with $c=\max\{1,\sqrt{r},\sqrt{s}\}>0$ .

Now the result follows by applying the second part of Theorem 2 and Remark 6 to (6.2) and the residual function $\widetilde{\psi}(x)$ . ∎

6.2. Convergence rate of feasible descent schemes

Error bounds are important to estimate the convergence rate of iterative algorithms in nonlinear optimization. Here, we present the convergence analysis in [36, Theorem 5], which is relevant to Theorem 1.

Let $\mathrm{R}=\mathbb{R}$ and $g_{i},h_{j}$ defined in (2.5) be convex polynomials. Then the goal of a feasible descent scheme is to find stationary solutions of a polynomial $f\in\mathbb{R}[X_{1},\ldots,X_{n}]_{\leq d}$ over a convex $M$ (assuming that $\inf_{x\in M}f>-\infty$ ), where a stationary solution is an $x\in\mathbb{R}^{n}$ such that

\displaystyle x-\operatorname{Proj}_{M}\!\big{(}x-\nabla f(x)\big{)}=0,

in which $\operatorname{Proj}_{M}(\cdot)$ denotes the projection onto the convex set $M$ . The idea of a feasible descent scheme is to generate a sequence $\{x_{k}\}_{k=1}^{\infty}$ of solutions by

(6.3)

\displaystyle x_{k+1}=\operatorname{Proj}_{M}\!\big{(}x_{k}-\alpha_{k}\nabla f(x_{k})+e_{k}\big{)},

where $\alpha_{k}>0$ is so-called the step length and $e_{k}$ is an error vector depending on $x_{k}$ . If we define the set of stationary solutions as

\displaystyle S:=\Big{\{}x\in\mathbb{R}^{n}\mid x-\operatorname{Proj}_{M}\!\big{(}x-\nabla f(x)\big{)}=0\Big{\}},

then the following result is well-known for the convergence rate of a feasible descent scheme which we specialize for the polynomial $f$ .

Proposition 6.1 (Theorem 5 in [36]).

Suppose that the gradient of $f$ is Lipschitz continuous and there exists $\varepsilon>0$ such that

\displaystyle x\in S,\ \ y\in S,\ \ f(x)\neq f(y)\Longrightarrow\|x-y\|\geq\varepsilon.

If $\liminf\alpha_{k}>0$ and the sequences $\{e_{k}\}_{k=1}^{\infty}$ and $\{x_{k}\}_{k=1}^{\infty}$ generated by (6.3) satisfy

	$\displaystyle\\|e_{k}\\|\leq\kappa_{1}\\|x_{k}-x_{k+1}\\|,\ \text{for some}\ \kappa_{1}>0,$
	$\displaystyle f(x_{k+1})-f(x_{k})\leq-\kappa_{2}\\|x_{k}-x_{k+1}\\|^{2},\ \text{for some}\ \kappa_{2}>0,$

then the sequence $\{f(x_{k})\}_{k=1}^{\infty}$ converges at least sub-linearly, at the rate $k^{1-\rho}$ , where $\rho\geq 1$ is an integer satisfying

\displaystyle\operatorname{dist}(x,S)^{\rho}\leq\kappa\cdot\|x-\operatorname{Proj}_{M}\!\big{(}x-\nabla f(x)\big{)}\|

for some $\kappa>0$ and for all $x$ in a compact semi-algebraic subset of $M$ .

Notice that $S$ and $\|x-\operatorname{Proj}_{M}\!\big{(}x-\nabla f(x)\big{)}\|$ are both semi-algebraic, and the latter is a residual function. Therefore, Theorem 1 and Lemma 5.3 can be applied to quantify the convergence rate $k^{1-\rho}$ in terms of $d$ and $n$ only.

Remark 10.

The upper bound (3.6) was used to quantify the convergence rate of the cyclic projection algorithm applied to finite intersections of convex semi-algebraic subsets of $\mathbb{R}^{n}$ [11, Theorem 4.4].

6.3. Sums of squares relaxation

A polynomial optimization problem is formally defined as the following: given a polynomial $f\in\mathbb{R}[X_{1},\ldots,X_{n}]_{\leq d}$ , compute

(6.4)

\displaystyle f_{\min}^{*}:=\inf\big{\{}f(x)\mid x\in M\big{\}},

where $M$ is defined in (2.5) with $\mathrm{R}=\mathbb{R}$ . We assume, without loss of generality, here that $s=0$ in (2.5).

Unlike semi-definite optimization, see e.g., [5], there is no efficient interior point method for polynomial optimization. Nevertheless, tools in real algebra have laid the groundwork for developing an efficient numerical approach, where semi-definite relaxation plays a central role. Using this approach, (6.4) is approximated by a hierarchy of semi-definite relaxations, so-called sums of squares (SOS) relaxations [26, 44], see also [27]. A SOS relaxation of order $t$ is defined as

(6.5)

\displaystyle f_{\mathrm{sos}}^{*t}=\sup\{\beta\mid f-\beta\in\mathbf{\mathcal{M}}_{2t}(g_{1},\ldots,g_{r})\},

where

	$\displaystyle\mathbf{\mathcal{M}}_{2t}(g_{1},\ldots,g_{r})$	$\displaystyle=$
		$\displaystyle\bigg{\{}u_{0}-\sum_{j=1}^{r}u_{j}g_{j}\mid u_{0},u_{j}\in\Sigma,\ \deg(u_{0}),\deg(u_{j}g_{j})\leq 2t,\ j=1,\ldots,r\bigg{\}}$

is called the truncated quadratic module generated by $g_{1},\ldots,g_{r}$ and $\Sigma$ is the convex cone of SOS polynomials. It is worth noting that (6.5) is a semi-definite optimization problem of size $O(n^{t})$ . Under some conditions on $M$ , see e.g., [27, Proposition 6.2 and Theorem 6.8], (6.5) is feasible for sufficiently large $t$ , and $f_{\mathrm{sos}}^{*t}\to f_{\min}^{*}$ as $t\to\infty$ .

Recently, Baldi and Mourrain [1] provided a convergence rate for $f_{\mathrm{sos}}^{*t}$ in terms of $t$ , in which the Łojasiewicz exponent plays a central role. The authors proved [1, Theorem 4.3], under some conditions, that there exists $c>1$ such that

\displaystyle 0<f_{\min}^{*}-f_{\mathrm{sos}}^{*t}\leq c\cdot\|f\|\deg(f)^{\frac{7}{5}}t^{-\frac{1}{2.5n\rho}},

where $c$ depends on $n$ , $\rho$ , and $g_{1},\ldots,g_{r}$ , $\|f\|:=\max_{x\in[-1,1]^{n}}|f(x)|$ , and $\rho$ is the error bound exponent for the inequality

\displaystyle\operatorname{dist}(x,M)^{\rho}\leq\kappa\cdot|\min\{g_{1}(x),\ldots,g_{r}(x),0\}|,\quad\text{for all}\ x\in[0,1]^{n}

for some $\kappa>0$ . Then the application of Theorem 2 and Remark 6 yields an upper bound $d^{O(n^{2})}$ on $\rho$ and thus proves a lower bound on the convergence rate $t^{-\frac{1}{2.5n\rho}}$ of the SOS relaxation in terms of $n$ and $d$ only.

Remark 11.

There are other applications of the Lojasiewicz inequality to polynomial optimization in the literature. For instance, it was shown in [23] that the Łojasiewicz inequality (3.2) can be used to reduce (6.4) to minimization over a ball.

7. Conclusion

In this paper, we proved a nearly tight upper bound on the Łojasiewicz exponent for semi-algebraic functions over a real closed field $\mathrm{R}$ in a very general setting. Unlike the previous best known bound in this setting due to Solernó [45], our bound is independent of the cardinalities of the semi-algebraic descriptions of $f$ , $g$ , and $A$ . We exploited this fact to improve the best known error bounds for polynomial and non-linear semi-definite systems. As an abstraction of the notion of independence from the combinatorial parameters, we proved a version of Łojasiewicz inequality in polynomially bounded o-minimal structures. We proved existence of a common Łojasiewicz exponent for certain combinatorially defined infinite (but not necessarily definable) families of pairs of functions, which improves a prior result due to Chris Miller [38].

We end with a few open problems. We proved in Theorem 2 that the exponent $\rho=d^{O(n)}$ in the error bound with respect to a zero-dimensional semi-algebraic set $M$ , and Example 1 indicates that this bound is indeed tight. Without the assumption on the dimension on $M$ , the general bound on the exponent $\rho$ in Theorem 2 is $d^{O(n^{2})}$ . There are some indications in [21] for generating examples whose Łojasiewicz exponent is worse than Example 1. However, we have not been able to find any example with $\rho=d^{O(n^{2})}$ , so we do not know if this bound is tight as well. It would be interesting to resolve this gap.

Another interesting question is to prove an upper bound that depends on $\dim M$ which interpolates between the $0$ -dimensional and the general case. More precisely, is it possible to improve the upper bound in Theorem 2 to $d^{O(n\cdot\dim M)}$ ?

While the emphasis in the current paper has been on proving a bound on the Łojasiewicz exponent which is independent of the combinatorial parameter there is a special case that merits attention and in which the combinatorial parameter may play a role. It is well known [2] that the topological complexity (say measured in terms of the Betti numbers) of a real algebraic set in $\mathrm{R}^{n}$ defined by $s$ quadratic equations is bounded by $n^{O(s)}$ . This bound (unlike the bounds discussed in the current paper) is polynomial in $n$ for fixed $s$ . One could ask if a similar bound also holds in this setting for the Łojasiewicz exponent.

Acknowledgements

The first author was partially supported by NSF grants CCF-1910441 and CCF-2128702. The second author was partially supported by NSF grant CCF-2128702.

References

[1] L. Baldi and B. Mourrain, On the effective Putinar’s positivstellensatz and moment approximation, (2022). arXiv:2111.11258v2 https://arxiv.org/abs/2111.11258.
[2] A. I. Barvinok, On the Betti numbers of semi-algebraic sets defined by few quadratic inequalities, Math. Z., 225 (1997), pp. 231–244.
[3] S. Basu, Combinatorial complexity in o-minimal geometry, Proc. London Math. Soc. (3), 100 (2010), pp. 405–428.
[4] S. Basu, Algorithms in real algebraic geometry: a survey, in Real algebraic geometry, vol. 51 of Panor. Synthèses, Soc. Math. France, Paris, 2017, pp. 107–153.
[5] S. Basu and A. Mohammad-Nezhad, On the central path of semi-definite optimization: Degree and worst-case convergence rate, SIAM Journal on Applied Algebra and Geometry, 6 (2022), pp. 299–318.
[6] S. Basu, R. Pollack, and M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43 (1996), pp. 1002–1045.
[7] , Algorithms in real algebraic geometry, vol. 10 of Algorithms and Computation in Mathematics, Springer-Verlag, Berlin, version bpr-ed2-posted3 from 27/06/2016 available at http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html.
[8] S. Basu and M.-F. Roy, Bounding the radii of balls meeting every connected component of semi-algebraic sets, Journal of Symbolic Computation, 45 (2010), pp. 1270–1279.
[9] S. Basu and M.-F. Roy, Quantitative curve selection lemma, Mathematische Zeitschrift, (2021).
[10] J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry, Springer, 1998.
[11] J. M. Borwein, G. Li, and L. Yao, Analysis of the convergence rate for the cyclic projection algorithm applied to basic semi-algebraic convex sets, SIAM Journal on Optimization, 24 (2014), pp. 498–527.
[12] L. Bröcker, On basic semi-algebraic sets, Expositiones Mathematicae, 9 (1991), pp. 289–334.
[13] M. Coste, An introduction to o-minimal geometry, Istituti Editoriali e Poligrafici Internazionali, Pisa, 2000. Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica.
[14] D. D’Acunto and K. Kurdyka, Explicit bounds for the Łojasiewicz exponent in the gradient inequality for polynomials, Annales Polonici Mathematici, 87 (2005), pp. 51–61.
[15] E. de Klerk, Aspects of Semi-definite Programming: Interior Point Algorithms and Selected Applications, vol. 65 of Series Applied Optimization, Springer, 2006.
[16] A. Gabrielov and N. Vorobjov, Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. (2), 80 (2009), pp. 35–54.
[17] J. Gwoździewicz, The Łojasiewicz exponent of an analytic function at an isolated zero, Commentarii Mathematici Helvetici, 74 (1999), pp. 364–375.
[18] L. Hörmander, On the division of distributions by polynomials, Ark. Mat., 3 (1958), pp. 555–568.
[19] L. Hörmander, On the division of distributions by polynomials, Arkiv för Matematik, 3 (1958), pp. 555–568.
[20] S. Ji, J. Kollar, and B. Shiffman, A global Łojasiewicz inequality for algebraic varieties, Transactions of the American Mathematical Society, 329 (1992), pp. 813–818.
[21] J. Kollár, An effective Łojasiewicz inequality for real polynomials, Periodica Mathematica Hungarica, 38 (1999), pp. 213–221.
[22] K. Kurdyka and S. Spodzieja, Separation of real algebraic sets and the Łojasiewicz exponent, Proceedings of the American Mathematical Society., 142 (2014-9-14), pp. 3089–3102.
[23] , Convexifying positive polynomials and sums of squares approximation, SIAM Journal on Optimization, 25 (2015), pp. 2512–2536.
[24] K. Kurdyka, S. Spodzieja, and A. Szlachcińska, Metric properties of semi-algebraic mappings, Discrete & Computational Geometry, 55 (2016), pp. 786–800.
[25] , Correction to: Metric properties of semi-algebraic mappings, Discrete & Computational Geometry, 62 (2019), pp. 990–991.
[26] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2001), pp. 796–817.
[27] M. Laurent, Sums of Squares, Moment Matrices and Optimization Over Polynomials, Springer New York, New York, NY, 2009, pp. 157–270.
[28] A. S. Lewis and J.-S. Pang, Error Bounds for Convex Inequality Systems, Springer US, Boston, MA, 1998, pp. 75–110.
[29] G. Li, On the asymptotically well behaved functions and global error bound for convex polynomials, SIAM Journal on Optimization, 20 (2010), pp. 1923–1943.
[30] G. Li, B. S. Mordukhovich, and T. S. Pham, New fractional error bounds for polynomial systems with applications to hölderian stability in optimization and spectral theory of tensors, Mathematical Programming, 153 (2015), pp. 333–362.
[31] S. Łojasiewicz, Sur le problème de la division, Studia Math., 18 (1959), pp. 87–136.
[32] S. Łojasiewicz, Triangulation of semi-analytic sets., Ann. Scuola Norm. Sup. Pisa, Sci. Fis. Mat., 18 (1964), pp. 449–474.
[33] , Ensembles semi-analytiques. preprint, IHES, 1965.
[34] S. Łojasiewicz, Sur les ensembles semi-analytiques, (1971), pp. 237–241.
[35] X.-D. Luo and Z.-Q. Luo, Extension of Hoffman’s error bound to polynomial systems, SIAM Journal on Optimization, 4 (1994), pp. 383–392.
[36] Z.-Q. Luo, New error bounds and their applications to convergence analysis of iterative algorithms, Mathematical Programming, 88 (2000), pp. 341–355.
[37] Z.-Q. Luo and J.-S. Pang, Error bounds for analytic systems and their applications, Mathematical Programming, 67 (1994), pp. 1–28.
[38] C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic, 68 (1994), pp. 79–94.
[39] J. Milnor, Singular points of complex hypersurfaces, Annals of Mathematics Studies, No. 61, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1968.
[40] L. M. G. na Drummond and Y. Peterzil, The central path in smooth convex semidefinite programs, Optimization, 51 (2002), pp. 207–233.
[41] B. Osińska-Ulrych, G. Skalski, and S. Spodzieja, Effective Łojasiewicz gradient inequality for Nash functions with application to finite determinacy of germs, Journal of the Mathematical Society of Japan, 73 (2021), pp. 277–299.
[42] B. Osińska-Ulrych, G. Skalski, and A. Szlachcińska, Łojasiewicz inequality for a pair of semi-algebraic functions, Bulletin des Sciences Mathématiques, 166 (2021), p. 102927.
[43] J.-S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), pp. 299–332.
[44] P. A. Parrilo, Semi-definite programming relaxations for semi-algebraic problems, Math. Program., 96 (2003), pp. 293–320. Algebraic and geometric methods in discrete optimization.
[45] P. Solernó, Effective Łojasiewicz inequalities in semi-algebraic geometry, Applicable Algebra in Engineering, Communication and Computing, 2 (1991), pp. 1–14.
[46] S. Starchenko, NIP, Keisler measures and combinatorics, no. 390, 2017, pp. Exp. No. 1114, 303–334. Séminaire Bourbaki. Vol. 2015/2016. Exposés 1104–1119.
[47] L. van den Dries, Tame topology and o-minimal structures, vol. 248 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1998.
[48] R. J. Walker, Algebraic Curves, Springer, New York, NY, USA, 1978.

Improved effective Łojasiewicz inequality and applications

Abstract.

Key words and phrases:

2000 Mathematics Subject Classification:

1. Introduction

2. Main results

Definition 2.1 (𝒫\mathcal{P}-formulas and semi-algebraic sets).

2.1. Semi-algebraic case

Theorem 1.

Remark 1 (Sharpness).

Example 1.

Remark 2 (Independence from the combinatorial parameter).

Remark 3 (Separation of combinatorial and algebraic parts).

Remark 4.

2.2. Application to error bounds

Definition 2.2 (Error bounds and residual function).

Theorem 2.

Remark 5.

Remark 6.

Corollary 1.

2.3. O-minimal case

2.3.1. Extension of the notion of combinatorial complexity to arbitrary o-minimal structures

2.3.2. Łojasiewicz inequality in polynomially bounded o-minimal structures

Notation 1.

Definition 2.3.

Example 2.

Theorem 3 (Łojasiewicz inequality for 𝒜\mathcal{A}-sets and ℬ\mathcal{B}-functions for any pair of definable families 𝒜\mathcal{A} and ℬ\mathcal{B}).

Remark 7 (Theorem 3 generalizes Theorem 5.4 (page 94) in [38]).

2.4. Outline of the proofs of the main theorems

3. Prior and related work

3.1. Prior results on Łojasiewicz inequality

3.2. Other forms of Łojasiewicz inequality

3.3. Prior work on error bounds

4. Combinatorial and algebraic complexity

Theorem (Quantitative Curve Selection Lemma).

Theorem 4 (Quantifier Elimination).

5. Proofs of the main results

5.1. Proof of Theorem 1

5.1.1. Cylindrical definable decomposition

Definition 5.1 (Cylindrical definable decomposition).

5.1.2. Sign conditions

Notation 2 (Sign conditions and their realizations).

Lemma 5.1.

Proof.

Notation 3 (Realizable sign conditions).

Proposition 5.1.

Proof.

Lemma 5.2.

Proof.

Proposition 5.2.

Proof.

Theorem 5.

Proof.

Proof of Theorem 1.

5.2. Proof of Theorem 2

Lemma 5.3.

Proposition 5.3 (Thom’s Lemma).

Proof of Lemma 5.3.

Remark 8.

Proof of Theorem 2.

Remark 9.

Proof of Corollary 1.

5.3. Proof of Theorem 3

Proposition 5.4 (Quantitative cylindrical definable cell decomposition).

Proposition 5.5 (o-minimal quantitative version of Proposition 2.6.4 in [10]).

Proof.

Theorem 6.

Proof.

Proof of Theorem 3.

6. Applications to optimization

6.1. Binary feasibility problems

Corollary 2.

Proof.

6.2. Convergence rate of feasible descent schemes

Proposition 6.1 (Theorem 5 in [36]).

Remark 10.

6.3. Sums of squares relaxation

Remark 11.

7. Conclusion

Acknowledgements

Definition 2.1 ( $\mathcal{P}$ -formulas and semi-algebraic sets).

Theorem 3 (Łojasiewicz inequality for $\mathcal{A}$ -sets and $\mathcal{B}$ -functions for any pair of definable families $\mathcal{A}$ and $\mathcal{B}$ ).