Authors Pavel Hrube{\v{s}}, Amir Yehudayoff,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129
www.theoryofcomputing.org
Arithmetic Complexity in Ring Extensions
Pavel Hrubeš∗ Amir Yehudayoff†
Received: May 25, 2009; published: May 9, 2011.
Abstract: Given a polynomial f with coefficients from a field F, is it easier to compute f
over an extension ring R than over F? We address this question, and show the following. For
every polynomial f , there is a noncommutative extension ring R such that F is in the center
of R and f has a polynomial-size formula over R. On the other hand, if F is algebraically
closed, no commutative extension ring R can reduce formula or circuit complexity of f . To
complete the picture, we prove that over any field, there exist hard polynomials with zero-one
coefficients. (This is a basic theorem, but we could not find it written explicitly.) Finally,
we show that low-dimensional extensions are not very helpful in computing polynomials.
As a corollary, we obtain that the elementary symmetric polynomials have formulas of size
nO(log log n) over any field, and that division gates can be efficiently eliminated from circuits,
over any field.
ACM Classification: F.2.1
AMS Classification: 03D15
Key words and phrases: algebraic complexity, algebraic extensions
1 Introduction
We investigate the following general question: given a field F and a polynomial f with coefficients from F,
is it easier to compute f over a ring extension R ⊇ F than over F? As our model of computation we take
the standard model for computing polynomials, arithmetic circuits. In principle, the circuit complexity
of a polynomial can decrease when working in a larger field or ring. This is related to the fact that in
the circuit model, we assume that addition and multiplication of elements of the underlying ring can be
∗ Partially supported by NSF grant CCF 0832797.
† Partially supported by NSF grant CCF 0832797.
2011 Pavel Hrubeš and Amir Yehudayoff
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2011.v007a008
PAVEL H RUBE Š AND A MIR Y EHUDAYOFF
performed at unit cost, no matter how complicated the ring is. We always assume that the field F is in the
center of the extension ring R we investigate, that is, for all v ∈ F and a ∈ R we have va = av.
One example, where the order of the underlying field is important, is the computation of the elementary
symmetric polynomials; the elementary symmetric polynomials have small formulas over large fields, but
we do not know whether they have polynomial-size formulas when the field is small. This is essentially
due to a powerful interpolation argument, first suggested by Ben-Or, see [9]. In the converse direction, we
know how to prove exponential lower bounds on the size of depth-three circuits over finite fields [6, 5],
but we do not know how to do that over infinite fields. Nevertheless, it is not known whether circuits over
larger fields are more powerful than over smaller ones.
From a different perspective, it was shown in [8] that the permanent is computable by polynomial-size
formulas when working over a large Clifford algebra. In this approach, it is assumed that addition and
multiplication of elements of the Clifford algebra can be performed at unit cost. In fact, the algebra has
an exponential dimension and if we wanted to represent the computations as, say, matrix addition and
multiplication, we would require exponentially large matrices. We can view this as computation over a
ring extension of the real numbers.
We start with a mildly surprising observation (that generalizes the Clifford-based formulas for the
permanent): any polynomial of degree d in n variables has a formula of size O(dn) over some noncom-
mutative ring extension. We then show that the situation is quite different in the case of commutative
extensions: if a field F is algebraically closed and f is a polynomial over F, then for any commutative
ring extension R of F, computing f over R is not easier than over F. In this sense, commutative extensions
are weaker than noncommutative ones. This, however, does not guarantee that for any field F, there
exist polynomials that are hard over any commutative extension of F. To complete the picture, we show
that over any field, there exist polynomials with zero-one coefficients which require large circuits over
the field. Thus, when the field F is algebraically closed, the hard polynomials are also hard over any
commutative extension of F. This theorem seems to be a “folklore” result; it is a theorem without which
proving lower bounds for algebraic circuits would be virtually impossible. However, we could not find an
explicit statement of it. We note that a similar argument shows that over any field, there exist zero-one
tensors of high tensor rank (or zero-one matrices that are rigid).
Finally, we consider ring extensions of a bounded linear dimension. We show that if R ⊇ F has,
as a vector space, small dimension, then any computation over R can be ‘efficiently’ simulated by a
computation over F (see Theorem 4.2 for more details). As two applications, we show that elementary
symmetric polynomials have formulas of size nO(log log n) over any field, and that divisions can be efficiently
eliminated from circuits over any field (the latter was known for infinite fields).
2 Preliminaries
We denote the family of sub-multisets of size d of [n] = {1, . . . , n} by [n]{d} and we denote by [n]d the
family of ordered d-tuples with entries from [n]. Logarithms are always to the base two.
Rings and polynomials We assume that a ring is always a unital ring, a ring with multiplicative identity
element 1 ∈ R. Let X = {x1 , x2 , . . . , xn } be a finite set of variables. A monomial is a product xi1 xi2 · · · xik
with i1 ≤ i2 · · · ≤ ik . We shall write it as xI , where I = {i1 , . . . , ik } is a multiset. A polynomial over a ring
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 120
A RITHMETIC C OMPLEXITY IN R ING E XTENSIONS
R is a finite formal sum
f = ∑ fI xI ,
I
where fI ∈ R is the coefficient of the monomial xI in f . Addition of polynomials is defined by ( f + g)I =
fI + gI . A product f · g is defined as ∑I,J fI gJ xI∪J , where I ∪ J is the union of the multisets I and J. We
denote by R[X] the ring of polynomials in the set X of variables with coefficients from R. Note that the
variables multiplicatively commute with each other, as well as with every element of R, whether the ring
R is commutative or not.
If R? is a ring extending the ring R, the dimension of R? over R, dimR (R? ), is defined as the smallest
natural number k such that there exist e1 , . . . , ek ∈ R? with the following properties:
1. e1 = 1 and every a ∈ R commutes with every ei , i ∈ {1, . . . , k}, and
2. every b ∈ R? can be uniquely written as ∑ki=1 bi ei , with bi ∈ R.
(If no such k exists, the dimension is infinite.) Observe that if the dimension is finite and R is commutative,
then R is in the center of R? . Specifically, when R is also a field, then dimR (R? ) is the dimension of R? as
a vector space over R.
Arithmetic circuits and formulas We are interested in the arithmetic complexity of a polynomial f
over a field F, and how this complexity can change when computing f over a ring R extending F. The
ring R, however, is no longer required to be a field (or even to be commutative).
An arithmetic circuit Φ over the ring R and the variables X is a directed acyclic graph with every
node of indegree either two or zero, labelled in the following manner: every vertex of indegree 0 is
labelled either by a variable in X or by an element of R. Every other node in Φ has indegree two and is
labelled either by × or by +. The circuit Φ computes a polynomial f ∈ R[X] in the obvious manner. An
arithmetic circuit is called a formula if the outdegree of each node is one (and so the underlying graph is
a directed tree). The size of a circuit is the number of nodes, and the depth of a circuit is the length of the
longest directed path.
If f is a polynomial with coefficients from R, we denote by CR ( f ) the size of a smallest circuit over R
computing f . We denote by LR ( f ) the size of a smallest formula over R computing f . Finally, DR ( f )
denotes the smallest depth of a circuit computing f in R.
3 General extensions
We start with an elementary property of arithmetic complexity measures. Let R, R? be two rings and let
H : R → R? be a ring homomorphism. If f = ∑I fI xI is a polynomial in R[X], then fH ∈ R? [X] denotes
the polynomial ∑I H( fI )xI .
The following simple proposition tells us that allowing a circuit to use elements of a larger ring cannot
make it “weaker.”
Proposition 3.1. Let f ∈ R[X]. Let H : R → R? be a ring homomorphism. Then CR? ( fH ) ≤ CR ( f ) and
LR? ( fH ) ≤ LR ( f ). In particular, if R ⊆ R? , then CR? ( f ) ≤ CR ( f ) and LR? ( f ) ≤ LR ( f ).
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 121
PAVEL H RUBE Š AND A MIR Y EHUDAYOFF
Proof. Let Φ be a smallest circuit computing f over R. Let Ψ be the circuit Φ after substituting
each constant a ∈ R by H(a) ∈ R? . Thus Ψ computes fH , and so CR? ( fH ) ≤ CR ( f ). The proof of
LR? ( fH ) ≤ LR ( f ) is similar.
The following theorem shows that if one allows noncommutative ring extensions of arbitrary dimen-
sion, every polynomial can be computed by a polynomial-size formula.
Theorem 3.2. Let R be a ring. Let f ∈ R[X] be a polynomial of degree d (recall |X| = n). Then there
exists R? ⊇ R such that LR? ( f ) = O(dn).
The ring R? depends on the polynomial f . Moreover, it is a noncommutative ring of a large finite
dimension. (The dimension can be taken roughly as nd .) As we will see, noncommutativity and a
significant increase in dimension are inevitable.
Proof. We can assume that f is homogeneous of degree d. (Otherwise introduce a new variable t and
consider polynomial ∑ j t d− j H j ( f ) with H j ( f ) the j-th homogeneous part of f .) Let us introduce a set Z
of dn new variables, Z = {zij : i ∈ {1, . . . , d} and j ∈ {1, . . . , n}}. Let S be the ring of noncommutative
polynomials over the set Z of variables with coefficients from R (defined similarly to a ring of polynomials
except that the variables do not commute among themselves). Consider the formula
∏ (zi1 x1 + zi2 x2 + . . . + zin xn ) , (3.1)
i∈{1,...,d}
which defines a polynomial F ∈ S[X]. The size of this formula is O(dn). Recall that for J ∈ [n]{d} , FJ ∈ S
is the coefficient of xJ in F. Let I ⊆ S be the ideal generated by the polynomials
FJ − fJ , J ∈ [n]{d} .
It is sufficient to prove that I ∩ R = {0}. For then R? = S/I extends R as R/I ∩ R is R, and (3.1) taken as
a formula over R? computes the polynomial f (in this case, FJ = fJ in the ring R? ).
Our goal now is to prove that I ∩ R = {0}. For K = (k1 , . . . , kd ) ∈ [n]d , let zK denote the monomial
1 2
zk1 zk2 · · · zdkd . For the rest of this proof, we call such a monomial an ordered monomial. For a multiset
J = { j1 , j2 , · · · , jd } ∈ [n]{d} , where j1 ≤ j2 ≤ · · · ≤ jd , let J 0 = ( j1 , j2 , . . . , jd ) ∈ [n]d , the d-tuple that is
the ordering of J. For K ∈ [n]d , let us define aK ∈ R by
(
fJ if K = J 0 ,
aK =
0 if K 6= J 0 for every J ∈ [n]{d} .
(Roughly speaking, this definition counts every K once so as to match f .) Since the variables in Z do not
commute, every monomial h ∈ S can be uniquely written as
h = h(1) · zK1 · h(2) · zK2 · · · h(s) · zKs · h(s+1) ,
where each zK` is an ordered monomial, each h(`) is a monomial in S, and s is the maximal integer for
which such a decomposition is possible. E. g., for d = 2 and n = 2, the monomial h = z11 z12 z21 can be
written in such a form with h(1) = z11 , zK1 = z12 z21 and h(2) = 1. For h of such a form, define
h0 = aK1 · · · aKs h(1) h(2) · · · h(s) h(s+1) .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 122
A RITHMETIC C OMPLEXITY IN R ING E XTENSIONS
For g = ∑ j b j h j , where b j ∈ R and the h j ∈ S are monomials, set g0 = ∑ j b j h0j . Define the ideal I = {g ∈
S : g0 = 0}. Then I ⊇ I, and for every nonzero a ∈ R, we have a 6∈ I since a0 = a.
Corollary 3.3. Let R be a ring. Then there exists a ring R ⊇ R such that for every f ∈ R[X] of degree d,
LR ( f ) = O(dn).
The ring R depends neither on f nor on d, and it has infinite dimension over R.
Proof. Let us first show that for every ring R there exists a ring R0 such that every polynomial in f ∈ R[X]
of degree d has a formula of size O(nd) in R0 . Let Fd ⊆ R[X] be the set of all polynomials of degree d
over R. For every f ∈ Fd , let R f ⊇ R be the extension of R with LR f ( f ) = O(dn), given by Theorem 3.2.
Let R0 be direct sum of R f , f ∈ Fd . Each R f can be canonically embedded into R0 . We can also assume
that R ⊆ R0 . This gives LR0 ( f ) = O(dn) for every f ∈ Fd .
Next, define a sequence of rings R0 = R, and Ri+1 = R0i ⊇ Ri (given by the above argument). Define
R = i≥0 Ri . Every f ∈ R[X] has a finite number of coefficients, and hence there exists k such that
S
f ∈ Rk [X]. If f has degree d, then LRk+1 ( f ) = O(dn). Finally, LR ( f ) = O(dn), since Rk ⊆ R.
The situation is entirely different in the case of commutative extensions. We now show that if F
is algebraically closed, then circuit size and formula size cannot be reduced by taking a commutative
extension of F. A similar statement appears in Chapter 4.3 of [1] and we prove it here for completeness.
In other words, given a field F and a polynomial f over F, the complexity of f in any commutative
extension of F is at least the complexity of f in the algebraic closure of F. Theoretically, this would still
allow the alternative that all polynomials from F would have polynomial-size formulas over the algebraic
closure. We shall dispense with this alternative in Theorem 3.7.
Theorem 3.4. Assume that F is an algebraically closed field. Let R be a subring of F and let R? ⊇ R be
a commutative ring. Then for every f ∈ R[X], we have CF ( f ) ≤ CR? ( f ) and LF ( f ) ≤ LR? ( f ).
Proof. Let us argue about circuit size; formula size is similar. Let Φ be a circuit over R? computing
f . Assume that Φ contains a1 , . . . , ak ∈ R? \ R. Let us introduce new variables z1 , . . . , zk . Let Φ0 be the
circuit obtained from Φ by replacing every ai by zi . Thus Φ0 defines a polynomial F with coefficient in
S = R[z1 , . . . , zk ].
Let I ⊆ S be the ideal generated by the polynomials FJ − fJ . (Recall that FJ and fJ are the coefficients
of the monomial xJ in F and f respectively.) The ideal I does not contain 1. This is because the equations
FJ (z1 , . . . , zk ) − fJ = 0 have a common solution a1 , . . . , ak in R? , and so every polynomial h in I satisfies
h(a1 , . . . , ak ) = 0. Since 1 6∈ I, Hilbert’s “Weak Nullstellensatz” tells us that there exist v1 , . . . , vk ∈ F
such that for every J, FJ (v1 , . . . , vk ) − fJ = 0.
Let Φ00 be the circuit obtained by replacing every zi in Φ0 by vi ∈ F. Thus Φ00 computes the polynomial
f , and the size of Φ00 is the same as the size of Φ.
Our next goal is to show that over every field (and hence over every commutative ring), there exist
“hard” polynomials with zero-one coefficients.
Lemma 3.5. Let F be a field. Let F : Fn → Fm be a polynomial map of degree d > 0, that is, F =
(F1 , . . . , Fm ), each Fi is of degree d. Then |F(Fn ) ∩ {0, 1}m | ≤ (2d)n .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 123
PAVEL H RUBE Š AND A MIR Y EHUDAYOFF
Proof. Without loss of generality assume that F is algebraically closed. (Otherwise, we can consider the
n
closure F of F and |F(Fn ) ∩ {0, 1}m | ≤ |F(F ) ∩ {0, 1}m |.) We use a few notions from algebraic geometry.
For formal definitions see, for example, [4]. We start by proving the following stronger claim.
Claim 3.6. Let V ⊆ Fn be an irreducible variety of dimension k and degree r > 0. Then
|F(V ) ∩ {0, 1}m | ≤ r(2d)k .
Proof. The proof of the claim is by induction on k. If k = 0, the variety V is a single point and so
|F(V )| ≤ 1. Let k > 0, and assume that there exists some i ∈ {1, . . . , m} such that both of the varieties
V0 = V ∩ Fi−1 (0) and V1 = V ∩ Fi−1 (1) are nonempty. (If no such i exists, |F(V )| ≤ 1.) Since V0 and V1
are proper subvarieties of V , the dimension of both V0 and V1 is less than k, the dimension of V . Let
ε ∈ {0, 1}, and consider Vε . Since Fi has degree at most d, Bezout’s Theorem (see Section 2.2 in [3]) tells
us that the irreducible components of Vε , say Vε1 , . . . ,Vεtε , satisfy ∑ j∈[tε ] rεj ≤ rd, where rεj = deg(Vεj ). By
the inductive assumption, |F(Vεj ) ∩ {0, 1}m | ≤ rεj (2d)k−1 for every j ∈ [tε ]. Thus,
|F(V ) ∩ {0, 1}m | ≤ ∑ ∑ |F(Vεj ) ∩ {0, 1}m | ≤ 2rd(2d)k−1 = r(2d)k .
ε∈{0,1} j∈[tε ]
Since F is algebraically closed, it follows that Fn is an irreducible variety of dimension n and degree
1, and Claim 3.6 implies the lemma.
The previous lemma shows that the zero-one image of a polynomial map is small. The next theorem
uses the lemma to conclude that there exist hard polynomials with zero-one coefficients. The basic idea
behind the proof of the theorem is that a polynomial computed by a circuit is an image of a polynomial
map.
Theorem 3.7. Let d, n ∈ N and let F be a field. Let m = n+d−1
d . Then there exists a homogeneous
polynomial f of degree d in the variables x1 , . . . , xn with zero-one coefficients such that
!
√ n + d − 1 d/2
CF ( f ) ≥ Ω m ≥ Ω and
d
!
n+d −1 d
m −1
LF ( f ) ≥ Ω ≥ Ω (d log(n + d)) · .
log m d
Proof. Let us start with the first inequality. We first consider a type of circuits we call skeletons. Let
z1 , . . . , zs be new variables. A circuit Γ in the variables x1 , . . . , xn , z1 , . . . , zs with no field elements in it is
called a skeleton. A skeleton Γ computes a polynomial g = ∑J gJ xJ ∈ S[x1 , . . . , xn ] with S = F[z1 , . . . , zs ].
We say that a skeleton Γ defines a polynomial f ∈ F[x1 , . . . , xn ] if there exist v1 , . . . , vs ∈ F such that
f (x1 , . . . , xn ) = g(x1 , . . . , xn , v1 , . . . , vs ). Assume that the size of Γ is at most s. Thus the degree of every
gJ , as a polynomial in z1 , . . . , zs , is at most 2s . Let F : Fs → Fm be the map FI (v1 , . . . , vs ) = gI (v1 , . . . , vs )
for every I ∈ {1, . . . , m}. (We think of I as determining a monomial of total degree exactly d.) The map F
is a polynomial map of degree at most 2s . Moreover, if Γ defines a homogeneous polynomial f , then the
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 124
A RITHMETIC C OMPLEXITY IN R ING E XTENSIONS
vector of coefficients of f is in the image of F. By Lemma 3.5, the skeleton Γ computes at most (2s+1 )s
polynomials with zero-one coefficients.
Every skeleton of size at most s contains at most n + s variables, the symbols +, ×, and no constants.
Thus, there are at most (n + s + 2)s s2s skeletons of size at most s (the indegree of each node is at most
2
two). Hence, skeletons of size at most s define at most 2s(s+1) (n + s + 2)s s2s ≤ 2cs polynomials with
zero-one coefficients, where c > 0 is a constant (we can assume s > n).
Back to considering general circuits. Let Φ be a circuit over F in the variables x1 , . . . , xn of size at
most s. The circuit Φ contains at most s elements of F, say a1 , . . . , as (the ordering is arbitrary but fixed).
Let Γ be the skeleton obtained from Φ by replacing every ai by zi . The size of Γ is at most s. In addition,
if Φ computes a polynomial f ∈ F[x1 , . . . , xn ], then Γ defines f . Since there exist 2m homogeneous
polynomials of degree d with zero-one coefficients, in order to compute all such polynomials, we must
2
have 2cs ≥ 2m and so s ≥ Ω(m1/2 ). For the latter inequality in the statement of the theorem, we use the
estimate
n+d −1 d
n+d −1
≥ .
d d
To obtain a lower bound on LF ( f ), we use a similar argument. Consider formula skeletons instead of
circuit skeletons. The difference is that for formulas, gJ has degree at most s. Hence F : Fs → Fm is a map
of degree at most s, and a formula skeleton defines at most (2s)s polynomials with zero-one coefficients.
We note that the number of circuit skeletons above is an upper bound on the number of formula skeletons
of size s, and conclude that formula skeletons define at most (2s)s (n + s + 2)s s2s ≤ 2cs log s polynomials
with zero-one coefficients (c > 0 is a constant). This gives 2cs log s ≥ 2m and hence s ≥ Ω(m log−1 m). For
the latter inequality in the statement of the theorem, we estimate
e(n + d − 1) d
n+d −1
log ≤ log = O(d log(n + d)) .
d d
To match the statement of the theorem, we must show that that the lower bounds on CF and LF can be
achieved simultaneously. This follows from the fact that the above arguments give that majority of the
polynomials with zero-one coefficients have this complexity.
Corollary 3.8. The statement of Theorem 3.7 holds for any non-trivial commutative ring R (instead of
F).
Proof. Let R be a non-trivial commutative ring (i. e., 0 6= 1), and let I be a maximal ideal in R. Thus
F = R/I is a field. Let f be the polynomial given by Theorem 3.7 with the field F. Let H be the canonical
homomorphism H : R → F. Proposition 3.1 tells us that CF ( fH ) ≤ CR ( f ). Finally, the polynomial f has
zero-one coefficients, and so f = fH .
The existence of hard polynomials with real coefficients was proved, for example, in [2]. The
argument of [2] does not apply to polynomials with zero-one coefficients; the polynomials considered
in [2] have algebraically independent coefficients (so-called generic polynomials). On the other hand,
the circuit lower bound on generic polynomials essentially matches the formula lower bound from
Theorem 3.7, whereas the circuit lower bound in Theorem 3.7 is roughly the square root of the “expected”
value.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 125
PAVEL H RUBE Š AND A MIR Y EHUDAYOFF
Tensor rank and matrix rigidity Lemma 3.5 can be applied to several other problems; for example, it
implies the existence of zero-one tensors of high tensor rank, and zero-one matrices of high rigidity.
Valiant defined the concept of matrix rigidity [12], and proved the existence of matrices of high
rigidity over any field. In the case of a finite field, the proof is by a counting argument, and in the infinite
case, by a dimension argument. The matrices take as entries all possible field elements. The existence of
rigid zero-one matrices was proved in [7], in the case of the field of real numbers. The authors use a real
number version of Lemma 3.5 which is due to Warren [13]. Warren’s theorem is a stronger version of
Lemma 3.5, but it applies exclusively to R.
Here is a sketch of a proof of the existence of tensors of high rank. Consider a three dimensional
tensor, say, T : [n]3 → F. Recall that a rank one tensor is a tensor such that t(x1 , x2 , x3 ) = t1 (x1 )t2 (x2 )t3 (x3 )
for every x1 , x2 , x3 ∈ [n]. Also recall that the tensor rank of a tensor T is defined as the minimal integer r
such that T = ∑i∈[r] t (i) with t (i) of rank one. Let us count the zero-one tensors of rank at most r. Each
(i) (i) (i) (i)
rank-one tensor t (i) = t1 t2 t3 is defined by 3n variables, n variables for each t j . Think of t (i) as a
3
polynomial map from F3n to Fn ; as such it has degree three. Similarly, a rank-r tensor is a polynomial
3
map from F3nr to Fn . Lemma 3.5 tells us that the number of zero-one tensors of rank at most r is at
3
most 63nr . On the other hand, the number of zero-one tensors is 2n . Thus, there exist zero-one tensors of
tensor rank Ω(n2 ).
4 Extensions of small dimension
We start by observing that formulas can be assumed to be balanced. (This type of argument is well-known,
see, e. g., [10].)
Lemma 4.1. Let R be a ring. Then for every polynomial f , c−1 DR ( f ) ≤ log LR ( f ) ≤ DR ( f ), where c ≥ 1
is a universal constant.
Proof. Since the number of nodes in a tree with indegree at most two of depth ` is at most 2` , log LR ( f ) ≤
DR ( f ). The proof of the other inequality is by induction on the size of the formula. Let Φ be a smallest
formula for f , that is, LR ( f ) = s where s is the size of Φ. Since the indegree is at most two, let u be a
node in Φ so that Φu , the subformula of Φ rooted at u, is of size between s/3 and 2s/3. Denote by g the
polynomial computed by u, and denote by fa , a ∈ R, the polynomial computed at the output of Φ after
deleting the two edges (and hence the two subformulas) going into u and labelling it by a. Thus,
f = ( f1 − f0 )g + f0
(this follows by induction on the structure of Φ). All the polynomials g, f0 and f1 have formulas of size at
most 2s/3. By induction, every h ∈ {g, f0 , f1 } admits DR (h) ≤ c log LR (h); let Φh be a formula for h of
depth DR (h) ≤ c log(2s/3). Set
Ψ = (Φ f1 + (−1) × Φ f0 ) × Φg + Φ f0 .
Thus, Ψ computes f and its depth is at most c log(2s/3) + 4 ≤ c log s with c ≥ 1 a constant.
The following theorem shows that extensions of low dimensions are not extremely helpful when
computing polynomials.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 126
A RITHMETIC C OMPLEXITY IN R ING E XTENSIONS
Theorem 4.2. Let R and R? ⊇ R be rings such that dimR (R? ) = k. Let f ∈ R[X]. Then
CR ( f ) ≤ O(k3 )CR? ( f ) and LR ( f ) ≤ (LR? ( f ))O(log k) .
Proof. Let 1 = e1 and e2 , . . . , ek be elements of R? such that every a ∈ R? can be uniquely written as
∑ ai ei .
i∈{1,...,k}
We denote a = ha1 , . . . , ak i. Addition and multiplication in R? can be performed as (a + b)i = ai + bi and
(a · b)i = λi (a, b), where λi is a bilinear map over R. Every λi is computable by a circuit φi over R of size
at most ck2 and depth at most c log k with c > 0 a constant.
For g = ∑ gJ xJ ∈ R? [X] and i ∈ {1, . . . , k}, define gi ∈ R[X] as ∑J gJ,i xJ , where gJ,i = (gJ )i . Denote
g = hg1 , . . . , gk i. For every i ∈ {1, . . . , k},
(g + h)i = gi + hi and (g · h)i = λi (g, h) ;
for example,
(g · h)i = ∑(gI hJ )i xI xJ = ∑ λi (gI , hJ )xI xJ = λi ∑ I I ∑ J J = λi (g, h) .
g x , h x
I,J I,J I J
We start by considering circuit size. Let Φ be an arithmetic circuit over R? of size s and depth d
computing f . We simulate the computations in R? by the computation in R. Let us define a new circuit Ψ
over R as follows. For every node u in Φ that computes gu , the circuit Ψ contains k + 1 nodes u0 , . . . , uk
computing gu0 , . . . , guk . We define Ψ inductively as follows. If u is a leaf, then gu is either a variable or
an element of R? . In this case, label each ui by (gu )i . If u = v + w is a sum node, set ui = vi + wi . If
u = v × w is a product node, set ui = λi (v, w).
The size of Ψ is at most O(k3 )s and its depth is at most d · O(log k). If u is the output node of Φ, then
u0 computes the polynomial f0 . Since f ∈ R[x1 , . . . , xn ], we have f = f0 , and hence u0 computes f . This
shows that CR ( f ) ≤ O(k3 )CR? ( f ).
For formula size, we use Lemma 4.1. Let Φ be a circuit computing f over R? of depth D = DR? ( f ) ≤
c log LR? ( f ). The above argument tells us that f has a circuit over R of depth at most D · O(log k)
computing f . Lemma 4.1 now tells us that LR ( f ) ≤ 2D·O(log k) ≤ LR? ( f )O(log k) .
One consequence of Theorem 4.2 is that formulas over R can polynomially simulate formulas over
C (the same holds for circuits). More exactly, LC ( f ) ≤ (LR ( f ))c1 and CC ( f ) ≤ c2CR ( f ) for appropriate
constants c1 , c2 > 0. Here are two more applications of Theorem 4.2.
Elementary symmetric polynomials over finite fields The elementary symmetric polynomial of
degree k is the polynomial
∑ xi1 xi2 · · · xik .
i1 <i2 <···<ik ∈[n]
Ben-Or showed that over large fields the elementary symmetric polynomials have formulas of size
O(n2 ) (see [9]). This construction is by interpolation, which requires the existence of n + 1 distinct field
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 127
PAVEL H RUBE Š AND A MIR Y EHUDAYOFF
elements. Nevertheless, Theorem 4.2 implies that we can find relatively small formulas for the symmetric
polynomials over any finite field as well. Indeed, let F be a finite field and let E be an extension of F
of dimension 2 log n, so that the order of E is at least n + 1. As mentioned above, over E we can use
interpolation to construct a formula of size O(n2 ) for the symmetric polynomial. Now, Theorem 4.2 tells
us that we can simulate this formula by a formula of size nO(log log n) over F.
Eliminating division nodes over finite fields A circuit with divisions is a circuit that has one more
type of nodes, divisions gates, that are labelled by /. Every node of such a circuit computes a formal
rational function, an element of the field F(X). We require that for any node u/v in the circuit, v computes
a nonzero rational function g (though it may happen that g = 0 on every input from F). In [11], Strassen
proved that, over an infinite field, if a polynomial f ∈ F[X] of degree d is computable by a circuit Φ of
size s with divisions, it is also computable by a circuit Ψ of size O(d 2 s) without divisions (see also [1],
Chapter 7.1).
Strassen’s argument works over any field which is large enough: Without loss of generality, we can
assume that Φ contains exactly one division node u/v that computes g1 /g2 with polynomials g1 , g2 ∈ F[X].
(This is true as we can efficiently simulate the denominator and numerator separately without using
divisions.) For the argument to work, it is sufficient to find a1 , . . . , an ∈ F such that g2 (a1 , . . . , an ) 6= 0.
Since the degree of g2 is at most 2s , it is enough to have |F| ≥ 2s + 1 (as the Schwartz-Zippel Lemma
tells us).
Here is how we can make it work over small fields as well. If F is not large enough, we can take a
field extension E of degree greater than s and compute f over E efficiently. Now, Theorem 4.2 implies
that we can, in fact, compute f over F by a circuit of size O(s3 d 2 s) = poly(s, d).
Acknowledgement We wish to thank Avi Wigderson for helpful discussions.
References
[1] P ETER B ÜRGISSER , M ICHAEL C LAUSEN , AND M OHAMMAD A. S HOKROLLAHI: Algebraic
complexity theory. Volume 315 of Grundlehren der mathematischen Wissenschaften. Springer,
1997. 123, 128
[2] P ETER B ÜRGISSER , T HOMAS L ICKTEIG , AND M ICHAEL S HUB: Test complexity of generic
polynomials. J. Complexity, 8(3):203–215, 1992. [doi:10.1016/0885-064X(92)90022-4] 125
[3] V. I. DANILOV: Algebraic varieties and schemes. In I. R. S HAFAREVICH, editor, Algebraic
Geometry: Algebraic Curves, Algebraic Manifolds and Schemes, volume 23 of Algebraic Geometry
I, Encyclopedia of Mathematical Sciences, pp. 167–297. Springer, 1994. 124
[4] Z EEV DVIR: Extractors for varieties. In Proc. 24th IEEE Conf. Comput. Complexity (CCC’09), pp.
102–113. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.7] 124
[5] D. G RIGORIEV AND A. R AZBOROV: Exponential lower bounds for depth 3 arithmetic circuits in
algebras of functions over finite fields. Appl. Algebra Engrg. Comm. Comput., 10(6):465–487, 2000.
[doi:10.1007/s002009900021] 120
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 128
A RITHMETIC C OMPLEXITY IN R ING E XTENSIONS
[6] D IMA G RIGORIEV, M AREK K ARPINSKI , AND A NDREW C HI -C HIH YAO: An exponential lower
bound on the size of algebraic decision trees for Max. Comput. Complexity, 7(3):193–203, 1998.
[doi:10.1007/s000370050010] 120
[7] P. P UDL ÁK AND V. R ÖDL: Some combinatorial-algebraic problems from complexity theory.
Discrete Math., 136(1–3):253–279, 1994. [doi:10.1016/0012-365X(94)00115-Y] 126
[8] R EN É S CHOTT AND G. S TACEY S TAPLES: Reductions in computational complexity using Clifford
algebras. Adv. in Appl. Clifford Algebr., 20:121–140, 2010. [doi:10.1007/s00006-008-0143-2] 120
[9] A MIR S HPILKA AND AVI W IGDERSON: Depth-3 arithmetic formulae over fields of characteristic
zero. In Proc. IEEE 14th Conf. Comput. Complexity (CCC’99), pp. 87–96. IEEE Comp. Soc. Press,
1999. [doi:10.1109/CCC.1999.766267] 120, 127
[10] P. M. S PIRA: On time-hardware complexity tradeoffs for Boolean functions. In Proc. 4th. Hawaii
Intern. Symp. Syst. Sciences., pp. 525–527, 1971. 126
[11] VOLKER S TRASSEN: Vermeidung von Divisionen. J. Reine Angew. Math., 264:184–202, 1973.
[doi:10.1515/crll.1973.264.184] 128
[12] L ESLIE G. VALIANT: Graph-theoretic properties in computational complexity. J. Comput. System
Sci., 13(3):278–285, 1976. [doi:10.1016/S0022-0000(76)80041-4] 126
[13] H UGH E. WARREN: Lower bounds for approximations by nonlinear manifolds. Trans. Amer. Math.
Soc., 133:167–178, 1968. [doi:10.2307/1994937] 126
AUTHORS
Pavel Hrubeš
Postdoctoral fellow
Princeton University, NJ
pahrubes@gmail.com
Amir Yehudayoff
Senior lecturer
Technion, Haifa, Israel
amir.yehudayoff@gmail.com
ABOUT THE AUTHORS
PAVEL H RUBE Š graduated from Charles University at Prague in 2004; his advisor was Pavel
Pudlák. His thesis focused on proof complexity.
A MIR Y EHUDAYOFF graduated from Weizmann Institute in 2008; his advisor was Ran Raz.
His thesis focused on algebraic complexity with an emphasis on multilinear computation.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 119–129 129