Introduction

A problem of testing membership to a semialgebraic set Σ was considered by many authors (see, e.g., [B 83], [B 92], [BKL 92], [BL 92], [BLY 92], [MH 85], [GKV 94], [Y 92], [Y 93], [YR 80] and the references there). We consider a problem of testing membership to a convex polyhedron P in n-dimensional space R^{n}. Let P have N facets of all the dimensions. In [MH 85] it was shown, in particular, that for this problem O(log N)n^{O(1)} upper bound is valid for the depth of linear decision trees, in [YR 80] a lower bound Ω(log N) was obtained. A similar question was open for algebraic decision trees. In [GKV 94] we proved a lower bound Ω(log N) for the depth of algebraic decision trees testing membership to P, provided that N > (dn)^{Ω(n^{2})}. In the present paper we weaken the latter assumption to N > (dn)^{Ω(n)}. In this new form the bound looks plausible to be applicable to polyhedra given by 2^{O(n)} linear constraints (like in “knapsack” problem).

In [GV 94] the lower bound Ω(\sqrt{log N}) was proved for the Pfaffian computation tree model. This model uses at gates Pfaffian functions, the latter include all major elementary transcendental and algebraic functions.

Several topological methods were introduced for obtaining lower bounds for the complexity of testing membership to Σ by linear decision trees, algebraic decision trees, algebraic computation trees (the definitions one can find in, e.g., [B 83]).

In [B 83] a lower bound Ω(log C) was proved for the most powerful among the considered in this area computational models, namely algebraic computation trees, where C is the number of connected components of Σ or of the complement of Σ. After that, in [BLY 92], a lower bound Ω(log χ) for linear decision trees was proved, where χ is Euler characteristic of Σ, in [Y 92] this lower bound was extended to algebraic computation trees. A stronger lower bound Ω(log B) was proved later in [BL 92], [B 92] for linear decision trees, where B is the sum of Betti numbers of Σ (obviously, C, χ ≤ B). In the recent paper [Y 94] the latter lower bound was extended to the algebraic decision trees.

Unfortunately, all the mentioned topological tools fail when Σ is a convex polyhedron, because B = 1 in this situation. The same is true for the method developed in [BLY 92] for linear decision trees, based on the minimal number of convex polyhedra onto which Σ can be partitioned.

To handle the case of a convex polyhedron, we introduce in Sections 1, 3 another approach which differs drastically from [GKV 94]. Let W be a semialgebraic set accepted by a branch of an algebraic decision tree. In Section 3 we make an “infinitesimal perturbation” of W which transforms this set into a smooth hypersurface. Then we describe the semialgebraic subset of all the points of the hypersurface in which all its principal curvatures are “infinitely large” (the set K_{0} in Section 3). We also construct a more general set K_{i} (for each 0 ≤ i ≤ n − 1) of the points with infinitely large curvatures in the shifts of a fixed (n−i)-dimensional plane. Section 1 provides a short system of inequalities for determining K_{i}. It is done by developing an explicit symbolic calculis for principal curvatures.

In Section 2 we introduce some necessary notions concerning infinitesimals and apply them to define the “standard part” K_{i} = st(K_{i}) ⊂ R^{n}. We show (Corollary to Lemma 3 in Section 3) that to obtain the required bound for the number of i-facets P_{i} of P such that dim(P_{i} ∩ W) = i it is sufficient to estimate the number of facets P_{i} with dim(P_{i} ∩ K_{i}) = i. In Section 4 we reduce the latter bound to an estimate of the number of local maxima of a generic linear function L on K_{i} with the help of a Whitney stratification of K_{i}. To estimate these local maxima we introduce in Section 5 another infinitesimal perturbation of K_{i} and obtain a new smooth hypersurface. At this point a difficulty arises due to the fact that K_{i} (and therefore, the related smooth hypersurface) are defined by systems of inequalities involving algebraic functions, rather than polynomials, because in the expressions for curvatures (in Section 1) square roots of polynomials appear. We represent the set of local maxima of L on the smooth hypersurface by a formula of the first-order theory of real closed fields with merely existential quantifiers and quantifier-free part Φ. We estimate in Section 5 (invoking [Mi 64] in a usual way) the number of the connected components of the semialgebraic set defined by Φ.

In Section 6 we describe a particular class of polyhedra (dual to cyclic polyhedra [MS 71]) having large numbers of facets, for which Theorem 1 provides a nontrivial lower bound.

Now let us formulate precisely the main result. We consider algebraic decision trees of a fixed degree d (see, e.g., [B 83], [Y 93]). Suppose that such a tree T, of the depth k, tests a membership to a convex polyhedron P ⊂ R^{n}. Denote by N the number of facets of P of all dimensions from zero to n − 1. In this paper we agree that a facet is “open”, i.e., does not contain facets of smaller dimensions.

Theorem 1.

k ≥ Ω(log N),

provided that N ≥ (dn)^{cn} for a suitable c > 0.

Let us fix a branch of T which returns “yes”. Denote by f_{i} ∈ R[X_{1}, …, X_{n}], 1 ≤ i ≤ k the polynomials of degrees deg(f_{i}) ≤ d, attached to the vertices of T along the fixed branch. Without loss of generality, we can assume that the corresponding signs of polynomials along the branch are

f_{1} = ⋯ = f_{k_{1}} = 0, f_{k_{1}+1} > 0, …, f_{k} > 0.

Then the (accepted) semialgebraic set

W = {f_{1} = ⋯ = f_{k_{1}} = 0, f_{k_{1}+1} > 0, …, f_{k} > 0}

lies in P.

Our main technical tool is the following theorem.

Theorem 2. The number of facets P′ of P such that dim(P′) = dim(P′ ∩W) is bounded from above by (knd)^{O(n)}.

Let us deduce Theorem 1 from Theorem 2.

For each facet P′ of P there exists at least one branch of the tree T with the output “yes” and having an accepted set W_{1} ⊂ R^{n} such that

dim(W_{1} ∩ P′) = dim(P′).

Since there are at most 3^{k} different branches of T, the inequality

N < 3^{k}(knd)^{O(n)}

follows from Theorem 2. This inequality and the assumption N > (dn)^{cn} (for a suitable c) imply k ≥ Ω(log N), which proves Theorem 1.

Note that in the case k_{1} = 0 for an open set W and each facet P′ of P we have P′ ∩ W = ∅. Thus in what follows we can suppose that k_{1} ≥ 1.

1. Computer algebra for curvatures

Let a polynomial F ∈ R[X_{1}, …, X_{n}] with deg(F) < d. Assume that at a point x ∈ \{F = 0\} ⊂ R^{n} the gradient grad_{x}(F) = (\frac{∂F}{∂X_{1}} , …, \frac{∂F}{∂X_{n}} )(x) ≠ 0. Then, according to the implicit function theorem, the real algebraic variety {F = 0} ⊂ R^{n} is a smooth hypersurface in a neighbourhood of x.

Fix a point x ∈ {F = 0}. Consider a linear transformation X ⟶ AX + x, where A is an arbitrary orthogonal matrix such that

u_{1} = Ae_{1} + x = \frac{grad_{x}(F)}{∥grad_{x}(F)∥}

is the normalized gradient and e_{1}, …, e_{n} is the coordinate basis at the origin. Then the linear hull of vectors u_{j} = Ae_{j} + x, 2 ≤ j ≤ n is the tangent space T_{x} to {F = 0} at x.

Denote by U_{1}, …, U_{n} the coordinate variables in the basis u_{1}, …, u_{n}. By the implicit function theorem, there exists a smooth function H(U_{2}, …, U_{n}) defined in a neighbourhood of x on T_{x} such that {F = 0} = {U_{1} = H(U_{2}, …, U_{n})} in this neighbourhood.

Let u_{1} = (α̃_{1}, …, α̃_{n}) with α̃_{i_{0}} ≠ 0. Take any permutation π_{i_{0}} of {1, …, n} such that π_{i_{0}}(1) = i_{0}. Denote (α_{1}, …, α_{n}) = (α̃_{π_{i_{0}} (1)}, …, α̃_{π_{i_{0}} (n)}) (thus α_{1} ≠ 0) and β_{i} = \sqrt{α_{1}^{2} + ⋯ + α_{i}^{2}}, 1 ≤ i ≤ n. Obviously β_{i} > 0 and β_{n} = 1.

As A one can take the following product of (n − 1) orthogonal matrices:

∏_{0≤k≤n−2} ( \begin{matrix}\frac{β_{n−k−1}}{β_{n−k}} & 0 & ⋯ & 0 & \frac{α_{n−k}}{β_{n−k}} & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 & 0 & 0 & ⋯ & 0 \\ −\frac{α_{n−k}}{β_{n−k}} & 0 & ⋯ & 0 & \frac{β_{n−k−1}}{β_{n−k}} & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 1 \end{matrix} )

(in kth matrix of this product the element \frac{β_{n−k−1}}{β_{n−k}} occurs at the positions (1, 1) and (n − k, n − k)).

Denote F̂(U_{1}, …, U_{n}) = F (A^{T} (U_{1}, …, U_{n}) + x). Differentiating this function twice and taking into the account that F̂(H(U_{2}, …, U_{n}), U_{2}, …, U_{n}) = 0 in a neighbourhood of x in T_{x} we get

\frac{∂^{2}F̂}{∂U_{1}∂U_{j}} \frac{∂H}{∂U_{i}} + \frac{∂F̂}{∂U_{1}} \frac{∂^{2}H}{∂U_{i}∂U_{j}} + \frac{∂^{2}F̂}{∂U_{i}∂U_{j}} = 0  (1)

for 2 ≤ i, j ≤ n.

Since

\frac{∂H}{∂U_{i}} |_{(U_{2},...,U_{n})=0} = 0 and \frac{∂F̂}{∂U_{1}} |_{(U_{1},...,U_{n})=0} = ∥grad_{x}(F)∥ ≠ 0,

evaluating the equality (1) at x (i.e., substituting (U_{1}, …, U_{n}) = 0) we obtain (cf. [Mi 64]):

(\frac{∂^{2}H}{∂U_{i}∂U_{j}} )|_{(U_{2},...,U_{n})=0} = (∥grad_{x}(F)∥)^{−1}(\frac{∂^{2}F̂}{∂U_{i}∂U_{j}} )|_{(U_{1},...,U_{n})=0}.  (2)

Introduce the symmetric (n − 1) × (n − 1)-matrix

H = (\frac{∂^{2}H}{∂U_{i}∂U_{j}} )|_{(U_{2},...,U_{n})=0}.

Its eigenvalues λ_{2}, …, λ_{n} belong to R and are called the principal curvatures of the hypersurface {F = 0} at x [Th 77].

Now we describe symbolically the set of all points x with all principal curvatures greater than some parameter κ.

Denote by χ(Z) the characteristic polynomial of the matrix H. The roots of χ are exactly λ_{2}, …, λ_{n}. Due to Sturm theorem, every λ_{2}, …, λ_{n} is greater than κ if and only if χ_{l}(κ)χ_{l+1}(κ) < 0, 0 ≤ l ≤ n − 2, where χ_{0} = χ, χ_{1} = χ′_{0} and χ_{2}, …, χ_{n−1} is the polynomial remainder sequence of χ_{0}, χ_{1} [Lo 82]. Obviously deg_{Z}(χ_{l}) = n − l − 1.

Observe that every element of the matrix A can be represented as a fraction γ_{1}/γ_{2} where

γ_{2} = β_{1}^{ν_{1}} ⋯ β_{n−1}^{ν_{n−1}}∥grad_{x}(F)∥^{ν}

and γ_{1} = Γ(β_{1}, …, β_{n−1}, X_{1}, …, X_{n}) is a polynomial in

β_{1}(X_{1}, …, X_{n}), …, β_{n−1}(X_{1}, …, X_{n}), X_{1}, …, X_{n}

with Γ ∈ R[Z_{1}, …, Z_{n−1}, X_{1}, …, X_{n}]. Moreover, ν_{1} + ⋯ + ν_{n−1} + ν ≤ 2(n − 1) and deg(Γ) ≤ d(n − 1). Hence all elements of A are algebraic functions in X_{1}, …, X_{n} of quadratic-irrational type. By the degree of such quadratic-irrational function we mean max{deg(Γ), ν_{1} + ⋯ + ν_{n−1} + ν}. In what follows we deal with algebraic functions in X_{1}, …, X_{n} of the similar type.

Formula (2) and Habicht’s theorem [Lo 82] imply that deg(χ_{l}) ≤ (nd)^{O(1)}.

We summarize a description of the set of all points with large principal curvatures in the following lemma.

Lemma 1. Fix 1 ≤ i_{0} ≤ n. The set of all points x ∈ {F = 0} such that grad_{x}(F) = (α̂_{1}, …, α̂_{n}) has α̂_{i_{0}} ≠ 0 and all principal curvatures of the hypersuface {F = 0} at x are greater than κ can be represented as {F = 0, g_{1} > 0, …, g_{n} > 0}. Here g_{1} = α̂_{i_{0}}^{2}, …, g_{s} are polynomials in κ of degrees at most 2n with coefficients being quadratic-irrational algebraic functions (see above) of degrees less than (nd)^{O(1)}.

Remark. Observe that a set given by a system of inequalities involving real algebraic functions is semialgebraic. Hence the set introduced in Lemma 1 is semialgebraic.

2. Computations with infinitesimals

The following digest on infinitesimals follows [GV 88].

Let K be an arbitrary real closed field (see, e.g., [L 65]) and an element ε be infinitesimal relative to elements of K. The latter means that for any positive element a ∈ K inequalities 0 < ε < a are valid in the ordered field K(ε). Obviously, the element ε is transcendental over K. For an ordered field K′ we denote by K̃′ its (unique up to isomorphism) real closure, preserving the order on K′ [L 65].

Let us remind some other well-known statements concerning real closed fields. A Puiseux (formal power-fractional) series over K is series of the kind

b = ∑_{i≥0} a_{i}ε^{ν_{i}/μ},

where 0 ≠ a_{i} ∈ K for all i ≥ 0, integers ν_{0} < ν_{1} < … increase and the natural number μ ≥ 1. The field K((ε^{1/∞})) consisting of all Puiseux series (appended by zero) is real closed, hence K((ε^{1/∞})) ⊃ K̃(ε) ⊃ K(ε). Besides the field K[\sqrt{−1}]((ε^{1/∞})) is algebraically closed.

If ν_{0} < 0, then the element b ∈ K((ε^{1/∞})) is infinitely large. If ν_{0} > 0, then b is infinitesimal relative to elements of the field K. A vector (b_{1}, …, b_{n}) ∈ (K((ε^{1/∞})))^{n} is called K-finite if each coordinate b_{i}, 1 ≤ i ≤ n is not infinitely large relative to elements of K.

For any K-finite element b ∈ K((ε^{1/∞})) its standard part st(b) is definable, namely st(b) = a_{0} in the case ν_{0} = 0 and st(b) = 0 if ν_{0} > 0. For any K-finite vector (b_{1}, …, b_{n}) ∈ (K((ε^{1/∞})))^{n} its standard part is defined by the equality

st(b_{1}, …, b_{n}) = (st(b_{1}), …, st(b_{n})).

For a set W ⊂ (K((ε^{1/∞})))^{n} consisting of only K-finite vectors we define

st(W) = {st(w) : w ∈ W}.

The following “transfer principle” is true [T 51]. If K′, K′′ are real closed fields with K′ ⊂ K′′ and P is a closed (without free variables) formula of the first order theory of the field K′, then P is true over K′ if and only if P is true over K′′.

In the sequel we consider infinitesimals ε_{1}, ε_{2}, … such that ε_{i+1} is infinitesimal relative to the real closure R_{i} of the field R(ε_{1}, …, ε_{i}) for each i ≥ 0. We assume that R_{0} = R.

For an R_{i}-finite element b ∈ R_{i+1} its standard part (relative to R_{i}) denote by st_{i}(b) ∈ R_{i}. For any b ∈ R_{j}, j > i we define st_{i}(b) = st_{i}(st_{i+1}(… st_{j−1}(b) …). For a semialgebraic set V ⊂ R_{i}^{n} defined by a certain formula Φ of the first order theory of the field R_{i} we define the completion V^{(ε_{j})} ⊂ R_{j}^{n} of V as the semialgebraic set given in R_{j}^{n} by the same formula Φ (we say that V^{(ε_{j})} is defined over R_{i}). In a similar way one can define completions of polynomials and algebraic functions.

Lemma 2 (cf. Lemma 4a) in [GV 88]). Let F be a smooth algebraic function defined on an open semialgebraic set U ⊂ R_{i}^{n} and determined by a polynomial with coefficients from R_{i}. Then ε_{i+1} is not a critical value of F (i.e., grad_{y}(F) does not vanish at any point y ∈ {F = ε_{i+1}} ∩ U).

To prove Lemma 2 note that Sard’s theorem [Hi 76] and the transfer principle imply the finiteness of the set of all critical values, moreover this set lies in R_{i}.

3. Curved points

In what follows we assume w.l.o.g. that polyhedron P is compact, a reduction of a general case to this one is described in Section 2 of [GKV 94].

For an m-plane Q ⊂ R_{i}^{n} and a point x ∈ R_{i}^{n} denote by Q(x) the m-plane collinear to Q and containing x.

Two planes Q_{1}, Q_{2} of arbitrary dimensions are called transversal if

dim(Q_{1}(0) ∩ Q_{2}(0)) = max{0, dim(Q_{1}(0)) + dim(Q_{2}(0)) − n}.

For every 0 ≤ i < n choose an (n − i)-plane Π_{n−i} (defined over R) transversal to any facet of the polyhedron P.

Denote f = f_{1}^{2} + ⋯ + f_{k_{1}}^{2}.

Fix 0 ≤ i < n and denote by f̂ the restriction of f on Π_{n−i}(x).

Definition. A point y ∈ {f = ε_{3}} is called i-curved if grad_{y}(f̂ − ε_{3}) ≠ 0, all principal curvatures of the variety {f̂ = ε_{3}} ⊂ Π_{n−i}(y) at y are greater than ε_{1}^{−1} and f_{k_{1}+1}(y) > ε_{1}, …, f_{k}(y) > ε_{1}.

Remark. We fix an orthogonal basis in Π_{n−i}(0) with coordinates belonging to R. Then in Definition we consider curvatures in Π_{n−i}(y) with respect to the basis obtained from the fixed one by the shift Y ⟶ Y + y.

One can consider this definition as a kind of “localization” of the key concept of an angle point from [GV 94].

Denote the set of all i-curved points by K_{i}. Observe that K_{i} is semialgebraic due to the remark at the end of Section 1. Denote K_{i} = st_{0}(K_{i}) ⊂ R^{n}, this set is also semialgebraic [RV 94].

Lemma 3. Let for an i-facet P_{i} of P the dimension dim(W ∩P_{i}) = i. Then W ∩P_{i} ⊂ K_{i}.

Corollary. If dim(W ∩ P_{i}) = i then dim(K_{i} ∩ P_{i}) = i.

This Corollary implies that in order to prove Theorem 2 it is sufficient to bound the number of i-facets P_{i} for which dim(K_{i} ∩ P_{i}) = i.

Lemma 4. For any smooth point z ∈ K_{i} with the dimension dim_{z}(K_{i}) ≥ i + 1 the tangent plane T_{z} to K_{i} at z is not transversal to Π_{n−i}.

Remark. In the particular case i = 0 Lemma 4 states that K_{0} consists of a finite number of points.

4. Facets of P and Whitney stratification of K_{i}

Denote by B_{x}(r) the open ball in R_{i}^{n} centered at x and of the radius r.

For a subset E ⊂ R_{i}^{n} denote by cl(E) its closure in the topology with the base of all open balls. Denote by ∂E the boundary

{y ∈ R_{i}^{n} : for any 0 < r ∈ R_{i} ∅ ≠ B_{y}(r) ∩ E ≠ B_{y}(r)}.

Recall that K_{i}, as any semialgebraic set, admits a Whitney stratification (see, e.g., [GM 88]). Namely, K_{i} can be represented as a disjoint union K_{i} = ⋃_{j} S_{j} of a finite number of semialgebraic sets, called strata, which are smooth manifolds and such that:

(1) (frontier condition) S_{j_{1}} ∩ cl(S_{j_{2}}) ≠ ∅ if and only if S_{j_{1}} ⊂ cl(S_{j_{2}});

(2) (Whitney condition A) Let S_{j_{1}} ⊂ cl(S_{j_{2}}) and a sequence of points x_{l} ∈ S_{j_{2}} tends to a point y ∈ S_{j_{1}} when l ⟶ ∞. Assume that the sequence of tangent planes T_{x_{l}} to S_{j_{2}} at points x_{l} tends to a certain plane T. Then T_{y} ⊂ T where T_{y} is a tangent plane to S_{j_{1}} at y.

Lemma 5. Let for an i-facet P_{i} of P the dimension dim(K_{i} ∩ P_{i}) = i. Assume that S_{j} is a stratum of K_{i} such that dim(cl(S_{j}) ∩ K_{i} ∩ P_{i}) = i. Then S_{j} ⊂ P_{i}.

Denote g = f_{k_{1}} ⋯ f_{k}. Choose 0 < μ ∈ R satisfying the following properties:

(a) μ is less than the absolute values of all critical values of the restrictions of g on i-facets P_{i} (note that Sard’s theorem implies the finiteness of the number of all critical values, moreover they all belong to R);

(b) for any P_{i} such that dim(K_{i} ∩ P_{i}) = i the dimension

dim({g = μ} ∩ cl(S_{j}) ∩ K_{i} ∩ P_{i}) ≤ i − 2

for every stratum S_{j} which is not contained in P_{i} (observe that due to Lemma 5 there exists at most finite number of μ violating this condition).

Fix i-facet P_{i} for which dim(W ∩ P_{i}) = i. Denote K′_{i} = K_{i} ∩ {g = μ}.

¿From the properties (a), (b) using Lemma 3 we deduce the following lemma.

Lemma 6. The variety

K′_{i} ∩ P_{i} = {g = μ} ∩ {f_{k_{1}} > 0, …, f_{k} > 0} ∩ P_{i}

is a nonempty smooth hypersurface in P_{i}. Moreover

dim((cl(K′_{i} \ P_{i})) ∩ (K′_{i} ∩ P_{i})) ≤ i − 2.

The next important step is the proof of the following lemma.

Lemma 7. The number of i-facets P_{i} such that K′_{i} ∩ P_{i} is a nonempty smooth hypersurface in P_{i} and

dim((cl(K′_{i} \ P_{i})) ∩ (K′_{i} ∩ P_{i})) ≤ i − 2,

does not exceed (nkd)^{O(1)}.

Theorem 2 immediately follows from Lemmas 6 and 7. A sketch of a proof of Lemma 7 is given in the next section.

Lemma 8.

K′_{i} = st_{0}(K_{i} ∩ {|g − μ| ≤ ε_{2}}).

5. Extremal points of a linear function on K_{i}

Take a generic linear function L = γ_{1}X_{1} +⋯+γ_{n}X_{n} with coefficients γ_{1}, …, γ_{n} ∈ R. Since P is compact the function L attains its maximal value, say θ_{0}, on K′_{i} ∩P_{i} at a certain point v. Denote by V a connected component of K′_{i} ∩ P_{i} which contains v. There exists 0 < r ∈ R such that B_{v}(r) ∩ K′_{i} = B_{v}(r) ∩ V due to the property (b) (see Section 4). Moreover, there exists 0 < r_{1} ∈ R such that the values of L on the set K′_{i} ∩ ∂B_{v}(r) are less than θ_{0} − r_{1}. This implies, using Lemma 8, the following lemma.

Lemma 9. L attains its maximal value θ on the set

cl(K_{i} ∩ {|g − μ| ≤ ε_{2}}) ∩ B_{v}(r/2)

(at a point, say, w) and for a suitable 0 < r_{1} ∈ R the values of L on the set

cl(K_{i} ∩ {|g − μ| ≤ ε_{2}}) ∩ ∂B_{v}(r/2)

are less than θ − r_{1}.

In particular, L attains a local maximum on ∂(K_{i} ∩ {|g − μ| ≤ ε_{2}}) at w.

For a point y let

grad_{y}(f̂− ε_{3}) = (u_{1}, …, u_{n−i})

(cf. Definition). The set K_{i}∩{|g−μ| ≤ ε_{2}} of the points y = (y_{1}, …, y_{n}) can be represented as a union of n − i semialgebraic sets of the form

U^{(i_{0})} = {f − ε_{3} = 0, u_{i_{0}}^{2} > 0, p_{1} > 0, …, p_{s} > 0}, 1 ≤ i_{0} ≤ n − i

for some algebraic functions p_{1}, …, p_{s} of the quadratic-irrational type introduced in Section 1, i.e., rational functions in y_{1}, …, y_{n} and in

\sqrt{u_{i_{0}}^{2}}, \sqrt{u_{i_{0}}^{2} + u_{π_{i_{0}} (2)}^{2}} , …, \sqrt{u_{i_{0}}^{2} + u_{π_{i_{0}} (2)}^{2} + … + u_{π_{i_{0}} (n−i)}^{2}}  (3)

(see Lemma 1). Here π_{i_{0}} is a permutation of {1, 2, …, n − i} such that π_{i_{0}}(1) = i_{0} (cf. Section 1).

Denote

q = (ε_{5}^{2} − (f − ε_{3})^{2})(u_{i_{0}}^{2} − ε_{4})(p_{1} − ε_{4}) ⋯ (p_{s} − ε_{4}).

Introduce the semialgebraic set

U^{(i_{0})} = {q = ε_{6}} ∩ {ε_{5}^{2} > (f − ε_{3})^{2}, u_{i_{0}}^{2} > ε_{4}, p_{1} > ε_{4}, …, p_{s} > ε_{4}}.

The next lemma follows from Lemmas 1, 4 in [GV 92].

Lemma 10.

st_{3}(U^{(i_{0})}) = cl(U^{(i_{0})}).

Lemma 11. For an appropriate 1 ≤ i_{0} ≤ n − i the function L attains its maximal value θ_{1} on the set U^{(i_{0})} ∩ B_{v}(r/3) and for a certain 0 < r_{2} ∈ R the values of L on the set U^{(i_{0})} ∩ ∂B_{v}(r/3) are less than θ_{1} − r_{2}.

Lemma 11 follows from Lemmas 9, 10. For a proof, take 1 ≤ i_{0} ≤ n − i such that the corresponding point w (see Lemma 9) lies in cl(U^{(i_{0})}).

Corollary The number of i-facets P_{i} satisfying the conditions of Lemma 7 does not exceed the number of local maxima of L on the set ⋃_{1≤i_{0}≤n−i} U^{(i)}.

Observe that in the open semialgebraic set {u_{i_{0}}^{2} > 0} all the square roots (3) are positive. Therefore all algebraic functions p_{1}, …, p_{s} occuring in U^{(i_{0})} are smooth, hence q is smooth as well. Because of Lemma 2 ε_{6} is not a critical value of q in the set {u_{i_{0}}^{2} > 0}. Then the implicit function theorem implies the following lemma.

Lemma 12. U^{(i_{0})} is a smooth hypersurface.

Finally, let us prove the following lemma.

Lemma 13. The number ν of local maxima of L on U^{(i_{0})} does not exceed (nkd)^{O(n)}.

Together with Corollary to Lemma 11 this implies Lemma 7 (and hence Theorem 2).

Because of Lemma 12, ν does not exceed the number of connected components of the semialgebraic set

M = \{0 = q − ε_{6} = γ_{i} \frac{∂q}{∂X_{j}} − γ_{j} \frac{∂q}{∂X_{i}} , 1 ≤ i < j ≤ n\}.

Replace each occurrence of the square root

\sqrt{u_{i_{0}}^{2} + u_{π_{i_{0}} (2)}^{2} + ⋯ + u_{π_{i_{0}} (m)}^{2}},

1 ≤ m ≤ n − i in q by a new variable Z_{m}. Denote the resulting rational function by Q ∈ R_{5}[X_{1}, …, X_{n}](Z_{1}, …, Z_{m}) (cf. Section 1).

Introduce the semialgebraic set

M = \{0 = Q − ε_{6} = γ_{i} \frac{∂Q}{∂X_{j}} − γ_{j} \frac{∂Q}{∂X_{i}} , 1 ≤ i < j ≤ n,

Z_{m} > 0, Z_{m}^{2} = u_{i_{0}}^{2} + u_{π_{i_{0}} (2)}^{2} + ⋯ + u_{π_{i_{0}} (m)}^{2}, 1 ≤ m ≤ n − i} ⊂ R_{6}^{n+m}.

Consider the linear projection

ρ : R_{6}^{n+m} ⟶ R_{6}^{n}, ρ(X_{1}, …, X_{n}, Z_{1}, …, Z_{m}) = (X_{1}, …, X_{n}).

Then ρ(M) = M. Hence the number of connected components of M is less than or equal to the number of connected components of M.

Observe that the degrees of rational functions occuring in M can be bounded from above by (knd)^{O(1)} due to Lemma 1. Therefore, the number of connected components of M does not exceed (knd)^{O(n)} by [Mi 64].

This completes the proof of Lemma 13 and thereby Theorems 2 and 1.

6. Lower bounds for concrete polyhedra

In this section we give an application of the lower bound from Theorem 1 to a concrete class of polyhedra. We follow the construction of cyclic polyhedra (see [MS 71]), used in the analysis of the simplex method.

Take any m > Ω(n^{2}) points in R^{n} of the form (t_{j}, t_{j}^{2}, …, t_{j}^{n}) for pairwise distinct t_{j}, 1 ≤ j ≤ m. Consider the convex hull of these points and denote by P_{n,m} ⊂ R^{n} its dual polyhedron [MS 71]. Then P_{n,m} has m faces of the highest dimension n − 1 and the number of faces of all dimensions

N > \binom{m − [n/2]}{[n/2]} > m^{Ω(n)}

(see [MS 71]).

Therefore, Theorem 1 implies that the complexity of testing membership to P_{n,m} is bounded by Ω(log N) > Ω(n log m).

We would like to mention that Section 4 of [GKV 94] provides a weaker bound Ω(log m) even for algebraic computation trees.

Acknowledgements

We thank Dima Burago, Friedhelm Meyer auf der Heide, Kolia Ivanov, Andy Yao for a number of useful discussions and Anders Björner for a help with the example from Section 6.

References

[B 83] M. Ben-Or, “Lower bounds for algebraic computation trees, ” Proceedings of ACM Symposium on Theory of Computing, 1983, 80-86.

[B 92] A. Björner, “Subspace arrangements,” Proceedings of 1st European Congress of Mathematicians, Paris, 1992.

[BKL 92] P. Buergisser, M. Karpinski, and T. Lickteig “On randomized algebraic test complexity,” Technical Report TR-92-070, International Computer Science Institute, Berkeley, 1992.

[BL 92] A. Björner, and L. Lovasz “Linear decision trees, subspace arrangements and Möbius functions,” Preprint, 1992.

[BLY 92] A. Björner, L. Lovasz, and A. Yao “Linear decision trees: Volume estimates and topological bounds,” Proceedings of ACM Symposium on Theory of Computing, 1992, 170-177.

[G 88] D. Grigoriev “Complexity of deciding Tarski algebra,” Journal Symbolic Comp., V. 5, 1988, 65-108.

[GKS 93] D. Grigoriev, M. Karpinski, and M. Singer “Computational complexity of sparse real algebraic function interpolation,” Proceedings MEGA’92, in: Progress in Mathematics, Birkhäuser, V. 109, 1993, 91-104.

[GKV 94] D. Grigoriev, M. Karpinski, and N. Vorobjov “Lower bounds on testing membership to a polyhedron by algebraic decision trees,” Proceedings of ACM Symposium on Theory of Computing, 1994, 635-644.

[GM 88] M. Goresky, and R. MacPherson “Stratified Morse Theory,” Springer-Verlag, Berlin, 1988.

[GV 88] D. Grigoriev, and N. Vorobjov “Solving systems of polynomial inequalities in subexponential time,” Journal Symbolic Comp., V. 5, 1988, 37-64.

[GV 92] D. Grigoriev, and N. Vorobjov “Counting connected components of a semialgebraic set in subexponential time,” Computational Complexity, V. 2, 1992, 133-186.

[GV 94] D. Grigoriev, and N. Vorobjov “Complexity lower bounds for computation trees with elementary transcendental function gates,” Proceedings of IEEE Symposium on Foundations of Computer Science, 1994.

[Hi 76] M. Hirsch “Differential Topology,” Springer-Verlag, 1976.

[L 65] S. Lang “Algebra,” Addison-Wesley, New York, 1965.

[Lo 82] R. Loos “Generalized polynomial remainder sequences,” in: Symbolic and Algebraic Computation, B. Buchberger et al., eds., Springer-Verlag, New York, 1982.

[M 64] J. Milnor “On the Betti numbers of real varieties,” Proc. Amer. Math. Soc., V.15, 1964, 275-280.

[MH 85] F. Meyer auf der Heide “Fast algorithms for n-dimensional restrictions of hard problems,” Proceedings of ACM Symposium on Theory of Computing, 1985, 413-420.

[MS 71] P. McMullen, and G. Shephard “Convex Polythopes and the Upper Bound Conjecture,” Cambridge University Press, Cambridge, 1971.

[RV 94] M. -F. Roy, and N. Vorobjov “Finding irreducible components of some real transcendental varieties,” Computational Complexity, V. 4, 1994, 107-132.

[T 51] A. Tarski “A Decision Method for Elementary Algebra and Geometry,” University of California Press, 1951.

[Th 77] J. A. Thorpe “Elementary Topics in Differential Geometry,” Springer-Verlag, Berlin, 1977.

[Y 92] A. Yao “Algebraic decision trees and Euler characteristics,” Proceedings of IEEE Symposium on Foundations of Computer Science, 1992, 268-277.

[Y 94] A. Yao “Decision tree complexity and Betti numbers,” Proceedings of ACM Symposium on Theory of Computing, 1994, 615-624.

[YR 80] A. Yao, and R. Rivest “On the polyhedral decision problem,” SIAM J. Comput., V. 9, 1980, 343-347.