A NOTE ON RABIN’S WIDTH OF A COMPLETE PROOF

José L. Montaña, Luis M. Pardo and Tomas Recio

This paper is published in
Computational Complexity
Vol.  4, pages 12--36, 1994.

Abstract. We introduce and analyze the concept of generic width of a semialgebraic set, showing that it gives lower bounds for decisional complexities. By means of the computation of the generic width we are able to solve rigorously the complexity problems posed by M.O. Rabin in [10], such as optimization of linear mappings on finite sets. We show that the results on the generic width can also be applied to obtain lower bounds for problems which in general do not admit a linear mapping description, such as optimization of polynomial mappings on finite sets, existence of a real root, finite selection and subset decision, or the direct oriented–convex hull problem introduced by J. Jaromczyk in [8].

Key words. Algebraic complexity theory; decisional complexity; semialgebraic sets; width of a complete proof; generic width of a semialgebraic set.

Subject classifications. 68Q25, 68Q40, 14P20, 14P10.

1. Introduction

Within the general framework of algebraic complexity theory, a paper of M. O. Rabin ([10]) discussed the optimality of algorithms solving the membership problem for convex sets given by the simultaneous positivity of linear forms. Formally, the author analyzed the complexity of convex sets of the kind

W = {x ∈ IR^{n} : L_{1}(x) ≥ 0, …, L_{m}(x) ≥ 0}

where the L_{j} : IR^{n} ⟶ IR are affine linear functions for 1 ≤ j ≤ m. The main applications presented by Rabin deal with lower bounds for the following problems (involving real numbers as inputs, and all having complexity O(N)).

Problem 1.1. Given N real numbers x_{1}, …, x_{N} ∈ IR, find j such that x_{j} is the maximum of all of them.

Problem 1.2. Given N real numbers x_{1}, …, x_{N} ∈ IR, find j such that x_{j} is the minimum of all of them.

Problem 1.3. Given 2N real numbers x_{1}, …, x_{N}, y_{1}, …, y_{N} ∈ IR, find j such that x_{j} + y_{j} is the minimum of all the sums x_{i} + y_{i} for 1 ≤ i ≤ N.

Problem 1.4. The membership problem for an N–orthant, i.e., given x ∈ IR^{N} decide whether x belongs to the semialgebraic set

O_{N} = {x = (x_{1}, …, x_{N}) ∈ IR^{N} : x_{1} ≥ 0, …, x_{N} ≥ 0}.

Problems 1.1 to 1.3 above are particular cases of the maximization and minimization of linear functions over finite sets problem. As in [1], one can ask the natural question: why can’t these problems be solved in constant time?

Rabin’s computation model in [10] is the (non–uniform) model given by a sequence of algebraic computation trees {T_{N}}_{N∈IN}. In terms of the size N of the problem instances (the cardinality of the input set), the complexity of the problem is the number of arithmetic operations and polynomial sign tests that are performed to reach a leaf in T_{N}. As was observed in [9], a usual method to obtain lower bounds in this model is to choose a weaker measure of complexity: for instance, Rabin introduced decisional measures of complexity (taking arithmetic operations for free). Then, he computed the width of a complete proof of a simultaneous positivity for the convex set W, claiming that, in general, the minimum width gives a lower bound for the decisional complexity of each problem. In order to conclude this claim he argues that a complete proof is immediately obtained from an algebraic computation tree, showing in this way that Ω(N) is actually a lower bound for the problems. As remarked in Section 3 below, the relationship between complete proofs and algebraic computation trees is not so straightforward, and the validity of using the width as a lower bound is not so clear.

In 1981, J.W. Jaromczyk [8] extended the concept of the width of a complete proof to the case of non–linear polynomials, but without noticing this problem. Thus, he also assumes—without any proof—that the width of any complete proof relative to the trivial clause [1 ≠ 0] provides a lower bound for the following geometric problem.

Direct oriented–convex hull problem (DO–CH problem). Given a sequence (z_{1}, …, z_{N}) of points in the real plane, z_{i} ∈ IR^{2}, decide whether they are the clockwise oriented vertices of their convex hull.

The present note intends to fill in the gaps in [8] and [10]. First, we consider the complexity analysis in the more general setting of semialgebraic sets; see Section 2 for definitions. Then, in Section 3, after extending the definition of width in [8] and [10], we introduce the concept of the generic width of a semialgebraic set. The relation and differences between width and generic width are explained in Subsection 3.6. Next, in Section 4, we prove that the generic width gives a lower bound for the decisional complexity. We remark that it is unknown whether the “width” is a lower bound for decisional complexity. Luckily we are able to compute in many cases (see, for instance, Corollaries 3.9, 3.10, and 3.11) the generic width of a semialgebraic set and we observe that, in the examples studied by Rabin, the generic width agrees with the minimum width of any complete proof relative to any non–zero polynomial (see Subsection 4.5). As an application of Theorem 3.8, we are able to show that Problems 1.1 to 1.4 above and the DO–CH problem all have linear lower bounds, as stated by Rabin and Jaromczyk respectively (see Subsections 4.1 and 4.2).

Our techniques are also applied to new problems involving non–linear polynomials, as finite polynomial optimization (which strictly includes Problems 1.1 to 1.3 above).

Let f ∈ IR[X_{1}, …, X_{n}] be a fixed non–constant polynomial.

Finite polynomial maximization. Given a finite set F = {x_{1}, …, x_{N}} ⊆ IR^{n} find an element x_{i} ∈ F such that f(x_{i}) is the maximum of f(F).

Finite polynomial minimization. Given a finite set F = {x_{1}, …, x_{N}} ⊆ IR^{n} find an element x_{i} ∈ F such that f(x_{i}) is the minimum of f(F).

Other applications are finite subset decision, finite selection (under the hypothesis of real complete intersection) and existence of a real root (see Section 4 for more detailed descriptions).

The main technique used in Section 3 of this paper to compute lower bounds of the generic width of semialgebraic sets detects a local obstruction which is invariant under semialgebraic diffeomorphisms (i.e., Nash diffeomorphisms). Namely, we find that for any semialgebraic set W with a Nash m−corner point, the inequality m ≤ ω_{gen}(W) holds (see Theorem 3.8 below and [13] for the terminology). Therefore, the complexity of W is also greater than m. We think that this is an interesting result by itself, since the usual methods used to provide lower bounds of semialgebraic sets regard only some global geometric features of the considered set, such as connected components or geometric degrees (see [1], [9], [14], or [15]). For this reason, we have introduced as a mere technical device some facts from real algebraic geometry and elementary Nash function theory (see [2] and [3]).

2. Decisional Measures of Complexity

A semialgebraic set is a subset W of some real affine space, W ⊆ IR^{n}, that can be described by a boolean combination of polynomial equations and inequalities, i.e., the set W can be given as

W = ⋃_{i∈I}{x ∈ IR^{n} : p_{i}(x) = 0, q_{i,j}(x) > 0 for j ∈ J}

where the polynomials p_{i}, q_{i,j} ∈ IR[X_{1}, …, X_{n}] for i ∈ I, j ∈ J, and I, J are finite sets. The subset W is said to be open basic in IR^{n} if #I = 1 and only strict inequalities occur. Closed basic semialgebraic subsets W of IR^{n} are those given as a simultaneous positivity of arbitrary polynomials, i.e., W = {x ∈ IR^{n} : p_{1}(x) ≥ 0, …, p_{r}(x) ≥ 0}. The following result relates the property of being closed (respectively, open) for the Euclidean topology in IR^{n} and the existence of formulae describing the set only with “ ≥ 0” sign conditions.

Finiteness Theorem (see [3], 2.7.1, [7], and [11]). Every closed semialgebraic subset W of IR^{n} is a finite union of closed basic semialgebraic sets, i.e., there are non–negative integers k, t, and polynomials p_{i,j} ∈ IR[X_{1}, …, X_{n}] such that

W = ⋃_{i=1}^{t}{x ∈ IR^{n} : p_{i,1}(x) ≥ 0, …, p_{i,k}(x) ≥ 0}.

As a consequence of this, by taking complements, semialgebraic sets open in the Euclidean topology in IR^{n} are finite unions of open basic semialgebraic sets.

An algebraic computation tree (ACT for short), T = T (X_{1}, …, X_{n}), introduced in [1] and [10], is a rooted binary tree with a finite number of nodes. Nodes are of four types: just one input node (the root of the tree, accepting x = (x_{1}, …, x_{n}) ∈ IR^{n} as input), computation nodes (nodes with just one child where an arithmetic operation is performed), branching nodes (nodes with two children where a sign test “z_{i} μ 0?”, μ ∈ {≥, >, =} is executed for some precomputed z_{i}) and output nodes (also called leaves, labeled with the corresponding YES/NO answer). With respect to the definitions in [10] we have added sign tests of the form “P = 0?” but this does not modify either the model of computation or the complexity measure we describe below. Both approaches to describing ACT’s are essentially equivalent.

The subset W (T) of IR^{n} accepted by an ACT, T = T (X_{1}, …, X_{n}), is the subset of all points in IR^{n} that follow a path in T from the root to some leaf with an affirmative answer. Observe that the subsets accepted by some ACT and the class of semialgebraic sets coincide. As in algebraic complexity theory, the total complexity of a semialgebraic set W is defined as the minimum height of any ACT accepting W (see [1], [9], [14], or [15]).

In order to deal with the problems stated in Section 1, [10] introduces a weaker measure of the complexity that takes arithmetic operations for free.

Definition 2.1. Let T be an algebraic computation tree and W a semialgebraic subset of IR^{n}

i) The decisional height of a path Γ from the root to some leaf in T, h_{D}(Γ), is the number of branching nodes occuring in Γ.

ii) Likewise, the decisional height of T, h_{D}(T), is the maximum of all the decisional heights of all paths Γ in T.

iii) The decisional complexity of W, C_{D}(W), is the minimum decisional height of all ACT’s solving the membership problem for W.

Proposition 2.2. The decisional complexity of any semialgebraic set of dimension d can be bounded by an effective function of d.

Proof. Given a semialgebraic set W of dimension d it can be decomposed as the union of a semialgebraic set which is open in the Zariski closure of W plus a semialgebraic set of strictly smaller dimension. Now, every open semialgebraic set in an algebraic set of dimension d can be written using at most s(d) × t(d) polynomials, where s(d) and t(d) are the upper bounds of the Bröcker invariants (see [5] and [6]), and are some effective functions of d. In fact, s(d) is defined as the minimum number of polynomial strict inequalities (“> 0”) needed to represent an open basic semialgebraic set in an algebraic set V of dimension d. In the same way, t(d) is the minimum number of unions of basic closed semialgebraic sets needed to represent an open semialgebraic set in an algebraic set V of dimension d. Bröcker’s work shows that these bounds depend only on the dimension d and not on the particular algebraic variety where one considers the semialgebraic sets. More concretely, it is shown in [5] that s(d) equals d and

t(d) ≤ t(d − 1) + \binom{4^{d−1}}{2 · 4^{d−2} − 2^{d−2}} .

Therefore the decisional complexity of this open set is at most s(d) × t(d) + 1: one may construct an ACT that tests, using just one branching node, the membership in the Zariski closure of W, and then concatenate the s(d) × t(d) polynomials to test membership in the open set. Since the zero dimensional case involves only decisional height one, we use induction on the dimension of the semialgebraic set W to complete the proof. □

Remark 2.3. The decisional complexity is clearly a lower bound for the total complexity of any semialgebraic set (counting also the number of involved arithmetic operations, as in [1] and [9]). But Proposition 2.2 above shows that decisional complexity fails in most cases to approximate total complexity; in fact, one can exhibit semialgebraic sets in IR^{n} of arbitrarily high total complexity while the decisional complexity is always bounded by a function of d ≤ n. For example, an algebraic subset of IR always has decisional complexity one, but the total complexity depends on the number of its components. Another example is that of regular polygons in IR^{2} having decisional complexity two, regardless of the number of vertices—which determines the total complexity (see [9]). Notice that every regular polygon Q in IR^{2} is given as Q = {(x, y) ∈ IR^{2} : P (x, y) ≥ 0, Q(x, y) ≥ 0}, where P (X, Y) is the equation of the circle passing through all the vertices of Q, while Q(X, Y) is the polynomial given as the product of the equations of all lines passing through the sides of the polygon Q. This behavior can explain in precise terms the comment of Ben-Or in [1] about the failure of the methods of Rabin and Jaromczyk, using algebraic decision trees, to give non–linear lower bounds for some problems.

We can observe that the decisional complexity is not necessarily a lower bound in terms of the input size. For instance, in [1] Ben-Or analyzed lower bounds for the total complexity of the following problem.

Element distinctness problem. Given x_{1}, …, x_{N} ∈ IR, is there a pair i, j with i ≠ j and x_{i} = x_{j}?

A Ω(Nlog_{2}N) lower bound for the total complexity of this problem is given in [1]. However, the decisional complexity of element distinctness is clearly 1.

3. Generic Width of a Semialgebraic Set

Nevertheless, the decisional complexity provides a useful lower bound for some other problems (where topological methods as in [1] and [9] fail), when combined with the analysis of the concept of width according to the following definition: denote by SP (X) the formula given by the conjunction

L_{1}(X) ≥ 0 ∧ ⋯ ∧ L_{m}(X) ≥ 0

where L_{j} : IR^{n} ⟶ IR are affine linear functions for 1 ≤ j ≤ m.

Definition 3.1. ([10]) Let Q(X) = Q(X_{1}, ⋯, X_{n}) be a polynomial and F a convex subset of IR^{n}. We say that the t × k array P of polynomials

P = ( \begin{matrix}p_{1,1}(X) & … & p_{1,k}(X) \\ ⋮ & ... & ⋮ \\ p_{t,1}(X) & … & p_{t,k}(X) \end{matrix} )

is a complete proof in F of SP (X), relative to Q(X), if

i) for every 1 ≤ i ≤ t and every x_{0} ∈ IR^{n},

[x_{0} ∈ F ∧ 0 ≤ p_{i,1}(x_{0}) ∧ ⋯ ∧ 0 ≤ p_{i,k}(x_{0})] ⟹ SP (x_{0}), and ii) for every x_{0} ∈ F satisfying SP (x_{0}) and Q(x_{0}) ≠ 0, there exists an i,

1 ≤ i ≤ t, such that

0 ≤ p_{i,1}(x_{0}) ∧ ⋯ ∧ 0 ≤ p_{i,k}(x_{0}).

Furthermore, we define Width(P) = k.

Rabin simply used the term complete proof of SP (X) to refer to those complete proofs P relative to the constant polynomial 1 ∈ IR[X_{1}, …, X_{n}].

Following the underlying ideas of [10], we can extend the concept of a complete proof of any closed semialgebraic subset W ⊆ IR^{n} in the following manner.

We can understand a complete proof P as a description, in matricial presentation, of a semialgebraic closed set W (P) ⊆ IR^{n}, as in the Finiteness Theorem:

W (P) = ⋃_{i=1}^{t}{x ∈ IR^{n} : p_{i,1}(x) ≥ 0, …, p_{i,k}(x) ≥ 0}.

We shall say that one of such matrices, P, is a complete proof of a semialgebraic subset W ⊆ IR^{n} relative to Q(X) when the following two conditions hold:

1. W (P) ⊆ W,

2. W \ {x ∈ IR^{n} : Q(x) ≠ 0} ⊆ W (P) \ {x ∈ IR^{n} : Q(x) ≠ 0}.

When F = IR^{n}, complete proofs relative to Q(X) of the syntactic expression SP (X) (as in Definition 3.1) are just complete proofs relative to Q(X) of the following subset W of IR^{n}:

W = {x ∈ IR^{n} : L_{1}(x) ≥ 0, …, L_{m}(x) ≥ 0}.

Again, we simply use the term complete proofs of a semialgebraic subset W ⊆ IR^{n} to refer to those complete proofs relative to the constant polynomial 1, i.e., P is a complete proof of W if and only if W = W (P).

In [10], Proposition 6, Rabin states that for all those non–trivial SP (X) (i.e., those with non–empty interior) the clause “relative to Q(X) ” can always be dropped. In our terminology this result can be translated as follows. Given a closed semialgebraic set W ⊆ IR^{n} whose interior points are dense in W, for every complete proof P of W relative to a non–zero Q(X), we have W (P) = W, i.e., P is in fact a complete proof of W and the clause “relative to Q(X)” can also be dropped. The proof follows the same arguments as Proposition 6 in [10].

In [10], Rabin claimed that “after certain sign changes” in an ACT solving the membership problem for a set {x ∈ IR^{n} : L_{1}(x) ≥ 0, …, L_{m}(x) ≥ 0}, one can obtain a complete proof of that set. This assertion is not clear for the authors. Take the semialgebraic subset {x ∈ IR : x ≥ 0} of IR and a polynomial f(X) ∈ IR[X] with only negative roots, say f(X) = X + 2. In Figure 1 below, we exhibit an ACT, T, solving the membership problem for {x ∈ IR : x ≥ 0} in IR.

x ∈ IR

↓

x · f^{2} ≥ 0?

Yes ↙↘_{No}

−(x + 1) · f^{2} ≥ 0? NO

Yes ↙↘_{No}

NO  YES

Figure 1: An algebraic decision tree that does not produce a complete proof.

Now, following the arguments of Rabin we should be able to obtain a complete proof P of {x ∈ IR : x ≥ 0} relative to Q(X) = X(X + 1)f^{2}(X), just making some sign changes, but preserving the family of polynomials occuring in this ACT. However, note that a complete proof consists only of non–strict “≥ 0” sign inequalities. Moreover, the semialgebraic set W (P) must be included in {x ∈ IR : x ≥ 0} (see condition (i) of Definition 3.1 above). Nevertheless, as P uses only the polynomials {Xf^{2}(X), (X + 1)f^{2}(X)} and sign conditions “≥ 0”, W (P) contains all negative roots of f(X), and it would never be posible to have the following inclusion:

W (P) ⊆ {x ∈ IR : x ≥ 0}.

This difficulty can be avoided if we include some new polynomials. For instance, consider including with the given family all the derivatives of these polynomials as in Thom’s Lemma (see [3], 2.5.4, and [7]), or consider adding a separating polynomial g(X), which is strictly negative on the roots of f(X) and positive on {x ∈ IR : x ≥ 0}. With this bigger collection we can find a complete proof of the given set.

This example shows that obtaining a complete proof, even if it is relative to some non–zero polynomial, is not simply a matter of sign changes but requires adding some new polynomials to the family occuring in the given ACT.

There are algorithmic procedures to get these new polynomials; this is the idea behind all the known proofs of the Finiteness Theorem (see [3], [7], and [11] for details). Given a description (a formula or an ACT) of a semialgebraic set W known to be closed, we can construct from the given description a separating family of polynomials using Thom’s Generalized Lemma as in [7] and [11]. This family is big enough to produce a complete proof of the set. However, the method is based on a cylindrical algebraic decomposition and it introduces all the partial derivatives of all polynomials occuring in the tree. This technique leads to complete proofs of width O(2^{h}) where h is the height of the tree.

There is another method based on Lojasiewicz’s inequality [3]. This method is very accurate for open semialgebraic sets, but not so good for closed ones. It introduces O(N2^{h−1}) new polynomials, where N is the number of NO leaves and h is the height of the tree. The complete proofs of closed sets obtained by this method also have width of order O(N2^{h−1}).

These features lead to enormous changes on the complexity and we cannot recuperate the height of the original tree as a linear function of the width of the obtained complete proof.

Nevertheless, we observe that the conclusion in [10] (i.e., that the width is a lower bound for the decisional complexity) remains true in the example of Figure 1 above: 1 ≤ h_{D}(T) = 2 (see Corollary 4.6 below). In order to show how this relation holds, we proceed by slightly changing the concept of width, without explicitly using the procedures to construct complete proofs.

Definition 3.2. Let F, W be two semialgebraic subsets of IR^{n}, W closed. The width of W in F, ω(W, F), is the minimum non–negative integer k ∈ IN such that there are an integer t ∈ IN and polynomials p_{i,j} ∈ IR[X_{1}, …, X_{n}] for 1 ≤ i ≤ k, 1 ≤ j ≤ t, verifying

W ∩ F = ⋃_{j=1}^{t}{x ∈ F : p_{1,j}(x) ≥ 0, …, p_{k,j}(x) ≥ 0}. (3.2.1)

By convention, we assume ω(IR^{n}, F) = 0 and ω(∅, F) = 0.

Similarly, if W′ is an open semialgebraic subset of IR^{n}, we define the concept of the width of W′ in F by replacing “≥ 0” by “> 0” in the equality (3.2.1) above.

For technical reasons, we will work in the realm of Nash function theory throughout the remainder of this section: a Nash function defined on an open semialgebraic subset U of IR^{n} is an analytic function f : U ⟶ IR which is algebraic over the polynomials (see [3], Ch. 8, for more detailed descriptions). We shall denote by N (U) the ring of Nash functions defined on U. A Nash set in U is the zero set of a finite collection of Nash functions in N (U). An important property of Nash functions is that sets given by a Boolean formula of sign conditions on Nash functions defined on U are also semialgebraic subsets of IR^{n}. Another important property we shall apply below is that N (U) is a factorial domain whenever U is an open ball (see [4] and [12]).

Analogously to Definition 3.2 above, for an open semialgebraic subset U of IR^{n} we define the Nash width of a closed (respectively open) semialgebraic subset W in F, ω^{N} (W, U), by replacing the polynomials p_{i,j} by Nash functions defined on U in equality (3.2.1) above.

Definition 3.3. Let W, W′, F be three semialgebraic subsets of IR^{n}. We say that W and W′ are generically equal in F if and only if dim(W △ W′) ∩ F < dim F, where W △ W′ is the symmetric difference of W and W′.

Remark 3.4.

i) Since the dimension of F as a semialgebraic set is the dimension of its Zariski closure, “W generically equal to W′ in F ” means, when the Zariski closure of F is irreducible, that there is a polynomial q ∈ IR[X_{1}, …, X_{n}], non–identically zero on F, such that

W ∩ F \ {x ∈ F : q(x) = 0} = W′ ∩ F \ {x ∈ F : q(x) = 0}.

ii) The relation ‘generically equal in F ’ is an equivalence relation.

iii) While complete proofs relative to a non–zero polynomial are in fact complete proofs in non–trivial cases, the property of being “generically equal” does not mean “equal” in these cases. Consider for instance the closed semialgebraic sets W_{1} = {(x, y) ∈ IR^{2} : x ≥ 0, y ≥ 0} and

W_{2} = {(x, y) ∈ IR^{2} : x ≥ 0, y ≥ 0} ∪ {(x, y) ∈ IR^{2} : −y^{2} ≥ 0}.

Both sets are generically equal in IR^{2} but are not equal.

iv) If U is an open connected semialgebraic subset of IR^{n}, a proper Nash set is a semialgebraic subset of dimension smaller than the dimension of U. Two semialgebraic subsets of IR^{n}, W and W′, are generically equal in U if and only if there is a Nash function h ∈ N (U), non–identically zero on U, such that W ∩ U \ {x ∈ U : h(x) = 0} = W′ ∩ U \ {x ∈ U : h(x) = 0}.

Our analysis will combine the widths of open and closed sets generically equal to the given one. This improves the performance of the width as a lower bound, but the computation of these generic widths requires a result stronger than the Main Theorem in [10].

Definition 3.5. Given two semialgebraic subsets W and F of IR^{n}, we define the generic width of W in F, ω_{gen}(W, F), as follows:

ω_{gen}(W, F) = min{ω(C, F) : C is closed, generically equal to W in F }
= min{ω(O, F) : O is open, generically equal to W in F }.

Analogously, the Nash generic width of W in an open set U, ω_{gen}^{N}(W, U), is defined by replacing “width” by “Nash width” in the equalities above. Obviously, as polynomials are also Nash functions, we have

ω_{gen}^{N}(W, U) ≤ ω_{gen}(W, U) ≤ n.

This last inequality is from Bröcker’s works [5] and [6].

Remark 3.6. Let us denote by ϖ(W, IR^{n}) the minimum of the widths of any complete proof of W relative to some polynomial Q(X). We observe that the parameters ω_{gen}(W, IR^{n}), ϖ(W, IR^{n}) (used in [10]), and ω(W, IR^{n}) (used in [8]) are different. First, we have the obvious relation

ω_{gen}(W, IR^{n}) ≤ ϖ(W, IR^{n}) ≤ ω(W, IR^{n}). (3.6.1)

Second, for semialgebraic subsets W ⊆ IR^{n} whose interior points are dense, we have the following equality:

ϖ(W, IR^{n}) = ω(W, IR^{n}).

However, both of them can be different from the generic width. Consider, for instance, examples of basic closed semialgebraic sets where the dimension falls beyond a smooth boundary. More concretely, consider the closed semialgebraic subset of IR^{2} described by the cubic with an isolated point:

W = {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} ≥ 0, x − 1/2 ≥ 0}
= {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} > 0}
∪ {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} = 0, x ≠ 0}.

It is clear that W is generically equal to the open semialgebraic set given by {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} > 0}, thus ω_{gen}(W, IR^{2}) = 1.

On the other hand, let P be a complete proof of W relative to a non–zero polynomial Q(X, Y) ∈ IR[X, Y] \ {0}. Since the interior points of W are dense, we have that W (P) = W and P is a complete proof of W. Now, we have the following inequality:

2 ≤ ω(W, IR^{2}).

Assume there are polynomials P_{1}(X, Y), …, P_{t}(X, Y) ∈ IR[X, Y] such that

W = {(x, y) ∈ IR^{2} : P_{1}(x, y) ≥ 0} ∪ ⋯ ∪ {(x, y) ∈ IR^{2} : P_{t}(x, y) ≥ 0}.

The set B = {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} = 0, x ≠ 0} is the set of regular points of the irreducible curve C = {(x, y) ∈ IR^{2} : x^{3} − x^{2} − y^{2} = 0}. Then, B is Zariski dense in C and the ideal of C is (X^{3} − X^{2} − Y^{2}). Now, observe that B is the boundary of W which implies that no P_{i}(X, Y) can be strictly positive on points of B. Since B ⊆ W, we must have the following inclusion:

B ⊆ {P_{1}(x, y) = 0} ∪ ⋯ ∪ {P_{t}(x, y) = 0} = {(x, y) ∈ IR^{2} : ∏_{i=1}^{t} P_{i}(x, y) = 0}.

We conclude that C ⊆ {(x, y) ∈ IR^{2} : ∏_{i=1}^{t} P_{i}(x, y) = 0} and X^{3} − X^{2} − Y^{2} divides ∏_{i=1}^{t} P_{i}(X, Y). Then, since X^{3} − X^{2} − Y^{2} is irreducible, X^{3} − X^{2} − Y^{2} divides P_{i}(X, Y) for some i, which finally implies P_{i}(0, 0) = 0, (0, 0) ∈ W, and we have arrived at a contradiction.

On the other hand, it is easy to find examples where the last two values in the inequality of (3.6.1) differ. For instance, consider the semialgebraic subset S of IR^{3} given by

S = {(x, y, z) ∈ IR^{3} : x ≥ 0, y ≥ 0, −z^{2} ≥ 0}.

Using Proposition 3.7 below, we can prove that ω(S, IR^{3}) = 2, but −1 ≥ 0 is a complete proof of S relative to Z ∈ IR[X, Y, Z].

Proposition 3.7. For every open semialgebraic neighborhood U ⊆ IR^{n} of the origin 0 ∈ IR^{n}, we have

ω_{gen}^{N}({x ∈ IR^{n} : x_{1} ≥ 0, …, x_{m} ≥ 0}, U) = m.

Proof. We show that for every open semialgebraic neighborhood U of the origin 0 ∈ IR^{n}, there are no Nash functions g, q_{i,j} ∈ N (U) \ {0} such that the following equality holds.

{x ∈ U : x_{1} ≥ 0, …, x_{m} ≥ 0} \ {x ∈ U : g(x) = 0}

= ⋃_{j=1}^{t}{x ∈ U : q_{1,j}(x) ≥ 0, …, q_{m−1,j}(x) ≥ 0} \ {x ∈ U : g(x) = 0} (3.7.1)

We may assume that U is an open ball centered at the origin and proceed by induction on m (≤ n). The case m = 1 follows from the observation that {x ∈ U : x_{1} < 0} is a non–empty open semialgebraic set, hence the semialgebraic set {x ∈ U : x_{1} ≥ 0} can be generically equal neither to IR^{n} nor to the empty set.

Suppose that the induction hypothesis is true for m − 1 and suppose that there are Nash functions g, q_{i,j} ∈ N (U) \ {0} such that the equality (3.7.1) holds. The strategy we follow in this inductive step will be to get from the equality (3.7.1) a description of {x_{1} ≥ 0, …, x_{m−1} ≥ 0} as a subset of IR^{n−1} having Nash generic width at most m − 2. The rest of the proof shows the procedure that generates this description.

Note that if f, h ∈ N (U) \ {0}, the semialgebraic set {x ∈ U : q^{2} · h(x) ≥ 0} is generically equal to the semialgebraic set {x ∈ U : h(x) ≥ 0}. Then, without loss of generality, we can assume that the factorizations in N (U) of the Nash functions g and q_{i,j} occuring in the equality (3.7.1) are square free. Now, for each pair of indices (i, j) there is an r_{i,j} ∈ {0, 1} such that q_{i,j} = x_{m}^{r_{i,j}} · q′_{i,j} and q′_{i,j} is not in the ideal (x_{m})N (U). In the same way, there is an r ∈ {0, 1} such that g = x_{m}^{r} · h and h ∉ (x_{m})N (U). Let B be the subset of U given by

B = ⋃_{j=1}^{t}{x ∈ U : x_{m} ≥ 0, q′_{1,j}(x) ≥ 0, …, q′_{m−1,j}(x) ≥ 0}

and let π be the Nash function π = h ∏_{i,j} q′_{i,j}. For simplicity, let us write Δ_{m} = {x ∈ U : x_{1} ≥ 0, …, x_{m} ≥ 0}.

Claim. Under the above notation, the following equality holds:

Δ_{m} \ {x ∈ U : π(x) = 0} = B \ {x ∈ U : π(x) = 0}.

Proof. For the first inclusion, let us consider a point α in the semialgebraic set Δ_{m} \ {x ∈ U : π(x) = 0}. Note that it is the limit of a sequence of points {α_{k} = (x_{k1}, …, x_{kn})}_{k∈IN} contained in Δ_{m} \ {x ∈ U : π(x) = 0} such that for every k ∈ IN, x_{km} is strictly positive. Then, g(α_{k}) = x_{km}^{r} · h(α_{k}) ≠ 0 and from the equality (3.7.1) we conclude that

{α_{k}}_{k∈IN} ⊆ ⋃_{j=1}^{t}{x ∈ U : q_{1,j}(x) ≥ 0, …, q_{m−1,j}(x) ≥ 0} \ {x ∈ U : g(x) = 0}.

Since x_{km} > 0, if α_{k} ∈ {x ∈ U : q_{1,j}(x) ≥ 0, …, q_{m−1,j}(x) ≥ 0}, we conclude that q′_{i,j}(α_{k}) ≥ 0 for 1 ≤ i ≤ m − 1. This implies that

α_{k} ∈ {x ∈ U : x_{m} ≥ 0, q′_{1,j}(x) ≥ 0, …, q′_{m−1,j}(x) ≥ 0}.

Hence, {α_{k}}_{k∈IN} ⊆ B and, taking the limit of the sequence, the inclusion follows.

As for the converse, assume an element α = (x_{1}, …, x_{m}, x_{m+1}, …, x_{n}) in B \ {π(x) = 0} to be given. There must be a j, 1 ≤ j ≤ t, such that

α ∈ {x ∈ U : x_{m} ≥ 0, q′_{1,j}(x) ≥ 0, …, q′_{m−1,j}(x) ≥ 0} \ {x ∈ U : π(x) = 0}

and α is the limit of a sequence of points {α_{k} = (x_{k1}, …, x_{kn})}_{k∈IN} contained in the open set

{x ∈ U : x_{m} > 0, q′_{1,j}(x) > 0, …, q′_{m−1,j}(x) > 0} \ {x ∈ U : π(x) = 0}.

Then, q_{i,j}(α_{k}) = x_{mk}^{r_{i,j}} · q′_{i,j}(α_{k}) ≥ 0 and

{α_{k}}_{k∈IN} ⊆ ⋃_{j=1}^{t}{x ∈ U : q_{1,j}(x) ≥ 0, …, q_{m−1,j}(x) ≥ 0}.

Since this last set is closed and g(α_{k}) = x_{km}^{r} · h(α_{k}) ≠ 0, then

α ∈ ⋃_{j=1}^{t}{x ∈ U : q_{1,j}(x) ≥ 0, …, q_{m−1,j}(x) ≥ 0} \ {x ∈ U : g(x) = 0}

which gives the inclusion. □

Now, for every 1 ≤ j ≤ t, reordering the indices i if necessary, define s(j) such that r_{i,j} = 0 if and only if i ≤ s(j). We have the following cases.

1. If s(j) = m − 1 then the set

{x ∈ U : x_{m} ≥ 0, q′_{1,j}(x) ≥ 0, …, q′_{m−1,j}(x) ≥ 0} \ {π(x) = 0}

has no common point with the hyperplane {x ∈ IR^{n} : x_{m} = 0} since otherwise, by continuity, there would be a point x in Δ_{m} with m–coordinate x_{m} < 0.

2. If s(j) = m−2 the condition q′_{m−1,j} ≥ 0 always holds over the set of points {x ∈ U : x_{m} = 0, q′_{1,j}(x) ≥ 0, …, q′_{m−2,j}(x) ≥ 0} \ {x ∈ U : π(x) = 0} since otherwise, by continuity, there would be a point x ∈ {x ∈ U : q_{1,j}(x) > 0, …, q_{m−2,j}(x) > 0, q′_{m−1,j}(x) < 0} \ {x ∈ U : π(x) = 0} with m–coordinate x_{m} < 0. Since q_{m−1,j}(x) = x_{m} · q′_{m−1,j}(x) > 0 and g(x) = x_{m}^{r} · h(x) ≠ 0, by equality (3.7.1) this point would be in Δ_{m}.

3. Finally, if 0 ≤ s(j) < m − 2, let us define the following Nash functions

Q_{i,j} = \{ \begin{matrix}q′_{i,j}, & if 1 ≤ i ≤ s(j) \\ q′_{s(j)+1,j}q′_{i,j}, & if s(j) + 2 ≤ i ≤ m − 1. \end{matrix}

Then, we have the following set equality:

{x ∈ U : x_{m} = 0, q′_{1,j}(x) ≥ 0, …, q′_{m−1,j}(x) ≥ 0, π(x) ≠ 0} =
{x ∈ U : x_{m} = 0, q′_{1,j}(x) ≥ 0, …, q′_{s(j),j}(x) ≥ 0,
Q_{s(j)+2,j}(x) ≥ 0, …, Q_{m−1,j}(x) ≥ 0, π(x) ≠ 0}.

Otherwise, there would be a point x ∈ U satisfying the system of equations and inequalities

\begin{matrix}x_{m} = 0, q′_{1,j}(x) ≥ 0, …, q′_{s(j),j}(x) ≥ 0, \\ q′_{s(j)+1,j} · q′_{s(j)+2,j}(x) ≥ 0, …, q′_{s(j)+1,j} · q′_{m−1,j}(x) ≥ 0, π(x) ≠ 0 \end{matrix}

so that q′_{i,j}(x) < 0 for some i, s(j) + 1 ≤ i ≤ m − 1. This would imply that q′_{i,j}(x) < 0 for every s(j) + 1 ≤ i ≤ m − 1. Now, by continuity, one can choose a point y satisfying the following system:

\begin{matrix}y_{m} < 0, q′_{1,j}(y) > 0, …, q′_{s(j),j}(y) > 0, \\ q′_{s(j)+1,j}(y) < 0, …, q′_{m−1,j}(y) < 0, π(y) ≠ 0. \end{matrix}

Now, observe that we have q_{i,j}(y) = y_{m} · q′_{i,j}(y) > 0 for s(j) + 1 ≤ i ≤ m − 1. On the other hand, for 1 ≤ i ≤ s(j), q′_{i,j}(y) = q_{i,j}(y) > 0 and g(y) = y_{m}^{r} · h(y) ≠ 0. Finally, by equality (3.7.1), this point y would be in Δ_{m} and we would arrive to a contradiction since y_{m} < 0.

Identifying IR^{n−1} with the linear hyperplane {x ∈ IR^{n} : x_{m} = 0}, it follows from 1 to 3 above that the Nash generic width of Δ_{m−1} in IR^{n−1} is at most m − 2, which contradicts the induction hypothesis; thus, the proof of Proposition 3.7 is complete. □

From the classical literature, we define Nash m–corner points (see for instance [13], p. 15) in semialgebraic sets W ⊆ IR^{n} as those points α ∈ W such that there is a Nash diffeomorphism of a neighborhood U of α onto a neighborhood U′ of the origin, such that under this diffeomorphism W ∩ U looks like {x_{1} ≥ 0, …, x_{m} ≥ 0}.

Theorem 3.8. For a semialgebraic subset W ⊆ IR^{n}, if there is an m–corner point α ∈ W, then m ≤ ω_{gen}(W, IR^{n}).

The proof follows in a straightforward manner from Proposition 3.7. The following corollaries deal with more concrete instances where the hypothesis of Theorem 3.8 holds.

Corollary 3.9. Let p_{1}(X), …, p_{m}(X) ∈ IR[X_{1}, …, X_{n}] be a collection of polynomials, and let α be a point in IR^{n} such that p_{1}(α) = 0, …, p_{m}(α) = 0 and the rank of the Jacobian matrix defined by p_{1}(X), …, p_{m}(X) at α is m, i.e., rank J(p_{1}, …, p_{m})_{α} = m. Then,

ω_{gen}^{N}({x ∈ IR^{n} : p_{1}(x) ≥ 0, …, p_{m}(x) ≥ 0}, U) = m

for every open neighborhood U of α in IR^{n}.

Proof. The hypothesis means that {p_{1}, …, p_{m}} is a subset of a regular system of parameters near α. Thus, using the local (Nash) coordinates of the Implicit Function Theorem for Nash functions (see [3]) we can identify W, near α, with an m–corner, and the Corollary is then a consequence of Theorem 3.8. □

Corollary 3.10. Let f_{1}, …, f_{m} ∈ IR[X_{1}, …, X_{n}] be a collection of polynomials for which there is a point α ∈ IR^{n} and a non–negative integer k, 1 ≤ k ≤ m, such that

f_{1}(α) = … = f_{k}(α) = 0, f_{k+1}(α) > 0, …, f_{m}(α) > 0

and the rank of the jacobian matrix verifies rank J(f_{1}, …, f_{k})_{α} = k. Then, the following inequality holds:

k ≤ ω_{gen}({x ∈ IR^{n} : f_{1}(x) ≥ 0, …, f_{m}(x) ≥ 0}, IR^{n}).

Proof. First observe that the point α is a k–corner point in the semialgebraic set {f_{1} ≥ 0, …, f_{m} ≥ 0}. Consider a semialgebraic open neighborhood U of α contained in the open set {x ∈ IR^{n} : f_{k+1}(x) > 0, …, f_{m}(x) > 0}. Now, observe that the generic width of a set S in U is that of S ∩U in U. Since the following set equality holds:

{x ∈ IR^{n} : f_{1}(x) ≥ 0, …, f_{m}(x) ≥ 0} ∩ U
= {x ∈ IR^{n} : f_{1}(x) ≥ 0, …, f_{k}(x) ≥ 0} ∩ U,

by Corollary 3.9, we conclude that

ω_{gen}({x ∈ IR^{n} : f_{1}(x) ≥ 0, …, f_{m}(x) ≥ 0}, U) = k.

The statement follows since for every semialgebraic set S ⊆ IR^{n} and every open semialgebraic subset U of IR^{n} we have ω_{gen}(S, U) is at most ω_{gen}(S, IR^{n}). □

Corollary 3.11. Let f_{1}, …, f_{d} ∈ IR[X_{1}, …, X_{n}] be a collection of polynomials such that the ideal I = (f_{1}, …, f_{d}) is real and of height d. Then, the following inequality holds:

d ≤ ω_{gen}({f_{1} ≥ 0, …, f_{d} ≥ 0}, IR^{n}).

The proof follows from the observation that I is a real complete intersection and there must exist a simple point α ∈ IR^{n} of the algebraic set described by the equations {f_{1} = 0, …, f_{d} = 0}. This point is a d–corner point of {f_{1} ≥ 0, …, f_{d} ≥ 0} and Theorem 3.8 applies.

4. Applications of the Generic Width

We have mentioned previously that the main Theorem in [10] can not be immediately applied to obtain lower bounds of decisional complexity as done by Rabin. Actually, Theorem 3.8 and its corollaries are very useful in this sense because of the following Proposition.

Proposition 4.1. Let W be a semialgebraic subset of IR^{n}. Then,

ω_{gen}^{N}(W, IR^{n}) ≤ ω_{gen}(W, IR^{n}) ≤ C_{D}(W).

Proof. Let T be an ACT solving the membership problem for W. Let Γ_{1}, …, Γ_{r} be the oriented paths in T from the root to some leaf, ending at an affirmative label (i.e., paths followed by inputs belonging to W).

We have W = W (T) = ⋃_{i=1}^{r} W (Γ_{i}), where W (Γ_{i}) is the semialgebraic set given by the sequence of polynomial sign conditions occuring in Γ_{i}. After a renumbering, let r′ ≤ r be such that there is no equation among the sign conditions describing W (Γ_{i}) if and only if i ≤ r′. Let W′ be the semialgebraic set given as W′ = ⋃_{j=1}^{r′} W (Γ_{j}). Clearly, W′ is generically equal to W in IR^{n}.

Let W′′(Γ_{j}) be the closed semialgebraic set obtained after replacing the strict sign conditions occuring in Γ_{j}, “> 0”, by the relaxed sign conditions “≥ 0”. Then, let W′′ be the union of those W′′(Γ_{j}). The proof is complete once one observes that the following conditions hold:

i) W′′ is generically equal to W in IR^{n} and thus ω_{gen}(W, IR^{n}) ≤ ω(W′′, IR^{n}),

ii) ω(W′′, IR^{n}) ≤ h_{D}(T). □

4.1. Finite polynomial optimization. Problems 1.1 to 1.3 of the Introduction are particular cases of finite polynomial maximization and minimization. Now, we observe that our analyses in Section 3 and Proposition 4.1 provide linear lower bounds for all of them regardless of the fixed, non–constant polynomial f ∈ IR[X_{1}, …, X_{n}].

Corollary 4.2. Both problems, finite maximization and finite minimization, have complexity at least Ω(N) = Ω(#(F)).

Proof. We do the proof only for maximization. First of all, note that lower bounds for the complexity of maximization can be immediately obtained from lower bounds of the following problem.

Problem 4.3. Decide whether x_{1} verifies f(x_{1}) = max f(F).

This is the membership problem for a semialgebraic subset of M ⊆ IR^{nN}. We are going to describe this subset. Let us denote by (X_{1}, …, X_{nN}) the coordinates of the elements of IR^{nN}. Let us also define the set of polynomials:

g_{i}(X_{1}, …, X_{nN}) = f(X_{1}, …, X_{n}) − f(X_{in+1}, …, X_{(i+1)n})

where 1 ≤ i ≤ N − 1. Clearly, we have

M = {x ∈ IR^{nN} : g_{1}(x) ≥ 0, …, g_{N−1}(x) ≥ 0}.

As f is a non–constant polynomial, the polynomial g(X_{1}, …, X_{n}, Y_{1}, …, Y_{n}) = f(X_{1}, …, X_{n}) − f(Y_{1}, …, Y_{n}) changes sign in IR^{2n}. Now, applying the Change of Sign Criterion for real hypersurfaces (see [3], 4.5.1), we know there is a point (α, β) ∈ IR^{2n} such that g(α, β) = 0 and \frac{∂g}{∂X_{j}} (α, β) ≠ 0 or \frac{∂g}{∂Y_{j}} (α, β) ≠ 0 for some j, 1 ≤ j ≤ n. Finally, consider the point A = (α, β, …, β) ∈ IR^{nN} verifying g_{1}(A) = ⋯ = g_{N−1}(A) = 0 and rankJ(g_{1}, …, g_{N−1})_{A} = N −1. Then, N − 1 ≤ ω_{gen}(M, IR^{nN}), which is smaller than the decisional complexity of M, as wanted. □

4.2. Direct oriented–convex hull. As was observed in the Introduction, this problem was motivated by the work of J. Jaromczyk [8], who applied the width directly to get lower bounds for the DO–CH problem. The limitations of this approach are those of [10], which we have discussed in Section 3. Now, we provide lower bounds for the problem using Theorem 3.8 and, specifically, Corollary 3.10.

Corollary 4.4. The problem DO–CH has complexity at least Ω(N).

Proof. Given z_{i} = (x_{i}, y_{i}), z_{j} = (x_{j}, y_{j}), z_{k} = (x_{k}, y_{k}), define

det(z_{i}, z_{k}, z_{j}) = x_{k}.(y_{i} − y_{j}) + y_{k}.(x_{j} − x_{i}) + y_{j}.x_{i} − y_{i}.x_{j}.

The decisional problem DO–CH is the membership problem for a semialgebraic subset of IR^{2.N} given by

D = {(z_{1}, …, z_{N}) ∈ IR^{2.N} : det(z_{1}, z_{2}, z_{3}) ≥ 0, …,

det(z_{N−2}, z_{N−1}, z_{N}) ≥ 0, det(z_{N−1}, z_{N}, z_{1}) ≥ 0, det(z_{N}, z_{1}, z_{2} ≥ 0)}.

From Corollary 3.10, it is enough to observe that the point A ∈ IR^{2·N} given by

A = ((1, 0), (2, 0), …, (N − 1, 0), (N, −1))

verifies the following equations:

det((i, 0), (i + 1, 0), (i + 2, 0)) = 0 for 1 ≤ i ≤ N − 3
det((N − 2, 0), (N − 1, 0), (N, −1)) > 0
det((N − 1, 0), (N, −1), (1, 0)) > 0
det((N, 0), (1, 0), (2, 0)) > 0
rankJ(det(z_{1}, z_{2}, z_{3}), …, det(z_{N−3}, z_{N−2}, z_{N−1}))_{A} = N − 3.

Thus, we conclude that N −3 ≤ ω_{gen}(D, IR^{2N}) ≤ C_{D}(D), which is smaller than the complexity of DO–CH. □

4.3. Finite subset and finite selection in real complete intersections. These problems arise naturally in computational geometry. We have some fixed subset A ⊆ IR^{n} and a property R on points of IR^{n}. Then, we consider the following questions.

Finite subset decision.Given a finite set F = {x_{1}, …, x_{N}} ⊆ IR^{n}, decide whether F ⊆ A. Finite selection.Given a finite set F = {x_{1}, …, x_{N}} ⊆ IR^{n}, find a point x_{i} ∈ F such that x_{i} verifies property R.

The model of algebraic computation trees can only be applied when A is a semialgebraic set or R is a property described by a first order formula over the reals. Our lower bound method applies, for instance, under the following conditions:

Assume {f_{1}, …, f_{d}} ⊆ IR[X_{1}, …, X_{n}] to be a collection of polynomials such that the ideal I = (f_{1}, …, f_{d}) is real of height d. Let us also assume for A and R the following hypotheses:

A = {x ∈ IR^{n} : f_{1}(x) ≥ 0, …, f_{d}(x) ≥ 0}
R ↔ [f_{1}(X_{1}, …, X_{n}) ≥ 0] ∨ ⋯ ∨ [f_{d}(X_{1}, …, X_{n}) ≥ 0].

Observe that in the case d = 1, the above hypotheses simply mean that f_{1} changes its sign in IR^{n} or equivalently that R is not the trivial property [1 ≥ 0] (see [3], 4.5.1, for more detailed descriptions). Now we want to show the following.

Corollary 4.5. Under the above hypotheses, finite subset decision and finite selection have complexity in Ω(#(F)) = Ω(N).

Proof. First of all, observe that the ideal I = (f_{1}, …, f_{d}) is a real complete intersection ideal and there must be a point α ∈ IR^{n} such that

f_{1}(α) = 0, …, f_{d}(α) = 0, and rankJ(f_{1}, …, f_{d})_{α} = d.

On the other hand, to get lower bounds for finite subset decision, we note that it can be understood as the membership problem for a semialgebraic subset SD ⊆ IR^{nN}. As above let us denote by (X_{1}, …, X_{nN}) the coordinates of the elements of IR^{nN} and define the polynomials

g_{i,j}(X_{1}, …, X_{nN}) = f_{i}(X_{jn+1}, …, X_{(j+1)n}). (4.4.2)

We have the following equality:

SD = {(x_{1}, …, x_{nN}) ∈ IR^{nN} :
g_{i,j}(x_{1}, …, x_{nN}) ≥ 0 for 1 ≤ i ≤ d and 1 ≤ j ≤ N}.

Finally, the point A = (α, …, α) ∈ IR^{nN} verifies the hypothesis of Corollary 3.9 and dN ≤ ω_{gen}(SD, IR^{nN}), which is smaller than the complexity of finite subset decision.

For finite selection, the hypothesis implies that the property R above is non–trivial, so we have a non–empty semialgebraic subset of S ⊆ IR^{nN} given by S = {(x_{1}, …, x_{N}) ∈ IR^{nN} : no x_{i} verifies property R}.

Lower bounds for finite selection can be immediately obtained from lower bounds from the membership problem for S. However, using the notation of (4.4.2), we observe that

S = {(x_{1}, …, x_{nN}) ∈ IR^{nN} :
g_{i,j}(x_{1}, …, x_{n.N}) < 0 for 1 ≤ i ≤ d and 1 ≤ j ≤ N}.

The point B = (α, …, α) ∈ IR^{nN} verifies the hypothesis of Corollary 3.9. Hence, dN ≤ ω_{gen}(S, IR^{nN}) ≤ C_{D}(S), which is a lower bound for the complexity of finite selection. □

4.4. Existence of real root condition. Here we consider the size of formulae that describe the existence of real roots for any polynomial of a fixed degree d. Any of these formulae describes a semialgebraic subset of IR^{d+1}. Our purpose now will be to prove the following Corollary.

Corollary 4.6. Any quantifier free first order formula equivalent to

∃z ∈ IR X_{d}z^{d} + X_{d−1}z^{d−1} + ⋯ + X_{0} = 0 (4.5.1)

involves at least \frac{d}{2} polynomials.

Proof. Consider the polynomial

P (T_{1}, …, T_{\frac{d}{2}} , X) = (X^{2} + T_{1}) ⋯ (X^{2} + T_{\frac{d}{2}} ).

From any formula Φ(X_{d}, …, X_{0}) equivalent to (4.5.1), we obtain by substitution a formula φ(T_{1}, …, T_{\frac{d}{2}} ) describing the semialgebraic set

E =\{(t_{1}, …, t_{\frac{d}{2}} ) ∈ IR^{\frac{d}{2}} : ∃x ∈ IR such that P (t_{1}, …, t_{\frac{d}{2}} , x) = 0\}
=\{t_{1} ≤ 0\} ∪ … ∪ \{t_{\frac{d}{2}} ≤ 0\}.

The number of polynomials involved in φ is bigger than the decisional complexity of E. Finally,

C_{D}(E, IR^{\frac{d}{2}} ) = C_{D}(E^{c}, IR^{\frac{d}{2}} ) ≥ ω_{gen}(\{t_{1} > 0, …, t_{\frac{d}{2}} > 0\}, IR^{\frac{d}{2}} ) = \frac{d}{2}.

□

4.5. Rabin’s Theorem Revisited. Finally, we remark that Theorem 3.8 and Proposition 4.1 above yield as a consequence Rabin’s claim in a particular case: one may use the minimum width of complete proofs as a lower bound under the strong restriction of linear functions and sign independence.

As in [10], a collection p_{1}, …, p_{m} : IR^{n} ⟶ IR of polynomial mappings is said to be sign independent in an open semialgebraic set U ⊆ IR^{n} if, for every sequence of sign conditions μ_{1}, …, μ_{m} ∈ {<, =, >}, the set {x ∈ U : p_{1}(x)μ_{1}0, …, p_{m}(x)μ_{m}0} is non–empty.

Corollary 4.7. Under the conventions of Section 3 and Definition 3.1, let SP (X) be the formula L_{1}(X) ≥ 0 ∧ ⋯ ∧ L_{m}(X) ≥ 0 and W the convex set W = {x ∈ IR^{n} : L_{1}(x) ≥ 0, …, L_{m}(x) ≥ 0}. Then,

i) for every complete proof P of SP (X) relative to some non–zero polynomial Q(X), ω_{gen}(W, IR^{n}) ≤ Width(P),

ii) if, in addition to the above hypothesis, L_{1}(X), …, L_{m}(X) are sign independent in IR^{n}, then we have

ω_{gen}(W, IR^{n}) = ϖ(W, IR^{n}) = m = C_{D}(W).

Proof. The first statement is clear from our discussions in Section 3. As for the second statement, observe that given affine linear functions L_{1}, …, L_{m} : IR^{n} ⟶ IR, the L_{i}’s are sign independent if and only if the rank of the Jacobian defined by {L_{1}, …, L_{m}} at some point α ∈ IR^{n}, verifying L_{1}(α) = 0, …, L_{m}(α) = 0, is m. Then, Theorem 3.8 and Proposition 4.1 allow us to conclude that ω_{gen}(W, IR^{n}) = ω(W, IR^{n}) = m = C_{D}(W).

On the other hand, Theorem 3.8 and Remark 3.6 yield the main Theorem in [10], i.e., m = ω_{gen}(W, IR^{n}) ≤ ϖ(W, IR^{n}) ≤ m = C_{D}(W), which completes the proof. □

Remark 4.8. The statement of Corollary 4.6 does not hold under the weaker hypothesis of sign independence on the polynomials p_{1}, …, p_{m} if they are not linear forms: consider in IR^{2} the linear functions L_{1} = X_{1}, L_{2} = X_{2}, L_{3} = X_{2} − X_{1} and L_{4} = X_{1} + X_{2} and the polynomial mappings p_{1} = L_{1}L_{2} and p_{2} = L_{3}L_{4}. Clearly, the polynomial mappings p_{1} and p_{2} are sign independent in any open semialgebraic neighborhood U ⊆ IR^{2} of the origin 0 ∈ IR^{2}, but {p_{1} ≥ 0, p_{2} ≥ 0} = {L_{2}L_{3} ≥ 0}.

On the other hand, sign independence for conditions in {>, <} is a necessary condition for Corollary 4.6 to hold. Actually, if for some sequence μ_{1}, …, μ_{m} ∈ {<, >} the set {x ∈ U : p_{1}(x)μ_{1}0, ldots, p_{m}(x)μ_{m}0} = ∅, then w_{gen}({x ∈ U : p_{1}(x)μ_{1}0, …, p_{m}(x)μ_{m}0}, U) ≤ m − 1. In order to see this, let us suppose that μ_{1} = ⋯ = μ_{l} = “>” and μ_{l+1} = ⋯ = μ_{m} = “<”; then, the following equality holds:

{x ∈ U : p_{1}(x) ≥ 0, …, p_{m}(x) ≥ 0} \ {x ∈ U : Π_{i=1}^{m}p_{i}(x) = 0} =
{x ∈ U : p_{1}(x) ≥ 0, …, p_{l}(x) ≥ 0, p_{l+1}.p_{l+2}(x) ≥ 0,
…, p_{l+1}.p_{m}(x) ≥ 0} \ {x ∈ U : Π_{i=1}^{m}p_{i}(x) = 0}.

Rabin’s Width  25

Acknowledgements

The authors are partially supported by DGICyT PB 92/0498 and “POSSO”, ESPRIT–BRA 6846.

References

[1] M. Ben-Or, Lower bounds for algebraic computation trees. In Proc. Fifteenth Ann. ACM Symp. Theor. Comput., 1983, 80–86.

[2] R. Benedetti and J. J. Risler, Real algebraic and semialgebraic geometry. Hermann, Paris, 1990.

[3] J. Bochnak, M. Coste and M.-F. Roy, Géométrie algébrique réelle. Ergebnisse der Math., 3.Folge, Band 12, Springer–Verlag, Berlin, Heidelberg, New York, 1987.

[4] J. Bochnak, Sur la factorialité des anneaux de fonctions de Nash. Comment. Math. Helv. 52 (1977), 211–218.

[5] L. Bröcker, Minimale Erzeugung von Positivbereich. Geom. Dedicata 16 (1984), 335–350.

[6] L. Bröcker, Spaces of orderings and semialgebraic sets. In Quadratic and Hermitian Forms, CMS Conf. Proc. 4, Providence, Amer. Math. Soc. (1984), 231–248.

[7] M. Coste, Ensembles Semi–algébriques. In Géométrie Algébrique Réelle et Formes Quadratiques, J. L. Colliot-Thélene, M. Coste, L. Mahé, and M.-F. Roy, eds., Lecture Notes in Mathematics 959, Springer–Verlag, Berlin, Heidelberg, New York, 1982, 109–139.

[8] J. Jaromczyk, An extension of Rabin’s complete proof concept. In Math. Found. of Comp. Sci. 1981, J. Gruska and M. Chytill, eds., Lecture Notes in Computer Science 118, Springer–Verlag, Berlin, Heidelberg, New York, 1981, 321–326.

[9] J. L. Montaña, L. M. Pardo and T. Recio, The non–scalar model of complexity in computational geometry. In Proc. MEGA’90. C. Traverso and T. Mora, eds., Progress in Mathematics 94, Birkhäuser Boston, 1991, 347–362.

[10] M. O. Rabin, Proving simultaneous positivity of linear forms. J. Comput. System Sci. 6 (1972), 639–650.

[11] T. Recio, Una Descomposición de un Conjunto Semialgebraico. In Actas del V Congreso de la Agrupación de Matemáticos de Expresión Latina, CSIC, Publicaciones del Instituto Jorge Juan, Madrid, 1978, 217–221.

[12] J. J. Risler, Sur l’anneau des fonctions de Nash globales. Ann. Scien. Ecole Norm. Sup., 4éme série, 8 (1975), 365–378.

26  Montaña, Pardo & Recio

[13] J.T. Schwartz, Differential Geometry and Topology. Notes on Mathematics and its Applications, Gordon and Breach, 1968.

[14] V. Strassen, Algebraic Complexity Theory. In Handbook of Theoretical Computer Science, J. van Leeuwen, ed., Elsevier, Amsterdam, 1990, 633–673.

[15] F.F. Yao, Computational Geometry. In Handbook of Theoretical Computer Science, J. van Leeuwen, ed., Elsevier, Amsterdam, 1990, 343–391.

Manuscript received 2 January 1992

Jose L. Montaña Dept. de Matemáticas, Est. y Comp. Facultad de Ciencias Universidad de Cantabria Santander, 39071 SPAIN

montana1@ccucvx.unican.es

Luis M. Pardo

Dept. de Matemáticas, Est. y Comp. Facultad de Ciencias Universidad de Cantabria Santander, 39071 SPAIN

                                       pardo@ccucvx.unican.es

Tomas Recio Dept. de Matemáticas, Est. y Comp. Facultad de Ciencias Universidad de Cantabria Santander, 39071 SPAIN

recio@ccucvx.unican.es