MODULAR ALGORITHMS IN SYMBOLIC SUMMATION AND SYMBOLIC INTEGRATION

By DONALD JACKSON

CONTENTS 1 BACKGROUND CONCEPTS 1 1 1 COMPUTER ALGEBRA SYSTEMS 1 1 2 MATHEMATICAL PSEUDO LANGUAGE MPL 2 1 3 AUTOMATIC SIMPLI CATION AND EXPRESSION STRUCTURE 5 1 4 GENERAL POLYNOMIAL EXPRESSIONS 11 1 5 MISCELLANEOUS OPERATORS 12 2 INTEGERS RATIONAL NUMBERS AND FIELDS 17 2 1 THE INTEGERS 17 2 2 RATIONAL NUMBER ARITHMETIC 37 2 3 FIELDS 44 3 AUTOMATIC SIMPLI CATION 63 3 1 THE GOAL OF AUTOMATIC SIMPLI CATION 63 3 2 AN AUTOMATIC SIMPLI CATION ALGORITHM 91 4 SINGLE VARIABLE POLYNOMIALS 111 4 1 ELEMENTARY CONCEPTS AND POLYNOMIAL DIVISION 111 4 2 GREATEST COMMON DIVISORS IN F X 126 4 3 COMPUTATIONS IN ELEMENTARY ALGEBRAIC NUMBER FIELDS 146 4 4 PARTIAL FRACTION EXPANSION IN F X 166 5 POLYNOMIAL DECOMPOSITION 179 5 1 THEORETICAL BACKGROUND 180 5 2 A DECOMPOSITION ALGORITHM 188 6 MULTIVARIATE POLYNOMIALS 201 6 1 MULTIVARIATE POLYNOMIALS AND INTEGRAL DOMAINS 201 6 2 POLYNOMIAL DIVISION AND EXPANSION 207 6 3 GREATEST COMMON DIVISORS 229 7 THE RESULTANT 265 7 1 THE RESULTANT CONCEPT 265 7 2 POLYNOMIAL RELATIONS FOR EXPLICIT ALGEBRAIC NUMBERS 289 8 POLYNOMIAL SIMPLI CATION WITH SIDE RELATIONS 297 8 1 MULTIPLE DIVISION AND REDUCTION 297 8 2 EQUIVALENCE SIMPLI CATION AND IDEALS 318 8 3 A SIMPLI CATION ALGORITHM 334 9 POLYNOMIAL FACTORIZATION 349 9 1 SQUARE FREE POLYNOMIALS AND FACTORIZATION 350 9 2 IRREDUCIBLE FACTORIZATION THE CLASSICAL APPROACH 360 9 3 FACTORIZATION IN ZP X 370 9 4 IRREDUCIBLE FACTORIZATION A MODERN APPROACH 399 1 BACKGROUND CONCEPTS IN THIS CHAPTER WE SUMMARIZE THE BACKGROUND MATERIAL THAT PROVIDES A FRAMEWORK FOR THE MATHEMATICAL AND COMPUTATIONAL DISCUSSIONS IN THE BOOK A MORE DETAILED DISCUSSION OF THIS MATERIAL CAN BE FOUND ON THE CD THAT ACCOMPANIES THIS BOOK AND IN OUR COMPANION BOOK COMPUTER ALGEBRA AND SYMBOLIC COMPUTATION ELEMENTARY ALGORITHMS COHEN 24 READERS WHO ARE FAMILIAR WITH THIS MATERIAL MAY WISH TO SKIM THIS CHAPTER AND REFER TO IT AS NEEDED 1 1 COMPUTER ALGEBRA SYSTEMS A COMPUTER ALGEBRA SYSTEM CAS OR SYMBOL MANIPULATION SYSTEM IS A COM PUTER PROGRAM THAT PERFORMS SYMBOLIC MATHEMATICAL OPERATIONS IN THIS BOOK WE REFER TO THE COMPUTER ALGEBRA CAPABILITIES OF THE FOLLOWING THREE SYSTEMS WHICH ARE READILY AVAILABLE AND SUPPORT A PROGRAMMING STYLE THAT IS MOST SIMILAR TO THE ONE USED HERE MAPLE A VERY LARGE CAS ORIGINALLY DEVELOPED BY THE SYMBOLIC COMPUTATION GROUP AT THE UNIVERSITY OF WATERLOO CANADA AND NOW DISTRIBUTED BY WATERLOO MAPLE INC INFORMATION ABOUT MAPLE IS FOUND IN HECK 45 OR AT THE WEB SITE HTTP WWW MAPLESOFT COM MATHEMATICA A VERY LARGE CAS DEVELOPED BY WOLFRAM RESEARCH INC INFORMATION ABOUT MATHEMATICA CAN BE FOUND IN WOLFRAM 102 OR AT THE WEB SITE HTTP WWW WOLFRAM COM 1 2 1 BACKGROUND CONCEPTS MUPAD A LARGE CAS DEVELOPED BY THE UNIVERSITY OF PADERBORN GERMANY AND SCIFACE SOFTWARE GMBH CO KG INFORMATION ABOUT MUPAD CAN BE FOUND IN GERHARD ET AL 40 OR AT THE WEB SITE HTTP WWW MUPAD COM 1 2 MATHEMATICAL PSEUDO LANGUAGE MPL MATHEMATICAL PSEUDO LANGUAGE MPL IS AN ALGORITHMIC LANGUAGE THAT IS USED THROUGHOUT THIS BOOK TO DESCRIBE THE CONCEPTS EXAMPLES AND ALGO RITHMS OF COMPUTER ALGEBRA MPL ALGORITHMS ARE READILY EXPRESSED IN THE PROGRAMMING LANGUAGES OF MAPLE MATHEMATICA AND MUPAD AND IMPLE MENTATIONS OF THE DIALOGUES AND ALGORITHMS IN THESE SYSTEMS ARE INCLUDED ON THE CD THAT ACCOMPANIES THIS BOOK MATHEMATICAL EXPRESSIONS MPL MATHEMATICAL EXPRESSIONS ARE CONSTRUCTED WITH THE FOLLOWING SYMBOLS AND OPERATORS INTEGERS AND FRACTIONS THAT UTILIZE IN NITE PRECISION RATIONAL NUMBER ARITHMETIC IDENTI ERS THAT ARE USED BOTH AS PROGRAMMING VARIABLES THAT REPRE SENT THE RESULT OF A COMPUTATION AND AS MATHEMATICAL SYMBOLS THAT REPRESENT INDETERMINATES OR VARIABLES IN A MATHEMATICAL EXPRESSION THE ALGEBRAIC OPERATORS POWER AND FACTORIAL AS WITH ORDINARY MATHEMATICAL NOTATION WE USUALLY OMIT THE OPERATOR AND USE RAISED EXPONENTS FOR POWERS FUNCTION FORMS THAT ARE USED FOR MATHEMATICAL FUNCTIONS SIN X EXP X ARCTAN X ETC MATHEMATICAL OPERATORS EXPAND U FAC TOR U INTEGRAL U X ETC AND UNDE NED FUNCTIONS F X G X Y ETC THE RELATIONAL OPERATORS AND THE LOGICAL CONSTANTS TRUE AND FALSE AND THE LOGICAL OPERATORS AND OR AND NOT FINITE SETS OF EXPRESSIONS THAT UTILIZE THE SET OPERATIONS SET DI ERENCE AND SET MEMBERSHIP FOLLOWING MATHEMATICAL CONVEN TION SETS DO NOT CONTAIN DUPLICATE ELEMENTS AND THE CONTENTS OF A SET DOES NOT DEPEND ON THE ORDER OF THE ELEMENTS E G A B B A FINITE LISTS OF EXPRESSIONS A LIST IS REPRESENTED USING THE BRACKETS AND E G 1 X X2 THE EMPTY LIST WHICH CONTAINS NO EXPRESSIONS 1 2 MATHEMATICAL PSEUDO LANGUAGE MPL 3 IS REPRESENTED BY LISTS MAY CONTAIN DUPLICATE ELEMENTS AND THE ORDER OF ELEMENTS IS SIGNI CANT E G A B B A THE MPL SET AND LIST OPERATORS AND THE CORRESPONDING OPERATORS IN COMPUTER ALGEBRA SYSTEMS ARE GIVEN IN FIGURE 1 1 MPL MATHEMATICAL EXPRESSIONS HAVE TWO SOMEWHAT OVERLAPPING ROLES AS EITHER PROGRAM STATEMENTS THAT REPRESENT A COMPUTATIONAL STEP IN A PRO GRAM OR AS DATA OBJECTS THAT ARE PROCESSED BY PROGRAM STATEMENTS ASSIGNMENTS FUNCTIONS AND PROCEDURES THE MPL ASSIGNMENT OPERATOR IS A COLON FOLLOWED BY AN EQUAL SIGN AND AN ASSIGNMENT STATEMENT HAS THE FORM F U WHERE U IS A MATHEMATICAL EXPRESSION AN MPL FUNCTION DE NITION HAS THE FORM F X1 XL FUNCTION U WHERE X1 XL IS A SEQUENCE OF SYMBOLS CALLED THE FORMAL PARAMETERS AND U IS A MATHEMATICAL EXPRESSION MPL PROCEDURES EXTEND THE FUNCTION CONCEPT TO MATHEMATICAL OPERATORS THAT ARE DE NED BY A SEQUENCE OF STATEMENTS THE GENERAL FORM OF AN MPL PROCEDURE IS GIVEN IN FIGURE 1 2 FUNCTIONS AND PROCEDURES ARE INVOKED WITH AN EXPRESSION OF THE FORM F A1 AL WHERE A1 AL IS A SEQUENCE OF MATHEMATICAL EXPRESSIONS CALLED THE ACTUAL PARAMETERS IN ORDER TO PROMOTE A PROGRAMMING STYLE THAT WORKS FOR ALL LANGUAGES WE ADOPT THE FOLLOWING CONVENTIONS FOR THE USE OF LOCAL VARIABLES AND FORMAL PARAMETERS IN A PROCEDURE AN UNASSIGNED LOCAL VARIABLE CANNOT APPEAR AS A SYMBOL IN A MATH EMATICAL EXPRESSION IN SITUATIONS WHERE A PROCEDURE REQUIRES A LO CAL UNASSIGNED MATHEMATICAL SYMBOL WE EITHER PASS THE SYMBOL THROUGH THE PARAMETER LIST OR USE A GLOBAL SYMBOL FORMAL PARAMETERS ARE USED ONLY TO TRANSMIT DATA INTO A PROCEDURE AND NOT AS LOCAL VARIABLES OR TO RETURN DATA FROM A PROCEDURE WHEN WE NEED TO RETURN MORE THAN ONE EXPRESSION FROM A PROCEDURE WE RETURN A SET OR LIST OF EXPRESSIONS DECISION AND ITERATION STRUCTURES MPL PROVIDES THREE DECISION STRUCTURES THE IF STRUCTURE THE IF ELSE STRUC TURE WHICH ALLOWS FOR TWO ALTERNATIVES AND THE MULTI BRANCH DECISION STRUC TURE WHICH ALLOWS FOR A SEQUENCE OF ALTERNATIVES MPL CONTAINS TWO ITERATION STRUCTURES THAT ALLOW FOR REPEATED EVALUA TION OF A SEQUENCE OF STATEMENTS THE WHILE STRUCTURE AND THE FOR STRUCTURE SOME OF OUR PROCEDURES CONTAIN FOR LOOPS THAT INCLUDE A RETURN STATEMENT