Mathematics - Fundamental Problems in Algorithmic Algebra.pdf - Matematyka. Algebra i Geometria - heroinka94

§ 1. Problem of Algebra

Lecture 0

Page 1

Lecture 0

INTRODUCTION

This lecture is an orientation on the central problems that concern us. Speciﬁcally, we identify three

families of “Fundamental Problems” in algorithmic algebra (

1–

3). In the rest of the lecture (

4–

9), we brieﬂy discuss the complexity-theoretic background.

10 collects some common mathematical

terminology while

11 introduces computer algebra systems. The reader may prefer to skip

4-11

on a ﬁrst reading, and only use them as a reference.

All our rings will contain unity which is denoted 1 (and distinct from 0). They

are commutative except in the case of matrix rings.

The main algebraic structures of interest are:

= natural numbers 0 , 1 , 2 ,...

= integers

= rational numbers

=ls

= complex numbers

R [ X ] = polynomial ring in d

1variables X =( X 1 ,...,X n )

with coecients from a ring R .

≥

R [ X ], we let deg( P )and lead ( P )denoteits

degree and leading coecient (or leading coecient). If P = 0 then by deﬁnition, deg( P )=

∈

−∞

and

=0. Wesay P is a (respectively) integer, rational,

real or complex polynomial, depending on whether R is

≥

0and lead ( P )

I.1). With the exception of matrix

rings, all our rings are commutative. The basic algebra we assume can be obtained from classics

such as van der Waerden [22] or Zariski-Samuel [27, 28].

1. Fundamental Problem of Algebra

Consider an integer polynomial

P ( X )=

a i X i

( a i ∈ Z

,a n

=0) .

(1)

i =0

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

P ( X )=0 ,

(2)

i.e. , to ﬁnd numbers α such that P ( α ) = 0. We call such an α a solution of equation (2); alterna-

tively, α is a root or zero of the polynomial P ( X ). By deﬁnition, an algebraic number is a zero of some

polynomial P

∈ Z

[ X ]. The Fundamental Theorem of Algebra states that every non-constant poly-

is algebraically closed. d’Alembert ﬁrst

formulated this theorem in 1746 but Gauss gave the ﬁrst complete proof in his 1799 doctoral thesis

∈ C

[ X ]hasaroot α

∈ C

. Put another way,

Chee-Keng Yap

March 6, 2000

Let R be any ring. For a univariate polynomial P

lead ( P ) = 0; otherwise deg( P )

In the course of this book, we will encounter other rings: (e.g.,

nomial P ( X )

§ 1. Problem of Algebra

Lecture 0

Page 2

at Helmstedt. It follows that there are n (not necessarily distinct) complex numbers α 1 ,...,α n ∈ C

such that the polynomial in (1) is equal to

P ( X )

≡

a n

( X

−

α i ) .

(3)

i =1

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 ,weget

P ( X )= Q 1 ( X )

( X

−

α 1 )+ β 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).

−

1 with coe cients in

and β 1 ∈ C

The computational version of the Fundamental Theorem of Algebra is the problem of ﬁnding roots

of a univariate polynomial. We may dub this the Fundamental Problem of Computational Algebra

(or 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 )isthis:

Given P ( X )

∈

R 0 [ X ] , solve the equation P ( X )=0 in R 1 .

We are mainly interested in cases where

Z ⊆

R 0 ⊆

R 1 ⊆ C

. The three main versions are where

), respectively. We call them the Diophantine , real and

complex versions (respectively) of the Fundamental Problem.

) , (

)and(

What does it mean “to solve P ( X )=0in 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 ,weconsidertwo

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 1 roots, we must

address the representation of these roots. For instance, we will study a representation via “isolating

intervals”.

and R 1 denote the

complex subring comprising all those elements that can be obtained by applying a ﬁnite number of

ﬁeld operations (ring operations plus division by non-zero) and taking n th roots ( n

≥

2), starting

. 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 .Whatifdeg P> 2? This was a major 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, “The Great Art”, (1545). This was the

algebra book until Descartes’ (1637) and Euler’s Algebra (1770). Abel (1824) (also Wantzel) show

that there is no solution by radicals for a general polynomial of degree 5. Runi had a prior though

incomplete proof. This kills the hope for a single formula which solves all quintic polynomials. This

still leaves open the possibility that for each quintic polynomial, there is a formula to extract its

roots. But it is not hard to dismiss this possibility: for example, an explicit quintic polynomial that

1 There is possible confusion here: the word “enumerate” means to “count” as well as to “list by name”. Since we

are interested in both meanings here, we have to appropriate the word “enumerate” for only one of these two senses.

In this book, we try to use it only in the latter sense.

Chee-Keng Yap

March 6, 2000

where Q 1 ( X ) is a polynomial of degree n

( R 0 ,R 1 )equals(

Recall another classical version of the Fundamental Problem. Let R 0

from

§ 2. Algebraic Geometry

Lecture 0

Page 3

16 X + 2 (see [3, p.574]). Miller and Landau

[12] (also [26]) revisits these question from a complexity viewpoint. The above historical comments

may be pursued more fully in, for example, Struik’s volume [21].

Remarks: . The Fundamental Problem of algebra used to come under the rubric “theory of equa-

tions”, which nowadays is absorbed into other areas of mathematics. In these lectures, we are

interested in general and eﬀective methods, and we are mainly interested in real solutions.

2. Fundamental Problem of Classical Algebraic Geometry

To generalize the Fundamental Problem of algebra, we continue to ﬁx two rings,

Z ⊆

R 0 ⊆

R 1 ⊆ C

First consider a bivariate polynomial

P ( X, Y )

∈

R 0 [ X, Y ] .

(4)

Let Zero( P )denotethesetof R 1 -solutions of the equation P =0, i.e. ,( α, β )

∈

R 1

such that

,theset

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 reserve the term surface for the

special case d =3.

≥

R 1 , 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

∈

≥

1 polynomial equations in d

≥

1variables:

P 1 =0

P 2 =0

P m =0

(where P i ∈

R 0 [ X 1 ,...,X d ])

(5)

Apoint( α 1 ,...,α d )

∈

R 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 )=0for i =1 ,...,m . In general, for any subset J

⊆

R 0 [ X ],

denote the zero set of J . To denote the dependence on R 1 ,wemayalsowrite

Zero R 1 ( J ). If R 1 is a ﬁeld, we also call a zero set an algebraic set . 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 .Ifeach P i is

linear 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 well understood, and their

solution technique will form the basis for solving nonlinear systems.

⊆

R d

Again, we have three natural meanings 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 “inﬁnity”, we could reﬁne the

question by asking for the dimension of the zero set. (iii) Finally, the enumeration interpretation

poses no problems when there are only ﬁnitely 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 inﬁnite. Luckily, when R 1 =

Chee-Keng Yap

March 6, 2000

does not admit solution by radicals is P ( X )= X 5 −

P ( α, β )=0. The zero set Zero( P )of P is generally an inﬁnite set. In case R 1

Given two surfaces deﬁned by the equations P ( X, Y, Z )=0and Q ( X, Y, Z ) = 0, their intersection

is generally a curvilinear set of triples ( α, β, γ )

let Zero( J )

, such zero sets are

well-behaved topologically, and each zero set consists of a ﬁnite number of connected components.

§ 3. Ideal Theory

Lecture 0

Page 4

(For that matter, the counting interpretation can be re-interpreted to mean counting the number

of components of each dimension.) 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 recognition

of this, we adopt the geometric language of “points and space”. The set R d

( d -fold Cartesian product

of R 1 ) is called the d -dimensional a ne 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 ane 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 classical techniques via elimination theory for solving these Fundamental Problems. The

recent years has seen a revival of these techniques as well as major advances. In one line of work,

Wu Wen-tsun exploited Ritt’s idea of characteristic sets to give new methods for solving (5) rather

eciently in the complex case, R 1 =

Unfortunately, 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, most mathematical literature treats the

complex case. More generally, they apply to any algebraically closed ﬁeld. There is now a growing

body of results for real algebraic sets.

Another step traditionally taken to “regularize” algebraic sets is to consider projective sets, which

abolish the distinction between ﬁnite and inﬁnite 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 )todenotethe 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

≥

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 eﬀective

methods of computing semi-algebraic sets, thanks to the pioneering work of Tarski and Collins [7].

Recent work by various researchers have reduced the complexity of these algorithms from double

exponential time to single exponential space [15]. This survey also describes to applications of semi-

algebraic in algorithmic robotics, solid modeling and geometric theorem proving. Recent books on

real algebraic sets include [4, 2, 10].

3. Fundamental Problem of Ideal Theory

Algebraic sets are basically geometric objects: witness the language of “space, points, curves, sur-

faces”. 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.

Chee-Keng Yap

March 6, 2000

. These methods turn out to be useful for proving theorems

in elementary geometry as well [25]. But many applications are conﬁned to the real case ( R 1 =

§ 3. Ideal Theory

Lecture 0

Page 5

Fix

Z ⊆

R 0 ⊆

R 1 ⊆ C

as before. A polynomial P ( X )

∈

R 0 [ X ]issaidto vanish on a subset

⊆ A

d ( R 1 ) if for all a

∈

U , P ( a ) = 0. Deﬁne

Ideal( U )

⊆

R 0 [ X ]

to comprise all polynomials P

∈

R 0 [ X ]thatvanishon U .ThesetIdeal( U ) is an ideal. Recall that

a non-empty subset J

⊆

R of a ring R is an ideal if it satisﬁes the properties

1. a, b

∈

⇒

−

∈

2. c

∈

R, a

∈

⇒

∈

For any a 1 ,...,a m ∈

R and R ⊇

R ,theset( a 1 ,...,a m ) R

deﬁned by

( a 1 ,...,a m ) R :=

{

a i b i : b 1 ,...,b m ∈

R }

i =1

is an ideal, the ideal generated by a 1 ,...,a m in R . We usually omit the subscript R if this is

understood.

The Fundamental Problem of classical algebraic geometry (see Equation (5)) can be viewed as com-

puting (some characteristic property of) the zero set deﬁned 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. We may then ask for the algebraic analogue of the

Fundamental Problem of classical algebraic geometry. A naive answer is that, “given P 1 ,...,P m ,to

enumerate the set ( P 1 ,...,P m )”. Of course, this is impossible. But we eﬀectively “know” a set S

if, for any purported member x , we can decisively say whether or not x is a member of S .Thuswe

reformulate the enumerative 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 eﬀective methods to solve this problem. The technique of Grobner bases (as popularized

by Buchberger) is notable. There is strong historical basis for our claim that the ideal membership

problem is fundamental: van der Waerden [22, vol. 2, p. 159] calls it the “main problem of ideal

theory in polynomial rings”. Macaulay in the introduction to his 1916 monograph [14] states that

the “object of the algebraic theory [of ideals] is to discover those general properties of [an ideal]

which will aﬀord a means of answering the question whether a given polynomial is a member of a

given [ideal] or not”.

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 ﬁnite number of polynomials. The answer is provided by

what is perhaps the starting point of modern algebraic geometry: the Hilbert!Basis Theore .Aring

R is called Noetherian if all its ideals are ﬁnitely generated. For example, if R is a ﬁeld, 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 2 from a constructive viewpoint: it assures us

that although ideals are potentially inﬁnite sets, they are ﬁnitely describable.

2 The paradox is, many view the original proof of this theorem as initiating the modern tendencies toward non-

constructive proof methods.

Chee-Keng Yap

March 6, 2000

Mathematics - Fundamental Problems in Algorithmic Algebra.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: