§2. Problem of Algebra  Lecture 0  Page 1

Lecture 0 INTRODUCTION

This lecture gives an overview of the central problems that concern us. Specifically, we identify three families of “Fundamental Problems” in algorithmic algebra. We also briefly discuss the complexity theoretic background.

All our rings will contain unity which is denoted 1 (and distinct from 0). They are commutative except in the case of matrix rings.

§1. Basic Rings

The main algebraic structures of interest are:

= natural numbers 0, 1, 2,…
= integers
= rational numbers
= reals
= complex numbers
R[X] = polynomial ring in d ≥ 1 variables X = (X_{1},…, X_{d})

with coefficients from a ring R.

For a univariate polynomial P ∈ R[X], we let deg(P) and lead(P) denote its degree and leading coefficient. If P = 0 then by definition, deg(P) = −∞ and lead(P) = 0; otherwise deg(P) ≥ 0 and lead(P) ≠ 0. We say P is a (respectively) integer, rational, real or complex polynomial, depending on whether R is , , or .

The basic algebra we assume can be obtained from classics such as van der Waerden [14] or Zariski-Samuel [17].

§2. Fundamental Problem of Algebra

Consider an integer polynomial

P (X) = ∑_{i=0}^{n} a_{i}X^{i}  (a_{i} ∈ , a_{n} ≠ 0).  (1)

Many of the oldest problems in mathematics stem from attempts to solve the equation

P (X) = 0,  (2)

i.e., to find numbers α such that P (α) = 0. We call such an α a solution of equation (2); alternatively, α is a root or zero of the polynomial P (X). By definition, an algebraic number is a zero of some polynomial P ∈ [X]. The Fundamental Theorem of Algebra states that every non-zero polynomial P (X) ∈ [X] has a root α ∈ . Put another way, is algebraically closed.

D’Alembert first formulated this theorem in 1746 but Gauss gave the first complete proof in his 1799 doctoral thesis at Helmstedt. We present a modern proof in Lecture 5, via real closed fields. It follows that there are n (not necessarily distinct) complex numbers α_{1},…, α_{n} ∈ such that the polynomial in (1) is equal to

P (X) ≡ a_{n} ∏_{i=1}^{n}(X − α_{i}).  (3)

To see this, suppose α_{1} is a root of P (X) as guaranteed by the Fundamental Theorem. Using the synthetic division algorithm to divide P (X) by X − α_{1}, we get

P (X) = Q_{1}(X) · (X − α_{1}) + β_{1}

where Q_{1}(X) is a polynomial of degree n − 1 with coefficients in and β_{1} ∈ . On substituting X = α_{1}, the left-hand side vanishes and the right-hand side becomes β_{1}. Hence β_{1} = 0. If n = 1, then Q_{1}(X) = a_{n} and we are done. Otherwise, this argument can be repeated on Q_{1}(X) to yield equation (3).

The computational version of the Fundamental Theorem of Algebra is the problem of finding roots of a univariate polynomial. We dub this the Fundamental (Computational) Problem of Algebra. The Fundamental theorem is about complex numbers. For our purposes, we slightly extend the context as follows. If R_{0} ⊆ R_{1} are rings, the Fundamental Problem for the pair (R_{0}, R_{1}) is this:

Given P (X) ∈ R_{0}[X], solve the equation P (X) = 0 in R_{1}.

We are mainly interested in cases where ⊆ R_{0} ⊆ R_{1} ⊆ . In practice, the three main versions are where (R_{0}, R_{1}) equals ( , ), ( , ) and ( , ), respectively. We call them the Diophantine, real and complex versions (respectively) of the Fundamental Problem.

What does it mean “to solve P (X) = 0 in R_{1}”? The most natural interpretation is that we want to enumerate all the roots of P that lie in R_{1}. Besides this enumeration interpretation, we consider two other possibilities: the existential interpretation simply wants to know if P has a root in R_{1}, and the counting interpretation wants to know the number of such roots. To enumerate roots, we must address the representation of these roots. For instance, we will study a representation via “isolating intervals”.

It is interesting to recall another classical version of the Fundamental Problem. Let R_{0} = and R_{1} denote the complex subring comprising all those elements that can be obtained by applying a finite number of field operations (ring operations plus division by non-zero) and taking nth roots (n ≥ 2), starting from . This is the famous “solution by radicals version” of the Fundamental Problem. It is well known that when deg P = 2, there is always a solution in R_{1}. What if deg P > 2? This was the major research question of the 16th century, challenging the best mathematicians of its day. We now know that solution by radicals exists for deg P = 3 (Tartaglia, 1499-1557) and deg P = 4 (variously ascribed to Ferrari (1522-1565) or Bombelli (1579)). These methods were widely discussed, especially after they were published by Cardan (1501-1576) in his classic Ars magna (1545). This classic was the algebra book until Descartes. The case deg P = 5 was finally resolved when Abel proved that there is no general solution for deg P ≥ 5. Ruffini had a prior though incomplete solution. These historical comments can be pursued more fully in, for example, Struik’s volume [13]. Recent work of Miller and Landau has revisited these question from a complexity viewpoint.

§3. Algebraic Geometry  Lecture 0  Page 3

Remarks:. The Fundamental Problem of algebra used to come under the rubric “theory of equations”, which nowadays is absorbed into other areas of mathematics. In these lectures, we are interested in general and effective methods, and we are mainly interested in real solutions. It is worth observing that these fundamental problems are also fundamental in areas such as computational geometry: most of the basic (“constant time”) operations assumed in geometric algorithms are instances of the Fundamental Problem.

§3. Fundamental Problem of Classical Algebraic Geometry

We look beyond the Fundamental Problem of algebra. Again, fix two rings R_{0} ⊆ R_{1}. For this section, it is convenient to assume ⊆ R_{0} ⊆ R_{1} ⊆ .

First consider a bivariate polynomial

P (X, Y) ∈ R_{0}[X, Y].  (4)

Let Zero(P) denote the set of R_{1}-solutions of the equation P = 0, i.e., (α, β) ∈ R_{1}^{2} such that P (α, β) = 0. The set Zero(P), called the zero set of P, is generally an infinite set. In case R_{1} = , the set Zero(P) is a planar curve that can be plotted and visualized. Just as solutions to equation (2) are called algebraic numbers, the zero sets of bivariate integer polynomials are called algebraic curves. But there is no reason to stop at two variables. For d ≥ 3 variables, the zero set of an integer polynomial in d variables is called an algebraic hypersurface: we shall reserve the term surface for the special case d = 3.

Given two surfaces defined by the equations P (X, Y, Z) = 0 and Q(X, Y, Z) = 0, their intersection is generally a curvilinear set of triples (α, β, γ) ∈ R_{1}^{3}, consisting of all simultaneous solutions to the pair of simultaneous equations P = 0, Q = 0. We may extend our previous notation and write Zero(P, Q) for this intersection. More generally, we want the simultaneous solutions to a system of m ≥ 1 polynomial equations in d ≥ 1 variables:

P_{1} = 0 ; P_{2} = 0 ; ⋮ ; P_{m} = 0 }  (P_{i} ∈ R_{0}[X_{1},…, X_{d}] = R_{0}[X])  (5)

A point (α_{1},…, α_{d}) ∈ R_{1}^{d} is called a solution of the system of equations (5) or a zero of the set {P_{1},…, P_{m}} provided P_{i}(α_{1},…, α_{d}) = 0 for i = 1,…, m. In general, for any subset J ⊆ R_{0}[X], let Zero(J) ⊆ R_{1}^{d} denote the zero set of J. To denote the dependence on R_{1}, we may also write Zero_{R_{1}}(J). If R_{1} is a field, we also call a zero set an algebraic set. (When we refer to a zero set as an algebraic set, we automatically assume R_{1} is a field.) The term variety is reserved for irreducible algebraic sets, but that comes later. Since the primary objects of study in classical algebraic geometry are algebraic sets, we may call the problem of solving the system (5) the Fundamental (Computational) Problem of classical algebraic geometry.

If the degree of each P_{i} is one in (5), we are looking at a system of linear equations. One might call this is the Fundamental (Computational) Problem of linear algebra. Of course, linear systems are rather well understood and their solution will form the basis for solving nonlinear systems.

Again, we have three natural meaning to the expression “solving the system of equations (5) in R_{1}”: (i) The existential interpretation asks if Zero(P_{1},…, P_{m}) is empty. (ii) The counting interpretation asks for the cardinality of the zero set. In case the cardinality is “infinity”, we could refine the question by asking for the dimension of the zero set. (iii) Finally, the enumeration interpretation poses no problems when there are only finitely many solutions. This is because the coordinates of these solutions turn out to be algebraic numbers and so they could be explicitly enumerated. It becomes problematic when the zero set is infinite. Luckily, when R_{1} = or , such zero sets are well-behaved topologically, and consists of a finite number of connected components. (For that matter, counting can be interpreted to mean counting the number of connected components.) A typical interpretation of “enumeration” is “give at least one sample point from each connected component”. For real planar curves, this interpretation is useful for plotting the curve since the usual method is to “trace” each component by starting from any point in the component.

Note that we have moved from algebra (numbers) to geometry (curves and surfaces). In recogition of this, we adopt the geometric language of “points and space”. The set R_{1}^{d} (d-fold Cartesian product of R_{1}) is called the d-dimensional affine space of R_{1}, denoted ^{d}(R_{1}). Elements of ^{d}(R_{1}) are called d-points or simply points. Our zero sets are subsets of this affine space ^{d}(R_{1}). In fact, ^{d}(R_{1}) can be given a topology (the Zariski topology) in which zero sets are the closed sets.

There are highly classical techniques via elimination theory for solving these Fundamental problems. In recent years, Wu Wen-tsun exploited Ritt’s idea of characteristic sets to give new methods for solving (5) rather efficiently in the complex case, R_{1} = . These methods turn out to be useful for proving theorems in elementary geometry as well. But many applications are confined to the real case (R_{1} = ). It is a general phenomenon that real algebraic sets do not behave as regularly as the corresponding complex ones. This is already evident in the univariate case: the Fundamental Theorem of Algebra fails for real solutions. In view of this, the classical literature usually treats the complex case. There is now a fast growing body of results is on real algebraic sets.

Another step traditionally taken to “regularize” algebraic sets is to consider projective sets, which abolish the distinction between finite and infinite points. A projective d-dimensional point is simply an equivalence class of the set ^{d+1}(R_{1}) \ {(0,…, 0)}, where two non-zero (d + 1)-points are equivalent if one is a constant multiple of the other. We use ^{d}(R_{1}) to denote the d-dimensional projective space of R_{1}.

Semialgebraic sets. The real case admits a generalization of the system (5). We can view (5) as a conjunction of basic predicates of the form “P_{i} = 0”:

(P_{1} = 0) ∧ (P_{2} = 0) ∧ ⋯ ∧ (P_{m} = 0).

We generalize this to an arbitrary Boolean combination of basic predicates, where a basic predicate now has the form (P = 0) or (P > 0) or (P ≥ 0). For instance,

((P = 0) ∧ (Q > 0)) ∨ ¬(R ≥ 0)

is a Boolean combination of three basic predicates where P, Q, R are polynomials. The set of real solutions to such a predicate is called a semi-algebraic set (or a Tarski set). We have effective methods of computing semi-algebraic sets, thanks to Tarski, Collins and others. Recent work by Grigoryev, Renegar and many others has reduced the complexity of these algorithms from double exponential time to single exponential space. The application of semialgebraic sets to robotics was clearly demonstrated in the seminal paper of Schwartz and Sharir [12].

§4. Ideal Theory  Lecture 0  Page 5

§4. Fundamental Problem of Ideal Theory

Algebraic sets are basically geometric objects: witness the language of “space, points, curves, surfaces”. Now we switch from the geometric viewpoint (back!) to an algebraic one. One of the beauties of this subject is this interplay between geometry and algebra.

We continue to fix two rings ⊆ R_{0} ⊆ R_{1} ⊆ . A polynomial P (X) ∈ R_{0}[X] = R_{0}[X_{1},…, X_{d}] is said to vanish on a subset U ⊆ ^{d}(R_{1}) if for all a ∈ U, P (a) = 0. Define

Ideal(U) ⊆ R_{0}[X]

to comprise all polynomials P ∈ R_{0}[X] that vanishes on U. The set Ideal(U) is an ideal. Recall that a non-empty subset J ⊆ R of a ring R is an ideal if it satisfies the properties

1. a, b ∈ J ⇒ a − b ∈ J

2. c ∈ R, a ∈ J ⇒ ca ∈ J.

For any a_{1},…, a_{m} ∈ R and R′ ⊇ R, the set (a_{1},…, a_{m})_{R′} defined by

(a_{1},…, a_{m})_{R′} :={∑_{i=1}^{m} a_{i}b_{i} : b_{1},…, b_{m} ∈ R′}

is an ideal, the ideal generated by a_{1},…, a_{m} in R′. Usually, we omit the subscript R′ if this is understood.

The Fundamental Problem of classical algebraic geometry (see Equation (5)) can be viewed as computing (some characteristic property of) the zero set defined by the input polynomials P_{1},…, P_{m}. But note that

Zero(P_{1},…, P_{m}) = Zero(I)

where I is the ideal generated by P_{1},…, P_{m}. Hence we might as well assume that the input to the Fundamental Problem is the ideal I (represented by a set of generators). This suggests that we view ideals to be the algebraic analogue of zero sets. So the algebraic analogue of the Fundamental Problem of classical algebraic geometry (under the enumeration interpretation) is to “enumerate all the polynomials in the ideal (P_{1},…, P_{m})”. Of course, this is impossible. But we effectively know a set S if, for any purported member x, we can decisively say whether or not x is a member of S. Thus we reformulate the enumerative algebraic Fundamental Problem as the Ideal Membership Problem:

Given P_{0}, P_{1},…, P_{m} ∈ R_{0}[X], is P_{0} in (P_{1},…, P_{m})?

Where does R_{1} come in? Well, the ideal (P_{1},…, P_{m}) is assumed to be generated in R_{1}[X]. We shall introduce effective methods to solve this problem. Here, the technique of Gröbner bases (as popularized by Buchberger) is notable. Historical support for the claim that the ideal membership problem is fundamental comes from Van der Waerden [14, volume 2, p.159] who calls it the “main problem of ideal theory in polynomial rings”.

How general are the ideals of the form (P_{1},…, P_{m})? The only ideals that might not be of this form are those that cannot be generated by a finite number of polynomials. The answer is provided by what is perhaps the starting point of modern algebraic geometry: the Hilbert Basis Theorem. A ring R is called Noetherian if all its ideals are finitely generated. For example, if R is a field, then it is Noetherian since its only ideals are (0) and (1). The Hilbert Basis Theorem says that R[X] is Noetherian if R is Noetherian. This theorem is crucial from a constructive viewpoint: it assures us that although ideals are potentially infinite sets, they are in practice finitely describable

We now have a mapping

U ↦ Ideal(U)  (6)

from subsets of ^{d}(R_{1}) to the ideals of R_{0}[X], and conversely a mapping

J ↦ Zero(J)  (7)

from subsets of R_{0}[X] to algebraic sets of ^{d}(R_{1}). It is not hard to see that

J ⊆ Ideal(Zero(J)),  U ⊆ Zero(Ideal(U))  (8)

for all subsets J ⊆ R_{0}[X] and U ⊆ ^{d}(R_{1}). Two other basic identities are:

Zero(Ideal(Zero(J))) = Zero(J),  J ⊆ R_{0}[X]
Ideal(Zero(Ideal(U))) = Ideal(U),  U ⊆ ^{d}(R_{1})  (9)

We prove the first equality: If a ∈ Zero(J) then for all P ∈ Ideal(Zero(J)), P (a) = 0. Hence a ∈ Zero(Ideal(Zero(J)). Conversely, if a ∈ Zero(Ideal(Zero(J)) then P (a) = 0 for all P ∈ Ideal(Zero(J)). But since J ⊆ Ideal(Zero(J)), this means that P (a) = 0 for all P ∈ J. Hence a ∈ Zero(J). The second equality (9) is left as an exercise.

If we restrict the domain of the map in (6) to algebraic sets and the domain of the map in (7) to ideals, would these two maps be inverses of each other? The answer is no, based on a simple observation: An ideal I is called radical if for all integers n ≥ 1, P^{n} ∈ I implies P ∈ I. It is not hard to check that Ideal(U) is radical. On the other hand, the ideal (X^{2}) ∈ [X] is clearly non-radical.

It turns out that if we restrict the ideals to radical ideals, then Ideal(·) and Zero(·) would be inverses of each other. This is captured in the Hilbert Nullstellensatz (in English, Hilbert Zero Theorem). After the Basis Theorem, this is perhaps the next fundamental theorem of algebraic geometry. It states that if P vanishes on the zero set of an ideal I then some power P^{n} of P belongs to I. As a consequence,

I = Ideal(Zero(I)) ⇔ I is radical.

In proof: Clearly the left-hand side implies I is radical. Conversely, if I is radical, it suffices to show that Ideal(Zero(I)) ⊆ I. Say P ∈ Ideal(Zero(I)). Then the Nullstellensatz implies P^{n} ∈ I for some n. Hence P ∈ I since I is radical, completing our proof.

We now have a bijective correspondence between algebraic sets and radical ideals. This implies that ideals in general carry more information than algebraic sets. For instance, the ideals (X) and (X^{2}) have the same zero set, viz., X = 0. But the unique zero of (X^{2}) has multiplicity 2.

The ideal-theoretic approach characterizes the transition from classical to “modern algebraic geometry”. Post-modern^{1} algebraic geometry has gone on to more abstract objects such as

1to borrow a term from architecture.

§5. Representation and Size  Lecture 0  Page 7

schemes, but it seems that the contemporary challenge in constructive algebraic geometry is at the ideal-theoretic level. Recently, work by Brown and others have given us effective versions of classical results such as the Hilbert Nullstellensatz. Such results yields complexity bounds that are necessary for efficient algorithms (see Exercise).

In sum, these lectures concern certain fundamental problems in geometry and algebra. While deeply classical, these topics are now viewed through the lens of complexity theory. The reader interested in the profound transformations that algebraic geometry has undergone over the centuries may consult Dieudonne [3] who described the subject in “seven epochs”. The book of Hoffmann [4] illustrates a wide range of applications using the fundamental problems treated in our lectures.

Exercise 4.1: Show the relation (8), and relation (9).

Exercise 4.2: Show that the ideal membership problem is polynomial-time equivalent to the problem of checking if two sets of elements generate the same ideal: Is (a_{1},…, a_{m}) = (b_{1},…, b_{n})? [Two problems are polynomial-time equivalent if one can be reduced to the other in polynomial-time and vice-versa.]

Exercise 4.3*: a) Given P_{0}, P_{1},…, P_{m} ∈ [X_{1},…, X_{d}], where these polynomials have degree at most n, there is a known double exponential bound B(d, n) such that if P_{0} ∈ (P_{1},…, P_{m}) there there exists polynomials Q_{1},…, Q_{m} of degree at most B(d, n) such that

P_{0} = P_{1}Q_{1} + ⋯ + P_{m}Q_{m}.

Note that B(d, n) does not depend on m. Use this fact to construct a double exponential time algorithm for ideal membership.

b) Does the bound B(d, n) translate into a corresponding bound for [X_{1},…, X_{d}]?

§5. Representation and Size

We switch from mathematics to computer science. To investigate the computational complexity of the Fundamental Problems, we need tools from complexity theory. The complexity of a problem is a function of some size measure on its input instances. The size of a problem instance depends on its representation.

Here we describe the representation of some basic objects that we compute with. For each class of objects, we choose a notion of “size”.

Integers: Each integer n ∈ is given the binary notation and has (bit-)size

size(n) = 1 + ⌈log(|n| + 1)⌉

where logarithms are always base 2 unless otherwise stated. The term “1+… ” takes care of the sign-bit.

Rationals: Each rational number p/q ∈ is represented as a pair of integers with q > 0. We do not assume the reduced form of a rational number. The (bit-)size is given by

size (\frac{p}{q}) = size(p) + size(q) + 1.

§6. Models  Lecture 0  Page 8

Matrices: The default is the dense representation of matrices so that zero entries must be explicitly represented. An m × n matrix M = (a_{ij}) has (bit-)size

size(M) = mn + ∑_{i=1}^{m} ∑_{j=1}^{n} size(a_{ij}).

Polynomials: The default is the dense representation of polynomials. So a degree-n univariate polynomial is represented as a (n + 1)-tuple of its coefficients – and the size of the (n + 1)- tuple is already covered by the above size consideration for matrices.

Other representations (especially of multivariate polynomials) can be more involved. In constrast to dense representations, sparse representations refers to those whose sizes grow linearly with the number of non-zero terms of a polynomial. In general, such compact representations greatly increase the computational complexity of problems. For instance, Plaisted has shown that deciding if two dense univariate integer polynomials are relatively prime is NP -hard (see [7,8]).

Ideals: Usually, ‘ideals’ refer to polynomial ideals. An ideal I is represented by any finite set {P_{1},…, P_{n}} of elements that generate it: I = (P_{1},…, P_{n}). The size of this representation just the sum of the sizes of the generators. Clearly, the representation of an ideal is far from unique.

The representations and sizes of other algebraic objects (such as algebraic numbers) will be discussed as they arise.

§6. Computational Models

We briefly review four models of computation: Turing machines, Boolean circuits, algebraic programs and random access machines. With each model, we will note some natural complexity measures (time, space, size, etc), including their correspondences across models. We will be quite informal since many of our assertions about these models will be (with some coaching) self-evident. A general reference for machine models is Aho, Hopcroft and Ullman [1] or Yap [16]. For a more comprehensive treatment of the algebraic model, see Borodin and Munro [2]; for the Boolean model, see Wegener [15].

Turing machine model. The Turing model is embodied in the multitape Turing machine in which inputs are represented by a binary string. Our representation of objects and definition of sizes in the last section are especially appropriate for this model of computation. The machine is essentially a finite state automaton (called its finite state control) equipped with a finite set of doubly-infinite tapes, including a distinguished input tape. Each tape is divided into cells indexed by the integers. Each cell contains a symbol from a finite alphabet. Each tape has a head which scans some cell at any moment. The Turing machine operates deterministically according to the specification of a finite transition table: in each step, depending on the current state and the symbols being scanned under each tape head, the transition table specifies the next state, modifies the symbols under each head and moves each head to a neighboring cell. The main complexity measures in the Turing model are time (the number of steps in a computation), space (the number of cells used during a computation) and reversal (the number of times a tape head reverses its direction).

Boolean circuit model. This model is based on Boolean circuits. A Boolean circuit is a directed acyclic graph whose nodes are classified as input nodes or gates. The input nodes have in-degree 0 and the gates are labeled by any Boolean function on at most two variables, with in-degree commensurate with the label. The out-degree has no a priori bound. The main complexity measures here are circuit size (the number of gates) and circuit depth (the longest path) and circuit width (roughly, the largest antichain).

A circuit can only compute a function on a fixed number of Boolean inputs. Hence to compare the Boolean circuit model to the Turing machine model, we need to consider a circuit family, which is an infinite sequence (C_{0}, C_{1}, C_{2},…) of circuits, one for each input size. Because there is no a priori connection between the circuits in a circuit family, we call such a family nonuniform. For this reason, we call Boolean circuits a “non-uniform model” as opposed to Turing machines which is “uniform”. Circuit size can be identified with time on the Turing machine. Circuit depth is more subtle, but it can be (following Jia-wei Hong) identified with “reversals” on Turing machines.

It turns out that the Boolean complexity of any problem is at most 2^{n}/n (see [15] or [16]). Clearly this is a severe restriction on the generality of the model. But it is possible to make Boolean circuits families “uniform”. This can be done in several ways and the actual choice is usually not critical. For instance, we may require that there is a Turing machine using logarithmic space such that on input n in binary, constructs the (encoded) nth circuit of the circuit family. The resulting uniform Boolean complexity is now polynomially related to Turing complexity. Still, the non-uniform model suffices for many applications (see §8), and that is what we will use in this book.

Encodings and bit models. The previous two models are called bit models because mathematical objects must first be encoded as binary strings before they can be used on these two models. The issue of encodings may be quite significant [16, Chapter 1], though we get around this by assuming standard conventions such as binary encoding of numbers, list representation of sets, etc. In algorithmic algebra, it is sometimes useful to avoid encodings by incorporating the relevant algebraic structures directly into the computational model. This leads us to our next model.

Algebraic program models. In this model, we must fix some algebraic structures (such as , polynomials or matrices over a ring R) and specify a set of primitive algebraic operations called the basis of the model. Usually the basis includes the ring operations (+, −, ×), possibly supplemented by other operations appropriate to the underlying algebraic structure. A common supplement is some form of root finding (e.g., multiplicative inverse, radical extraction or general root extraction). Strictly speaking, the “algebraic program model” is a class of models based on different algebraic structures and different bases.

An algebraic program is defined to be a rooted ordered tree T where each node represents either an assignment step of the form

V ← F (V_{1},…, V_{k}),

or a branch step of the form

F (V_{1},…, V_{k}) : 0.

Here, F is a k-ary operation in the basis and each V_{i} is either an input variable, a constant or a variable that has been assigned a value further up the tree. The outdegree of an assignment node is 1; the outdegree of a branch node is 2, corresponding to the outcomes F (V_{1},…, V_{k}) = 0 and F (V_{1},…, V_{k}) ≠ 0, respectively. If the underlying algebraic structure is real, the branch steps can be extended to a 3-way branch, corresponding to F (V_{1},…, V_{k}) < 0, = 0 or > 0. At the leaves of T, we fix some convention for specifying the output.

The input size is just the number of input variables. The main complexity measure studied with this model is time, the length of the longest path in T. Note that we charge a unit cost to each basic operation. This could easily be generalized. For instance, a multiplication step in which one of the operands is a constant (i.e., does not depend on the input parameters) may be charged nothing. This originated with Ostrowski who wrote one of the first papers in algebraic complexity.

Like Boolean circuits, this model is non-uniform because each algebraic program solves problems of a fixed size. Again, we introduce the algebraic program family which is an infinite set of algebraic programs, one for each input size.

When an algebraic program has no branch steps, it is called a straight-line program. To see that in general we need branching, consider algebraic programs to compute the GCD (see Exercise below).

RAM model. Finally, consider the random access machine (RAM) model of computation. Each RAM is defined by a finite set of instructions, rather as in assembly languages. These instructions refers to operands called registers. Each register can hold an arbitrarily large integer and is indexed by a natural number. If n is a natural number, we can denote its contents by ⟨n⟩. Thus ⟨⟨n⟩⟩ refers to the contents of the register whose index is ⟨n⟩. In addition to the usual registers, there is an unindexed register called the accumulator in which all computations are done (so to speak). The RAM instruction sets can be defined variously and has the simple format

INSTRUCTION OPERAND

where OPERAND is either n or ⟨n⟩ and n is the index of a register. We call the operand direct or indirect depending on whether we have n or ⟨n⟩. We have five RAM instructions: a STORE and LOAD instruction (to put the contents of the accumulator to register n and vice-versa), TEST instruction (to skip the next instruction if ⟨n⟩ is zero) and the SUCC operation (to add one to the content of the accumulator.) For example, ‘LOAD 5’ instructs the RAM to put ⟨5⟩ into the accumulator; but ‘LOAD ⟨5⟩’ puts ⟨⟨5⟩⟩ into the accumulator; ‘TEST 3’ causes the next instruction to be skipped if ⟨3⟩ = 0; ‘SUCC’ will put increments the accumulator content by one. There are two main models of time-complexity for RAM models: in the unit cost model, each executed instruction is charged 1 unit of time. In contrast, the logarithmic cost model charges ⌈lg(n + ⟨n⟩)⌉ whenever a register n is accessed. Note that an instruction accesses one or two registers, depending on whether the operand is direct or indirect. It is known that the logarithmic cost RAM is within a quadratic factor of the Turing time complexity. The above RAM model is called the successor RAM to distinguish it from other variants, which we now briefly note. More powerful arithmetic operations (ADDITION, SUBTRACTION and even MULTIPLICATION) are sometimes included in the instruction set. Schönhage describes an even simpler RAM model than the above model, essentially by making the operand of each of the above instructions implicit. He shows that this simple model is real-time equivalent to the above one.

§7. Asymptotic Notations  Lecture 0  Page 11

Exercise 6.1:

(a) Describe an algebraic program for computing the GCD of two integers. (Hint: implement the Euclidean algorithm. Note that the input size is 2 and this computation tree must be infinite although it halts for all inputs.)

(b) Show that the integer GCD cannot be computed by a straightline program.

(c) Describe an algebraic program for computing the GCD of two rational polynomials P (X) = ∑_{i=0}^{n} a_{i}X^{i} and Q(X) = ∑_{i=0}^{m} b_{i}X^{i}. The input variables are a_{0}, a_{1},…, a_{n}, b_{0},…, b_{m}, so the input size is n + m + 2. The output is the set of coefficients of GCD(P, Q).

§7. Asymptotic Notations

Once a computational model is chosen, there are additional decisions to make before we get a “complexity model”. This book emphasizes only the worst case time measure (or its equivalent) in each of our computational models. To each machine or program A in our computational model, this associates a function T_{A}(n) that specifies the worst case number of time steps used by A, over all inputs of size n. Call T_{A}(n) the complexity of A. Abstractly, we may define a complexity model to comprise a computational model together with an associated complexity function T_{A}(n) for each A. The complexity models in this book are: Turing complexity model, Boolean complexity model, algebraic complexity model, and RAM complexity model For instance, in Turing complexity model, we refer to the worst-case time complexity of Turing machines. Also, “algebraic complexity model” is a generic term that, in any specific instance, must be instantiated by some choice of algebraic structure and basis operations.

We intend to distinguish complexity functions up to constant multiplicative factors and up to their eventual behavior. To facilitate this, we introduce some important concepts.

Definition 1 A complexity function is a real partial function f : → ∪ {∞} such that f(x) is defined for all sufficiently large natural numbers x ∈ .

If f(x) is undefined, we write f(x) ↑, and this is to be distinguished from the case f(x) = ∞. We often use familiar partial functions such that log x and 2^{x} as complexity functions, even though we are mainly interested in their values at . Note that if f, g are complexity functions, so are

f + g, fg, f^{g}, f ∘ g

where f ∘ g denotes function composition.

The big-Oh notation. Let f, g be complexity functions. We say f dominates g if f(x) ≥ g(x) for all sufficiently large x, and provided f(x), g(x) are both defined. By “sufficiently large x” or “large enough x” we mean “for all x ≥ x_{0}” where x_{0} is some unspecified constant.

The big-Oh notation is the most famous member of a family of symptotic notations. The prototypical use of this notation goes as follows. We say f is big-Oh of g (or, f is order of g) and write

f = O(g)  (10)

if there is a constant C > 0 such that C · g(x) dominates f(x). As examples of usage, f(x) = O(1) (respectively, f(x) = x^{O(1)}) means that f(x) is eventually bounded by some constant (respectively, by some polynomial). Or again, n log n = O(n^{2}) and 1/n = O(1) are both valid.

Our definition in Equation (10) gives a very specific formula for using the big-Oh notation. We now describe an extension. Recursively define O-expressions as follows. Basis: If g is a symbol for a complexity function, then g is an O-expression. Induction: If E_{i} (i = 1, 2) are O-expressions, then so are

O(E_{1}), E_{1} + E_{2}, E_{1}E_{2}, E_{1}^{E_{2}}, E_{1} ∘ E_{2}.

Each O-expression denotes a set of complexity functions. Basis: The O-expression g denotes the singleton set {g′} where g′ is the function denoted by g. Induction: If E_{i} denotes the set of complexity functions E′_{i} then the O-expression O(E_{1}) denotes the set of complexity functions f′ such that there is some g′ ∈ E′_{1} and C > 0 and f′ is dominated by Cg′. The expression E_{1} + E_{2} denotes the set of functions of the form f_{1} + f_{2} where f_{i} ∈ E′_{i}. Similarly for E_{1}E_{2} (product), E_{1}^{E_{2}} (exponentiation) and E_{1} ∘ E_{2} (function composition). Finally, we use these O-expressions to assert the containment relationship: we write

E_{1} = E_{2},

to mean E′_{i} ⊆ E′_{2}. Clearly, the equality symbol in this context is asymmetric.

After this preceding definition, we revert to taking the usual license of confusing a function symbol g with the function g′ that it denotes. Likewise, we confuse the concept of an Oexpression and the set of functions it denotes. By convention, the expressions ‘c’ (c ∈ ) and ‘n’ denotes (respectively) the constant function c and the identity function. Then ‘n^{2}’ and ‘log n’ are O-expressions denoting the (singleton set containing the) square function and logarithm function. Other examples of O-expressions: 2^{n+O(log n)}, O(O(n)^{log n}+n^{O(n)} log log n), f(n) ∘ O(n log n).

The subscripting convention. There is another useful way to extend the basic formulation of Equation (10): instead of viewing its right-hand side “O(g)” as denoting a set of functions (and hence the equality sign as set membership ‘∈’ or set inclusion ‘⊆’), we can view it as denoting some particular function C · g that dominates f. The big-Oh notation in this view is just a convenient way of hiding the constant ‘C’ (it saves us the trouble of inventing a symbol for this constant). In this case, the equality sign is interpreted as the “dominated by” relation, which explains the tendency of some to write ‘≤’ instead of the equality sign. Usually, the need for this interpretation arises because we want to obliquely refer to the implicit constant. For instance, we may want to indicate that the implicit constants in two occurrences of the same Oexpression are really the same. To achieve this cross reference, we use a subscripting convention (see [16]): we can attach a subscript or subscripts to the O, and this particularizes that Oexpression to refer to some fixed function. Two identical O-expressions with similar subscripts refer to the same implicit constants. By choosing the subscripts judiciously, this notation can be quite effective. For instance, instead of inventing a function symbol T_{A}(n) = O(n) to denote the running time of a linear-time algorithm A, we may simply use the subscripted expression “O_{A}(n)”; subsequent use of this expression will refer to the same function. Another simple illustration is “O_{3}(n) = O_{1}(n) + O_{2}(n)”: the sum of two linear functions is linear, with different implicit constant for each subscript.

§8. Complexity Theory  Lecture 0  Page 13

Related asymptotic notations. We say f is big-Omega of g and write

f(n) = Ω(g(n))

if there exists a real C > 0 such that f(x) dominates C · g(x). We say f is Theta of g and write

f(n) = Θ(g(n))

if f = O(g) and f = Ω(g). We normally distinguish complexity functions up to Theta-order. We say f is small-oh of g and write

f(n) = o(g(n))

if f(n)/g(n) → 0 as n → ∞. We say f is small-omega of f and write

f(n) = ω(g(n))

if f(n)/g(n) → ∞ as n → ∞. We say

f ∼ g

if f = g[1 ± o(1)]. For instance, n + log n ∼ n but not n + log n ∼ 2n.

These notations can be extended as in the case of the big-Oh notation. The semantics of mixing these notations are less obvious and is, in any case, not needed.

§8. Elements of Complexity Theory

Let us now fix complexity model M. This amounts to associating a complexity function T_{A}(n) to each program or machine A of M. Complexity theory really begins when we associate a complexity function T_{P} (n) with each computational problem P. We call T_{P} (n) the “intrinsic complexity” of P, relative to the complexity model. It turns out that such a function T_{P} (n) may be somewhat illusive.

But what is the concept of a “problem”? Without trying to formalize this, we simply try to identify it with the set of machines that is said to “solve” the problem. In each concrete situation, this is not hard to make precise. For our purposes, we simply identify a problem as a set P of machines: if A is a machine in P, we say A solves P or A an algorithm for P.^{2} We say a complexity function f(n) is an upper bound on the intrinsic complexity of P if there is an algorithm A in M that solves P such that f(n) dominates T_{A}(n). If, for every algorithm A in M that solves P, T_{A}(n) dominates f(n), then we call f(n) a lower bound on the intrinsic complexity of P.

The concepts of upper and lower bound are asymetrical: let U be the set of upper bounds on the intrinsic complexity of P. Clearly U determines the set L of lower bounds. Moreover, there exists a function ℓ(x) in L such that ℓ(x) dominates each functions f(x) ∈ L. If there exists a function T (n) in U that is dominated by all other functions in U, we may identify T (n) as the intrinsic complexity T_{P} (n) of P that we sought. Unfortunately, it is not obvious that T_{P} (n) exists in general. To resolve this case of the missing intrinsic complexity, we generalize our concept of a function:

2Thus the concept of an algorithm is a semantic one, denoting a relationship between a machine/program (which is syntactic) and some computational problem.

Definition 2 An intrinsic (complexity) function is any non-empty family U of complexity functions that is not external dominated, i.e., if f ∈ U and g dominates f then g ∈ U.

The set U of upper bounds on the intrinsic complexity of P is an intrinsic function: we may identify this as the intrinsic complexity T_{P} of P. A subset V ⊆ U is called a generating set of U if every f ∈ U dominates some g ∈ V. We say U is principal if U has a generating set consisting of one function f_{0}; in this case, we call f_{0} a generator of U. If f is a complexity function, we may identify f with the principal intrinsic function with f as a generator. Note that in non-uniform computational models, the intrinsic complexity of any problem is principal.

Let U, T be intrinsic functions. We would like to treat intrinsic functions as ordinary functions. For instance, we often write ‘U(n)’ instead of ‘U’. Like ordinary functions, we let the expressions

U + T, UT, U^{T} , U ∘ T  (11)

denote intrinsic functions in the natural way. For instance, U + T denotes the intrinsic function generated by the set of functions of the form u + t where u ∈ U and t ∈ T. We also need terminology for discussing bounds on intrinsic functions:

Definition 3 We say U is big-Oh of T, written

U(n) = O(T (n)),

if there exists u ∈ U such that for all t ∈ T, we have u = O(t) in the usual sense. In case f(n) is a generator of T, we may write U(n) = O(f(n)) instead.

This definition may need some getting used to, but it appears to do exactly what we expect (cf. (14) in §9) . Caveat: unlike ordinary functions, we shall neither extend this notation to general O-expressions, nor use any subscripting convention.

Similarly, we say U is big-Omega of T, written U(n) = Ω(T (n)), if for all u ∈ U, there exists t ∈ T such that u = Ω(t). We say U is Theta of T, written U(n) = Θ(T (n)), if U = O(T) and U = Ω(T).

Complexity of multiplication. Let us illustrate these concepts on some actual problems. It will be clear that our definitions preserve the locutions that researchers use when they informally describe intrinsic complexity of problems. We shall say Turing complexity of a problem P instead of “intrinsic complexity of P under the Turing complexity model”. ^{3} The Turing complexity of integer addition is easily seen to be Θ(n). More interesting is the Turing complexity of integer multiplication. This fundamental quantity is used in many other complexity bounds. In these lectures, we denote this intrinsic complexity by

M_{B}(n).

It is by no means clear that M_{B}(n) is principal. The best upper bound is

M_{B}(n) = O(n log n log log n),  (12)

3Similarly for “Boolean complexity”, “algebraic complexity” and “RAM complexity”. But “bit complexity”

will be a term covering both Turing and Boolean complexity.

from a celebrated result [11] of Schönhage and Strassen (1971). To simplify our display of such bounds (cf. [9,6]), we write L^{k}(n) (k ≥ 1) to denote some fixed but non-specific function f(n) such that

\frac{f(n)}{log^{k} n} = (log log n)^{O(1)}.

If k = 1, the superscript in L^{1}(n) is omitted. Thus Equation (12) implies

M_{B}(n) = nL(n).

Note that we need not write the big-Oh notation since it is absorbed inside the L(n) notation. Schönhage [10](cf. [5, p. 295]) has shown that the complexity of integer multiplication takes a simpler form with alternative computational models (see §6): A successor RAM can multiply two n-bit integers in O(n) time under the unit cost model, and in O(n log n) time in the logarithmic cost model.

Next consider the algebraic complexity of multiplying two degree n polynomials, denoted

M_{A}(n).

The basis for our algebraic programs is comprised of the ring operations of R, where the polynomials are from R[X]. Trivially, M_{A}(n) = O(n^{2}) but we shall show that

M_{A}(n) = O(n log n).

Finally, consider the algebraic complexity of multiplying two n × n matrices. We assume the basis is comprised of the ring operations of a ring R, where the matrix entries come from R. This is another fundamental quantity which will be denoted by

MM(n)

in this book. Of course, since we consider a non-uniform model, this intrinsic function is principal. Trivially, MM(n) = O(n^{3}) and Strassen (1968) first showed that this is suboptimal in a famous paper. The current record upper bound is

MM(n) = O(n^{2.376}).  (13)

§9. Bit versus Algebraic  Lecture 0  Page 16

Complexity Classes. Corresponding to each computational model, we have complexity classes of problems. Each complexity class is usually characterized by a complexity model (worst-case time, randomized space, etc) and a set complexity bounds (polynomial, etc). The class of problems that can be solved in polynomial time on a Turing machine is usually denoted P: it is arguably the most important complexity class. This is because we identify this class with the “feasible problems”. For instance, the the Fundamental Problem of Algebra (in its various forms) is in P but the Fundamental Problem of Classical Algebraic Geometry or of Ideal Theory are not in P. Complexity theory can be characterized as the study of relationships among complexity classes [16, preface]. We only make occasional allusions to such complexity classes but keeping them at the back of our minds may motivate much of our activities. Another important class is NC which comprises those problems that can be solved simultaneously in depth log^{O(1)} n and size n^{O(1)}, under the Boolean circuit model. Since circuit depth equals parallel time, this is an important class in the parallel computation. Although we did not define the circuit analogue of algebraic programs, this is rather straightforward: they are like Boolean circuits except we perform algebraic operations at the nodes. Then we can define NC_{A}, the algebraic analogue of the class NC.

Note that NC concerns a composite complexity resource (simultaneous size and depth), unlike our usual complexity models involving just time. The proper treatment of such complexity classes would necessitate the use of bivariate complexity functions f(x, y), etc.

Exercise 8.1: Prove the existence of a problem whose intrinsic complexity is not principal.

§9. On Bit versus Algebraic Complexity

We have omitted other important models such as pointer machines that have a minor role in algebraic complexity. But why such a proliferation of models? Researchers use different models depending on the problem at hand. We offer some guidelines for these choices.

1. There is a consensus in complexity theory that our Turing model the most basic^{4} of all general-purpose computational models. To the extent that algebraic complexity seeks to be compatible to the rest of complexity theory, it is preferable to use the Turing model.

2. In practice, the RAM model is invariably used to describe algebraic algorithms because the Turing model is too cumbersome. Upper bounds (i.e., algorithms) are more readily explained in the RAM model and we are happy to take advantage of this in order to make the result more accessible. Sometimes, we could further assert (“left to the reader”) that the RAM result extends to the Turing model.

3. Complexity theory proper is regarded to be a theory of “uniform complexity”. This means “naturally” uniform models such as Turing machines are preferred over “naturally non-uniform” models such as Boolean circuits. Nevertheless, non-uniform models has the advantage of being combinatorial and conceptually simpler. Historically, this was a key motivation for studying Boolean circuits, since it is hoped that powerful combinatorial arguments may yield superquadratic lower bounds on the Boolean size of specific problems. Such a result would immediately imply non-linear lower bounds on Turing machine time for the same problem. (Unfortunately, neither kind of results has yet been realized.) Another advantage of non-uniform models is that the intrinsic complexity of problems is always principal. Although the intrinsic complexity of problems in the Boolean model cannot exceed 2^{n}/n, many problems of interest have low polynomial complexity and there is no evidence than imposing some uniformity constraint would significantly change their complexity.^{5} Another area where Boolean circuits seems more natural is parallel computation: circuit depth and Turing machine reversals roughly correspond to parallel time, but circuit depth seems more natural than the reversals.

4. The choice between bit complexity and the algebraic complexity is problem-dependent. For instance, the algebraic complexity of integer GCD would not make much sense (see Exercise in §6). But bit complexity is meaningful for any problem (the encoding of the problem must be taken into account). This may suggest that algebraic complexity is a more specialized tool than bit complexity. But even in a situation where bit complexity is of primary interest, one may have to investigate the corresponding algebraic complexity. For instance, the algebraic complexity of multiplying integer matrices is MM(n) = O(n^{2.376}) as noted above. Let^{6} MM(n, N) denote the Turing complexity of integer matrix multiplication, where N is an additional bound on the bit size of each entry of the matrix. The best upper bound for MM(n, N) comes from the trivial remark,

4To be more precise, the most basic among all sequential, deterministic “modes” of computation. See [16] where this mode is called the fundamental mode of computation.

5This situation is less clear in the case of efficient parallel (or NC) algorithms. For instance, there seems to be a difference between uniform and non-uniform NC circuits for integer division.

MM(n, N) = O(MM(n)M_{B}(N)).  (14)

[The reader should verify that Equation (14) makes sense since the “functions” involved are intrinsic functions rather than ordinary functions.] So the most general formulation of the upper bound on MM(n, N) might as well be the separate upper bounds, MM(n) and M_{B}(N). In other words, we do not know how to exploit the interaction of the two parameters n and N in this problem.

Linear Programming. The above example illustrates a common situation, where the best bit complexity of a problem is obtained as the best algebraic complexity multiplied by the best bit complexity on the underlying operations. We now show an example where this is not the case.

Consider the problem of linear optimization (linear programming). Let m, n, N are complexity parameters where the linear constraints are represented by Ax ≤ b, A is an m × n matrix, and all the numbers in A, b have at most N bits. The linear programming problem can be reduced to checking for the feasibility of the inequality Ax ≤ b, on input A, b. The Turing complexity T_{B}(m, n, N) of this problem is known to be polynomial in m, n, N. This result was a major breakthrough due to Khacian. However, all known algorithms for linear programming is at least single exponential in the parameters m, n alone. It is a major open problem whether the corresponding algebraic complexity T_{A}(m, n) of linear programming is polynomial in m, n.

Euclidean shortest paths. In contrast to linear programming, we now show a problem for which the bit complexity is not known to be polynomial but whose algebraic complexity is polynomial. This is the problem of finding the shortest paths between two points on the plane. Let us formulate a version of the Euclidean shortest path problem: we are given a planar graph G that is linearly embedded in the plane, i.e., each vertex v of G is mapped to a point m(v) in the plane and each edge (u, v) between two vertices is represented by the corresponding line segment [m(u), m(v)], where two segments may only intersect at their endpoints. We want to find the shortest (under the usual Euclidean metric) path between two specified vertices s, t. Assume that the points m(v) have rational coordinates. Clearly this problem can be solved by Djikstra’s algorithm in polynomial time, provided we can (i) take square-roots, (ii) add two sums of square-roots, and (iii) compare two sum of square-roots in constant time. Thus the algebraic complexity is polynomial time (where the basis operations include (i-iii)). However, the current best bound on the bit complexity of this problem is single exponential space. Note: The numbers that arise in this problem are called the constructible reals because they can be finitely constructed by a ruler and a compass.

The lesson of these two examples is that bit complexity and algebraic complexity are two different animals. We cannot generally expect a polynomial relationship between these two types of complexities: depending on the problem, either one could be exponentially worst than the other.

6The bit complexity bound on any problem is usually formulated to have one more size parameter (N) than the corresponding algebraic complexity bound.

§10. Miscellany  Lecture 0  Page 18

Exercise 9.1*: Obtain an upper bound on the above Euclidean shortest path problem.

Exercise 9.2: Show that a real number of the form

α = n_{0} ± \sqrt{n_{1}} ± \sqrt{n_{2}} ± ⋯ ± \sqrt{n_{k}}

(where n_{i} are positive integers) is a zero of a polynomial P (X) of degree at most 2^{k}, and that all zeros of P (X) are real.

§10. Miscellany

This section serves as a quick general reference.

Equality Symbols. We introduce two new symbols to reduce^{7} the semantic overload commonly placed on the equality symbol ‘=’. We use the symbol ‘←’ for programming variable assignments, from right-hand side to the left. Thus, V ← U +W is an assignment to V. We use the symbol ‘:=’ to denote definitional assignments, from the right-hand side to the left-hand side. Thus, “f(n) := n log n” is a definition of the function f. But we refrain from using the mirror images of the new symbols (we will neither write “U + W → V ” nor “n log n =: f(n)”).

Sets and functions. The empty set is written ∅. Let A, B be sets. Subsets and proper subsets are respectively indicated by A ⊆ B and A ⊂ B. Set difference is written A \ B. Set formation is usually written {x : … x…} where … x… specifies some properties on x. We write f ∘ g for the composition of functions g : U → V, f : V → W. So (f ∘ g)(x) = f(g(x)). If a function f is undefined for a certain value x, we write f(x) ↑.

Numbers. Let i denote the square root of −1. For a complex number b = x+iy, let Re(b) = x and Im(b) = y denote its real and imaginary part, respectively. Its modulus |b| is defined to be the positive square-root of x^{2} + y^{2}. If b is real, |b| is also called the absolute value. But if S is any set, |S| will refer to the cardinality.

For a real number r, we use Iverson’s notation (as popularized by Knuth) ⌈r⌉ and ⌊r⌋ for the ceiling and floor functions. We have

⌊r⌋ ≤ ⌈r⌉.

In this book, we introduce the symmetric ceiling and symmetric floor functions:

⌈r⌉_{s}:= \{ \begin{matrix}⌈r⌉ & if r ≥ 0, \\ ⌊r⌋ & if r < 0. \end{matrix}

⌊r⌋_{s}:= \{ \begin{matrix}⌊r⌋ & if r ≥ 0, \\ ⌈r⌉ & if r < 0. \end{matrix}

These functions satisfy the following inequalities, valid for all real numbers r:

|⌊r⌋_{s}| ≤ |r| ≤ |⌈r⌉_{s}|.

7Perhaps to atone for our introduction of the asymptotic notations.

(The usual floor and ceiling functions fail this inequality when r is negative.) We also use ⌊r⌉ to denote the rounding function, ⌊r⌉:=⌈r − 0.5⌉. So

⌊r⌋ ≤ ⌊r⌉ ≤ ⌈r⌉.

The base of the logarithm function log x is assumed to be 2 unless otherwise noted; usually this base is immaterial.

For positive integers a, b, we define the usual quotient and remainder functions, rem(a, b) and quo(a, b) which satisfy the relation

a = quo(a, b) · b + rem(a, b)

such that b > rem(a, b) ≥ 0. We also write these functions using an in-fix notation:

(a div b) := quo(a, b); (a mod b) := rem(a, b).

These functions can be generalized to Euclidean domains (lecture II§2). Note that we continue to use ‘mod’ in the standard notation “a ≡ b(mod m)” for congruence modulo m.

Norms. For a complex polynomial P ∈ [X] and for each positive real number k, let ∥P ∥_{k} denote the k-norm,

∥P ∥_{k}:= (∑_{i=0}^{n} |p_{i}|^{k})^{1/k}

where p_{0},…, p_{n} are the coefficients of P. We extend this definition to k = ∞, where

|P ∥_{∞}:= max{|p_{i}| : i = 0,…, n}.  (15)

For 0 < r < s, we have

∥P ∥_{∞} ≤ ∥P ∥_{s} ≤ ∥P ∥_{r} ≤ (n + 1)∥P ∥_{∞}  (16)

The second inequality (called Jensen’s inequality) follows from:

\frac{(∑_{i} |p_{i}|^{s})^{1/s}}{(∑_{j} |p_{j}|^{r})^{1/r}} = \{∑_{i=0}^{n} \frac{|p_{i}|^{s}}{(∑_{j} |p_{j}|^{r})^{s/r}} \}^{\frac{1}{s}} = \{∑_{i=0}^{n} (\frac{|p_{i}|^{r}}{∑_{j} |p_{j}|^{r}} )^{\frac{s}{r}} \}^{\frac{1}{s}}

≤ \{∑_{i=0}^{n} (\frac{|p_{i}|^{r}}{∑_{j} |p_{j}|^{r}} )\}^{\frac{1}{s}} = 1.

The 1-, 2- and ∞-norms of P are also known as the weight, (Euclidean) length and height of P. If u is a vector of numbers, we define the k-norm ∥u∥_{k} of u by viewing u as the coefficient vector of a polynomial.

Inequalities. Let a = (a_{1},…, a_{n}) and b = (b_{1},…, b_{n}) be real n-vectors. We write ⟨a, b⟩ for their scalar product ∑_{i=1}^{n} a_{i}b_{i}.

Hölder’s Inequality: If \frac{1}{p} + \frac{1}{q} = 1 then

|⟨a, b⟩| ≤ ∥a∥_{p}∥b∥_{q},

with equality iff there is some k such that b_{i}^{q} = ka_{i}^{p} for all i. In particular, we have the Cauchy-Schwartz Inequality:

|⟨a, b⟩| ≤ ∥a∥_{2} · ∥b∥_{2}.

Minkowski’s inequality: for k > 1,

∥a + b∥_{k} ≤ ∥a∥_{k} + ∥b∥_{k}.

This shows that the k-norms satisfy the triangular inequality.

A real function f(x) defined on an interval I = [a, b] is convex on I if for all x, y ∈ I, f(\frac{x+y}{2} ) ≤ \frac{f(x)+f(y)}{2}. For instance, if f′′(x) is defined and f′′(x) ≥ 0 on I implies f is convex on I. If f is a convex function on I, p_{1}+p_{2}+⋯+p_{n} = 1 (p_{i} ≥ 0) and x_{i} ∈ I then f(∑_{i=1}^{n} p_{i}x_{i}) ≤ ∑_{i=1}^{n} p_{i}f(x_{i}).

Polynomials. Let p(X) = ∑_{i=0}^{n} a_{i}X^{i} be a univariate polynomial. We sometimes are interested in the largest power j ≥ 0 such that X^{j} evenly divides p(X); this j is called the tail degree of p and the coefficient a_{j} the tail coefficient of p.

Let X = {X_{1},…, X_{n}} be n ≥ 1 (commutative) variables, and consider multivariate polynomials in R[X]. A power product over X is a polynomial of the form T = ∏_{i=1}^{n} X_{i}^{e_{i}} where each e_{i} ≥ 0 is an integer. In particular, if all the e_{i}’s are 0, the power product is 1. The (total) degree deg(T) of T is given by ∑_{i=1}^{n} e_{i}, and the maximum degree mdeg(T) is given by max_{i=1}^{n} e_{i}. The (term) length of a polynomial P to be the number of monomials in P, not to be confused with its Euclidean length ∥P ∥_{2}.

A monomial is a polynomial of the form cT where T is a power product and c ∈ R \ {0}. So a polynomial p can be written uniquely as a sum p = ∑_{i=1}^{k} p_{i} of monomials with distinct power products; each such monomial p_{i} is said to belong to p. The total degree deg(T) (respectively, maximum degree mdeg(T)) of a polynomial P is the largest total (respectively, maximum) degree of a power product in P. A polynomial is homogeneous if each of its monomials has the same total degree. Again, any polynomial p can be written uniquely as a sum p = ∑_{i} h_{i} of homogeneous polynomials h_{i} of distinct degrees; each h_{i} is said to be a homogeneous component of p.

Ideals. Let R be a ring and I, J be ideals of R. The ideal generated by elements a_{1},…, a_{m} ∈ R is denoted (a_{1},…, a_{m}) and is defined to be the smallest ideal of R containing these elements. Since this well-known notation for ideals may be ambiguous, we sometimes write^{8}

Ideal(a_{1},…, a_{m}).

Another source of ambiguity is the underlying ring R that generates the ideal; thus we may sometimes write

(a_{1},…, a_{m})_{R} or Ideal_{R}(a_{1},…, a_{m}).

An ideal I is principal if it is generated by one element, I = (a) for some a ∈ R; it is finitely generated if it is generated by some finite set of elements. For instance, the zero ideal is (0) = {0} and the unit ideal is (1) = R. Writing aR:={ax : x ∈ R}, we have that (a) = aR, exploiting the presence of 1 ∈ R. A principal ideal ring or domain is one in which every ideal is principal.

8Cf. the notation Ideal(U) ⊆ R_{0}[X_{1},…, X_{d}] where U ∈ ^{d}(R_{1}), introduced in §4. We capitalize the names of maps from an algebraic to a geometric setting or vice-versa. Thus Ideal, Zero.

An ideal is called homogeneous (resp., monomial) if it is generated by a set of homogeneous polynomial (resp., monomials).

The following are five basic operations defined on ideals:

Sum: I + J is the ideal consisting of all a + b where a ∈ I, b ∈ J.

Product: IJ is the ideal generated by all elements of the form ab where a ∈ I, b ∈ J.

Intersection: I ∩ J is just the set theoretic intersection of I and J.

Quotient: I : J is defined to be the set {a|aJ ⊆ I} If J = (a), we simply write I : a for I : J.

Radical: \sqrt{I} is defined to be set \{a|(∃n ≥ 1)a^{n} ∈ I\}

Some simple relationships include IJ ⊆ I ∩J, I(J +J′) = IJ +IJ′, (a_{1},…, a_{m})+(b_{1},…, b_{n}) = (a_{1},…, a_{m}, b_{1},…, b_{n}). An element b is nilpotent if some power of b vanishes, b^{n} = 0. Thus \sqrt{(0)} is the set of nilpotent elements.

An ideal I is maximal if I ≠ R and it is not properly contained in an ideal J ≠ R. An ideal I is prime if ab ∈ I implies a ∈ I or b ∈ I. An ideal I is primary if ab ∈ I, a ∉ I implies b^{n} ∈ I for some positive integer n. A ring with unity is Noetherian if every ideal I is finitely generated. It turns out that for Noetherian rings, the basic building blocks are primary ideals (not prime ideals). We assume the reader is familiar with the construction of ideal quotient rings, R/I.

Exercise 10.1: Let I ≠ R be an ideal in a ring R with unity.

a) I is maximal iff R/I is a field.

b) I is prime iff R/I is a domain.

c) I is primary iff every zero-divisor in R/I is nilpotent.

Exercise 10.2: Verify the rest of equation (16).

Exercise 10.3: Show that (∑_{i=1}^{n} |a_{i}|)^{2} ≤ 2n (∑_{i=1}^{n} |a_{i}|^{2}).

HINT: (∑_{i=1}^{n} |a_{i}|)^{2} = ∑_{i,j=1}^{n} |a_{i}a_{j}|.

References

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.

[2] A. Borodin and I. Munro. The computational complexity of algebraic and numeric problems. American Elsevier Publishing Company, Inc., 1975.

[3] Jean Dieudonné. History of algebraic geometry. Wadsworth Advanced Books & Software, 1985. (trans. from French, Judith D. Sally).

[4] Christoph M. Hoffman. Geometric and Solid Modeling. Morgan Kaufmann Publishers, Inc, San Mateo, California 94403, 1989.

[5] D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, 2nd edition edition, 1981.

[6] Lars Langemyr. Computing the GCD of two polynomials over an algebraic number field. PhD thesis, The Royal Institute of Technology, Stockholm, Sweden, January 1989. Technical Report TRITA-NA-8804.

[7] David A. Plaisted. New np-hard and np-complete polynomial and integer divisibility problems. Theoretical Computer Science, 31:125–138, 1984.

[8] David A. Plaisted. Complete divisibility problems for slowly utilized oracles. Theoretical Computer Science, 35:245–260, 1985.

[9] Michael O. Rabin. Probabilistic algorithms for finite fields. SIAM Journal Computing, 9(2):273–280, 1980.

[10] A. Schönhage. Storage modification machines. SIAM Journal Computing, 9:490–508, 1980.

[11] A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing, 7:281– 292, 1971.

[12] Jacob T. Schwartz and Micha Sharir. On the piano movers’ problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4:298–351, 1983.

[13] D.J. Struik, editor. A source book in Mathematics, 1200-1800. Princeton University Press, 1986.

[14] B.L. van der Waerden. Algebra, volume 1 & 2. Frederick Ungar Publishing Co., 1970.

[15] Ingo Wegener. The complexity of Boolean functions. B.G.Teubner, Stuttgart, and John Wiley & Sons, Chichester, 1987.

[16] Chee-Keng Yap. Introduction to the Theory of Complexity Classes. Oxford University Press, (to appear, 1993).

[17] Oscar Zariski and Pierre Samuel. Commutative Algebra. Springer-Verlag, New York, 1975. 2 volumes.