COMPLEXITY LOWER BOUNDS FOR RANDOMIZED COMPUTATION TREES OVER ZERO CHARACTERISTIC FIELDS

D. Grigoriev IMR Université Rennes-1 Beaulieu 35042 Rennes France dima@maths.univ-rennes1.fr

We obtain a nonlinear complexity lower bounds for randomized computation trees with branching signs {=, ≠} over zero characteristic fields. As consequences we get Ω(n log n) lower bound for the distinctness problem and Ω(n^{2}) lower bound for the knapsack problem. For more customary randomized computation trees over reals with branching signs {≤, >} the similar bounds were proved: for the knapsack problem in [GK97] and for the distinctness problem in [G99].

Introduction.

Complexity lower bounds for algebraic decision and computation trees over the reals, where for the branching the signs {≤, >} are involved, were widely studied. In [SY82], [B83] the lower bound Ω(log c − n) was obtained for recognizing a semialgebraic set with the number c of connected components in the set or in its complement. Afterwards in [CMP92] the lower bound was strengthened to Ω(log c). In [BLY92], [Y92], [BL94] the lower bound Ω(log χ) was proved where χ is the Euler characteristic of the set. Finally, in [Y94], [MMP96] the strongest among these “topological” lower bounds Ω(log b) was obtained, where b is the sum of Betti number of the set. For the sets with the trivial topology, like polyhedra, these bounds are not applicable and in [GKV97] the complexity lower bound Ω(log N) was proved using a differential-geometric approach, for recognizing a polyhedron with N faces

Typeset by AMS-TEX

(of all the dimensions). We mention also that for a parallel computation trees model the upper complexity bound O(\sqrt{log N log log N}) close to the lower one Ω(\sqrt{log N}) [Y81], [MP93] was obtained in [G97] for small dimensions.

Another challenging problem which was open for many years, is obtaining complexity lower bounds for the randomized decision and computation algebraic trees. Recall (see e.g. [M85]) that in the randomized models for any input point the answer could be given with the probability of an error at most γ < \frac{1}{2}. In [GKMS96] a lower bound Ω(log N) was proved for randomized decision trees recognizing an arrangement (i.e. a union of hyperplanes) or a polyhedron with N faces. This gives as corollaries the lower bound Ω(n log n) for the distinctness problem ∪_{1≤i<j≤n}{X_{i} = X_{j}} and the lower bound Ω(n^{2}) for the knapsack problem ∪_{I⊂{1,...,n}} {∑_{i∈I}x_{i} = 1} (both problems are treated as arrangements). In [GK97] the lower bound Ω(n^{2}) was proved for the knapsack problem for the more natural model of randomized computation trees. In [G99] the lower bound Ω(n log n) was ascertained for the distinctness problem for the same model. The basic difference between the decision and computation trees is that in the former one the testing polynomials (usually, of some fixed degree) are given, while in the latter one the testing polynomials are computed along a branch of the tree, thus the degree of testing polynomials could grow exponentially, that provides major difficulties in proving the complexity lower bounds. In [GKS96] the complexity lower bounds were ascertained also for the randomized decision analytic tree, in which arbitrary analytic functions could be used as testing ones.

Decision and computation trees over other fields rather than ℝ are not so well studied (see [S83], also [L90] where the case of recognizing an irreducible hypersurface was treated). In [B94] the trees with the signs {=, ≠} in branching instructions over algebraically closed fields of positive characteristic were introduced and the lower bound Ω(log_{2} C) for recognizing a variety was obtained, where C is the degree of the Zeta-function of the variety. Also it is promised in [B94] to prove the analogue of this bound over the fields of zero characteristic in a future paper.

In the present paper we focus (apparently, for the first time) on the randomized computation trees over fields F of zero characteristic (the results were announced in [G98]). For the problem of recognizing an arrangement S = ∪_{1≤i≤m}H_{i}, where H_{i} ⊂ F^{n} are hyperplanes, we prove the complexity lower bound Ω(log Ñ), here Ñ is the lower bound for the number of faces in any subarrangement ∪_{1≤j≤q}H_{ℓ_{j}} of S where q ≥ αm for an appropriate constant α > 0 (theorem 2). As consequences we obtain the lower bounds Ω(n log n) for the distinctness problem (corollary 2) and Ω(n^{2}) for the knapsack problem (corollary 3). Notice that a similar problem for obtaining a nonlinear lower bound for the distinctness problem for the randomized computations over the real field still remains open (see [GK97]).

It is interesting to observe that considering arrangements (so the varieties of codimension 1) is essential as shows the example from [BKL93], where a randomized computation tree with the linear complexity O(n) is designed for recognizing the equality set problem {(x_{1}, …, x_{n}, y_{1}, …, y_{n}) ∈ F^{2n} : (x_{1}, …, x_{n}) is a permutation of (y_{1}, …, y_{n})}, being not an arrangement, but rather a union of n-dimensional planes in 2n-dimensional space.

The proof of theorem 2 relies on corollary 1 in which the lower bound Ω(log N) is proved on the multiplicative complexity of any function f which vanishes on an arrangement with N faces. In its turn, the proof of the corollary 1 is based on the degree method [S73], on the complexity of computing the gradient [BS83] and on the technical core of the paper, namely theorem 1, in which a lower bound on the degree of the gradient map of f is ascertained in terms of N (over the algebraic closure \overline{F} of F).

Basically, it is shown in the proof of theorem 1 that the limits of the gradients at the points tending to a singular point (namely, to a vertex of the arrangement in n-dimensional space), sweep the whole (n − 1)-dimensional projective space. The difficulty, why the method of [BS83] could not be used in a more direct way, is that it is not excluded that the degree of the gradient map for a polynomial could be greater than the one for a multiple of this polynomial.

It would be interesting to get similar lower bounds for the randomized computation trees over the fields of positive characteristic.

1. Complexity of multiples of a product of linear functions.

Let F be an algebraically closed field of zero characteristic. Consider pairwise distinct hyperplanes H_{1}, …, H_{m} ⊂ F^{n}, let L_{i} ∈ F [X_{1}, …, X_{n}] be a linear function such that its variety of zeroes H_{i} = {L_{i} = 0}, 1 ≤ i ≤ m. By S = ∪_{1≤i≤m}H_{i} denote an arrangement, L = ∏_{1≤i≤m}L_{i}, so S = {L = 0}.

If for some 1 ≤ i_{1} < ⋯ < i_{n−k} ≤ m the dimension dim(H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}}) = k, the intersection H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} is called k-face of S. In this section by N we denote the number of 0-faces (in other words, vertices) of S.

Let a polynomial 0 ≢ f ∈ F [X_{1}, …, X_{n}] be a certain multiple of L. Similar to [S73], [L90] consider the graph of f joined by its gradient grad_{f}(x) = (\frac{∂f}{∂x_{1}} , ⋯, \frac{∂f}{∂x_{n}} ) (x).

\begin{matrix}G = \{(x_{1}, …, x_{n}, x_{0}, y_{1}, …, y_{n}); (x_{1}, …, x_{n}) ∈ F^{n}, x_{0} \\ = f(x_{1}, …, x_{n}), (y_{1}, …, y_{n}) = grad_{f}(x)\} ⊂ F^{2n+1} . \end{matrix}

The main purpose of the present section is to prove a lower bound on the degree (see e.g. [M76], [S73], [S94]) deg G in terms of N (see theorem 1 below). As usual while studying the degree one considers the embedding of an affine variety G ⊂ F^{2n+1} ⊂ ℙ^{2n+1} = ℙ^{2n+1}(F) into the projective space. Then deg G equals to the maximal possible (and simultaneously, typical) number of points of intersections of the projective closure \overline{G} ⊂ ℙ^{2n+1} with linear subspaces, provided the intersection is finite.

Theorem 1. deg G ≥ \frac{N}{2^{2n+1}}

Proof. Introduce the following rational map ψ : F^{2n+1} → ℙ^{n^{2}+2n−1} defined by the formula

ψ(x_{1}, …, x_{n}, x_{0}, y_{1}, …, y_{n}) = ({x_{i}y_{j}} : y_{1} : ⋯: y_{n}) ; 0 ≤ i ≤ n , 1 ≤ j ≤ n

where {x_{i}y_{j}} denote n(n + 1) projective coordinates. Observe that ψ is the composition of the canonical maps F^{n+1} × (F^{n} − 0) → F^{n+1} × ℙ^{n−1} → ℙ^{n+1} × ℙ^{n−1} → ℙ^{n^{2}+2n−1} where the latter one is the Segre embedding. Thus, ψ is defined when not all y_{1}, …, y_{n} vanish (the role of ψ is to make the coordinates of the gradient to be projective). Obviously dim ψ(G) = dim G = n.

Consider also a rational map σ : ℙ^{n^{2}+2n−1} → ℙ^{n−1}, being a linear projection: σ({z_{ij}} : y_{1} : ⋯: y_{n}) = (y_{1} : ⋯: y_{n}) (its role is to distinguish the coordinates of the gradient).

First we remark that the theorem holds easily in case n = 1. Indeed, the arrangement S ⊂ F consists of N points being the zeroes of L, therefore deg f ≥ N since L|f. The graph G = {(x, f(x), f′(x)) : x ∈ F } ⊂ F^{3} and its degree deg G ≥ deg f. Henceforth, we assume that n ≥ 2.

Besides, we suppose that N ≥ 1, otherwise the theorem is evident. Lemma 1. For any vertex x^{(0)} = (x_{1}^{(0)}, …, x_{n}^{(0)}) of S set x_{0}^{(0)} = f(x_{1}^{(0)}, …, x_{n}^{(0)}) = 0. Then dim(σ(\overline{ψ(G)} ∩ H^{(0)})) = n − 1, where (n − 1)-dimensional projective linear subspace

H^{(0)} = H(x^{(0)}) = {({x_{i}^{(0)}y_{j}} : y_{1} : ⋯: y_{n}); (y_{1} : ⋯: y_{n}) ∈ ℙ^{n−1}} ⊂ ℙ^{n^{2}+2n−1}

is determined by the linear equations z_{ij} = x_{i}^{(0)}y_{j}, 0 ≤ i ≤ n, 1 ≤ j ≤ n. Remark. Lemma 1 implies that H^{(0)} ⊂ \overline{ψ(G)} and therefore, σ(\overline{ψ(G)} ∩ H^{(0)}) = σ(H^{(0)}) = ℙ^{n−1}. Proof of the lemma. W.l.o.g. we assume for the sake of simplifying the notations that x^{(0)} = 0 and the hyperplanes {X_{1} = 0}, …, {X_{n} = 0} ⊂ F^{n} are among H_{1}, …, H_{m} (this could be achieved by a suitable linear transformation of the coordinates).

Suppose that the conclusion in lemma is wrong. Then there exists a non-zero homogeneous polynomial h ∈ F [Y_{1}, …, Y_{n}] such that h(y_{1}, …, y_{n}) = 0 for any point (\{0\} : y_{1} : ⋯: y_{n}) ∈ \overline{ψ(G)}(∩H^{(0)}).

Write f = f_{s} + f_{s+1} + ⋯ + f_{s_{1}}, where f_{j} is the homogeneous component of f of degree j and f_{s} ≢ 0. Since X_{1} ⋯ X_{n}|f we have s ≥ n ≥ 2, moreover in the decomposition into the sum of homogeneous components \frac{∂f}{∂X_{j}} = \frac{∂f_{s}}{∂X_{j}} + \frac{∂f_{s+1}}{∂X_{j}} +⋯+ \frac{∂f_{s_{1}}}{∂X_{j}} the least component \frac{∂f_{s}}{∂X_{j}} of degree (s − 1) does not vanish identically.

Let us show that for any line {(tx_{1}, …, tx_{n})}_{t∈F} ⊂ F^{n}, where a point 0 ≠ (x_{1}, …, x_{n}) ∈ F^{n}, passing through x^{(0)} = 0, such that grad_{f_{s}} does not vanish on this line identically (and thus, does not vanish for any t ≠ 0, as grad_{f_{s}} is homogeneous), it holds

(1)  (\{0\} : \frac{∂f_{s}}{∂X_{1}} : ⋯: \frac{∂f_{s}}{∂X_{n}} ) (x_{1}, …, x_{n}) ∈ \overline{ψ(G)}

Indeed, we have \frac{∂f}{∂X_{j}} (tx_{1}, …, tx_{n}) = t^{s−1}f̃_{j}(t, x_{1}, …, x_{n}) = (t^{s−1} \frac{∂f_{s}}{∂X_{j}} + t^{s} \frac{∂f_{s+1}}{∂X_{j}} + ⋯ + t^{s_{1}−1} \frac{∂f_{s_{1}}}{∂X_{j}} ) (x_{1}, …, x_{n}), 1 ≤ j ≤ n and f(tx_{1}, …, tx_{n}) = t^{s}f̃_{0}(t, x_{1}, …, x_{n}) for suitable polynomials f̃_{0}, f̃_{1}, …, f̃_{n} ∈ F [t, x_{1}, …, x_{n}]. Then the point

({tx_{i} · t^{s−1}f̃_{j}}_{1≤i,j≤n} : {t^{s}f̃_{0} · t^{s−1}f̃_{j}}_{1≤j≤n} : t^{s−1}f̃_{1} : ⋯: t^{s−1}f̃_{n})

belongs to ψ(G). Dividing all the coordinates over the common factor t^{s−1} and after that substituting t = 0 we get (1) for the resulting limit point.

Thus, for any point (x_{1}, …, x_{n}) ∈ F^{n} we have h ((\frac{∂f_{s}}{∂X_{1}} , ⋯, \frac{∂f_{s}}{∂X_{n}} ) (x_{1}, …, x_{n})) = 0 since h is homogeneous, i.e. h (\frac{∂f_{s}}{∂X_{1}} , ⋯, \frac{∂f_{s}}{∂X_{n}} ) ≡ 0.

Consider the monomial ordering deglex, according to which a monomial is higher than another one if either its total degree is greater or the degrees of both coincide and the monomial is higher in the lexicographical ordering (with respect to a certain fixed ordering of the variables X_{1}, …, X_{n}).

Let M = X_{1}^{i_{1}} ⋯ X_{n}^{i_{n}} be the least monomial of f_{s} in deglex ordering (hence M is also the least monomial of f), then i_{1} ≥ 1, …, i_{n} ≥ 1 since X_{1} ⋯ X_{n}|f. Therefore, the least monomial of \frac{∂f_{s}}{∂x_{j}} is \frac{M}{X_{j}}. Let h = ∑_{K} h_{K}Y_{1}^{K_{1}} ⋯ Y_{n}^{K_{n}}. In the expansion of h (\frac{∂f_{s}}{∂X_{1}} , ⋯, \frac{∂f_{s}}{∂X_{n}} ) the least monomials (\frac{M}{X_{1}} )^{K_{1}} ⋯ (\frac{M}{X_{n}} )^{K_{n}} of the items are pairwise distinct; indeed, assuming the contrary we have, (\frac{M}{X_{1}} )^{p_{1}} ⋯ (\frac{M}{X_{n}} )^{p_{n}} = 1 for some integers p_{1}, …, p_{n} not all of them being zeroes, then the vector (p_{1}, …, p_{n}) is collinear with the vector (i_{1}, …, i_{n}), thus M^{i_{1}+···+i_{n}} = M, but i_{1} + ⋯ + i_{n} ≥ n ≥ 2 and we get a contradiction. Since the least monomials of the items are pairwise distinct, they cannot cancel each other, this leads to the contradiction with h (\frac{∂f_{s}}{∂X_{1}} , ⋯, \frac{∂f_{s}}{∂X_{n}} ) ≡ 0 and proves the lemma.

Lemma 2. deg \overline{ψ(G)} ≥ N

Proof. Consider a variety V = \overline{ψ(G)} ∩ P ⊂ ℙ^{n^{2}+2n−1}, where P = \{\{z_{ij}\}_{1≤i,j≤n} : {0} : y_{1} : ⋯: y_{n}} is the subspace (of codimension n) obtained by means of substituting zeroes for the coordinates {z_{0i}}_{1≤i≤n}.

Pick out any vertex x^{(0)} of S (taking into account that N ≥ 1), then \overline{ψ(G)} ∩ H^{(0)} ⊂ V and lemma 1 entails that dim(σ(V ∩ H^{(0)})) = n − 1. On the other hand, consider a hyperplane {X_{0} = 0} ⊂ F^{2n+1}, then ψ(G) ∩ P ⊂ ψ(G ∩ {X_{0} = 0}), hence dim (ψ(G) ∩ P) ≤ dim(G ∩ {X_{0} = 0}) ≤ n − 1, therefore, no n-dimensional irreducible component of ψ(G) lies entirely in P and because of that dim V ≤ n−1, thus dim V = n − 1.

The theorem on the dimensions of the fibres [S94], [M76] implies the existence (actually, an open set) of a point y^{(0)} = (y_{1}^{(0)} : ⋯: y_{n}^{(0)}) ∈ ℙ^{n−1} such that the preimage σ^{−1}(y^{(0)}) ∩ V consists of a finite number of points and moreover, y^{(0)} ∈ σ(V ∩ H^{(0)}) for any vertex x^{(0)} of S. Therefore, deg \overline{ψ(G)} ≥ N since the intersection of V with the subspace {y_{i}y_{j}^{(0)} = y_{j}y_{i}^{(0)}}_{1≤i,j≤n} consists of a finite number of points σ^{−1}(y^{(0)}) ∩ V, and for any of vertices x^{(0)} = (x_{1}^{(0)}, …, x_{n}^{(0)}) of S this intersection contains the point ({x_{i}^{(0)}y_{j}^{(0)}}_{1≤i,j≤n} : {0} : y_{1}^{(0)} : ⋯: y_{n}^{(0)}) due to the choice of y^{(0)} (cf. [S94],[S73]). Lemma 2 is proved.

To complete the proof of the theorem one could invoke the inequality deg \overline{ψ(G)} ≤ deg ψ · deg G (see [S73], [S94]), but in order to estimate deg ψ one should consider Graph ψ of the map ψ into the projective space ℙ^{n^{2}+2n−1} and Segre embedding Graph ψ into ℙ^{(2n+2)(n^{2}+2n)−1} (see [M76], [S94]) which would increase its degree. Instead of that, we give an alternative self-contained proof of the required inequality deg \overline{ψ(G)} ≤ 2^{2n+1}deg G.

Take a subspace P ⊂ ℙ^{n^{2}+2n−1} of the codimension n such that P ∩ψ(G) consists of deg ψ(G) = deg \overline{ψ(G)} points (such a subspace exists since for almost any ncodimensional subspace its intersection with \overline{ψ(G)} consists of deg \overline{ψ(G)} points and for almost any subspace its intersection with the set \overline{ψ(G)} − ψ(G) of dimension less than n is empty). Then ψ(ψ^{−1}(P) ∩ G) = P ∩ ψ(G). Hence deg \overline{ψ(G)} does not exceed the number of irreducible components of the variety ψ^{−1}(P) ∩ G which in its turn is less or equal to deg (ψ^{−1}(P) ∩ G) ≤ deg ψ^{−1}(P)deg G according to the Bezout inequality for locally closed sets proved in [H83] which extends the more customary case of the closed projective sets intersecting completely, see e.g. [M76], [S94], also [S73]. The local closedness of the set ψ^{−1}(P) follows from the next paragraph.

It remains to estimate deg ψ^{−1}(P). If P is determined by linear equations of

the form ∑_{0≤i≤n,1≤j≤n}α_{ij}z_{ij} + ∑_{1≤i≤n}α_{i}y_{i} = 0, then ψ^{−1}(P) ⊂ F^{2n+1} is determined

(out of the plane L = {y_{1} = ⋯ = y_{n} = 0} where ψ is not defined) by quadratic equations of the form

(2)  ∑ α_{ij}x_{i}y_{j} + ∑ α_{i}y_{i} = 0

By induction on 0 ≤ q ≤ 2n one could choose the linear combinations g_{1}, …, g_{q} ∈ F [X_{1}, …, X_{n}, X_{0}, Y_{1}, …, Y_{n}] of the equations of the form (2) satisfying the property that any irreducible component of codimension less than q of the locally closed set {g_{1} = ⋯ = g_{q} = 0} − L is also an irreducible component of ψ^{−1}(P). As q_{q+1} one can choose a linear combination of the equations of the form (2) such that g_{q+1} does not vanish identically on any irreducible component of {g_{1} = ⋯ = g_{q} = 0}, not being an irreducible component of ψ^{−1}(P). At the end of this process ψ^{−1}(P) is a union of several irreducible components of {g_{1} = ⋯ = g_{2n+1} = 0} (the latter variety could contain few extra its 0-dimensional irreducible components). Hence deg ψ^{−1}(P) ≤ deg {g_{1} = ⋯ = g_{2n+1} = 0} ≤ 2^{2n+1} again due to the Bezout inequality.

Finally, deg \overline{ψ(G)} ≤ 2^{2n+1}deg G, together with lemma 2 this proves the theorem 1.

In the following corollary we utilize introduced above notations. From now on let F be an arbitrary field of zero characteristic.

Corollary 1. Let L|f, f ≢ 0, then the multiplicative complexity C of f is greater or equal to \frac{1}{3}(log_{2} N − 2n − 1)

For the proof we treat the polynomials L, f over the algebraic closure \overline{F} of F. Notice that the [BS83] implies that the multiplicative complexity of the family of polynomials (f, grad_{f}) is less or equal to 3C, hence [S73] entails that deg G ≤ 2^{3C} (cf. also [L90]), which together with the theorem 1 proves the corollary.

2. Complexity lower bound for randomized computation trees

Let us consider first a deterministic algebraic computation tree (CT) T′ which recognizes an arrangement S. Prune from T′ all possible degenerate branches which lead to the sign ≠ for identically vanishing testing functions. After that the resulting CT (which we still denote by T′) possesses the unique (we call it “thick”) branch with the testing polynomials f_{1}, …, f_{k} ∈ F [X_{1}, …, X_{n}], respectively, such that all the signs along this branch are ≠. Denote f = f_{1} ⋯ f_{k}. Obviously, the set W = \{f ≠ 0\} ⊂ \overline{F}^{n} of the points satisfying the tests along the “thick” branch is open and dense in the Zariski topology (see e.g. [M76]). Evidently, the total complexity of the sequence f_{1}, …, f_{k} does not exceed k, therefore, the complexity of f being the product of this sequence, does not exceed 2k − 1. The output of the “thick” branch should be “no”, i.e. W ∩ S = ϕ, hence L|f.

For any 0 ≤ r ≤ n − 1 denote by φ_{r}(S) the number of r-faces of S.

Proposition. The complexity of a deterministic computation tree recognizing an arrangement S is greater than \frac{1}{6}(log_{2} φ_{r}(S) − 2(n − r)).

Remark. Moreover, we show that a certain branch (in fact, the ”thick” one) of a computation tree contains at least \frac{1}{6}(log_{2} φ_{r}(S) − 2(n − r)) multiplications.

To prove the proposition take a (n − r)-dimensional plane P ⊂ F^{n} in generic position and restrict CT T′ and S on P. Then the multiplicative complexity of the restriction f|_{P} is still less or equal than 2k − 1 and the arrangement S ∩ P ⊂ P has φ_{r}(S) vertices. Since L|_{P} | f|_{P}, one applies the corollary 1 and concludes that (2k − 1) ≥ \frac{1}{3}(log_{2} φ_{r}(S) − 2(n − r) − 1), thus the proposition is proved.

But our main issue are the randomized algebraic computation trees (RCT, see e.g. [M85], [GKMS96], [GK97]). Under RCT 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 are obtained if to define the depth of an RCT as the expectation of the depths of T_{α}’s [M85]). The main requirement is that for any input an RCT gives a correct output with probability at least 1 − γ > \frac{1}{2} (γ is called the error probability of RCT, see e.g. [M85], [GKMS96]).

Let k_{0} be the complexity (depth) of T, then any testing polynomial in T has the degree at most 2^{k_{0}}. Take N = ⌈\frac{2^{k_{0}+2}}{1−2γ} ⌉ and arbitrary N pairwise distinct elements α_{1}, …, α_{N} ∈ F. Consider a grid R = {α_{1}, …, α_{N}}^{n−1} ⊂ F^{n−1}. Then for any polynomial 0 ≢ g ∈ F [X_{1}, …, X_{n−1}] of degree at most 2^{k_{0}+1} the number of zeroes of g on R does not exceed 2^{k_{0}+1} · N^{n−2} ≤ \frac{1−2γ}{2} N^{n−1} (see [S80]).

Now embed the grid R into each hyperplane H_{i}, 1 ≤ i ≤ m (in an arbitrary way), one can assume w.l.o.g. that the embeddings in the different hyperplanes have no common points. The union of all these embeddings we denote by Δ ⊂ S.

Observe that for the “thick” branches of T the output “yes” could be given with the probability at most γ. Indeed, there exists a point which belongs to the open sets W_{α} which correspond to the “thick” branches of T_{α} for all α and to the complement F^{n} − S; for this point the incorrect output “yes” could appear with a probability at most γ.

Therefore, there exists α such that CT T_{α} gives the output “no” for its “thick” branch and besides, gives the correct output (so, “yes”) for at least (1 − 2γ)|Δ| = (1 − 2γ)m N^{n−1} points among Δ, denote this set of points by Δ_{0} ⊂ Δ. Indeed, otherwise the correct output for the points from Δ is given with an expectation less than (1 − 2γ) + γ, the latter summand γ refers to α such that the ”thick” branch of T_{α} gives the output ”yes” (see above); that would contradict to the definition of γ. Let f_{1}, …, f_{k} be the testing polynomials along the “thick” branch of T_{α}, then f = f_{1} ⋯ f_{k} vanishes at Δ_{0} (obviously, k ≤ k_{0}, deg f_{i} ≤ 2^{i}, deg f ≤ 2^{k_{0}+1} and the complexity of f does not exceed 2k − 1).

Assume that there are exactly number q of hyperplanes H_{i_{1}}, …, H_{i_{q}} among H_{1}, …, H_{m} such that each of them contains more than \frac{1−2γ}{2} N^{n−1} points from Δ_{0}. Then (m − q)\frac{1−2γ}{2} · N^{n−1} + qN^{n−1} ≥ (1 − 2γ)m N^{n−1}, whence q ≥ \frac{1−2γ}{1+2γ} m. Observe now that f vanishes on each of hyperplanes H_{i_{1}}, …, H_{i_{q}} (due to the choice of N). Denote by L̃ ∈ F [X_{1}, …, X_{n}] the product of q linear functions which define H_{i_{q}}, …, H_{i_{q}}. Then L̃|f. Finally, applying corollary 1 as in the proof of the proposition (i.e. to the restriction of L̃ and f onto a certain plane), we obtain the following lower bound on the complexity of RCT.

Theorem 2. Assume that for any ⌈\frac{1−2γ}{1+2γ} m⌉ hyperplanes among H_{1}, …, H_{m}, the arrangement S̃ ⊂ S = ∪_{1≤i≤m}H_{i} being a union of these hyperplanes, has at least Ñ faces of all the dimensions. Then the complexity of RCT with error probability γ < \frac{1}{2} which recognizes S, is greater than \frac{1}{6}(log_{2} Ñ − 2n − log_{2} n).

Remark. In fact, one could replace \frac{1−2γ}{1+2γ} by any other constant less than 1 − 2γ. Now we give two application of theorem 2.

Corollary 2. Any RCT recognizing the distinctness, i.e. the arrangement S = ∪_{1≤i<j≤n}{X_{i} = X_{j}} has the complexity at least Ω(n log n).

The proof exploits an idea from [GKMS96]. Fix any constant 1 ≥ β > 0 and take at least β \frac{n(n−1)}{2} hyperplanes H_{1}, …, H_{q} among \{X_{i} = X_{j}\}, 1 ≤ i < j ≤ n. Let us show that the arrangement H_{1} ∪ ⋯ ∪ H_{q} has at least n^{Ω(n)} faces, then theorem 2 would entail the corollary. For the sake of simplicity of notations suppose that n is even.

Consider all possible subsets I ⊂ \{1, …, n\} for which |I| = \frac{n}{2}. By the argument of counting in average there exists a subset I such that among (\frac{n}{2})^{2} hyperplanes of the kind \{X_{i} = X_{j}\} where i ∈ I, j ∉ I there are at least β \frac{n^{2}}{4} from H_{1}, …, H_{q}. Denote α = \frac{1}{2}(1 − \sqrt{1 − β}) > 0. There exist at least αn numbers i_{1}, …, i_{t} ∈ I such that for any i_{t_{1}}, 1 ≤ t_{1} ≤ t there are at least αn hyperplanes of the kind {X_{i_{t_{1}}} = X_{j}}, j ∉ I among H_{1}, …, H_{q}. Indeed, otherwise among the hyperplanes of the kind \{X_{i} = X_{j}\}, i ∈ I, j ∉ I one could find at least (\frac{n}{2} − αn)^{2} = \frac{n^{2}}{4} (1 − β) hyperplanes which are not among H_{1}, …, H_{q}.

For i_{1} choose one of the possible of at least [αn] hyperplanes of the kind {X_{i_{1}} = X_{j_{1}}}, j_{1} ∉ I among H_{1}, …, H_{q}; after that for i_{2} choose one of the possible of at least ([αn] − 1) hyperplanes of the kind {X_{i_{2}} = X_{j_{2}}}, j_{2} ≠ j_{1}, j_{2} ∉ I among H_{1}, …, H_{q} and so on. Finally, for i_{[αn]} we have at least 1 possibility for j_{[αn]}. Any possible intersection of the hyperplanes {X_{i_{1}} = X_{j_{1}}} ∩ ⋯ ∩ {X_{i_{[αn]}} = X_{j_{[αn]}}} provides a face of the codimension [αn], and there are at least [αn]! such faces.

Remark. For the more customary trees over the real field F = ℝ with the signs {≤, >} at the testing nodes, lower bound Ω(n log n) for the distinctness problem was proved in [GKMS96] in case of the randomized algebraic decision trees. In case of the randomized computation trees the complexity of the distinctness problem was posed as an open question in [GK97].

Corollary 3. Any RCT recognizing the restricted integer programming (RIP) ∪_{a∈{0,...,j−1}^{n}}{aX = 1} ⊂ F^{n} has the complexity at least Ω(n^{2} log j).

Notice that in the particular case j = 2 this problem coincides with the knapsack problem.

The corollary follows from theorem 2 and from [GK97] where it is proved in particular, that for some σ > 0 any subarrangement of the RIP consisting of ⌊j^{σn}⌋ hyperplanes of the form {aX = 1} has at least j^{λn^{2}} faces for a suitable λ > 0.

Remark. Actually, the corollary 3 in case of an algebraically closed field F can be deduced directly from the complexity lower bound Ω(n^{2} log j) for the RIP for the randomized computation trees over the real field F = ℝ with the signs {≤, >} [GK97]. Indeed, in case of the field F = ℂ (or algebraic numbers F = \overline{ℚ}) one can easily convert RCT T into RCT T^{(ℝ)} over F = ℝ (respectively, F = \overline{Q} ∩ ℝ), representing each computed polynomial g in RCT T as g = g_{1} + \sqrt{−1} g_{2} where g_{1}, g_{2} ∈ ℝ[X_{1}, …, X_{n}] and computing both g_{1}, g_{2} in T^{(ℝ)}. This gives the corollary 3 in case of 𝔽 = ℂ or F = \overline{ℚ}.

For an arbitrary algebraically closed field F one can write the condition of the non-existence of a RCT with a fixed low enough complexity and fixed probabilities p_{α} which recognizes RIP, as a formula of the first order theory of algebraically closed fields with the coefficients in \overline{ℚ} (provided that p_{α} ∈ \overline{ℚ}). This formula is true over F = ℂ (and over F = \overline{ℚ}), hence it is true over an arbitrary algebraically closed field F.

Remark. The results of this paper can be extended from the considered above arrangements to the so-called ”distorted” arrangements. Namely, for irreducible polynomials h_{1}, …, h_{m} ∈ F [X_{1}, …, X_{n}] (here we assume F to be algebraically closed) a ”distorted” arrangement is a variety W = {h_{1} ⋯ h_{m} = 0} ⊂ F^{n}. A ”distorted” k-face of W is an irreducible k-dimensional variety W_{k} ⊂ F^{n} for which there exist 1 ≤ i_{1}, …, i_{n−k} ≤ m such that W_{k} is an irreducible component of the variety {h_{i_{1}} = ⋯ = h_{i_{n−k}} = 0} and in addition, for almost any (in Zariski topology) point x ∈ W_{k} the gradients grad_{h_{i_{1}}} (x), …, grad_{h_{i_{n−k}}} (x) are linearly independent.

Let f ∈ F [X_{1}, …, X_{n}] vanish on W and N denote the number of 0-faces of W.

Then the inequality from theorem 1 still holds. Indeed, for any 0-face x ∈ W we

make a linear transformation of the coordinates, after which the gradient grad_{h_{i_{j}}} (x)

becomes orthogonal to the coordinate hyperplane {X_{j} = 0}, 1 ≤ j ≤ n and x

becomes the origin of the coordinates. Then the least homogeneous component of

h_{i_{j}} (at the point x) equals to c_{j}X_{j}, c_{j} ≠ 0, 1 ≤ j ≤ n. Hence the least homogeneous

component of h_{i_{1}} ⋯ h_{i_{n}} equals to (c_{1} ⋯ c_{n})X_{1} ⋯ X_{n}, therefore X_{1} ⋯ X_{n} divides

the least homogeneous component of the polynomial f, and the proof of theorem

1 goes through for the polynomial f almost literally, thereby as well the proof of

corollary 1.

The proof of theorem 2 also goes through for ”distorted” arrangements. Instead

of the grid R in the proof one should take a suitable finite subset of points from

a hypersurface {h_{i} = 0} ⊂ F^{n}, 1 ≤ i ≤ n to guarantee that if any polynomial

g ∈ F [X_{1}, …, X_{n}] of a given degree vanishes at any fraction of β > 0 among these

points then h_{i}|g (of course, the number of points in this finite subset depends on

β and on the degree of g). For example, one could consider a linear projection

π : F^{n} → F^{n−1} such that dim(π{h_{i} = 0}) = n − 1, take an appropriate grid

R_{1} ⊂ F^{n−1}, then the preimage π^{−1}(R_{1}) could replace R in the proof.

References

[BS83] W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci. 22 (1983), 317–330.

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

[B94] M. Ben-Or, Algebraic computation trees in characteristic p > 0, Proc. IEEE Symp. Found. Comput.Sci. (1994), 534–539.

[BL94] A. Bjorner, L. Lovasz, Linear decision trees, subspace arrangements and Moebius functions, J. AMS 7, 3 (1994), 677–705.

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

[BKL93] P. Buergisser, M. Karpinski, T. Lickteig, On randomized algebraic test complexity, J. Complexity 9 (1993), 231–251.

[CMP92] F. Cucker, J.L. Montana, L.M. Pardo, Time bounded computations over the reals, Int. Journal of Algebra and Computation 2, 4 (1992), 395–408.

[G97] D. Grigoriev, Nearly sharp complexity bounds for multiprocessor algebraic computations, J. Complexity 13, 1 (1997), 50–64.

[G98] D. Grigoriev, Randomized complexity lower bounds, Proc. ACM Symp. Th. Comput. (1998), 219–223.

[G99] D. Grigoriev, Randomized complexity lower bounds for arrangements and polyhedra, Discrete and Computational Geometry (1999).

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

[GKS96] D. Grigoriev, M. Karpinski, R. Smolensky, Randomization and the computational power of analytic and algebraic decision trees, Computational Complexity 6, 4 (1997), 376–388.

[GKMS96] 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), 612–619.

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

[H83] J.Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci. 24 (1983), 239–277.

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

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

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

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

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

[S80] T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM 27 (1980), 701–717.

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

[SY82] M. Steele, A. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), 1–8.

[S73] V. Strassen, Die Berechnungskomplexitaet von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1973), 238–251.

[S83] V. Strassen, The complexity of continued fractions, SIAM J. Comput. 12,1 (1983), 1–27.

[Y81] A. Yao, On the parallel complexity for the knapsack problem, Proc. ACM Symp. Th. Comput. (1981), 123–127.

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

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