ELIMINATION METHODS IN POLYNOMIAL COMPUTER ALGEBRA
CONTENTS CHAPTER 1 GEOMETRY ALGEBRA AND ALGORITHMS 1 1 POLYNOMIALS AND A NE SPACE 1 2 A NE VARIETIES 5 3 PARAMETRIZATIONS OF A NE VARIETIES 14 4 IDEALS 29 5 POLYNOMIALS OF ONE VARIABLE 37 CHAPTER 2 GR BNER BASES 49 1 INTRODUCTION 49 2 ORDERINGS ON THE MONOMIALS IN K X1 XN 54 3 A DIVISION ALGORITHM IN K X1 XN 61 4 MONOMIAL IDEALS AND DICKSON S LEMMA 70 5 THE HILBERT BASIS THEOREM AND GR BNER BASES 76 6 PROPERTIES OF GR BNER BASES 83 7 BUCHBERGER S ALGORITHM 90 8 FIRST APPLICATIONS OF GR BNER BASES 97 9 RE NEMENTS OF THE BUCHBERGER CRITERION 105 10 IMPROVEMENTS ON BUCHBERGER S ALGORITHM 109 CHAPTER 3 ELIMINATION THEORY 121 1 THE ELIMINATION AND EXTENSION THEOREMS 121 2 THE GEOMETRY OF ELIMINATION 129 3 IMPLICITIZATION 132 4 SINGULAR POINTS AND ENVELOPES 143 5 GR BNER BASES AND THE EXTENSION THEOREM 156 6 RESULTANTS AND THE EXTENSION THEOREM 161 CHAPTER 4 THE ALGEBRA GEOMETRY DICTIONARY 177 1 HILBERT S NULLSTELLENSATZ 177 2 RADICAL IDEALS AND THE IDEAL VARIETY CORRESPONDENCE 183 3 SUMS PRODUCTS AND INTERSECTIONS OF IDEALS 191 4 ZARISKI CLOSURES IDEAL QUOTIENTS AND SATURATIONS 201 5 IRREDUCIBLE VARIETIES AND PRIME IDEALS 210 6 DECOMPOSITION OF A VARIETY INTO IRREDUCIBLES 216 7 PROOF OF THE CLOSURE THEOREM 223 8 PRIMARY DECOMPOSITION OF IDEALS 232 9 SUMMARY 236 CHAPTER 5 POLYNOMIAL AND RATIONAL FUNCTIONS ON A VARIETY 237 1 POLYNOMIAL MAPPINGS 237 2 QUOTIENTS OF POLYNOMIAL RINGS 244 3 ALGORITHMIC COMPUTATIONS IN K X1 XN I 252 4 THE COORDINATE RING OF AN A NE VARIETY 262 5 RATIONAL FUNCTIONS ON A VARIETY 274 6 RELATIVE FINITENESS AND NOETHER NORMALIZATION 284 CHAPTER 6 ROBOTICS AND AUTOMATIC GEOMETRIC THEOREM PROVING 297 1 GEOMETRIC DESCRIPTION OF ROBOTS 297 2 THE FORWARD KINEMATIC PROBLEM 303 3 THE INVERSE KINEMATIC PROBLEM AND MOTION PLANNING 310 4 AUTOMATIC GEOMETRIC THEOREM PROVING 325 5 WU S METHOD 341 CHAPTER 7 INVARIANT THEORY OF FINITE GROUPS 351 1 SYMMETRIC POLYNOMIALS 351 2 FINITE MATRIX GROUPS AND RINGS OF INVARIANTS 363 3 GENERATORS FOR THE RING OF INVARIANTS 372 4 RELATIONS AMONG GENERATORS AND THE GEOMETRY OF ORBITS 380 CHAPTER 8 PROJECTIVE ALGEBRAIC GEOMETRY 393 1 THE PROJECTIVE PLANE 393 2 PROJECTIVE SPACE AND PROJECTIVE VARIETIES 404 3 THE PROJECTIVE ALGEBRA GEOMETRY DICTIONARY 414 4 THE PROJECTIVE CLOSURE OF AN A NE VARIETY 423 5 PROJECTIVE ELIMINATION THEORY 430 6 THE GEOMETRY OF QUADRIC HYPERSURFACES 445 7 BEZOUT S THEOREM 460 CHAPTER 1 GEOMETRY ALGEBRA AND ALGORITHMS THIS CHAPTER WILL INTRODUCE SOME OF THE BASIC THEMES OF THE BOOK THE GEOMETRY WE ARE INTERESTED IN CONCERNS A NE VARIETIES WHICH ARE CURVES AND SURFACES AND HIGHER DIMENSIONAL OBJECTS DE NED BY POLYNOMIAL EQUATIONS TO UNDERSTAND A NE VARIETIES WE WILL NEED SOME ALGEBRA AND IN PARTICULAR WE WILL NEED TO STUDY IDEALS IN THE POLYNOMIAL RING K X1 XN FINALLY WE WILL DISCUSS POLYNOMIALS IN ONE VARIABLE TO ILLUSTRATE THE ROLE PLAYED BY ALGORITHMS 1 POLYNOMIALS AND A NE SPACE TO LINK ALGEBRA AND GEOMETRY WE WILL STUDY POLYNOMIALS OVER A ELD WE ALL KNOW WHAT POLYNOMIALS ARE BUT THE TERM ELD MAY BE UNFAMILIAR THE BASIC INTUITION IS THAT A ELD IS A SET WHERE ONE CAN DE NE ADDITION SUBTRACTION MULTIPLICATION AND DIVISION WITH THE USUAL PROPERTIES STANDARD EXAMPLES ARE THE REAL NUMBERS AND THE COMPLEX NUMBERS WHEREAS THE INTEGERS ARE NOT A ELD SINCE DIVISION FAILS 3 AND 2 ARE INTEGERS BUT THEIR QUOTIENT 3 2 IS NOT THE FORMAL DE NITION OF A ELD MAY BE FOUND IN DE NITION 1 OF APPENDIX A 1 ONE REASON THAT ELDS ARE IMPORTANT IS THAT LINEAR ALGEBRA WORKS OVER ANY ELD THUS EVEN IF YOUR LINEAR ALGEBRA COURSE RESTRICTED THE SCALARS TO LIE IN OR MOST OF THE THEOREMS AND TECHNIQUES YOU LEARNED APPLY TO AN ARBITRARY ELD K IN THIS BOOK WE WILL EMPLOY DI ERENT ELDS FOR DI ERENT PURPOSES THE MOST COMMONLY USED ELDS WILL BE THE RATIONAL NUMBERS THE ELD FOR MOST OF OUR COMPUTER EXAMPLES THE REAL NUMBERS THE ELD FOR DRAWING PICTURES OF CURVES AND SURFACES THE COMPLEX NUMBERS THE ELD FOR PROVING MANY OF OUR THEOREMS 1 ON OCCASION WE WILL ENCOUNTER OTHER ELDS SUCH AS ELDS OF RATIONAL FUNCTIONS SEE DE NITION 1 OF 3 THERE IS ALSO A VERY INTERESTING THEORY OF NITE ELDS SEE THE EXERCISES FOR ONE OF THE SIMPLER EXAMPLES WE CAN NOW DE NE POLYNOMIALS THE READER CERTAINLY IS FAMILIAR WITH POLYNOMIALS IN ONE AND TWO VARIABLES BUT WE WILL NEED TO DISCUSS POLYNOMIALS IN N VARIABLES X1 XN WITH COE CIENTS IN AN ARBITRARY ELD K WE START BY DE NING MONOMIALS DE NITION 1 A MONOMIAL IN X1 XN IS A PRODUCT OF THE FORM XA1 1 XA2 2 XAN N WHERE ALL OF THE EXPONENTS A1 AN ARE NONNEGATIVE INTEGERS THE TOTAL DEGREE OF THIS MONOMIAL IS THE SUM A1 AN WE CAN SIMPLIFY THE NOTATION FOR MONOMIALS AS FOLLOWS LET A A1 AN BE AN N TUPLE OF NONNEGATIVE INTEGERS THEN WE SET XA XA1 1 XA2 2 XAN N WHEN A 0 0 NOTE THAT XA 1 WE ALSO LET A A1 AN DENOTE THE TOTAL DEGREE OF THE MONOMIAL XA DE NITION 2 A POLYNOMIAL F IN X1 XN WITH COE CIENTS IN A ELD K IS A NITE LINEAR COMBINATION WITH COE CIENTS IN K OF MONOMIALS WE WILL WRITE A POLYNOMIAL F IN THE FORM A F A AAX AA K WHERE THE SUM IS OVER A NITE NUMBER OF N TUPLES A A1 AN THE SET OF ALL POLYNOMIALS IN X1 XN WITH COE CIENTS IN K IS DENOTED K X1 XN WHEN DEALING WITH POLYNOMIALS IN A SMALL NUMBER OF VARIABLES WE WILL USUALLY DISPENSE WITH SUBSCRIPTS THUS POLYNOMIALS IN ONE TWO AND THREE VARIABLES LIE IN K X K X Y AND K X Y Z RESPECTIVELY FOR EXAMPLE F 2X3Y2Z 3 2 Y3Z3 3XYZ Y2 IS A POLYNOMIAL IN X Y Z WE WILL USUALLY USE THE LETTERS F G H P Q R TO REFER TO POLYNOMIALS WE WILL USE THE FOLLOWING TERMINOLOGY IN DEALING WITH POLYNOMIALS DE NITION 3 LET F A AAXA BE A POLYNOMIAL IN K X1 XN I WE CALL AA THE COE CIENT OF THE MONOMIAL XA II IF AA 0 THEN WE CALL AAXA A TERM OF F III THE TOTAL DEGREE OF F 0 DENOTED DEG F IS THE MAXIMUM A SUCH THAT THE COE CIENT AA IS NONZERO THE TOTAL DEGREE OF THE ZERO POLYNOMIAL IS UNDE NED AS AN EXAMPLE THE POLYNOMIAL F 2X3Y2Z 3 2 Y3Z3 3XYZ Y2 GIVEN ABOVE HAS FOUR TERMS AND TOTAL DEGREE SIX NOTE THAT THERE ARE TWO TERMS OF MAXIMAL TOTAL DEGREE WHICH IS SOMETHING THAT CANNOT HAPPEN FOR POLYNOMIALS OF ONE VARIABLE IN CHAPTER 2 WE WILL STUDY HOW TO ORDER THE TERMS OF A POLYNOMIAL ELIMINATION METHODS IN POLYNOMIAL COMPUTER ALGEBRA 2 THE SUM AND PRODUCT OF TWO POLYNOMIALS IS AGAIN A POLYNOMIAL WE SAY THAT A POLYNOMIAL F DIVIDES A POLYNOMIAL G PROVIDED THAT G F H FOR SOME POLYNOMIAL H K X1 XN ONE CAN SHOW THAT UNDER ADDITION AND MULTIPLICATION K X1 XN SATIS ES ALL OF THE ELD AXIOMS EXCEPT FOR THE EXISTENCE OF MULTIPLICATIVE INVERSES BECAUSE FOR EXAMPLE 1 X1 IS NOT A POLYNOMIAL SUCH A MATHEMATICAL STRUCTURE IS CALLED A COMMUTATIVE RING SEE DE NITION 2 OF APPENDIX A 1 FOR THE FULL DE NITION AND FOR THIS REASON WE WILL REFER TO K X1 XN AS A POLYNOMIAL RING THE NEXT TOPIC TO CONSIDER IS A NE SPACE DE NITION 4 GIVEN A ELD K AND A POSITIVE INTEGER N WE DE NE THE N DIMENSIONAL A NE SPACE OVER K TO BE THE SET KN A1 AN A1 AN K FOR AN EXAMPLE OF A NE SPACE CONSIDER THE CASE K HERE WE GET THE FAMILIAR SPACE N FROM CALCULUS AND LINEAR ALGEBRA IN GENERAL WE CALL K1 K THE A NE LINE AND K2 THE A NE PLANE LET US NEXT SEE HOW POLYNOMIALS RELATE TO A NE SPACE THE KEY IDEA IS THAT A POLYNOMIAL F A AAXA K X1 XN GIVES A FUNCTION F KN K DE NED AS FOLLOWS GIVEN A1 AN KN REPLACE EVERY XI BY AI IN THE EXPRESSION FOR F SINCE ALL OF THE COE CIENTS ALSO LIE IN K THIS OPERATION GIVES AN ELEMENT F A1 AN K THE ABILITY TO REGARD A POLYNOMIAL AS A FUNCTION IS WHAT MAKES IT POSSIBLE TO LINK ALGEBRA AND GEOMETRY THIS DUAL NATURE OF POLYNOMIALS HAS SOME UNEXPECTED CONSEQUENCES FOR EXAMPLE THE QUESTION IS F 0 NOW HAS TWO POTENTIAL MEANINGS IS F THE ZERO POLYNOMIAL WHICH MEANS THAT ALL OF ITS COE CIENTS AA ARE ZERO OR IS F THE ZERO FUNCTION WHICH MEANS THAT F A1 AN 0 FOR ALL A1 AN KN THE SURPRISING FACT IS THAT THESE TWO STATEMENTS ARE NOT EQUIVALENT IN GENERAL FOR AN EXAMPLE OF HOW THEY CAN DI ER CONSIDER THE SET CONSISTING OF THE TWO ELEMENTS 0 AND 1 IN THE EXERCISES WE WILL SEE THAT THIS CAN BE MADE INTO A ELD WHERE 1 1 0 THIS ELD IS USUALLY CALLED F2 NOW CONSIDER THE POLYNOMIAL X2 X X X 1 F2 X SINCE THIS POLYNOMIAL VANISHES AT 0 AND 1 WE HAVE FOUND A NONZERO POLYNOMIAL WHICH GIVES THE ZERO FUNCTION ON THE A NE SPACE F1 2 OTHER EXAMPLES WILL BE DISCUSSED IN THE EXERCISES HOWEVER AS LONG AS K IS IN NITE THERE IS NO PROBLEM PROPOSITION 5 LET K BE AN IN NITE ELD AND LET F K X1 XN THEN F 0 IN K X1 XN IF AND ONLY IF F KN K IS THE ZERO FUNCTION PROOF ONE DIRECTION OF THE PROOF IS OBVIOUS SINCE THE ZERO POLYNOMIAL CLEARLY GIVES THE ZERO FUNCTION TO PROVE THE CONVERSE WE NEED TO SHOW THAT IF F A1 AN 0 FOR ALL A1 AN KN THEN F IS THE ZERO POLYNOMIAL WE WILL USE INDUCTION ON THE NUMBER OF VARIABLES N ELIMINATION METHODS IN POLYNOMIAL COMPUTER ALGEBRA 3