Document [original]

On Numerical Invariants in Algebraic

Complexity Theory

Dissertation

zur Erlangung des Doktorgrades

der Fakult¨at f¨ur Elektrotechnik, Informatik und Mathematik

der Universit¨at Paderborn

vorgelegt von

Martin Lotz

Paderborn, den 17. Mai, 2005

Gutachter: Prof. Dr. Peter B¨urgisser

Prof. Dr. Helmut Lenzing

Prof. Dr. Felipe Cucker

Summary

A common theme in mathematics is the classification of mathematical ob-

jects by assigning numerical invariants to them. There are two ways in which

such numerical invariants can appear in relation to computational complex-

ity. On the one hand, mathematical invariants are used in the context of

proving lower complexity bounds: they serve as obstructions to the existence

of fast algorithms for solving certain problems. On the other hand, it is

the computational complexity of actually computing such invariants that

is of interest. The first part of this thesis is concerned with lower bounds

for the problems of computing linear and bilinear maps. The invariants

used, namely the mean square volume,singular values, and rigidity, belong

to linear algebra. One of the main results is a tight lower bound of order

Ω(nlog n) for the problem of multiplying two polynomials, in the model of

bounded coefficient circuits. This lower bound is extended to circuits for

which a limited number of unbounded scalar multiplications (help gates)

are allowed. The second part is concerned with the complexity of actually

computing numerical invariants. The objects of study are two of the most

prominent invariants in algebraic geometry and topology: the Euler char-

acteristic and the Hilbert polynomial of complex projective varieties. These

problems are studied within the framework of counting complexity classes.

It is shown that the problem of computing the Euler characteristic of a

complex projective variety is on essentially the same level of difficulty as

the problem of counting the number of solutions of a system of polynomial

equations. A similar result is proved for the Hilbert polynomials, when the

input variety is assumed to be smooth and equidimensional.

Danksagungen

An erster Stelle m¨ochte ich meinem Betreuer Peter B¨urgisser herzlichst

danken: F¨ur seine Unterst¨utzung und Leitung, seine Geduld, und f¨ur alles

was ich von ihm gelernt habe (mathematisch, und auch sonst). Estoy muy

agradecido a Felipe Cucker por invitarme a Hong Kong, donde parte de este

trabajo fue escrito, y por su ayuda en varios aspectos.

Dar¨uber hinaus m¨ochte ich mich bedanken bei:

- Joachim von zur Gathen, f¨ur das Bereitstellen eines Teils meiner Stelle,

sein Interesse an meiner Arbeit, und f¨ur wichtige Literaturhinweise.

- Helmut Lenzing und dem Institut f¨ur Mathematik, f¨ur die hervorra-

genden Arbeitsbedingungen, und die Verl¨angerung meiner Stelle, was

es mir erm¨oglicht hat die Arbeit hier zu beenden.

- Andreas Meyer and Peter Scheiblechner, f¨ur wertvolle Gespr¨ache und

Unterst¨utzung in vielfacher Hinsicht.

- Die Teilnehmer der AG Geometrie. Einige der Dinge, die ich dort

gelernt habe, konnten gewinnbringend in diese Arbeit einfliessen.

- Meinen Eltern, Evelina and Friedhelm, f¨ur das kritische Pr¨ufen der

Beweise ;-), und f¨ur sonstige Unterst¨utzung.

Die vorliegende Arbeit wurde durch DFG Sachbeihilfe BU 1371 and

PaSCo (Paderborn Institute for Scientific Computation) unterst¨utzt.

Contents

0 Introduction 1

0.1 Lower Complexity Bounds . . . . . . . . . . . . . . . . . . . . 1

0.2 Complexity Theory in Geometry and Topology . . . . . . . . 8

0.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

0.4 Credits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

I Lower Bounds on the Complexity of Bilinear Maps 21

1 Preliminaries I 23

1.1 The Model of Computation . . . . . . . . . . . . . . . . . . . 23

1.2 Singular Values and Matrix Rigidity . . . . . . . . . . . . . . 25

1.3 Complex Gaussian Vectors . . . . . . . . . . . . . . . . . . . . 26

1.4 Bounding Large Deviations . . . . . . . . . . . . . . . . . . . 27

1.5 Two Useful Inequalities . . . . . . . . . . . . . . . . . . . . . 28

2 Lower Bounds for Linear and Bilinear Maps 29

2.1 The Mean Square Volume Bound . . . . . . . . . . . . . . . . 29

2.2 A Lower Bound on Cyclic Convolution . . . . . . . . . . . . . 31

2.3 An Alternative to Lemma 2.6 (after Raz) . . . . . . . . . . . 36

2.4 Multiplication and Division of Polynomials . . . . . . . . . . 38

3 Unbounded Scalar Multiplications 41

3.1 Extension of the Mean Square Volume Bound . . . . . . . . . 41

3.2 Extremal Values of Gaussian Random Vectors . . . . . . . . . 42

3.3 Cyclic Convolution and Help Gates . . . . . . . . . . . . . . . 43

II Computational Complexity of Euler Characteristics 47

4 Preliminaries II 49

4.1 Algebraic Geometry . . . . . . . . . . . . . . . . . . . . . . . 49

4.2 Algebraic Topology . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3 Transversality . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

vi CONTENTS

4.4 Model of Computation and Complexity . . . . . . . . . . . . 53

5 Counting Complexity Theory 63

5.1 Counting Complexity Classes . . . . . . . . . . . . . . . . . . 63

5.2 Generic Parsimonious Reductions . . . . . . . . . . . . . . . . 66

5.3 Boolean Parts of Complexity Classes . . . . . . . . . . . . . . 72

6 Topological Euler Characteristic 77

6.1 Projective Degrees and Euler Characteristics . . . . . . . . . 78

6.2 Computing Projective Degrees . . . . . . . . . . . . . . . . . 81

6.3 Complexity of the Euler Characteristic . . . . . . . . . . . . . 83

6.4 Expressing Transversality . . . . . . . . . . . . . . . . . . . . 85

6.5 Proof of Proposition 6.3 . . . . . . . . . . . . . . . . . . . . . 87

7 Hilbert Polynomial 91

7.1 Statement of Results . . . . . . . . . . . . . . . . . . . . . . . 91

7.2 Projective Characters . . . . . . . . . . . . . . . . . . . . . . 93

7.3 The Hilbert Polynomial and Projective Characters . . . . . . 99

7.4 Complexity of the Hilbert Polynomial . . . . . . . . . . . . . 100

7.5 Expressing Transversality . . . . . . . . . . . . . . . . . . . . 106

8 Hilbert Polynomial and Degeneracy Loci 111

8.1 Singular Homology Theory . . . . . . . . . . . . . . . . . . . 111

8.2 Chern Classes and Riemann-Roch . . . . . . . . . . . . . . . 113

8.3 Symmetric Functions . . . . . . . . . . . . . . . . . . . . . . . 115

8.4 Proof of Theorem 7.13 . . . . . . . . . . . . . . . . . . . . . . 117

Chapter 0

Introduction

A common theme in mathematics is the classification of mathematical ob-

jects by assigning numerical invariants to them. There are two ways in which

such numerical invariants can appear in relation to computational complex-

ity. On the one hand, mathematical invariants are used in the context of

proving lower complexity bounds: they serve as obstructions to the existence

of fast algorithms for solving certain problems. On the other hand, it is the

computational complexity of actually computing such invariants that is of

interest. The first part of this thesis is concerned with the use of invariants

for proving lower complexity bounds. The problems under consideration are

linear and bilinear maps, and the invariants used, namely the mean square

volume,singular values, and rigidity, belong to linear algebra. The second

part is concerned with the complexity of actually computing numerical in-

variants. The objects of study are two of the most prominent invariants in

algebraic geometry and topology: the Euler characteristic and the Hilbert

polynomial of complex projective varieties.

0.1 Lower Complexity Bounds

0.1.1 Linear Maps

Given an m×nmatrix Aover the complex numbers C, how many arithmetic

operations in Care necessary to compute the linear transformation x7→ Ax

for an input vector x= (x1,...,xn)∈Cn? It is clear that this product

can be computed with a budget of nm multiplications with scalars and

(n−1)madditions. On the other hand, there are obvious examples of

matrices for which far less operations are needed. A less immediate example

is the following:

A=





1 1 1 1

1i−1−i

1−11−1

1−i−1i





, y =Ax =





x1+x2+x3+x4

x1+ix2−x3−ix4

x1−x2+x3−x4

x1−ix2−x3+ix4





.

The vector y=Ax can be computed from xusing only 9 additions and scalar

multiplications, as illustrated by the following sequence of instructions.

2Introduction

g1=x1+x3

g2=x2+x4

g3=x1−x3

g4=x2−x4

g5=i·g4

g6=g1+g2

g7=g3+g5

g8=g1−g2

g9=g3−g5

x1x2x3x4

• • • •

+ + − −

+−+−

• • • •

y1y3y2y4

Figure 1: The Fast Fourier Transform

The above example is a special case of an important linear transformation

called the Discrete Fourier Transform (DFT), while the algorithm presented

in Figure (1) is known as the Fast Fourier Transform (FFT). In general,

the n×nDFT matrix over Cis the matrix DFTn:= ωij0≤i,j<n, where

ω=e2πi/n is an n-th root of unity in C. The Fast Fourier Transform

performs the linear transformation x7→ DFTnxusing O(nlog n) arithmetic

operations (a comprehensive exposition is found in [GG03, Chapter 8]). Is

it possible to significantly improve this bound? Could there be a procedure

that computes the DFT with a number of arithmetic operations that is linear

in n? We don’t know.

There is, however, a strong indication that the FFT algorithm is asymp-

totically optimal with respect to the number of arithmetic operations needed.

The reason for this is a lower bound on the complexity of linear maps due

to Jacques Morgenstern [Mor73]. For an n×nmatrix Awith entries in C,

let C(A) denote the minimal number of additions, subtractions, and scalar

multiplications with scalars of absolute value at most 2, needed to compute

the linear map x7→ Ax. Such a sequence of instructions is called bounded

coefficient circuit (b.c. circuit for short) in the sequel. Morgenstern’s bound

states that

C(A)≥log |det A|.(1)

In words, the absolute value of the determinant, that is, the volume of the

parallelepiped spanned by the rows of A, provides a lower bound for the

size of a bounded coefficient circuit computing the linear map x7→ Ax. It

is known that the determinant of the DFT matrix is nn/2, from which an

2log nlower bound for the Discrete Fourier Transform follows.

In order to derive the Morgenstern’s bound (1), assume (g1,...,gr) to

be an optimal sequence of instructions computing Ax from x= (x1,...,xn).

0.1 Lower Complexity Bounds 3

For 0 ≤i≤r, let Gibe the n×(n+i) matrix whose columns consist of the

vectors representing the linear forms x1,...,xn, g1,...,gi(in particular, G0

is the identity matrix). Let further mi:= voln(Gi) denote the maximum of

the absolute values of all n×nsubdeterminants of Gi. Every giis of the

form gj+gkor λgj, with j, k < i and |λ| ≤ 2. From the multilinearity of

the determinant it follows that mican at most double in each computation

step. Since m0= 1, it follows that |det A| ≤ mr≤2r. Taking logarithms

yields Morgenstern’s bound.

One annoying drawback of this bound is the restriction to constants of

bounded absolute value1. Leslie Valiant [Val76, Val77] analysed the problem

of proving nonlinear lower bounds on the complexity of the Discrete Fourier

Transform, and related linear problems, in the unrestricted model of arith-

metic circuits. Despite many attempts, this problem is still open today. It

should be noted, however, that many algorithms for arithmetic problems,

like the Fast Fourier Transform and the fast algorithms based on it, use only

small constants. Bernard Chazelle [Cha98] advocated the bounded coeffi-

cient model as a natural model of computation by arguing that the finite

representation of numbers is essentially equivalent to bounded coefficients.

In Section 0.1.3, the bounded coefficient property is relaxed by allowing a

limited number of unbounded scalar multiplications (“help gates”), and it

is shown that meaningful lower bounds are still possible in this setting.

0.1.2 Bilinear Maps

An important example of a bilinear map is polynomial multiplication. Given

two univariate polynomials f=Pn−1

i=0 aiXiand g=Pn−1

j=0 bjXjin C[X],

the problem consists of computing the product

f·g=

2n−2

k=0

ckXk, ck=X

i+j=k

aibj.

This map is readily interpreted as a bilinear map ϕ:Cn×Cn→C2n−1on

the coefficient vectors aand b. Polynomial multiplication can be reduced to

the bilinear map of cyclic convolution, and vice versa:

f ? g =

n−1

k=0

ckXk, ck=X

i+j≡kmod n

aibj.

This corresponds to multiplication in the quotient ring C[X]/(Xn−1). The

cyclic convolution, in turn, can be computed using the Fast Fourier Trans-

form (the procedure is described in detail in [GG03, Chapter 8]). The re-

sulting circuit makes use of O(nlog n) arithmetic operations. Again, the

1It is easy to see that the bound of 2 on the absolute value of the scalars can be replaced

with any other constant c, with an increase in size of order log2c.

4Introduction

question arises whether this is optimal. The main result of Part I (Theorem

2.4) consists of an Ω(nlog n) lower bound for the problem of computing the

cyclic convolution, and thus also for polynomial multiplication, in the model

of bounded coefficient circuits.

The proof is based on ideas by Ran Raz [Raz03] to establish a lower

bound on the complexity of a bilinear map (x, y)7→ ϕ(x, y) in terms of

the complexity of the linear map y7→ ϕ(a, y), obtained by specialising the

first input to a(Lemma 1.4). Let Adenote the matrix corresponding to

y7→ ϕ(a, y). A circuit for the computation of y7→ Ay resulting from a

hypothetical bounded coefficient circuit for ϕhas to be transformed into

one with bounded coefficients with only a small increase in size. A lower

bound son C(A) thus leads to a lower bound on the complexity C(ϕ) of the

original bilinear map:

C(ϕ)≥ρC(A)−R≥ρs −R, (2)

where ρand Rdepend on aand an optimal circuit for ϕ.

The existence of a suitable ais shown using the probabilistic method2: a

vector ais chosen at random according to the standard normal distribution

in a suitable linear subspace of Cn(Lemma 2.5). To obtain the bound (2),

one has to show that this bound is satisfied with positive probability.

Raz applied this strategy to the bilinear map of matrix multiplication,

and obtained an Ω(n2log n) lower bound. His estimate of ρand R, as well

as his lower bound for the multiplication with a random matrix is based on

his notion of geometric rigidity (see Equations (1.2) and (2.2)).

We apply a related approach to the problem of cyclic convolution. Let

ϕ:Cn×Cn→Cndenote the bilinear map of cyclic convolution. The matrix

of the linear map y7→ ϕ(a, y) resulting by specialising to a∈Cnis the

circulant matrix

Circ(a) = 





a0a1. . . an−1

an−1a0. . . an−2

... ... ... ...

a1a2. . . a0





.

An estimate for the complexity of the multiplication with a random cir-

culant matrix has to be found. An analysis reveals that, as in the case of

matrix multiplication, such a bound does not seem attainable using only

Morgenstern’s bound. This problem is treated instead by extending Mor-

genstern’s bound in a new way, which leads to the notion of the r-Mean

Square Volume (MSV) of a complex matrix A, suggested by B¨urgisser.

While the determinant det Ais the product λ1··· λnof the eigenvalues

of A, the r-mean square volume of A∈Cn×n(1 ≤r≤n) can be defined as

2See [AS00].

0.1 Lower Complexity Bounds 5

the square root of the r-th elementary symmetric function in the |λj|2:

msvrA=

X

1≤i1<···<ir≤n|λi1|2···|λir|2



1/2

The square of msvrAis, up to sign, the r-th coefficient of the characteristic

polynomial of AA∗, where A∗denotes the complex transpose of A. From

the definition given it is clear that the MSV is unitary invariant. Moreover,

msvrA≥ |λ1|···|λr| ≥ |λr|r, where |λ1| ≥ ··· ≥ |λn|is assumed. The case

r=nyields the absolute value of the determinant.

Based on a refinement of the proof of Morgenstern’s bound due to Raz,

the following MSV bound is obtained:

C(A)≥log msvrA−n/2.

An immediate corollary is the eigenvalue bound

C(A)≥rlog |λr|−n/2.(3)

This bound also follows from Chazelle’s Spectral Lemma [Cha00, Lemma 6.1]

and Raz’s rigidity bound [Raz03], see also Equations (2.2) and (1.2).

The advantage of the mean square volume in our situation can be out-

lined as follows (details may be found in the proof of Lemma 2.6). Assume

the vector a∈Cnis chosen at random, according to the standard normal

distribution in some fixed r-dimensional subspace of Cn. The eigenvalues

of Circ(a) are given by λ= DFTna. Since it is known that n−1/2DFTnis

unitary, the vector α=n−1/2λis also standard normal distributed in an r-

dimensional subspace U⊆Cn. Unfortunately, the mean of the determinant

det Circ(a) = nnQn

i=1 |αi|2turns out to be too small to obtain useful lower

bounds. The mean square volume, however, allows to select a “good” set of

eigenvalues:

msvr(Circ(a))2=nrX

|J|=rY

k∈J|αk|2≥nrY

k∈I|αk|2

for any I⊆[n], |I|=r. Given an n×rmatrix B= (b1,...,br) whose

columns are an orthonormal basis of Uand I⊆[n], with |I|=r, denote by

BIthe matrix consisting of the rows of Bindexed by I. Using the Covariance

Lemma 2.7, it is shown that for any index set I, with probability at least

1/2 the following holds:

k∈I|αk|2≥δr|det BI|2,

where δis some positive constant.

6Introduction

Figure 2: Volume contraction ratio

It is known (Binet-Cauchy formula) that the sum of the “volume con-

traction ratios” |det BI|2equals 1. Therefore, there exists an Isuch that

|det BI|2≥n

r−1. Combining this with the MSV bound, we arrive at

Lemma 2.6, which states that if ais standard normal distributed in an

r-dimensional subspace of Cn,

C(Circ(a)) ≥1

2rlog n−O(n) (4)

holds with probability at least 1/2. The factor rplays a role in the deter-

mination of the parameters Rand ρ, which bounds the increase in size of a

circuit for ϕafter substituting aand transforming it into a b.c. circuit. The

choice of r=n/2 leads to the lower bound on cyclic convolution

C(ϕ)≥1

12nlog n−O(nlog log n).

Ran Raz (personal communication) pointed out a technically simpler

proof for a variant of bound (4), which avoids the study of correlations.

His proof is based on the eigenvalue (or rigidity) bound, combined with a

lower bound for the sum of squares of the smallest reigenvalues of a random

circulant matrix. His proof is outlined in Section 2.3.

From the lower bound for the cyclic convolution, a nonlinear lower bound

for polynomial multiplication, inversion of power series, and polynomial di-

vision with remainder is obtained by noting that the well-known reductions

between these problems [BCS97] preserve the b.c. property. These lower

bounds are again optimal up to order of magnitude.

0.1.3 Help Gates

It is possible to extend the eigenvalue bound (3) to circuits allowing up to

(1 −)nhelp gates (0 <  ≤1), corresponding to scalar multiplications with

unbounded constants.

Assume a computation sequence g1,...,grfor computing the linear map

x7→ Ax is given, such that help gates are among the gi, and the dimension of

0.1 Lower Complexity Bounds 7

the space spanned by the linear forms computed at these help gates is h < n.

Removing these help gates leads to a sequence computing a map x7→ Bx for

a matrix Bthat coincides with Aon the orthogonal complement of the “help

space”, that is, the subspace spanned by the help gates. If |λ1| ≥ ··· ≥ |λn|

are absolute values of the eigenvalues of A,|e

λ1| ≥ ··· ≥ |e

λn|those of B,

then a classic result (see [GVL96, Theorem 8.1.7] or [CH31, I.§4.2]) states

that

|λr| ≥ |e

λr| ≥ |λr+h|(5)

for r+h≤n. Over R, and assuming Ato be symmetric, this can be

seen geometrically by interpreting the absolute values of the eigenvalues as

lengths of the principal axes of the ellipsoid {Ax | kxk= 1}. The eigenvalues

of Arestricted the complement of the help space are then the lengths of the

principal axes of the intersection of this ellipsoid with this complement.

“Help space” V

λ1

λ2e

λ1

λ1≥e

λ1≥λ2

Figure 3: Interlacing property and help gates

Let Ch(A) denote the length of the shortest bounded coefficient sequence

of instructions computing x7→ Ax with at most hhelp gates. The MSV

bound for B, the fact the number of instructions in the bounded coefficient

sequence for Bis at least hless than in the original sequence, and the

“interlacing property” (5), give rise to the following lower bound:

Ch(A)≥rlog |λr+h|−n/2 + h.

This bound is derived in detail in Chapter 3. In the case of the Discrete

Fourier Transform, this leads to an Ω(nlog n) lower bound in the presence

of (1 −)nhelp gates, 0 <  ≤1.

In Part I, the ideas presented so far are developed in the more general

context of m×nmatrices, where singular values take over the role that the

absolute values of the eigenvalues play for square matrices. It was shown

by B¨urgisser that the idea of allowing help gates carries over to the case of

bilinear maps (Sections 3.2 and 3.3), although some subtleties have to be

considered.

8Introduction

0.1.4 Related Work

A lower bound for the complexity of linear maps in terms of singular values

was already given by Chazelle [Cha98, Cha00]. His applications are nonlin-

ear lower bounds for range searching problems. His lower bound also works

in the presence of up to n/2 help gates, which are allowed to compute any

function on the intermediate results at unit cost. Thus his bound is weaker

than ours with respect to the number of help gates allowed, but stronger

with respect to the power of these help gates.

Several articles [NW95, Lok95, Pud98] studied b.c. arithmetic circuits.

The concept of matrix rigidity, originally introduced in [Val77], hereby plays

a vital role. A geometric variant of this concept (Euclidean metric instead

of Hamming metric) is closely related to the singular value decomposition

of a matrix and turns out to be an important tool, as worked out by Satya-

narayana Lokam [Lok95]. Ran Raz [Raz02, Raz03] proved a nonlinear lower

bound on the complexity of matrix multiplication in the b.c. model. This

article and [NW95] seem to be the only ones which deal with the complex-

ity of bilinear maps in the b.c. model of computation3. Recently, Maurice

Jansen and Kenneth Regan [JR04] proved lower bounds on the complexity

of linear and bilinear maps in a model of b.c. circuits that operate on orbits

of the input vector under the action of a matrix group.

0.2 Complexity Theory in Geometry and Topology

Computational complexity theory is the study of the resources needed to

solve problems algorithmically. The problems under consideration can be

decision or computation problems, while the resources studied are usually

space and time4. One of the central issues on the agenda of complexity

theory, according to [Pap94], is to understand why some problems are inher-

ently harder to solve than others. The standard approach chosen for this

purpose is to group problem in complexity classes and to identify certain

problems as hardest problems within each such class. It is this approach

that we apply to the study of the algorithmic problems of computing the

Euler characteristic and the Hilbert polynomial.

We begin by introducing these two objects and then proceed to discuss

the philosophy of counting complexity theory.

3The proof of the Ω(nlog n) lower bound in [NW95](Cor. 3) is incorrect, as it assumes

that the derivative inequality [BS83] carries over to the b.c. model. The counterexample

2nP1≤i≤nXiYi, pointed out by Pavel Pudl´ak (personal communication), shows that this

is not true.

4For precise definitions we refer to [Pap94]. Throughout this introduction, the reader

may think of time complexity vaguely as the number of computation steps needed.

0.2 Complexity Theory in Geometry and Topology 9

0.2.1 The Euler Characteristic

In its most simple incarnation, the Euler characteristic of a triangulated

polyhedron counts the number of vertices minus the number of edges plus

the number of faces5. In general, for spaces admitting a finite triangulation,

it is the alternating sum of the number of i-simplices of the triangulation.

The Euler characteristic of a topological space Vis denoted by χ(V).

χ(S2) = 12 −30 + 20 = 2 χ(T) = 1 −2 + 1 = 0

Figure 4: Euler characteristic of polyhedra and cell complexes

The Euler characteristic does not depend on any specific triangulation

of the object under consideration. In fact, it is a topological invariant, which

means that it doesn’t change under homeomorphism. Remarkably, the Euler

characteristic appears in several different ways. It is the alternating sum of

the Betti numbers bi(V) of a topological space V, that is, of the ranks of the

homology groups Hi(V;Z). For a finite cell complex, it is the alternating

sum of the number of cells in each dimension (see Figure 4). For compact,

differentiable manifolds, it can be characterised as the alternating sum over i

of the number of critical points of index iof any Morse function f:V→R,

or as the sum of the indices at the zeros of a vector field. Moreover, for

a Riemannian manifold the Gauss-Bonnet theorem gives a characterisation

of χ(V) in terms of Gaussian curvature. It is this diversity that makes the

Euler characteristic fascinating from a purely mathematical, and accessible

from a computational point of view.

A rich class of geometric objects are those defined as the zero sets of

systems of polynomial equations over the complex numbers C. These will

be referred to as (complex affine) varieties throughout this introduction.

Given a set of homogeneous multivariate polynomials over C, their common

zero set in complex projective n-space Pnis called a projective variety. An

affine or projective variety is equipped with the Euclidean topology via the

identification C∼

=R2. The computational problem we are interested in is

the following.

ProjEulerC(Euler characteristic of projective varieties). Given a finite

5See [Lak76] for a vivid account of the history of the Euler characteristic.

10 Introduction

set of complex homogeneous polynomials, compute the Euler charac-

teristic of its projective zero set.

The model of computation in which this question is discussed is the BSS

machine over C, named after Lenore Blum, Mike Shub, and Steve Smale

[BSS89, BCSS98]. Questions regarding the important issue on how the poly-

nomials are encoded as inputs to such a machine are discussed in Section

4.4. In contrast to the lower bounds described in Part I, the complexity

bounds for ProjEulerCare not absolute. Instead, following the tradition

of complexity theory, this problem is put in relation to another important

computational problem, which in a sense captures the complexity of a large

class of problems. This is the problem #HNCof counting the number of

solutions of a system of polynomial equations. Informally, our main result

about the Euler characteristic can be stated as follows:

The problem ProjEulerCis polynomial time equivalent to the

problem #HNCof counting the number of solutions of a system

of polynomial equations.

What this means is, roughly speaking, that any subroutine for one of

these problems can be used to solve the other problem with a number of

computation steps that is, up to the subroutine calls, polynomially bounded

in the input size.

The mathematical aspects of the reduction of ProjEulerCto #HNC

are briefly outlined next. The reduction exploits an intimate relation of the

Euler characteristic to the notion of degree of a complex projective variety.

The degree dof a variety V⊆Pncounts the number of intersection points of

Vwith a generic linear subspace of complementary dimension. For the zero

set of a single irreducible polynomial f(called a hypersurface), the degree

of this set is simply the degree of f.

Figure 5: Degree of elliptic curve y2=x3−x+ 1/2

For an irreducible, smooth hypersurface V⊆Pnof degree d, the rela-

0.2 Complexity Theory in Geometry and Topology 11

tionship of Euler characteristic and degree is explicitly given by:

χ(V) = 1

d((1 −d)n+1 −1) + n+ 1.(6)

As an example, an irreducible degree 3 curve in P2(elliptic curve) has Euler

characteristic 0. In fact, such a curve is topologically a torus.

Assume now that an irreducible polynomial fis given, and that the

resulting hypersurface Vis smooth. A straight-forward approach for com-

puting the Euler characteristic would be to intersect Vwith a random line

L⊆Pn, that is, add n−1 linear equations g1,...,gn−1, and count the num-

ber of solutions to the system f= 0, g1= 0,...,gn−1= 0. The resulting

number is with high probability the degree d, and Equation (6) thus yields

the Euler characteristic. In order to turn this procedure into a deterministic

polynomial time reduction, it has to be properly “derandomised”.

The approach taken is to use the notion of transversality: if Lmeets V

transversely, then the number of intersection point equals the degree. The

point is now that it is possible to compute in polynomial time a sequence

of lines L1,...,Lr, such that the majority of them meets Vtransversely.

This was shown in [BC04a]. The reason for this to be possible is that the

transversality condition can be expressed in a certain way as a first order

formula over the reals, and moreover this formula is generically satisfied.

It can be shown from this that a sequence of vectors called partial witness

sequence can be constructed, such that the majority of them satisfies the

first-order formula describing transversality. These ideas are discussed in

Section 5.2.

A generalisation of Equation (6) to possibly singular hypersurfaces was

found by Paolo Aluffi [Alu03] in terms of projective degrees. The sequence

of projective degrees d0,...,dn−1is derived from the graph of the gradient

map

Pn\Σ→Pn, x = (x0:···:xn)7→ ∂f

∂X0

(x): ···:∂f

∂Xn

(x),

where fis the polynomial defining the hypersurface and Σ is the common

zero set of the partial derivatives ∂f/∂Xj. Aluffi’s formula states that

χ(V) = n+

i=1

(−1)i−1dn−i.

The diare arrived at by counting the points of the intersection of the closure

of the graph Γ of the gradient map in Pn×Pnwith a product of generic

linear spaces. It is shown in Section 6.4 that such “generic” linear subspaces

can be computed in polynomial time from f, using transversality arguments

as in the case of the degree. The case of general varieties is reduced to

the case of a hypersurface using the inclusion-exclusion principle (Lemma

12 Introduction

4.5). Even though the resulting sum is exponential, it follows from an im-

portant principle in counting complexity, namely the closure of #PC(and

related classes) under exponential summation, that a single system of poly-

nomial equations can be constructed such that the Euler characteristic can

be deduced from the number of solutions of this system. The idea is best

illustrated using a trivial example. Let F(u, x) be a parametrised system of

polynomial equations. For fixed u∈ {0,1}m, let ϕ(u) denote the number

of solutions of the system of equations F(u, x) in x. Then the exponential

sum Pu∈{0,1}mϕ(u) equals the number of solutions of the single system of

polynomial equations F0(u, x) in (u, x), which arises from Fby adding the

equations u2

j=uj, 1 ≤j≤m.

0.2.2 The Hilbert Polynomial

Let V⊆Cnbe a complex projective variety of dimension m. The Hilbert

polynomial pV(T) associated to Vis a polynomial of degree mwith ratio-

nal coefficients, which encodes valuable geometric information about V: its

leading coefficient is the degree of V, and the constant coefficient gives the

arithmetic genus of V.

Our goal is to relate the complexity of computing the Hilbert polynomial

to the problem #HNCof counting points. This goal is achieved for the case

of smooth, equidimensional varieties. These are smooth varieties, in which

each irreducible component has the same dimension. The main result of

Chapter 7 can be roughly formulated as follows:

The problem of computing the Hilbert polynomial of a smooth,

equidimensional complex projective variety is at most as hard

as the problem #HNCof counting the number of solutions of a

system of polynomial equations.

The reduction uses concepts from enumerative geometry and Schubert

calculus, as well as the Hirzebruch-Riemann-Roch theorem, in order to ex-

press the coefficients of the Hilbert polynomial in terms of the degrees of

certain polar varieties. An example of a plane curve V⊆P2, given by an

irreducible polynomial f, should illustrate the case. The Hilbert polynomial

of Vis given by

pV(T) = dT + (1 −g),

where dis the degree of fand gthe genus of the curve. The leading coef-

ficient equals the number of intersection points of Vwith a generic line. Is

there a way of interpreting 1 −gin terms of the number of solutions to a

polynomial system? For smooth V, given a point y∈P2, define the polar

variety P(y) to be the set of points in Vwhose tangents at Vcontain y:

P(y) := {x∈V|y∈TxV},

0.2 Complexity Theory in Geometry and Topology 13

Figure 6: Polar variety

where TxVdenotes the tangent of Vat x.

If Vis smooth, then for generic y∈P2, the constant coefficient of the

Hilbert polynomial is given by

1−g=d−1

2|P(y)|.

This shows how the constant coefficient of the Hilbert polynomial can be

computed by means of “counting points”. In this simple example it is easy

to see, using B´ezout’s Theorem, that |P(y)|=d(d−1) holds for generic y.

This is consistent with the well known formula g=1

2(d−1)(d−2) for the

genus. More on algebraic curves can be found in [BK81] or [Ful89]

For a general smooth, purely m-dimensional variety V, the projective

tangent space TxVat xlives in the Grassmannian G(m, n) of m-planes

in Pn. Associated to a partition λ= (λ1,...,λm) and a flag of subspaces

F:F0⊆ ···Fn−1⊆Pn, there are the Schubert varieties Ωλ(F)⊆G(m, n).

The Gauss map ϕ:V→G(m, n) maps each x∈Vto its projective tangent

space TxV, and the pullback

Pλ(F) := ϕ−1(Ωλ(F))

is a generalised polar variety, called a degeneracy locus. The plane curve

example arises as special case with n= 2, m= 1, and λ= (1). It is known

that there is an integer dλ, such that for generic F,dλ= deg Pλ(F) holds.

These integers will be called projective characters.

Just as in the case of a smooth curve, there is a relationship between

the projective characters and the coefficients of the Hilbert polynomial of a

smooth, purely m-dimensional variety V⊆Pn. Let pk(V) denote the k-th

coefficient of the Hilbert polynomial of V. Then for 0 ≤k≤m:

pk(V) = 1

k!X

|µ|≤m−k

µ1≤n−m

δm,k

µdeg Pµ,

where the δm,k

µare combinatorial constants, easily describable in terms of

m, k, and the partition µ. This formula is derived in Chapter 8 using the

14 Introduction

Hirzebruch-Riemann-Roch theorem, which describes the coefficients of the

Hilbert polynomial in terms of determinants in the Chern classes of the

tangent bundle of V. These determinants, in turn, can be realised by the

homology classes of degeneracy loci using a classic result of Schubert calculus

(Kempf and Laksov [KL74], Fulton [Ful98]).

Again, the problem arises of how to compute a flag Fsuch that dλ=

deg Pλ(F). As for the degree, such a flag can be computed by exploit-

ing transversality. It is shown that whenever the Gauss map ϕmeets the

Schubert variety transversely (in a sense described in Section 7.2), then the

condition dλ= deg Pλ(F) is satisfied. It is then shown in Section 7.4 that

this transversality condition can be expressed as a logical formula in a way

that allows to actually compute such a flag Fin polynomial time, using

the methods of Chapter 5. The fact that the formula for pk(V) consists of

an exponential sum is treated by saying the magic formula “#PCis closed

under exponential summation”, see the previous section and Chapter 5.

0.2.3 Counting Complexity Theory

As already seen in the previous sections, the computation of the Euler char-

acteristic and the Hilbert polynomial is intimately related to a special kind

of computation problem, called counting problem. While a decision prob-

lem usually asks for the existence of a solution to a problem instance, the

corresponding counting problem asks for the number of solutions.

Counting problems abound in computer science and mathematics. A

classic example from optimisation theory, well suited to illustrate the ideas

of counting complexity theory, is the assignment problem: given a collection

of njobs and npersons, each of whom capable of performing one or more

of the jobs, find an assignment such that each person gets to do a different

job. Such an assignment is commonly referred to as a perfect matching6

(see Figure 7). The corresponding counting problem asks for the number of

possible perfect matchings.

The problem of telling whether an assignment exists at all is easy from a

computational complexity point of view. There are algorithms solving this

problem in time O(n3) and better, see for example [Pap94, Chapter 1] and

the references therein.

The number of perfect matchings is equal to the permanent of the adja-

cency matrix of the problem. The adjacency matrix is the n×n-matrix M,

whose (i, j)-th entry is 1 if person iis qualified for job j, and 0 else.

The permanent is then defined as

Per(M) = X

σ∈Sn

i=1

mi,σ(i),

6There are several variations to this theme. For example, each person may be differently

skilled at each of the jobs, and the problem may consist in finding an optimal assignment.

0.2 Complexity Theory in Geometry and Topology 15

Job Person

• •

1 1

2 2

3 3

4 4

M=





1 0 0 1

1 1 1 0

1 0 0 1

0 1 0 1







Per(M) = 2

Figure 7: There are 2 perfect matchings

where Snis the symmetric group of permutations on nletters, and mi,j

denotes the (i, j)-th entry of the matrix M. Multiplying each monomial in

the sum with the sign of the corresponding permutation gives rise to the

familiar definition of the determinant of the matrix. While the determinant

can be computed with O(n3) arithmetic operations using Gaussian elimina-

tion, the permanent has pertinaciously resisted all attempts at finding an

efficient algorithm. In fact, the best known methods for computing (deter-

ministically and exact) the permanent require O(2n) arithmetic operations

[Knu98, 4.6.4, Ex. 9-10]7.

In his seminal work [Val79a, Val79b], Leslie Valiant developed an ele-

gant theory that, in a way, explains why the determinant is easier than the

permanent. Roughly speaking, the class Pconsists of decision problems

solvable in polynomial time, while NP consists of decision problems, such

that each problem instance can be verified in polynomial time with the help

of a witness. For example, the problem of deciding whether a bipartite graph

has a perfect matching is in NP, since each graph with a perfect matching

has this matching as witness. Valiant introduced the counting class #P,

which consists of functions mapping problem instances in NP to the num-

ber of satisfying witnesses. He showed that the problem of computing the

permanent of a 0 −1 matrix is complete in this class. This implies that

the problem of computing the permanent is at least as hard as any other

problem in #P, and hence, a deterministic, polynomial time algorithm for

this problem would imply P=NP. It is generally believed that P6=NP

holds, even though there is no proof for this yet.

A counting complexity theory for algebraic and geometric problems over

the real and complex numbers, based on the BSS model of computation, was

initiated by Klaus Meer, Peter B¨urgisser and Felipe Cucker [Mee00, BC04a,

BC04b, BCL05]. The complexity class #P

Cplays the role of #Pover the

complex numbers, and the basic complete problem for this class is the prob-

7It should be noted, though, that there are randomised algorithms that approximate

a permanent with non-negative entries in polynomial time, as shown by Jerrum, Sinclair,

and Vigoda [JSV01]

16 Introduction

lem #HNCof counting the number of solutions of a system of polynomial

equations (the notation HNCstands for “Hilbert’s Nullstellensatz over C).

It is then investigated how other geometric problems relate to #HNCin

terms of computational complexity.

When an enumerative geometer asks for the solution of a counting prob-

lems, like “how many lines in P3intersect four given lines” [KL72], then it

is assumed that the answer is the same for almost all (generic) lines. This

assumption is based on what was called “Das Princip von der Erhaltung

der Anzahl” by Hermann Schubert in 1879 [Sch79]. The same principle is

implicit in the characterisation of the notion of degree as the number of

intersection points of a variety with a “generic” linear space of complemen-

tary dimension. In a sense, the problem of computing the degree is a more

natural representative for geometric counting problems than #HNC.

In terms of counting complexity theory, this state of affairs leads to the

notions of generic parsimonious reductions, coined by Peter B¨urgisser. In

a very simplified way, the definition states that a function ϕgenerically

reduces to a counting function ψin #P

C, if ϕ(x) = ψ(x, r) holds for all x

and “almost all” parameters r. In practice, one would like to be able to

actually compute such an r. Therefore, the definition involves a relation

R⊆C∞×C∞, such that

1. (x, r)∈R⇒ϕ(x) = ψ(x, r),

2. For all x,R(x, r) is satisfied for almost all r.

Moreover, the relation is required to be expressible in a certain way, namely

in the constant free polynomial hierarchy over the reals. It was shown in

[BC04a, BCL05] (based on earlier work by Koiran [Koi97a]) that for such

R, a satisfying parameter rcan be computed in polynomial time by means of

partial witness sequences. (A key step in the construction is closely related

to the concept of correct test sequences from Heintz and Schnorr [HS82],

and similar ideas also appear in the Witness Theorem [BCSS96, BCSS98].)

All this is explained in Chapter 5.

Going back to geometry, it is well-known that a statement of the form

Aholds for almost all (generic) B

can very often be rephrased as saying

Aholds whenever Bsatisfies a certain transversality property,

almost all (generic) Bsatisfy this transversality property.

This observation can be seen as a model for the definition of generic parsi-

monious reductions. In fact, it is this kind of situation that is encountered

in the study of the Euler characteristic and the Hilbert polynomial in Chap-

ters 6 and 7, where it is shown that suitable transversality conditions can

be expressed in a way that leads to generic parsimonious reductions.

0.2 Complexity Theory in Geometry and Topology 17

0.2.4 Related Work on Algorithms

There has been some recent work on the algorithmic problem of computing

the Euler characteristic for real and complex varieties. The first single-

exponential algorithm for computing the Euler characteristic of a semi-

algebraic set was given by Saugata Basu [Bas99], see also [BPR03, Chapter

13]. The complexity of computing the Euler characteristic was studied in

[BC04a], where using Morse theory, it was shown that this problem is poly-

nomial time equivalent to the problem of counting points in semi-algebraic

sets. Algorithms for computing the Euler characteristic of projective va-

rieties where described by Uli Walther [Wal00, Wal02] and Paolo Aluffi

[Alu03].

Several algorithms for computing the Hilbert function and Hilbert poly-

nomial are known. To our knowledge, the first algorithms for the Hilbert

function were described by M¨oller and Mora [MM83]. An important ap-

proach for computing Hilbert functions is based on a result of Macaulay

[Mac27], which states that the Hilbert function of an ideal equals the Hilbert

function of its initial ideal with respect to some monomial order, see also

[Eis95, 15.10.2]. Therefore, the problem of computing the Hilbert func-

tion can be reduced to the case of monomial ideals via Gr¨obner bases

[Buc65, Buc85], see also [CLO98, Eis95]. A polynomial space algorithm

for computing the Hilbert function of a monomial ideal was described by

Dave Bayer and Mike Stillman [BS92], see also [Eis95, Chapter 15] and

[GP02, Chapter 5]. Moreover, Bayer and Stillman show that the problem of

computing a Hilbert function is NP-hard. Other algorithms were described

by Bigatti, Caboara, and Robbiano [BCR91, Big97] of the CoCoA Research

Team. Some of these algorithms have been implemented in computer al-

gebra systems, such as Macaulay2 [GS], Singular [GPS01], and CoCoA

[CoC].

The algorithms considered so far all rely on the computation of Gr¨obner

bases, which leads to bad worst-case complexity estimates. In fact, the

problem of computing a Gr¨obner basis is exponential space hard [May97].

Both the cardinality and the maximal degree of a Gr¨obner basis can be

double exponential in the number of variables [MM82, Huy86, BS88]. It

is generally believed that these bounds are quite pessimistic, and that for

problems with “nice” geometry, single exponential upper bounds should

hold for Gr¨obner bases. Among the results that are known in this direction

are [Giu84, DFGS91, BM93, May97]. However, currently no upper bound

better than exponential space is known for the computation of the Hilbert

function or Hilbert polynomial of a homogeneous ideal. It is interesting to

note that, while the Hilbert function is computed with the help of Gr¨obner

bases, knowledge of the Hilbert function of an ideal can help speed up the

Buchberger algorithm [Tra96] (see also [GP02, Remark 5.2.9]).

The problem #HNCof counting the number of solutions of a system

18 Introduction

of polynomial equations has received some attention in the past. There

are algorithms solving #HNCin single exponential time (or even parallel

polynomial time). A key point for showing this is the fact that a Gr¨obner

basis of a zero-dimensional ideal can be computed in single exponential time

[DFGS91, Lak91, LL91]. The number of solutions can then be determined

using linear algebra techniques, as described for example in [CCS99, Chap-

ter 2]. Another approach for counting the number of solutions is by using

Bernstein’s theorem, which interprets the number of solutions in (Cn)∗as

mixed volume of the Newton polytope of the system of equations. However,

this method assumes some regularity condition on the system of equations.

For this and other approaches for solving #HNC(such as resultants), a

reference is [CLO98] (see also [Stu02]).

0.3 Outline

Chapter 1 contains a description of the model of computation, as well as ba-

sic definitions and results from linear algebra and probability theory. Chap-

ter 2 contains the heart of Part I. Here, the mean square volume bound is

introduced, and a lower bound for the bilinear problem of cyclic convolu-

tion is obtained. This bound is then used to obtain lower bounds for the

problems of polynomial multiplication and division, and inversion of power

series. Chapter 3 extends the lower bounds to a model of computation in

which a limited number of help gates are allowed. This extension is carried

out for linear and bilinear maps.

Chapter 4 recalls basic concepts from geometry, topology, and gives a

short introduction to BSS complexity theory. In Chapter 5, a counting

complexity theory in the BSS model of computation is explored. This chap-

ter introduces the important notion of generic parsimonious reduction and

the complexity classes related to this notion. The framework developed in

Chapter 5 is used in Chapters 6 and 7, in order to study the complexity of

the Euler characteristic and the Hilbert polynomial, respectively. Finally,

Chapter 8 contains the derivation of a formula for the coefficients of the

Hilbert polynomial in terms of the degrees of polar classes.

0.4 Credits

Most of the content of this thesis has been published as joint work with

Peter B¨urgisser and Felipe Cucker in [BL02, BL04, BCL04, BCL05, BL05].

The contribution of my co-authors, and that of the other persons mentioned

below, is gratefully acknowledged.

0.4 Credits 19

Part I

The concept of the mean square volume as unitary invariant measure was

proposed by Peter B¨urgisser. The idea of studying help gates was inspired

by the work of Bernard Chazelle [Cha98, Cha00] (even though our approach

differs significantly), and the extension of help gates to the bilinear case

(Section 3.3) was suggested by Satyanarayana Lokam and carried out by

B¨urgisser. The study of correlated standard normal vectors, specifically in

Lemma 2.7 and in Section 3.2, has benefited from the expert advise of Mario

Wschebor. The alternative proof of the lower bound on the complexity of

random circulants in Section 2.3 has been worked out around an approach

suggested by Ran Raz. Much of the content of Part I profits from Raz’s

article [Raz03], which was pointed out to us by Joachim von zur Gathen.

Part II

The study of counting complexity theory described in Chapter 5 was first

started by B¨urgisser and Cucker in [BC04a, BC04b], based on earlier ideas

of Pascal Koiran [Koi97b, Koi99a], and further developed in [BCL05].

The main part of Chapter 6 is concerned with the application of Aluffi’s

formula (6.8) in order to obtain upper bounds on the complexity of the Euler

characteristic. Aluffi’s article [Alu03] was pointed out to us by Joachim von

zur Gathen.

In Chapter 7, the idea of how to use the testable input condition (Equa-

tion (7.1)) instead of just assuming the input varieties to be smooth and

equidimensional, was proposed by B¨urgisser. The #P-hardness of the Hilbert

polynomial of smooth varieties (Proposition 7.17) follows along the lines of

the #P-hardness proof of Eric Bach for sheaf cohomology [Bac99], while

the PSPACE lower bound for the Hilbert polynomials was pointed out by

B¨urgisser.

20 Introduction

Part I

Lower Bounds on the Complexity

of Bilinear Maps

Chapter 1

Preliminaries I

1.1 The Model of Computation

The underlying model of computation throughout Part I is the model of

algebraic straight-line programs over C, which are often called arithmetic

circuits in the literature. Straight-line programs differ from the notion of

circuit as introduced in Part II, in that no sign gates are allowed. For

details on this model of computation, the reader may consult Chapter 4 of

[BCS97]. By a result of Volker Strassen [Str73b], it is possible to exclude

divisions without loss of generality.

Definition 1.1 Astraight-line program Γ expecting inputs of length nis

a sequence (Γ1,...,Γr) of instructions Γs= (ωs;is, js), ωs∈ {×,+,−} or

Γs= (ωs;is), ωs∈C, with integers is, jssatisfying −n < is, js< s. A

sequence of polynomials b−n+1,...,bris called the result sequence of Γ on

input variables a1,...,an, if for −n < s ≤0, bs=an+s, and for 1 ≤s≤r,

bs=bisωsbjsif Γs= (ωs;is, js) and bs=ωsbisif Γs= (ωs;is). Γ is said to

compute a set of polynomials Fon input a1,...,an, if the elements in Fare

among those of the result sequence of Γ on that input. The size S(Γ) of Γ

is the number rof its instructions.

A straight-line program can be interpreted as directed graph with nodes

(gates) corresponding to inputs, outputs, arithmetic operations, and scalar

multiplications. In the sequel, such straight-line programs are briefly re-

ferred to as circuits. A circuit in which the scalar multiplication is restricted

to scalars of absolute value at most 2 is called a bounded coefficient circuit

(b.c. circuit for short). Any circuit can be transformed into a b.c. circuit by

replacing a multiplication with a scalar λwith at most log |λ|1. additions

and a multiplication with a scalar of absolute value at most 2. By the same

argument it follows that the bound of 2 could be replaced by any other fixed

bound.

Next, restricted notions of circuits are introduced, which are designed

for computing linear and bilinear maps.

1Unless otherwise stated, log always refers to logarithms to the base 2.

24 Preliminaries I

Definition 1.2 A circuit Γ = (Γ1,...,Γr) expecting inputs X1,...,Xnis

called a linear circuit, if ωs∈ {+,−} for every instruction Γs= (ωs;is, js),

or ωs∈Cif the instruction is of the form (ωs;is). A circuit on inputs

X1,...,Xm, Y1,...,Ynis called a bilinear circuit, if its sequence of instruc-

tions can be partitioned as Γ = (Γ(1),Γ(2),Γ(3),Γ(4)), where Γ(1) is a linear

circuit with the Xias inputs, Γ(2) is a linear circuit with the Yjas inputs,

each instruction from Γ(3) has the form (×;i, j), with Γi∈Γ(1) and Γj∈Γ(2),

and Γ(4) is a linear circuit with the previously computed results of Γ(3) as

inputs. In other words, Γ(1) and Γ(2) compute linear functions f1,...,fkin

the Xiand g1,...,g`in the Yj. Γ(3) then multiplies the fiwith the gjand

Γ(4) computes linear combinations of the products figj.

It is clear that linear circuits compute linear maps and that bilinear

circuits compute bilinear maps. On the other hand, it can be shown that any

linear (bilinear) map can be computed by a linear (bilinear) circuit such that

the size increases at most by a constant factor (see [BCS97, Theorem 13.1,

Proposition 14.1]). This remains true when considering bounded coefficient

circuits. From now on, only bounded coefficient circuits are considered.

Definition 1.3 The b.c. complexity C(ϕ) of a bilinear map ϕ:Cm×Cn→Cp

is the size of a smallest b.c. bilinear circuit computing ϕ. The b.c. complex-

ity C(ϕA) of a linear map ϕA:Cn→Cm(or of the corresponding matrix

A∈Cm×n), is the size of a smallest b.c. linear circuit computing ϕA.

By abuse of notation, C(F) also stands for the smallest size of a b.c.

circuit computing a set Fof polynomials from the variables.

Let ϕ:Cm×Cn→Cpbe a bilinear map described by ϕ`(X, Y ) =

Pi,j aij`XiYjfor 1 ≤`≤p. Assuming |aij`| ≤ 2, it is clear that C(ϕ)≤

3mnp.

The complexity of a bilinear map ϕcan be related to the complexity of

the associated linear map ϕ(a, −), where a∈Cm. The following lemma is

from [Raz03].

Lemma 1.4 Let ϕ:Cm×Cn→Cpbe a bilinear map and Γbe a b.c.

bilinear circuit computing ϕ. If f1,...,fkare the linear maps computed by

the circuit on the first set of inputs, then for all a∈Cm:

C(ϕ(a, −)) ≤ S(Γ) + plog (max

j|fj(a)|).

Proof. Let a∈Cmbe chosen and set γ= maxj|fj(a)|. Transform the

circuit Γ into a linear circuit Γ0by the following steps:

1. replace the first argument xof the input by a,

2. replace each multiplication by fi(a) with a multiplication by 2γ−1fi(a),

1.2 Singular Values and Matrix Rigidity 25

3. multiply each output by γ/2, simulating this with at most log (γ/2)

additions and one multiplication with a scalar of absolute value at

most 2.

This is a b.c. linear circuit computing the map ϕ(a, −): Cn→Cp. Since

there are poutputs, the size increases by at most plog γ.2

1.2 Singular Values and Matrix Rigidity

The Singular Value Decomposition (SVD) is an important matrix decompo-

sitions in numerical analysis. Lately, it has also come to play a prominent

role in proving lower bounds for linear circuits [Lok95, Cha98, Raz03]. In

this section, some basic facts about singular values are presented, and it is

shown how they relate to notions of matrix rigidity. For a more detailed

account on the SVD, the reader may consult [GVL96]. The classic [CH31,

Chapt. 1, Sect. 4] also turns out to be a useful reference.

The singular values of A∈Cm×n,σ1≥... ≥σmin{m,n}, can be defined

as the square roots of the eigenvalues of the Hermitian m×m-matrix AA∗,

where A∗denotes the complex transpose of A. Alternatively, the singular

values can be characterised as follows:

σr+1 = min{kA−Bk2|B∈Cm×n,rk(B)≤r},

where k·k2denotes the matrix 2-norm, that is, kAk2:= maxkxk2=1 kAxk2.

A geometric version of the above characterisation is the Courant-Fischer

min-max theorem stating

σr+1 = min

codimV=rmax

x∈V−{0}kAxk2

kxk2

where the minimum is taken over all linear subspace V⊆Cnof codimension

rin Cn. This description implies the following useful fact from matrix

perturbation theory:

σr+h(A)≤σr(A+E) (1.1)

if the matrix Ehas rank at most h.

More generally, for a metric d on Cm×n(or Rm×n) and 1 ≤r≤min {m, n},

the r-rigidity of a matrix Acan be defined to be the distance of Ato the

set of all matrices of rank at most rwith respect to this metric:

rigd,r(A) = min{d(A, B)|B∈Cm×n,rk(B)≤r}.

Using the Hamming metric, we obtain the usual matrix rigidity as intro-

duced in [Val77]. On the other hand, using the metric induced by the 1,2-

norm kAk1,2:= maxkxk1=1 kAxk2, we obtain the following geometric notion

of rigidity, as introduced in [Raz03]:

rigr(A) = min

dim V=rmax

1≤i≤ndist(ai, V ).

26 Preliminaries I

Here, the aiare the column vectors of A∈Cm×nand dist denotes the usual

Euclidean distance, that is, dist(ai, V ) := minb∈Vkai−bk2. Note that in

Equation (1.2), the minimum is taken over subspaces of dimension r.

Example 1.5 Let A∈R3×3. Then rig0(A) is the radius of the smallest

ball centred at the origin enclosing the column vectors of A, rig1(A) the

radius of the smallest cylinder through the origin containing these vectors,

and rig2(A) has a similar interpretation in terms of plates.

Notions of rigidity can be related to one another the same way the un-

derlying norms can. In particular, the following relationship between the

geometric rigidity and the singular values holds:

√nσr+1(A)≤rigr(A)≤σr+1(A).(1.2)

The proofs of these inequalities are based on well known inequalities for

matrix norms. To be precise, note that if Bis a matrix of rank at most r

with columns bi, then

kA−Bk2

1,2= max

ikai−bik2

2≥1

i=1 kai−bik2

2≥1

nkA−Bk2

2≥1

nσ2

r+1,

which shows the left inequality. The other inequality follows from the fact

that kAk1,2≤ kAk2, which is a consequence of kxk2≤ kxk1for x∈Cn.

1.3 Complex Gaussian Vectors

A random vector X= (X1,...,Xn) in Rnis called standard Gaussian if

its components Xiare i.i.d. standard normal distributed. An orthogonal

transformation of such a random vector is again standard Gaussian.

We will mainly consider random vectors Zassuming values in Cn. By

identifying Cnwith R2n,Zcan be thought of as a 2n-dimensional real

random vector. In particular, it makes sense to say that such Zis (standard)

Gaussian in Cn.

Let Ube an r-dimensional linear subspace of Cn. A random vector

Zwith values in Uis standard Gaussian in Uif for some orthonormal

basis b1,...,brof Uthis vector can be written as Z=Pjζjbj, where the

random vector (ζj) of the components is standard Gaussian in Cr. This

description does not depend on the choice of the orthonormal basis. In fact,

the transformation of a standard Gaussian vector with a unitary matrix is

again standard Gaussian, since a unitary transformation Cr→Crinduces

an orthogonal transformation R2r→R2r.

The following lemma is a direct consequence of known facts about the

normal distribution. For completeness, a proof is outlined.

1.4 Bounding Large Deviations 27

Lemma 1.6 Let (Z1,...,Zn)be standard Gaussian in Cn. Consider a com-

plex linear combination S=f1Z1+...+fnZnwith f= (f1,...,fn)∈Cn.

Then the real and imaginary parts of Sare independent and normal dis-

tributed, each with mean 0and variance kfk2

2. Moreover, T:= |S|2/2kfk2

is exponentially distributed with parameter 1. That is, the density function

is e−tfor t≥0and the mean and the variance of Tare both equal to 1.

Proof. If X1,...,Xnare standard Gaussian in Rand a= (a1,...,an)∈Rn,

then Pn

j=1 ajXjis again Gaussian, with mean 0 and variance kak2

2. Note

also that if Z=X+iY with independent standard Gaussian X,Yin R,

and f∈C, then the real and imaginary parts of fZ are again independent,

with mean 0 and variance |f|2. This follows from the fact that complex

multiplication corresponds to a rotation and scaling. These observations

imply the first statement of the lemma. In particular, kfk−1

2S=X+iY

with independent standard Gaussian X, Y in R. It is well known that in this

case, 1

2(X2+Y2) is exponentially distributed with parameter 1, see [Fel71,

II.2-3] for details 2

1.4 Bounding Large Deviations

The theory of large deviations is concerned with the rate of convergence

of the strong law of large numbers. For a proof of the following theorem,

references are [DZ98] or [Bau02, Section 12].

Theorem 1.7 (Cram´er, Chernoff) Let Sn=X1+···+Xnbe the sum

of i.i.d. random variables, each with mean η. Then for any ≥0

P [Sn≥(η+)n]≤e−I(η+)n

where

I(λ) := sup

t∈R{tλ −ln E[etX1]}

is called the rate function (or Cram´er transform) of the distribution of X1.

This theorem will be needed in the case of exponentially distributed

variables. For Xexponentially distributed with parameter 1 and t < 1,

E[etX ] = Z∞

etxe−xdx =1

1−t.

In this case, the rate function takes the form

I(λ) = sup

t<1{λt + ln (1 −t)},

and a simple calculation shows that for λ > 0 the supremum takes the value

(λ−1) −ln λ.

28 Preliminaries I

If Zis standard normal distributed in Cn, then kZk2/2 is the sum of

nindependent exponentially distributed variables (cf. Section 1.3) and it

follows that

PkZk2/2≥(1 + )n≤((1 + )e−)n(1.3)

for ≥0.

A useful consequence, which is used only in Section 2.3, is the estimate

PkZk2≤n≤√e/2n.(1.4)

To see this, let kZk2/2 = Pn

i=1 Xi, with exponentially distributed Xi,

and set Yi= 1−Xi,Tn=Pn

i=1 Yi. Then P kZk2/2≤n/2= P [Tn≥n/2].

A straight-forward calculation shows that the rate function of Y1at λ= 1/2

is given by I(1/2) = ln(2) −1/2, and the claim follows from Theorem 1.7.

1.5 Two Useful Inequalities

The inequalities presented in this section are only needed in the proof of

Lemma 2.7. Let X, Y be i.i.d. standard normal random variables and set

γ:= 1−E[log X2] and θ:= E[log2(X2+Y2)]. Evaluating the corresponding

integrals yields2

γ= 1 −1

√2πZ∞

t−1/2e−t/2log t dt ≈2.83

θ=1

2Z∞

e−t/2log2t dt ≈3.45.

Lemma 1.8 Let Zbe a centred Gaussian variable with complex values.

Then

0≤log E[|Z|2]−E[log |Z|2]≤γ, Var(log |Z|2)≤θ.

Proof. By a principal axis transformation, it can be assumed that Z=

λ1X+iλ2Ywith independent standard normal X, Y and λ1, λ2≥0. The

difference ∆ := log E[|Z|2]−E[log |Z|2] is nonnegative, since log is concave

(Jensen’s inequality). By linearity of the mean, ∆ as well as Var(log |Z|2) are

invariant under multiplication of Zwith scalars. We may therefore w.l.o.g.

assume that 1 = λ1≥λ2. From this it follows that

log E[|Z|2] = log E[X2+λ2

2Y2]≤log E[X2+Y2] = 1

E[log |Z|2] = E[log (X2+λ2

2Y2)] ≥E[log X2] = 1 −γ,

which implies the first claim. The estimates

Var(log |Z|2)≤E[log2|Z|2]≤E[log2(X2+Y2)] = θ

prove the second claim. 2

2The sum of nsquares of standard normal random variables is χ2-distributed with n

degrees of freedom, cf. [Fel71, II.2-3] for background and the corresponding densities.

Chapter 2

Lower Bounds for Linear and

Bilinear Maps

Morgenstern’s bound [Mor73] states that C(A)≥log |det (A)|for a square

matrix A, see also [BCS97, Chapter 13] for details. In this chapter, several

generalisations of this bound are presented.

2.1 The Mean Square Volume Bound

Let A∈Cm×nbe a matrix. For an r-subset I⊆[m] := {1,...,m}let AI

denote the sub-matrix of Aconsisting of the rows indexed by I. Over R,

the Gramian determinant det AIA∗

Ican be interpreted as the square of the

volume of the parallelepiped spanned by the rows of AI.

Raz [Raz03] defined the r-volume of Aby

volr(A) := max

|I|=r(det AIA∗

I)1/2

and observed that the proof of Morgenstern’s bound extends to the following

r-volume bound:

C(A)≥log volr(A).(2.1)

Moreover, Raz related this quantity to the geometric rigidity as follows:

volr(A)≥(rigr(A))r,

which implies the rigidity bound,

C(A)≥rlog rigr(A).(2.2)

It will be convenient to work with a variant of the r-volume that is

completely invariant under unitary transformations. Instead of taking the

maximum of the volumes (det AIA∗

I)1/2, the sum of the squares is used. The

r-mean square volume msvr(A) of A∈Cm×nis defined by

msvr(A) := X

|I|=r

det AIA∗

I1/2

=X

|I|=|J|=r|det AI,J|21/2

30 Lower Bounds for Linear and Bilinear Maps

Hereby, AI,J denotes the r×rsub-matrix consisting of the rows indexed

by Iand columns indexed by J. The second equality is a consequence of

the Binet-Cauchy formula det AIA∗

I=P|J|=r|det AI,J|2, see [Bel97, Chap-

ter 4]. The choice of the L2-norm instead of the maximum norm results in

the following inequality

volr(A)≤msvr(A)≤sm

rvolr(A).(2.3)

The mean square volume has some nice properties.

Lemma 2.1 Let A∈Cm×n. Then

msvr(A) = msvr(A∗),msvr(λA) = |λ|rmsvr(A),msvr(A) = msvr(UAV ),

where λ∈Cand Uand Vare unitary matrices of the correct format.

Proof. The first two properties are straightforward to verify. As for unitary

invariance, let A= (a1,...,am)>, where aidenotes the i-th column of A,

1≤i≤m. Then for I⊆[m] with |I|=rwe have AIA∗

I= (haj, aki)j,k∈I,

where h·,·i denotes the complex scalar product. From the unitary invariance

of this scalar product, we get msvr(AV ) = msvr(A) for a unitary matrix V

of the correct format. Unitary invariance on the right follows now from the

invariance under complex conjugation. 2

Remark 2.2 The r-volume can be seen as the 1,2-norm of the map ΛrA

induced by Abetween the exterior algebras ΛrCnand ΛrCm.1Similarly,

the mean square volume can be interpreted as the Frobenius norm of ΛrA.

The unitary invariance of the mean square volume also follows from the fact

that Λris equivariant with respect to unitary transformations and that the

Frobenius norm is invariant under such.

Note also that msvn(A) = |det A|for A∈Cn×n. The unitary invariance

allows to express the mean square volume of Ain terms of the singular

values σ1≥...≥σpof A,p:= min {m, n}, as follows.

It is well known [GVL96] that there are unitary matrices U∈Cm×mand

V∈Cn×nsuch that U∗AV = diag(σ1,...,σp).2Hence

msv2

r(A) = msv2

r(diag(σ1,...,σp)) = X

|I|=rY

i∈I

σ2

i≥σ2

1σ2

2···σ2

r,(2.4)

where Iruns over all r-subsets of [p]. It follows that the square of the r-mean

square volume of a matrix is the r-th elementary symmetric polynomial in

the squares of its singular values.

1See e.g.., [Bou70] for background on multilinear algebra.

2In fact, this is how the SVD is defined in [GVL96].

2.2 A Lower Bound on Cyclic Convolution 31

Combining the r-volume bound (2.1) with (2.3) we obtain the following

mean square volume bound.

Proposition 2.3 For A∈Cm×nand r∈Nwith 1≤r≤min{m, n}

C(A)≥log msvr(A)−m

2.(2.5)

2.2 A Lower Bound on Cyclic Convolution

In this section, the mean square volume bound (2.5) is used in order to prove

a lower bound on the bilinear map of the cyclic convolution.

Let f=Pn−1

i=0 aiXiand g=Pn−1

i=0 biXibe polynomials in C[X]. The

cyclic convolution of fand gis the polynomial h=Pn−1

i=0 ciXi, which is

given by the product of fand gin the quotient ring C[X]/(Xn−1). Ex-

plicitly:

ck=X

i+j≡kmod n

aibj,0≤k < n.

Cyclic convolution is a bilinear map on the coefficients. For a fixed polyno-

mial with coefficient vector a= (a0,...,an−1), this map turns into a linear

transformation with the circulant matrix

Circ(a) = 





a0a1. . . an−1

an−1a0. . . an−2

... ... ... ...

a1a2. . . a0





.

Let DFTn= (ωjk)0≤j,k<n be the matrix of the Discrete Fourier Trans-

form, with ω=e2πi/n. It is well known [GVL96, Sect. 4.7.7] that

Circ(a) = 1

√nDFTn−1diag(λ0,...,λn−1)1

√nDFTn,

where the eigenvalues λkof Circ(a) are given by

(λ0,...,λn−1)>= DFTn(a0,...,an−1)>.(2.6)

Hence the singular values of Circ(a) are |λ0|,...,|λn−1|(in some order).

Note that n−1/2DFTnis unitary.

The Fast Fourier Transform provides a b.c. bilinear circuit of size O(nlog n)

that computes the n-dimensional cyclic convolution, see [GG03, 8.2]. The

main result of this chapter is the asymptotic optimality of this algorithm in

the b.c. model.

Theorem 2.4 The bounded coefficient complexity of the n-dimensional

cyclic convolution convnsatisfies C(convn)≥1

12 nlog n−O(nlog log n).

In fact, the proof of the theorem shows that the constant factor 1/12 can

be replaced by the slightly larger value 0.086. The theorem is stated with

1/12 for simplicity of exposition.

32 Lower Bounds for Linear and Bilinear Maps

2.2.1 Bounding the Absolute Values of Linear Forms

To prepare for the proof, some lemmas are needed. The idea behind the

following lemma is already present in [Raz03]. Linear forms on Cnare

identified with vectors in Cn.

Lemma 2.5 Let f1,...,fk∈Cnbe linear forms and let 1≤r < n. Then

there exists a complex subspace U⊆Cnof dimension rsuch that for a

standard normal distributed complex random vector awith values in U, we

have

Pmax

i|fi(a)| ≤ 2pln (4k) rign−r(f1,...,fk)≥1

Proof. Set R= rign−r(f1,...,fk). Then there exists a linear subspace

V⊆Cnof dimension n−rsuch that dist(fi, V )≤Rfor all 1 ≤i≤k. Let

ibe the projection of fialong Vonto the orthogonal complement U:= V⊥

of V. By the choice of the subspace Vwe have kf0

ik ≤ R.

f’

ifi

Let (b1,...,bn) be standard normal distributed in Cnand abe the or-

thogonal projection of bonto Ualong V. Then ais standard normal dis-

tributed with values in U. Moreover, we have f0

i(b) = fi(a). By Lemma 1.6,

the random variable T=|f0

i(b)|2/(2kf0

ik2) is exponentially distributed with

parameter 1. For any λ > 1, and using Equation (1.3) with n= 1, we get

P [T≥λ] = P |f0

i(b)|2≥2λkf0

ik2≤λe−(λ−1).

By the union bound, and using the fact that kf0

ik ≤ R, we obtain

Pmax

i|fi(a)| ≥ √2λ R≤kλe−(λ−1).

Setting λ= 2 ln (4k) completes the proof. 2

2.2.2 Proof of the Main Result

In the next lemma, a lower bound on the b.c. linear complexity of a circulant

Circ(a) with standard Gaussian parameter vector ain a subspace of Cnis

stated.

2.2 A Lower Bound on Cyclic Convolution 33

Lemma 2.6 Let U⊆Cnbe a subspace of dimension r. For a standard

Gaussian vector ain U,

PC(Circ(a)) ≥1

2rlog n−cn>1

where c=1

2(2 + γ+√2θ)≈3.73, and γ, θ are the constants introduced in

Section 1.5.

We postpone the proof of this lemma and proceed with the proof of the

main theorem.

Proof. (of Theorem 2.4) Let Γ be a b.c. bilinear circuit for convn, which

computes the linear forms f1,...,fkon the first set of inputs. Fix 1 ≤r < n,

to be specified later, and set R= rign−r(f1,...,fk). By Lemma 2.5 and

Lemma 2.6 there exists an a∈Cn, such that the following conditions hold:

1. max1≤i≤k|fi(a)| ≤ 2pln (4k)R,

2. C(Circ(a)) ≥1

2rlog n−cn.

By Lemma 1.4 and the fact that k≤3n3(see Section 1.1), we get

S(Γ) + nlog (2pln (12n3)R)≥ C(Circ(a)).(2.7)

On the other hand, the rigidity bound (2.2) implies the following upper

bound on Rin terms of S(Γ):

S(Γ) ≥ C(f1,...,fk)≥(n−r) log R.

By combining this with (2.7) and using the second condition above, we

obtain 1 + n

n−rS(Γ) ≥r

2log n−O(nlog log n).

Setting =r/n yields

S(Γ) ≥(1 −)

2(2 −)nlog n−O(nlog log n).

A simple calculation shows that the coefficient of the nlog nterm attains the

maximum 0.086 for ≈0.58. Choosing = 1/2 for simplicity of exposition

finishes the proof. 2

Before going into the proof of Lemma 2.6, a lemma on bounding the

deviations of products of correlated normal random variables is stated.

Lemma 2.7 Let Z= (Z1,...,Zr)be a centred Gaussian vector in Cr.

Define the complex covariance matrix of Zby Σr:= (E(ZjZk))j,k and put

δ:= 2−(γ+√2θ)≈0.02. Then E(|Z1|2···|Zr|2)≥det Σrand

P|Z1|2···|Zr|2≥δrdet Σr>1

34 Lower Bounds for Linear and Bilinear Maps

Proof. For proving the bound on the expectation decompose Zr=ξ+ηinto

a component ξin the span of Z1,...,Zr−1plus a component ηorthogonal

to this span in the Hilbert space of quadratic integrable random variables

with respect to the inner product defined by the joint probability density of

Z. Therefore, |Zr|2=|ξ|2+ξη +ξη +|η|2, hence by independence

E(|Z1|2···|Zr−1|2|Zr|2) = E(|Z1|2···|Zr−1|2|ξ|2) + E(|Z1|2· · · |Zr−1|2) E(|η|2)

≥E(|Z1|2···|Zr−1|2) E(|η|2).

Let ξ=Pi<r λiZi. Then the complex covariance matrix Σ0

rof the vector

(Z1,...,Zr−1, η) arises from Σrby subtracting the λi-th multiple of the i-th

column from the r-th column, and by subtracting the λj-th multiple of the

j-th row from the r-th row, for all i, j < r. Therefore, using E(Ziη) = 0, we

obtain

det Σr= det Σ0

r= E(|η|2) det Σr−1.

The desired bound on the expectation E(|Z1|2···|Zr|2)≥det Σrthus follows

by induction on r. Noting that E(|Zr|2)≥E(|η|2), we also conclude from

the above equation that

E(|Z1|2)···E(|Zr|2)≥det Σr.(2.8)

In order to prove the probability estimate for the product |Z1|2···|Zr|2,

we first transform the product into a sum by taking logarithms. For every

 > 0 Chebychev’s inequality yields the bound

Ph1

r

j=1

(log |Zj|2−E[log |Zj|2])≥i≤Var(Pr

j=1 log |Zj|2)

2r2.(2.9)

For the variance we have by Lemma 1.8

Var(

j=1

log |Zj|2) = X

j,k

Cov(log |Zj|2,log |Zk|2)

≤X

j,k qVar(log |Zj|2)Var(log |Zk|2)≤r2θ.

Setting 2= 2θin this equation and after exponentiating in (2.9) we obtain

Ph|Z1|2···|Zr|2≤2−r+Pr

j=1 E[log |Zj|2]i≤1

2.(2.10)

By combining the bound (2.8) with Lemma 1.8 we get

log det Σr≤

i=1

log E[|Zi|2]≤γr +

i=1

E[log |Zi|2].

Hence we conclude from (2.10) that

Ph|Z1|2···|Zr|2≤2−(+γ)rdet Σri≤1

from which the lemma follows. 2

2.2 A Lower Bound on Cyclic Convolution 35

Proof. (of Lemma 2.6) By Equation (2.6) we have λ= DFTnaand the

singular values of the circulant Circ(a) are given by the absolute values of

the components of λ. Setting

α=n−1/2λ=n−1/2DFTna,

we obtain for the r-mean square volume by (2.4)

msv2

r(Circ(a)) = nrX

|I|=rY

i∈I|αi|2.(2.11)

Now let abe a standard Gaussian vector in the subspace Uof di-

mension r. Let Wbe the image of Uunder the unitary transformation

n−1/2DFTn. As a unitary transformation of a,αis standard Gaussian in

the subspace W(cf. Section 1.3). This means that there is an orthonormal

basis b1,...,brof Wsuch that

α=β1b1+···+βrbr,

where (βi) is standard Gaussian in Cr. Let B∈Cn×rdenote the matrix

with the columns b1,...,brand let BIbe the sub-matrix of Bconsisting

of the rows indexed by I, for I⊆[n] with |I|=r. Setting αI= (αi)i∈I

we have αI=BIβ. The complex covariance matrix of αIis given by Σ :=

E[αIα∗

I] = BIB∗

I, hence

det Σ = |det BI|2.

Note that |det BI|2can be interpreted as the volume contraction ratio of

the projection Cn→CI, α 7→ αIrestricted to W. For later purposes we also

note that E(|αi|2) = Pj|Bij|2≤1.

By the Binet-Cauchy formula and the orthogonality of the basis (bi) we

get X

|I|=r|det BI|2= det (hbi, bji)1≤i,j≤r= 1.

Therefore, an index set Ican be chosen such that

|det BI|2≥n

r−1

≥2−n.

By applying Lemma 2.7 to the random vector αIand using (2.11), we get

that with probability at least 1/2,

msv2

r(Circ(a)) ≥nrδrdet Σ ≥nrδr2−n,(2.12)

where δ= 2−(γ+√2θ). The mean square volume bound (2.5) implies that

C(Circ(a)) ≥log msvr(Circ(a)) −n

2≥1

2rlog n−1

2(2 + log δ−1)n,

with probability at least 1/2. This proves the lemma. 2

36 Lower Bounds for Linear and Bilinear Maps

2.3 An Alternative to Lemma 2.6 (after Raz)

The purpose of this section is to prove a variation of Lemma 2.6, using a

method suggested by Ran Raz (personal communication). The proof de-

pends crucially on a sharp tail estimate for the sum of independent expo-

nentially distributed random variables, as given in Equation (1.4). Also, the

parameter rhas to be carefully chosen.

Lemma 2.8 Let U⊆Cnbe a subspace of dimension r > (26/50)n. For a

standard Gaussian vector ain Uand sufficiently large n,

PC(Circ(a)) ≥1

50nlog n−O(n)>1

Proof. Let U⊆Cnbe a fixed subspace of dimension r=n, with some

 > 26/50 fixed. Let bbe a complex normal distributed vector in Cnand

let a=b−cbe the orthogonal projection of bto U. Write A= Circ(a),

B= Circ(b) and C=B−A= Circ(c). Set d=δn for some 0 <δ<1. The

mean square volume bound (2.5) implies

C(A)≥log msvd(A)−O(n)≥dlog σd(A)−O(n),

where σddenotes the d-th largest singular value of A. (The second inequality

is basically the rigidity bound.) Let Dbe a matrix of rank at most d−1

such that σd(A) = kA−Dk2(cf. Section 1.2). Then

√nσd(A)≥ kA−DkF≥ kB−DkF−kCkF,(2.13)

where k · kFdenotes the Frobenius norm3. We would like to show that

for large n, the right-hand side of Equation (2.13) is of order Ω(n) with

probability greater than 1/2. We do this by proving (a) a lower bound on

kB−Dk2

Fand (b) an upper bound on kCk2

(a) The term kB−Dk2

Fcan be bounded from below by the squares of the

n−dsmallest singular values of B, using the Hoffman-Wielandt inequality

[GVL96, 8.1.2]:

kB−Dk2

F≥

j=1

(σj(B)−σj(D))2≥

j=d+1

σ2

j(B),

where the last inequality follows from the fact that the last n−d+1 singular

values of Dvanish, since Dhas rank at most d−1.

Let β=n−1/2DFTnb, so that the vector of eigenvalues of Bis given by

√nβ, see Equation (2.6). Since n−1/2DFTnis unitary, βis again complex

standard normal distributed in Cn, and thus each 1

2|βi|2is exponentially

3The Frobenius norm of a matrix M= (mij ) is given by kMk2

F=Pi,j m2

ij .

2.3 An Alternative to Lemma 2.6 (after Raz) 37

distributed with parameter 1. For I⊂[n] with |I|=n−dset SI=

Pj∈I|βj|2, and set Smin := min|I|=n−dSI. From Bound (1.4) it follows that

for each such I, P [SI≤n−d]≤(√e/2)n−d, and by the union bound we

get

P [Smin ≤n−d]≤n

d√e

2n−d

.(2.14)

The binomial coefficient can be estimated using the entropy bound4

n

d≤2nH(δ),

where H(δ) = −δlog(δ)−(1 −δ) log(1 −δ) is the entropy function (recall

that δ=d/n). We would like the right-hand side in Equation 2.14 to be

smaller than 1/2 for large n. Taking logarithms, it follows that this is the

case whenever

H(δ) + (1 −δ) log √e

2<0.

This equation is satisfied for δ= 1/25. Using the fact that Pn

j=d+1 σ2

j(B) =

nSmin, we obtain n

j=d+1

σ2

j(B)≥24

25n2

with probability greater than 1/2.

(b) Next, we derive an upper bound on kCk2

F. It is known [GVL96,

2.5.3] that the square of the Frobenius norm is the sum of the squares of all

singular values of a matrix. The singular values of Care given by √n|γi|,

where γ=n−1/2DFTnc. It follows from this that kCk2

F=nPj|γj|2. Since

γis standard normal distributed in a subspace of dimension n−r, the sum

Pj|γj|2is χ2-distributed with 2(n−r) degrees of freedom, and the expected

value of kCk2

Fequals 2n(n−r) = 2(1 −)n2. The sum Pj|γj|2/2 can be

seen as the sum of n−rindependent, exponentially distributed random

variables. Therefore, Bound (1.3) implies that

PkCk2

F≤2(1 + λ)(1 −)n2≥1−((1 + λ)e−λ)n−r

holds for any λ≥0 (note that the of Bound (1.3) is called λhere). For

the right-hand side of Equation (2.13) to be positive, λhas to be adjusted

such that 2(1 + λ)(1 −)<24/25. Clearly, as long as  > 26/50, a solution

λ > 0 can be found.

Summarising, for  > 26/50 and sufficiently large n(the bigger , the

smaller nmay be), Equation (2.13) implies that with probability at least

1/2,

σd(A)≥Ω(√n),

4See [vL99, (1.4.5)] for a derivation.

38 Lower Bounds for Linear and Bilinear Maps

where d=n/25. Inserting this into the the singular value bound, the claim

follows. 2

2.4 Multiplication and Division of Polynomials

By reducing the cyclic convolution to several other important computational

problems, lower bounds of order nlog nfor these problems are proved. These

bounds are optimal up to a constant factor.

2.4.1 Polynomial Multiplication

Let f=Pn−1

i=0 aixi,g=Pn−1

i=0 bixibe polynomials in C[X] and fg =

P2n−2

i=0 cixi. Clearly, the coefficients of the cyclic convolution of fand g

can be obtained by adding ckto ck+nfor 0 ≤k < n. This observation and

Theorem 2.4 immediately imply the following corollary.

Corollary 2.9 The bounded coefficient complexity of the multiplication of

polynomials of degree less than nis at least 1

12 nlog n−O(nlog log n).

2.4.2 Division with Remainder

First, a lower bound on the inversion of power series mod Xn+1 is derived,

and then this is used to get a lower bound for the division of polynomials.

Let C[[X]] denote the ring of formal power series in the variable X. We

will study the problem to compute the first ncoefficients b1,,...,bnof the

inverse in C[[X]]

f−1= 1 + ∞

k=1

bkXk

of the polynomial f= 1 −Pn

i=1 aiXigiven by the coefficients ai. Note that

the bkare polynomials in the ai, which are recursively given by

b0:= 1, bk=

k−1

i=0

ak−ibi.

It should be noted that the problem to invert power series is not bilinear.

[Sie72] and [Kun74] designed a b.c. circuit of size O(nlog n) solving this

problem.

We now prove a corresponding lower bound on the b.c. complexity of

this problem by reducing polynomial multiplication to the problem to invert

power series.

Theorem 2.10 The map assigning to a1,...,anthe first ncoefficients

b1,...,bnof the inverse of f= 1−Pn

i=1 aiXiin the ring of formal power se-

ries has bounded coefficient complexity greater than 1

324 nlog n−O(nlog log n).

2.4 Multiplication and Division of Polynomials 39

Proof. Put g=Pn

i=1 aiXi. The equation

1 + ∞

k=1

bkXk=1

1−g=∞

k=0

gk.

shows that g2is the homogeneous quadratic part of P∞

k=1 bkXkin the vari-

ables ai.

Let Γ be an optimal b.c. circuit computing b1,...,bn. According to the

proof in [BCS97, Theorem 7.1], there is a b.c. circuit of size at most 9 S(Γ)

computing the homogeneous quadratic parts of the b1,...,bnwith respect to

the variables ai. This leads to a b.c. circuit of size at most 9 S(Γ) computing

the coefficients of the squared polynomial g2.

Now let m:= bn/3c, and assume that g=g1+X2mg2with g1, g2of

degree smaller than m. Then

g2=g2

1+ 2g1g2X2m+g2

2X4m,

By the assumption on the degrees we have no “carries” and we can therefore

find the coefficients of the product polynomial g1g2among the middle terms

of g2. Thus we obtain a b.c. circuit for the multiplication of polynomials of

degree m−1. The theorem now follows from Corollary 2.9. 2

We now show how to reduce the inversion of power series to the problem

of dividing polynomials with remainder. The reduction in the proof of the

following corollary is from [Str73a], see also [BCS97, Section 2.5].

Corollary 2.11 Let f, g be polynomials with n= deg f≥m= deg gand g

be monic. Let qbe the quotient and rbe the remainder of fdivided by g, so

that f=qg +rand deg r < deg g. The map assigning to the coefficients of

fand gthe coefficients of the quotient qand the remainder rhas bounded

coefficient complexity at least 1

324 nlog n−O(nlog log n).

Proof. Dividing f=X2nby g=Pn

i=0 aiXn−i, where a0= 1, we obtain:

X2n=n

i=0

qiXi n

i=0

aiXn−i+

n−1

i=0

riXi.

By substituting Xwith 1/X in the above equation and multiplying with

X2n, we get

1 = n

i=0

qiXn−i n

i=0

aiXi+

n−1

i=0

riX2n−i.

Since the remainder is now a multiple of Xn+1, we get

n

i=0

aiXi−1≡n

i=0

qiXn−imod Xn+1.

40 Lower Bounds for Linear and Bilinear Maps

From this it follows that the coefficients of the quotient are precisely the

coefficients of the inverse mod Xn+1 of Pn

i=0 aiXiin the ring of formal

power series, and the proof is finished. 2

Chapter 3

Unbounded Scalar Multiplications

The model of bounded coefficient circuits can be extended by allowing some

instructions corresponding to scalar multiplications with constants of abso-

lute value greater than two, briefly called help gates in the sequel. If there

are at most hhelp gates allowed, then the corresponding bounded coefficient

complexity is denoted by the symbol Ch.

It turns out that the proof techniques from the previous chapters are

robust in the sense that they still allow to prove nlog nlower bounds if the

number of help gates is restricted to (1 −)nfor some fixed  > 0.

3.1 Extension of the Mean Square Volume Bound

As a first step the mean square volume bound (2.4) and (2.5) is extended

for dealing with help gates.

Proposition 3.1 Assume A∈Cm×nhas the singular values σ1≥...≥σp,

where p:= min {m, n}. Then for all integers s, h with 1≤s≤p−h,

Ch(A)≥

h+s

i=h+1

log σi−m

2+h≥slog σh+s−m

2+h.

Proof. Let Γ be a b.c. circuit with at most hhelp gates, which computes

the linear map corresponding to A. Without loss of generality, it may be

assumed that Γ has exactly hhelp gates. Let gi,i∈I, be the linear forms

computed at the help gates of Γ. We transform the circuit Γ into a b.c.

circuit Γ0by replacing each help gate with a multiplication by zero. This new

circuit is obviously a b.c. circuit of size S(Γ0) = S(Γ)−h, computing a linear

map corresponding to a matrix B∈Cm×n. The linear maps corresponding

to Aand Bcoincide on the orthogonal complement of span{gi|i∈I}in

Cn, therefore B=A+Efor a matrix Eof rank at most h. From the

perturbation inequality (1.1) it follows that

σi(B)≥σi+h(A) for i≤p−h.

42 Unbounded Scalar Multiplications

By (2.4) this implies for s≤p−hthat

msv2

s(B)≥X

0<i1<···<is≤p−h

σ2

i1(B)···σ2

is(B)≥X

h<i1<···<is≤p

σ2

i1(A)···σ2

is(A).

On the other hand, the mean square volume bound (2.5) implies

S(Γ) −h=S(Γ0)≥log msvs(B)−m

Combining the last two estimates completes the proof. 2

Remark 3.2 1. Proposition 3.1 implies C(1−)n(DFTn)≥(1

2nlog n−n)

for the Discrete Fourier Transform DFTn, provided 0 <  ≤1.

2. The number hof help gates may be replaced by the dimension of the

subspace spanned by the linear functions computed at the help gates.

3. Proposition 3.1 can be seen as a variant of the spectral lemma in

[Cha98]. Using entropy considerations, Chazelle obtained the slightly

worse lower bound Ω((r−2h) log σr) for the b.c. complexity of a matrix

A∈Rn×nwith at most hhelp gates. While this allows to handle at

most n/2 help gates, Chazelle’s result is stronger in the sense that

it involves a more general notion of help gates, which are allowed to

compute any function of the previous intermediate results.

3.2 Extremal Values of Gaussian Random Vectors

In this section an auxiliary result about the distribution of the maximal ab-

solute value of the components of a Gaussian random vector is derived. This

result is needed in order to extend the the lower bound on cyclic convolution

by accommodating help gates.

Lemma 3.3 1. A centred Gaussian random vector X= (X1,...,Xn)in

Rnwith maxiE(X2

i)≤1satisfies for any  > 0

lim

n→∞Pmax

i|Xi|>√2 ln n+= 0.

2. A centred Gaussian random vector Z= (Z1,...,Zn)in Cnsuch that

maxiE(|Zi|2)≤1satisfies for any  > 0

lim

n→∞Pmax

i|Zi|>2pln(2n) + = 0.

3.3 Cyclic Convolution and Help Gates 43

Proof. 1. Since Xis centred we have for any u∈R

Phmax

i|Xi| ≥ ui≤Phmax

iXi≥ui+ P hmax

i(−Xi)≥ui≤2P hmax

iXi≥ui.

For proving the first assertion it is therefore sufficient to show that for any

 > 0

lim

n→∞Pmax

iXi>√2 ln n+= 0.(3.1)

For this we may assume that the components of Xare uncorrelated.

In fact, Slepian’s inequality (see [LT91]) implies that for centred Gaussian

vectors X= (X1,...,Xn) and Y= (Y1,...,Yn) we have

Pmax

iXi≤u≤Pmax

iYi≤u

provided E(X2

i) = E(Y2

i) and E(XiXj)≤E(YiYj) for all i, j.

We may also assume that all the Xihave variance 1 since the distribution

function

Fσ(u) := 1

σ√2πZu

∞

exp(−t2

2σ2)dt.

of a centred normal random variable with variance σ2≤1 satisfies F1(u)≤

Fσ(u) for all u≥0. Hence, if Xis a Gaussian vector with uncorrelated

components Xiof variance σ2

i≤1, we have

F1(u)n≤

i=1

Fσi(u) = P max

iXi≤u.

In the case where X1,...,Xnare independent and standard normal dis-

tributed we have according to [Cra46] that

E(max

iXi) = √2 ln n+o(1),Var(max

iXi) = π2

ln n(1 + o(1)), n → ∞

and Claim (3.1) follows from Chebychev’s inequality.

2. The second assertion follows from the first one applied to the Gaussian

vector Wwith values in R2ngiven by the real and imaginary parts of the

Zi(in some order). Note that max1≤i≤n|Zi| ≤ √2 max1≤j≤2n|Wj|.2

3.3 Cyclic Convolution and Help Gates

Our goal is to prove the following extension of Theorem 2.4.

Theorem 3.4 The bounded coefficient complexity with at most (1 −)n

help gates of the n-dimensional cyclic convolution convnis at least Ω(nlog n)

for fixed 0<  ≤1.

44 Unbounded Scalar Multiplications

The proof follows the same line of argument as in Section 2.2. The next

lemma is an extension of Lemma 2.6.

Lemma 3.5 Let U⊆Cnbe a subspace of dimension rand h∈Nwith

h < r. For a standard Gaussian vector ain U, we have

PCh(Circ(a)) ≥1

2(r−h) log n−n(c+ log log n)>1

for some constant c > 0.

Proof. As in the proof of Lemma 2.6 it is assumed that the random vector

α=n−1/2DFTnais standard Gaussian with values in some r-dimensional

subspace W. Recall that √n|αi|are the singular values of Circ(a). We

denote by |α(1)| ≥ ...≥ |α(n)|the components of αwith decreasing absolute

values. In particular, |α(1)|= maxi|α(i)|. Proposition 3.1 implies that

Ch(Circ(a)) ≥

i=h+1

log(√n|α(i)|)−n

2+h

2(r−h) log n+ log r

i=h+1 |α(i)|−n

2+h.

In the proof of Lemma 2.6 (2.12) we showed that msv2

r(Circ(a)) ≥

nrδr2−nwith probability at least 1/2. In the same way, one can show that

with probability at least 3/4 we have msv2

r(Circ(a)) ≥nrcn

1for some fixed

constant c1>0. From the estimate

|I|=rY

i∈I|αi|2≤2n

i=1 |α(i)|2

we thus obtain that Qr

i=1 |α(i)|2≥(c1/2)nwith probability at least 3/4.

By applying Lemma 3.3 to the centred Gaussian random variable αwe

obtain that with probability at least 3/4

max

i|α(i)|2=|α(1)|2≤c2log n

for some fixed constant c2>0. (Recall that E(|α(i)|2)≤1.)

Altogether, we obtain that with probability at least 1/2 we have

i=h+1 |α(i)|2≥Qr

i=1 |α(i)|2

|α(1)|2h≥c1

2c2log nn

This completes the proof of the lemma. 2

3.3 Cyclic Convolution and Help Gates 45

Proof. (of Theorem 3.4) Let Γ be a b.c. bilinear circuit computing convn

using at most h≤(1 −)nhelp gates, 0 <  ≤1. Referring to the partition

of instructions in Definition 1.2, we assume that Γ(1) uses h1help gates,

and that Γ(2),Γ(3),Γ(4) use a total of h2help gates. Thus h1+h2=h. Let

f1,...,fkdenote the linear forms computed by Γ(1).

Assume h2< r < n −h1and set R= rign−r(f1,...,fk). By Lemma 2.5

and Lemma 3.5 there exists an a∈Cn, such that the following conditions

hold:

1. max1≤i≤klog |fi(a)| ≤ log(2pln (4k)R)≤log R+O(log log n),

2. Ch2(Circ(a)) ≥1

2(r−h2) log n−O(nlog log n).

On the other hand, by Proposition 3.1 and using σn−r(f1,...,fk)≥R, we

get

S(Γ) ≥ Ch1(f1,...,fk)≥(n−r−h1) log R−k

The proof of Lemma 1.4 shows that

S(Γ) + nmax

1≤i≤klog |fi(a)| ≥ Ch2(Circ(a)).

By combining all this we obtain

1 + n

n−r−h1S(Γ) + nk

2(n−r−h1)+O(nlog log n)≥1

2(r−h2) log n.

We set now r:= b(h2+n−h1)/2c. Then r+h1≤(1−

2)nand r−h2≥

2n−1.

By plugging this into the above inequality we obtain

+ 2

S(Γ) + k

+O(nlog log n)≥

4nlog n.

Let κ:= 2

8. If k≤κn log n+n, then S(Γ) ≥2

8(+2) nlog n−O(nlog log n).

On the other hand, if k > κn log n+n, then trivially

S(Γ) ≥ Ch1(f1,...,fk)≥k−n≥κn log n.

This completes the proof of the theorem. 2

46 Unbounded Scalar Multiplications

Part II

Computational Complexity of

Euler Characteristics

Chapter 4

Preliminaries II

Some fundamental geometric and topological concepts, including the defini-

tions of the Hilbert polynomial and the topological Euler characteristic, are

recalled. Also, a short introduction to complexity theory in the setting of

the Blum-Shub-Smale model of computation is given. The methods used in

the proofs of Chapters 6, 7, and 8 assume familiarity with algebraic geome-

try at a level beyond of what can reasonably be presented here. The main

purpose of the geometric and topological part of this chapter is therefore to

fix notation and terminology. More specialised concepts are introduced in

Chapters 6, 7, and 8, as needed.

4.1 Algebraic Geometry

Most of what is presented in this section can be found in standard textbooks

on algebraic geometry, such as [Sha74, Har77, Har95].

4.1.1 Basic Terminology

An affine variety (or algebraic set)Vis defined as the zero set

V=Z(f1,...,fr) := {x∈Cn|f1(x) = 0,...,fr(x) = 0}

of finitely many polynomials f1,...,fr∈C[X1,...,Xn]. Likewise, the term

projective variety is used to denote the common zero set of a finite set of

homogeneous polynomials in complex projective space Pn. Sometimes ZCn

or ZPnis written to emphasise that the zero set is to be considered in affine

or projective space. The vanishing ideal I(V) of an affine (projective) variety

Vconsists of all the (homogeneous) polynomials vanishing on V.

The affine (projective) varieties in Cn(Pn) are the closed sets of the

Zariski topology. Non-empty open sets in this topology are dense in Cn

(Pn). Locally closed sets in the Zariski topology are called basic quasi-

algebraic (quasi-projective). Finite unions of basic quasi-algebraic are called

quasi-algebraic (quasi-projective). A property is said to hold for almost all

points in a variety if the set of points satisfying the given property is a dense

subset with respect to the Zariski topology.

50 Preliminaries II

If Vis an affine variety and f1,...,frgenerate the ideal I(V), then

the Zariski tangent space TxVof Vat a point x∈Vis defined by TxV=

ZCn(dxf1,...,dxfr), where the differential dxf:Cn→Cof fat xis the

linear function dxf=Pn

j=1 ∂

∂Xjf(x)Xj. The point x∈Vis called a smooth

point of Vif the dimension of TxVequals the local dimension of Vat x.

Otherwise, xis called a singular point of V.

4.1.2 Grassmannians and Products of Projective Space

For 0 ≤k≤nthe Grassmannian G(k, n) is the set of all k+ 1-dimensional

vector subspaces of Cn+1. The simplest example is G(0, n) which is iso-

morphic to Pn. In general, the Grassmannian can be embedded as a closed

subset G(k, n)⊆P(n+1

k+1)−1of projective space, and as such it is an irreducible

projective variety of dimension (k+ 1)(n−k), see [Har95, Lecture 6]. El-

ements in G(k, n) are in bijective correspondence with subspaces Pk⊆Pn.

We often write Ln−kfor an element in G(k, n), the superscript emphasising

the codimension.

Another important class of varieties are products of projective spaces.

The product Pn×Pmhas the structure of a projective variety via the Segre

embedding Pn×Pm,→P(n+1)(m+1)−1, see [Har95, Example 2.11].

4.1.3 The Hilbert Polynomial

Let S:= C[X0,...,Xn] denote a polynomial ring and let Mbe a finitely

generated, graded S-module. Denote by Mkthe k-th graded part of M.

The function hM:Z→N, defined by hM(k) = dimCMkis called the Hilbert

function of M. A proof of the following can be found in [Har77, I.7].

Theorem 4.1 (Hilbert-Serre) Let Mbe a finitely generated, graded S-

module. Then there exists a unique polynomial pM(T)∈Q[T]such that

hM(`) = pM(`)for sufficiently large `. Furthermore, the degree of pMequals

the dimension of the projective zero set of the annihilator {s∈S|sM = 0}

of M.

The polynomial pM(T) is called the Hilbert polynomial of M. Of special

interest is the case M=S/I, where I⊆Sis a homogeneous ideal. If

I=I(V) is the homogeneous ideal of a complex projective variety V⊆Pn,

then we write pV:= pS/I and call this the Hilbert polynomial of V. It thus

follows that deg pV= dim V.

Example 4.2 1. The Hilbert polynomial of V=Pnis pV(T) = T+n

n.

2. Let f∈C[X0,...,Xn] be homogeneous and squarefree of degree dand

let V=ZPn(f). Then pV(T) = T+n

n−T+n−d

n.

4.2 Algebraic Topology 51

Let V⊆Pnbe an m-dimensional projective variety with Hilbert poly-

nomial pV(T) = pmTm+···+p1T+p0. The geometric degree deg Vof

Vis defined as deg V:= m!pm. The degree counts the number of inter-

section points of Vwith a generic linear subspace of complementary di-

mension [Har95, Lect. 18]. Moreover, deg(V1∪V2) = deg V1+ deg V2if

V1,V2have the same dimension. The arithmetic genus of Vis defined as

ga(V) := (−1)m(p0−1). While the degree depends on the embedding in

projective space, the arithmetic genus is a birational invariant (see [Har77,

Ex. III.5.3]).

4.2 Algebraic Topology

General references on algebraic topology are [Bre97] and [Hat02]. Further

good summaries of singular homology theory and the associated intersection

theory can be found in [Ful97, Appendix B] and [Man01, Appendix A].

4.2.1 Euler Characteristic

The Euler characteristic is one of the oldest and most important topological

invariants. There are many ways to characterise it; some are very general,

others assume restrictions on the topological space X. The most intuitive

one is perhaps using a finite triangulation. In this situation, which requires

Xto be finitely triangulable (and therefore, compact), the Euler charac-

teristic is the alternating sum χ(X) = Pd

i=0(−1)iNi, where Nidenotes the

number of i-simplices in the triangulation and dis the dimension of X. It

is a fundamental fact that this definition does not depend on the particu-

lar triangulation chosen. As an example, for the tetrahedron T, we have

χ(T) = 4 −6 + 4 = 2, and therefore for the 2-sphere χ(S2) = 2. More

generally, for the n-sphere Snwe have χ(Sn) = 1 + (−1)n.

For possibly more general topological spaces, the Euler characteristic is

defined via singular homology (see Section 8.1). In the following definition,

Hk(X) denotes the k-th singular homology group of a topological space X.

Definition 4.3 The Euler characteristic χ(X) of a topological space Xis

defined as the alternating sum χ(X) = Pk∈N(−1)krank Hk(X), provided

this sum is finite.

If V⊆Pnis an m-dimensional variety over C, then it can be seen as an

2m-dimensional real variety, and we have Hj(V) = 0 for j > 2m.

In [BC04a], the complexity of computing the modified Euler characteris-

tic χ∗(S) of a semi-algebraic set Swas studied. The latter is a minor varia-

tion of the Euler characteristic, introduced by Andew Yao [Yao92], which is

additive with respect to disjoint unions and coincides with the usual Euler

characteristic for compact semi-algebraic sets.

52 Preliminaries II

The following proposition expresses that for complex quasi-algebraic sets,

the modified Euler characteristic coincides with the Euler characteristic. A

proof can be found in [Ful93, Exercise §4.5, p. 95 and Notes §4.13, p. 141].

Proposition 4.4 If V=FN

i=1 Viis a disjoint union of complex quasi-

algebraic sets, then χ(V) = PN

i=1 χ(V).

The Euler characteristic satisfies the following principle of inclusion and

exclusion.

Lemma 4.5 Let V1,...,Vrbe complex quasi-algebraic sets. Write VI:=

∪i∈IVifor an index set I⊆[r]. Then

χ(V1∩···∩Vr) = X

∅6=I⊆[r]

(−1)|I|−1χ(VI).

Proof. This follows easily from Proposition 4.4 and [BC04a, Corollary 6.4]

by passing to the complement. 2

4.3 Transversality

A central concept in differential topology is the concept of transversality. In

many cases, the notion of transversality allows to formalise “general po-

sition” arguments. For the following definition, recall that a morphism

ϕ:V→Yof smooth varieties induces a differential dxϕ:TxV→Tϕ(x)Y

of tangent spaces at each x∈V.

Definition 4.6 Let X⊆Ybe a subvariety of a smooth variety Yand

ϕ:V→Ya morphism of smooth varieties. Then ϕmeets Xtransverse

at x∈ϕ−1(X), written ϕtxX, if Xis smooth at ϕ(x) and Tϕ(x)X+

dxϕ(TxV) = TxY. The map ϕis transverse to X, written ϕtX, if ϕtxX

holds for all x∈ϕ−1(X).

A common special case is when ϕis the inclusion. In this case, VtX

is written. The relationship of transversality to regular points and regular

values, which is central in differential topology, is described in Section 6.5.

It is not immediately obvious how to generalise the definition to possibly

singular varieties. One approach is to stratify the varieties in question into

smooth subvarieties in a certain way, and require the morphism to meat

each stratum transversely [GM88]. In the special case of a decomposition of

a Schubert variety into Schubert cells, this approach is taken in Chapter 7.

An important fact is that transversality is a generic condition. A special

case is the following well-known statement, see [Har95, Lecture 18].

4.4 Model of Computation and Complexity 53

Theorem 4.7 Let V⊆Pnbe a smooth projective variety. Then almost all

linear subspaces L⊆Pnmeet Vtransversely. Moreover, there is an integer

d, such that for all Lof dimension n−dim V,LtVimplies that the number

of intersection points equals d.

In fact, the constant din the theorem equals the degree deg Vof V.

A similar result for subvarieties of Pn×Pnis given in Proposition 6.3 and

used in Chapter 6. A generalisation of Theorem 4.7 for homogeneous spaces

(for example, the Grassmannian) is Kleiman’s transversality lemma [Kle74],

a variant of which is given in Lemma 7.9 and used in Chapter 7. These

two variations lead to the concepts of projective degrees (see [Har95, Lecture

18]) and projective characters (see [Ful98, Example 14.3.3]), which play a

fundamental role in the complexity results in Chapters 6 and Chapter 7 for

the Euler characteristic and the Hilbert polynomial, respectively.

4.4 Model of Computation and Complexity

This section gives a short introduction to complexity theory in the Blum-

Shub-Smale model of computation. Throughout this section, Kdenotes one

of the fields F2,R, or C, and K∞is the set of all finite strings of elements

of K. The notation F2is used to denote the field with two elements.

The notions of algorithm and complexity acquire a precise meaning only

after a model of computation has been specified. In classical complexity

theory, the model of choice is the (multi-tape) Turing machine. For algo-

rithmic problems arising in areas of mathematics such as numerical analysis

or algebraic geometry, it seems worthwhile to extend the power of Turing

machines, allowing them to do arithmetic in structures such as the real

or complex numbers. Such enhanced Turing machines were introduced by

Lenore Blum, Michael Shub, and Steve Smale in [BSS89] and are commonly

referred to as BSS machines. Roughly speaking, a BSS machine over a field

Ktakes inputs from K∞, performs a number of arithmetic operations and

comparisons following a finite list of instructions, and either halts return-

ing an element of K∞or loops forever. For a comprehensive exposition the

reader may consult the monograph [BCSS98].

The following brief treatment of complexity classes in the BSS model is

based on the characterisation by John B. Goode [Goo94] and Bruno Poizat

[Poi95]. This characterisation does not depend on a formal specification of

a BSS machine, using uniform families of circuits instead.

4.4.1 Circuits

The presentation given here follows [BC04b] and also [BCSS98, 18.4], other

references are [Poi95, Koi00a]. More comprehensive information on circuits

54 Preliminaries II

in general may be found in [Gat86]1.

Definition 4.8 An (algebraic) circuit Cover Kis an acyclic directed graph,

whose nodes are either input gates of in-degree 0, constant gates of in-degree

0 labelled with constants from K,arithmetic gates of in-degree 2, labelled by

one of {+,−,×, /},sign gates of in-degree 1, and output gates of in-degree

1 and out-degree 0.

The size of a circuit Cis the number nodes in it, while the depth is the

number of nodes on the longest path from an input to an output node. Given

an assignment of elements of Kto each input gate, each arithmetic gate

performs an arithmetic operation on the values of Kprovided by its parent

nodes (if defined), while each sign gate returns 1 if the value xprovided by

its parent node satisfies x6= 0, and 0 else. If Kis ordered, then a sign gate

returns 1 if x≥0 and 0 else. Sign gates allow the computation to branch

according to sign tests. A circuit with ninput gates and moutput gates

thus defines a (partial) map Kn→Km(assuming an order on the nodes of

the circuit). The value of this map on x∈Knis denoted by C(x).

Example 4.9 The following circuit over Rreturns x2+y2if (x, y) satisfies

x2+y2≥1.

x))55?>=<89:;

∗

y))55?>=<89:;

∗//?>=<89:;

+//

?>=<89:;

−//GFED@ABC

sgn //?>=<89:;

∗//output

Figure 4.1: Algebraic circuit

A family {Cn}n∈Nof circuits computes a function f:K∞→K∞, if for

each n∈Nand x∈Kn,Cn(x) = f(x) holds. The family decides a language

S⊆K∞, if it computes its characteristic function χS. A family {Cn}n∈Nis

called uniform, if there exists a fixed number of constants α1,...,αm∈K,

such that each circuit Cncontains exactly mconstant nodes labelled with

the αi, and there exists a Turing machine, which on input (n, i) outputs a

description of the i-th node of Cn(with respect to some natural order on

the nodes of the circuit). Moreover, the family is called P-uniform, if the

Turing machine operates in time polynomial in n. Uniform circuits with no

constants other than 0 and 1 are called constant free.

1Our notion of circuit corresponds to the notion of arithmetic network in [Gat86].

4.4 Model of Computation and Complexity 55

4.4.2 Complexity Classes

It can be shown2that the functions computable by BSS machines over K

are just the functions computable by uniform families of circuits. The next

definitions thus characterise languages (functions) that are considered de-

cidable (computable) by BSS machines over Kwith certain bounds on their

resources.

Definition 4.10 (1) The class PKconsists of all languages S⊆K∞

decidable by a P-uniform family of circuits {Cn}n∈Nof size polynomial

in n. The corresponding function class is called FPK.

(2) The class PARKconsists of all languages decidable by a P-uniform fam-

ily of circuits {Cn}n∈Nof depth polynomial in n. The corresponding

function class is called FPARK.

(3) The class EXPKconsists of all languages decidable by a P-uniform

family of circuits {Cn}n∈Nof size exponential in n. The corresponding

function class is called FEXPK.

The inclusions PK⊆PARK⊆EXPKare clear. For K=Rand K=C

it is known that PARK6= EXPK[Cuc92, BC04b], but in general only the

inequality PK6= EXPKis known. The class PARF2equals the class PSPACE

of languages decidable by Turing machines in polynomial space [Bor77].

However, the definition of PSPACE is not suited for generalisation to BSS

machines over arbitrary fields K: it was shown by Michaux [Mic89] that BSS

machines over Rcan compute anything in constant space3.

The next important class consists of those languages S, for which mem-

bership x∈Sis efficiently decidable with the help of a witness y∈K∞4.

A relation R⊆(K∞)k+1 is called balanced, with associated polynomials

p1,...,pk, if for x∈Kn, (x, y1,...,yk)∈Rimplies yi∈Kpi(n)for 1 ≤i≤k.

Definition 4.11 The class NPKconsists of all languages S⊆K∞, for which

there exists a balanced relation RS⊆K∞×K∞in PKwith associated

polynomial p, such that

x∈S⇔ ∃y∈Kp(n)(x, y)∈RS

holds for an x∈Kn.

At the time of this writing, it is not known whether PK6= NPKholds for

K∈ {F2,R,C}. The definition of NPKcan be generalised in order to define

a whole hierarchy of complexity classes.

2This is implied by [Goo94, Poi95] and [BCSS98, Chapter 18].

3This is essentially because of the possibility of encoding a lot of information into a

single real number.

4One way of viewing NP

Kis as consisting of languages S, such that for each x∈Sthere

is a short proof of membership, as explained, for example, in the first Lecture in [Rud04].

56 Preliminaries II

Definition 4.12 Let w∈N. The class Σw

Kconsists of all languages S⊆

K∞, for which there exists a balanced relation RS⊆(K∞)w+1 in PK, with

associated polynomials p1,...,pw, such that for all x∈Knand all n∈N,

x∈S⇔Q1y1∈Kp1(n). . . Qwyw∈Kpw(n)(x, y1, . . . , yw)∈RS

where Q1=∃and the quantifiers Qi∈ {∃,∀} alternate. If Q1=∀, then

the class is denoted by Πw

K. The cumulative polynomial hierarchy over Kis

defined as the union PHK=∪wΣw

K=∪wΠw

The class Σ1

Kis just NPK, and the class Π1

Kis the set of of languages

whose complement is in NPK. The latter is also called coNPK.

All complexity classes considered so far have a constant free version.

These are the classes arrived at by requiring all circuit families occurring

in the definitions to be constant free. These classes will be denoted by P 0

NP 0

K, PH 0

K, etc. Following [BC04a], complexity classes over F2are written

sans-serif and without the subscript F2, e.g., Pstands for PF2.

4.4.3 Decidability

There is an obvious but nonetheless useful way of characterising BSS de-

cidable sets over a field K. Given a set of constants α1,...,αm∈K,

let FK(α1,...,αm) denote the set of first-order formulas in the theory of

fields (or, in case Kis ordered, of ordered fields) with constants 0, 1, and

α1,...,αm. The notion of P-uniformity for families {Fn}n∈Nof formulas is

defined just as for circuits. A subset S⊆K∞is definable by a family of

formulas {Fn}n∈N, if for each n∈N,

S∩Kn={x∈Kn|Fn(x)}.

The next lemma follows from [BCSS98, Section 2.6].

Lemma 4.13 Let S⊆K∞. Then Sis decidable by a P-uniform family of

circuits {Cn}n∈Nif and only if there exist constants α1,...,αmsuch that

Lis definable by a a P-uniform family {Fn}n∈Nof existential formulas in

FK(α1,...,αm).

If the field Kis one of F2,R, and C(and in fact, any field allowing

quantifier elimination), then the polynomial hierarchy is decidable. More

specifically, over R, the following theorem holds. In the form presented

here, this is due to James Renegar [Ren92]. A general reference is [BPR03,

Chapter 14].

Theorem 4.14 Let F∈FRbe a formula with kfree variables, nbounded

variables and walternating quantifier blocks, of the form

Q1y1∈Kn1. . . Qwyw∈KnwG(x, y1,...,yw),

4.4 Model of Computation and Complexity 57

where Qi∈ {∃,∀} and Gis a quantifier-free formula with matomic predi-

cates of degree at most δ. Then Fis equivalent to a quantifier-free formula

F0in disjunctive normal form WI

i=1 VJi

j=1 hij∆ij0, with Matomic predicates

hij of degree at most D, where Dand Msatisfy the bounds

log D≤2O(w)log(mδ)

i=1

ni,log M≤2O(w)(k+ 1) log(mδ)

i=1

and ∆ij ∈ {≥, >, =, <, ≤}. If moreover the coefficients in Fare of bit size

at most `, then the hij can be assumed to be integer polynomials with

coefficients of bit size at most L, with log L≤2O(w)log(mδ)Qw

i=1 ni+

O(log(k+`)).

The sets in Rndefinable by quantifier-free formulae in FRare called

semi-algebraic, the corresponding sets in Cnare called quasi-algebraic or

constructible. Here, FRdenotes the first-order language of the reals with

arbitrary real constants (as opposed to F0

R, which is used to denote the

language without constants other than 0 and 1).

4.4.4 Coding Polynomial Systems

Algorithmic problems in algebraic geometry involve questions about systems

of multivariate polynomials, the ideals they generate, and sets defined by

them (i.e., semi- or quasi-algebraic sets, projective varieties, etc.). In or-

der to study these problems within the complexity classes introduced, their

coding as strings in K∞has to be addressed. Here and in the following, a

polynomial f=Pe∈IaeXe1

1···Xen

nis represented in the sparse encoding as

a list of pairs (ae, e) for e∈I, where I={e∈Nn|ae6= 0}. The exponent

vector eis given by a bit vector of length at most O(nlog deg f). The aeare

usually assumed to be elements of K∞, even though the case where K=F2

and the ae∈Zare represented as bit vectors is sometimes considered. The

sparse size of fis defined as the sum of the sizes of the (ae, e) for e∈I.

This size can be exponential in nin the worst case. Other possible encod-

ings are the dense encoding or the straight-line program encoding, see [Kri04]

(and the references therein) for more on the latter. A set Z⊆Kndefin-

able by a quantifier-free first-order formula over K(for example, algebraic,

quasi-algebraic, or semi-algebraic) is coded by writing the defining formula

in disjunctive normal form F=WiVjhij∆ij0, where the hij are polynomial

equations and inequalities given in sparse encoding. A set C ⊆ K∞is called

aproperty of first-order definable sets, if it consists of codings of polynomial

systems, such that membership F∈ C depends only on the underlying set

Z={x|F(x)}. By abuse of notation, Z∈ C is sometimes used in order

to express that any admissible coding of a first-order formula defining Zis

in C.

58 Preliminaries II

For many problems of interest, the choice between dense and sparse

encoding turns out to be not so important from the point of view of com-

plexity theory. For example, it is always possible to transform a system of

polynomial equations into one of quadratic equations in polynomial time, by

introducing new variables that allow to represent monomials of high degree

by “repeated squaring”. Over Cand R, these new quadratic systems have

the same dimension, number of solutions (if finite), and homeomorphism

type as the original system. More details, and a worked out example, can

be found in [Koi97b].

4.4.5 Basic Decision Problems

The most elementary question to be asked about a system of polynomial

equations is if there is a solution. This problem was named HN in [BSS89]

in analogy to Hilbert’s Nullstellensatz. The general specification follows.

HNK(Hilbert’s Nullstellensatz). Given a finite set of multivariate poly-

nomials with coefficients in K, decide whether these polynomials have

a common zero over K.

The problem HNKis clearly in NPKfor any field K. For K=F2,

this problem is equivalent to SAT, the satisfiability problem for Boolean

formulas5. The problem HNKis decidable over the fields F2,R, and C.

Over F2this is trivial. One way to establish decidability over Cis by

means of the effective Nullstellensatz6: A system of multivariate polyno-

mials f1,...,fr∈C[X1,...,Xn] of degree at most ddoes not have a solu-

tion over Cif and only if there is a representation 1 = Pr

j=1 ajfj, where

the aj∈C[X1,...,Xn] are polynomials such that ajfjhas degree degree at

most max{d, 3}n. This reduces the problem HNCto the problem of deciding

whether a system of linear equations has a solution.

Another fundamental problem involving systems of polynomial equations

over the real and complex numbers is concerned with the dimension of an

semi-algebraic and algebraic set.

DimR(Semi-algebraic dimension). Given a set of multivariate real poly-

nomials describing a semi-algebraic set Zand d∈N, decide whether

dim Z≥d.

DimC(Algebraic dimension). Given a finite set of multivariate com-

plex polynomials with affine zero set Zand d∈N, decide whether

dim Z≥d.

5See [Pap94, Chapter 4] and [Rud04].

6The canonical reference is [Kol88]. There are variants of the effective Nullstellensatz

for polynomials over Z, including considerations about the size of coefficients as well.

These are known as “arithmetic effective Nullstellensatz”, see [KPS01] and the references

therein.

4.4 Model of Computation and Complexity 59

For the algorithmic problem of computing the dimension of semi-algebraic

sets, the reader may consult [BPR03, 14.4] and the references given there.

The fact that DimCis solvable in parallel polynomial time follows from

[CGH89, GH91, GH93]. The problem was shown to be in NPCby Pascal

Koiran [Koi97b].

Another important problem is that of computing the local dimension of

a semi-algebraic set at a point x. The local dimension at xis the largest

dimension of an irreducible component containing x. It is known that the

following problem is in PHR: decide if the local dimension of a semi-algebraic

set at a point xis at least d(see Lemma 4.16)7.

4.4.6 Reduction and Completeness

The problem HNKis in a sense representative for NPK. This is made precise

by the notions of reduction and completeness.

Definition 4.15 Let S, T ⊆K∞. A function π:K∞→K∞is called a

(many-one) reduction from Sto T, if π∈FPKand for all x∈K∞,x∈Sif

and only if π(x)∈T. If Cis a class of subsets of K∞, then Tis called hard

for C, if every S∈ C reduces to T. If moreover T∈ C, then Tis complete

for C.

It is a fundamental result, shown in [BSS89, BCSS98], that for any K∈

{R,C}, the problem HNKis complete for NPK. The NP-completeness of

HNF2(generally known as SAT) was shown by Stephen Cook [Coo71] and

Leonid Levin [Lev73]. The problems DimRand DimCwhere shown to be

complete for NPRand NP

C, respectively, by Pascal Koiran [Koi97b, Koi99b].

4.4.7 Relativisation

Let Cbe a class of functions ϕ:K∞→K∞(possibly characteristic functions

of languages), computable by a uniform family of circuits. A circuit Ccan

be enhanced by adding functions ϕ∈ C to the set of operations {+,−,×, /}

performed by arithmetic gates. These additional gates are then called oracle

gates for C. The relativised class P C

K(FP C

K) consists of those languages

(functions) decided (computed) by a P-uniform family of circuits with oracle

for C. The relativised classes NP C

K, PH C

K, etc., are defined in an obvious

manner.

Relativisation allows to define a more liberal, yet natural, concept of

reduction. Let S, T ⊆K∞. Then STuring reduces to T, if S∈PT

K. If

Cis a class of subsets of K∞, then Tis called Turing hard for C, if every

S∈ C Turing reduces to T. If moreover T∈ C, then Tis Turing complete

for C. The concept of Turing reduction also works if S,Tare replaced by

7The corresponding problem over Cis more involved. An analysis of this problem is

given in [Koi00b].

60 Preliminaries II

functions. Clearly, many-one reduction implies Turing reduction, but the

converse need not be the case.

4.4.8 Implicit Inputs

There are situations in which first-order definable sets Zu, parametrised

by some u∈K∞, are not given explicitly by their defining polynomials,

but for which the membership relation x∈Zuis nonetheless decidable

in polynomial time. An example is provided by determinantal varieties:

given a matrix Mwith with entries in C[X1,...,Xn] and k∈N, define

ZM,k := {x∈Cn|rankM(x)≤k}. Clearly, given Mand k, membership

to ZM,k can be decided in polynomial time, while writing down the rank

condition in terms of non-vanishing of minors would lead to a representation

of possibly exponential size.

Many properties C ∈ PHKof semi-algebraic or constructible sets can be

expressed by means of first-order formulas involving only the membership

relation x∈Zfor a set Z∈ C. For example, the property “is bounded” can

be expressed as

∃B∀xB > 0∧((x∈Z)⇒ kxk2≤B2).

Assume Cis such a property of first-order sets in PHK, and let R⊆K∞×K∞

be a balanced relation in PHKwith associated polynomial p. For u∈Knset

Zu={x∈Kp(n)|(u, x)∈R}.

Then it is not hard to see that the set

S={u∈K∞|Zu∈ C}

is also in PHK.

A special case of this observation is given by the next lemma. The lemma

is stated using the constant free polynomial hierarchy, since this situation is

needed later on.

Lemma 4.16 Let R⊆R∞×R∞be a balanced relation in PH0

Rwith

associated polynomial pand consider for u∈Rnthe semi-algebraic set

Su:= {x∈Rp(n)|(u, x)∈R}. Then both decision problems {(u, d)∈

R∞×N|dim Su≥d}and {(u, x, d)∈R∞×R∞×N|dimxSu≥d}are in

PH0

Proof. It is known that dim Su≥dif and only if there exists a d-

dimensional coordinate subspace such that the projection of Suon this

subspace has a non-empty interior. Writing this condition as a first order

formula over Ryields the claim for the dimension 8.

8For a more economic description, see [Koi99b].

4.4 Model of Computation and Complexity 61

Let B(x) denote the open ball with radius centred at x. Then dimxSu≥

dif and only if dim(Su∩B(x)) ≥dfor sufficiently small  > 0, cf. [BPR03].

Writing this as a first order formula over Rimplies the claim about the local

dimension. 2

62 Preliminaries II

Chapter 5

Counting Complexity Theory

The counting theory presented here was developed by Peter B¨urgisser and

Felipe Cucker in [BC04a, BC04b, BCL05].

5.1 Counting Complexity Classes

Counting complexity classes consist of functions related to counting the num-

ber of witnesses to problem instances in NPK. The most prominent such

problem is the problem of counting the number of solutions to a system of

polynomial equations.

#HNK(Algebraic point counting). Given a finite set of multivariate poly-

nomials over K, count the number of common zeros in K, returning ∞

if this number is not finite.

The counting functions considered may not alway have finite values. It

is therefore convenient to extend the set of integers by adding infinities.

Let b

N:= N∪ {∞} and b

Z:= Z∪ {−∞,∞,nil}, with additional symbols

−∞,∞, and nil. The addition and multiplication of integers extends to

maps b

Z×b

Z→b

Zby setting

∞+ (−∞) := nil,(−∞) + ∞:= nil,0·(±∞) := 0,(±∞)·0 := 0,

and a+b:= nil, a·b:= nil if aor bequals nil. In all other cases, a+band a·b

are defined in the usual, intuitive way. It is straightforward to check that the

addition and the product are both associative on b

Z. The distributivity law

may be violated: for instance ∞=∞·(2 + (−1)) 6=∞·2 + ∞·(−1) = nil.

However, a·(b+c) = a·b+a·cholds for a∈Z\{0}, b, c ∈b

Z. The subtraction

is defined by a−b:= a+ (−1) ·bfor a, b ∈b

Z. The sum, the difference, and

the product of two functions K∞→b

Zis defined point-wise.

Definition 5.1 The class #PKconsists of all functions ϕ:K∞→b

N, for

which there exists a balanced relation R⊆K∞×K∞in PKwith associated

polynomial p, such that

ϕ(x) = |{y∈Kp(n)|(x, y)∈R}|

64 Counting Complexity Theory

holds for all x∈Knand all n∈N. The class GapKconsists of all functions

γ:K∞→b

Zof the form γ=ϕ−ψfor ϕ, ψ ∈#PK.

Clearly, #HNKbelongs to #PK. The corresponding problem for GapK

is the problem ∆HNKof computing the difference of the cardinalities of zero

sets of multivariate polynomials.

∆HNKGiven two finite families F1, F2of multivariate polynomials over K,

compute |Z(F1)|−|Z(F2)|.

If A⊆K∞and ϕis a function in GapKthat vanishes outside A, then

this function is sometimes specified as ϕ:A→b

Z. (An example are functions

{0,1}∞→Zin GapK.)

5.1.1 Properties of Counting Functions

Counting functions satisfy useful closure properties with respect to algebraic

operations and composition. The first such property, given in following

lemma, is easy to verify.

Lemma 5.2 Let ϕ∈GapKand ψ∈FPK. Then ϕ◦ψ∈GapK.

The next lemma from [BCL05] lists some algebraic properties of #PK

and GapK1.

Lemma 5.3 (i) The sum of two functions in #PKis in #PK. The sum

and difference of two functions in GapKis in GapK.

(ii) The product of two finite valued functions in #PK(GapK) is in #PK

(GapK).

(iii) [BC04a, Lemma 8] Let ϕ:K∞×{0,1}∞→Zbe a function in GapK

and qbe a polynomial. Define eϕ:K∞→Zby setting for u∈Km

eϕ(u) = X

y∈{0,1}q(m)

ϕ(u, y)

Then eϕbelongs to GapK.

Proof. (i) Let ϕ, ψ ∈#PKand let Rϕ, Rψthe corresponding relations with

associated polynomials p, q (recall Definition 5.1). Then for all u∈Km,

(ϕ+ψ)(u) = {(b, y, z)∈K1+p(m)+q(m)|(b= 0 ∧y= 0 ∧(u, z)∈Rψ)

∨(b= 1 ∧z= 0 ∧(u, y)∈Rϕ)},

1The case of #Pand GapP is treated in [For97].

5.1 Counting Complexity Classes 65

This shows that #PKis closed under taking sums. Moreover, using the

associativity of + and the fact that (−1) ·(b+c) = (−1) ·b+ (−1) ·cfor

b, c ∈b

Z, it is straightforward to verify that GapKis closed under sums and

differences.

(ii) With the notation of (i), the following holds:

(ϕψ)(u) = {(y, z)∈Kp(m)+q(m)|(u, z)∈Rψ∧(u, y)∈Rϕ}.

From this it follows that #PKis closed under products. The statement

for GapKfollows from the distributivity law, which holds for finite valued

functions.

(iii) Assume first that ϕ∈#PKand let Rbe the relation associated to ϕ,

with polynomial p. Then

eϕ(u) = {(y, z)∈ {0,1}q(m)×Kp(m+q(m)) |(u, y, z)∈R}.

The case ϕ∈GapKfollows by applying (i). 2

The rest of this work is concerned mainly with the case K=C. The other

cases that have been studied are K=F2and K=R. The counting class

#P= #PF2was introduced and studied by Leslie Valiant, in his influen-

tial work [Val79a, Val79b], starting the area of counting complexity theory.

The class #P

Rwas introduced by Klaus Meer [Mee00], who also studied its

descriptive complexity theory, and was further explored in [BC04a].

Remark 5.4 Let Kbe any field. A function g:F∞

2→Zin GapP can be

considered as a function K∞→Zby identifying F2with {0,1} ⊆ Kand

letting gvanish outside {0,1}∞. Given functions g∈GapP and ϕ∈GapK,

it is thus possible to interpret the function K∞×F∞

2→Z,(x, y)7→ g(y)ϕ(x)

as a function K∞×{0,1}∞→Zin GapK.

5.1.2 Completeness and Reductions

The concepts of reduction and completeness known for decision problems

naturally extend into the framework of counting problems.

Definition 5.5 Let ϕ, ψ:K∞→b

Z. A function π:K∞→K∞is a parsi-

monious reduction from ϕto ψif πcan be computed in polynomial time

and, for all x∈K∞,ϕ(x) = ψ(π(x)).

Let Cbe a class of functions ϕ:K∞→b

Z. A function ψis hard for Cif

for every ϕ∈ C there is a parsimonious reduction from ϕto ψ. A function

ψis C-complete, if in addition ψ∈ C holds.

The notation ϕψis used to express that there exists a parsimonious

reduction from ϕto ψ. The notions of Turing reduction and completeness are

defined as expected. Thus GapKTuring reduces to #PK, meaning GapK∈

FP#P

K. The following is clear.

66 Counting Complexity Theory

Lemma 5.6 The classes #PKand GapKare closed under parsimonious re-

ductions. This means that if ψ#PK(GapK)and ϕψ, then ϕ∈#PK(GapK).

As expected, the fundamental #P

C-complete problem with respect to

parsimonious reductions is the problem #HNCof counting the number of

solutions of a system of polynomial equations. Completeness also holds if

inequalities are allowed, as in the problem #QASCdefined next.

#QASC(Quasi-algebraic point counting). Given a quasi-algebraic set S⊆

Cncount the number of points in S, returning ∞if this number is not

finite.

Theorem 5.7 ([BC04a]) The problems #HNCand #QASCare #P

C-complete

with respect to parsimonious reductions. The problem ∆HNCis GapC-

complete with respect to parsimonious reductions.

There are algorithms solving #HNCin single exponential time (or even

parallel polynomial time). A key point for showing this is the fact that a

Gr¨obner basis of a zero-dimensional ideal can be computed in single expo-

nential time [DFGS91, Lak91, LL91]. The number of solutions can then be

determined using linear algebra techniques2.

5.2 Generic Parsimonious Reductions

The concept of generic parsimonious reduction, as introduced in [BCL05]

and implicit in [BC04a], allows to make “general position” arguments as

part of a reduction algorithm. A paradigmatic example is that of reducing

the problem of computing the geometric degree of a variety Vto #HNCby

intersecting Vwith a generic linear subspace of complementary dimension.

Of interest are problems where it is possible to compute in polynomial time a

list of candidates for generic parameters, among which the majority is in fact

“generic”. This can be achieved by only requiring the genericity condition

to be describable in terms of the constant free polynomial hierarchy over R.

5.2.1 Generic Quantifiers and Reductions

A useful piece of notation are Koiran’s generic quantifiers3, which are intro-

duced in the following definition.

Definition 5.8 Let F∈FR, with free variables x1,...,xk. Then Fis

Zariski-generically true, written ∀∗aF (a), if the set of values a∈Rknot

satisfying Fhas dimension strictly less than k.

2See for example [CCS99, Chapter 2].

3These were introduced in [Koi97b, Koi99a, Koi99b]. See also [BC04a, Def. 4.2].

5.2 Generic Parsimonious Reductions 67

The same definition applies over C. It is known that the condition

∀∗aF(a) is equivalent to the statement that the set of a∈Rnsatisfying

Fis dense in the Euclidean topology. This can be expressed as

∀∈R∀a∈Rn∃a0∈Rn( > 0⇒F(a0)∧ka−a0k< ),(5.1)

which shows that the formula ∀∗aF (a) is expressible in FR.

In the following, relations R⊆C∞×C∞are considered. It makes sense

to say that such a relation is in PH0

Rby representing points in Cnas points in

R2nin the obvious way. Relations can be treated as predicates rather than

as subsets, and thus the notation R(a) will often be used instead of a∈R.

Given a balanced relation R⊆C∞×C∞, the restriction R∩Cm×C∞is

denoted by Rm.

Definition 5.9 Let ϕ, ψ:C∞→b

Z. A generic parsimonious reduction from

ϕto ψconsists of a pair (π, R), where π:C∞×C∞→C∞is computable in

polynomial time over Cby a constant-free machine, and R⊆C∞×C∞is

a balanced relation (with associated polynomial p) in PH0

Rsuch that for all

m∈Nthe following holds:

(i) ∀u∈Cm∀a∈Cp(m)(R(u, a)⇒ϕ(u) = ψ(π(u, a))),

(ii) ∀u∈Cm∀∗a∈Cp(m)R(u, a).

The notation ϕ∗ψis used to express that there exists a generic par-

simonious reduction from ϕto ψ.

5.2.2 Properties of Generic Reductions

Generic parsimonious reductions share many fundamental properties with

parsimonious reductions. The first such property is transitivity.

Lemma 5.10 The generic parsimonious reduction ∗is transitive.

Proof. Assume that ϕ∗ψvia the reduction given by (π, R) and ψ∗χ

via the reduction given by (ρ, S). Define the function σby σ(u, a, b) :=

ρ(π(u, a), b) and the relation Tby setting T(u, a, b)≡R(u, a)∧S(π(u, a), b).

It remains to be seen that (σ, T) is a generic parsimonious reduction ϕ∗χ.

Let pand qbe the polynomials associated to Rand S, respectively, and

rbe a polynomial such that π(u, a)∈Cr(m)for u∈Cm, a ∈Cp(m). It is

easy to see that Tis a balanced relation in PH0

R. Moreover,

∀u∈Cm∀a∈Cp(m)∀b∈Cq(r(m)) T(u, a, b)⇒ϕ(u) = χ(σ(u, a, b)),

which gives Condition (i) in Definition 5.9. Finally,

∀u∈Cm∀∗a∈Cp(m)R(u, a)∧

∀u∈Cm∀a∈Cp(m)∀∗b∈Cq(r(m)) S(π(u, a), b),

68 Counting Complexity Theory

which implies

∀u∈Cm∀∗a∈Cp(m)∀∗b∈Cq(r(m)) T(u, a, b),

hence Condition (ii) in Definition 5.9 is also satisfied. 2

The following important fact is shown in [BCL05, Theorem 4.4].

Theorem 5.11 Let ϕ, ψ:C∞→b

Z. If ϕ∗ψthen ϕTuring reduces to ψ.

The proof relies on the elimination of generic quantifiers in parameterised

formulas due to Koiran [Koi97b, Koi99a], as well as its extension devel-

oped in [BC04a]. The proof uses the notion of partial witness sequences

from [BC04a].

Definition 5.12 Let Rm⊆R2m×Rkbe a semi-algebraic subset. A partial

witness sequence for Rmis a sequence (α(1),...,α(4m+1)) of points in Rk

such that

∀u∈R2m∀∗a∈RkRm(u, a)=⇒ |{i∈[4m+ 1] |Rm(u, α(i))}| >2m.(5.2)

The next result, Theorem 5.13 below, is a consequence of [BC04a, Theo-

rem 4.9 and Remark 4.10]. Only a rough outline of the proof is given, details

can be found in the above reference.

Theorem 5.13 Let R⊆C∞×C∞be a balanced relation in PH0

R. Then

there is a constant-free machine over C, which computes upon input m∈N

a partial witness sequence αmfor Rm(u, a)in time polynomial in m.

The following lemma from [Koi97a] plays an important role in the proof.

See also [HS82] and [BCSS96] for similar constructions. This lemma is also

needed later on in Section 5.3.

Lemma 5.14 For positive integers k, `, d compute

α1:= 2`, αj:= 1 + α1(d+ 1)j−1αd

j−1for 2≤j≤k

from 1by a straight-line program with O(klog d+ log `)arithmetic opera-

tions. Then h(α1,...,αk)6= 0 for any integer polynomial hin kvariables of

degree at most dand coefficients of absolute value less than 2`.

Proof of Theorem 5.13. (Rough idea.) According to Theorem 4.14, the

formula (5.2) is equivalent to a quantifier free formula Fsatisfying certain

bounds. Moreover, using a transcendence degree argument, it is shown

that Equation (5.2) (and thus F) is satisfied for generic sequences α∈

Rp(m)(4m+1), where pis the polynomial associated to the balanced relation

R. From this it can be deduced that an αsatisfying h(α)6= 0 for all

polynomials happearing in F, also satisfies F. Now Lemma 5.14 can be

invoked in order to obtain such a sequence α∈Rp(m)(4m+1). This αsatisfies

F, and thus Equation (5.2). 2

5.2 Generic Parsimonious Reductions 69

Remark 5.15 The partial witness sequence αmconstructed in the proof of

Theorem 5.13 is a sequence of integers obtained by repeated squaring. Since

the components of αmhave bit-size exponential in m, the computation of

αmis not possible in time polynomial in min the classical setting of Turing

machines. It follows, however, that a system of equations Fm(y, α) with

integer coefficients can be obtained by a Turing machine in time polynomial

in msuch that there exists a unique solution (y, α) of Fm(y, α) with α=αm.

Proof of Theorem 5.11. Let (π, R) be a generic parsimonious reduction

from ϕto ψ. By Theorem 5.13, a partial witness sequence αmfor Rmcan

be computed by a machine over Cin time polynomial in m. Hence the

following algorithm can be implemented by a P-uniform family of circuits

over Cwith oracle for ψ:

input u∈Cm

compute a partial witness sequence (α(1)

m,...,α(4m+1)

m) for Rm

for i= 1 to 4m+ 1 do

compute π(u, α(i)

get Ni:= ψ(π(u, α(i)

m)) by an oracle call to ψ

compute the number Noccurring most among the numbers N1,...,N4m+1

return N.

Condition (ii) of Definition 5.9 states that ∀∗a∈Cp(m)Rm(u, a). Hence,

since αmis a partial witness sequence, Rm(u, α(i)

m) holds for the majority of

the indices i∈[4m+1]. On the other hand, by Condition (i) of Definition 5.9,

Rm(u, α(i)

m)⇒ϕ(u) = ψ(π(u, α(i)

m)).

holds for all i∈[4m+ 1]. Therefore, ϕ(u) = ψ(π(u, α(i))) for the majority

of the indices i∈[4m+ 1] as claimed. 2

5.2.3 Generic Complexity Classes

The closures of #P

Cand GapCwith respect to generic parsimonious reduc-

tions defined below seem to capture more accurately the kind of counting

problems encountered in algebraic and enumerative geometry.

Definition 5.16 (i) The class #P∗

Cis the class of all functions ϕ:C∞→b

such that there exists ψ∈#P

Cwith ϕ∗ψ.

(ii) The class Gap∗

Cconsists of all functions ϕ:C∞→b

Zsuch that there

exists ψ∈GapCwith ϕ∗ψ.

The functions in Gap∗

Ccan also be characterised as the differences of two

functions in #P∗

70 Counting Complexity Theory

Remark 5.17 Let ψbe in #P

C. According to Lemma 5.2, the function

ψ◦πis itself in #P

C. Therefore, without lack of generality the reduction

πcan be assumed to be the identity. This simplification is used in the

proofs throughout this section, and a generic parsimonious reduction is only

specified by the balanced relation R.

Just like GapC(Lemma 5.3), the class Gap∗

Csatisfies some important

algebraic closure properties.

Lemma 5.18 (i) The sum of two functions in #P∗

Cis in #P∗

C. The sum

and difference of two functions in Gap∗

Cis in Gap∗

(ii) The product of two finite valued functions in #P∗

C(Gap∗

C) is in #P∗

(Gap∗

C).

Proof. The proof is just given for the case of addition of functions in #P∗

The other cases are similar. Let ϕ, ψ ∈#P∗

Cand χ1, χ2∈#P∗

Csuch that

ϕ∗χ1and ψ∗χ2with respect to the generic parsimonious reductions

given by relations Rand S, respectively. Let p, q be the polynomials asso-

ciated to Rand S. Then, for all u∈Cm,

∀a∈Cp(m)Rm(u, a)⇒ϕ(u) = χ1(u, a),

∀b∈Cq(m)Sm(u, b)⇒ψ(u) = χ2(u, b).

Moreover, ∀∗a∈Cp(m)Rm(u, a) and ∀∗b∈Cq(m)Sm(u, b). From Lemma 5.3(i),

it can be deduced that the function χdefined by χ(u, a, b) := χ1(u, a) +

χ2(u, b) is in GapC. It follows that for all u∈Cm

∀a∈Cp(m)∀b∈Cq(m)Rm(u, a)∧Sm(u, b)⇒ϕ(u) + ψ(u) = χ(u, a, b).

Moreover, ∀∗a∈Cp(m)∀∗b∈Cq(m)Rm(u, a)∧Sm(u, b). 2

Lemma 5.19 Let ϕ:C∞× {0,1}∞→Zbe a function in Gap∗

C,qbe a

polynomial, and g:F∞

2→Zbe in GapP. Define eϕ:C∞→Zby setting for

u∈Cm

eϕ(u) = X

y∈{0,1}q(m)

g(y)ϕ(u, y).

Then eϕbelongs to Gap∗

C. A similar statement holds for GapC.

Proof. It follows from Lemma 5.18(ii) and Remark 5.4 that the function

C∞× {0,1}∞→Z,(u, y)7→ g(y)ϕ(u, y) is in Gap∗

C, and we may reduce

to the case of a sum eϕ(u) = Py∈{0,1}q(m)ϕ(u, y) with ϕ∈Gap∗

C. Let

ψ∈GapCsuch that ϕ∗ψvia the reduction given by a balanced relation

Rwith associated polynomial p. Then, for all m∈N,

∀u∈Cm∀y∈ {0,1}q(m)∀a∈Cp(m+q(m)) R(u, y, a)⇒ϕ(u, y) = ψ(u, y, a)

5.2 Generic Parsimonious Reductions 71

and ∀u∈Cm∀y∈ {0,1}q(m)∀∗a∈Cp(m+q(m)) R(u, y, a). The above

formula implies

∀u∈Cm∀a∈Cp(m+q(m)) ^

y∈{0,1}q(m)

R(u, y, a)⇒eϕ(u) = e

ψ(u, a),

where the function e

ψis defined by e

ψ(u, a) = Py∈{0,1}q(m)ψ(u, y, a). It is

now easy to see that eϕ∗e

ψ. Moreover, from Lemma 5.3 it follows that the

map

C∞×{0,1}∞×C∞→b

Z,(u, y, a)7→ ψ(u, y, a)

is in GapC.. Since the assertion of the lemma is true for the class GapC, it

follows that e

ψbelongs to GapCand hence eϕ∈Gap∗

C.2

5.2.4 Complexity of Computing the Degree

In [BC04a] the problem of computing the geometric degree of the zero set

Z⊆Cnof given complex polynomials was Turing reduced to HNC. An

analysis of the proof reveals that this reduction is generic parsimonious

except for the computation of the dimension of Z. The following slight

modification of the degree problem, however, is in #P∗

Degree (Geometric degree). Given an algebraic set Z⊆Cnand d∈

Nsuch that dim Z≤d, compute the geometric degree of the d-

dimensional part of Z.

Theorem 5.20 ([BC04a]) The problem Degree is #P∗

C-complete with

respect to parsimonious reductions.

The lower bound is easy. The proof that Degree is in #P∗

Cconsists of

a generic parsimonious reduction to #HNC, by intersecting Ztransversely

with a subspace of codimension d. The key point in the proof is finding a

way to express transversality in PH0

Theorem 5.20 generalises to the case where Zu⊆Cnis a constructible

set depending on a complex parameter vector uand membership of xin Zu

can be decided in polynomial time. (The degree of a constructible set is

defined as the sum of the degrees of its components of maximal dimension.)

Lemma 5.21 Let Rbe a polynomial time decidable relation over C, let p

be a polynomial, and consider for u∈Cnthe constructible set

Zu:= {x∈Cp(n)|(u, x)∈R}.

Then there is a function ϕin #P∗

Csuch that for all u∈C∞, d ∈Nthe

value ϕ(u, d)equals the degree of the d-dimensional part of Zu, provided

dim Zu≤d.

72 Counting Complexity Theory

Proof. The proof follows from Theorem 5.20, using arguments as in Section

4.4.8. The fact that Theorem 5.20 generalises to constructible sets follows

from the proof given in [BC04a], see also [BC04b, Theorem 7.2]. 2

Example 5.22 Let Fbe a matrix with entries in C[X1,...,Xn], k, d ∈N

such that Z:= {x∈Cn|rank F(x)≤k}has dimension at most d. Then, by

Lemma 5.21, the degree of the d-dimensional part of Zcan be computed in

#P∗

C. This follows since the rank condition can be tested in polynomial time

using linear algebra. (However, writing down the rank condition in terms of

non-vanishing of minors would lead to a representation of exponential size.)

5.3 Boolean Parts of Complexity Classes

It is natural and important to consider the discrete versions of problems

regarding polynomial systems. These are the problems arrived at by re-

stricting the input to integer polynomials coded in binary. If L⊆K∞is

a language consisting of first-order formulas, then the discrete version is

regarded as a language in F∞

2and is denoted by LZ. Examples are the prob-

lems HNZ

Cand DimZ

C. The corresponding restrictions of complexity classes

over Kto languages over binary inputs are called Boolean parts.

5.3.1 Boolean Parts of Counting Classes

Determining Boolean parts amounts to characterise, in terms of classical

complexity classes, the power of resource bounded machines over Ror C

when their inputs are restricted to be binary 4.

Definition 5.23 (i) The Boolean part of a class Cof decision problems

over Kis the class BP(C) = {S∩{0,1}∞|S∈ C}.

(ii) The Boolean part BP(C) of a class Cof functions K∞→K∞is the class

of functions {0,1}∞→ {0,1}∞which can be obtained from functions

in the class Cby restricting inputs to {0,1}∞.

(iii) The Boolean part BP(C) of class Cof counting functions K∞→b

Zis

the class of functions {0,1}∞→b

Zwhich can be obtained by restricting

inputs to {0,1}∞.

The constant-free Boolean part of Cis defined as BP0(C) := BP(C0).

Boolean parts can are regarded as classes of languages in F∞

2(or func-

tions defined on F∞

2) by identifying F2with {0,1}, see also Remark 5.4.

In [BC04a], the class of geometric counting complex problems GCC was

defined as the constant-free Boolean part of #PC. This is a class of Boolean

4These have been studied, for example, in [B¨ur00, CG97, CKK+95, CK95, Koi94,

Koi97c].

5.3 Boolean Parts of Complexity Classes 73

counting problems, closed under parsimonious reductions, which can be

located in a small region in the general landscape of Boolean complexity

classes, namely,

#P⊆GCC ⊆FPSPACE.

It is not hard to see (although not completely immediate) that #HNZ

Cis in

GCC. In [BC] it is moreover shown that this problem is complete for GCC.

The class GCC may be alternatively defined as the Boolean part of #PC.

That is, the restriction to constant-free machines is not necessary.

Lemma 5.24 BP(#P

C) = GCC.

Proof. Let ϕ:{0,1}∞→b

Nbe in BP(#P

C). Then there is a balanced

relation R⊆C∞×C∞with associated polynomial p, decidable by a P-

uniform family of circuits {Cn}of polynomial size, such that for all x∈

{0,1}n,ϕ(x) = |{y∈Cp(n)|R(x, y)}|. Without loss of generality [BCSS98,

§7], the machine constants a1,...,ak∈Cin the circuits can be assumed to

be algebraically independent over Qand it can be assumed that the circuits

do not perform divisions.

For x∈ {0,1}nlet gx∈Z[a1,...,ak] be the product of the (non-zero)

test polynomials occurring along the computation path on input xin Cn.

Moreover, define gnto be the product of the gxover all x∈ {0,1}n. It is

easy to see that both the degree and the bit size of the coefficients of gnare

bounded by 2nO(1) .

The following constant-free circuit C0

ndefines ϕon input x∈ {0,1}n:

Compute a test vector α:= (α1,...,αk)∈Znsatisfying gn(α)6= 0 as

described in Lemma 5.14, and then simulate the computation of Cnby re-

placing the constants aiby αi. The resulting circuit has the same branching

behaviour as Cn. The verification that the resulting family of circuits {C0

is P-uniform and that the C0

nhave size polynomially bounded in nfollows

from Lemma 5.14. 2

The next proposition shows the effect of taking Boolean parts on rela-

tivisation.

Proposition 5.25 (i) BP(P#P∗

C) = BP(P#P

C) = PGCC.

(ii) BP(FP#P∗

C) = BP(FP#P

C) = FPGCC.

By Theorem 5.11 it follows that P#P∗

C= P#P

C(and the same for function

classes), so it remains to prove the second equalities in the statement of the

proposition.

The proof needs some preparation. In the following, the polynomial ring

R:= Z[a1,...,ak] in the indeterminates a1,...,akwill serve as a coefficient

ring. For a polynomial f∈R[X1,...,Xn] and α∈Ck, the notation fα∈

74 Counting Complexity Theory

Z[X1,...,Xn] is used for the polynomial obtained from fby specialising the

vector of indeterminates (a1,...,ak) to α.

Lemma 5.26 Let f1,...,frbe polynomials in Z[a1,...,ak, X1,...,Xn]of

total degree at most dand having coefficients of bit size at most `, such that

their zero set over the algebraic closure Kof the quotient field Quot(R)is

finite. Then there is a polynomial h∈Rwith degree and bit size bounded

by (r`dn)O(1) satisfying the following property: For all α∈Cksuch that

h(α)6= 0, the system fα

1= 0,...,fα

r= 0 has the same number of solutions

as the system f1= 0,...,fr= 0.

The following auxiliary result, which follows from [GH93, §3.4.7], is

needed.

Lemma 5.27 Assuming the situation of Lemma 5.26, there exist integers

γ1,...,γnand an irreducible univariate polynomial g∈R[Y]such that

ϕ:ZKn(f1,...,fr)→ ZK(g),(x1,...,xn)7→ γ1x1+···+γnxn

is a bijective map, whose inverse ψis given by y7→ θ−1(r1(y),...,rn(y)) for

some θ∈R\0and r1,...,rn∈R[Y]. The total degree and the bit size of

the ri,g, and θcan be bounded by (r`dn)O(1). (The bit size of γican be

bounded by O(nlog d+ log r).)

Proof of Lemma 5.26. Let h1∈Rdenote the product of θ, the discriminant

of g, and of the leading coefficient of g. We are going to show that there

exists a polynomial h2∈Rof the required size such that if h1(α)h2(α)6= 0,

then the map

ϕα:ZCn(fα

1,...,fα

r)→ ZC(gα),(x1,...,xn)7→ γ1x1+···+γnxn

is bijective and its inverse ψαis given by y7→ (θ(α)−1rα

1(y),...,θ(α)−1rα

n(y)).

This implies the desired assertion since gαis square free and deg g= deg gα.

The polynomials P0:= g(γ1X1+···+γnXn) and Pk:= rk(γ1X1+···+

γnXn)−θXk(1 ≤k≤n) vanish on Z:= ZKn(f1,...,fr). In fact, note that

(P1(x),...,Pn(x)) = θ(ψ(ϕ(x)) −x) for x∈Z. By the effective arithmetic

Nullstellensatz (cf. [KP94, KPS01]), there are representations

ρkPek

k=uk,1f1+···+uk,rfr,0≤k≤n, (5.3)

with positive integers ek, polynomials uk,j over R, and nonzero ρk∈Rsuch

that the degree and the bit size of ρkis bounded by (`dn)O(1). We define

h2:= ρ0···ρnand put h:= h1h2. Then the degree and the bit size of hare

bounded by (r`dn)O(1).

Assume that h(α)6= 0 and x∈ ZCn(f1,...,fr). Specialising ajto αjin

Equation (5.3), we get Pα

k(x) = 0 for all k, since ρk(α)6= 0. In particular,

Pα

0(x) = 0, which implies that the map ϕαis well defined.

5.3 Boolean Parts of Complexity Classes 75

The polynomials Qi:= θdfi(θ−1r1(Y),...,θ−1rn(Y)) and Q0:= γ1r1(Y)+

···+γnrn(Y)−θY vanish on ZK(g). In fact, note that Q0(y) = θ(ϕ(ψ(y))−y)

for y∈ ZK(g). Therefore, the irreducible polynomial gdivides the Qiin

R[Y]. It follows that the map ψαis well defined. Moreover, the maps ϕα

and ψαare inverse to each other. 2

Proof of Proposition 5.25. (i) It is sufficient to show BP(P#P

C)⊆PGCC,

the reverse inclusion is straightforward.

Claim 1. BP(P#P

C)⊆BP0(P#P

C).

Let S⊆ {0,1}∞be a set in BP(P#P

C). Then there exists a P-uniform

family of circuits deciding Sin polynomial time with oracle gates for #HNC.

The elimination of the machine constants can be done as in the proof of

Lemma 5.24. Moreover, Lemma 5.26 ensures that the test sequence α,

which replaces the machine sequence, can be computed so that the oracle

calls to #HNCin the modified family of circuits give the same result as in

the original family.

Claim 2. BP0(P#P

C)⊆PGCC.

Let {Cn}be a constant-free P-uniform family of circuits deciding S⊆

{0,1}∞in polynomial time with oracle gates for #HNC.

At any moment of the computation of Cnwith input x∈ {0,1}n, the

value zof any intermediately computed quantity can be described by a

division-free straight-line program ζwith ninput variables, and length poly-

nomial in n, in the sense that z=ζ(x).

To such a ζwe can associate in polynomial time a system of equations

ϕζ(x, y) in xand new variables y1,...,ymsuch that, for all x∗∈ {0,1}n,

ϕζ(x, y) has a unique solution (x∗, y∗) and y∗

m=ζ(x∗). Therefore, for all

x∈ {0,1}n, the system {ϕζ(x, y), ym= 0}has either one solution or none

at all and

ζ(x) = 0 ⇐⇒ |{y∈Cm|ϕζ(x, y), ym= 0}| = 1.

This construction is used in the following Turing machine deciding S. Given

x∈ {0,1}nas input, simulate the computation of Cnby keeping straight-line

program representations of intermediate results. When reaching a sign node,

if the tested value is z, then query #HNZ

Cwith input {ϕζ(x, y), ym= 0}.

When reaching a query node, then if the input to the query is a system of

equations f1= 0,...,fr= 0 whose coefficients are z1,...,zs, query #HNZ

with input {fy

1= 0,...,fy

r= 0, ϕζ1(x, y(1)),...,ϕζs(x, y(s))}(where fy

ρis

obtained from fρby replacing zjby y(j)

mj,j= 1,...,s). This machine runs in

polynomial time and queries #HNZ

C∈GCC. This shows BP(P#P

C)⊆PGCC.

(ii) The assertion follows by applying part (i) to the components of any

function in BP(FP#P

C). 2

76 Counting Complexity Theory

From Theorem 5.11 it follows that BP(P#P∗

C) = BP(P#P

C). Therefore, as

far as Boolean parts are concerned, the generic class #P∗

Cdoes not introduce

more power than #P

Cwhen considering Turing reductions.

Remark 5.28 Let ϕ, ψ :{0,1}∞→b

Z. It is natural to define a notion

of randomised parsimonious reduction from ϕto ψas a pair (π, R) where

π:{0,1}∞× {0,1}∞→ {0,1}∞is computable in polynomial time by a

Turing machine, and R⊆ {0,1}∞× {0,1}∞is a balanced relation such

that, for all m∈N, the following holds (where p, q are polynomials and pis

associated to R):

(i) ∀u∈ {0,1}m∀a∈ {0,1}p(m)R(u, a)⇒ϕ(u) = ψ(π(u, a)),

(ii) ∀u∈ {0,1}mProb{a∈ {0,1}p(m)| ¬R(u, a)} ≤ 2−q(m).

As in the proof of Proposition 5.25 one may show that for any ϕin BP(#P∗

there exists a randomised parsimonious reduction from ϕto HNZ

C. Recall

from the proof that the intermediate results of the computation are integers

represented by straight-line programs. The point is now that testing those

for zero can be done in coRP [IM83, Sch80, Kal87]. Similarly, for any ϕ

in BP(Gap∗

C) there exists a randomised parsimonious reduction from ϕto

∆HNZ

Chapter 6

Topological Euler Characteristic

The problems considered in this chapter are specified as follows.

EulerC(Euler characteristic of affine varieties). Given a finite set of com-

plex multivariate polynomials, compute the Euler characteristic of its

affine zero set.

ProjEulerC(Euler characteristic of projective varieties). Given a finite

set of complex homogeneous polynomials, compute the Euler charac-

teristic of its projective zero set.

The goal is to show is that these problems are on essentially the same

level of difficulty as the problem of counting the number of solutions to a

polynomial system of equations. Within the framework developed in Chap-

ter 5, the precise statement reads as follows.

Theorem 6.1 The problems EulerCand ProjEulerCare Gap∗

C-complete

for Turing reductions.

In conjunction with Theorem 5.11, this implies that the problems EulerC

and ProjEulerCTuring reduce to the problem #HNCof counting the num-

ber of solutions to a system of polynomial equations. A similar result applies

in the classical Turing machine model of computation, when restricting to

inputs with integer coefficients.

Theorem 6.2 The problems EulerZ

Cand ProjEulerZ

Care FPGCC-complete

with respect to Turing reductions.

The upper bound in Theorem 6.1 is based on a formula due to Paolo

Aluffi [Alu03], expressing the Euler characteristic of a projective hypersur-

face in terms of certain quantities called projective degrees. Furthermore,

Aluffi describes (and implements) an algorithm for computing the Euler

characteristic (and other quantities) using his formula. The main difference

between Aluffis algorithm and the algorithm underlying Theorem 6.1 is in

the computation of the projective degrees. While Aluffis algorithm depends

on the computation of Gr¨obner bases, the algorithm presented here uses

78 Topological Euler Characteristic

transversality arguments in order to obtain a generic parsimonious reduc-

tion to #HNC.

6.1 Projective Degrees and Euler Characteristics

An extension of the notion of degree of a projective variety is the sequence

of projective degrees of a rational morphism [Har95, Lecture 19].

Let f0,...,fn∈C[X0,...,Xn] be homogeneous nonzero polynomials of

the same degree dand let Σ := ZPn(f0,...,fn) denote their projective zero

set. Then these polynomials define a regular morphism

ϕ:U→Pn,(x0:···:xn)7→ (f0(x) : ···:fn(x))

on the domain of definition U:= Pn\Σ, which is open and dense in the

Zariski topology. Thus ϕdefines a rational morphism ϕ:Pn99K Pn. Let

ΓU⊆Pn×Pndenote the graph of ϕand let Γ denote the closure of ΓUin

the Zariski topology. Then Γ = ΓU∪ΓΣ, where ΓΣis the inverse image of

Σ under the projection π1: Γ →Pnonto the first factor. Clearly, dim ΓΣ<

n= dim Γ.

Next, consider Li∈G(n−i, n) and Ln−i∈G(i, n) in the Grassmanni-

ans. Since dim Γ = n, the intersection Γ ∩(Li×Ln−i) is finite for generic

(Li, Ln−i). The natural question arises under which conditions the num-

ber of points in this intersection does not depend on (Li, Ln−i). The next

proposition gives an answer and leads to the concept of projective degrees.

A proof is given at the end of this chapter.

Proposition 6.3 Let ϕ:Pn99K Pnbe a rational morphism defined on U

and let Γbe the closure of the graph of ϕ.

(i) For 0≤i < n there exists a non-negative integer disuch that, if

ΓUt(Li×Ln−i)and ΓΣ∩(Li×Ln−i) = ∅

then

|ΓU∩(Li×Ln−i)|=|Li∩ϕ−1(Ln−i)|=di.

(ii) The above two conditions are satisfied for a generic pair (Li, Ln−i)∈

G(n−i, n)×G(i, n).

Definition 6.4 The integers d0,...,dn−1are called the projective degrees

of the rational morphism ϕ(compare [Har95, Chapter 19]).

Example 6.5 Let f0=X1X2,f1=X0X2,f2=X0X1in the case n= 2.

Then Σ = Z(f0, f1, f2) = {(1 : 0 : 0),(0 : 1 : 0),(0 : 0 : 1)}. It is easy to see

6.1 Projective Degrees and Euler Characteristics 79

that d1= 2, and the claim is that d0= 1. Indeed, a point L2is given by

L2=ZP2(a0Y0+a1Y1+a2Y2, b0Y0+b1Y1+b2Y2) and

ϕ−1(L2) = Z(a0/X0+a1/X1+a2/X2, b0/X0+b1/X1+b2/X2, X0X1X26= 0)

consists of exactly one point in P2for generic coefficients ai, bi.

In general, if the image of ϕ:Pn99K Pnis dense, then d0is the cardinality

of the generic fibre of ϕ.

The following proposition is stated in order to illustrate the notion of

projective degrees, and is not used elsewhere.

Proposition 6.6 Let f0,...,fn∈C[X0,...,Xn]be homogeneous nonzero

polynomials of the same degree dand let rbe the codimension of Σ :=

Z(f0,...,fn)in Pn. Then the projective degrees diof the corresponding

rational map ϕsatisfy dn−i=difor 1≤i < r and dn−r=dr−deg(Σ).

Proof. For generic Lr,ϕ−1(Lr) = Z(g1,...,gr)\Σ, where g1,...,grform a

generic linear combination of f0,...,fn. It is known [Mat86] that (g1,...,gr)

is a regular sequence. Let C1,...,Csbe the irreducible components of V:=

ZPn(g1,...,gr). Then all Cjhave codimension rand we have deg V=

j=1 deg Cj=dr. Suppose that C1,...,Ckare the irreducible components

of Vthat are contained in Σ. Then these are the irreducible components

of Σ of maximal dimension and hence deg Σ = Pk

j=1 deg Cj. Therefore, for

generic Ln−r,

dn−r=|Ln−r∩ϕ−1(Lr)|=|Ln−r∩(V\Σ)|=

j=k+1

deg Cj=dr−deg Σ.

The proof that dn−i=difor i < r is similar. 2

Let V=Z(f)⊆Pnbe a smooth, irreducible hypersurface. Then the

formula

χ(V) = 1

d((1 −d)n+1 −1) + n+ 1.(6.1)

expresses the Euler characteristic in terms of the degree dof V[Dim92, §5].

Example 6.7 (i) Pn=Z(X0)⊂Pn+1 implies χ(Pn) = n+ 1.

(ii) For a smooth planar curve V⊂P2of degree d, Equation (6.1) implies

the well-known formula χ(V) = 1

d((1 −d)3−1) + 3 = d(3 −d) =

2(1 −ga(V)), where ga(V) is the arithmetic genus of V.

A generalisation of Equation (6.1) to the case of possibly singular hy-

persurfaces follows from a formula of Aluffi [Alu03] for Chern-Schwartz-

MacPherson classes for arbitrary hypersurfaces. The statement below fol-

lows from Theorem 2.1 and the remark at the end of §2.6 in [Alu03].

80 Topological Euler Characteristic

Theorem 6.8 (Aluffi [Alu03]) Let f∈C[X0,...,Xn]be homogeneous

and non-constant. The Euler characteristic of the projective hypersurface

V=Z(f)is given by

χ(V) = n+

i=1

(−1)i−1dn−i,

where d0,...,dn−1are the projective degrees of the gradient morphism

Pn\Σ→Pn, x = (x0:···:xn)7→ ∂

∂X0

f(x): ··· :∂

∂Xn

f(x)

and Σ := Z(∂

∂X0f, . . . , ∂

∂Xnf).

Example 6.9 (i) Let f=Qs

i=1(αiX0+βiX1)ei. Then Z(f)⊆P1con-

sists of exactly spoints. Theorem 6.8 says χ(Z(f)) = 1 + d0. On the

other hand, a straight-forward calculation shows that indeed d0=s−1.

(This example illustrates that Theorem 6.8 works for reducible f.)

(ii) Proposition 6.6 implies that dn−i= (d−1)ifor 1 ≤i < codimPnΣ. In

the special case of a smooth irreducible hypersurface we have Σ = ∅

and therefore dn−i= (d−1)ifor 1 ≤i≤n. Plugging this into the

formula in Theorem 6.8, Equation (6.1) follows.

(iii) Consider f=X0X1X2with zero set V⊆P2. Note that Vis a singular

hypersurface. Example 6.5 shows that d0= 1, d1= 2. Theorem 6.8

therefore gives χ(V) = 2 + d1−d0= 3. This can be easily verified

using the principle of inclusion and exclusion: Set Vi:= Z(Xi)≃P1.

Then, for i < j, each Vi∩Vjconsists of one point only and

χ(V) =χ(V0) + χ(V1) + χ(V2)

−χ(V0∩V1)−χ(V0∩V2)−χ(V1∩V2) = 3.

(iv) The last example can be generalised by considering the zero set V⊂Pn

of f=X0X1···Xn. Note that the hypersurface Vis highly singular.

Its singular locus Σ = ∪i<jZPn(Xi, Xj) is a subspace arrangement

with an interesting combinatorial structure. The projective degrees

of Vthus contain information about Σ which does not follow from

deg V. It is an instructive exercise to prove that di=n

ifor 0 ≤

i < n and to check the formula in Theorem 6.8. To compute χ(V),

note that C∗:= C\ {0}is homotopy equivalent to the circle S1and

(C∗)n→Pn\V, (x1,...,xn)7→ (1: x1:···:xn) is an isomorphism,

hence χ(V) = χ(Pn)−χ(C∗)n=n+ 1 since χ(S1) = 0.

6.2 Computing Projective Degrees 81

6.2 Computing Projective Degrees

In this section, the complexity of the problems EulerCand ProjEulerC

is determined. To do so, the following auxiliary problems are considered:

ProjDegreeC(Projective degrees). Given a set of homogeneous poly-

nomials f0,...,fnin C[X0,...,Xn] of the same degree and i∈N,

0≤i < n, compute the ith projective degree diof the rational mor-

phism ϕ:Pn99K Pndefined by them.

#QProjC(Counting points in quasi-projective sets). Given a quasi-projective

set S⊆Pn, count the number of points in S, returning ∞if this num-

ber is not finite.

#BiQProjC(Counting points in bi-projective quasi-algebraic sets). Given

a quasi-algebraic set S⊆Pn×Pn, count the number of points in S,

returning ∞if this number is not finite.

The main results of this section are that ProjDegreeCis in #P∗

Cand

that EulerCand ProjEulerCare Gap∗

C-complete with respect to Turing

reductions. To prove them, the following auxiliary result is needed.

Lemma 6.10 The problems #QProjCand #BiQProjCare in #P

Proof. The projective space Pncan be partitioned as Pn=Fn

i=0 Ei, where

Ei={x∈Pn|x0=...=xi−1= 0, xi6= 0} ≃ Cn−i.

Let ϕ(x0,...,xn) be the system of homogeneous polynomials describing the

set S⊆Pn. The above partition of Pnthen induces a partition of Sas a

disjoint union of the quasi-algebraic subsets of Cn+1 defined by the systems

ϕi:= ϕ(0,...,0,1, xi+1,...,xn) of (non-homogeneous) polynomials. It fol-

lows that the number of points of Sis equal to the number of points of the

quasi-algebraic subset of Cn+1 described by Wn

i=0 ϕi. This reduces #QProjC

to #QASC(see Chapter 5) and thus shows that #QProjC∈#P

C. The

proof for #BiQProjCis similar. 2

Proposition 6.11 The problem ProjDegreeCis in #P∗

The proof consists of finding a generic parsimonious reduction (π, R)

from ProjDegreeCto #BiQProjC. The proof is based on the technical

Lemma 6.12 stated below, whose proof is deferred to §6.4. In order to state

this lemma, some notation is needed.

Let u∈Cmbe a vector parameterising the homogeneous polynomials

f0,...,fnand let Γu= Γu

U∪Γu

Σ⊆Pn×Pnbe the closure of the graph

associated to f0,...,fnas described in §6.1. Also, to a point a∈Ci(n+1)

82 Topological Euler Characteristic

(seen as a matrix with irows and n+ 1 columns), we associate the linear

space Li

adefined by ax = 0. Note that, for generic a, dim Li

a=n+1−i, i.e.,

La∈G(n−i, n). So, Li

ais written for an element in G(n−i, n) parameterised

by a, even though for a thin subset of Ci(n+1), one has Li

a6∈ G(n−i, n).

Similarly for b∈C(n−i)(n+1) and Ln−i

Define the following transversality relation for m∈Nand 0 ≤i < n:

transm,n,i :=

n(u, a, b)∈Cm+n(n+1) |Γu

Σ∩(Li

a×Ln−i

b) = ∅ ∧ Γu

Ut(Li

a×Ln−i

b)o

and write trans := Sm,n,i transm,n,i.

Lemma 6.12 The relation trans is in PH0

The proof of this lemma is postponed to Section 6.4. With the help of

this Lemma, the proof of Proposition 6.11 can be given.

Proof of Proposition 6.11. We construct a generic parsimonious reduc-

tion (π, R) from ProjDegreeCto #BiQProjC. Let 0 ≤i < n, let

f0,...,fn∈C[X0,...,Xn] be homogeneous given by a parameter u∈Cm,

and let (Li

a, Ln−i

b) be given by a parameter (a, b)∈Cn(n+1). The following

formula expresses that (p, q)∈Li

a×Ln−i

membL(p, q, a, b) :=

k=1 n

j=0

ak,jpj= 0∧

n−i

`=1 n

j=0

b`,jqj= 0.

Let Fr,s := Yrfs(X0,...,Xn)−Ysfr(X0,...,Xn), in the variables X0,...,Xn

and Y0,...,Yn. Then (p, q)∈Γu

Ucan be described by the following formula:

membU(p, q, u) := ^

0≤r<s≤n

(Fr,s(p, q) = 0) ∧

r=0

(fr(p)6= 0).(6.2)

It follows that a description of the set Γu

U∩(Li

a×Ln−i

b) can be computed

in polynomial time from i, a, b and f0,...,fnby a constant-free machine.

Define πas the function mapping (u, a, b) to the above description of the set

Γu

U∩(Li

a×Ln−i

b) and let R:= trans be the above defined relation, which,

according to Lemma 6.12, is in PH0

Part (i) of Proposition 6.3 shows that the number of points in π(u, (a, b))

is the ith projective degree of (f0,...,fn), provided R(u, a, b) holds. Part (ii)

of Proposition 6.3 says that ∀u∈Cm∀∗(a, b)∈Cn(n+1) R(u, a, b). There-

fore, (π, R) is a generic parsimonious reduction from ProjDegreeCto

#BiQProjCand the statement follows from Lemma 6.10. 2

6.3 Complexity of the Euler Characteristic 83

6.3 The Complexity of Computing the Euler Characteristic

In this section, Theorem 6.1, which states that EulerCand ProjEulerC

are Gap∗

C-complete for Turing reductions, is proven. The next lemma gives

the upper bounds in Theorem 6.1. To state it, the following auxiliary prob-

lem is defined:

PHSEulerC(Euler characteristic of projective hypersurfaces). Given a

non-constant complex homogeneous polynomial, compute the Euler

characteristic of its projective zero set.

Proposition 6.13 (i) PHSEulerC∈Gap∗

(ii) ProjEulerC∈Gap∗

(iii) EulerC∈Gap∗

Proof. (i) Let f∈C[X0,...,Xn] be an instance of PHSEulerC, that is, a

non-constant homogeneous polynomial. Put d:= deg fand let V⊂Pnde-

note the projective zero set of f. Let d0,...,dn−1be the projective degrees of

the rational map Pn99K Pndefined by the gradient (∂f/∂X0, . . . , ∂f/∂Xn)

of f. Theorem 6.8 states that

χ(V) =

i=1 (−1)i−1dn−i+ 1.

Now consider the function

ϕ:C∞×{0,1}∞→V, (V, i)7→ (−1)i−1dn−i+ 1 if 0 ≤i < n

0 otherwise.

where i∈Nis identified with its binary encoding. By Proposition 6.11,

the problem ProjDegreeCbelongs to #P∗

C. Using Lemma 5.18, it follows

that ϕ∈Gap∗

C. Using Lemma 5.19, it follows that PHSEulerCbelongs to

Gap∗

(ii) Let f1,...,fr∈C[X0,...,Xn] be an instance of ProjEulerC.

For an index set I⊆[r] write VIfor the projective zero set of the product

fI:= Qi∈Ifi. Lemma 4.5 implies that χ(ZPn(f1,...,fr)) = χ+(f1,...,fr)−

χ−(f1,...,fr), where

χ+:= X

|I|odd

χ(VI), χ−:= X

|I|>0 even

χ(VI).

By part (i), PHSEulerCbelongs to Gap∗

C. Therefore, Lemma 5.19 implies

that both functions χ+and χ−belong to Gap∗

Cas well. This proves that

ProjEulerCbelongs to Gap∗

84 Topological Euler Characteristic

(iii) Let f1,...,fr∈C[X1,...,Xn] be an instance of EulerCand dbe

an upper bound on the degrees of these polynomials. Define the homoge-

neous polynomials Fiof degree d+ 1 by Fi:= Xd+1

0fi(X1/X0,...,Xn/X0)

and put V:= ZPn(F1,...,Fr) and U:= V∩ {X06= 0}. The set Uis

homeomorphic to the affine zero set ZCn(f1,...,fr). Moreover, by con-

struction, we have V−U=ZPn(X0)) ≃Pn−1. Proposition 4.4 implies that

χ(U) = χ(V)−χ(Pn−1) = χ(V)−n. The assertion (iii) therefore follows

from (ii). 2

The next lemma gives the lower bounds in Theorem 6.1.

Lemma 6.14 Both problems EulerCand ProjEulerCare #P

C-hard for

Turing reductions.

Proof. In the proof of part (iii) of Proposition 6.13, a Turing reduction

from EulerCto ProjEulerCwas given. To prove the hardness, a Turing

reduction from Degree to EulerCis established.

An instance f1,...,fr∈C[X1,...,Xn] of Degree is parametrised by

its coefficient vector u. Let Zu⊆Cndenote the affine zero set of these

polynomials. Let a∈Cn(n+1) parameterise in the usual way a sequence of

affine subspaces A0, A1,...,Anof Cnsuch that dim Ai=i. Note that if

Zuis nonempty of codimension k, then for generic a, we have Ai∩Zu=∅

for i < k,Ak∩Zu6=∅,AktZu, and χ(Ak∩Zu) = |Ak∩Zu|= deg Zu.

Consider the set

Rm,n := n(u, a)∈Cm+n(n+1) |

(Zu=∅)∨

k=0 ^

i<k Ai∩Zu=∅∧Ak∩Zu6=∅∧AktZuo.

(6.3)

According to [BC04a, Lemma 5.9], the set R:= Sm,n Rm,n is expressible in

PH0

R. Moreover, for fixed u∈Cm, we have ∀∗a∈Cn(n+1) Rm,n(u, a).

Define now δ(u, a) to be the first nonzero element of the sequence

(χ(Zu∩A0),...,χ(Zu∩An)),

if this is not the zero sequence; otherwise we put δ(u, a) := 0. Note that

δ(u, a) can be computed by a polynomial time machine making oracle calls

to EulerC. By the previous reasonings we have that, for all u, a,

R(u, a) holds ⇒δ(u, a) = deg Zu.

As in the proof of Theorem 5.11, it can be shown that the following algorithm

computes the degree of Zu.

6.4 Expressing Transversality 85

input u∈Cm

compute partial witness sequence αm= (α(1)

m,...,α(4m+1)

m) for Rm,n(u, a)

for i= 1 to 4m+ 1 do

compute Ni:= δ(u, α(i)

m) by making oracle calls to EulerC

compute the majority Nof the numbers N1,...,N4m+1

return N

The algorithm can be implemented as a polynomial time BSS machine over

Cmaking oracle calls to EulerC.2

6.4 Expressing Transversality

This section is dedicated to the proof of Lemma 6.12. For an irreducible

variety V⊆Pn×Pngiven as the zero set of bihomogeneous polynomials

f1,...,fr, write b

Vfor the zero set of these polynomials in Cn+1 ×Cn+1.

Let (p, q)∈Vand bp, bq∈Cn+1 be affine representatives of p, q, respectively.

From the homogeneity of the defining equations it follows that the tangent

space of b

Vat (bp, bq) does not depend on the particular bp, bqchosen, and may

therefore be written T(p,q)b

Consider the canonical map π:b

V\{0} → V. At a point (p, q)∈V,π

induces a surjective map d(p,q)π:T(p,q)b

V→T(p,q)Vof the tangent spaces

with kernel p×q, which allows to identify the tangent space T(p,q)Vwith

T(p,q)b

V /(p×q) in a natural way. Here p×qis the product of pand qas

one-dimensional subspaces of Cn+1.

For a projective linear subspace L⊆Pnwrite b

Lfor the corresponding

linear subspace of Cn+1.

Lemma 6.15 Let ΓUbe the graph of a rational morphism ϕ:Pn99K Pn

defined by polynomials f0,...,fnof the same degree. Let 0≤i < n,

(Li, Ln−i)∈G(n−i, n)×G(i, n), and (p, q)∈ΓU∩(Li×Ln−i). Then

ΓUt(p,q)(Li×Ln−i)if and only if

T(p,q)b

ΓU∩(b

Li×b

Ln−i) = p×q.

Proof. Since the spaces ΓUand Li×Ln−ihave complementary dimension

in Pn×Pn, we have ΓUt(p,q)(Li×Ln−i) if and only if

T(p,q)ΓU∩T(p,q)(Li×Ln−i) = 0.

This is equivalent to T(p,q)b

ΓU/(p×q)∩(b

Li×b

Ln−i)/(p×q) = 0, which shows

the assertion. 2

86 Topological Euler Characteristic

Proof of Lemma 6.12. Denote by Cn+1

∗the set Cn+1 \{0}and write ΓU:=

Γu

U. By Lemma 6.15, ΓUt(Li

a×Ln−i

b) if and only if

∀p, q ∈Cn+1

∗(p, q)∈b

ΓU∩(b

a×b

Ln−i

b)⇒T(p,q)b

ΓU∩(b

a×b

Ln−i

b) = p×q

∧dim Li

a=n−i∧dim Ln−i

b=i.

The condition (p, q)∈b

ΓU∩(b

a×b

Ln−i

b) is expressed by the formula

membU(p, q, u)∧membL(p, q, a, b) (see the proof of Proposition 6.11) and

can thus be checked in polynomial time. Also, the last two statements con-

cerning dimension can be checked in polynomial time.

Let (p, q)∈b

ΓUand ξ, η ∈Cn+1. Since locally at (p, q) the vanishing

ideal of b

ΓUis given by the polynomials Fr,s(X, Y ) (cf. (6.2)), we have (ξ, η)∈

T(p,q)b

ΓUif and only if

0≤r<s≤nn

j=0

ξj

∂Fr,s

∂Xj

(p, q) +

k=0

ηk

∂Fr,s

∂Yk

(p, q) = 0.

More explicitly, this can be expressed by the following formula membT(ξ, η, p, q, u):

0≤r<s≤nηrfs(p)−ηsfr(p) +

j=0 ξjqr

∂fs

∂Xj

(p)−ξjqs

∂fr

∂Xj

(p)= 0.

Hence, T(p,q)b

ΓU∩(b

a×b

Ln−i

b) = p×qcan be expressed as follows:

∀ξ, η ∈Cn+1 (ξ, η)∈p×q⇐⇒ membT(ξ, η, p, q, u)∧membL(ξ, η, a, b).

This is a coNP0

C-statement, in particular, it is expressible in PH0

We next deal with the property Γu

Σ∩(Li

a×Ln−i

b) = ∅. This property is

equivalent to Γ ∩(Li

a×Ln−i

b)⊆ΓU, which means that

∀p, q ∈Cn+1

∗(p, q)∈ΓU∩(Li

a×Ln−i

b)⇒(p, q)∈ΓU,(6.4)

since Γ is the Zariski closure of ΓU. To express this condition we use the

fact [Mum76] that Γ is also the closure of ΓUwith respect to the Euclidean

topology. This topology can be defined by a metric in projective space as

follows. Define, for p, q ∈Cn+1

∗,

dPn(p, q) = arccos(|hp, qi|/(kpk·kqk)),

which is the angle between the vectors pand q. It is straightforward to check

that this is well defined when considering pand qas elements in Pn, that

the usual properties of a metric are satisfied, and that the metric induced

on the affine charts is equivalent to the Euclidean metric.

We note that “dPn(p, q)< ε for sufficiently small ε > 0” is equivalent to

“|hp, qi|/(kpk·kqk)≥1−δfor sufficiently small δ” and thus can be expressed

6.5 Proof of Proposition 6.3 87

by a first order formula over R. (It is not clear how to express condition (6.4)

by a formula over C.)

Condition (6.4) can now be expressed in PH0

Ras follows:

∀p, q ∈Cn+1

∗∀ε > 0∃p0, q0∈Cn+1

∗membU(p0, q0, u)∧membL(p, q, a, b)

∧dPn(p, p0)< ε ∧dPn(q, q0)< ε ⇒membU(p, q, u).

The completes the proof. 2

6.5 Proof of Proposition 6.3

The goal is to give a proof of Proposition 6.3. This section begins with a

definition of the concepts of regular points and regular values, tailored to

the situation of not necessarily smooth varieties.

Definition 6.16 Let ϕ:X→Ybe a surjective morphism of irreducible

complex projective varieties of the same dimension. A point p∈Xis called

aregular point of ϕif pis a smooth point of Xand dpϕ:TpX→Tϕ(p)Yis

an isomorphism (and hence ϕ(p) is smooth in Y). A point q∈Yis called a

regular value of ϕif all p∈ϕ−1(q) are regular points of ϕ.

Lemma 6.17 Let ϕ:X→Ybe a surjective morphism of irreducible com-

plex projective varieties of the same dimension. Then all fibres of regular

values of ϕhave the same finite cardinality.

Proof. In [Mum76, Cor. 4.16] it is proved that any nonempty Zariski open

subset of an irreducible complex projective variety is connected in the Eu-

clidean topology. Sard’s lemma [Mum76, 3.7] implies that the set Rof

regular values of ϕis a nonempty Zariski open subset of Y. Therefore, Ris

connected. It is thus sufficient to prove that the function ψ:R→N, y 7→

|ϕ−1(y)|is well defined and locally constant.

Let y∈R. The inverse function theorem implies that ϕ−1(y) is dis-

crete. Since it is also compact, it must be finite. So, ψis well defined.

Let ϕ−1(y) = {x1,...,xk}. By the inverse function theorem there exists an

open neighbourhood Ω ⊆Yof yand pairwise disjoint open neighbourhoods

V1,...,Vkof x1,...,xk, respectively, such that ϕ−1(Ω) = V1∪···∪Vkand

ϕ|Vj:Vj→Ω is an isomorphism for all i. Since |ϕ−1(y0)|=kfor all y0∈Ω,

it follows that ψis locally constant. 2

Recall that the Grassmannian G(k, n) is an irreducible smooth projective

variety of dimension dim G(k, n) = (k+ 1)(n−k), see Chapter 4.

Lemma 6.18 Let Γ⊆Pn×Pnbe an irreducible projective variety of di-

mension nand 0≤i≤n. Define the closed subvariety

Φ := {(p, q, Li, Ln−i)|(p, q)∈Γ∩(Li×Ln−i)} ⊆ Γ×G(n−i, n)×G(i, n)

88 Topological Euler Characteristic

and let π2: Φ →G(n−i, n)×G(i, n)be the projection on the second factor.

(i) The incidence relation Φis an irreducible projective variety of dimen-

sion dim Φ = dim(G(n−i, n)×G(i, n)) = 2i(n−i) + n.

(ii) Let (p, q)be a smooth point of Γand (Li, Ln−i)∈G(n−i, n)×G(i, n).

Then Γt(p,q)(Li×Ln−i)holds if and only if (p, q, Li, Ln−i)is a regular

point of the projection π2.

Proof. (i) Consider the projection π1: Φ →Γ onto the first factor. For any

(p, q)∈Γ, there is the following isomorphism of varieties

π−1

1(p, q)≃ {Li∈G(n−i, n)|p∈Li}×{Ln−i∈G(i, n)|q∈Ln−i}

≃G(n−i−1, n −1) ×G(i−1, n −1).

This is an irreducible variety of dimension dim π−1

1(p, q) = 2i(n−i) (we use

the convention G(−1, m) := ∅). Using [Har95, Theorem 11.14], it follows

that Φ is irreducible and

dim Φ = dim Γ + dim π−1(p, q) = n+ 2i(n−i) = dim(G(n−i, n)×G(i, n)).

(ii) Assume without loss of generality that p=q= (1: 0: ···: 0), Li=

Z(Xn−i+1,...,Xn), and Ln−i=Z(Yi+1,...,Yn). Moreover, since the asser-

tion is local, we may work with the affine neighbourhoods {X06= 0} ≃ Cn

and {Y06= 0} ≃ Cnof pand qin Pn, respectively. Let e

Γ⊆Cn×Cnbe the

subvariety thus corresponding to Γ.

For a matrix a∈Ci×(n+1−i)let Li

a⊆Cnbe the zero set of the affine

polynomials

g1:= a1,0+a1,1X1+···+a1,n−iXn−i−Xn−i+1,

gi:= ai,0+ai,1X1+···+ai,n−iXn−i−Xn.

(Note that this notation Li

aslightly differs from the one used in §6.2.) It is

well known that [Har95, Lecture 6]

Ci×(n+1−i)→G(n−i, n), a 7→ Li

gives local isomorphisms of sufficiently small neighbourhoods of 0 to neigh-

bourhoods of Li=Li

0in G(n−i, n). An analogous statement holds for

C(n−i)×(i+1) →G(i, n), b 7→ Ln−i

where the affine space Ln−i

bis defined as the zero set of the affine polynomials

gi+1 := b1,0+b1,1Y1+···+b1,iYi−Yi+1,

gn:= bn−i,0+bn−i,1Y1+···+bn−i,iYi−Yn.

6.5 Proof of Proposition 6.3 89

This induces the following local isomorphism ϕaround the origin:

ϕ:Cn×Cn×Ci×(n+1−i)×C(n−i)×(i+1) →Pn×Pn×G(n−i, n)×G(i, n),

(x, y, a, b)7→ ((1: x1:···:xn),(1: y1:···:yn), Ln−i

a, Li

b).

Assume now that (p, q) is a smooth point of Γ. Let f1,...,fnbe poly-

nomials in X1,...,Xn, Y1,...,Ynhaving the zero set e

Γ⊆Cn×Cnlocally

around (0,0) such that the differentials df1,...,dfnat (0,0) are linearly in-

dependent (this is possible, see [Mum76]). Let e

Φ denote the zero set of

f1,...,fn, g1,...,gnin Cn×Cn×Ci×(n+1−i)×C(n−i)×(i+1). Then the map

ϕgives a local isomorphism of e

Φ to Φ around the origin.

The differentials of the giat the origin satisfy

d0g1=d0a1,0−d0Xn−i+1,...,d0gi=d0ai,0−d0Xn,

d0gi+1 =d0b1,0−d0Yi+1,...,d0gn=d0bn−i,0−d0Yn.

Clearly, these differentials are linearly independent of d0f1,...,d0fn. There-

fore, the tangent space of e

Φ at 0 is the zero set of d0f1,...,d0fn, d0g1,...,d0gn.

In particular, dim T0e

Φ = dim e

Φ and hence 0 is a smooth point of e

Φ.

Let eπ2:e

Φ→Ci×(n+1−i)×C(n−i)×(i+1) denote the projection onto the

second factor. Then the above description of the differentials shows that the

kernel of

d0eπ2:T0e

Φ→Ci×(n+1−i)×C(n−i)×(i+1),(ξ, η, α, β)7→ (α, β)

is isomorphic to T(0,0) e

Γ∩(Li

0×Ln−i

0). Hence 0 is a regular point of eπ2if

and only if e

Γ and Li

0×Ln−i

0intersect transversally at 0, which was to be

shown. 2

Proof of Proposition 6.3. Let Γ ⊆Pn×Pnbe the closure of the graph of

a rational map ϕ:Pn99K Pn. Fix 0 ≤i < n and consider the incidence

relation

Φ := {(p, q, Li, Ln−i)|(p, q)∈Γ∩(Li×Ln−i)} ⊆ Γ×G(n−i, n)×G(i, n)

introduced in Lemma 6.18. Then the projection π2: Φ →G(n−i, n)×G(i, n)

satisfies all the assumptions of Lemma 6.17. Hence there is an integer di

such that all fibres of π2at regular values (Li, Ln−i) have cardinality di.

(i) If ΓUt(Li×Ln−i) and ΓΣ∩(Li×Ln−i) = ∅, then all (p, q)∈

π−1

2(Li, Ln−i) are in ΓUand thus smooth points of Γ. Hence (p, q, Li, Ln−i)

is a regular value of π2by Lemma 6.18. Therefore,

di=|π−1

2(Li, Ln−i)|=|ΓU∩(Li×Ln−i)|

which shows claim (i).

90 Topological Euler Characteristic

For part (ii), note first that the property ΓΣ∩(Li×Ln−i) = ∅holds for

generic (Li, Ln−i) since dim ΓΣ< n. Moreover, if ΓΣ∩(Li×Ln−i) = ∅holds,

then Lemma 6.18 implies that ΓUt(Li×Ln−i) if and only if (Li, Ln−i) is a

regular value of π2. Hence the claim (ii) follows from Sard’s lemma [Mum76,

3.7]. 2

Chapter 7

Hilbert Polynomial

In its most general form, the problem of computing the Hilbert polynomial

can be specified as follows.

Hilbert (Hilbert polynomial). Given a family of non-constant homoge-

neous polynomials f1,...,frin C[X0,...,Xn] and 0 ≤k≤n, com-

pute the k-th coefficient of the Hilbert polynomial of the homogeneous

ideal generated by f1,...,fr.

It can be shown that the problem of computing the Hilbert polynomial

is FPSPACE-hard, see Section 7.4.2. A consequence of this is an FPSPACE-

lower bound for the problem of computing the rank of cohomology groups of

coherent sheaves on projective space as well as for the problem of computing

the corresponding Euler characteristic (Corollary 7.22), which improves the

#P-lower bound in Bach [Bac99].

The main theme of this chapter, however, is the study of the restricted

problem of computing the Hilbert polynomial of a smooth equidimensional

complex projective variety V⊆Pnwithin the framework of counting com-

plexity theory, as developed in Chapter 5. More precisely, it is shown that

this problem, called Hilbertsm for the moment (the exact specification is

given below), is in Gap∗

Cby means of a generic parsimonious reduction to

the problem #HNC. In particular, in the Turing model an FPSPACE-upper

bound for the discrete version HilbertZ

sm is obtained.

7.1 Problem Specification and Statement of Results

When trying to formally define the problem under consideration, the ques-

tion arises whether the smoothness condition can be tested at all within

reasonable resources. The obvious idea of checking the Jacobian criterion at

all points in the variety V(which is possible in coNPC) will fail if the given

polynomials f1,...,frdescribing the variety Vdo not generate a radical

ideal and thus differ from the vanishing ideal I(V) of V. Indeed, it is not

known whether a set of generators of I(V) can be computed from f1,...,fr

in parallel polynomial time or even weaker, in single exponential time.

92 Hilbert Polynomial

To overcome these difficulties, an input specification is given which, on

the one hand, can be checked in coNPC, and on the other hand guarantees

that the highest dimensional part of the variety is smooth. The goal is then

to compute the Hilbert polynomial of the highest dimensional part.

Given homogeneous polynomials f1,...,frin C[X0, . . . , Xn] and m∈N,

the following condition will be referred to as the input condition:

∀x∈ Z(f1,...,fr)−{0}

dim{z∈Cn+1 |dxf1(z) = 0,...,dxfr(z) = 0} ≤ m+ 1.(7.1)

This input condition (7.1) can be tested in coNPC.

Lemma 7.1 Assume V0=Z(f1,...,fr)satisfies the input condition (7.1)

for some m∈N. Then V0=V∪Wis a disjoint union of a smooth variety

V⊆Pnof pure dimension m(possibly empty) and a subvariety W⊆Pn

with dim W < m.

Proof. For all x∈V0,TxV0⊆P(∩r

i=1 ker dxfi) holds, where TxV0is the

projective tangent space of V0at x. The input condition implies that for all

x∈V0, dimxV0≤dim TxV0≤mis satisfied. Therefore, all points x∈V0

of local dimension mare smooth. The claim follows since there is exactly

one irreducible component passing through a smooth point. 2

In particular, from the input condition it follows that the irreducible

components of the m-dimensional part Vof V0are pairwise disjoint and a

point x∈V0is in Vif and only if dimxV0=m. Moreover, n−m≤rand

for all x∈Vthe Jacobian matrix ( ∂fs

∂Xi(x)) has rank n−m.

The formal specification of Hilbertsm can now be given. In order to

make sure that the output is an integer, a certain multiple of the k-th coef-

ficient of the Hilbert polynomial is computed.

Hilbertsm (Hilbert polynomial of smooth equidimensional varieties). Given

integers 0 ≤k≤m≤nand a family f1,...,frof homogeneous poly-

nomials in C[X0,...,Xn] satisfying the input condition for m, com-

pute the integer multiple N(k, m)pk(V) of the k-th coefficient pk(V)

of the Hilbert polynomial of the m-dimensional part Vof V0, where

N(k, m) := [(m−k+ 1)! ···2!1!]2.

Here is the main result of this chapter.

Theorem 7.2 The problem Hilbertsm is in Gap∗

C. In particular, the prob-

lem Hilbertsm Turing reduces (over C) to HNC.

This theorem immediately implies the following corollary, cf. Section 5.3.

Corollary 7.3 The problem HilbertZ

sm is in BP(Gap∗

C). In particular, the

problem HilbertZ

sm Turing reduces to HNZ

7.2 Projective Characters 93

The reduction from Hilbertsm to #HNCconsists of the following three

steps:

1. Interpret the value pV(d) of the Hilbert polynomial of V⊆Pnon d∈Z

as the Euler characteristic χ(OV(d)) of the twisted sheaf OV(d).

2. The Hirzebruch-Riemann-Roch Theorem [Hir95] gives an explicit com-

binatorial description of χ(OV(d)) in terms of certain determinants

∆λ(c) (related to Schur polynomials) in the Chern classes ciof the

tangent bundle of V.

3. The homology class corresponding to the cohomology class ∆λ(c) can

be realized up to sign by a degeneracy locus, which is defined as the

pull-back of a Schubert variety under the Gauss map (cf. Fulton [Ful98,

Ex. 14.3.3]). The geometric degree of such a degeneracy locus is called

a projective character.

This allows to express (certain integer multiples of) the coefficients of the

Hilbert polynomial as integer linear combinations of projective characters.

Next, the fact that the computation of the geometric degree of varieties is

possible in the complexity class Gap∗

C, and that the class Gap∗

Cis closed

under exponential summation (Lemma 5.19), is used.

7.2 Projective Characters

General references for the material presented in this section are [Ful97,

Man01]. In the following we assume 0 ≤m≤nand consider the Grassman-

nian

G(m, n) := {A|A⊆Pnlinear subspace of dimension m},

as defined in Chapter 4.

The flag variety Fis defined as the set of all complete flags Fof linear

subspaces F0⊂... ⊂Fn−1⊂Fn=Pn, such that dim Fi=ifor 0 ≤i≤n.

It is an irreducible smooth projective variety [Ful97, III.9.1].

For A∈G(m, n) and a flag F∈ F we consider the weakly increasing

sequence of dimensions (dim(A∩Fj))0≤j≤nand denote by 0 ≤σ0< σ1<

···< σm≤nthe positions where the “jumps” occur, that is, dim(A∩Fj) = i

for σi≤j < σi+1 (using the conventions dim ∅=−1 and σ−1:= 0, σm+1 :=

n). The sequence (σi) can be encoded by the sequence of integers n−m≥

λ1≥λ2≥...≥λm+1 ≥0 defined by λi+1 := n−m+i−σi.

Generally, a partition λ= (λ1,...,λr) is a weakly decreasing sequence

of natural numbers. The length of λis defined as the number of nonzero

components of λ. The size of λis defined as |λ|:= λ1+···+λr, and we

call λa partition of k, if |λ|=k. We say that a partition µcontains a

94 Hilbert Polynomial

partition λ,λ⊆µ, if λi≤µifor all i(we set λi= 0 for all iexceeding the

length of λ).

To a partition λof length at most m+ 1 with λ1≤n−m(in which case

we call λadmissible) we associate a strictly increasing sequence 0 ≤σ0<

···< σm≤nby setting σi:= n−m+i−λi+1 for 0 ≤i≤m. The σi

are used to select a subflag Fσ0⊂... ⊂Fσmwith dim Fσi=σi. For such

a partition λand a flag F∈ F the Schubert variety Ωλ(F) is defined as

follows:

Ωλ(F) := {A∈G(m, n)|dim(A∩Fσi)≥ifor 0 ≤i≤m}.

For A∈G(m, n) we always have dim(A∩Fσi)≥i−λi+1, so that λi+1

measures the excess in dimension of the intersection. It is known that Ωλ(F)

is an irreducible variety of codimension |λ|in G(m, n) [Ful97, III.9.4]. (Note

that since λis admissible, we have |λ| ≤ dim G(m, n).) In general, Schubert

varieties are singular [Man01, §3.4].

For a flag F∈ F and an admissible partition λthe Schubert cell eλ(F)

is defined as follows (put F−1=∅)

eλ(F) := {A∈Ωλ(F)|dim(A∩Fσi−1) = i−1 for 0 ≤i≤m}.(7.2)

Thus eλ(F) consists of those elements A∈Ωλ(F) for which dim A∩Fj

increases at exactly the positions j=σi. The Grassmann variety G(m, n) is

the disjoint union of the Schubert cells eλ(F) over all admissible partitions λ.

Moreover, it is known that

Ωλ(F) = [

λ⊆µ

eµ(F),(7.3)

where the union is over all admissible partitions µcontaining λ, cf. [Ful97,

III.9.4, Ex. 13] or [Man01, §3.2]. The Schubert cell is a complex analytic

submanifold of G(m, n) of codimension |λ|. It is open and dense in Ωλ(F).

Moreover, eλ(F) is contained in the smooth part of Ωλ(F), cf. [Man01, §3.4].

Example 7.4 (i) In the case λ= (k) = (k, 0,...,0) the degeneracy

conditions reduce to the single condition A∩Fσ06=∅on Fσ0∈

G(n−m−k, n).

(ii) In the case λ= (1k) = (1,...,1,0,...,0) the degeneracy conditions

reduce to the single condition dim(A∩Fσk−1)≥k−1 on Fσk−1∈

G(n−m+k−2, n).

(iii) We have Pn=G(0, n) = Ω0(F) = ∪n

i=0e(i), where e(i)=Fi−Fi−1∼

Ci, which is just the usual decomposition of Pnas a disjoint union of

affine spaces.

7.2 Projective Characters 95

Let V⊆Pnbe a smooth projective variety of pure dimension m. The

Gauss map ϕ:V→G(m, n) maps x∈Vto the projective tangent space

TxV⊆Pnat x. For an admissible partition λand a flag F∈ F we define

the generalised polar variety

Pλ(F) := ϕ−1(Ωλ(F)) = {x∈V|dim(TxV∩Fσi)≥ifor 0 ≤i≤m}(7.4)

to be the preimage of the Schubert variety Ωλ(F) under the Gauss map.

The well-known polar varieties

Pk(F) := P(1k)(F) = {x∈V|dim(TxV∩Fn−m+k−2)≥k−1}

correspond to the special case λ= (1k) = (1,...,1,0,...,0), see [Pie78,

Bra00]. We remark that a different concept of generalised polar varieties has

been previously used for algorithmic purposes, see [BGHM01, BGHP04].

Note that the case where Vis a linear space is degenerate: then we have

dim ϕ(V) = 0 and thus Pλ(F) is empty for almost all F∈ F, provided |λ|>

0. A result by Zak, cf. [FL81, §7], states that this is the only degenerate case.

Namely, if V⊆Pnis a nonlinear irreducible smooth projective variety, then

the Gauss map ϕ:V→ϕ(V) is finite. In particular, we have dimϕ(V) =

dim Vin this case.

We recall from Section 4.3 the important notion of transversality. For

x∈Vwe denote by TxVthe Zariski tangent space and by dxϕ:TxV→

Tϕ(x)G(m, n) the differential of ϕat x, respectively. The Gauss map ϕmeets

the Schubert cell eλ(F)transversely at x∈ϕ−1(eλ(F)), written ϕtxeλ(F),

Tϕ(x)G(m, n) = dxϕ(TxV) + Tϕ(x)eλ(F).

Moreover, ϕmeets eλ(F)transversely, written ϕteλ(F), if ϕtxeλ(F)

holds for all xin ϕ−1(eλ(F)).

Remark 7.5 If ϕteλ(F) then it is well known that ϕ−1(eλ(F)) is a smooth

complex submanifold of codimension |λ|in V, unless it is empty. (Recall

that eλ(F) has the codimension |λ|in G(m, n).)

We can extend the notion of transversality to Schubert varieties in the

following natural way, exploiting their stratification (7.3) by Schubert cells.

Definition 7.6 We say that ϕmeets Ωλ(F)transversely, written ϕtΩλ(F),

if for every admissible µ⊇λwe have ϕteµ(F).

The following lemma is of central importance, since it allows to define

the projective characters.

Lemma 7.7 Let V⊆Pnbe a smooth projective variety of pure dimension

msuch that not all irreducible components of Vare linear. Let ϕ:V→

G(m, n)be the Gauss map of Vand λbe an admissible partition with

|λ| ≤ m. Then we have

96 Hilbert Polynomial

(i) ϕtΩλ(F)for almost all flags F∈ F,

(ii) if ϕtΩλ(F), then dim(ϕ(V)∩eλ(F)) = m−|λ|and codimVPλ(F) =

|λ|,

(iii) there exists an integer dλ, such that deg Pλ(F) = dλ, provided that

ϕtΩλ(F).

We call deg Pλ:= dλthe projective character of Vcorresponding to λ.

These quantities were studied by Severi [Sev02], see also [Ful98, Ex. 14.3.3].

Note that the degree of Vequals the projective character for λ= 0.

Example 7.8 Let V⊆P2be a smooth curve. Then deg P1counts the

number of points on the curve whose tangents go through a generic point in

P2. B´ezout’s theorem implies that this number equals d(d−1), where dis

the degree of the curve.

For the proof of Lemma 7.7 we need the following result of Kleiman [Kle74],

see also [Har77, III.10].

Lemma 7.9 Let ϕ:V→Ybe a morphism of smooth irreducible varieties

and let X⊆Ybe a quasi-projective smooth subvariety. Assume that Yis a

homogeneous space, with a connected algebraic group Gacting transitively

on it. Then for almost all g∈G,ϕmeets gX transversely. Moreover, if

δ:= dim ϕ(V)+dim X−dim Y≥0, then ϕ(V)∩gX is of pure dimension δ,

for almost all g∈G.

Recall that a partition λwas named admissible if λ1≤n−mand the

length is at most m+ 1.

Corollary 7.10 Let Z⊆G(m, n)be a quasi-projective irreducible subva-

riety and λbe an admissible partition. Then, for almost all F∈ F, the

intersection Z∩Ωλ(F)has codimension |λ|in Zif |λ| ≤ dim Z, and it is

empty otherwise.

Proof. Recall from (7.3) the cell decomposition Ωλ(F) = ∪λ⊆µeµ(F). The

Grassmannian G(m, n) is a homogeneous space with respect to the natural

action of the linear group G:= GL(n+ 1,C). The group Galso acts tran-

sitively on the flag variety F(in fact, we can define Fas a quotient of G,

cf. [Man01, §3.6]) and we have geλ(F) = eλ(gF ). Decompose Zas finite

disjoint union of smooth irreducible quasi-projective varieties Zj. We can

then apply Lemma 7.9 to the inclusion of Zjin G(m, n) and to a Schubert

cell X:= eµ(F) in order to obtain that, for almost all F, the intersection

Zj∩eµ(F) has the expected dimension (namely dim Zj−|µ|if this is non-

negative, otherwise the intersection is empty). This implies the assertion. 2

7.2 Projective Characters 97

Proof of Lemma 7.7. Without lack of generality we may assume that V

is irreducible and not linear. (Note that for linear V,ϕ(V) consists of one

point only and thus the transversality condition ϕtΩλ(F) is equivalent

to ϕ(V)∩Ωλ(F) = ∅, except for the trivial case λ= (0). We may thus

safely ignore linear components and restrict attention to a single nonlinear

component.)

In this case, a result of Zak [FL81, §7] says that the Gauss map ϕ:V→

G(m, n) is finite, hence dim ϕ(V) = dim V=m. Since we are dealing with

projective varieties, we have dim(ϕ(V)∩Ωλ(F)) ≥dim ϕ(V) + dim Ωλ(F)−

dim G(m, n) = m− |λ|for any partition λwith |λ| ≤ mby a standard

dimension argument, cf. [Har95, Thm.17.24].

(i) Let µ⊇λbe an admissible partition. Lemma 7.9 implies that for

almost all flags F∈ F,ϕmeets eµ(F) transversely. Looking at the cell

decomposition (7.3) of Ωλ(F), the claim follows (recall Definition 7.6).

(ii) We proceed by induction on the size of λ. Assume that the claim is

true for all partitions µsuch that |λ|<|µ| ≤ m. Suppose ϕtΩλ(F). The

cell decomposition (7.3) of Ωλ(F) implies that

ϕ(V)∩Ωλ(F) = [

µ⊇λ

ϕ(V)∩eµ(F).

We are going to show that ϕ(V) intersects the cell eλ(F). If this were not

the case, we had dim(ϕ(V)∩Ωλ(F)) = maxµ⊃λ(m− |µ|)< m −|λ|, since

we have dim(ϕ(V)∩eµ(F)) = m− |µ|by induction hypothesis. However,

this contradicts the fact that dim(ϕ(V)∩Ωλ(F)) ≥m−|λ|.

Now note that Pλ(F) = ∪µ⊇λϕ−1(eλ(F)). By Remark 7.5, ϕ−1(eµ(F))

is either empty or of codimension m−|µ|in V. Moreover, we just showed

that ϕ−1(eλ(F)) is nonempty. This show the induction claim. The induction

start where |λ|=mis proved similarly.

(iii) We fix a flag F0∈ F and set Ω := Ωλ(F0), e:= eλ(F0), ∂e := Ω−e.

Consider the map

δ:G→N, g 7→ deg ϕ−1(gΩ).

It is easy to see that the fibres of δare constructible. Since Gis irreducible,

there exists a unique integer dλsuch that δ(g) = dλfor almost all g∈G.

We have to show that

∀g∈G(ϕtgΩ =⇒δ(g) = dλ).

Fix g0∈Gsuch that ϕtg0Ω holds and write N:= δ(g0). By (ii) we know

that ϕ−1(g0Ω) is of codimension |λ|in V. It is sufficient to show that the

function δis constant in a Euclidean neighbourhood of g0.

Let A⊆Pnbe a linear subspace of dimension k:= n−m+|λ|such that

A∩ϕ−1(g0∂e) = ∅and Atϕ−1(g0e).(7.5)

98 Hilbert Polynomial

Then the intersection A∩ϕ−1(g0Ω) consists of exactly Nelements, say

x1,...,xN, cf. [Mum76, §5A]. It is therefore sufficient to show that for all g

in some neighbourhood of g0condition (7.5) holds with ginstead of g0and

|A∩ϕ−1(gΩ)|=N.

Fix a point xi. Since ϕ−1(g0e) is smooth and of codimension kin Pn,

it can be defined locally around xiby kequations h1(x, g0),...,hk(x, g0).

Moreover, these equations can be chosen such that h1,...,hn−mare lo-

cal equations for Varound xi(not depending on g0) and hn−m+1,...,hk

are obtained by pulling back local equations for g0eat the smooth point

ϕ(x). Note that these last |λ|equations are polynomials in xas well

as in the parameter g0. Suppose that Ais the zero set of linear forms

a1,...,an−k. The transversality condition Atxiϕ−1(g0e) implies that

dxh1(xi, g0),...,dxhk(xi, g0), a1,...,an−kare linearly independent. We are

thus in the situation of the implicit function theorem: there is a Euclidean

neighbourhood Uof g0and a Euclidean neighbourhood Viof xisuch that

for each g∈Uthe set A∩ϕ−1(gΩ) ∩Viconsists of exactly one point xi(g).

It remains to be seen that for gsufficiently close to g0, the set A∩ϕ−1(gΩ)

cannot have more than Nelements. Suppose by contradiction that there is a

sequence gνin Gconverging to g0such that for all ν,A∩ϕ−1(gνΩ) contains

a point yνdifferent from x1(gν),...,xN(gν). Since Vis compact, by passing

to a subsequence, we may assume that yνconverges to a point y∈V. By

continuity, y∈A∩ϕ−1(g0Ω), hence y=xifor some i. We conclude that

yν=xi(gν) for νsufficiently large, contradicting our assumption. 2

The following is used later.

Lemma 7.11 Let Wbe a quasi-projective variety and let ψ:W→G(m, n)

be a morphism. Let λbe an admissible partition. For F∈ F set Rλ(F) :=

ψ−1(Ωλ(F)). Then for almost all F∈ F we have dim Rλ(F)≤dim W−|λ|

if |λ| ≤ dim W, and Rλ(F) = ∅otherwise.

Proof. We may assume without loss of generality that Wis irreducible

and that dim ψ−1(ψ(x)) is constant for x∈W, say equal to δ. (Decompose

Winto the locally closed subsets Wi:= {x∈W|dim ψ−1(ψ(x)) = i}and

apply the assertion to the irreducible components of Wi.) By [Sha74, §I.6.3

Thm. 7] (see also [Har95, Thm. 11.12]) we have

dim W= dim Z+δ, dim Rλ(F)≤dim ψ(Rλ(F)) + δ,

where we have set Z:= ψ(W). Assume first that |λ| ≤ dim Z. By Corollary

7.10, we have dim(Z∩Ωλ(F)) = dim Z− |λ|for almost all F∈ F. Since

ψ(Rλ(F)) = Z∩Ωλ(F), we obtain for almost all F

dim Rλ(F)≤dim ψ(Rλ(F)) + δ= dim Z−|λ|+δ= dim W−|λ|.

7.3 The Hilbert Polynomial and Projective Characters 99

If |λ|>dim Zwe have Z∩Ωλ(F) = ∅and therefore Rλ(F) = ∅for al-

most all F. The inequality dim Rλ(F)≥dim W−|λ|follows from [Har95,

Thm. 17.24]. 2

7.3 Expressing the Hilbert Polynomial by Projective Char-

acters

Our goal is to express the coefficients of the Hilbert polynomial of Vin terms

of its projective characters. We first introduce some notation.

To any sequence c= (ci)i∈Nof elements of a commutative ring such that

c0= 1 and to a partition λ= (λ1,...,λr) we assign the ring element ∆λ(c)

as follows:

∆λ(c) := det ((cλi−i+j)1≤i,j≤r)

= det 





cλ1cλ1+1 ··· cλ1+r−1

cλ2−1cλ2··· cλ2+r−2

··· ··· ··· ···

cλr−r+1 cλr−r+2 ··· cλr





,(7.6)

using the convention ci= 0 for i < 0. Note that the value of this determinant

does not change if we extend the partition λby zeros.

In the following let bbe the coefficient sequence of the power series

i≥0

biti:= t

1−e−t= 1 + t

2+X

j≥1

(−1)j−1Bj

(2j)! t2j,(7.7)

where the Bjare the Bernoulli numbers. E.g., B1=1

6, B2=1

30 , B3=1

42 .

Remark 7.12 It is known that Bn= (−1)n−1P2n

k=1 1

k+1 Pk

r=1(−1)rk

rrn

[GKP94, 6.5]. This implies that (2n+1)!Bnis an integer, hence i!(i+1)!biis

an integer for all i. Taking into account that for a partition λ= (λ1,...,λr)

of size Mand length rwe always have λ1+r−1≤M, we conclude that

[(M+ 1)! ···(M−r+ 2)!]2∆λ(b) is an integer.

To a pair (λ, µ) of partitions of length at most mwe assign the following

determinant of binomial coefficients

λµ := det λi+m+ 1 −i

µj+m+ 1 −j1≤i,j≤m

Now let 0 ≤k≤mand µbe a partition with |µ| ≤ m−k. To this data we

assign the rational number

δm,k

µ:= (−1)|µ|X

µ⊆λ

|λ|=m−k

∆λ(b)dm

λµ,(7.8)

100 Hilbert Polynomial

where the sum is over all partitions λof size m−kthat contain µas sub-

partition.

The following crucial statement is proved in Chapter 8.

Theorem 7.13 Let V⊆Pnbe a smooth complex projective variety of pure

dimension mand 0≤k≤m. Then the k-th coefficient pk(V)of the Hilbert

polynomial of Vis given by

pk(V) = 1

k!X

|µ|≤m−k

µ1≤n−m

δm,k

µdeg Pµ,

where deg Pµis the projective character introduced in §7.2. In particular,

[(m−k+ 1)! ···2!1!]2k!pk(V)is an integer.

Example 7.14 1. The above formula yields pm(V) = 1

m!δm,m

0deg P0=

m!deg V, as expected (check that ∆0(b) = 1, dm

0,0= 1).

2. In the case where V⊆Pnis a smooth curve (n≥2), the above formula

implies that p0=δ1,0

0deg P0+δ1,0

1deg P1= deg V−1

2deg P1, where

deg P1= #{x∈V|TxV∩L6=∅} for a generic linear subspace L⊂Pn

of codimension 2.

3. In the special case of a smooth planar curve V(see Example 7.8), we

have p0(V) = d−1

2d(d−1) = 1

2d(3 −d), which implies the well known

formula 1 −p0(V) = 1

2(d−1)(d−2) for the arithmetic genus.

4. Consider the rational normal curve V⊆Pn, which is defined as the

projective closure of {(t, t2,...,tn)|t∈C}. The Hilbert polynomial

of Vsatisfies pV(T) = nT +1. It is not too hard to verify directly that

deg P1= 2(n−1).

7.4 Complexity of Computing the Hilbert Polynomial

The goal of this section is to prove Theorem 7.2, that is, that the problem of

computing the Hilbert polynomial of a smooth equidimensional projective

variety lies in the class Gap∗

7.4.1 Upper Bounds

The upper bound on Hilbertsm is based on Theorem 7.13. We therefore

first study the problem to compute projective characters (recall Lemma 7.7

for their definition).

ProjChar (Projective characters). Given 0 ≤m≤n, homogeneous poly-

nomials f1,...,frin C[X0,...,Xn] satisfying the input condition for m

7.4 Complexity of the Hilbert Polynomial 101

and a partition λsuch that λ1≤n−mand |λ| ≤ m, compute

the projective character deg Pλof the m-dimensional part Vof V0=

Z(f1,...,fr).

Proposition 7.15 The problem ProjChar is in #P∗

We prove Proposition 7.15 using a generic parsimonious reduction from

ProjChar to a certain auxiliary problem, which we describe next. Consider

an instance of ProjChar. Write ψ(x) := PTr

i=1 ker dxfifor x∈V0

and define for a flag F∈ F the following constructible set (recall that

σi=n−m+i−λi+1)

Qλ(F) := {x∈V0|dim(ψ(x)∩Fσi)≥ifor 0 ≤i≤m}.(7.9)

We will represent a flag F∈ F by a matrix a∈Cn×(n+1) such that Fσiis

the projective zero set of the linear forms corresponding to the first δi:=

n−σi=m−i+λi+1 rows of a, for 0 ≤i < m.

Lemma 7.16 There is a function Φin #P∗

Cwhich takes as input an instance

of ProjChar and a flag F∈ F and outputs the degree of the (m− |λ|)-

dimensional part of Qλ(F), provided dim Qλ(F)≤m−|λ|.

Proof. Suppose we have an instance of ProjChar and a flag F∈ F given

by the matrix a∈Cn×(n+1). Let Mi(x, a)∈C(δi+r)×(n+1) denote the matrix

obtained by taking the submatrix of aconsisting of the first δirows of aand

adding the Jacobian matrix (∂fs/∂Xj(x))1≤s≤r,0≤j≤nat the bottom. Then

we have for all x

dim(ψ(x)∩Fσi)≥i⇐⇒ rankMi(x, a)≤n−i.

This condition can be tested in PC, since the rank of a matrix can be com-

puted in polynomial time, e.g., using Gaussian elimination (compare Exam-

ple 5.22). The claim follows now from Lemma 5.21. 2

Proof of Proposition 7.15. Suppose we are given an instance of ProjChar.

Let ψ(x) = PTr

i=1 ker dxfiand Qλ(F) be defined for a flag F∈ F as

in (7.9). By the input condition (7.1), ψ(x) is a linear subspace of Pn

of dimension at most mfor every x∈V0. Let V0=V∪Wbe as in

Lemma 7.1, so that Vis smooth of dimension mand dim W < m. We then

have ψ(x) = TxVfor all x∈V, so that the restriction ϕ:= ψ|Vdetermines

the Gauss map ϕ:V→G(m, n). Note that ψ(x) may be different from the

projective tangent space at points x∈W.

Set Pλ(F) := Qλ(F)∩Vand Rλ(F) := Qλ(F)∩W. Then Pλ(F) is the

generalised polar variety introduced in (7.4) and we have Qλ(F) = Pλ(F)∪

Rλ(F).

102 Hilbert Polynomial

Consider the following property of an instance Iof ProjChar and a

flag F∈ F:

ϕtΩλ(F) and dim Rλ(F)< m −|λ|. (Π)

According to Lemma 7.7, the condition ϕtΩλ(F) implies that dim Pλ(F) =

m−|λ|and deg Pλ(F) = deg Pλ, under the assumption that not all compo-

nents of Vare linear, or λ= 0. (If the latter assumption is violated, then

Pλ(F) = ∅.) We therefore get

Π is satisfied =⇒deg Pλ= deg Pλ(F) = Φ(I, F ),

where Φ is the function from Lemma 7.16, i.e., the degree of the (m−

|λ|)-dimensional part of Qλ(F). This establishes a generic parsimonious

reduction from ProjChar to the function Φ ∈#P∗

C, once we have shown

that Π is definable in the constant-free polynomial hierarchy over Rand that

for any fixed instance Iof ProjChar, property Π is satisfied by almost all

F∈ F (cf. Definition 5.9).

Lemma 7.7 tells us that ϕtΩλ(F) is satisfied for almost all F∈ F.

In order to show that dim Rλ(F)< m − |λ|for almost all F, we apply

Lemma 7.11 to the quasi-projective set Wj:= {x∈W|dim ψ(x) = j}and

the map ψj:Wj→G(j, n), x 7→ ψ(x), for 0 ≤j≤m. It is not hard to

identify the set

Rj,λ(F) := {x∈Wj|dim(ψ(x)∩Fσi)≥ifor 0 ≤i≤m}

as the preimage of the Schubert variety corresponding to the flag Fand to a

partition µ(j)satisfying |µ(j)| ≥ |λ|. Thus Rj,λ(F) has dimension dim Wj−

|µ| ≤ dim Wj−|λ|for almost all F. Since W=W0∪···∪Wmand dim W <

mwe have Rλ(F) = R0,λ(F)∪ ··· ∪ Rm,λ(F), and conclude that indeed

dim Rλ(F)< m −|λ|.

It remains to be seen that Π can be defined in PH0

R. According to

Definition 7.6, ϕtΩλ(F) can be expressed as follows:

∀µ(µ⊇λ∧µadmissible =⇒ϕteµ(F)),(7.10)

where the transversality condition ϕteµ(F) means that

∀x(x∈V∧ϕ(x)∈eµ(F) =⇒ϕtxeµ(F)).

Lemma 7.24 in Section 7.5 says that the local transversality condition

in the parenthesis is decidable in P0

C. This implies that condition (7.10) is

expressible in coNP0

Cand thus in PH0

In order to express dim Rλ(F)< m − |λ|, we recall that the points

x∈Wcan be characterised among the points of V0as those having local

dimension smaller than m, cf. Lemma 7.1. The local dimension of (semi-

)algebraic sets is expressible in the constant-free polynomial hierarchy over

the reals (compare Lemma 4.16). We can thus express membership to Rλ(F)

in PH0

R. Finally, using Lemma 4.16 again, we conclude that the condition

dim Rλ(F)< m −|λ|is expressible in PH0

R.2

7.4 Complexity of the Hilbert Polynomial 103

Using Proposition 7.15, we can proceed to prove the main Theorem 7.2.

Proof of Theorem 7.2. Put N(k, m) := [(m−k+1)! ···2!1!]2. Consider the

function g:{0,1}∞→Zmapping (m, k, µ) to N(k, m)δm,k

µ, where m, k ∈N,

µa partition with |µ| ≤ m−k,µ1≤n−mand δm,k

µis defined in Equa-

tion (7.8), i.e., δm,k

µ:= (−1)|µ|Pµ⊆λ,|λ|=m−k∆λ(b)dm

λµ. By Remark 7.12,

the values of gare integers. The functions mapping (m, k, µ, λ) to ∆λ(b)dm

λµ

and to N(k, m), respectively, are clearly polynomial time computable, if we

think of (m, k, µ) as being encoded in unary. It then follows from elemen-

tary properties of GapP (closure under exponential summation and product,

cf. [For97]) that gis in GapP. Let ϕ:C∞× {0,1}∞→Z∪ {−∞,∞} be

the function corresponding to the problem ProjChar, where the first argu-

ment contains the description of the polynomials and the second argument

the partition λ. According to Proposition 7.15, ϕ∈#P∗

C, so we can apply

the Summation Lemma 5.19 to the main formula in Theorem 7.13 to con-

clude that Hilbertsm ∈Gap∗

C.2

7.4.2 Lower Bounds

We first complement the upper bound in Corollary 7.3 by a lower bound.

Proposition 7.17 The problem HilbertZ

sm is #P-hard.

Proof. We proceed as in [Bac99]. Let ϕbe a Boolean formula in the

variables X1,...,Xnin conjunctive normal form. It is well known that

the problem #SAT to count the number of satisfying assignments of such

formulas is #P-complete [Val79b, Val79a].

For each literal λput gλ:= 1 −Xiif λ=Xiand gλ:= Xiif λis the

negation of Xi. For each clause κ=λ1∨···∨ λkput gκ:= Qk

i=1 gλi. Let

fκdenote the homogenisation of gκwith respect to the variable X0.

We assign to the Boolean formula ϕ=κ1∧···∧κsthe system of homo-

geneous equations

1−X1X0,...,X2

n−XnX0, fκ1,...,fκs.

Clearly, the zero set V0of this system in Pncorresponds bijectively to the

satisfying assignments of ϕ(there are no solutions at infinity). Moreover,

looking at the first nequations we see that the input condition (7.1) is

satisfied with m= 0. The Hilbert polynomial of V0is constant and equals

the number of satisfying assignments of ϕ. This provides a polynomial time

reduction from #SAT to HilbertZ

sm.2

Remark 7.18 Due to the input condition (7.1) it is not clear whether

Hilbertsm and HilbertZ

sm are #P

C-hard and GCC-hard, respectively.

104 Hilbert Polynomial

Corollary 7.3 states that the problem HilbertZ

sm to compute the Hilbert

polynomial of smooth varieties is in BP(Gap∗

C). We next show that the

general problem to compute the Hilbert polynomial of a homogeneous ideal

is presumably more difficult, namely FPSPACE-hard. Consider the following

problems:

HIM (Homogeneous ideal membership problem). Given non-constant ho-

mogeneous polynomials f1,...,fr, g ∈C[X0,...,Xn], decide whether

glies in the ideal generated by f1,...,fr.

Hilbert (Hilbert polynomial). Given a family of non-constant homoge-

neous polynomials f1,...,frin C[X0,...,Xn] and 0 ≤k≤n, com-

pute the k-th coefficient of the Hilbert polynomial of the homogeneous

ideal generated by f1,...,fr.

We will use the following simple and well-known lemma to establish a

Turing reduction from HIMZto HilbertZ, and then invoke a result in

Mayr [May97, Thm. 17], which states that HIMZis PSPACE-complete.

Lemma 7.19 Let Ibe a homogeneous ideal such that some Xiis not a

zero-divisor of C[X0,...,Xn]/I. Let gbe a non-constant homogeneous poly-

nomial. Then g∈Iif and only if Iand I+ (g)have the same Hilbert

polynomial.

Proof. Assume Xiis not a zero-divisor of C[X0,...,Xn]/I. Let I,gbe

such that J:= I+ (g) and Ihave the same Hilbert polynomial. This means

that J(d)=I(d)for sufficiently large degree d. Hence, we have Xd

ig∈Ifor

sufficiently large d, and thus g∈I.2

By introducing a further variable Ywe can achieve that Yis not a

zero-divisor of C[X0,...,Xn, Y ]/I, where I=C[X0,...,Xn, Y ]I. Hence we

obtain the following lower bound.

Theorem 7.20 The problem HilbertZis FPSPACE-hard.

Based on this theorem, we can now improve the #P-lower bound in [Bac99]

for the problem to compute the ranks of cohomology groups of coherent

sheaves on projective space. The lower bound is also true for the problem

to compute the corresponding Euler characteristic.

For an introduction to sheaf cohomology we refer to [Har77, Iit82]. We

encode the input to our problems as in [Bac99]. Thus we specify a coherent

sheaf on Pnby giving a graded matrix. This is a matrix (pij)1≤i≤s,1≤j≤rof

homogeneous polynomials in S:= C[X0,...,Xn] together with two arrays

of integers (d1,...,ds) and (e1,...,er) such that deg pij =di−ejwhenever

7.4 Complexity of the Hilbert Polynomial 105

pij 6= 0. A graded matrix defines a degree-preserving morphism

γ:

j=1

S(ej)→

i=1

S(di)

of graded S-modules. (As usual, S(d) denotes Swith degrees shifted by d

to the left, so that S(d)0=Sd.) The cokernel Mof γis a finitely generated,

graded S-module and thus determines a coherent sheaf f

Mon Pn(cf. [Har77,

p. 116]). We study the task to compute the dimensions of the cohomology

C-vector spaces Hi(Pn,f

M) for i= 0,...,n. (It is known that these vector

spaces vanish for i > n [Har77, III.2.7].) The Euler characteristic of the

sheaf f

Mis defined as

χ(f

M) :=

i=0

(−1)idim Hi(Pn,f

M).(7.11)

The link to the Hilbert polynomial is given by the following proposition,

a proof of which can be found in [Iit82, Section 7.6], see also [Har77, Ex.

III.5.2].

Proposition 7.21 Let I⊆S:= C[X0,...,Xn]be a homogeneous ideal,

M=S/I and pM(T)∈Q[T]the corresponding Hilbert polynomial. Then

pM(d) = χ(f

M(d)) for all d∈Z.

We now consider the following problems.

RankSheaf (Rank of sheaf cohomology). Given a morphism γby a graded

matrix as above and given i∈N, compute dim Hi(Pn,f

M) for M=

cokerγ.

EulerSheaf (Euler characteristic of sheaf cohomology). Given a mor-

phism γby a graded matrix as above, compute χ(f

M) for M= cokerγ.

The following result improves the #P-lower bound in [Bac99].

Corollary 7.22 The problems RankSheafZand EulerSheafZare both

FPSPACE-hard.

Proof. Clearly, EulerSheafZcan be Turing reduced to RankSheafZ.

Theorem 7.20 tells us that HilbertZis FPSPACE-hard. It is therefore

sufficient to establish a Turing reduction from HilbertZto EulerSheafZ.

An instance of HilbertZis a family of non-constant homogeneous poly-

nomials f1,...,frin Z[X0,...,Xn]. Let Idenote the corresponding homo-

geneous ideal in C[X0,...,Xn]. Consider the graded morphism γ:⊕r

j=1

S(ej)→Sgiven by f1,...,fr, where ej:= −deg fj. The cokernel Mof γ

equals S/I.

106 Hilbert Polynomial

By Proposition 7.21 we have pM(d) = χ(f

M(d)) for all d∈Z. We

can therefore obtain the values pM(d) for d= 0,...,n by n+ 1 calls to

EulerSheafZand then compute the coefficients of pMby interpolation. 2

Remark 7.23 The algorithm in [BS92] combined with the upper bounds

in [May97] implies that HilbertZis in FEXPSPACE. We do not know of

any better upper bound on this problem. The known algorithms for sheaf

cohomology (cf. [Vas98, Chapter 8], [DE02]) suggest that RankSheafZis

in FEXPSPACE.

7.5 Expressing Transversality

In this section we conclude the proof of Proposition 7.15. We consider input

data of the form (f, n, m, µ, F , x) where f= (f1,...,fr) is a sequence of

homogeneous polynomials in C[X0,...,Xn] satisfying the input condition

(7.1) for m∈Nand xis in the projective zero set V0of these polynomials.

Moreover, Fis a flag in Fencoded by a matrix a∈Cn×(n+1) and µ=

(µ1,...,µm+1) is an admissible partition with respect to nand m. Recall

from Lemma 7.1 the decomposition V0=V∪W, where Vis smooth of pure

dimension mand dim W < m.

Let u∈C∞be an encoding of (f, n, m, µ), let a∈C∞be an encoding

of Fand define the relation trans ⊆C∞×C∞×C∞by

trans(u, a, x) :⇐⇒ x∈V∧ϕ(x)∈eµ(F) =⇒ϕtxeµ(F),

where ϕis the Gauss map of V.

Lemma 7.24 The relation trans is decidable in polynomial time by a

constant-free machine over C.

Before going into the proof, we recall some facts concerning the manifold

structure and cell decomposition of Grassmannians. For a comprehensive

account, we refer to [Ful97, III.9] and [Man01].

Dual to our usual encoding a∈Cn×(n+1) of a flag F∈ F (where the

Fiare zero sets of row forms of a), we can represent the flag Fby a basis

`= (`0,...,`n) of Cn+1 such that Fiis spanned by (`0, . . . , `i) for 0 ≤i≤n.

Clearly, this basis is uniquely determined by Fup to scaling and can be

computed from ain polynomial time.

Let µbe an admissible partition and let σdenote the associated sequence

0≤σ0<···< σm≤ndefined by σi:= n−m+i−µi+1. To a fixed basis

`and µwe assign the Schubert cell eµ:= eµ(`) := eµ(F) according to (7.2).

(To ease notation, we will usually drop the dependence on `.) It is not

hard to see that every subspace Ain eµhas a unique basis, that can be

represented with respect to the basis `by the rows of an (m+ 1) ×(n+ 1)

7.5 Expressing Transversality 107

row echelon matrix, which has a 1 at the intersection of the i-th row with

the σi-th column, and zeros in the i-th row to the right of this position as

well as zeros in the σi-th column below this position, for all 0 ≤i≤m. In

the case m= 3, n = 7, µ= (3,1,0), σ= (1,4,6,7) such an echelon matrix

looks as follows: 





∗1 0 0 0 0 0 0

∗0∗ ∗ 1 0 0 0

∗0∗ ∗ 0∗1 0

∗0∗ ∗ 0∗0 1





.(7.12)

In order to describe a covering of G(m, n) in terms of affine charts,

consider for fixed `the subspaces Lµand Lµof Cn+1 spanned by `σ0,...,`σm

and {`j|j6∈ {σ0,...,σm}}, respectively. We define Uµ:= Uµ(`)⊆G(m, n)

as the set of (m+ 1)-dimensional subspaces A⊆Cn+1 whose projection to

the subspace Lµalong Lµis an isomorphism. The open sets Uµform an

open cover of G(m, n). By identifying A∈Uµwith the graph of a linear

map from Lµto Lµ, we get an isomorphism

αµ:Uµ∼

−→ Hom(Lµ, Lµ)∼

−→ C(n−m)×(m+1),(7.13)

where the last isomorphism maps an element of Hom(Lµ, Lµ) to its matrix

representation with respect to the bases defined by `. The matrix αµ(A) is

obtained from the echelon matrix in (7.12) by removing all the σi-columns

(thus removing a unit matrix of size m+ 1) and transposing. Taking this

into account, we see that eµ⊆Uµand that the image of eµunder αµcan

be described as follows:

αµ(eµ) = (aij)∈C(n−m)×(m+1) |aij = 0 for j≥σi−i, 0≤i≤m,

0≤j < n −m.

(7.14)

In particular, αµ(eµ) is a linear subspace of C(n−m)×(m+1).

Proof of Lemma 7.24. Assume that x∈Vand ϕ(x)∈eµ(`). The claim is

that the transversality condition

Tϕ(x)G(m, n) = dxϕ(TxV) + Tϕ(x)eµ(`).(7.15)

can be checked in constant-free polynomial time over C.

In order to simplify notation, we will identify Vwith its affine cone b

xwith an affine representative bx, and the Gauss map ϕwith the corre-

sponding morphism bϕ:b

V−{0} → G(m, n). This causes no problem, since

dxϕ(TxV) = dbxbϕ(Tbxb

V).

Given a basis `and a partition µ, we represent eµ=eµ(`) and the

tangent spaces TAG(m, n) and TAeµfor A∈eµby means of the chart αµ

defined in (7.13). Around xwe extend the Gauss map ϕinto the chart

considering

ϕµ:V∩ϕ−1(Uµ)ϕ

−→ Uµ

αµ

−−→ C(n−m)×(m+1)

108 Hilbert Polynomial

In this light, Equation (7.15) translates into

C(n−m)×(m+1) =dxϕµ(TxV) + αµ(eµ).

Equation (7.14) gives an explicit and simple description of αµ(eµ). It remains

to find a suitable description of dxϕµ(TxV).

After a linear coordinate transformation, we may assume that Lµ=

Cm+1 ×0 and Lµ= 0 ×Cn−m. Thus without loss of generality, we assume

that X0,...,Xnare coordinates adapted to the decomposition Cn+1 =Lµ⊕

Lµ.

Locally around the point x, the variety V⊆Cn+1 is given as the zero set

of the polynomials f1,...,fr. Our assumption ϕ(x)∈eµmeans that TxVlies

in eµand thus in Uµ. This implies that the matrix ( ∂fs

∂Xt(x))1≤s≤r,m<t≤nhas

rank n−m. After a permutation, we assume that ( ∂fs

∂Xt(x))1≤s≤n−m,m<t≤nis

invertible. It will be convenient to use the abbreviations X0:= (X0,...,Xm)

and X00 := (Xm+1,...,Xn).

By the implicit function theorem there are analytic functions h1,...,hn−m

in X0such that in a neighbourhood of x, the variety Vis the graph of the

analytic function h:= (h1,...,hn−m) defined on a neighbourhood of x0. In

particular, x= (x0, h(x0)). From this we obtain the following description of

the Gauss map:

ϕµ(X0, h(X0)) = ∂hs

∂Xi

(X0)1≤s≤n−m,0≤i≤m∈C(n−m)×(m+1).

Hence the vector space dxϕµ(TxV) is spanned by the matrices

∂2hs

∂Xi∂Xj

(x0)1≤s≤n−m,0≤i≤m

for 0 ≤j≤m. It remains to show that these matrices can be computed

in constant-free polynomial time over C. We remark that in the case of a

hypersurface (m=n−1), this matrix just describes the second fundamental

form of Vat x.

By taking the derivative with respect to Xiof fs(X0, h(X0)) = 0, we

obtain

∂fs

∂Xi

(X0, h(X0)) +

t=m+1

∂fs

∂Xt

(X0, h(X0)) ∂ht

∂Xi

(X0) = 0 (7.16)

for 1 ≤s≤n−m, 0≤i≤m. From this, ∂ht

∂Xi(x0) can be computed by

inverting the matrix ( ∂fs

∂Xt(x)). By taking the derivative of Equation (7.16)

7.5 Expressing Transversality 109

with respect to Xjfor 0 ≤j≤mwe get

∂2fs

∂Xi∂Xj

+ 2 X

t>m

∂2fs

∂Xt∂Xj

∂ht

∂Xi

t,k>m

∂2fs

∂Xt∂Xk

∂ht

∂Xi

∂hk

∂Xj

t>m

∂fs

∂Xt

∂2ht

∂Xi∂Xj

= 0.

From this, the desired second order derivatives ∂2ht

∂Xi∂Xj(x0) can be computed

by inverting the matrix ( ∂fs

∂Xt(x)). This finishes the proof. 2

110 Hilbert Polynomial

Chapter 8

Hilbert Polynomial and

Degeneracy Loci

This chapter is devoted to the proof of Theorem 7.13. Some preliminary

material is presented first. As in Chapter 4, the aim is mainly to fix termi-

nology. We base the rudimentary intersection theory used in this chapter

on singular homology theory. For a more general setting, a good reference

is Fultons treatment [Ful98].

8.1 Singular Homology Theory

Associated to a topological space Xare the singular homology groups Hi(X)

and cohomology groups Hi(X), with coefficients in Z. These groups are

homotopy invariants.

There is a cup product

Hi(X)⊗Hj(X)→Hi+j(X), α ⊗β7→ α`β,

and a cap product

Hi(X)⊗Hj(X)→Hj−i(X), α ⊗b7→ αab.

The cup product turns H∗(X) = ⊕Hi(X) into a skew-commutative ring

with 1 ∈H0(X) as unit. The cap product gives the total homology group

H∗(X) = ⊕Hi(X) the structure of a H∗(X)-module. In particular, the

identity

(α`β)aa=αa(βaa)

holds for α∈Hi(X), β∈Hj(X) and a∈Hk(X). A special case is the

evaluation map Hi(X)⊗Hi(X)→Z, α ⊗a7→ hα, ai=∗(αaa), where

∗is the augmentation map [Bre97, IV.2]. If Hk−1(X) is torsion-free, then

Hk(X) = Hom(Hk(X),Z) by the universal coefficient theorem [Bre97, V.7],

and h·,·i is just the usual evaluation.

A continuous map f:X→Yinduces a push-forward f∗:H∗(X)→

H∗(Y) and pull-back f∗:H∗(Y)→H∗(X). These maps satisfy the identity

f∗(f∗(α)aa) = αaf∗(a)

112 Hilbert Polynomial and Degeneracy Loci

for α∈H∗(Y) and a∈H∗(X). The `for the cup product is often omitted,

and α·βor simply αβ is written instead for α`β.

For a connected, compact, oriented manifold Mof dimension m, the

top homology Hm(M) is isomorphic to Z, and its distinguished generator

is called the fundamental class µM[Bre97, VI.7]. It consists of the sum of

all top-dimensional simplices in a triangulation. A nonsingular, irreducible

subvariety of Pnis a compact, connected, 2m-dimensional manifold with

the orientation induced from the complex structure, and thus possesses a

fundamental class [MS74, Chapter 13].

A fundamental class can be associated to any irreducible variety. Accord-

ing to [Hir75], any variety can be triangulated, such that the singular locus

is a subcomplex of strictly smaller dimension. The fundamental class is then

the sum of the top dimensional simplices, the orientation being provided by

the complex structure. For another approach to showing the existence of

a fundamental class, based on Borel-Moore homology, cf. [Ful97, Appendix

B].

Let Vbe an m-dimensional, irreducible variety. There is the Poincar´e

duality map

Hi(V)→H2m−i(V), α 7→ αaµV

which is an isomorphism for nonsingular V, see [Bre97, VI.8].

In the nonsingular case, the Poincar´e dual of the cup product is called

the intersection product ·:Hi(V)×Hj(V)→Hi+j(V) defined by

(αaµV)·(βaµV) = (α`β)aµV.

Let i:V→Mbe the inclusion of an irreducible m-dimensional variety

into a smooth, irreducible, n-dimensional variety M. The push-forward

[V]M:= i∗µVof the fundamental class is called the class of Vin H2m(M).

If the ambient variety Mis understood or not important, we omit the index

and write [V] instead of [V]M. The most common case we will encounter is

where M=Pn. If Vis not irreducible, define

[V] = [W1] + ···+ [W`],

where the sum goes over the irreducible components of maximal dimension.

The intersection product has the property that if V,Wmeet transversely

in M, then

[V]·[W] = [V∩W],

see [Bre97, VI.11] for a detailed discussion. Note that the intersection prod-

uct operating on [V] and [W] is defined in H∗(M), and we do not require V

and Wto be nonsingular.

Of special importance is the cohomology of complex projective space Pn.

As a ring, H∗(Pn) = Z[a]/(an+1), with distinguished generator a∈H2(Pn).

The even cohomology groups are torsion-free and given by H2i(Pn) = Zai,

8.2 Chern Classes and Riemann-Roch 113

the odd ones are zero. A linear subspace Lkof codimension ksatisfies the

relation han−k,[Lk]i= 1, and since Hk(Pn) = Hom(Hk(Pn),Z), the class

[Lk] generates H2n−2k(Pn).

In particular, linear subspaces of the same dimension are homologous to

one another. Let [L] be the class of a hyperplane. From the previous dis-

cussion it follows that [L]k= [Lk], where [L]kmeans the k-fold intersection

product and Lkis a subspace of codimension k. Moreover, if a∈H2(Pn)

is the distinguished generator mentioned above and V⊆Pnis a smooth,

projective subvariety, then

aka[V] = [Lk]·[V] = [Lk∩V],(8.1)

where Lkis a generic linear subspace of codimension kin Pn.

Let i:V ,→Pnbe the inclusion of an m-dimensional irreducible variety.

From the homology of Pnit follows that i∗µV= [V] = d[Ln−m] for some

integer d. This coefficient is in fact equal to the geometric degree of the

embedding of Vinto Pn. If f:V→Pnis any morphism such that f(V) has

the same dimension as V, then

f∗µV=d[f(V)],

where dis the degree of the generic fibre of f[Ful97, Appendix B]. This is

simply called the degree of f.

8.2 Chern Classes and Riemann-Roch

References for the material presented here are [Che46, Hir95, MS74]. See also

[Ful98] for the algebraic geometry perspective. Let V⊆Pnbe a projective

variety. Chern classes are characteristic cohomology classes ci(E)∈H2i(V)

associated to a complex vector bundle p:E→V. Chern classes are charac-

terised axiomatically as follows:

1. ci(E)∈H2i(V), c0(E) = 1 and c1(L) generates H2(Pn), where Lis

the canonical line bundle on Pn.

2. Let f:W→Vbe a morphism of projective varieties. Then ci(f∗(E)) =

f∗(ci(E)), where f∗(E) is the pull-back bundle with respect to f.

3. (Whitney formula.) An exact sequence 0 →E0→E→E00 →0 of

bundles implies ck(E) = Pici(E0)`ck−i(E00).

From Equation (8.1) it follows that for a smooth, closed subvariety V⊆

Pn, the cap product c1(L)ka[V] corresponds to intersecting Vwith k

generic hyperplanes.

The total Chern class is the sum c(E) = Pi≥0ci(E)∈H∗(V) of all the

Chern classes. If Vis smooth and irreducible of dimension m, then the top

114 Hilbert Polynomial and Degeneracy Loci

Chern class cm(TV ) of the tangent bundle evaluated at the fundamental

class yields the topological Euler characteristic of V:

χ(V) = deg(cm(T V )a[V]),

see [MS74, page 170]. Here adenotes the cap-product and deg: H0(V)→Z

is defined by deg(Ppnp[p]) = Ppnp.

We now introduce the necessary terminology needed in order to state

the Hirzebruch-Riemann-Roch theorem, which relates the Chern classes to

the Hilbert polynomial.

Let f(t) = t

1−e−t∈Q[[t]] be the formal power series (7.7) and t1,...,tn

different variables. Consider the product

f(t1)···f(tn) = ∞

i=0

gi(t1,...,tn),

where the giare the i-th graded parts. The giare symmetric polynomials in

the ti, so there is an expression gn(t1,...,tn) = Tn(σ1,...,σn), where σiis

the i-th elementary symmetric function in the ti. The Tn∈Q[X1,...,Xn]

are called Todd polynomials. Note that Tnis homogeneous of weight n, when

we define the weight of a monomial Xi1

1···Xin

nto be the sum Pn

k=1 kik. For

example, the first three Todd polynomials are: T1=1

2X1, T2=1

12 (X2

X2), T3=1

24 X1X2.

If c(TV ) is the total Chern polynomial of the tangent bundle of a smooth

variety Vof dimension m, then we define the Todd class of Vto be

td(V) := 1 +

i=1

Ti(c1,...,ci),

where here (and later) we write cias shorthand for ci(TV ).

Consider the sum Pn

i=1 eti=n+Pi≥1pi(t1,...,tn). Again, the piare

symmetric, so there is a polynomial Kn(X1,...,Xn) which evaluated at the

elementary symmetric functions in the tiyields pn. If ci(E) are the Chern

classes of a vector bundle Eon a variety V, then the class

ch(E) := 1 + X

i≥1

Ki(c1(E),...,ci(E))

is called the Chern character of E.

To a variety V⊆Pnand d∈Zone can assign the twisted sheaf OV(d).

The Chern character of the sheaf OV(d) is particularly easy to describe.

Since OV(d) corresponds to a line bundle, we have only a first Chern class,

which is c1(OV(d)) = dc1(LV). Here, and in what follows, LVdenotes

the line bundle corresponding to the sheaf OV(1) and L∨

Vits dual, i.e., the

canonical line bundle on V. For the Chern character we get

ch(OV(d)) = ec1(OV(d)) =X

i≥0

i!c1(LV)i.(8.2)

8.3 Symmetric Functions 115

To a vector bundle Eon a variety Vthere corresponds a locally free

sheaf E, see [Sha74, VI.1.3] or [Har77, Ex. II.5.18]. Thus we can define

the Euler characteristic χ(E) of Eto be the Euler characteristic χ(E) =

Pi(−1)idim Hi(V, E) of Ewith respect to sheaf cohomology, cf. Equa-

tion (7.11).

Lemma 8.1 Let V⊆Pnbe a variety and d∈Z. Then the Euler character-

istic of the line bundle OV(d)equals the Hilbert polynomial of Vevaluated

at d, that is, χ(OV(d)) = pV(d).

Proof. Let i:V→Pnbe the inclusion and Fbe a coherent sheaf on V.

Then Hj(V, F) = Hj(Pn, i∗F) for all j, cf. [Har77, Lemma III.2.10]. If

M=S/I denotes the homogeneous coordinate ring of V, then i∗OV(d) =

M(d), so by Proposition 7.21 we have χ(OV(d)) = pV(d). 2

With all these notions introduced, we can formulate the Hirzebruch-

Riemann-Roch theorem.

Theorem 8.2 (Hirzebruch-Riemann-Roch, [Hir95]) Let Ebe a vec-

tor bundle on an irreducible smooth variety Vof dimension m. Then

χ(E) = deg ((ch(E)`td(V))ma[V]) .

Theorem 8.2 combined with Lemma 8.1 and Equation (8.2) immediately

yields the following.

Corollary 8.3 Let V⊆Pnbe an irreducible, smooth variety of dimen-

sion m. Then the k-th coefficient of the Hilbert polynomial of Vis given

pk(V) = 1

k!deg(c1(LV)k`Tm−k(c1,...,cm−k)a[V]),

where c1,...,cmare the Chern classes of the tangent bundle TV .

8.3 Generalities on Symmetric Functions

We gather some results from the theory of symmetric functions that will be

used later. Reference for this material are [Mac95, Man01], [FH91, Appendix

A] and [Ful98, Appendix A.9].

For a partition λ, we denote by λ0its conjugate partition. Recall the

definition of ∆λ(c) in Equation (7.6). Claims 1 and 2 of the following lemma

are easy to verify, a proof of the third one is given in [Ful98, Lemma A.9.2].

Lemma 8.4 Let λbe a partition and c={ci}i∈Nbe a sequence of elements

of a commutative ring such that c0= 1.

116 Hilbert Polynomial and Degeneracy Loci

1. The polynomial ∆λ(c)is homogeneous of weight |λ|in the ci, when ci

has weight i.

2. Let c∨={(−1)ici}i∈N. Then ∆λ(c∨) = (−1)|λ|∆λ(c).

3. Let c−1={c0

i}i∈N, where the c0

iare the coefficients of the inverse power

series (Pi≥0citi)−1. Then ∆λ(c−1) = ∆λ0(c∨).

Example 8.5 We verify claims 2 and 3 of the previous lemma for the special

case λ= (1k). For the partition (k) we have ∆(k)(c) = ck. For the partition

(1k) we have ∆(1k)(c) = det Mk(c), where Mk(c) is the Toeplitz matrix

Mk(c) = 





c1c2c3··· ck−1ck

1c1c2··· ck−2ck−1

0 1 c1··· ck−3ck−2

··· ··· ··· ··· ··· ···

0 0 0 ··· 1c1





.

We can expand the determinant as

det Mk(c) = −

i=1

(−1)icidet Mk−i(c).

This equation coincides with the recursive formula for the coefficients c0

jof

the inverse power series (Pi≥0(−1)ici)−1. In particular, we obtain ∆(1k)(c) =

det Mk(c) = c0

k= ∆(k)c−1.

Let γ= (γ1,...,γm) be variables and λbe a partition such that |λ| ≤ m.

Define the Schur polynomial associated to λas

sλ(γ) := sλ(γ1,...,γm) = det(γλj+m−j

i)1≤i,j≤m

det(γm−j

i)1≤i,j≤m

.(8.3)

The polynomial sλ(γ) is symmetric and homogeneous of degree |λ|. Note

that sλdepends not only on the partition λbut also on m.

A proof of the following lemma can be found in [Man01, 1.2.4], [Mac95,

I.3], and [FH91, Appendix A]1.

Lemma 8.6 Let λbe a partition with |λ| ≤ mand c={ci}i∈Nbe given

such that

c0+c1t+···+cmtm=

i=1

(1 + γit),

i.e., the ciare elementary symmetric functions in the γj. Then ∆λ(c) =

sλ0(γ).

1The formula presented is sometimes referred to as Jacobi-Trudi formula [Man01] or

Giambelli’s formula [FH91, Appendix A].

8.4 Proof of Theorem 7.13 117

Example 8.7 If λ= (k), then sλ(γ) is the k-th complete symmetric poly-

nomial in the γi. This is the sum of all distinct monomials of degree kin

the γi. If λ= (1k), then sλ(γ) is the k-th elementary symmetric function in

the γi.

We will further need a formula expanding the Schur polynomial of a sum

of variables. The following lemma follows from [Ful98, Example A.9.1] (see

also [Mac95, Example I.3.10]).

Lemma 8.8 Let λbe a partition with |λ| ≤ m. Then

sλ(γ1+β,...,γm+1 +β) = X

µ⊆λ

λµβ|λ|−|µ|sµ(γ1,...,γm+1),

where

λµ = det λi+m+ 1 −i

µj+m+ 1 −j1≤i,j≤m

Example 8.9 Let λ= (1k). Then any subpartition µ⊆λis of the form

(1j) for some j≤kand dm

λµ =m−j+1

m−k+1. This follows from looking at the

coefficients of the expansion of s(1k)(γ1+β,...,γm+1 +β), using the fact

that s(1k)is an elementary symmetric function (see Example 8.7).

8.4 Proof of Theorem 7.13

In this section we derive Theorem 7.13 from Corollary 8.3 in a series of

reductions. We start by observing a determinantal formula for the Todd

polynomials. For what follows, we will often write Tm(c) as shorthand for

Tm(c1,...,cm).

Lemma 8.10 Let b={bi}i∈Nbe the sequence of rational numbers from

Equation (7.7), c0= 1 and let c1,...,cmbe variables. Then the m-th Todd

polynomial is given by

Tm(c) = X

|λ|=m

∆λ0(b)∆λ(c),

where λ= (λ1,...,λm)runs over all partitions of m.

Proof. Consider the (formal) factorisations

1 +

i=1

ci=

j=1

(1 + γj),1 +

i=1

bi=

j=1

(1 + βj).

This amounts to writing the ciand bias elementary symmetric functions in

the γjand βj, respectively. For a partition λof m, let mλ(γ) be the sum

118 Hilbert Polynomial and Degeneracy Loci

of all different monomials arising from γλ1

1···γλm

mby permutation of the

γi(for example, m(1m)(γ) = γ1···γm). Also, let σλ=σλ1···σλmdenote

the product of the elementary symmetric functions indexed by the partition.

By definition, Tm(c) is the m-th graded component of f(γ1)···f(γm), where

f(γi) = Pj≥0bjγj

i. It follows that

Tm(c) = X

i1+···+im=m

bi1···bimγi1

1···γim

|λ|=m

bλ1···bλmmλ(γ) = X

|λ|=m

σλ(β)mλ(γ).

By [Mac95, I.4(4.2’-3’)] we have

|λ|≤m

σλ(β)mλ(γ) = Y

1≤i,j≤m

(1 + βjγi) = X

|λ|≤m

sλ0(β)sλ(γ),(8.4)

where sλis the Schur polynomial of the partition λ. Lemma 8.6 expresses

the Schur polynomials as determinants:

sλ(γ) = ∆λ0(c).

Noting that deg sλ(γ) = deg mλ(γ) = |λ|and taking the degree mparts in

(8.4) completes the proof. 2

What makes this formula useful is the fact that if cdenotes the total

Chern class of the tangent bundle of a smooth variety, the cohomology classes

∆λ(c) can be put in relation to homology classes [Pλ] of the generalised polar

varieties.

To a smooth variety V⊆Pnof dimension mwe can associate a vector

bundle e

TV of rank m+ 1 such that for all x∈V,TxV=P(e

TxV).

The proof of the following proposition uses a result of Kempf and Laksov

[KL74, Theorem 10], see also [Ful98, Theorem 14.3] or [Man01, 3.8].

Proposition 8.11 Let V⊆Pnbe an irreducible, smooth variety of dimen-

sion mand let λbe a partition with |λ| ≤ m. Then

∆λ0(c(e

T V )) a[V] = ((−1)|λ|[Pλ]if λ1≤n−m

0else.

Proof. Let Ebe the trivial (n+ 1)-bundle on V,e

NV := E/ e

TV and

π:E→e

NV be the projection map. Let λbe a partition with |λ| ≤ m

and λ1≤n−m. A flag F∈ F determines a partial flag Aof trivial

sub-bundles of Ewith Aicorresponding to Fσi−1for 1 ≤i≤m. Thus

rank(Ai) = σi−1+ 1 = n−m+i−λi. The determinantal locus

Ωλ(A;π) = {x∈V|dim(ker π(x)∩Ai(x)) ≥i, 1≤i≤m}

8.4 Proof of Theorem 7.13 119

studied in [Ful98, Chapter 14] coincides with the generalised polar variety

Pλ(F). Here, by dim(ker π(x)∩Ai(x)) we mean the affine dimension. The

statement of [Ful98, Theorem 14.3] implies that

∆λ(c(e

NV )) a[V] = [Ωλ(A;π)] = [Pλ(F)],

provided Ωλ(A;π) is of pure codimension |λ|. For justifying this, note that

in [Ful98], Ωλ(A;π) is interpreted as a subscheme of Vand its class is an

element of the Chow group A∗(Ωλ(A;π)). However, for generic F∈ F, the

scheme Ωλ(A;π) is multiplicity-free and of the right codimension, cf. Lemma

7.7. Moreover, there is a cycle map A∗(Ωλ(A;π)) →H∗(Ωλ(A;σ)) [Ful98,

Chapter 19], which is compatible with the action of Chern classes.

Let s(e

TV ) := 1/c(e

T V ) and e

TV ∨denote the dual bundle. We have

c(e

NV ) = s(e

TV ) and ci(e

T V ∨) = (−1)ici(e

TV ) [Ful98]. Using Lemma 8.4, we

thus get

∆λ(c(e

NV )) = ∆λ(s(e

TV )) = ∆λ0(c(e

T V ∨)) = (−1)|λ|∆λ0(c(e

T V )).

This shows the assertion in the case λ1≤n−m. If λ1> n −m, then since

NV is an (n−m)-bundle, we have cj(e

NV ) = 0 for j≥λ1, which in turn

implies ∆λ(c(e

NV )) = 0. This completes the proof. 2

We now turn attention to the tangent bundle TV .

Lemma 8.12 Let V⊆Pnbe an irreducible, smooth variety of dimension m

and let λbe a partition with |λ| ≤ m. For the tangent bundle TV we have

∆λ0(c(TV )) a[V] = X

µ⊆λ

µ1≤n−m

(−1)|µ|dm

λµc1(LV)|λ|−|µ|a[Pµ],

where dm

λµ is defined as in Lemma 8.8.

Proof. It is well known (compare [Har95, Chapter 16]) that the tangent

bundle TV of a smooth variety is given by T V ∼

=Hom L∨

V,e

TV/L∨

V.

Taking the direct sum with the trivial bundle E= Hom(L∨

V,L∨

V) we get

TV ⊕E∼

=Hom L∨

V,e

TV/L∨

V⊕E∼

=Hom(L∨

V,e

T V )∼

=LV⊗e

TV.

By the Whitney product formula (see §8.2) and the fact that c(E) = 1 we

obtain

c(TV ) = c(TV ⊕E) = c(LV⊗e

TV ).

Let c(e

TV ) = Qm+1

i=1 (1+γi) be the formal factorisation and set β:= c1(LV).

By Lemma 8.6 we have for a partition µwith |µ| ≤ m

∆µ0(c(e

T V )) = sµ(γ1,...,γm+1).(8.5)

120 Hilbert Polynomial and Degeneracy Loci

On the other hand, it is known that (see [Ful98, Remark 3.2.3b])

c(LV⊗e

TV ) =

m+1

i=1

(1 + γi+β).

Using Lemma 8.6 again, we get for any partition λwith |λ| ≤ m

∆λ0(c(TV )) = ∆λ0(c(LV⊗e

TV )) = sλ(γ1+β,...,γm+1 +β).

By Lemma 8.8 we have

sλ(γ1+β,...,γm+1 +β) = X

µ⊆λ

λµβ|λ|−|µ|sµ(γ1, . . . , γm+1).

Proposition 8.11 and (8.5) now imply for a partition µwith |µ| ≤ m:

sµ(γ)a[V] = ∆µ0(c(e

T V )) a[V] = ((−1)|µ|[Pµ] for µ1≤n−m

0 else.

This finishes the proof. 2

Example 8.13 Let λ= (1k). Then ∆λ0(c) = ck(TV ), the k-th Chern class

of the tangent bundle. By Example 8.9 we have dm

λµ =m−j+1

m−k+1, where

µ= (1j). Plugging this into the formula of Lemma 8.12, we get

ck(TV )a[V] =

j=0

(−1)jm−j+ 1

m−k+ 1c1(LV)k−ja[Pj],

where the [Pj] are the homology classes of the polar varieties. This formula

is just the known expression for Chern classes in terms of polar classes, see

for example [Pie78, Bra00].

Proof of Theorem 7.13. Assume first that Vis irreducible and write c=

c(TV ). We express the Poincar´e dual of the Todd polynomials in terms of

the degeneracy loci, using Lemma 8.10 and Lemma 8.12:

Tm−k(c)a[V] = X

|λ|=m−k

∆λ(b)∆λ0(c)a[V]

|λ|=m−k

∆λ(b)X

µ⊆λ

µ1≤n−m

(−1)|µ|dm

λµc1(LV)m−k−|µ|a[Pµ]

|µ|≤m−k

µ1≤n−m

(−1)|µ|



X

µ⊆λ

|λ|=m−k

∆λ(b)dm

λµ





|{z }

=:δm,k

c1(LV)m−k−|µ|a[Pµ]

8.4 Proof of Theorem 7.13 121

(Recall the definition of δm,k

µin Equation (7.8).) By Corollary 8.3 we obtain

for the k-th coefficient pk(V) of the Hilbert polynomial of V

pk(V) = 1

k!deg c1(LV)k`Tm−k(c)a[V]

k!X

|µ|≤m−k

µ1≤n−m

δm,k

µdeg c1(LV)m−|µ|a[Pµ].

Since capping with c1(LV)m−|µ|corresponds to intersecting with a generic

linear subspace of codimension m− |µ|in V, it follows that the degree

deg c1(LV)m−|µ|a[Pµ]= deg Pµ. This proves the claim for irreducible V.

Now let V=V1∪ ··· ∪ Vsbe the decomposition of Vinto irreducible

components of the same dimension. Let Pi

µdenote the degeneracy locus of

Vicorresponding to µand a generic flag F. Since Vis smooth, the Viare

pairwise disjoint and Pµ=P1

µ∪ ··· ∪ Ps

µ, from which deg Pµ=Pideg Pi

follows. On the other hand, the Hilbert polynomial is additive on the Vi,

which finishes the proof. 2

122 Hilbert Polynomial and Degeneracy Loci

Bibliography

[Alu03] P. Aluffi. Computing characteristic classes of projective schemes.

J. Symbolic Comput., 35(1):3–19, 2003.

[AS00] N. Alon and J. H. Spencer. The probabilistic method. Wiley-

Interscience Series in Discrete Mathematics and Optimization.

Wiley-Interscience [John Wiley & Sons], New York, 2000.

[Bac99] E. Bach. Sheaf cohomology is #P-hard. J. Symbolic Comput.,

27(4):429–433, 1999.

[Bas99] S. Basu. On bounding the Betti numbers and computing the

Euler characteristic of semi-algebraic sets. Discrete Comput.

Geom., 22(1):1–18, 1999.

[Bau02] H. Bauer. Wahrscheinlichkeitstheorie. de Gruyter Lehrbuch.

Walter de Gruyter & Co., Berlin, 2002.

[BC] P. B¨urgisser and F. Cucker. Counting complexity classes

for numeric computations II: Algebraic and semialgebraic

sets. http://www.arxiv.org/abs/cs/cs.CC/0312007. Ex-

tended abstract in Proc. 36th Ann. ACM STOC, pages 475–485,

2004.

[BC04a] P. B¨urgisser and F. Cucker. Counting complexity classes for

numeric computations II: Algebraic and semialgebraic sets. In

Proc. 36th Ann. ACM STOC, pages 475–485, 2004. Full version

at http://www.arxiv.org/abs/cs/cs.CC/0312007.

[BC04b] P. B¨urgisser and F. Cucker. Variations by complexity theo-

rists on three themes of Euler, B´ezout, Betti, and Poincar´e. In

Jan Krajicek, editor, Complexity of computations and proofs,

volume 13 of Quaderni di Matematica, pages 73–151. Aracne,

2004.

[BCL04] P. B¨urgisser, F. Cucker, and M. Lotz. The complexity to com-

pute the Euler characteristic of complex varieties. C.R. Acad.

Sc. Paris, Ser I 339:371–376, 2004.

124 BIBLIOGRAPHY

[BCL05] P. B¨urgisser, F. Cucker, and M. Lotz. Counting complexity

classes for numeric computations III: Complex projective sets.

Foundations of Computational Mathematics, 2005. To appear.

[BCR91] A.M. Bigatti, M. Caboara, and L. Robbiano. On the compu-

tation of Hilbert-Poincar´e series. Appl. Algebra Engrg. Comm.

Comput., 2(1):21–33, 1991.

[BCS97] P. B¨urgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Com-

plexity Theory, volume 315 of Grundlehren der mathematischen

Wissenschaften. Springer Verlag, 1997.

[BCSS96] L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings

for the Problem “P6=NP ?”. In The mathematics of numerical

analysis, number 32 in Lectures in Applied Mathematics, pages

125–144. Amer. Math. Soc., 1996.

[BCSS98] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and

Real Computation. Springer, 1998.

[Bel97] R. Bellman. Introduction to matrix analysis. SIAM, Philadel-

phia, PA, 1997.

[BGHM01] B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop. Polar va-

rieties and efficient real elimination. Math. Z., 238(1):115–144,

2001.

[BGHP04] B. Bank, M. Giusti, J. Heintz, and L. M. Pardo. Generalized

polar varieties: Geometry and algorithms. 2004. Preprint.

[Big97] A. M. Bigatti. Computation of Hilbert-Poincar´e series. J. Pure

Appl. Algebra, 119(3):237–253, 1997.

[BK81] E. Brieskorn and H. Kn¨orrer. Ebene algebraische Kurven.

Birkh¨auser Verlag, Basel, 1981.

[BL02] P. B¨urgisser and M. Lotz. Lower bounds on the bounded coef-

ficient complexity of bilinear maps. In Proc. 43rd FOCS, Van-

couver, pages 658–668, 2002.

[BL04] P. B¨urgisser and M. Lotz. Lower bounds on the bounded co-

efficient complexity of bilinear maps. J. ACM, 51(3):464–482,

2004.

[BL05] P. B¨urgisser and M. Lotz. The complexity of computing the

Hilbert polynomial of smooth equidimensional complex projec-

tive varieties. www.arxiv.org/abs/cs/cs.CC/0502044, 2005.

BIBLIOGRAPHY 125

[BM93] D. Bayer and D. Mumford. What can be computed in algebraic

geometry? In Computational algebraic geometry and commu-

tative algebra (Cortona, 1991), Sympos. Math., XXXIV, pages

1–48. Cambridge Univ. Press, Cambridge, 1993.

[Bor77] A.B. Borodin. On relating time and space to size and depth.

SIAM J. Comp., 6:733–744, 1977.

[Bou70] N. Bourbaki. El´ement de Math´ematique. Alg`ebre, volume I. Her-

mann, 1970.

[BPR03] S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Alge-

braic Geometry, volume 10 of Algorithms and Computation in

Mathematics. Springer-Verlag, 2003.

[Bra00] J.P. Brasselet. From Chern classes to Milnor classes—a history

of characteristic classes for singular varieties. In Singularities—

Sapporo 1998, volume 29 of Adv. Stud. Pure Math., pages 31–52.

Kinokuniya, Tokyo, 2000.

[Bre97] G. E. Bredon. Topology and Geometry, volume 139 of Graduate

Texts in Mathematics. Springer-Verlag, New York, 1997.

[BS83] W. Baur and V. Strassen. The complexity of partial derivatives.

Theoret. Comp. Sci., 22:317–330, 1983.

[BS88] D. Bayer and M. Stillman. On the complexity of computing

syzygies. J. Symb. Comp., 6:135–147, 1988.

[BS92] D. Bayer and M. Stillman. Computation of Hilbert functions.

J. Symb. Comp., 14:31–50, 1992.

[BSS89] L. Blum, M. Shub, and S. Smale. On a theory of computation

and complexity over the real numbers. Bull. Amer. Math. Soc.,

21:1–46, 1989.

[Buc65] B. Buchberger. Ein Algorithmus zum Auffinden der Basise-

lemente des Restklassenringes nach einem nulldimensionalen

Polynomideal. PhD thesis, Universit¨at Innsbruck, 1965.

[Buc85] B. Buchberger. Gr¨obner bases: an algorithmic method in poly-

nomial ideal theory. In N.K. Bose, editor, Recent trends in multi-

dimensional system theory, pages 184–232. K. Reidel publishing

company, Dordrecht, Holland, 1985.

[B¨ur00] P. B¨urgisser. Cook’s versus Valiant’s hypothesis. Theoret.

Comp. Sci., 235:71–88, 2000.

126 BIBLIOGRAPHY

[CCS99] A. M. Cohen, H. Cuypers, and H. Sterk. Some tapas of computer

algebra, volume 4 of Algorithms and Computation in Mathemat-

ics. Springer-Verlag, Berlin, 1999.

[CG97] F. Cucker and D.Yu. Grigoriev. On the power of real Turing

machines over binary inputs. SIAM J. Comp., 26:243–254, 1997.

[CGH89] L. Caniglia, A. Galligo, and J. Heintz. Some new effectivity

bounds in computational geometry. In Proc. 6th AAECC, num-

ber 357 in LNCS, pages 131–151. Springer Verlag, 1989.

[CH31] R. Courant and D. Hilbert. Methoden der mathematischen

Physik. I. Springer-Verlag, Berlin, 1931. Zweite Auflage.

[Cha98] B. Chazelle. A spectral approach to lower bounds with appli-

cations to geometric searching. SIAM Journal on Computing,

27(2):545–556, 1998.

[Cha00] B. Chazelle. The discrepancy method. Cambridge University

Press, Cambridge, 2000.

[Che46] S-S. Chern. Characteristic classes of Hermitian manifolds. An-

nals of Mathematics (2), 47:85–121, 1946.

[CK95] F. Cucker and P. Koiran. Computing over the reals with addition

and order: Higher complexity classes. J. Compl., 11:358–376,

1995.

[CKK+95] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and

K. Werther. On real Turing machines that toss coins. In Proc.

27th ACM STOC, Las Vegas, pages 335–342, 1995.

[CLO98] D. Cox, J. Little, and D. O’Shea. Using algebraic geometry,

volume 185 of Graduate Texts in Mathematics. Springer-Verlag,

New York, 1998.

[CoC] CoCoATeam. CoCoA: a system for doing Computations in Com-

mutative Algebra. Available at http://cocoa.dima.unige.it.

[Coo71] S.A. Cook. The complexity of theorem proving procedures. In

Proc. 3rd ACM STOC, pages 151–158, 1971.

[Cra46] H. Cram´er. Mathematical Methods of Statistics, volume 9 of

Princeton Mathematical Series. Princeton University Press,

1946.

[Cuc92] F. Cucker. PR6= NCR.J. Compl., 8:230–238, 1992.

BIBLIOGRAPHY 127

[DE02] W. Decker and D. Eisenbud. Sheaf algorithms using the ex-

terior algebra. In Computations in algebraic geometry with

Macaulay 2, volume 8 of Algorithms Comput. Math., pages 215–

249. Springer, Berlin, 2002.

[DFGS91] A. Dickenstein, N. Fitchas, M. Giusti, and C. Sessa. The mem-

bership problem for unmixed polynomial ideals is solvable in

single exponential time. Discrete Appl. Math., 33(1-3):73–94,

1991.

[Dim92] A. Dimca. Singularities and Topology of Hypersurfaces. Univer-

sitext. Springer Verlag, 1992.

[DZ98] A. Dembo and O. Zeitouni. Large deviations techniques and

applications, volume 38 of Applications of Mathematics (New

York). Springer-Verlag, New York, 1998.

[Eis95] D. Eisenbud. Commutative algebra, volume 150 of Graduate

Texts in Mathematics. Springer-Verlag, New York, 1995.

[Fel71] W. Feller. An introduction to probability theory and its applica-

tions, volume 2. John Wiley & Sons, 1971.

[FH91] W. Fulton and J. Harris. Representation Theory. Number 129

in GTM. Springer Verlag, 1991.

[FL81] W. Fulton and R. Lazarsfeld. Connectivity and its applica-

tions in algebraic geometry. In Algebraic geometry (Chicago,

Ill., 1980), volume 862 of Lecture Notes in Math., pages 26–92.

Springer, Berlin, 1981.

[For97] L. Fortnow. Counting complexity. In Complexity theory retro-

spective, II, pages 81–107. Springer, New York, 1997.

[Ful89] W. Fulton. Algebraic Curves. Advanced Book Classics. Addison-

Wesley Publishing Company Advanced Book Program, Red-

wood City, CA, 1989.

[Ful93] W. Fulton. Introduction to Toric Varieties. Annals of Math.

Studies. Princeton University Press, 1993.

[Ful97] W. Fulton. Young tableaux, volume 35 of London Mathematical

Society Student Texts. Cambridge University Press, Cambridge,

1997.

[Ful98] W. Fulton. Intersection Theory, volume 2 of Ergebnisse der

Mathematik und ihrer Grenzgebiete. Springer-Verlag, Berlin,

1998.

128 BIBLIOGRAPHY

[Gat86] J. von zur Gathen. Parallel arithmetic computations: a survey.

In Proc. 12th Symp. Math. Found. Comput. Sci., Bratislava,

number 233 in LNCS, pages 93–112, 1986.

[GG03] J. von zur Gathen and J. Gerhard. Modern Computer Algebra.

Cambridge University Press, 2003.

[GH91] M. Giusti and J. Heintz. Algorithmes—disons rapides—

pour la d´ecomposition d’une vari´et´e alg´ebrique en composantes

irr´eductibles et ´equidimensionnelles. In Effective methods in al-

gebraic geometry (Castiglioncello, 1990), volume 94 of Progr.

Math., pages 169–194. Birkh¨auser Boston, Boston, MA, 1991.

[GH93] M. Giusti and J. Heintz. La d´etermination des points isol´es et

de la dimension d’une variet´e alg´ebrique peut se faire en temps

polynomial. In D. Eisenbud and L. Robbiano, editors, Proc.

Cortona Conference on Computational Algebraic Geometry and

Commutative Algebra. Cambridge University Press, 1993.

[Giu84] M. Giusti. Some effectivity problems in polynomial ideal theory.

In EUROSAM 84 (Cambridge, 1984), volume 174 of Lecture

Notes in Comput. Sci., pages 159–171. Springer, Berlin, 1984.

[GKP94] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete math-

ematics. Addison-Wesley Publishing Company, Reading, MA,

1994.

[GM88] M. Goresky and R. MacPherson. Stratified Morse theory, vol-

ume 14 of Ergebnisse der Mathematik und ihrer Grenzgebiete

(3). Springer-Verlag, Berlin, 1988.

[Goo94] J. B. Goode. Accessible telephone directories. J. Symbolic Logic,

59(1):92–105, 1994.

[GP02] G.-M. Greuel and G. Pfister. ASingular introduction to com-

mutative algebra. Springer-Verlag, Berlin, 2002.

[GPS01] G.-M. Greuel, G. Pfister, and H. Sch¨onemann. Singular 2.0. A

Computer Algebra System for Polynomial Computations, Cen-

tre for Computer Algebra, University of Kaiserslautern, 2001.

http://www.singular.uni-kl.de.

[GS] D.R. Grayson and M.E. Stillman. Macaulay 2, a soft-

ware system for research in algebraic geometry. Available at

http://www.math.uiuc.edu/Macaulay2/.

[GVL96] G. H. Golub and C. Van Loan. Matrix Computations. The John

Hopkins University Press, Baltimore, 1996.

BIBLIOGRAPHY 129

[Har77] R. Hartshorne. Algebraic Geometry. GTM. Springer Verlag,

1977.

[Har95] J. Harris. Algebraic Geometry, volume 133 of Graduate Texts in

Mathematics. Springer-Verlag, New York, 1995.

[Hat02] A. Hatcher. Algebraic Topology. Cambridge University Press,

Cambridge, 2002.

[Hir75] H. Hironaka. Triangulation of algebraic sets. In Algebraic geom-

etry (Proc. Sympos. Pure Math., Vol. 29, Humboldt State Univ.,

Arcata, Calif., 1974), volume 29 of Proceedings of Symposia in

Pure Mathematics, pages 165–185. Amer. Math. Soc., 1975.

[Hir95] F. Hirzebruch. Topological methods in algebraic geometry. Clas-

sics in Mathematics. Springer-Verlag, Berlin, 1995.

[HS82] J. Heintz and C.P. Schnorr. Testing polynomials which are hard

to compute. In Logic and Algorithmic: An international Sym-

posium held in honor of Ernst Specker, pages 237–254. Monogr.

No. 30 de l’Enseign. Math., 1982.

[Huy86] D.T. Huyn. A superexponential lower bound for Gr¨obner bases

and Church-rosser commutative Thue systems. Information and

Control, 68:196–206, 1986.

[Iit82] S. Iitaka. Algebraic geometry, volume 76 of Graduate Texts in

Mathematics. Springer-Verlag, New York, 1982.

[IM83] O.H. Ibarra and S. Moran. Equivalence of straight-line pro-

grams. J. ACM, 30:217–228, 1983.

[JR04] M.J. Jansen and K.W. Regan. Towards arithmetical lower

bounds with unbounded coefficients. 2004. Preprint.

[JSV01] M.R. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time

approximation algorithm for the permanent of a matrix with

non-negative entries. In Proceedings of the Thirty-Third An-

nual ACM Symposium on Theory of Computing, pages 712–721

(electronic), New York, 2001. ACM.

[Kal87] E. Kaltofen. Factorization of polynomials given by straight-line

programs. In Adv. Comput. Res. In Press, 1987.

[KL72] S. L. Kleiman and D. Laksov. Schubert calculus. Amer. Math.

Monthly, 79:1061–1082, 1972.

[KL74] G. Kempf and D. Laksov. The determinantal formula of Schu-

bert calculus. Acta Math., 132:153–162, 1974.

130 BIBLIOGRAPHY

[Kle74] S. L. Kleiman. The transversality of a general translate. Com-

positio Math., 28:287–297, 1974.

[Knu98] D.E. Knuth. The Art of Computer Programming, volume 2:

semi-numerical algorithms. Addison-Wesley, 1998.

[Koi94] P. Koiran. Computing over the reals with addition and order.

Theoret. Comp. Sci., 133:35–47, 1994.

[Koi97a] P. Koiran. Elimination of constants from machines over alge-

braically closed fields. J. Compl., 13:65–82, 1997.

[Koi97b] P. Koiran. Randomized and deterministic algorithms for the

dimension of algebraic varieties. In Proc. 38th FOCS, pages

36–45, 1997.

[Koi97c] P. Koiran. A weak version of the Blum, Shub & Smale model.

J. Comp. Syst. Sci., 54:177–189, 1997.

[Koi99a] P. Koiran. Elimination of parameters in the polynomial hierar-

chy. Theoret. Comp. Sci., 215:289–304, 1999.

[Koi99b] P. Koiran. The real dimension problem is NPR-complete.

J. Compl., 15(2):227–238, 1999.

[Koi00a] P. Koiran. Circuits versus trees in algebraic complexity. In Proc.

STACS 2000, number 1770 in LNCS, pages 35–52. Springer Ver-

lag, 2000.

[Koi00b] P. Koiran. The complexity of local dimensions for constructible

sets. J. Compl., 16(1):311–323, 2000.

[Kol88] J. Koll´ar. Sharp effective Nullstellensatz. J. Amer. Math. Soc.,

1(4):963–975, 1988.

[KP94] T. Krick and L.M. Pardo. Une approche informatique pour

l’approximation diophantienne. C.R. Acad. Sc. Paris, 318:407–

412, 1994.

[KPS01] T. Krick, L. M. Pardo, and M. Sombra. Sharp estimates for

the arithmetic Nullstellensatz. Duke Math. J., 109(3):521–598,

2001.

[Kri04] T. Krick. Straight-line Programs in Polynomial Equation Solv-

ing. In R. Olver F. Cucker, R. DeVore and E. S¨uli, editors,

Foundations of Computational Mathematics, Minneapolis 2002,

volume 312 of LMS Lecture Notes, pages 96–136. Cambridge,

2004.

BIBLIOGRAPHY 131

[Kun74] H.T. Kung. On computing reciprocals of power series.

Num. Math., 22:341–348, 1974.

[Lak76] I. Lakatos. Proofs and refutations: the logic of mathematical

discovery. Cambridge University Press, 1976.

[Lak91] Y. N. Lakshman. A single exponential bound on the complex-

ity of computing Gr¨obner bases of zero-dimensional ideals. In

Effective methods in algebraic geometry (Castiglioncello, 1990),

volume 94 of Progr. Math., pages 227–234. Birkh¨auser Boston,

Boston, MA, 1991.

[Lev73] L.A. Levin. Universal search problems. Problems of Information

Transmission, 9:265–266, 1973.

[LL91] Y. N. Lakshman and D. Lazard. On the complexity of zero-

dimensional algebraic systems. In Effective methods in algebraic

geometry (Castiglioncello, 1990), volume 94 of Progr. Math.,

pages 217–225. Birkh¨auser Boston, Boston, MA, 1991.

[Lok95] S.V. Lokam. Spectral methods for matrix rigidity with applica-

tions to size-depth tradeoffs and communication complexity. In

Proc. 36th FOCS, pages 6–15, 1995.

[LT91] M. Ledoux and M. Talagrand. Probability in Banach Spaces,

volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete,

3. Folge. Springer Verlag, 1991.

[Mac27] F.S. Macaulay. Some properties of enumeration in the theory of

modular systems. Proc. London Math. Soc., 26:531–555, 1927.

[Mac95] I. G. Macdonald. Symmetric functions and Hall polynomials.

Oxford Mathematical Monographs. The Clarendon Press Oxford

University Press, New York, 1995.

[Man01] L. Manivel. Symmetric functions, Schubert polynomials and de-

generacy loci, volume 6 of SMF/AMS Texts and Monographs.

American Mathematical Society, Providence, RI, 2001.

[Mat86] H. Matsumura. Commutative Ring Theory. Cambridge Univer-

sity Press, 1986.

[May97] E.W. Mayr. Some Complexity Results for Polynomial Ideals.

J. Compl., 13:303–325, 1997.

[Mee00] K. Meer. Counting problems over the reals. Theoret. Comp.

Sci., 242:41–58, 2000.

132 BIBLIOGRAPHY

[Mic89] C. Michaux. Une remarque `a propos des machines sur Rintro-

duites par Blum, Shub et Smale. C. R. Acad. Sci. Paris, 309,

S´erie I:435–437, 1989.

[MM82] E.W. Mayr and A.R. Meyer. The complexity of the word

problem for commutative semigroups and polynomial ideals.

Adv. Math., 46:305–329, 1982.

[MM83] F. Mora and H.M. M¨oller. The computation of the Hilbert

function. In EUROCAL, number 162 in LNCS, pages 157–167.

Springer Verlag, 1983.

[Mor73] J. Morgenstern. Note on a lower bound of the linear complexity

of the fast Fourier transform. J. ACM, 20:305–306, 1973.

[MS74] J. Milnor and J.D. Stasheff. Characteristic classes. Princeton

University Press, Princeton, N. J., 1974.

[Mum76] D. Mumford. Algebraic Geometry I: Complex Projective Vari-

eties. Springer Verlag, 1976.

[NW95] N. Nisan and A. Wigderson. On the complexity of bilinear forms.

In Proc. of the 27th ACM Symposium on the Theory of Com-

puting, pages 723–732, 1995.

[Pap94] C.H. Papadimitriou. Computational Complexity. Addison-

Wesley, 1994.

[Pie78] R. Piene. Polar classes of singular varieties. Ann. Sci. ´

Ecole

Norm. Sup. (4), 11(2):247–276, 1978.

[Poi95] B. Poizat. Les Petits Cailloux. Number 3 in Nur Al-Mantiq

War-Ma’rifah. Al´eas, Lyon, 1995.

[Pud98] P. Pudl´ak. A note on the use of determinant for proving lower

bounds on the size of linear circuits. ECCC Report, 42, 1998.

[Raz02] R. Raz. On the complexity of matrix product. In Proc. 34th

STOC, pages 144–151, 2002. Also available as ECCC Report

12, 2002.

[Raz03] R. Raz. On the complexity of matrix product. SIAM J. Com-

put., 32(5):1356–1369 (electronic), 2003.

[Ren92] J. Renegar. On the computational complexity and geometry of

the first-order theory of the reals. part I, II, III. J. Symb. Comp.,

13(3):255–352, 1992.

BIBLIOGRAPHY 133

[Rud04] S. Rudich. Complexity theory: from G¨odel to Feynman. In

Computational complexity theory, volume 10 of IAS/Park City

Math. Ser., pages 5–87. Amer. Math. Soc., Providence, RI, 2004.

[Sch79] H. Schubert. Kalk¨ul der abz¨ahlenden Geometrie. B. G. Teubner,

Leipzig, 1879.

[Sch80] J.T. Schwartz. Fast probabilistic algorithms for verification of

polynomial identities. J. ACM, 27:701–717, 1980.

[Sev02] F. Severi. Sulle intersezioni delle varieta algebriche e sopra i

loro caratteri e singolarita proiettive. Mem. Accad. Sci. Torino,

52(2):61–118, 1902.

[Sha74] I.R. Shafarevich. Basic Algebraic Geometry. Springer Verlag,

1974.

[Sie72] M. Sieveking. An algorithm for division of power series. Com-

puting, 10:153–156, 1972.

[Str73a] V. Strassen. Die Berechnungskomplexit¨at von elementar-

symmetrischen Funktionen und von Interpolationskoeffizienten.

Num. Math., 20:238–251, 1973.

[Str73b] V. Strassen. Vermeidung von Divisionen. Crelles J. Reine

Angew. Math., 264:184–202, 1973.

[Stu02] B. Sturmfels. Solving systems of polynomial equations, vol-

ume 97 of CBMS Regional Conference Series in Mathematics.

Published for the Conference Board of the Mathematical Sci-

ences, Washington, DC, 2002.

[Tra96] C. Traverso. Hilbert functions and the Buchberger algorithm.

J. Symbolic Comput., 22(4):355–376, 1996.

[Val76] L.G. Valiant. Graph theoretic properties in computational com-

plexity. J. Comp. Syst. Sci., 13:278–285, 1976.

[Val77] L.G. Valiant. Graph theoretic arguments in low-level complex-

ity. Number 53 in LNCS, pages 162–176. Springer Verlag, 1977.

[Val79a] L.G. Valiant. The complexity of computing the permanent. The-

oret. Comp. Sci., 8:189–201, 1979.

[Val79b] L.G. Valiant. The complexity of enumeration and reliability

problems. SIAM J. Comp., 8:410–421, 1979.

[Vas98] W.V. Vasconcelos. Computational methods in commutative al-

gebra and algebraic geometry, volume 2 of Algorithms and Com-

putation in Mathematics. Springer-Verlag, Berlin, 1998.

134 BIBLIOGRAPHY

[vL99] J. H. van Lint. Introduction to coding theory, volume 86 of

Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1999.

[Wal00] U. Walther. Algorithmic computation of de Rham cohomology

of complements of complex affine varieties. J. Symbolic Comput.,

29(4-5):795–839, 2000.

[Wal02] U. Walther. D-modules and cohomology of varieties. In Compu-

tations in algebraic geometry with Macaulay 2, volume 8 of Al-

gorithms Comput. Math., pages 281–323. Springer, Berlin, 2002.

[Yao92] A.C. Yao. Algebraic decision trees and Euler characteristic. In

Proc. 33rd FOCS, 1992.