Randomized Complexity Lower Bound for Arrangements and Polyhedra

D. Grigoriev

IRMAR, Université de Rennes Campus de Beaulieu, 35042 Rennes, cedex France dima@maths.univ-rennes1.fr

The complexity lower bound Ω(log N) for randomized computation trees is proved for recognizing an arrangement or a polyhedron with N faces. This provides in particular, the randomized lower bound Ω(n log n) for the DISTINCTNESS problem and generalizes [11] where the randomized lower bound Ω(n^{2}) was ascertained for the KNAPSACK problem. The core of the method is an extension of the lower bound from [8] on the multiplicative complexity of a polynomial.

Introduction.

The complexity lower bounds for deterministic algebraic computation trees were obtained in [26], [2], [4], [30], [31], [22] where the topological methods were developed. In particular, these methods provide the lower bound Ω(log N) for recognizing (a membership to) a union of planes (of different dimensions) with N faces, under a face we mean any nonempty intersection of several among these planes. As consequences we obtain the lower bound Ω(n log n) for the DISTINCTNESS problem ⋃_{1≤i<j≤n}{X_{i} = X_{j}} ⊂ IR^{n},

EQUALITY SET problem {(x_{1}, …, x_{n}, y_{1}, …, y_{n}) : (x_{1}, …, x_{n}) is a permutation of (y_{1}, …, y_{n})} ⊂ IR^{2n} and the lower bound Ω(n^{2}) for the KNAP-SACK problem ⋃_{I⊂{1,...,n}} {∑_{i∈I}x_{i} = 1} ⊂ IR^{n}. In [14], [15] a differential-

geometric approach for recognizing polyhedra (to which the mentioned topological methods are not applicable) was proposed which gives the lower bound Ω(log N/ log log N) where N is the number of faces of the polyhedron.

The first results on the randomized computation trees (RCT) appeared in [24], [20], [9], [10] but for decade an open problem remained, to obtain nonlinear complexity lower bounds for recognizing natural problems by RCT. In [13] for the first time the nonlinear lower bound was obtained for somewhat weaker computational model of the randomized algebraic decision trees in which the testing polynomials in the branching nodes are of a fixed degree, rather than the computation trees in which the testing polynomials are computed along the path of the computation, so they could have in principle an exponential degree. The approach of [13] provides the lower bound Ω(log N) for recognizing an arrangement, i.e. a union of hyperplanes, and for recognizing a polyhedron, where N is again the number of faces. In particular, this leads to the lower bound Ω(n log n) for the DISTINCTNESS problem and Ω(n^{2}) for the KNAPSACK problem. For the EQUALITY SET problem a complexity lower bound on a randomized algebraic decision tree seems to be an open question.

But the method of [13] does not provide a lower bound for more interesting model of RCT. Only in [11] a method was developed which gives in particular, a lower bound Ω(n^{2}) for the KNAPSACK problem on RCT. This method relies on the obtained in [11] lower bound on the multiplicative border complexity of polynomials. The lower bound Ω(log N) of [11] holds for arrangements or polyhedra which satisfy some special conditions which fail, for example, for the DISTINCTNESS problem.

In [8] the proposed lower bound Ω(log N) was proved for the randomized algebraic computation trees over an arbitrary field of zero characteristic, here the computation branches according to the signs {=, ≠} unlike the more customary computation trees over the reals, studied in all previously mentioned papers including the present one, which branch according to the signs {≤, >}. The core of the method of [8] was the lower bound Ω(log N) on the multiplicative complexity of a polynomial (see e.g. [27]), where N is the number of the faces of an arrangement on which the polynomial vanishes.

In the present paper the latter lower bound Ω(log N_{1}) on the multiplicative complexity of a polynomial is extended (see the corollary in section 2) to a modified invariant N_{1} of an arrangement, namely, the number of so-called strongly singular faces (see section 1) of the arrangement (now the polynomial does not necessary vanish on the arrangement). Relying on this lower bound on the multiplicative complexity, the proof of the complexity lower bound Ω(log N) for RCT recognizing an arrangement or a polyhedron with N faces (see the theorem in section 3) becomes much simpler than the related ones in [13], [11]. In particular, this gives the lower bound Ω(n log n) for RCT recognizing the DISTINCTNESS problem. The construction of RCT with the linear complexity O(n) for the EQUALITY SET problem from [5] shows that the condition imposed in the present paper (as well as in [8]) that the recognized set is an arrangement, so a union of hyperplanes, rather than a union of planes of greater than 1 codimensions as in the EQUALITY SET problem, is essential. In the last section 4 we generalize the construction of [5] and design a RCT for recognizing the following problem {(x_{1}, …, x_{n}, y_{1}, …, y_{m}) : each of the both differences of the multisets {x_{1}, …, x_{n}} and {y_{1}, …, y_{m}} contains at most k elements } ⊂ IR^{n+m} which has a linear complexity when k is a constant. For arbitrary n, m the randomized complexity of this problem remains to be an open question.

Let us also mention the paper [12] where a complexity lower bound was established for the randomized analytic decision trees (rather than for more customary algebraic ones) and also the paper [7] where a lower bound was ascertained for a randomized parallel computational model (rather than a sequential model considered in the quoted papers including the present one).

1 Strongly singular faces of an arrangement with respect to a polynomial.

By F we denote a field of zero characteristic. Let H_{1}, …, H_{m} ⊂ F^{n} be hyperplanes and let Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} have the dimension dim Γ = k, so Γ is k-face of the arrangement S = H_{1} ∪ ⋯ ∪ H_{m}.

Fix arbitrary coordinates Z_{1}, …, Z_{k} in Γ. Then treating H_{i_{1}}, …, H_{i_{n−k}} as the coordinate hyperplanes of the coordinates Y_{1}, …, Y_{n−k}, one gets the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} in F^{n}. The next construction of the leading terms of a polynomial is similar to [13], [11].

For any polynomial f(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}] following [13], [11] define its leading term

αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}

0 ≠ α ∈ F with respect to the coordinate system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} as the minimal term in the lexicographical ordering Z_{1} > ⋯ > Z_{k} > Y_{1} > ⋯ > Y_{n−k}, namely as follows. First take the minimal integer m_{n−k} such that Y_{n−k}^{m_{n−k}} occurs in the terms of f = f^{(0)}. Consider the polynomial

0 ≢ f^{(1)} = (\frac{f}{Y_{n−k}^{m_{n−k}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}, 0) ∈
F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}]

which could be viewed as a polynomial on the hyperplane H_{i_{n−k}}. Observe that m_{n−k} depends only on H_{i_{n−k}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}, since a linear transformation of the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1} changes the coefficients (being the polynomials from F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}]) of the expansion of f in the variable Y_{n−k}, and a coefficient vanishes identically if and only if it vanishes identically after the transformation. Then f^{(1)} is the coefficient of the expansion of f at the power Y_{n−k}^{m_{n−k}}.

Second, take the minimal integer m_{n−k−1} such that Y_{n−k−1}^{m_{n−k−1}} occurs in the terms of f^{(1)}. In other words, Y_{n−k−1}^{m_{n−k−1}} is the minimal power of Y_{n−k−1} occurring in the terms of f in which occurs the power Y_{n−k}^{m_{n−k}}. Therefore, m_{n−k}, m_{n−k−1} depend only on the hyperplanes H_{n−k}, H_{n−k−1} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}, since (as above) a linear transformation of the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2} changes the coefficients (being the polynomials from F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}]) of the expansion of f in the variables Y_{n−k}, Y_{n−k−1} and a coefficient vanishes identically if and only if it vanishes identically after the transformation. Denote by 0 ≢ f^{(2)} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}] the coefficient of the expansion of f at the monomial Y_{n−k−1}^{m_{n−k−1}} Y_{n−k}^{m_{n−k}}. Obviously

f^{(2)} = (\frac{f^{(1)}}{Y_{n−k−1}^{m_{n−k−1}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}, 0)

One could view f^{(2)} as a polynomial on the (n−2)-dimensional plane H_{i_{n−k}} ∩ H_{i_{n−k−1}}.

Continuing in the similar way, we obtain consecutively the (non-negative) integers m_{n−k}, m_{n−k−1}, …, m_{1} and the polynomials

0 ≢ f^{(l)} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l}]

1 ≤ l ≤ n − k, by induction on l. Herewith, Y_{n−k−l+1}^{m_{n−k−l+1}} is the minimal power of Y_{n−k−l+1} occurring in the terms of f, in which occurs the monomial Y_{n−k−l+2}^{m_{n−k−1+2}} ⋯ Y_{n−k}^{m_{n−k}} for each 1 ≤ l ≤ n − k. Notice that m_{n−k}, …, m_{n−k−l} depend only on the hyperplanes H_{i_{n−k}}, …, H_{i_{n−k−l}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}. Then f^{(l)} is the coefficient of the expansion of f at the monomial Y_{n−k−l+1}^{m_{n−k−l+1}} ⋯ Y_{n−k}^{m_{n−k}} and

f^{(l+1)} = (\frac{f^{(l)}}{Y_{n−k−l}^{m_{n−k−l}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}, 0)

Thus, f^{(l)} depends only on H_{i_{n−k}}, …, H_{i_{n−k−l}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}. One could view f^{(l)} as a polynomial on the (n − l) dimensional plane H_{i_{n−k}} ∩⋯∩H_{i_{n−k−l+1}}. Continuing, we define also m′_{k}, …, m′_{1}. Observe that the leading term lm(f^{(l)}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k−l}^{m_{n−k−l}}, we refer to this equality as the maintenance property (see also [13], [11]).

From now on the construction and the definitions differ from the ones in [13], [11].

For any polynomial g ∈ F [X_{1}, …, X_{n}] one can rewrite it in the coordinates \overline{g}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) and expand \overline{g} = g_{s} + g_{s+1} + ⋯ + g_{s_{1}}, where g_{j} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}], s ≤ j ≤ s_{1} is homogeneous with respect to the variables Y_{1}, …, Y_{n−k} of degree j and g_{s} = g_{s}^{(0)} ≢ 0. Consider the leading term lm(g_{s}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}} and denote by Var^{(H_{i_{1}},...,H_{i_{n−k}})}(g) the number of positive (in other words, nonzero) integers among m_{n−k}, …, m_{1}, note that s = m_{1} + ⋯ + m_{n−k}. Although Var^{(H_{i_{1}},...,H_{i_{n−k}})}(g) depends on the order of the hyperplanes H_{i_{1}}, …, H_{i_{n−k}}, we will denote it sometimes by Var^{(Γ)}(g) for brevity when no ambiguity could happen. As we have shown above Var^{(H_{i_{1}},...,H_{i_{n−k}})}(g) is independent from the coordinates Z_{1}, …, Z_{k} of Γ. Obviously, Var^{(H_{i_{1}},...,H_{i_{n−k}})}(g) coincides with the number of 1 ≤ l ≤ n − k such that Y_{n−k−l}|g_{s}^{(l)}, the latter condition is equivalent to that the variety {g_{s}^{(l)} = 0} ∩ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{n−k−l+1}} contains the plane H_{i_{n−k}} ∩⋯∩H_{i_{n−k−l+1}} ∩H_{i_{n−k−l}} (being a hyperplane in H_{i_{n−k}} ∩⋯∩H_{i_{n−k−l+1}}).

It is convenient (see also [13], [11]) to reformulate the introduced concepts by means of infinitesimals in case of a real closed field F (see e.g. [19]). We say that an element ε transcendental over F is an infinitesimal (relative to F) if 0 < ε < a for any element 0 < a ∈ F. This uniquely induces the order on the field F (ε) of rational functions and further on the real closure F̃ (ε) (see [19]).

One could make the order in F̃ (ε) clearer by embedding it in the larger real closed field F ((ε^{1/∞})) of Puiseux series (cf. e.g. [16]). A nonzero Puiseux series has the form b = ∑_{i≥i_{0}} β_{i}ε^{i/δ}, where −∞ < i_{0} < ∞ is an integer, β_{i} ∈ F for every integer i; β_{i_{0}} ≠ 0 and the denominator of the rational exponents δ ≥ 1 is an integer. The order on F ((ε^{1/∞})) is defined as follows: sgn(b) = sgn(β_{i_{0}}). When i_{0} ≥ 1, then b is called an infinitesimal, when i_{0} ≤ −1, then b is called infinitely large. For any not infinitely large b we define its standard part st(b) = st_{ε}(b) ∈ F as follows: when i_{0} = 0, then st(b) = β_{i_{0}}, when i_{0} ≥ 1, then st(b) = 0. In the natural way we extend the standard part to the vectors from (F ((ε^{1/∞})))^{n} and further to subsets in this space.

Now let ε_{1} > ε_{2} ⋯ > ε_{n+1} > 0 be infinitesimals, where ε_{1} is an infinitesimal relative to IR; in general ε_{i+1} is an infinitesimal relative to IR(ε_{1}, …, ε_{i}) for all 0 ≤ i ≤ n. Denote the real closed field IR_{i} = IR ˜ (ε_{1}, …, ε_{i}), in particular, IR_{0} = IR. For an element b ∈ IR_{n+1} for brevity denote the standard part st_{i}(b) = st_{ε_{i+1}}(st_{ε_{i+2}} ⋯ (st_{ε_{n+1}}(b) ⋯)) ∈ IR_{i} (provided that it is definable).

Also we will use the Tarski’s transfer principle [29]. Namely, for two real closed fields F_{1} ⊂ F_{2} a closed (so, without free variables) formula in the language of the first-order theory of F_{1} is true over F_{1} if and only if this formula is true over F_{2}.

An application of Tarski’s transfer principle is the concept of the completion. Let F_{1} ⊂ F_{2} be real closed fields and Ψ be a formula (with quantifiers and, perhaps, with n free variables) of the language of the first-order theory of the field F_{1}. Then Ψ determines a semialgebraic set V ⊂ F_{1}^{n}. The completion V^{(F_{2})} ⊂ F_{2}^{n} is a semialgebraic set determined by the same formula Ψ (obviously, V ⊂ V^{(F_{2})}).

One could easily see that for any point (z_{1}, …, z_{k}) ∈ IR_{k}^{k} and a polynomial g ∈ IR[X_{1}, …, X_{n}] such that g_{s}^{(n−k)}(z_{1}, …, z_{k}) ≠ 0 (we utilize the introduced above notations) the following equality for the signs

σ_{1}^{m_{1}} … σ_{n−k}^{m_{n−k}} sgn(g_{s}^{(n−k)}(z_{1}, …, z_{k})) =
sgn(\overline{g}(z_{1}, …, z_{k}, σ_{1}ε_{k+1}ε_{n+1}, …, σ_{n−k}ε_{n}ε_{n+1}))  (1)

holds for any σ_{1}, …, σ_{n−k} ∈ {−1, 1}. For any 1 ≤ i ≤ n − k such that m_{i} = 0 (1) holds also for σ_{i} = 0, agreeing that 0^{0} = 1. Moreover, the following polynomial identity holds:

g_{s}^{(n−k)}(Z_{1}, …, Z_{k}) = st_{k} (\frac{\overline{g}(Z_{1}, …, Z_{k}, ε_{k+1}ε_{n+1}, …, ε_{n}ε_{n+1})}{ε_{k+1}^{m_{1}} ⋯ ε_{n}^{m_{n−k}}ε_{n+1}^{s}})

Now let F be an algebraically closed field of zero characteristic. Take a certain 0 < η ≤ 1 (it will be specified later). We call k-face Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} of the arrangement S strongly singular (with respect to a polynomial g ∈ F [X_{1}, …, X_{n}]) if Var^{(H_{i_{1}},...,H_{i_{n−k}})}(g) ≥ η(n − k). Denote by N the number of strongly singular k-faces of S with respect to g (since g will be fixed for the time being, in the sequel we omit mentioning of g in this context).

2 Multiplicative complexity and strongly singular faces.

Consider the graph (cf. [27], [18]) of the gradient map G = {(x, grad_{g}(x)) : x ∈ F^{n}\} ⊂ F^{2n} = \{(x_{1}, …, x_{n}, v_{1}, …, v_{n})\}, so v_{i} = \frac{∂g}{∂X_{i}} (x), 1 ≤ i ≤ n. The notion of the degree deg was extended in [17] to constructible sets in an affine space from the usual case of closed projective sets ([25], [23]). We are now able to formulate the main technical tool of this section (cf. theorem 1 [8]).

Lemma 1 For any 0 ≤ k ≤ n, 0 < η ≤ 1 and an arrangement S = H_{1} ∪ ⋯ ∪ H_{m} having N strongly singular k-faces with respect to a polynomial g ∈ F [X_{1}, …, X_{n}] over an algebraically closed zero-characteristics field F, the following bound holds: deg G ≥ Ω(N/(m^{(1−η)(n−k)}2^{4n}))

Proof. w.l.o.g. we assume that N ≥ 1, otherwise the lemma is trivial. We introduce a linear projection φ : F^{2n} → F^{n} where φ(X_{1}, …, X_{n}, V_{1}, …, V_{n}) = (X_{1}, …, X_{n}). Also we introduce a rational map ψ : F^{2n} → IP^{n^{2}+n−1} where IP^{n^{2}+n−1} is the projective space with the coordinates {W_{iℓ}}_{1≤i,ℓ≤n} : {W_{ℓ}}_{1≤ℓ≤n}, herewith ψ is given by the formulae W_{iℓ} = X_{i}V_{ℓ}, W_{ℓ} = V_{ℓ}, 1 ≤ i, ℓ ≤ n. Thus, ψ is defined for any point (x, v) ∈ F^{2n} such that v ≠ 0. In fact, ψ could be viewed as the composition of the following natural rational maps F^{2n} → F^{n} × (F^{n} − 0) → F^{n} × IP^{n−1} ↪ IP^{n} × IP^{n−1} ↪ IP^{n^{2}+n−1}, where the latter one is the Segre embedding ([25], [23]). Finally, we denote by σ : IP^{n^{2}+n−1} → IP^{n−1} the linear projection, where σ({W_{iℓ}} : {W_{ℓ}}) = {W_{ℓ}}. The role of σ is to distinguish the coordinates of the gradient.

For the time being fix a strongly singular k-face Γ = H_{i_{1}} ∩⋯∩H_{i_{n−k}} of g. We recall that for any point ν from Γ the chosen coordinates Y_{1}, …, Y_{n−k} vanish at ν, herewith H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes for Y_{1}, …, Y_{n−k}. We have an expansion \overline{g} = g_{s} + g_{s+1} + ⋯ + g_{s_{1}}, where the polynomial g_{j} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}], s ≤ j ≤ s_{1} is homogeneous of degree j with respect to the variables Y_{1}, …, Y_{n−k}, and g_{s} ≢ 0. Let Y_{ℓ_{1}}, …, Y_{ℓ_{p}}, p ≥ η(n − k) occur in lm(g_{s}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}. We remind that m_{1}, …, m_{n−k} do not depend on the coordinates Z_{1}, …, Z_{k}, thereby on a particular point ν from Γ; also g_{s}^{(n−k)} ∈ F [Z_{1}, …, Z_{k}] is the coefficient at Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}} of the expansion of g_{s}, herewith lm(g_{s}^{(n−k)}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}.

For the sake of simplifying the notations, we make a linear transformation of the coordinates X_{1}, …, X_{n} into Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} and the same linear transformation we apply also to the coordinates V_{1}, …, V_{n} (keeping for them the same notation). Then in the new coordinates G = {(z_{1}, …, z_{k}, y_{1}, …, y_{n−k}, v_{1}, …, v_{n}) : v_{i} = \frac{∂\overline{g}}{∂Z_{i}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}), 1 ≤ i ≤ k; v_{j+k} = \frac{∂\overline{g}}{∂Y_{j}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}), 1 ≤ j ≤ n − k\} and ψ is given by the same formulae W_{iℓ} = Z_{i}V_{ℓ}, W_{j+k,ℓ} = Y_{j}V_{ℓ}, W_{ℓ} = V_{ℓ} as above.

For a fixed point ν = (z_{1}, …, z_{k}, 0, …, 0) ∈ Γ consider (n−1)-dimensional plane P = P_{ν} = ψ(φ^{−1}(ν)) ⊂ IP^{n^{2}+n−1}. The following lemma is similar to lemma 1 [8].

Lemma 2 It holds dim(σ(\overline{ψ(G)} ∩ P)) ≥ η(n − k) − 1. Moreover, the linear (coordinate) functions W_{ℓ_{1}}, …, W_{ℓ_{p}} are algebraically independent on \overline{ψ(G)} ∩ P.

Proof. Take a point (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}) ∈ F^{n} and consider a line {t_{λ} = (z_{1}, …, z_{k}, λy_{1}, …, λy_{n−k})\}_{λ∈F} ⊂ F^{n}. Then \frac{∂\overline{g}}{∂Y_{ℓ}} (t_{λ}) = (\frac{∂g_{s}}{∂Y_{ℓ}} + \frac{∂g_{s+1}}{∂Y_{ℓ}} + ⋯ + \frac{∂g_{s_{1}}}{∂Y_{ℓ}} ) (t_{λ}) = λ^{s−1}(\frac{∂g_{s}}{∂Y_{ℓ}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k})+λg̃^{(ℓ)}), where g̃^{(ℓ)} ∈ F [λ, z_{1}, …, z_{k}, y_{1}, …, y_{n−k}], 1 ≤ ℓ ≤ n − k. Similar, \frac{∂\overline{g}}{∂Z_{i}} (t_{λ}) = λ^{s}ĝ^{(i)}, where ĝ^{(i)} ∈ F [λ, z_{1}, …, z_{k}, y_{1}, …, y_{n−k}]. Denote grad = (\frac{∂\overline{g}}{∂Z_{1}} , …, \frac{∂\overline{g}}{∂Z_{k}} , \frac{∂\overline{g}}{∂Y_{1}} , …, \frac{∂\overline{g}}{∂Y_{n−k}}).

Hence the point

ψ(t_{λ}, grad(t_{λ})) = λ^{s−1}(⋯: \frac{∂g_{s}}{∂Y_{ℓ}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}) + λg̃^{(ℓ)} : ⋯)

∈ ψ(G) ∩ P_{t_{λ}}

(provided that the point of the projective space is defined, i.e. grad(t_{λ}) ≠ 0). Divide all the coordinates of this point over their common factor λ^{s−1} and after that plug λ = 0. Then the resulting point (⋯: \frac{∂g_{s}}{∂Y_{ℓ}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}) : ⋯) ∈ \overline{ψ(G)} ∩ P_{ν} (provided that not all \frac{∂g_{s}}{∂Y_{ℓ}} (z_{1}, …, z_{k}, y_{1}, …, y_{n−k}) vanish).

For each 1 ≤ j ≤ ρ the leading term of the polynomial \frac{∂g_{s}}{∂Y_{ℓ_{j}}} (z_{1}, …, z_{k}, Y_{1}, …

, Y_{n−k}) equals to g_{s}^{(n−k)}(z_{1}, …, z_{k})m_{ℓ_{j}}Y_{1}^{m_{1}} ⋯ Y_{ℓ_{j}−1}^{m_{ℓ_{j} −1}}Y_{ℓ_{j}}^{m_{ℓ_{j}} −1}Y_{ℓ_{j}+1}^{m_{ℓ_{j} +1}} ⋯ Y_{n−k}^{m_{n−k}}, provided that g_{s}^{(n−k)}(z_{1}, …, z_{k}) ≠ 0 (recall that m_{ℓ_{j}} ≥ 1).

First we establish lemma 2 in case ρ = 1, then it suffices to verify that \overline{ψ(G)} ∩ P_{ν} ≠ ∅ because ρ ≥ η(n − k). Moreover, we prove that for any point w_{0} ∈ F^{n} we have \overline{ψ(G)} ∩ P_{w_{0}} ≠ ∅. Indeed, take any point w_{1} ∈ F^{n} for which the gradient grad(w_{1}) ≠ 0. Then grad does not vanish almost everywhere on the line {w_{λ} = w_{0} + λ(w_{1} − w_{0})}_{λ∈F}. Since (cf. above) the point ψ(w_{λ}, grad(w_{λ})) ∈ ψ(G) ∩ P_{w_{λ}}, provided that grad(w_{λ}) ≠ 0, we conclude that the limit of these points when λ → 0, belongs to \overline{ψ(G)} ∩ P_{w_{0}}, which is thereby, nonempty.

Now let ρ ≥ 2. If the statement of the lemma were wrong, there would exist a homogeneous polynomial h = ∑_{K} h_{K}W_{ℓ_{1}}^{K_{1}} ⋯ W_{ℓ_{ρ}}^{K_{ρ}} ∈ F [W_{ℓ_{1}}, …, W_{ℓ_{ρ}}] vanishing on \overline{ψ(G)} ∩ P_{ν} (or by the same token on σ(\overline{ψ(G)} ∩ P_{ν})). Therefore, h(\frac{∂g_{s}}{∂Y_{ℓ_{1}}} (z_{1}, …, z_{k}, Y_{1}, …, Y_{n−k}), …, \frac{∂g_{s}}{∂Y_{ℓρ}} (z_{1}, …, z_{k}, Y_{1}, …, Y_{n−k})) = 0. De-

note Y^{M} = Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}. The leading monomial of the product (\frac{∂g_{s}}{∂Y_{ℓ_{1}}} (z_{1}, …,

z_{k}, Y_{1}, …, Y_{n−k}))^{K_{1}} ⋯ (\frac{∂g_{s}}{∂Y_{ℓρ}} (z_{1}, …, z_{k}, Y_{1}, …, Y_{n−k}))^{K_{ρ}} equals to (\frac{Y^{M}}{Y_{ℓ_{1}}} )^{K_{1}} ⋯

(\frac{Y^{M}}{Y_{ℓρ}} )^{K_{ρ}}.

For any two distinct integer multiindices (K_{1}, …, K_{ρ}) ≠ (Q_{1}, …, Q_{ρ})

we have (\frac{Y^{M}}{Y_{ℓ_{1}}} )^{K_{1}} ⋯ (\frac{Y^{M}}{Y_{ℓρ}} )^{K_{ρ}} ≠ (\frac{Y^{M}}{Y_{ℓ_{1}}} )^{Q_{1}} ⋯ (\frac{Y^{M}}{Y_{ℓρ}} )^{Q_{ρ}}. Indeed, otherwise (\frac{Y^{M}}{Y_{ℓ_{1}}} )^{K_{1}−Q_{1}} ⋯ (\frac{Y^{M}}{Y_{ℓρ}} )^{K_{ρ}−Q_{ρ}} = 1, i.e. Y^{M(K_{1}−Q_{1}+···+K_{ρ}−Q_{ρ})} = Y_{ℓ_{1}}^{K_{1}−Q_{1}} ⋯

Y_{ℓ_{ρ}}^{K_{ρ}−Q_{ρ}}, therefore the multiindices (K_{1}−Q_{1}, …, K_{ρ}−Q_{ρ}) = (K_{1}−Q_{1}+⋯+ K_{ρ} − Q_{ρ})(m_{ℓ_{1}}, …, m_{ℓ_{ρ}}) coincide, in particular, K_{1} − Q_{1} + ⋯ + K_{ρ} − Q_{ρ} ≠ 0, but the sums of the coordinates in both multiindices differ by the factor of m_{ℓ_{1}} + ⋯ + m_{ℓ_{ρ}} ≥ ρ ≥ 2.

The obtained contradiction proves lemma 2 for the points ν = (z_{1}, …, z_{k}, 0, …, 0) such that g_{s}^{(n−k)}(z_{1}, …, z_{k}) ≠ 0. Now observe that for any point u ∈ IP^{n^{2}+n−1} the set φ(ψ^{−1}(u)) consists of a single point when u ∈ ψ(F^{2n}) or else is empty. Thus, φψ^{−1} : \overline{ψ(F^{2n})} → F^{n} is a rational surjective map [25]. Finally, applying the theorem on dimension of fibers [25] to the restriction of the rational map φψ^{−1} : \overline{ψ(G)} ∩ (φψ^{−1})^{−1}Γ → Γ being surjective as was shown above, we complete the proof of lemma 2. □

Now we come back to the proof of lemma 1. Observe that \overline{ψ(G)} ∩ P ⊂ IP^{n^{2}+n−1} (where P = P_{ν} for an arbitrary point ν ∈ Γ, see above) is a closed projective variety and the projection σ is defined everywhere on this variety, so being a regular map, hence σ(\overline{ψ(G)} ∩ P) ⊂ IP^{n−1} is a closed projective variety (see [25], [23]).

There exists a subspace B ⊂ IP^{n−1} with the dimension dim B = ⌊n−η(n− k)⌋ such that dim(\overline{ψ(G)} ∩ σ^{−1}(B)) ≤ n − η(n − k) + 1 (actually, almost any subspace satisfies this property). This follows from the theorem of dimension of fibres [23] applying it to the rational dominating map σ : \overline{ψ(G)} → \overline{σ(\overline{ψ(G)})} and taking into account that dim \overline{ψ(G)} = dim G = n.

Since the intersection of two closed projective varieties of the complement dimensions (see lemma 2) B∩σ(\overline{ψ(G)}∩P) is not empty [25], [23], we conclude that σ^{−1}(B) ∩ \overline{ψ(G)} ∩ P ≠ ∅, for any point ν from any strongly singular kface Γ. Varying P = P_{ν} for different points ν from Γ, the latter implies in particular, that dim(σ^{−1}(B) ∩ \overline{ψ(G)}) ≥ k.

Therefore, the constructible set U = φ(ψ^{−1}(σ^{−1}(B) ∩ \overline{ψ(G)})) ⊂ F^{n} contains all strongly singular k-faces Γ. Observe that dim U ≤ dim(σ^{−1}(B) ∩ \overline{ψ(G)}) ≤ n − η(n − k) + 1 since φψ^{−1} is a rational map (cf. above).

For each strongly singular k-face Γ = H_{i_{1}} ∩⋯∩H_{i_{n−k}} successively choose j_{1}, j_{2}, … ∈ {i_{1}, …, i_{n−k}}, such that for every ℓ ≥ 0 we have dim(U∩H_{j_{1}}∩⋯∩ H_{j_{ℓ}} ∩ H_{j_{ℓ+1}}) ≤ dim(U ∩ H_{j_{1}} ∩ ⋯ ∩ H_{j_{ℓ}}) − 1 while dim(U ∩ H_{j_{1}} ⋯ ∩ H_{j_{ℓ}}) > k. After at most q ≤ n − η(n − k) + 1 − k steps we reach j_{1}, …, j_{q} for which dim(U ∩ H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}}) = k, thus Γ is an irreducible component of U ∩H_{j_{1}} ∩⋯∩H_{j_{q}}. Take also a (n−k)-dimensional plane Q ⊂ F^{n} transversal to all k_{1}-faces of S for all 0 ≤ k_{1} ≤ n and to all irreducible components of U ∩H_{j_{1}} ∩…∩H_{j_{q}} for all j_{1}, …, j_{q}. Then the point Q∩Γ, being an irreducible component of 0-dimensional variety U ∩ H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q, does not belong to other k-faces except Γ.

Consider constructible sets H_{i} = ψ(φ^{−1}(H_{i})), Q = ψ(φ^{−1}(Q)) ⊂ IP^{n^{2}+n−1}, 1 ≤ i ≤ m. Consider also

U = U_{j_{1},...j_{q}} = σ^{−1}(B) ∩ \overline{ψ(G)} ∩ H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q.  (2)

Then φ(ψ^{−1}(U)) = U ∩ H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q = {u_{1}, …, u_{κ}} ⊂ F^{n} is a finite collection of points. Therefore, every irreducible component of U is contained in one of the pairwise disjoint (n − 1)-dimensional planes ψ(φ^{−1}(u_{1})), …, ψ(φ^{−1}(u_{κ})) ⊂ IP^{n^{2}+n−1}, since the image of this irreducible component under the rational map φψ^{−1} : \overline{ψ(F^{2n})} → F^{n}, being a subset of \{u_{1}, …, u_{κ}\}, should be a point; moreover each of these planes contains a certain component of U.

Thus, deg (U) = deg (U_{j_{1},...,j_{q}}) ≥ κ; we define the degree of a constructible set as the degree of its projective closure \overline{U} [23], [25], i.e. the sum of the degrees of irreducible components of \overline{U}.

Taking the sum of the latter inequalities over all 1 ≤ j_{1}, …, j_{q} ≤ m, q ≤ (n − k)(1 − η) + 1 and observing that each strongly singular k-face Γ gives a contribution into the right side of one of these inequalities, we conclude that

∑_{1≤j_{1},...,j_{q}≤m;q≤(n−k)(1−η)+1} deg (U_{j_{1},...,j_{q}}) ≥ N  (3)

Another method for bounding from below the degree of a variety passing through a given set of points one can find in [28], but this method is not applicable here. To bound deg (U_{j_{1},...,j_{q}}) from above, we rely on the following lemma.

Lemma 3 Let an affine Zariski closed set V ⊂ F^{2n}. Then deg (ψ(V)) ≤ 2^{2n}deg (V).

Proof. (cf. the proof of theorem 1 [8]). First, one can reduce lemma to the case of an irreducible V. Since dim(\overline{ψ(V)} − ψ(V)) < dim(ψ(V)), there is a subspace R ⊂ IP^{n^{2}+n−1} with dim R = n^{2} + n − 1 − dim ψ(V) for which R∩ψ(V) consists of deg ψ(V) = deg \overline{ψ(V)} points (in fact, almost any subspace has deg ψ(V) common points with \overline{ψ(V)}, and almost any subspace has an empty intersection with \overline{ψ(V)} − ψ(V)). Because ψ(ψ^{−1}(R) ∩ V) = R ∩ ψ(V), the degree deg ψ(V) does not exceed the number of irreducible components of the variety ψ^{−1}(R) ∩ V, which in its turn is less or equal to deg (ψ^{−1}(R) ∩ V). Then we apply the Bezout inequality deg (ψ^{−1}(R)∩V) ≤ deg (ψ^{−1}(R))·deg V which was proved for locally closed sets in [17], rather than for the usual case of projective closed varieties with the complete intersection [23], [25]. The local closedness of ψ^{−1}(R) follows from the next paragraph.

It remains to bound deg (ψ^{−1}(R)). If R is determined by several linear equations of the form ∑_{1≤i,ℓ≤n} α_{iℓ}W_{iℓ} + ∑_{1≤ℓ≤n} β_{ℓ}W_{ℓ} = 0, then ψ^{−1}(R) is determined by the quadratic equations ∑_{1≤i,ℓ≤n} α_{iℓ}X_{i}V_{ℓ} + ∑_{1≤ℓ≤n} β_{ℓ}V_{ℓ} = 0 out of the plane L = {V_{1} = ⋯ = V_{n} = 0} on which ψ is not defined. One can choose 2n suitable linear combination of these equations ζ_{1}, …, ζ_{2n} ∈ F [X_{1}, …, X_{n}, V_{1}, …, V_{n}] such that the irreducible components of the locally closed set {ζ_{1} = ⋯ = ζ_{2n} = 0} − L ⊂ F^{2n} contain all the irreducible components of ψ^{−1}(R) and in addition, perhaps, few points, being its 0dimensional components (cf. also [6]). Hence deg (ψ^{−1}(R)) ≤ 2^{2n} again due to the Bezout inequality. This completes the proof of lemma 3.

Coming back to bounding deg (U_{j_{1},...,j_{q}}) from above, we note that H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q = ψ(φ^{−1}(H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q)) (cf. (2)) and H = φ^{−1}(H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q) ⊂ F^{2n} being a plane, so of degree 1. Applying lemma 3 we obtain the bound

deg (ψ(H)) ≤ 2^{2n}.  (4)

For every 1 ≤ i ≤ n consider a principle affine Zariski open chart A_{ℓ} = {W_{ℓ} ≠ 0} ⊂ IP^{n^{2}+n−1} and denote A = ∪_{1≤ℓ≤n}A_{ℓ}. Observe that σ^{−1}(B) ⊂ A is closed in A.

Let us also show that H_{j_{1}} ∩ ⋯ ∩ H_{j_{q}} ∩ Q = ψ(H) ⊂ ψ(F^{2n}) ⊂ A is closed in A. Indeed, H is given by a system of linear equations {h_{t} = ∑_{1≤i≤n} γ_{ti}X_{i} + γ_{t0} = 0}_{t} which depend only on X_{1}, …, X_{n}. We claim that ψ(H) =

A ∩ { ∑_{1≤i≤n} γ_{ti}W_{iℓ} + γ_{t0}W_{ℓ} = 0}_{t,1≤ℓ≤n} ∩ {W_{iℓ_{1}}W_{ℓ_{2}} = W_{iℓ_{2}}W_{ℓ_{1}}}_{1≤i,ℓ_{1},ℓ_{2}≤n}

The inclusion ⊂ is obvious. To prove the inverse inclusion take a point {w_{iℓ}}_{i,ℓ} : {w_{ℓ}}_{ℓ} from the set at the right side. Then w_{ℓ_{0}} ≠ 0 for a certain 1 ≤ ℓ_{0} ≤ n. From the equalities w_{iℓ_{1}}w_{ℓ_{2}} = w_{iℓ_{2}}w_{ℓ_{1}} we get that

\{w_{iℓ}\}_{i,ℓ} : \{w_{ℓ}\}_{ℓ} = ψ (\frac{w_{1ℓ_{0}}}{w_{ℓ_{0}}} , ⋯, \frac{w_{nℓ_{0}}}{w_{ℓ_{0}}} , w_{1}, …, w_{n}). Finally, the equalities

\{∑_{1≤i≤n} γ_{ti}w_{iℓ_{0}} + γ_{t0}w_{ℓ_{0}} = 0\}_{t} entail that (\frac{w_{1ℓ_{0}}}{w_{ℓ_{0}}} , ⋯, \frac{w_{nℓ_{0}}}{w_{ℓ_{0}}} , w_{1}, …, w_{n}) ∈ H, which proves the inverse inclusion of the claim and thereby the closedness of ψ(H) in A.

Let U = σ^{−1}(B)∩\overline{ψ(G)}∩ψ(H) = ∪_{j}U_{j} ⊂ A (cf. (2)) be the decomposition of U, being the intersection of three Zariski closed in A subsets as was just proved, into its irreducible components U_{j}. For every 1 ≤ i ≤ n we have the induced decomposition of the intersection

(σ^{−1}(B) ∩ A_{i}) ∩ (\overline{ψ(G)} ∩ A_{i}) ∩ (ψ(H) ∩ A_{i}) = ∪_{j}(U_{j} ∩ A_{i})

of three Zariski closed affine sets (in A_{i}) into its irreducible components U_{j} ∩ A_{i}, provided that U_{j} ∩ A_{i} ≠ ∅. Moreover, in the latter case the closure \overline{U_{j} ∩ A_{i}} = \overline{U_{j}} ⊂ IP^{n^{2}+n−1} because A_{i} is open in IP^{n^{2}+n−1}, in particular deg (U_{j} ∩ A_{i}) = deg U_{j}. Applying the affine version of the Bezout inequality [17], we obtain

∑_{j} deg U_{j} ≤ deg (σ^{−1}(B) ∩ A_{i})deg (\overline{ψ(G)} ∩ A_{i}).
deg (ψ(H) ∩ A_{i}) ≤ deg \overline{ψ(G)} · deg ψ(H)

where the summation ranges over j for which U_{j} ∩ A_{i} ≠ ∅. Summing up these inequalities for all 1 ≤ i ≤ n, we conclude

deg U = ∑_{j} deg U_{j} ≤ n · deg \overline{ψ(G)} · deg ψ(H)

which together with the bounds (3), (4) gives the inequality

N ≤ ( \begin{matrix}m \\ ⌊(n − k)(1 − η)⌋ + 1 \end{matrix} ) · (n − k)(1 − η)n · deg \overline{ψ(G)} · 2^{2n},

hence taking into account the inequality deg \overline{ψ(G)} ≤ 2^{2n}deg G following from lemma 3, we finally get

deg G ≥ Ω (\frac{N}{m^{(n−k)(1−η)}2^{4n}} ) ,

that completes the proof of lemma 1.

Corollary. (cf. corollary 1 [8]). Let a polynomial g ∈ F [X_{1}, …, X_{n}] have N strongly singular k-faces in an arrangement H_{1} ∪ ⋯ ∪ H_{m} ⊂ F^{n}. Then the multiplicative complexity C(g) ≥ 1/3(log N − (n − k)(1 − η) log m − 4n− const).

The results from [27], [1] imply that deg G ≤ 2^{3C(g)}, then make use of lemma 1.

3 Lower bound for randomized computation trees

Recall (see e.g. [2]) that in the computation tree (CT) testing polynomials are computed along paths using the elementary arithmetic operations. In particular, for a testing polynomial f_{i} ∈ IR[X_{1}, …, X_{n}] at the level i (assuming that the root has the zero level) we have the obvious bound on its complexity, a fortiori multiplicative complexity C(f_{i}) ≤ i. Under RCT (cf. [24], [20]) we mean a collection of CT T = {T_{α}} and a probabilistic vector p_{α} ≥ 0, ∑_{α} p_{α} = 1 such that CT T_{α} is chosen with the probability p_{α}. The depth of an RCT (treated as its complexity) is defined as the maximum of the depths of all T_{α}’s (actually the equivalent complexity classes one gets if to define the depth of RCT as the expectation of the depths of T_{α}’s, [24]). The main requirement is that for any input RCT gives a correct output with the probability 1 − γ > \frac{1}{2} (γ is called the error probability of RCT).

For a hyperplane H ⊂ IR^{n} by H^{+} ⊂ IR^{n} denote the closed halfspace {L_{H} ≥ 0}, where L_{H} is a certain linear function with the zero set H. For a family of hyperplanes H_{1}, …, H_{m} the intersection S^{+} = ∩_{1≤i≤m}H_{i}^{+} is called a polyhedron. An intersection Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} is called k-face of S^{+} if for each 1 ≤ l ≤ n − k + 1 we have dim(H_{i_{l}} ∩ ⋯ ∩ H_{i_{n−k}}) = dim(H_{i_{l}} ∩ ⋯ ∩ H_{i_{n−k}} ∩S^{+}) = k +l−1 (then clearly H_{i_{l}} ∩⋯∩H_{i_{n−k}} is (k +l−1)-face of S^{+}). Recall (see section 1) that Γ is k-face of the arrangement S = ∪_{1≤i≤m}H_{i} if dim Γ = k.

Now we are able to formulate the main result of this paper.

Theorem. For any positive constants c, c_{1}, c_{2} there exists c_{0} > 0 satisfying the following. Let for some k ≤ (1 − c_{1})n an arrangement S = S = ∪_{1≤i≤m}H_{i} or a polyhedron S = S^{+} = ∩_{1≤i≤m}H_{i}^{+} have at least c_{2}(m^{c(n−k)}) kfaces. Then for any RCT recognizing S, its depth is greater than c_{0}(n log m).

For a family of polynomials f_{1}, …, f_{t} ∈ IR[X_{1}, …, X_{n}] we define Var^{(Γ)}(f_{1}, …, f_{t}) to be the number of the variables among Y_{1}, …, Y_{n−k} (we utilize the notations introduced in section 1) which occur in at least one of the leading terms lm(f_{1,s_{1}}), …, lm(f_{t,s_{t}}), where H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes of the coordinates Y_{1}, …, Y_{n−k}, respectively; \overline{f}_{j}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) = f_{j}(X_{1}, …, X_{n}) and \overline{f}_{j} = f_{j,s_{j}} + f_{j,s_{j}+1} + ⋯, herewith f_{j,l} is homogeneous with respect to the variables Y_{1}, …, Y_{n−k} of degree l and f_{j,s_{j}} ≢ 0, 1 ≤ j ≤ t. Because the expansion into the homogeneous components \overline{f}_{1} ⋯ \overline{f}_{t} = (f_{1,s_{1}} ⋯ f_{t,s_{t}}) + ⋯ starts with f_{1,s_{1}} ⋯ f_{t,s_{t}}, we have lm(f_{1,s_{1}} ⋯ f_{t,s_{t}}) = lm(f_{1,s_{1}}) ⋯ lm(f_{t,s_{t}}) and hence Var^{(H_{i_{1}},...,H_{i_{n−k}})}(f_{1} ⋯ f_{t}) = Var^{(Γ)}(f_{1} ⋯ f_{t}) = Var^{(Γ)}(f_{1}, ⋯, f_{t}).

For any CT T_{1} we denote by Var^{(Γ)}(T_{1}) = Var^{(H_{i_{1}},...,H_{i_{n−k}})}(T_{1}) the maximum of the Var^{(Γ)}(f_{1} ⋯ f_{t}) taken over all the paths of T_{1}, whose f_{1}, …, f_{t} are testing polynomials along the path.

The following lemma is similar to lemma 1 [13], [11], but differs from it due to the different definition of the leading term lm.

Lemma 4 Let T = {T_{α}} be an RCT recognizing

a) an arrangement S = ∪_{1≤i≤m}H_{i} such that Γ = H_{i_{1}} ∩⋯∩H_{i_{n−k}} is k-face of S, or

b) a polyhedron S^{+} = ∩_{1≤i≤m}H_{i}^{+} such that Γ = ∩_{1≤j≤n−k}H_{i_{j}} is k-face of S^{+} (so, see above, for each 1 ≤ l ≤ n − k + 1 we have dim(∩_{l≤j≤n−k}H_{i_{j}}) = dim(∩_{l≤j≤n−k}H_{i_{j}} ∩ S^{+}) = k + l − 1)

with error probability γ < \frac{1}{2}. Then Var^{(H_{i_{1}},...,H_{i_{n−k}})}(T_{α}) ≥ (1−2γ)^{2}(n−k) for a fraction of \frac{1−2γ}{2−2γ} of all T_{α}’s.

Proof of Lemma 4: Choose the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} such that Z_{1}, …, Z_{k} are the coordinates in Γ and H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes of Y_{1}, …, Y_{n−k}, respectively (cf. section 1), which satisfy the following properties. The origin \underbrace{(0, …, 0)}_{n} of this coordinates

system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} does not lie in any l-face with l < k and besides, in the case b) (0, …, 0) belongs to the polyhedron S^{+}. Also we require that for any testing polynomial f from any CT T_{α} the inequality f_{s}^{(n−k)} \underbrace{(0, …, 0)}_{k} ≠ 0 holds (recall that f_{s}^{(n−k)} ≢ 0 depends only on H_{i_{1}}, …, H_{i_{n−k}} and f = f_{s} + f_{s+1} + ⋯ where f_{j} is homogeneous with respect to the variables Y_{1}, …, Y_{n−k} of degree j, see section 1).

Observe that RCT T treated over the field IR_{n+1} recognizes the completion S^{(IR_{n+1})} ⊂ (IR_{n+1})^{n} (respectively, S^{+(IR_{n+1})}) due to the Tarski transfer principle (see section 1). For the sake of simplicity of the notations we keep the notations S (respectively, S^{+}) for the completions.

a) Consider the point E = (\underbrace{0, …, 0}_{k}, ε_{k+1}ε_{n+1}, …, ε_{n}ε_{n+1}) and the points

E_{i}^{(0)} = (\underbrace{0, …, 0}_{k}, ε_{k+1}ε_{n+1}, …, ε_{k+i−1}ε_{n+1}, 0, ε_{k+i+1}ε_{n+1}, …, ε_{n}ε_{n+1}), 1 ≤ i ≤

n − k. Then the point E ∉ S (because of the choice of the origin of the coordinates system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) and E_{i}^{(0)} ∈ S, 1 ≤ i ≤ n − k.

We show that there is a fraction of \frac{1−2γ}{2(1−γ)} of all T_{α}’s that give the correct

outputs for E and for at least (1 − 2γ)^{2}(n − k) many among E_{i}^{(0)}, 1 ≤ i ≤ n−k. Indeed, assuming the contrary we partition all T_{α}’s into three (disjoint) pieces. In the first one the output for E is incorrect (its fraction is at most γ). In the second one (which is desirable for our goal) the fraction of correct outputs for E_{i}^{(0)}, 1 ≤ i ≤ n − k is at least (1 − 2γ)^{2} (its fraction is at most \frac{1−2γ}{2(1−γ)} by the assumption). The rest of T_{α}’s comprise the third piece. Thus,

the total fraction of correct outputs for all E_{i}^{(0)}, 1 ≤ i ≤ n − k together does not exceed (γ + \frac{1−2γ}{2(1−γ)})+(1−2γ)^{2}(1−γ − \frac{1−2γ}{2(1−γ)}) = 1−2γ +4γ^{2} −4γ^{3} < 1−γ, that contradicts to the requirement on the error probability γ.

Take such T_{α_{0}} and some 1 ≤ i_{0} ≤ n − k for which T_{α_{0}} gives the correct output. Denote by f_{1}, …, f_{t} the testing polynomials along the path in T_{α_{0}} followed by the input E. We claim that Y_{i_{0}} occurs in one of the leading terms lm(f_{1,s_{1}}), …, lm(f_{t,s_{t}}) (thereby, Y_{i_{0}} occurs in lm(f_{1,s_{1}} … f_{t,s_{t}}) = lm(f_{1,s_{1}}) … lm(f_{t,s_{t}}), see above).

Suppose the contrary. Let lm(f_{l,s_{l}}) = βZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}, then m_{i_{0}} = 0 for each 1 ≤ l ≤ t by the supposition. Then (1) from section 1 implies that sgn(\overline{f_{l}}(E_{i_{0}}^{(0)})) = sgn(f_{l,s_{l}}^{(n−k)} \underbrace{(0, …, 0)}_{k}) ≠ 0 because of the choice

of the origin of the coordinates system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}. By the same token sgn(\overline{f_{l}}(E)) = sgn(f_{l,s_{l}}^{(n−k)} \underbrace{(0, …, 0)}_{k}). Therefore, E_{i_{0}}^{(0)} satisfies all the

tests along the path under consideration in T_{α_{0}} followed by the input E, hence the output of T_{α_{0}} for the input E_{i_{0}}^{(0)} is the same as for the input E, so incorrect, that contradicts the choice of i_{0}.

b) First we show that E ∈ S^{+}. Take any hyperplane H_{l} = {κ_{1}Z_{1} + … + κ_{k}Z_{k} + β_{1}Y_{1} + … + β_{n−k}Y_{n−k} + β_{0} = 0}, 1 ≤ l ≤ m given by linear function L_{H_{l}} with the coefficients κ_{i}, β_{j} ∈ IR. We need to show that L_{H_{l}}(E) ≥ 0. Let 0 ≤ j_{0} ≤ n − k be the uniquely defined index such that β_{0} = … = β_{j_{0}−1} = 0, β_{j_{0}} ≠ 0 (if all β_{0} = … = β_{n−k} = 0 then L_{H_{l}}(E) = 0). We prove that β_{j_{0}} > 0, this would entail that sgn(L_{H_{l}}(E)) = sgn(β_{j_{0}}) > 0. Because dim(H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{j_{0}+1}} ∩ S^{+}) = k + j_{0} and dim(H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{j_{0}+1}} ∩ H_{i_{j_{0}}}) = k + j_{0} − 1 (see the beginning of this section), there exists a point v_{n−j_{0}} ∈ (H_{i_{n−k}} ∩⋯∩H_{i_{j_{0}+1}} ∩S^{+})−H_{i_{j_{0}}}, notice that in the chosen coordinate system

v_{n−j_{0}} = (\underbrace{0, …, 0}_{k}, y_{1}^{(n−j_{0})}, …, y_{j_{0}}^{(n−j_{0})}, 0, …, 0). Then y_{j_{0}}^{(n−j_{0})} ≠ 0, therefore

y_{j_{0}}^{(n−j_{0})} > 0 since v_{n−j_{0}} ∈ S^{+}. Hence 0 < sgnL_{H_{l}}(v_{n−j_{0}}) = sgn(β_{j_{0}} · y_{j_{0}}^{(n−j_{0})}), this implies that sgn(β_{j_{0}}) > 0. Thus E ∈ S^{+}.

Notice that the points E_{i}^{(+)} = (\underbrace{0, …, 0}_{k}, ε_{k+1}ε_{n+1}, …, ε_{k+i−1}ε_{n+1},

−ε_{k+i}ε_{n+1}, ε_{k+i+1}ε_{n+1}, …, ε_{n}ε_{n+1}) ∉ S^{+}, 1 ≤ i ≤ n − k.

The rest of the proof is similar as in a), with replacing the role of the points E_{i}^{(0)} by E_{i}^{(+)}. In a similar way if m_{i_{0}} = 0 then sgn(\overline{f_{l}}(E_{i_{0}}^{(+)})) = sgn(f_{l,s_{l}}^{(n−k)}(\underbrace{0, …, 0}_{k})) = sgn(\overline{f_{l}}(E)) ≠ 0 again because of (1) from section 1.

Lemma 4 is proved.

An analogue of lemma 2 from [13], [11] is the following lemma.

Lemma 5 For any positive constants c, c_{1}, c_{2}, c_{3} there exists c_{4} > 0 satisfying the following. Let S = S or S = S^{+} fulfill the conditions of the theorem. Assume that CT T′ for some constant η > 1 − c, satisfies the inequality Var^{(Γ)}(T′) ≥ η(n − k) for at least M ≥ c_{3}(m^{c(n−k)}) of k-faces Γ of S. Then the depth t of T′ is greater than c_{4}(n log m).

The proof of lemma 5 differs from the proof of the analogous lemma 2 from [13] proved for d-decision trees, in which the degrees of the testing polynomials do not exceed d, rather than computation trees (considered in the present paper), in which the degrees of the testing polynomials could be exponential in the depth t of CT. Also it differs from the proof of lemma 2 [11] where the main tool was the lower bound on the border complexity. Here the proof of lemma 5 is much easier than in [13], [11] and relies on the corollary (see section 2) in which the multiplicative complexity of a polynomial is bounded from below in terms of the number of strongly singular faces of an arrangement.

Before proving lemma 5 we show how to deduce the theorem from lemmas 4 and 5. Consider RCT \{T_{α}\} recognizing S with error probability γ < \frac{1}{2}. Lemma 4 and counting imply the existence of T_{α_{0}} such that the inequality Var^{(Γ)}(T_{α_{0}}) ≥ (1 − 2γ)^{2}(n − k) is true for M = \frac{1−2γ}{2(1−γ)}Ω(m^{c(n−k)}) of k-faces Γ of S. Apply lemma 5 to CT T′ = T_{α_{0}} with η = (1 − 2γ)^{2}. Since the error probability γ could be made a positive constant as close to zero as desired at the expense of increasing by a constant factor the depth of RCT [20], take γ such that η > 1 − c. Then lemma 5 entails that t ≥ Ω(n log m), which proves the theorem. Thus, it remains to prove lemma 5.

Proof of lemma 5: To each k-face Γ of S satisfying the inequality Var^{(Γ)}(T′) ≥ η(n − k), we correspond a path in T′ with the testing polynomials f_{1}, …, f_{t_{0}} ∈ IR[X_{1}, …, X_{n}], t_{0} ≤ t such that Var^{(Γ)}(f_{1} ⋯ f_{t_{0}}) = Var^{(Γ)}(T′) (in other words, Γ is strongly singular k-face for f_{1} ⋯ f_{t_{0}}, see section 1). Denote f = f_{1} ⋯ f_{t_{0}}

Assume that 3^{t} ≤ O(m^{(η−1+c)(n−k)/2}), otherwise we are done. Then there exists a path of T′ (let us keep the notation f_{1}, …, f_{t_{0}} for the testing polynomials along this path) which corresponds to at least N = Ω(m^{(c−η+1)(n−k)/2}) of strongly singular k-faces Γ for f (because there are most 3^{t} paths in T′). Corollary from section 2 implies that the multiplicative complexity C(f) ≥ \frac{1}{3}((η − 1 + c)(n − k) log m − 4n − const). Obviously C(f) ≤ t + t_{0} − 1 ≤ 2t − 1 (cf. the proof of theorem 2 [8]). Hence t ≥ Ω(n log m) that proves lemma 5.

4 Applications and open problems

As a consequence of the theorem from the previous section we deduce the complexity lower bound Ω(n log n) for any RCT, recognizing the DISTINCT-NESS problem ∪_{1≤i<j≤n}{X_{i} = X_{j}} ⊂ IR^{n} (for the necessary in the theorem estimation of the number of [\frac{n}{2}]-faces see [13]).

Also we get the lower bound Ω(n^{2}) for the KNAPSACK problem ∪_{I⊂{1,...,n}}{∑_{i∈I} x_{i} = 1}, this result was already obtained in [11]. It would be interesting to extend the obtained bound to other types of sets, rather than considered in the theorem polyhedra and the unions of hyperplanes.

The linear O(n) complexity RCT from [5] for the SET EQUALITY problem {(x_{1}, …, x_{n}, y_{1}, …, y_{n}) : {x_{1}, …, x_{n}} is a permutation of {y_{1}, …, y_{n}}} ⊂ IR^{2n} provides an evidence that the lower bound from the theorem could not be directly extended even to such quite natural sets like the unions of planes.

Generalizing the construction of [5] we design RCT for recognizing the following set: Δ_{n,m}^{(k)} = {(x_{1}, …, x_{n}, y_{1}, …, y_{m}) : each of the both differences of the multisets {x_{1}, …, x_{n}} and {y_{1}, …, y_{m}} contains at most k elements} ⊂ IR^{n+m}. Evidently, k ≥ |n − m|. Denote the polynomials f(X) = (X − x_{1}) ⋯ (X − x_{n}), g(X) = (X − y_{1}) ⋯ (X − y_{m}). First compute (deterministically) f(z_{i}), g(z_{i}) at 2k + 1 random points, 0 ≤ i ≤ 2k with the complexity O(k(n + m)). Then (deterministically) interpolate the rational function h = f/g, being (presumably) a quotient of two monic polynomials both of degrees at most k by means of its values (f/g)(z_{i}), 1 ≤ i ≤ 2k with the complexity O(k log^{2} k) [3]. Finally, (deterministically) check whether the value of the obtained rational function h(z_{0}) coincides with f(z_{0})/g(z_{0}). The complexity O(k(n + m)) of the designed RCT is better than the complexity O((n + m) log(n + m)) of an obvious CT based on a sorting algorithm when k is small enough.

Acknowledgement. I would like to thank Marek Karpinski for useful discussions.

References

[1] W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci., Vol. 22, 1983, pp. 317–330

[2] M. Ben-Or, Lower bounds for algebraic computation trees, Proc. ACM Symp. Th. Comput., 1983, pp. 80–86

[3] D. Bini, V. Pan, Polynomial and matrix computations, Birkhauser, 1994

[4] A. Bjorner, L. Lovasz, A. Yao, Linear decision trees: volume estimates and topological bounds, Proc. ACM Symp. Th.Comput. 1992, pp. 170– 177.

[5] P. Buergisser, M. Karpinski, T. Lickteig, On randomized algebraic test complexity, J. Complexity, Vol. 9, 1993, pp. 231–251.

[6] A. Chistov, D. Grigoriev, Solving systems of algebraic equations in subexponential time I, II, Preprints LOMI E-9-83, E-10-83, Leningrad, 1983

[7] D.Grigoriev, Nearly sharp complexity bounds for multiprocessor algebraic computations, J. Complexity, Vol. 13,1, 1997, pp.50-64

[8] D.Grigoriev, Complexity lower bounds for randomized computation trees over algebraically closed fields, to appear in Computational Complexity

[9] D. Grigoriev, M. Karpinski, Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees, Technical Report TR-93-042, International Computer Science Institute, Berkeley, 1993

[10] D. Grigoriev, M. Karpinski, Lower Bound for Randomized Linear Decision Tree Recognizing a Union of Hyperplanes in a Generic Position, Research Report No. 85114-CS, University of Bonn, 1994

[11] D. Grigoriev, M. Karpinski, Randomized quadratic lower bound for knapsack, Proc. ACM Symp. Th. Comput., 1997, pp. 76–85

[12] Grigoriev, M. Karpinski, R. Smolensky, Randomization and the computational power of analytic and algebraic decision trees, Computational Complexity, 1997, vol. 6, 4, pp. 376–388

[13] D. Grigoriev, M. Karpinski, F. Meyer auf der Heide, R. Smolensky, A lower bound for randomized algebraic decision trees, Proc ACM Symp. Th. Comput., 1996, pp. 612–619

[14] D. Grigoriev, M. Karpinski, N. Vorobjov, Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Proc. 36th IEEE FOCS, 1995, pp. 258–265

[15] D. Grigoriev, M. Karpinski, N. Vorobjov, Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, Discrete and Computational Geometry, Vol. 17,2, 1997, pp. 191–215.

[16] D. Grigoriev, N. Vorobjov, Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Comp., Vol. 5, 1988, pp. 37–64

[17] J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci., Vol. 24, 1983, pp. 239-277

[18] T. Lickteig, On semialgebraic decision complexity, Preprint TR-0–052 ICSI, Berkeley, 1990.

[19] S. Lang, Algebra, Addison-Wesley, New York, 1965

[20] F. Meyer auf der Heide, Simulating probabilistic by deterministic algebraic computation trees, Theor. Comput. Sci., Vol. 41, 1985, pp. 325– 330.

[21] J. Montana, L. Pardo, Lower bounds for arithmetic networks, Appl. Algebra in Eng. Commun. Comput., Vol. 4, 1993, pp. 1–24.

[22] J.Montana, J.Morais, L.Pardo, Lower bounds for arithmetic network II: sum of Betti numbers, Appl. Algebra in Eng. Commun. Comput., Vol. 7, 1996, pp. 41-51.

[23] D. Mumford, Algebraic geometry, Springer, 1976.

[24] U. Manber, M. Tompa, Probabilistic, Nondetemrinistic and Alternating Decision Trees, Proc. 14th ACM STOC, 1982, pp. 234–244

[25] I. R. Shafarevich, Basic algebraic geometry, V. 1 – Springer, 1994.

[26] M. Steele, A. Yao, Lower bounds for algebraic decision trees, J. Algorithms, Vol. 3, 1982, pp. 1–8.

[27] V. Strassen, Die Berechnungskomplexitaet von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., Vol. 20, 1973, pp. 238–251.

[28] V. Strassen, Computational complexity over finite fields, SIAM J. Comput. 5, 2, 1976, pp. 324–331 [29] A.Tarski, A Decision Method for Elementary Algebra and Geometry,

University of California Press, 1951.

[30] A. Yao, Algebraic decision trees and Euler characteristic, Proc. IEEE Symp. Found. Comput. Sci., 1992, pp. 268–277.

[31] A. Yao, Decision tree complexity and Betti numbers, Proc. ACM Symp. Th. Comput., 1994, pp. 615–624.