zbMATH — the first resource for mathematics

Une inégalité de Łojasiewicz effective. (Effective Łojasiewicz inequality). (French) Zbl 0754.14036
Among the main results in real algebraic geometry we can quote Łowasiewicz inequality and the finiteness theorem. The first one in its more basic form says that given a compact semi-algebraic set \(V\subset\mathbb{R}^ n\) and polynomial functions \(F,G:V\to\mathbb{R}\) such that the zero-set of \(F\) is contained in the one of \(G\) then, there are numbers \(N\) and \(c\) such that for all \(x\) in \(V\) we have \(| G(x)|^ N\leq c| F(x)|\). On the other hand, the finiteness theorem states that any open semi-algebraic subset of \(\mathbb{R}^ n\) can be written as a finite union of basic open semi-algebraic sets. In the paper under review the author puts emphasis on the effective and quantitative side of this theorem. On the one hand, he bounds the constants appearing and on the other hand, he gives an algorithmic procedure for computing them. Moreover, this effective version of Łojasiewicz inequality is given for arbitrary continuous semi-algebraic functions – instead of polynomials. More precisely, for any formula \(\Phi\) we define \(\deg(\Phi)\) to be the sum of the degrees of the polynomials appearing in \(\Phi\), \(n(\Phi)\) its number of variables and \(a(\Phi)\) its number of quantifier alternations. With these notations the main result of the paper can be stated in the following way:
Let \(V\subset\mathbb{R}^ n\) be a compact semi-algebraic set defined by a prenex formula \(\Phi\) and \(f,g:V\to\mathbb{R}\) be continuous semi-algebraic functions whose graphs are defined by prenex formulae \(\Phi_ f\) and \(\Phi_ g\) such that the zero-set of \(f\) is included in that of \(g\). Also, let us consider \(D=\max\{\deg(\Phi),\det(\Phi_ f),\deg(\Phi_ g)\}\), \(n=\max\{n(\Phi),n(\Phi_ f),n(\Phi_ g)\}\), \(a=\max\{a(\Phi),a(\Phi_ f),a(\Phi_ g)\}\). Then, there is a universal constant \(c_ 1\in\mathbb{N}\) and a constant \(c_ 2\in\mathbb{R}\) (depending on \(V\), \(f\) and \(g)\) such that:
(i) if \(a>0\) then \(| g(x)|^{D^{n^{c_ 1\cdot a}}}\leq c_ 2\cdot| f(x)|\) for all \(x\in V\)
(ii) if \(a=0\) then \(| g(x)|^{D^{c_ 1\cdot n}}\leq c_ 2\cdot| f(x)|\) for all \(x\in V\).
Moreover, if the formulae are defined over \(\mathbb{Z}\), and \(\ell\) is a bound for the absolute values of the coefficients in \(\Phi\), \(\Phi_ f\) and \(\Phi_ g\), then we can choose \(c_ 2=\ell^{D^{n^{k\cdot a}}}\) in (i) and \(c_ 2=\ell^{D^{k\cdot n^ 2}}\) in (ii) with \(k\) a universal constant.
The preceding result improves the state of the art concerning Łojasiewicz inequality since its exponent is shown to be polynomial in \(D\) and single exponential in \(n\) (instead of doubly exponential). On the other hand the author quotes an already known example that allows him to prove optimality of this single exponential character. Finally, he applies these results to obtain an effective version of the finiteness theorem, showing that if \(S\) is an open semi-algebraic set described by a quantifier-free formula \(\Phi\), then it can be written as a union of at most \(D\) basic open sets the polynomials of which have degree bounded by \(D^{O(n^ 3)}\) in (fact, the sum of all their degrees is bounded by \(D^{O(n^ 3)})\).
An expanded version of the paper appeared in Appl. Algebra Eng. Commun. Comput. 2, No. 1, 1-14 (1991; see above).

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
14P10 Semialgebraic sets and related spaces
68W30 Symbolic computation and algebraic computation