Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees

Dima Grigoriev^{1}, Marek Karpinski^{2}, Nicolai Vorobjov^{3}

1Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802 Supported in part by NSF grant CCR-9424358 E-mail: dima@cse.psu.edu

2Department of Computer Science, University of Bonn, 53117 Bonn, and International Computer Science Institute, Berkeley, CA Supported in part by DFG Grant KA673/4-1, by the ESPRIT BR Grants 7097 and EC–US 030, and by the Volkswagen-Stiftung E-mail: marek@cs.bonn.edu

3School of Mathematical Sciences, University of Bath, Bath, BA2 7AY, UK E-mail: nnv@maths.bath.ac.uk

Abstract We introduce a new method of proving lower bounds on the depth of algebraic d-degree decision (resp. computation) trees and apply it to prove a lower bound Ω(log N) (resp. Ω(log N/ log log N)) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N > (nd)^{Ω(n)} (resp. N > n^{Ω(n)}). This bound apparently does not follow from the methods developed by M. Ben-Or, A. Björner, L. Lovasz, and A. Yao [B. 83], [BLY 93], [Y 94] because topological invariants used in these methods become trivial for convex polyhedra.

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], [GKV 94], [MH 85], [MMP 96], [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 faces 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 and computation 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)} and also prove a lower bound Ω(log N/ log log N) for algebraic computation trees, provided that N > n^{Ω(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), thus having 2^{O(n^{2})} faces. In the present paper we apply the obtained lower bound to a concrete class of polyhedra given by Ω(n^{2}) linear constraints and with n^{Ω(n)} faces.

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 decision and 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 [Y 94] the latter lower bound was extended to the algebraic decision and computation trees. In [MMP 96] the lower bound Ω(\sqrt{log(B)/n}) was proved for parallel complexity model.

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 intersections with 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 5 in Section 3) that to obtain the required bound for the number of i-faces P_{i} of P such that dim(P_{i} ∩ W) = i it is sufficient to estimate the number of faces 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 faces, for which Theorem 1 provides a nontrivial lower bound.

In Section 7 we give an outline of the proof of the complexity lower bound for testing membership to a polyhedron by a computation (rather than decision) trees; see Theorem 1′ below. A complete proof is given only for the case of decision trees because for computation trees it’s similar with an addition of some extra technical detailes.

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 faces of P of all dimensions from zero to n − 1. In this paper we agree that a face is “open”, i.e., does not contain faces 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 faces 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 face 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 face P′ of P we have P′ ∩ W = ∅. Thus in what follows we can suppose that k_{1} ≥ 1.

Finally we formulate a complexity lower bound for algebraic computation trees. Let k be now the depth of a computation tree, which tests a membership to P.

Theorem 1′.

k ≥ Ω(log N/ log log N),

provided that N ≥ n^{c_{1}n} for a suitable c_{1} > 0.

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 ⟶ A_{x}X + x, where A_{x} is an arbitrary orthogonal matrix such that

u_{1} = A_{x}e_{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} = A_{x}e_{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_{x}(U_{2}, …, U_{n}) defined in a neighbourhood of x on T_{x} such that {F = 0} = {U_{1} = H_{x}(U_{2}, …, U_{n})} in this neighbourhood.

Let grad_{x}(F) = (α̃_{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} = ∥grad_{x}(F)∥.

As A_{x} 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 the 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_{x}(U_{1}, …, U_{n}) = F (A_{x}^{T} (U_{1}, …, U_{n}) + x). Differentiating this function twice and taking into the account that F_{x}(H_{x}(U_{2}, …, U_{n}), U_{2}, …, U_{n}) = 0 in a neighbourhood of x in T_{x} we get

\frac{∂^{2}F_{x}}{∂U_{1}∂U_{j}} \frac{∂H_{x}}{∂U_{i}} + \frac{∂F_{x}}{∂U_{1}} \frac{∂^{2}H_{x}}{∂U_{i}∂U_{j}} + \frac{∂^{2}F_{x}}{∂U_{i}∂U_{j}} = 0  (1)

for 2 ≤ i, j ≤ n.

Since

\frac{∂H_{x}}{∂U_{i}} |_{(U_{2},...,U_{n})=0} = 0 and \frac{∂F_{x}}{∂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_{x}}{∂U_{i}∂U_{j}} )|_{(U_{2},...,U_{n})=0} = (∥grad_{x}(F)∥)^{−1}(\frac{∂^{2}F_{x}}{∂U_{i}∂U_{j}} )|_{(U_{1},...,U_{n})=0}.  (2)

Introduce the symmetric (n − 1) × (n − 1)-matrix (the matrix of Weingarten map [Th 77], Ch.9)

H_{x} = (\frac{∂^{2}H_{x}}{∂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], Ch.12.

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_{x}. 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_{x} can be represented as a fraction γ_{1}/γ_{2} where γ_{2} = β_{1}^{ν_{1}} ⋯ β_{n}^{ν_{n}}, ν_{1} ≥ 0, …, ν_{n} ≥ 0 are integers 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} ≤ 2(n − 1) and deg(Γ) ≤ d(n − 1). Hence all elements of A_{x} are algebraic functions in X_{1}, …, X_{n} of quadraticirrational type. By the degree of such quadratic-irrational function we mean

max{deg(Γ), ν_{1} + ⋯ + ν_{n}}.

Since an inequality for fraction one could rewrite as a system of inequalities for its numerator and denominator, in what follows we deal with more special algebraic functions in X_{1}, …, X_{n}, namely of the type γ_{1}.

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_{2}, …, g_{n} 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. Calculis with infinitesimals

The definitions below concerning infinitesimals follow [GV 88].

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

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

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

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

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

For any F-finite element b ∈ F((ε^{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 F-finite vector (b_{1}, …, b_{n}) ∈ (F((ε^{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 ⊂ (F((ε^{1/∞})))^{n} we define

st(W) = {st(w) : w ∈ W and w is F−finite}.

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

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 ⊂ F_{1}^{n} defined by a certain formula Φ of the first order theory of the real closed field F_{1} and for a real closed field F_{2} ⊃ F_{1} we define the completion V^{(F_{2})} ⊂ F_{2}^{n} of V as the semialgebraic set given in F_{2}^{n} by the same formula Φ (we say that V^{(F_{2})} is defined over F_{1}). We omit super-index (F_{2}) in V^{(F_{2})} when this does not lead to ambiguity. In a similar way one can define completions of polynomials and algebraic functions.

For any quadratic-irrational function (see Section 1) of the form

f(X_{1}, …, X_{n}, \sqrt{φ_{1}}, …, \sqrt{φ_{r}})

where

f ∈ R_{i}[X_{1}, …, X_{n}, Z_{1}, …, Z_{r}], φ_{e} ∈ R_{i}[X_{1}, …, X_{n}], 1 ≤ e ≤ r,

and a point y ∈ R_{j}^{n}, j ≥ i such that st_{i}(y) is definable and φ_{e}(y) ≥ 0, 1 ≤ e ≤ r, we have st_{i}(f(y)) = f(st_{i}(y)). Indeed, for Puiseux series b (see above) with b > 0 (and therefore with a_{0} > 0) its square root

\sqrt{b} = \sqrt{a_{0}}ε^{ν_{0}/(2μ)} + ⋯

Hence st(\sqrt{b}) = \sqrt{st(b)} is 0 if ν_{0} > 0 and equals to \sqrt{a_{0}} if ν_{0} = 0.

Note that one can apply the transfer principle also to a formula containing quadraticirrational functions since any such formula can be replaced by an equivalent formula of first-order theory. This can be done with replacing each occurrence of \sqrt{φ_{e}} by new variable Z_{e}, adding the quantifier prefix ∃Z_{e} and inequalities Z_{e} ≥ 0, Z_{e}^{2} = φ_{e}, 1 ≤ e ≤ r.

Denote by B_{x}(r) the open ball in R_{i}^{n} centered at x and of radius r, and by ∥ · ∥ the completion of Euclidean distance function.

The following lemma shows that the standard part of a semialgebraic set coincides with the standard part of its completion.

Lemma 2 Let R_{m} ⊂ F ⊂ R_{j} where F is a real closed field and V ⊂ F^{n} is a semialgebraic set defined over F. Then st_{m}(V) = st_{m}(V^{(R_{j})}).

Proof. The inclusion

st_{m}(V) ⊂ st_{m}(V^{(R_{j})})

is trivial.

To prove the opposite inclusion take a point x ∈ st_{m}(V^{(R_{j})}) and consider a semialgebraic set {∥x − y∥^{2} : y ∈ V } ⊂ F. This set is a finite union of (either closed, either open or semi-open) intervals. This is obvious for a semialgebraic subset of R, for an arbitrary real closed field this follows from the transfer principle. Let ω be the left endpoint of the left-most among these intervals. If x ∉ st_{m}(V) then there exists 0 < r_{0} ∈ R_{m} such that ω > r_{0}^{2}, hence B_{x}(r_{0}) ∩ V = ∅. By the transfer principle the completion of the latter set is also empty: B_{x}(r_{0}) ∩ V^{(R_{j})} = ∅. This contradicts to the inclusion x ∈ st_{m}(V^{(R_{j})}) and proves the lemma.

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

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

Note that the above definition of the closure, being applied to a semialgebraic set and written as a formula of first order theory of the field R_{m}, involves quantifiers. The following lemma shows that the closure of a semialgebraic set can be described in terms of infinitesimals.

Lemma 3 (cf. Lemma 1 [GV 92]).

a) Let polynomials φ_{e} ∈ R_{q}[X_{1}, … X_{n}], 1 ≤ e ≤ r and quadratic-irrational functions

h_{1}, …, h_{j}, g_{1}, …, g_{s} ∈ R_{q}[X_{1}, …, X_{n}, \sqrt{φ_{1}}, …, \sqrt{φ_{r}}]

and natural numbers q, l, m satisfy inequalities q < l < m. Consider semialgebraic sets

V = {φ_{1} > 0, …, φ_{r} > 0, g_{1} ≥ 0, …, g_{s} ≥ 0, h_{1} > 0, …, h_{j} > 0} ⊂ R_{q}^{n}

and

V = {φ_{1} > ε_{l}, …, φ_{r} > ε_{l}, g_{1} > −ε_{m}, …, g_{s} > −ε_{m}, h_{1} > ε_{l}, …, h_{j} > ε_{l}} ⊂ R_{m}^{n}.

Then

cl(V) = st_{q}(V) = st_{q}(cl(V)).

b) ∂V ⊂ st_{q}(∂V).

Proof.

a) Let x ∈ cl(V) and the standard part y = st_{q}(x) be definable. We prove that y ∈ cl(V). Consider a point y_{1} = st_{l}(x), then

φ_{e}(y_{1}) = st_{l}(φ_{e}(x)) ≥ ε_{l}, 1 ≤ e ≤ r; g_{s_{1}}(y_{1}) = st_{l}(g_{s_{1}}(x)) ≥ 0, 1 ≤ s_{1} ≤ s;
h_{j_{1}}(y_{1}) = st_{l}(h_{j_{1}}(x)) ≥ ε_{l}, 1 ≤ j_{1} ≤ j.

Hence y_{1} ∈ V^{(R_{l})}.

If y ∉ cl(V) then there exists 0 < r ∈ R_{q} such that B_{y}(r)∩V = ∅. Due to the transfer principle the latter relation holds also over the field R_{l}, namely, B_{y}(r) ∩ V^{(R_{l})} = ∅. On the other hand, y_{1} ∈ B_{y}(r) ∩ V^{(R_{l})} since st_{q}(y_{1}) = y. The obtained contradiction proves the inclusion st_{q}(cl(V)) ⊂ cl(V).

Now let y ∈ cl(V). Consider a semialgebraic set {∥y − z∥^{2} : z ∈ V} ⊂ R_{m}. Then this set is a finite union of (either closed, either open or semi-open) intervals (cf. the proof of Lemma 2). Let ω be the left endpoint of the left-most among these intervals. If y ∉ st_{q}(V) then there exists an element r_{1}, 0 < r_{1} ∈ R_{q} such that ω > r_{1}^{2}, i.e., V ∩ B_{y}(r_{1}) = ∅. On the other hand, V ∩ B_{y}(r_{1}) ≠ ∅ since y ∈ cl(V). Taking into the account the inclusion V ⊂ V, we get a contradiction which proves the inclusion cl(V) ⊂ st_{q}(V).

b) Let x ∈ ∂V and x ∉ st_{q}(∂V). Then there exists an element r_{2}, 0 < r_{2} ∈ R_{q} such that B_{x}(r_{2}) ∩ ∂V = ∅ (cf. the proof of a)). Because of a), x ∈ st_{q}(V), therefore B_{x}(r_{2}) ⊂ V. On the other hand, V ∩ R_{q}^{n} ⊂ V, hence B_{x}(r_{2}) ∩ R_{q}^{n} ⊂ V, this contradicts to the inclusion x ∈ ∂V.

Lemma is proved.

In the proof of Lemma 3 a) it was actually shown that for any semialgebraic set U ⊂ R_{m}^{n} we have st_{q}(U) = st_{q}(cl(U)), q < m.

Corollary. Using the notations of Lemma 3 let

V_{0} = {φ_{1} > 0, …, φ_{r} > 0, h = 0, h_{1} > 0, …, h_{j} > 0} ⊂ R_{q}^{n},
V_{0} = {φ_{1} > ε_{l}, …, φ_{r} > ε_{l}, h = ε_{m}, h_{1} > ε_{l}, …, h_{j} > ε_{l}} ⊂ R_{m}^{n}.

Then st_{q}(V_{0}) ⊂ cl(V_{0}).

To prove Corollary, in Lemma 3 a) instead of V consider a modified set

{φ_{1} > ε_{l}, …, φ_{r} > ε_{l}, −2ε_{m} < h < 2ε_{m}, h_{1} > ε_{l}, …, h_{j} > ε_{l}} ⊃ V_{0}.

Lemma 4 (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^{(R_{i+1})}).

Proof. Sard’s theorem [Hi 76] and the transfer principle imply the finiteness of the set of all critical values of F in U^{(R_{i+1})}, moreover this set lies in R_{i}.

3. Curved points

For any i-face P_{i} denote by \overline{P}_{i} the i-plane containing P_{i}.

First let us reduce Theorem 2 to the case of compact P. Let t be the minimal dimension of faces of P and P_{t} be a face with dim(P_{t}) = t. Then \overline{P}_{t} is a t-plane.

For each i-face P_{i} of P with dim(P_{i} ∩ W) = i choose a point x_{P_{i}} ∈ (P_{i} ∩ W) such that a suitable neighbourhood of x_{P_{i}} in P_{i} is contained in W.

First consider the case t ≥ 1. Choose any hyperplane Σ transversal to P_{t} such that the points x_{P_{i}} for all i-faces P_{i} lie in one of two semi-spaces of R^{n} \ Σ, denote this semi-space by Σ̃. Replace P by (P ∩ Σ̃) ∪ Σ reducing t by one. Continue this process while t ≥ 1.

Now consider the case t = 0.

Observe that there exists a linear form L = τ_{1}X_{1} +⋯+τ_{n}X_{n} with τ_{j} ∈ R, 1 ≤ j ≤ n such that for every γ ∈ R the intersection {L + γ ≥ 0} ∩ P is compact. Take γ such that x_{P_{i}} ∈ P′ = {L + γ ≥ 0} ∩ P for all P_{i}. The number of all i-faces P′_{i} of P′ such that dim(P′_{i} ∩ W) = i is greater or equal than the number of all i-faces P_{i} of P such that dim(P_{i} ∩ W) = i. ¿From now on we assume, without loss of generality, that P is compact.

For an m-plane Q ⊂ R_{j}^{n} and a point x ∈ R_{j}^{n} denote by Q(x) the m-plane parallel 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 every face of the polyhedron P.

Recall that in the Introduction we have fixed a branch of the tree T, denoted by f_{i}, 1 ≤ i ≤ k the polynomials attached to vertices along the branch, and assumed that the signs of these polynomials are

f_{1} = ⋯ = f_{k_{1}} = 0, f_{k_{1}+1} > 0, …, f_{k} > 0.
Denote f = f_{1}^{2} + ⋯ + f_{k_{1}}^{2}.
Fix 0 ≤ i < n and denote by f^{(x)} the restriction of f on Π_{n−i}(x) (for x ∈ R_{j}^{n}).

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

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} ⊂ R_{3}^{n}. 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 closed semialgebraic by Lemma 5.1 from [RV 94]. Corollary to Lemma 3 implies that K_{i} ⊂ cl(W).

Lemma 5. Suppose that P_{i} an i-face of P such that dim(W ∩P_{i}) = i, then W ∩P_{i} ⊂ K_{i}.

Proof. Let x ∈ W ∩ P_{i}. Then f_{j}(x) > c, k_{1} + 1 ≤ j ≤ k for a certain 0 < c ∈ R. Hence there exists 0 < r ∈ R such that for any point y from the open ball B_{x}(r) we have f_{j}(y) > c, k_{1} + 1 ≤ j ≤ k. Due to the transfer principle, f_{j}(y) > c, k_{1} + 1 ≤ j ≤ k for any point y ∈ B_{x}(r) ∩ R_{3}^{n}.

Observe that {f = ε_{3}} ∩ Π_{n−i}(x) = {f^{(x)} = ε_{3}} is a smooth hypersurface in Π_{n−i}(x), because x ∈ R^{n} and ε_{3} is not a critical value of the polynomial f^{(x)} by Lemma 4.

Our purpose is to prove that x = st_{2}(y) (and a fortiori x = st_{0}(y)) for a suitable y ∈ {f = ε_{3}}∩Π_{n−i}(x) such that all principal curvatures of the variety {f = ε_{3}}∩Π_{n−i}(x) at the point y are greater than ε_{2}^{−1}. This would imply Lemma 5 since grad_{y}(f^{(x)} − ε_{3}) ≠ 0 (see Definition).

The point x is a vertex of the polyhedron P = P ∩Π_{n−i}(x) because Π_{n−i} is transversal to P_{i}. Note that for each (n−i−1)-face of P the normalized orthogonal vector (in Π_{n−i}(x)) to this face has all coordinates in R. The vertex x belongs to at least (n − i) among (n − i − 1)-faces of the polyhedron P.

Choose any (n − i − 1)-faces T_{1}, …, T_{n−i} of this kind. Denote by T ⊂ Π_{n−j}(x) the closed cone with vertex at x, formed by planes \overline{T}_{1}, …, \overline{T}_{n−i} and containing P.

Observe that for any point y ∈ cl(B_{x}(r/2)) ∩ R_{3}^{n} the inequalities f_{j}(y) > c, k_{1} + 1 ≤ j ≤ k hold, since cl(B_{x}(r/2)) ⊂ B_{x}(r). Therefore,

{f = 0, f_{j} > c, k_{1} + 1 ≤ j ≤ k} ∩ cl(B_{x}(r/2)) = {f = 0} ∩ cl(B_{x}(r/2)).

Denote D = T ∩ cl(B_{x}(r/2)). For any point z ∈ {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)) we have st_{2}(z) ∈ {f = 0} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)) (see Section 2). Hence

st_{2}(z) ∈ W ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)) ⊂ P ∩ cl(B_{x}(r/2)) ⊂ D,

in particular, the distance ρ(z, D) from z to D is infinitesimal relative to R_{2} (the distance from a point to a bounded set closed in the topology with the base of all open balls, does exist because it is true over the field R, over arbitrary real closed field use the transfer principle).

Since the set {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)) is bounded and closed in the topology with the base of all open balls, there exists ρ_{0} = max ρ(z, D) (sf. the above arguing) where z ranges over all points from {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)), and ρ_{0} is infinitesimal relative to R_{2}.

Let us shift (in Π_{n−i}) each (n − i − 1)-dimensional plane among \overline{T}_{1}, …, \overline{T}_{n−i} parallel to itself outward the cone T to the distance ρ_{0}. The shifted planes form a new closed cone T′ with a vertex x′. Obviously T ⊂ T′. Observe that the distance ∥x − x′∥ is infinitesimal relative to R_{2}. Denote D′ = T′∩cl(B_{x}(r/2)). Then {f = ε_{3}}∩Π_{n−i}(x)∩cl(B_{x}(r/2)) ⊂ D′.

In the plane Π_{n−i}(x) choose a hyperplane Q such that the coordinates of the normalized vector orthogonal to Q belong to R, and T′ ∩ Q(x′) = {x′}. Take a hyperplane Q(y) (in Π_{n−i}(x)) such that its distance from the point x′ is positive, belongs to R, and T′ ∩ Q(y) ≠ ∅. Observe that T′ ∩ Q(y) is contained in a certain (n − i − 1)-dimensional open ball B ⊂ Q(y) with the center z such that the radius and the coordinates of the point z − x′ belong to R.

There exists the unique (n − i − 1)-dimensional sphere S ⊂ Π_{n−i}(x) containing both the point (x′ + z)/2 and the (n − i − 2)-dimensional sphere ∂B. Then the point x′ lies outside the (n − i)-dimensional open ball B bounded by S.

Denote by T′′ ⊂ Π_{n−i}(x) the closed cone with the vertex at x′ and with the base S. Then T′ ⊂ (T′′ \ ∂T′′) because T′ ∩ Q(y) ⊂ B ⊂ B.

The intersection S ∩ ∂T′′ is a (n − i − 2)-dimensional sphere situated in a certain hyperplane Γ (in Π_{n−i}(x)). Then S ∩ ∂T′′ divides S \ (S ∩ ∂T′′) into two connected components S_{1} and S_{2}. Let S_{1} be located in the same half-space (in Π_{n−i}(x)) with the boundary Γ as the point x′.

Denote by S_{1}(μ) the dilation of S_{1} with the coefficient μ with respect to the point x′. Observe that the open cone T′′ \ ∂T′′ is the disjoint union of the dilations S_{1}(μ) over all 0 < μ ∈ R_{3}. There exists the minimal μ_{0} > 0 such that

S_{1}(μ_{0}) ∩ {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)) ≠ ∅.

Then S_{1}(μ_{0}) divides the open cone T′′ \ ∂T′′ into two connected components, moreover the set

{f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2))

and all points from T′′ \ ∂T′′ sufficiently close to the point x′ belong to the different connected components.

Taking into the account that f(x) = 0, and applying Lemma 3 from [GV 88] to the polynomial f^{(x)}, we conclude that there exists a point y_{0} ∈ {f = ε_{3}} ∩ Π_{n−i}(x) such that the distance ∥x − y_{0}∥ is infinitesimal relative to R_{2}. Evidently, y_{0} ∈ cl(B_{x}(r/2)) and ∥y_{0} − x′∥ is also infinitesimal relative to R_{2}. Hence μ_{0} is infinitesimal relative to R_{2} as well. Therefore, the radius ν of the sphere S(μ_{0}) is also infinitesimal relative to R_{2}.

Consider a point

y ∈ S_{1}(μ_{0}) ∩ {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2)).

Then ∥y − x′∥ is infinitesimal relative to R_{2}. Besides, the hypersurfaces S_{1}(μ_{0}) and {f = ε_{3}} ∩ Π_{n−i}(x) (as well as the set {f = ε_{3}} ∩ Π_{n−i}(x) ∩ cl(B_{x}(r/2))) has the same tangent plane T (in Π_{n−i}(x)) at the point y.

Let H_{y} be (n − i − 1) × (n − i − 1)-matrix introduced in Section 1 (with f^{(x)} playing the role of F and y playing the role of x). For any normalized vector v ∈ T the second derivative vH_{y}v of the function H_{y} (see Section 1) in the direction v is greater or equal to the corresponding second derivative for the sphere S(μ_{0}) (at the point y). The latter second derivative equals to 1/ν (cf. the proof of Theorem 4 in Ch. 12 [Th 77]). In particular, for the principal curvatures of the hypersurface {f^{(x)} = ε_{3}} = {f = ε_{3}}∩Π_{n−i}(x) (in Π_{n−i}(x)), the inequalities λ_{2} ≥ 1/ν, …, λ_{n−i} ≥ 1/ν are valid, hence λ_{2} > ε_{2}^{−1}, …, λ_{n−i} > ε_{2}^{−1}.

Thus, the point y is i-curved (recall that f_{j}(y) > c > ε_{2}, k_{1} + 1 ≤ j ≤ k since y ∈ B_{x}(r)).

Finally, st_{2}(y) = x, because ∥x − y∥ is infinitesimal relative to R_{2} and x ∈ R^{n}, a fortiori st_{0}(y) = x, i.e., x ∈ K_{i}. The lemma is proved.

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-faces P_{i} for which dim(K_{i} ∩ P_{i}) = i.

Lemma 6. 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 6 states that K_{0} consists of a finite number of points.

Proof of Lemma 6. First let us reduce the proof to the case i = 0 (so assume in the reduction that dim(K_{0}) ≤ 0). Thus, let i ≥ 1 and suppose that e = dim_{z}(K_{i}) ≥ i + 1. Assume that T_{z} is transversal to Π_{n−i}, then dim(T_{z} ∩ Π_{n−i}(z)) = e − i. Take any (n − e)- plane R ⊂ Π_{n−i}(z) defined over R for which T_{z} ∩ R = {z}. Consider the linear orthogonal projection π : R_{3}^{n} ⟶ R_{3}^{e} onto e-subspace along R. Then dim(π(T_{z})) = e. Therefore, by the implicit function theorem, π(K_{i}) ⊂ R^{e} contains e-dimensional ball B_{π(z)}(r) for a certain 0 < r ∈ R.

For any point x ∈ K_{i} there is a point x′ ∈ K_{i} such that st_{0}(x′) = x, hence st_{0}(π(K_{i})) ⊃ B_{π(z)}(r).

For any point y ∈ R^{n} the set K_{0}^{(y)} of 0-curved points of the restriction f^{(y)} coincides with Π_{n−i}(y) ∩ K_{i} according to Definition. Applying the assumption that the lemma is valid for i = 0 to the polynomial f^{(y)} we obtain the inequality dim(st_{0}(Π_{n−i}(y) ∩ K_{i})) ≤ 0 (taking into the account that f^{(y)} is defined over R).

Let us show that π(K_{i}) does not contain a ball B_{w}(r_{1}) for any 0 < r_{1} ∈ R and w ∈ R_{3}^{n}. Assume the contrary, then there exists a point w_{1} ∈ B_{w}(r_{1}) ∩ R^{e}. Let y_{1} ∈ R^{n} be a point such that π(y_{1}) = w_{1}. Denote Π′ = π(Π_{n−i}), then dim(Π′) = e−i, Π_{n−i} = π^{−1}(Π′). Then the following inequalities hold:

dim st_{0}(Π′(w_{1}) ∩ π(K_{i})) ≥ dim st_{0}(Π′(w_{1}) ∩ B_{w}(r_{1})) = e − i ≥ 1.
On the other hand, Π′(w_{1}) ∩ π(K_{i}) = π(K_{i} ∩ Π_{n−i}(y_{1})), and, therefore,
dim st_{0}(Π′(w_{1}) ∩ π(K_{i})) ≤ dim st_{0}(K_{i} ∩ Π_{n−i}(y_{1})) ≤ 0,

(the latter inequality was proved above). The obtained contradiction shows that π(K_{i}) does not contain a ball B_{w}(r_{1}) for any 0 < r_{1} ∈ R.

We claim that for any ball B_{y_{2}}(r_{2}) ⊂ B_{π(z)}(r) defined over R_{3} such that 0 < r_{2} ∈ R, the intersection B_{y_{2}}(r_{2}) ∩ ∂π(K_{i}) ≠ ∅. Assume the contrary. Then either B_{y_{2}}(r_{2}) ⊂ π(K_{i}) or B_{y_{2}}(r_{2}) ∩ π(K_{i}) = ∅. The inclusion B_{y_{2}}(r_{2}) ⊂ π(K_{i}) is impossible as was shown above. If B_{y_{2}}(r_{2}) ∩ π(K_{i}) = ∅, then st_{0}(y_{2}) ∉ st_{0}(π(K_{i})), the latter contradicts the inclusions B_{st_{0}(y_{2})}(r_{2}/2) ⊂ B_{π(z)}(r) ⊂ st_{0}(π(K_{i})) of the sets in the space R^{e}. This proves the claim.

Observe that dim(∂(π(K_{i}))) ≤ e − 1. Applying Lemma 5.1 from [RV 94], we get dim st_{0}(∂(π(K_{i}))) ≤ e − 1.

On the other hand we shall now prove that st_{0}(∂(π(K_{i}))) ⊃ B_{π(z)}(r). This contradiction would complete the proof of the reduction of the lemma to the

case i = 0. Indeed, let y_{3} ∈ B_{π(z)}(r). Observe that the set {∥y − y_{3}∥^{2} : y ∈ ∂(π(K_{i}))} is semialgebraic. Hence, this set is a finite union of points and intervals (cf. the proof of Lemma 2). Let ω be the minimal among these points and the endpoints of these intervals. Suppose that y_{3} ∉ st_{0}(∂(π(K_{i}))), i.e., there does not exist y ∈ ∂(π(K_{i})) such that st_{0}(y) = y_{3}. Thus, ω > r_{3}^{2} for a suitable 0 < r_{3} ∈ R. It follows that B_{y_{3}}(r_{3})∩∂(π(K_{i})) = ∅. We get a contradiction with the proved above claim.

Now let i = 0. Suppose that the statement of the lemma is wrong and dim(K_{0}) = s ≥ 1. There is a linear projection ϕ : R_{3}^{n} ⟶ R_{3} onto one of the coordinates such that ϕ(K_{0}) ⊃ [η′_{1}, η′_{2}] for some η′_{1}, η′_{2} ∈ R, η′_{1} < η′_{2}. Since st_{0}(ϕ(K_{0})) ⊃ [η′_{1}, η′_{2}] and ϕ(K_{0}) ⊂ R_{3}, being a semialgebraic set, consists of a finite union of intervals and points, there exist η_{1}, η_{2} ∈ R, η_{1} < η_{2} such that ϕ(K_{0}) ⊃ [η_{1}, η_{2}]^{(R_{3})}.

Our nearest goal is to prove the existence of a semialgebraic curve C′ ⊂ K_{0} such that the mapping ϕ : C′ ⟶ [η_{1}, η_{2}]^{(R_{3})} is bijective.

For any point u ∈ [η_{1}, η_{2}]^{(R_{3})} take the unique point v_{u} ∈ K_{0} such that ϕ(v_{u}) = u according to the following rule.

A projection π_{1}(ϕ^{−1}(u)) of ϕ^{−1}(u) onto the coordinate X_{1}, being a semialgebraic set, is a union of a finite number of points and intervals (with or without endpoints). Let μ_{1}, μ_{2} be the endpoints of the left-most interval.

Consider four cases. In the first case μ_{1}, μ_{2} ∈ R_{3}, then put μ = (μ_{1} + μ_{2})/2. In the second case the interval is given either by inequality X < μ_{2} or by inequality X ≤ μ_{2}, we put μ = μ_{2} − 1. In the third case the interval is either {X > μ_{1}} or {X ≥ μ_{1}}, we put μ = μ_{1} + 1. In the last case the interval coincides with the whole R_{3}, we put μ = 0.

Note that μ ∈ π_{1}(ϕ^{−1}(u)). We fix the first coordinate of the point v_{u} under construction equal to μ.

Consider the projection π_{2}(ϕ^{−1}(u) ∩ {X_{1} = μ}) onto the axis X_{2}. Continuing in the similar way, after n steps we obtain a point v_{u} = (μ, …) ∈ ϕ^{−1}(u).

We define the semialgebraic curve C′ to be the set of all the obtained points v_{u} for u ∈ [η_{1}, η_{2}]^{(R_{3})}.

The curve C′ has only a finite number of singular points (this is well-known for algebraic curves over R, for arbitrary real closed fields we use the transfer principle). The curve C′ with deleted singular points is a finite union of smooth connected semialgebraic curves. Take one of these curves C such that ϕ(C) ⊃ [η_{3}, η_{4}]^{(R_{3})} for appropriate η_{3} < η_{4}, η_{3}, η_{4} ∈ R.

Since C ⊂ K_{0}, Theorem 1 from Ch. 9 in [Th 77] implies that for any point w ∈ C its curvature k(w) is greater or equal to the minimum of principal curvatures of the hypersurface {f = ε_{3}} at this point w, hence k(w) > ε_{2}^{−1} (according to Definition).

Consider the Gauss map G : C ⟶ S^{n−1} where S^{n−1} is (n−1)-sphere and for a point w ∈ C the image G(w) is the normalized vector tangent to C at w.

Let us prove the following statement:

For any reals θ, l and any smooth semialgebraic curve C with the projection on a certain coordinate axis greater than l and with the curvature at each point greater than θ, there exists a hyperplane Δ such that the semialgebraic set Δ ∩ S^{n−1} ∩ G(C) has the dimension zero and contains at least ⌊lθ/π⌋ points.

To prove this statement for a curve C defined over R observe that the length (with multiplicities) of the image G(C) ⊂ S^{n−1} equals to

∫_{w∈C} k(w) ≥ lθ

(cf. Ch. 10 in [Th 77]). Observe that the length of a curve C_{1} ⊂ S^{n−1} equals to the average (with respect to the uniform Borel measure) number of points of intersection C_{1} ∩S^{n−1} ∩Δ over all hyperplanes Δ, multiplied by π. This implies the statement for the semialgebraic curves C defined over R. For curves C defined over an arbitrary real closed field this statement follows from the transfer principle (applied for fixed θ and l).

Applying the statement to the curve C with l = η_{4} − η_{3} and fixed arbitrary real θ (taking into the account that for any point w ∈ C the curvature k(w) > ε_{2}^{−1} > θ), we conclude that there exists a vector (ρ_{1}, …, ρ_{n}) such that C contains at least ⌊lθ/π⌋ points w_{1} with the tangent vector t_{w_{1}} to C at w_{1} satisfying the linear equation t_{w_{1}} ·(ρ_{1}, …, ρ_{n}) = 0, and there is a finite number of such points.

One can formulate the condition t_{w_{1}} · (ρ_{1}, …, ρ_{n}) = 0 on a point w_{1} ∈ C as a formula of the first-order theory of real closed fields (for a fixed θ). Therefore, there is only a fixed finite number (depending on C) of such points w_{1}, but since one can take an arbitrary θ, we get a contradiction.

This implies that dim(K_{0}) ≤ 0 and completes the proof of the lemma.

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

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}}) (this defines a partial order S_{j_{1}} ≺ S_{j_{2}} on the strata);

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

Lemma 7. Suppose that P_{i} is an i-face of P such that dim(K_{i} ∩ P_{i}) = i. Assume that S′_{j} is a connected component of a stratum S_{j} of K_{i} such that dim(cl(S′_{j}) ∩ K_{i} ∩ P_{i}) = i. Then S′_{j} ⊂ P_{i}.

Proof. If dim(S_{j}) = i then S′_{j} ⊂ P_{i} because S′_{j} ⊂ K_{i} ⊂ cl(W) (see the definition of K_{i} in Section 3) and cl(W) ⊂ P, taking into the account that S′_{j} is a connected smooth semialgebraic set.

Now let e = dim S_{j} ≥ i + 1. We can assume without loss of generality that S_{j} is one of the maximal strata (with respect to the partial order ≺), otherwise take a maximal stratum containing S_{j} in its closure.

There is a stratum S_{l} such that dim(S_{l} ∩ cl(S′_{j}) ∩ K_{i} ∩ P_{i}) = i. The property (1) of Whitney stratification implies that S_{l} ⊂ cl(S_{j}). Take a connected component S′_{l} of S_{l} for which dim(S′_{l} ∩ cl(S′_{j}) ∩ K_{i} ∩ P_{i}) = i. Then dim(S′_{l}) = i, i.e., dim(S_{l}) = i because S′_{l} is smooth and S′_{l} ⊂ P, hence S′_{l} ⊂ P_{i} arguing as above. Let a point y ∈ S′_{l} ∩ cl(S′_{j}) ∩ K_{i} ∩ P_{i} be such that for a suitable 0 < r ∈ R we have

(B_{y}(r) ∩ P_{i}) ⊂ (S′_{l} ∩ cl(S′_{j}) ∩ K_{i} ∩ P_{i}),

then T_{y}(S′_{l}) = \overline{P}_{i}.

There exists a converging sequence y_{m} ⟶_{m→∞} y, y_{m} ∈ S′_{j} such that the sequence of e-dimensional tangent planes T_{y_{m}}(S′_{j}) converges when m → ∞ to a certain e-dimensional plane τ. Due to (2) (Whitney condition A), \overline{P}_{i} ⊂ τ.

Lemma 6 implies that T_{y_{m}}(S′_{j}) is not transversal to Π_{n−i} (taking into the account that y_{m} is a smooth point of K_{i} because S_{j} is a maximal stratum). Therefore, e′_{m} = dim(T_{y_{m}}(S′_{j}) ∩ Π_{n−i}(y_{m})) ≥ e − i + 1. Some subsequence T_{y_{mq}} (S′_{j}) ∩ Π_{n−j}(y_{m_{q}}) of planes converges when q → ∞ to a certain e′-dimensional plane χ ⊂ Π_{n−i}(y), where e′ = e′_{m_{q}} ≥ e − i + 1 for any large enough q.

Choose a basis a_{1}, …, a_{i} of i-plane \overline{P}_{i}(0) and a basis b_{1}, …, b_{e′} of χ(0). Then vectors a_{1}, …, a_{i}, b_{1}, …, b_{e′} are linearly independent due to transversality of \overline{P}_{i} and Π_{n−i}. For large enough q_{0}, for any q ≥ q_{0} there exist vectors

a_{1}^{(q)}, …, a_{i}^{(q)}, b_{1}^{(q)}, …, b_{e′}^{(q)} ∈ (T_{y_{mq}} (S′_{j}))(0)

situated sufficiently close to vectors a_{1}, …, a_{i}, b_{1}, …, b_{e′}, respectively, so that the vectors a_{1}^{(q)}, …, a_{i}^{(q)}, b_{1}^{(q)}, …, b_{e′}^{(q)} are also linearly independent. Hence dim(T_{y_{mq}} (S′_{j})) ≥ e′ + i ≥ e + 1. This leads to a contradiction with the equality dim(S_{j}) = e and proves the lemma.

Denote g = f_{k_{1}+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-faces P_{i} (note that Sard’s theorem implies the finiteness of the number of all critical values, moreover they all belong to R due to Lemma 4);

(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 connected component S′_{j} of a stratum S_{j} such that S′_{j} is not contained in P_{i}. Observe that due to Lemma 7 there exists at most finite number of μ violating this condition because dim(cl(S′_{j}) ∩ K_{i} ∩ P_{i}) ≤ i − 1, together with (a) this justifies the existence of the required μ.

Denote K′_{i} = K_{i} ∩ {g = μ}.

Lemma 8.

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

Proof. We first prove the inclusion ⊂.

Denote by F the real closure of the field R(ε_{2}, ε_{3}). Since K_{i} is defined over F we have K_{i} = (K_{i} ∩ F^{n})^{(R_{3})}. Apply Lemma 2 to the fields R ⊂ F ⊂ R_{3} taking the set K_{i} ∩ F^{n} as V. Then st_{0}(K_{i} ∩ F^{n}) = st_{0}(K_{i}) = K_{i}.

Let x ∈ K′_{i}. It follows that there exists a point y ∈ K_{i} ∩ F^{n} such that st_{0}(y) = x. Hence st_{0}(g(y)) = g(st_{0}(y)) = g(x) = μ. Then (g(y) − μ) ∈ F is infinitesimal relative to R. Taking into the account the representation of g(y) − μ as a Puiseux series in ε_{3} with the coefficients being, in their turn, Puiseux series in ε_{2} (see Section 2), we deduce that |g(y) − μ| < ε_{1}. Thus y ∈ K_{i} ∩ {|g − μ| < ε_{1}}, which proves the inclusion ⊂.

To prove the inclusion ⊃ take a point x ∈ st_{0}(K_{i} ∩{|g −μ| < ε_{1}}). Then, in particular, x ∈ st_{0}(K_{i}) = K_{i}. There exists a point y ∈ K_{i} ∩ {|g − μ| < ε_{1}} such that st_{0}(y) = x. Then μ = st_{0}(g(y)) = g(st_{0}(y)) = g(x). The lemma is proved.

Lemma 9. Let for an i-face P_{i} of P the dimension dim(W ∩ P_{i}) = i. The following equality of the varieties holds:

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

and, moreover, this variety is a nonempty smooth compact hypersurface in \overline{P}_{i}. Besides,

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

Proof. First we prove the inclusion

(K′_{i} ∩ P_{i}) ⊃ {g = μ} ∩ {f_{k_{1}+1} > 0, …, f_{k} > 0} ∩ P_{i}.

We have

{f_{k_{1}+1} > 0, …, f_{k} > 0} ∩ P_{i} = {f = 0, f_{k_{1}+1} > 0, …, f_{k} > 0} ∩ P_{i} = W ∩ P_{i}

since dim(W ∩ P_{i}) = i. By Lemma 5,

({f = 0, f_{k_{1}+1} > 0, …, f_{k} > 0} ∩ P_{i}) ⊂ (K_{i} ∩ P_{i}).

Intersecting both sides with the variety {g = μ}, we obtain the ⊃ inclusion.

To prove the inclusion ⊂ observe that f_{j} is nonnegative everywhere on K_{i} for each k_{1} + 1 ≤ j ≤ k because K_{i} ⊂ cl(W) (see Section 3).

On the other hand, f_{j} is nonzero everywhere on K′_{i} for k_{1} + 1 ≤ j ≤ k since f_{k_{1}+1} ⋯ f_{k} = μ. Thus, K′_{i} ⊂ {f_{k_{1}+1} > 0, …, f_{k} > 0} which proves ⊂ inclusion.

Now let us prove that K′_{i} ∩P_{i} is a nonempty smooth hypersurface in \overline{P}_{i}. Observe that K′_{i} ∩ P_{i} is bounded because P is compact, besides K′_{i} ∩ P_{i} is closed since its closure

K′_{i} ∩ cl(P_{i}) = K′_{i} ∩ \overline{P}_{i} ⊂ \{f_{k_{1}+1} > 0, …, f_{k} > 0\} ∩ \overline{P}_{i} = W ∩ \overline{P}_{i} = W ∩ P_{i} ⊂ P_{i}.

Since dim({f_{k_{1}+1} > 0, …, f_{k} > 0}∩P_{i}) = i, each connected component of the set {f_{k_{1}+1} > 0, …, f_{k} > 0\}∩P_{i} contains a connected component of the smooth hypersurface \{g = μ\}∩\overline{P}_{i} (in \overline{P}_{i}) due to Morse theory (see [Hi 76]) and in view of (a). Moreover, each connected component of the hypersurface \{g = μ\} ∩ \overline{P}_{i} either lies completely in the set \{f_{k_{1}+1} > 0, …, f_{k} > 0} ∩ P_{i} or does not intersect this set.

Finally, the inequality

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

immediately follows from (b). The lemma is proved.

The next section is dedicated to the proof of the following lemma.

Lemma 10. The number of i-faces P_{i} of P such that K′_{i} ∩ P_{i} is a nonempty compact smooth hypersurface in \overline{P}_{i} and

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

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

Theorem 2 immediately follows from Lemmas 9 and 10.

5. Extremal points of a linear function on K′_{i}

Take a linear form L = γ_{1}X_{1} + ⋯ + γ_{n}X_{n} with generic coefficients γ_{1}, …, γ_{n} ∈ R. Fix P_{i} satisfying the conditions of Lemma 10 and denote by L^{(P_{i})} the restriction of L on \overline{P}_{i}. Then L^{(P_{i})} attains its maximal value, say θ_{0}^{(P_{i})}, on the compact set K′_{i} ∩ P_{i}. Since L^{(P_{i})} is a generic linear form on \overline{P}_{i} as well, the following two properties are fulfilled:

(i) L^{(P_{i})} attains the value θ_{0}^{(P_{i})} at a unique point v ∈ K′_{i} ∩ P_{i} (cf. [Hi 76]);

(ii) the point v does not belong to cl(K′_{i} \ P_{i}) (cf. the conditions of Lemma 10).

Indeed, the semialgebric set of linear forms on \overline{P}_{i} for which the properties (i), (ii) fail, has dimension less than the dimension of the set of all linear forms on \overline{P}_{i}, and thus for the generic form L the properties (i), (ii) are valid.

Denote by V a connected component of K′_{i} ∩ P_{i} which contains v. The property (ii) implies that there exists 0 < r ∈ R such that B_{v}(r) ∩ K′_{i} = B_{v}(r) ∩ V. Thus, L attains a local isolated maximum on K′_{i} at the point v by the property (i). Hence, there exists an element 0 < ζ^{(P_{i})} ∈ R such that the values of L on the set ∂B_{v}(r/2) ∩ K′_{i} are less than θ_{0}^{(P_{i})} − ζ^{(P_{i})}.

Lemma 11. The linear form L attains its maximal value θ^{(P_{i})} on the set

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

(say, at a point w) and the values of L on the set

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

are less than st_{0}(θ^{(P_{i})}) − ζ^{(P_{i})}. Moreover, st_{0}(θ^{(P_{i})}) = θ_{0}^{(P_{i})} and st_{0}(w) = v ∈ P_{i}.

Proof. Due to Lemma 8 and the Remark after Lemma 3 from Section 2, we have:

st_{0}cl(K_{i} ∩ {|g − μ| < ε_{1}}) = K′_{i}.

By the transfer principle, L attains its maximum θ^{(P_{i})} on the closed bounded set cl(K_{i} ∩ {|g − μ| < ε_{1}}) ∩ cl(B_{v}(r/2)) at some point w. Then st_{0}(θ^{(P_{i})}) = θ_{0}^{(P_{i})} and st_{0}(w) = v (due to (i)).

Since

st_{0}(cl(K_{i} ∩ {|g − μ| < ε_{1}}) ∩ ∂B_{v}(r/2)) ⊂ K′_{i} ∩ ∂B_{v}(r/2)

we obtain the second statement of the lemma from the defining property of ζ^{(P_{i})}. Lemma is proved.

Lemma 11 states that L attains a local maximum on the set cl(K_{i} ∩ {|g − μ| < ε_{1}}) at a point w such that st_{0}(w) ∈ P_{i}. In order to estimate the number of such local maximum values of L we shall now construct a smooth hypersurface which is infinitely close to cl(K_{i} ∩ {|g − μ| < ε_{1}}). After that it will be sufficient to bound the number of local maxima of L on this smooth hypersurface.

For a point y denote the coordinates of the gradient

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

(cf. Definition). The set K_{i}∩{|g−μ| < ε_{1}} 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} ⊂ R_{3}^{n}, 1 ≤ i_{0} ≤ n − i

for some algebraic functions p_{1}, …, p_{s} of the quadratic-irrational type introduced in Section 1, i.e., polynomials (with coefficients from R_{2}) 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 semialgebraic sets

U_{0}^{(i_{0})} = {ε_{5}^{2} > (f − ε_{3})^{2}, u_{i_{0}}^{2} > ε_{4}, p_{1} > ε_{4}, …, p_{s} > ε_{4}} ⊂ R_{5}^{n}

and

U^{(i_{0})} = {q = ε_{6}} ∩ (U_{0}^{(i_{0})})^{(R_{6})} ⊂ R_{6}^{n}.

Lemma 12 (cf. Lemmas 1, 4 in [GV 92]).

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

Proof. Let us first show that to prove the lemma it is sufficient to establish the equality

st_{5}(U^{(i_{0})}) = ∂U_{0}^{(i_{0})}.  (4)

Indeed, due to Lemma 3a),

st_{3}(∂U_{0}^{(i_{0})}) ⊂ st_{3}(cl(U_{0}^{(i_{0})})) = cl(U^{(i_{0})}),

thus, due to (4), st_{3}(U^{(i_{0})}) ⊂ cl(U^{(i_{0})}).

On the other hand, cl(U^{(i_{0})}) = ∂(U^{(i_{0})}) because U^{(i_{0})} ⊂ {f = ε_{3}} and thereby U^{(i_{0})} contains no internal points. Hence, Lemma 3b) implies that cl(U^{(i_{0})}) ⊂ st_{3}(∂U_{0}^{(i_{0})}). It follows from (4) that cl(U^{(i_{0})}) ⊂ st_{3}(U^{(i_{0})}). This would prove the lemma, provided that (4) holds.

Now we prove (4) starting with the inclusion ⊂.

Let a point y ∈ U^{(i_{0})} and the standard part x = st_{5}(y) be definable. Then q(x) = 0 and

ε_{5}^{2} ≥ (f − ε_{3})^{2}, u_{i_{0}}^{2} ≥ ε_{4}, p_{1} ≥ ε_{4}, …, p_{s} ≥ ε_{4}.

Suppose that x ∉ ∂U_{0}^{(i_{0})}. Therefore there exists 0 < r_{0} ∈ R_{5} such that either B_{x}(r_{0}) ⊂ U_{0}^{(i_{0})} or B_{x}(r_{0}) ∩ U_{0}^{(i_{0})} = ∅.

If B_{x}(r_{0}) ⊂ U_{0}^{(i_{0})} we get a contradiction with q(x) = 0.

If B_{x}(r_{0}) ∩ U_{0}^{(i_{0})} = ∅ we conclude that the intersection B_{x}(r_{0}) ∩ (U_{0}^{(i_{0})})^{(R_{6})} = ∅. Since y belongs to this intersection we again get a contradiction which proves the inclusion ⊂ in (4).

To prove the inclusion ⊃ in (4) take a point x ∈ ∂U_{0}^{(i_{0})}. Observe that q is positive everywhere on U_{0}^{(i_{0})} and q vanishes everywhere on ∂U_{0}^{(i_{0})}, in particular q(x) = 0.

Suppose that x ∉ st_{5}(U^{(i_{0})}). Then there exists 0 < r_{1} ∈ R_{5} such that B_{x}(r_{1})∩U^{(i_{0})} = ∅ (cf. the proof of Lemma 2). Consider the decomposition of the intersection

B_{x}(r_{1}) ∩ U_{0}^{(i_{0})} = ⋃_{j} U_{j}

into its connected components (which are also semialgebraic sets and there is a finite number of them, see e.g. [GV 88]). Since x ∈ cl(B_{x}(r_{1}) ∩ U_{0}^{(i_{0})}) there is j_{0} for which x ∈ cl(U_{j_{0}}).

Observe that in the set U_{0}^{(i_{0})} ⊂ {u_{i_{0}}^{2} > 0} all the square roots (3) are positive. Therefore, by the transfer principle, all quadratic-irrational functions p_{1}, …, p_{s} are continuous in U_{0}^{(i_{0})}, hence q is continuous. All the values of the continuous function q on U_{j_{0}} form a connected semialgebraic subset Ξ ⊂ R_{5}. So, Ξ is an interval (or a point) with endpoints ξ_{1}, ξ_{2} ∈ R_{5}, ξ_{1} ≤ ξ_{2}, the set Ξ could be either closed, either open, or semi-open. Observe that ξ_{1} ≥ 0 because U_{j_{0}} ⊂ U_{0}^{(i_{0})}. On the other hand, ξ_{1} = 0 since q(x) = 0 and x ∈ cl(U_{j_{0}}). Obviously, ξ_{2} > 0. Due to the transfer principle, q attains on the set U_{j_{0}}^{(R_{6})} all the values from the interval (0, ξ_{2})^{(R_{6})}. In particular, there exists a point y ∈ U_{j_{0}}^{(R_{6})} such that q(y) = ε_{6}. Then y ∈ B_{x}(r_{1}) ∩ U^{(i_{0})}. The obtained contradiction completes the proof of the lemma.

Lemma 13. For a certain 1 ≤ i_{0} ≤ n − i the linear form L attains its maximal value θ_{1}^{(P_{i})} on the set cl(U^{(i_{0})}) ∩ B_{v}(r/2) at a certain point w_{1}, and the values of L on the set cl(U^{(i_{0})}) ∩ ∂B_{v}(r/2) are less than st_{0}(θ_{1}^{(P_{i})}) − ζ^{(P_{i})}. Moreover, st_{3}(θ_{1}^{(P_{i})}) = θ^{(P_{i})} and st_{0}(w_{1}) = v ∈ P_{i}.

Proof. Since

K_{i} ∩ {|g − μ| < ε_{1}} = ⋃_{1≤i_{0}≤n−i} U^{(i_{0})}

there is 1 ≤ i_{0} ≤ n − i such that w ∈ cl(U^{(i_{0})}) (see Lemma 11). The linear form L attains its maximum θ_{1}^{(P_{i})} on the bounded closed set cl(U^{(i_{0})}) ∩ cl(B_{v}(r/2)) at a point w_{1}. Using Lemma 12 and the equaliy st_{3}(U^{(i_{0})}) = st_{3}(cl(U^{(i_{0})})) (see the Remark in Section 2), we get: st_{3}(θ_{1}^{(P_{i})}) = θ^{(P_{i})}. Due to (i), st_{0}(w_{1}) = v.

The values of L on the set cl(U^{(i_{0})}) ∩ ∂B_{v}(r/2) are less than θ_{0}^{(P_{i})} − ζ^{(P_{i})} due to the similar statement in Lemma 11, taking into the account that

st_{3}(cl(U^{(i_{0})}) ∩ ∂B_{v}(r/2)) ⊂ ∂B_{v}(r/2).

Lemma is proved.

Since w_{1} is a local maximum of L on the set cl(U^{(i_{0})}) we obtain the following corollary.

Corollary. The number of i-faces P_{i} satisfying the conditions of Lemma 10 does not exceed the number of all the values of local maxima of the linear form L on the set

⋃_{1≤i_{0}≤n−i} cl(U^{(i_{0})}).

Lemma 14. U^{(i_{0})} is a smooth closed hypersurface, namely for each point x ∈ U^{(i_{0})} there is a neighborhood of x in which U^{(i_{0})} is defined by the equation q = ε_{6} and the gradient grad_{x}(q − ε_{6}) does not vanish.

Proof. First we prove that cl(U^{(i_{0})}) = U^{(i_{0})}. Let a point x ∈ cl(U^{(i_{0})}). Then

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

Neither among the latter inequalities could convert into an equality because q(x) = ε_{6} ≠ 0, hence x ∈ U^{(i_{0})}.

Since in the open semialgebraic set {u_{i_{0}}^{2} > 0} all the square roots (3) are positive, all algebraic functions p_{1}, …, p_{s} occuring in U_{0}^{(i_{0})} are smooth, hence q is smooth as well (sf. proof of Lemma 12). Because of Lemma 4, ε_{6} is not a critical value of q in the set {u_{i_{0}}^{2} > 0}. Lemma is proved.

Finally, let us prove the following lemma.

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

Proof. Because of Lemma 14, the number of local maxima of L on U^{(i_{0})} 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\} ⊂ R_{6}^{n}

(by the Lagrange multiplier theorem, see, e.g., Ch. 4 in [Th 77] and taking into the account the transfer principle).

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 polynomial by Q ∈ R_{5}[X_{1}, …, X_{n}, Z_{1}, …, Z_{n−i}] (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}^{2n−i}.

Consider the linear projection

ρ : R_{6}^{2n−i} ⟶ R_{6}^{n}, ρ(X_{1}, …, X_{n}, Z_{1}, …, Z_{n−i}) = (X_{1}, …, X_{n}).

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

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

This completes the proof of the lemma.

Lemma 15 together with Corollary to Lemma 13 imply Lemma 10 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.

7. Complexity lower bound for algebraic computation trees

Now we show how to extend the obtained complexity lower bound from decision to computation trees and thereby, to prove Theorem 1′.

Let an algebraic computation tree T of the depth k test membership to a polyhedron P. Fix some branch in T with the output “yes”, and denote by f_{1}, … f_{k} ∈ R[X_{1}, … X_{n}] the testing polynomials along this branch. Then there is a sequence of polynomials h_{1}, …, h_{k} such that h_{i} ∈ R[X_{1}, …, X_{n}, Z_{1}, …, Z_{i−1}] with deg(h_{i}) ≤ 2 and f_{i} = h_{i}(X_{1}, … X_{n}, f_{1}, …, f_{i−1}) for 1 ≤ i ≤ k. (In fact the polynomials h_{i} correspond the elementary arithmetic operations and have a simple structure, but we use only that deg(h_{i}) ≤ 2). For this branch a semialgebraic set

W = {f_{1}σ_{1}0, …, f_{k}σ_{k}0} ⊂ P

of the accepted points is assigned, where σ_{1}, …, σ_{k} ∈ {=, >} (see Introduction). Consider a semialgebraic set

W = {Z_{i} = h_{i}(X_{1}, …, X_{n}, Z_{1}, …, Z_{i−1}), 1 ≤ i ≤ k; Z_{1}σ_{1}0, …, Z_{k}σ_{k}0} ⊂ R^{n+k}

which can be treated as the “graph” of the branch. Denote by π : R^{n+k} ⟶ R^{n} the natural projection and by ρ : R^{n} ⟶ R^{n+k} the (graph) mapping ρ(x) = (x, f_{1}(x), …, f_{k}(x)). Then π(W) = W and ρ(W) = W, therefore the semialgebraic sets W and W are polynomially isomorphic. By the same token, the polyhedron P is isomorphic to its ρ-image P = ρ(P). Actually, P satisfies the following definition.

Definition. A subset P_{1} ⊂ R^{m} is called a distorted (closed) polyhedron if there exist polynomials g_{1}, …, g_{s} ∈ R[X_{1}, …, X_{m}] such that:

(1) zero is a noncritical value of g_{i} for every 1 ≤ i ≤ s;

(2) the smooth hupersurfaces {g_{i} = 0} intersect transversally, i.e., at any point x ∈ R^{m} the gradient vectors grad(g_{i_{j}})(x) are linearly independent for all i_{j} such that g_{i_{j}}(x) = 0. Finally,

P_{1} = {g_{1} ≥ 0, … g_{s_{1}} ≥ 0, g_{s_{1}+1} = ⋯ = g_{s} = 0}.

A (distorted) face of P_{1} is a connected component of a (nonempty) semialgebraic set of the form

{g_{i} = 0, i ∈ I; g_{j} > 0, j ∉ I; g_{s_{1}+1} = ⋯ = g_{s} = 0} ⊂ P_{1}

for a subset of indices I ⊂ {1, …, s_{1}}.

We say that a semialgebraic set

W_{1} = {f′_{1} = ⋯ = f′_{t_{1}} = 0, f′_{t_{1}+1} > 0, …, f′_{t} > 0} ⊂ P_{1}

with deg(f′_{j}) ≤ d touches a (distorted) face p_{1} of P_{1} if dim(p_{1} ∩ W_{1}) = dim(p_{1}). Similar to the proof of the Theorem 2 one could prove the following bound.

Theorem 2′. The number of the faces of P_{1} touched by W_{1} does not exceed (dtm)^{O(m)}.

Observe that P ⊂ R^{n+k} is a distorted polyhedron. We apply Theorem 2′ to P and the set W, taking into the account that a face p of P is touched by W if and only if the (distorted) face ρ(p) of P = ρ(P) is touched by ρ(W) = W. Therefore, the number of touched by W faces of P does not exceed (4k(n + k))^{O(n+k)} ≤ (kn)^{O(n+k)}. Finally, as in the introduction, we get the upper bound N < 3^{k}(kn)^{O(n+k)} ≤ (kn)^{O(n+k)} on the number N of the faces of P which implies the lower bound k ≥ Ω(log N/ log log N) provided that N > n^{c_{1}n} for a suitable c_{1}, and thus, Theorem 1′. Note, that if the restriction N > n^{c_{1}n} is not fulfilled, the bound log N/ log log N grows slower than O(n).

An interesting open problem is to get rid of the denominator log log N in the lower bound.

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, 548-552.

[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.

[MMP 96] J. l. Montaña, J. E. Morais, and L. M. Pardo “Lower bounds for arithmetic networks 2: sum of Betti numbers,” Appl. Algebra in Eng. Comm. Comp., V. 7, 1996, 41-51.

[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.