An Exponential Lower Bound for Depth 3 Arithmetic Circuits

Dima Grigoriev^{∗}  Marek Karpinski^{†}

Abstract

We prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field. This answers an open problem of [N91] and [NW95] for the case of finite fields. We intepret here arithmetic circuits in the algebra of polynomials over the given field. The proof method involves a new argument on the rank of linear functions, and a group symmetry on polynomials vanishing at certain nonsingular matrices, and could be of independent interest.

Introduction

In this paper we are interested in a fundamental problem of computing functions by unbounded fanin arithmetic circuits of depth 3. Unlike the boolean circuits, general arithmetic circuits of depth 3 are surprisingly powerful. They can compute (via polynomial interpolation) in polynomial size any symmetric function. To date however the best lower bound known for general arithmetic circuit size was only slightly superlinear Ω(n log n)

([S73]). In this paper we prove the first superpolynomial (in fact exponential) size lower bound on depth 3 arithmetic unbounded fanin circuits computing an explicit function, the determinant function, over an arbitrary finite field. In this paper, we interpret the arithmetic circuits in the polynomial algebra over the given field. The determinant function is especially interesting because of its algebraic universality property ([V79]) over arbitrary fields. We refer a general reader to [L84] and [H77] for all the needed notions used in our proof. We denote by F = 𝔽_{q} a finite field with q elements. We shall study fields for q ≥ 3 (for q = 2, the boolean case, the lower bound could be derived from [R87] and [V79]). We study the representation of Det = Det_{n} = ∑_{σ}(−1)^{sgn(σ)}X_{1,σ(1)} ⋯ X_{n,σ(n)} in the polynomial algebra F [X_{1,1}, …, X_{n,n}] in the form of a depth 3 arithmetic circuit, or equivalently, an expansion:

Det = ∑_{1≤ℓ≤N} ∏_{m} L_{ℓ,m}  (1)

where each L_{ℓ,m} = ∑_{i,j} a_{i,j}^{(ℓ,m)}X_{i,j} + a_{0}^{(ℓ,m)} ∈ F [X_{1,1}, …, X_{n,n}] is a linear function in the variables X_{1,1}, …, X_{n,n}. Our purpose is to prove the following exponential lower bound on the size of a representation (1). From this, the lower bound on the size of any depth 3 arithmetic unbounded fanin circuit computing the determinant follows.

Theorem For any q ≥ 3 there is a constant δ > 1 such that in a representation (1) the number of terms N = Ω(δ^{n}).

∗Dept. of Computer Science and Mathematics, Penn State University, University Park. Research partially supported by NSF Grant CCR-9424358. Email:

dima@cse.psu.edu

†Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by the International Computer Science Institute, Berkeley, DIMACS, by the DFG Grant 673/4-1, ESPRIT BR Grants 7079, 21726, and EC-US 030. Email:

marek@cs.bonn.edu

Representations of the form (1), but under the restriction that L_{ℓ,m} are (homogeneous) linear forms, rather than functions, were considered in [G82] (over an arbitrary field), where lower bounds on N were established. The basic idea in [G82] was to design a linear operator on polynomials into matrices which maps a product ∏_{m} L_{ℓ,m} into a matrix of a bounded rank. This approach was also used in [R87]. Later a different method of proving lower bounds on N (again under a similar to [G82] assumption that the degree of each product ∏_{m} L_{ℓ,m}, i.e. the number of linear functions in the product, is bounded) was proposed in [NW95]. The core of the method was to estimate the dimension of all the partial derivatives (up to a certain order). On the other hand, the circuits with a bounded depth (and unbounded fanin) were studied in connection with the boolean AC^{0} class and an exponential lower bound on their sizes was proved in [R87], [S87]. The methods in both papers were working just for boolean circuits, and it would be interesting to explore whether they could be extended to arbitrary finite fields (the present authors were not able to do it). These boolean methods imply, in particular, an exponential lower bound on the size of any bounded depth boolean circuit for determinant (and consequently, of any arithmetic circuit over 𝔽_{2}). The representation (1) can be viewed as a depth 3 arithmetic circuit. In contrast to boolean circuits we interpret arithmetic circuits (1) as an identity in the polynomial algebra (vs. the algebra of functions over F, see section 1 below). Recently, Razborov [R98] was able to generalize our results to the algebra of functions over F. An important problem remains open to get lower bounds for representations of the kind (1), or for the more general bounded depth circuits, over the arbitrary fields including zero characteristic. The rest of the paper is devoted to the proof of the Theorem. In Section 1 we treat the representation (1) and its partial derivatives in the algebra of functions over F and partition the terms ∏_{m} L_{ℓ,m} into two groups, regarding the rank of the family of linear functions {L_{ℓ,m}}_{m} being greater or less J than, respectively, a certain integer (threshold). We show that the products ∏_{m} L_{ℓ,m} with a large rank vanish (and moreover with a large multiplicity) everywhere out of a small fraction of points from F^{n^{2}} (which could be informally viewed as “erroneous” points). For the products with a small rank we estimate from above the dimension of the set of all its derivatives (up to some order) restricted to the algebra of functions over F. In Section 2 we study linear combinations of minors (of a fixed size) of a matrix vanishing at all the points (in other words, matrices) out of an “erroneous” set, because minors are just the derivatives of Det. Since the full linear group GL_{n}(F) acts on linear combinations of minors, we show that a small number of shifts by means of elements from GL_{n}(F) allow to get rid of the “erroneous” set and to obtain a linear combination of minors vanishing at all nonsingular matrices. Finally, we prove that it is impossible.

1 A product of linear functions in the algebra of functions over a finite field

Denote by A the algebra of all functions f : F^{n^{2}} → F which can be naturally identified with the quotient algebra

F [X_{1,1}, …, X_{n,n}]/({X_{i,j}^{q} − X_{i,j}}_{1≤i,j≤n})

For any set E ⊂ F^{n^{2}} of n × n matrices one can consider (as in [S87]) a quotient algebra A_{E} of A over the ideal of all the functions from A vanishing everywhere out of E. Obviously, dim A_{E} = dim_{F} A_{E} = q^{n^{2}}− | E |. Conversely, any quotient algebra of A equals to A_{E} for a suitable E (we do not use this remark). Talking about some elements from A_{E} we mean the images of the elements from A in the quotient algebra.

Fix a constant γ > 0 satisfying the inequality γ < q^{−q/2}. Then there exists a constant β such that

q^{qγ} < q^{β} < γ^{−sγ}  (2)

Introduce also a threshold

r = [β n]  (3)

For the time being we fix a product ∏_{m} L_{ℓ,m} (of linear functions (see (1)). By its rank r_{ℓ} we mean the dimension of the family of the linear functions {L_{ℓ,m}}_{m}, in other words, the rank of the matrix of their coefficients (a_{i,j}^{(ℓ,m)}, a_{0}^{(ℓ,m)}) (which has n^{2}+1 columns, hence r_{ℓ} ≤ n^{2}+1). We treat separately two cases: when the rank r_{ℓ} is less or greater, respectively, than the threshold r and consider the restriction of the product along with its derivatives onto the space F^{n^{2}} (in other words, the points defined over F).

Large rank Let r_{ℓ} ≥ r. Then the number of points from space F^{n^{2}} (of all n × n matrices with the entries from F), at which at most γn among the linear functions {L_{ℓ,m}}_{m} vanish, does not exceed

q^{n^{2}−r_{ℓ}}((q − 1)^{r_{ℓ}} + (\binom{r_{ℓ}}{1}) (q − 1)^{r_{ℓ}−1}

+ … + (\binom{r_{ℓ}}{⌈γn⌉}) (q − 1)^{r_{ℓ}−⌈γn⌉})

since one can choose a basis L_{1}, …, L_{r_{ℓ}} of r_{ℓ} functions among {L_{ℓ,m}}_{m} and assign in an arbitrary way the values for L_{1}, …, L_{r_{ℓ}} (among these values at most γn are zeros). A described point will play a role of an “erroneous” point at which all the derivatives of the product ∏_{m} L_{ℓ,m} of the order ⌈γn⌉ may not vanish. The obtained bound can be estimated from above by

q^{n^{2}−r_{ℓ}} (\binom{r_{ℓ}}{⌈γn⌉}) (q − 1)^{r_{ℓ}−⌈γn⌉}(γn + 1) (4)
since  the  sequence

(q − 1)^{r_{ℓ}}, (\binom{r_{ℓ}}{1})(q − 1)^{r_{ℓ}−1}, … increases until (\binom{r_{ℓ}}{⌈r_{ℓ}/q⌉})(q − 1)^{r_{ℓ}−⌈r_{ℓ}/q⌉} and beyond that decreases (taking into account (3) and the left inequality (2)). Now we show that (4) can be estimated from above by

q^{n^{2}}α^{n}  (5)

for a suitable α < 1 depending on q, γ, β. Denote r = y_{0}qγn (for an appropriate y_{0} > 1 (see (3))) and r_{ℓ} = yqγn where y ≥ y_{0}. Using Stirling’s formula one concludes that (4) is less (up to a factor polynomial in n) than q^{n^{2}}(\frac{yq(q−1)}{(yq−1)q})^{yqγn}(\frac{yq−1}{q−1})^{γn}. It suffices to check

that (\frac{yq(q−1)}{(yq−1)q})^{yq}(\frac{yq−1}{q−1}) < α_{1} for any y ≥ y_{0} and a certain α_{1} < 1 depending only on q, y_{0}. The logarithmic derivative q log \frac{y(q−1)}{yq−1} (over y) of the left side of the latter inequality is negative for any y > 1, hence the left side decreases for y ≥ 1 (for y = 1 it equals 1), that proves (5).

Small rank Now let r_{ℓ} < r. Note that derivatives of all the orders (actually, we are interested just in the order ⌈γn⌉) of the product ∏_{m} L_{ℓ,m} lie in the F -linear hull of the products of the form L_{1}^{i_{1}} ⋯ L_{r_{ℓ}}^{i_{r_{ℓ}}} for all nonnegative integers i_{j}, 1 ≤ j ≤ r_{ℓ}. When subsequently we restrict these derivatives onto the space F^{n^{2}}, thus treating them as elements from the algebra A, they would lie in the F -linear hull of the products L_{1}^{i_{1}} ⋯ L_{r_{ℓ}}^{i_{r_{ℓ}}}, 0 ≤ i_{j} ≤ q − 1, 1 ≤ j ≤ r_{ℓ}. Therefore, the dimension of the set of these images in A of the derivatives is less than q^{r}. The derivatives of the order ⌈γn⌉ of Det are exactly the minors M_{I,J} of the size (n − ⌈γn⌉) × (n − ⌈γn⌉), where I, J are subsets of the sets of rows and columns, respectively, | I |=| J |= n − ⌈γn⌉. We take all the derivatives of the order ⌈γn⌉ of both sides of (1) and subsequently restrict them onto F^{n^{2}} (thus, treating them as elements from the algebra A). Denote by E ⊂ F^{n^{2}} the union of the (“erroneous”) sets considered above for all the products from (1) of big ranks. Then the images in the quotient algebra A_{E} of taken derivatives vanish for all big rank products and we conclude with the following Lemma (making use also of (5))

Lemma 1 For any δ > 1, if Det has a representation (1) with N < δ^{n} then the set of all minors M = {M_{I,J}}_{|I|=|J|=n−⌈γn⌉} has the dimension less than δ^{n}q^{r} in the quotient algebra A_{E} for an appropriate subset E ⊂ F^{n^{2}} of the size | E |≤ q^{n^{2}}(δα)^{n}.

Remark. The statement of the Lemma is nontrivial when δ satisfies the following inequalities

δα < 1; δq^{β} < γ^{−2γ}  (6)

The second inequality means that the dimension of the minors from the Lemma is less than the number (\binom{n}{⌈γn⌉})^{2} of all (n − ⌈γn⌉) × (n − ⌈γn⌉) minors (due to the Stirling’s formula and (3)). Furthermore, any small enough δ > 1 satisfies (6) due to the right inequality (2), and any such δ one could use in the statement of the Theorem (see above).

Henceforth, we assume that δ satisfies (6).

2 Group symmetry on polynomials vanishing at matrices

Denote by H (being isomorphic to F^{\binom{n}{⌈γn⌉}}^{2}) the F -space of all the linear combinations of the minors from M. Observe that nonzero elements of H are also nonzero in A (a stronger statement will appear below in Lemma 3 ), thereby one can think that H ⊂ A. For any point (matrix) a ∈ F^{n^{2}} denote by H_{a} ∈ H a hyperplane consisting of all f ∈ H such that f(a) = 0. Lemma 1 states actually that the codimension in H

c = codim ( ⋂_{a∉E} H_{a}) < δ^{n}q^{r}

Because of the second inequality (6) and again the Stirling’s formula we get the inequality

dim H > c η^{n}  (7)

for a suitable constant η > 1.

Denote the full linear groups G = Gl_{n}(F) ⊂ F^{n^{2}}, it is well known that

|G| = (q^{n} − 1)(q^{n} − q) ⋯ (q^{n} − q^{n−1})

≥ q^{n^{2}}(q − 2)/(q − 1)

(remind that q ≥ 3). For any g ∈ G one can consider an F -linear operator T_{g} : H → H defined for any f ∈ H and any matrix a ∈ F^{n^{2}} by the formula (T_{g}(f)) (a) = f(ga) (moreover, one could define T_{g_{1}} by the same formula for any not necessarily nonsingular matrix g_{1} ∈ F^{n^{2}}). The latter formula defines an operator T_{g} : H → H since the minors from M of the matrix ga are the linear combinations (with the coefficients depending only on g) of the minors from M of a. Thus, T_{g} provides a representation of G because T_{g_{1}g_{2}} = T_{g_{1}}T_{g_{2}} (more precisely, this representation is the direct sum of \binom{n}{⌈γn⌉} copies of ⌈γn⌉-th wedge power of the natural representation of G on F^{n}). Clearly T_{g^{−1}}(H_{a}) = H_{ga}. Consider now a plane

P = ⋂_{a∈G\E} H_{a} ⊂ H,

its codimension c_{1} = codim P ≤ c. Also denote E_{1} = E ∩G. So, from now on we restrict ourselves to considering just matrices from G (rather than from the whole set of matrices F^{n^{2}}). Now assume that a subset S ⊂ G satisfies the following property

⋃_{g∈S} g (G \ E_{1}) = G  (8)

For any g ∈ G we have

T_{g^{−1}}(P) = ⋂_{a∈G\E_{1}} T_{g^{−1}}(H_{a}) = ⋂_{b∈g(G\E_{1})} H_{b}.

Therefore, we get from (8) that

⋂_{b∈G} H_{b} = ⋂_{g∈S} T_{g^{−1}}(P)  (9)

Next we need the following combinatorial lemma (see e.g. [L75]).

Lemma 2([L75]) Let (V, R) be a directed (regular) graph with |V | = m vertices and with the in-degree and the out-degree of each vertex both equal to d. Then there exists a subset U ⊂ V of a size O(\frac{m}{d} log(d + 1)) such that for any vertex v ∈ V there is a vertex u ∈ U forming an edge (u, v) ∈ R.

Construct a directed regular graph with the set of vertices G and an edge (g_{2}, g_{1}) if and only if g_{2}^{−1}g_{1} ∉ E_{1}. Applying to this graph Lemma 2 supplies us with a set S ⊂ G such that for any g_{1} ∈ G there is g ∈ S satisfying g^{−1}g_{1} ∉ E_{1}, or equivalently g_{1} ∈ g(G \ E_{1}). Thus, S fulfills (8). According to Lemma 2 and taking into account Lemma 1 and the first inequality (6)

|S| ≤ O (\frac{|G|}{|G| − q^{n^{2}}(δ α)^{n}} n^{2} log q) ≤ O(n^{2}).

Finally, we show that ⋂_{b∈G} H_{b} ≠ 0. Indeed, codim T_{g^{−1}}(P) = codim P = c_{1} ≤ c for any g ∈ G. Hence codim ⋂_{g∈S} T_{g^{−1}}(P) ≤ O(|S| c_{1}) ≤ O(n^{2} c) which is less than dim H because of (7). Therefore, 0 ≠ ⋂_{g∈S} T_{g^{−1}}(P) = ⋂_{b∈G} H_{b} (see (9)). Take an arbitrary 0 ≠ f ∈ ⋂_{b∈G} H_{b}, this means that f vanishes at all nonsingular matrices. So, to complete the proof of the Theorem (see the introduction), we need the following lemma.

Lemma 3 No multilinear polynomial 0 ≠ f ∈ F [X_{1,1}, …, X_{n,n}] vanishes at all nonsingular matrices (note that q ≥ 3).

Proof of Lemma 3 goes by induction on n. The base of induction for n = 1 is evident. For the inductive step suppose the contrary. Some variable occurs in f, permuting the rows and the columns we can assume w.l.o.g. that X_{n,n} occurs in f. Then f = X_{n,n} f_{1} + f_{0}, where f_{1} ≢ 0, f_{0} are multilinear polynomials being independent from X_{n,n}. On the other hand, Det = X_{n,n} M_{n,n} + h, where M_{n,n} is (n − 1) × (n − 1) minor and h is independent from X_{n,n}. For the time being, specify the variables X_{k,ℓ} = x_{k,ℓ}^{(0)} ∈ F for all 1 ≤ k, ℓ ≤ n−1 in such

a way that M_{nn}({x_{k,ℓ}^{(0)}}) ≠ 0 (so far, there are many possibilities for specifying). Also we get a multilinear polynomial

f({x_{k,ℓ}^{(0)}}) =
X_{n,n}f_{1}({x_{k,ℓ}^{(0)}}) + f_{0}({x_{k,ℓ}^{(0)}}) =
X_{n,n}\overline{f}_{1} + \overline{f}_{0},
where  \overline{f}_{1},  \overline{f}_{0},

∈ F [X_{n,1}, …, X_{n,n−1}, X_{1,n}, …, X_{n−1,n}]. For any set of the values of the variables

X_{n,k} = x_{n,k}^{(0)} ∈ F, X_{k,n} =
x_{k,n}^{(0)} ∈ F, 1 ≤ k ≤ n − 1 (10)

there are exactly (q − 1) ≥ 2 values of X_{n,n} such that Det does not vanish. Therefore, the multilinear polynomials \overline{f}_{1}, \overline{f}_{0} vanish identically: indeed, otherwise for some values (10) a nonvanishing identically linear polynomial

X_{n,n} \overline{f}_{1}(\{x_{n,k}^{(0)}, x_{k,n}^{(0)}\}_{k})+
\overline{f}_{0}(\{x_{n,k}^{(0)}, x_{k,n}^{(0)}\}_{k}) ∈ F [X_{n,n}]

would have q − 1 ≥ 2 roots.

On the other hand, there is an appropriate set of values (10) for which the substitution of these values f̃_{1} = f_{1}({x_{n,k}^{(0)}, x_{k,n}^{(0)}}_{k}) ∈ F [X_{1,1}, …, X_{n−1,n−1}] provides a nonvanishing identically polynomial. As we have seen above, f̃_{1} vanishes at any nonsingular (n−1)× (n − 1) matrix {x_{k,ℓ}^{(0)}}_{1≤k,ℓ≤n−1}; that contradicts to the inductive hypothesis and proves Lemma 3. □

3 Open Problems

An intriguing open problem remains to extend our exponential lower bound for depth 3 arithmetic circuits to arbitrary fields including characteristic zero.

Acknowledgements

We thank László Babai, Sasha Razborov, Avi Widgerson, and Andy Yao for interesting discussions on the subject of this paper.

References

[G82] D. Grigoriev, Lower Bounds in Algebraic Complexity, J. Soviet Math., 29 (1985), pp. 1388–1425.

[H77] R. Hartshorne, Algebraic Geometry, Springer Verlag, 1977.

[L75] L. Lovász, On the Ratio of Optimal Integral and Rational Covers, Discrete Mathematics, 13 (1975), pp. 383–390.

[N91]  N.  Nisan,  Lower

Bound for Non-Commutative Computation, Proc. 23rd ACM STOC (1991), pp. 410–418.

[L84] S. Lang, Algebra (2nd Edition), Addison-Wesley, 1984.

[NW95] N. Nisan and A. Widgerson, Lower Bound on Arithmetic Circuits via Partial Derivatives, Proc. IEEE FOCS (1995), pp. 16–25.

[R87] A. Razborov, Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with Logical Addition, Math. Notes, 41 (1987), pp. 333–338.

[R98] A. Razborov, Personal communication, 1998.

[S87] R. Smolensky, Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity, Proc. 19th ACM STOC (1987), pp. 77–82.

[S73] V. Strassen, Die Berechnungskomplexität von Elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1973), pp. 238– 251.

[S76] V. Strassen, Computational Complexity over Finite Fields, SIAM J. Comput. 5 (1976), pp. 324–331.

[V79] L. Valiant, Completeness Classes in Algebra, Proc. 11th ACM STOC (1979), pp. 259–261.