EXPERIMENTAL NUMBER THEORY
CONTENTS BASIC EXAMPLES 1 1 HOW THINGS VARY WITH P 1 1 1 QUADRATIC RECIPROCITY LAW 1 1 2 SIGN FUNCTIONS 1 1 3 CHECKING MODULARITY OF SIGN FUNCTIONS 1 1 4 EXAMPLES 1 2 RECOGNIZING NUMBERS 1 2 1 RATIONAL NUMBERS IN R 1 2 2 RATIONAL NUMBERS MODULO M 1 2 3 ALGEBRAIC NUMBERS 1 3 BERNOULLI POLYNOMIALS 1 3 1 DE?NITION AND PROPERTIES 1 3 2 CALCULATION 1 3 3 RELATED QUESTIONS 1 3 4 PROOFS 1 4 SUMS OF SQUARES 1 4 1 K = 1 4 2 K = 1 4 4 THE NUMBERS RK(N) 1 4 5 THETA FUNCTIONS 1 5 EXERCISES RECIPROCITY 2 1 MORE VARIATION WITH P 2 1 1 LOCAL ZETA FUNCTIONS 2 1 2 FORMULATION OF RECIPROCITY 2 1 3 GLOBAL ZETA FUNCTIONS 2 2 THE CUBIC CASE 2 2 1 TWO EXAMPLES 2 2 2 A MODULAR CASE 2 2 3 A NON-MODULAR CASE 2 3 THE ARTIN MAP 2 3 1 A GALOIS EXAMPLE 2 3 2 A NON-GALOIS EXAMPLE 2 4 QUANTITATIVE VERSION 2 4 1 APPLICATION OF A THEOREM OF TCHEBOTAREV 2 4 2 COMPUTING DENSITIES NUMERICALLY 2 5 GALOIS GROUPS 2 5 1 TCHEBOTAREV’S THEOREM 2 5 2 TRINK’S EXAMPLE 2 5 3 AN EXAMPLE RELATED TO TRINK’S 2 6 EXERCISES POSITIVE DE?NITE BINARY QUADRATIC FORMS 3 1 BASIC FACTS 3 1 1 REDUCTION 3 1 2 CORNACHIA’S ALGORITHM 3 1 3 CLASS NUMBER 3 1 4 COMPOSITION 3 2 EXAMPLES OF RECIPROCITY FOR IMAGINARY QUADRATIC ?ELDS 3 2 1 DIHEDRAL GROUP OF ORDER 3 2 2 THETA FUNCTIONS AGAIN 3 2 3 DIHEDRAL GROUP OF ORDER 3 2 4 AN EXAMPLE OF F VOLOCH 3 2 5 FINAL COMMENTS 3 3 EXERCISES SEQUENCES 4 1 TRINOMIAL NUMBERS 4 1 1 FORMULA 4 1 2 DIFFERENTIAL EQUATION AND LINEAR RECURRENCE 4 1 3 ALGEBRAIC EQUATION 4 1 4 HENSEL’S LEMMA AND NEWTON’S METHOD 4 1 5 CONTINUED FRACTIONS 4 1 6 ASYMPTOTICS 4 1 7 MORE COEF?CIENTS IN THE ASYMPTOTIC EXPANSION 4 1 8 CAN WE SUM THE ASYMPTOTIC SERIES? 4 2 RECOGNIZING SEQUENCES 4 2 1 VALUES OF A POLYNOMIAL 4 2 2 VALUES OF A RATIONAL FUNCTION 4 2 3 CONSTANT TERM RECURSION 4 2 4 A SIMPLE EXAMPLE 4 3 EXERCISES COMBINATORICS 5 1 DESCRIPTION OF THE BASIC ALGORITHM 5 2 PARTITIONS 5 2 1 THE NUMBER OF PARTITIONS 5 2 2 DUAL PARTITION 5 3 IRREDUCIBLE REPRESENTATIONS OF SN 5 3 1 HOOK FORMULA 5 3 2 THE MURNAGHAN–NAKAYAMA RULE 5 3 3 COUNTING SOLUTIONS TO EQUATIONS IN SN 5 3 4 COUNTING HOMOMORPHISM AND SUBGROUPS 5 4 CYCLOTOMIC POLYNOMIALS 5 4 1 VALUES OF ? BELOW A GIVEN BOUND 5 4 2 COMPUTING CYCLOTOMIC POLYNOMIALS 5 5 EXERCISES P-ADIC NUMBERS 6 1 BASIC FUNCTIONS 6 1 1 MAHLER’S EXPANSION 6 1 2 HENSEL’S LEMMA AND NEWTON’S METHOD (AGAIN) 6 2 THE P-ADIC GAMMA FUNCTION 6 2 1 THE MULTIPLICATION FORMULA 6 3 THE LOGARITHMIC DERIVATIVE OF P 6 3 1 APPLICATION TO HARMONIC SUMS 6 3 2 A FORMULA OF J DIAMOND 6 3 3 POWER SERIES EXPANSION OF ?P(X) 6 3 4 APPLICATION TO CONGRUENCES 6 4 ANALYTIC CONTINUATION 6 4 1 AN EXAMPLE OF DWORK 6 4 2 A GENERALIZATION 6 4 3 DWORK’S EXPONENTIAL 6 5 GAUSS SUMS AND THE GROSS–KOBLITZ FORMULA 6 5 1 THE CASE OF FP 6 5 2 AN EXAMPLE 6 6 EXERCISES POLYNOMIALS 7 1 MAHLER’S MEASURE 7 1 1 SIMPLE SEARCH 7 1 2 RE?NING THE SEARCH 7 1 3 COUNTING ROOTS ON THE UNIT CIRCLE 7 2 APPLICATIONS OF THE GRAEFFE MAP 7 2 1 DETECTING CYCLOTOMIC POLYNOMIALS 7 2 2 DETECTING CYCLOTOMIC FACTORS 7 2 3 WEDGE PRODUCT POLYNOMIAL 7 2 4 INTERLACING ROOTS OF UNITY 7 3 EXERCISES REMARKS ON SELECTED EXERCISES REFERENCES QUADRATIC RECIPROCITY LAW RECALL THAT A DIRICHLET CHARACTER ? MODULO M IS A GROUP HOMOMORPHISM ? : (Z/MZ)???C? (1 2) FOLLOWING A COMMON ABUSE OF NOTATION WE ALSO DENOTE BY ? THE FUNCTION ON Z WITH VALUES IN C DE?NED BY A ??(A MOD M) IF GCD(A, M) = 1 AND HOW THINGS VARY WITH P AND DISC(A) = ?3, WHEREAS A = Q( ? 3) HAS MINIMAL MODEL X2 ?3 AND DISC(A) = 12 THE DISCRIMINANT D := B2 ?4AC = DISC(F ) OF ANY POLYNOMIAL F = AX2 + BX+C ?Z[X] WITH A ?Q[X]/(F ) IS OF THE FORM Z2 DISC(A) FOR SOME NON-ZERO INTEGER Z NOTE THAT D ?0, 1 MOD 4; WE CALL ANY NON-ZERO INTEGER D WITH THIS PROPERTY A DISCRIMINANT (IT IS EASY TO CHECK THAT ANY DISCRIMINANT IS INDEED THE DISCRIMINANT OF SUCH AN F ) WE SAY THAT D IS A FUNDAMENTAL DISCRIMINANT IF IT IS THE DISCRIM- INANT OF A QUADRATIC ÉTALE ALGEBRA (IN GP, WE MAY TEST THIS WITH ISFUNDAMENTAL(D), WHICH RETURNS 1 IF TRUE AND 0 IF NOT ) LET US NOTE THAT D = 1 IS A FUNDAMENTAL DISCRIMINANT; IT CORRESPONDS TO THE ONLY QUADRATIC ÉTALE ALGEBRA WHICH IS NOT A ?ELD, NAMELY, Q × Q 1 : BASIC EXAMPLES HERE IS A SHORT LIST OF FUNDAMENTAL DISCRIMINANTS COMPUTED WITH GP ? FOR(D=-20,20,IF(ISFUNDAMENTAL(D),PRINT1(D," "))) -20 -19 -15 -11 -8 -7 -4 -3 1 5 8 12 13 ONE WAY TO THINK OF THE QUADRATIC RECIPROCITY IS THAT IT ESTABLISHES A ONE TO ONE CORRESPONDENCE A ???A, BETWEEN ISOMORPHISM CLASSES OF QUADRATIC ÉTALE ALGEBRAS AND PRIMITIVE DIRICHLET CHARACTERS OF ORDER DIVIDING 2 UNDER THIS CORRESPONDENCE WE HAVE COND(?A) = | DISC(A)| AND NA(P) = ?A(P) + (1 4) FOR ALL PRIMES P, WHERE NA(P) IS THE NUMBER OF SOLUTIONS TO THE CONGRUENCE F (X) ?0 MOD P WITH F A GLOBAL MINIMAL MODEL OF A IF F ?Z[X] IS AN ARBITRARY EQUATION DE?NING A THEN (1 4) IS VALID FOR ALL BUT ?NITELY MANY PRIMES IN PARTICULAR, WE MAY TAKE THE EQUATION F = X2 ?DISC(A) AND GIVE (1 4) IN THE MORE FAMILIAR FORM IN TERMS OF QUADRATIC SYMBOLS ?A(P) = DISC(A) P (1 5) THIS IS ACTUALLY VALID FOR ALL PRIMES P (USING THE KRONECKER SYMBOL ON THE RIGHT HAND SIDE) FOR EXAMPLE, IF A = Q( ? ±2) THEN DISC(A) = ±8 AND ?A ARE THE TWO PRIMITIVE CHARACTERS MENTIONED ABOVE FOR COMPLETENESS LET US CHECK A NUMERICAL EXAMPLE BY BRUTE FORCE SAY F = X2 + X ?1 A GLOBAL MINIMAL MODEL FOR THE ALGEBRA A = Q( ? 5) FIRST WE NEED A FUNCTION THAT WILL COMPUTE N(P) COUNT(F,P)=SUM(A=0,P-1,SUBST(F,X,MOD(A,P))==0) NOTE THE SOMEWHAT UNUSUAL MIXTURE OF BOOLEAN AND STANDARD ARITHMETIC: THE TERM IN THE SUM (SUBST(F,X,MOD(A,P))==0) IS 1 IF F (A) ?0 MOD P AND IS 0 OTHERWISE ? FORPRIME(P=2,50,PRINT(P, "\T", COUNT(Xˆ2+X-1,P), "\T", KRONECKER(5,P)+1)) SIGN FUNCTIONS WE CALL ANY FUNCTION SENDING PRIMES TO {?1, 0, 1} A SIGN FUNCTION WE SAY THAT A SIGN FUNCTION IS MODULAR IF (P) = ?(P) FOR SOME PRIMITIVE DIRICHLET CHARACTER ? FOR ALL BUT ?NITELY MANY P (THERE IS NO LOSS OF GENERALITY IN ASSUMING THAT ? IS PRIMITIVE AS WE ARE WILLING TO IGNORE A ?NITE SET OF PRIMES) IF M IS THE CONDUCTOR OF ? WE SAY THAT IS MODULAR OF CONDUCTOR M FOR EXAMPLE, WE MAY STATE THE QUADRATIC RECIPROCITY LAW AS SAYING THAT FOR ANY QUADRATIC ÉTALE ALGEBRA A THE MAP P ?NA(P) ?1 IS MODULAR WITH CHARACTER ?A WE WILL DISCUSS IN MORE DETAIL WHAT HAPPENS WITH N(P) FOR ONE-VARIABLE POLYNOMIALS OF HIGHER DEGREE IN THE NEXT CHAPTER FOR THE MOMENT, HOWEVER, CONSIDER THE FOLLOWING SIGN FUNCTION GIVEN A MONIC POLYNOMIAL F ?Z[X] WITH NON-ZERO DISCRIMINANT D DE?NE F (P) = (?1) H(DEG(H)+1) IF P ?D IF P | D (1 6) WHERE F ? H H MOD P IS THE FACTORIZATION OF F INTO IRREDUCIBLE FACTORS MODULO P (THE VALUE OF F (P) FOR P ?D IS THE SIGN OF ANY PERMUTATION IN THE FROBENIUS CONJUGACY CLASS FROBP SEE §2 3 ) THE QUADRATIC RECIPROCITY LAW IMPLIES THAT F IS MODULAR FOR F QUADRATIC THIS IS IN FACT TRUE IN GENERAL EXAMPLES HERE IS A GP SCRIPT TO COMPUTE THE SIGN FUNCTION F WE ASSOCIATED (1 6) TO POLYNOMIALS SGN(F,P)= { IF(POLDISC(F)%P,RETURN(0)); F=FACTORMOD(F,P); (-1)ˆSUM(J=1,LENGTH(F˜),POLDEGREE(F[J,1])+1) } THIS IS A LITERAL TRANSLATION OF THE MATHEMATICAL DE?NITION (1 6) THE CON- DITIONAL IF(POLDISC(F)%P,,) TESTS WHETHER P DIVIDES THE DISCRIMINANT D OF THE POLYNOMIAL F BY COMPUTING THE REMAINDER OF 1 : BASIC EXAMPLES THE DIVISION OF D BY P IF THE REMAINDER IS NON-ZERO (?RST OPTION) WE ?RST COMPUTE THE FACTORIZATION OF F MOD P WITH F=FACTORMOD(F,P) AND THEN THE EXPRESSION IN (1 6) IN TERMS OF THE FACTORS, OTHERWISE (SECOND OPTION) WE RETURN ZERO NOTE HOW WE RECYCLED VARIABLES BY ASSIGNING THE RESULT OF FACTORMOD(F,P) TO F ITSELF THIS MODI?CATION IS LOCAL TO THE FUNCTION SGN AND DOES NOT AFFECT THE ACTUAL INPUT POLYNOMIAL IN OTHER WORDS, IF WE HAD PREVIOUSLY DE?NED SAY F=2*X+1 AND THEN DO SGN(F,5) THE VALUE OF F WOULD NOT BE CHANGED WE CAN ALSO IMPROVE THE CODE BY USING THE FEATURE OF FACTORMOD THAT RETURNS THE DEGREES OF THE FACTORS WITHOUT THE FACTORS THEMSELVES (WHICH WE DO NOT ACTUALLY USE) SEE POLFACTTYPE IN §2 2 FOR AN EXAMPLE AS AN ILLUSTRATION LET US COMPUTE THE SIGN FUNCTION FOR THE ?FTH CYCLOTOMIC POLYNOMIAL F = X4 + X3 + X2 + X + 1 (GIVEN IN GP BY POLCYCLO(5)) AND ALL PRIMES P ?50 SUPPOSE THAT ALL THE RELEVANT FUNCTIONS ARE IN A ?LE MOD- SIGNS GP IN THE CURRENT DIRECTORY WHERE GP IS RUNNING WE START BY READING THIS ?LE INTO GP BY TYPING ? \R MOD-SIGNS GP THEN WE TYPE, FOR EXAMPLE, ? V=[]; FORPRIME(P=2,50, V=CONCAT(V,[[P,SGN(POLCYCLO(5),P)]]));V AT THE PROMPT AND GET [[2, -1], [3, -1], [5, 0], [7, -1], [11, 1], [13, -1], [17, -1], [19, 1], [23, -1], [29, 1], [31, 1], [37, -1], [41, 1], [43, -1], [47, -1]] WE TEST WITH ? TESTMOD(V,50) GETTING THE ANSWER [5, 0] THIS OF COURSE AGREES WITH THEOREM 1 1 SINCE THE DISCRIMINANT OF F IS (1 10) RECOGNIZING NUMBERS IN PRACTICE WE SHOULD INCREASE THE PRECISION OF OUR CALCULATION AND RUN RECOGNIZE AGAIN TO SEE IF THE ANSWER REMAINS THE SAME WE SHOULD EMPHA- SIZE THAT, OF COURSE, THERE IS NO WAY TO PROVE WITH A COMPUTER THAT AN UNKNOWN REAL NUMBER IS RATIONAL NO MATTER HOW GOOD AN APPROXIMATION OF IT WE HAVE WE SHOULD CLARIFY WHAT IS THE OUTPUT OF CONTFRAC IF THE INPUT IS RATIONAL THEN THE CONTINUED FRACTION TERMINATES AND WE GET IT EXACTLY IF THE INPUT IS A REAL NUMBER X ONLY KNOWN TO N SIGNI?CANT DIGITS (I E , WE KNOW RATIONAL NUMBERS A, B SUCH THAT A ?X ?B WITH 0 ?B/A?1 ?10?N) THEN CONTFRAC RETURNS THOSE PARTIAL QUOTIENTS THAN CAN BE CORRECTLY COMPUTED WITH THIS KNOWLEDGE ALONE (FOR A RANDOM NUMBER WE EXPECT TO GET 0 97 PARTIAL QUOTIENTS PER DECIMAL DIGIT, SEE [52] VOL 2, 4 5 4 EX 47 ) WE SHOULD STRESS THAT THIS, IN GENERAL, IS NOT THE SAME AS THE FRACTION P/Q WHICH MINIMIZES |X ?P/Q|, 1 ?Q ?Q, (1 13) SEE BELOW AND EX 3 ALSO WE MAY USE BESTAPPR FOR THE FOLLOWING ALTERNATE VERSION OF RECOGNIZE RECOGNIZE2(X)=BESTAPPR(X, 10ˆ(PRECISION(X) - 5)) WHAT DO WE DO IF WE ONLY KNOW THAT R IS RATIONAL BUT HAVE NO WAY TO IMPROVE OUR APPROXIMATION X OF IT? IN A WONDERFUL EXERCISE D KNUTH, [52] VOL 2 §4 5 3 EX 39, ASKS AT LEAST HOW MANY TIMES A BASEBALL PLAYER HAS BATTED IF HIS AVERAGE IS 334 (THE BATTING AVERAGE, IS THE RATIONAL NUMBER 0 ?H/B ?1 ROUNDED TO THREE DECIMAL PLACES, WHERE H IS THE NUMBER OF HITS AND B THE NUMBER OF BATTINGS ) TO SOLVE THE PROBLEM WE NEED TO ?ND THE FRACTION 3335 ?P/Q ? 3345 WITH SMALLEST POSSIBLE Q THE ANSWER IS 96/287 (NOT 1/3!) AND HENCE THE PLAYER MUST HAVE BATTED AT LEAST 287 TIMES THE SOLUTION TO THE GENERAL PROBLEM OF ?NDING P/Q ?[A, B] WITH THE SMALLEST POSSIBLE Q IS DESCRIBED IN [52] AND ITEM 101C BY R GOSPER IN [6] HERE IS A GP IMPLEMENTATION GOSPER(V)= { LOCAL(A,B,J,L,C); A=CONTFRAC(V[1]); B=CONTFRAC(V[2]); J=1; L=MIN(LENGTH(A),LENGTH(B)); WHILE(J <= L && A[J] == B[J],J++); C=VECTOR(J-1,K,A[K]); IF(J <= L, C=CONCAT(C,IF(A[J] < B[J],A[J],B[J])+1)); C=CONTFRACPNQN(C); C[1,1]/C[2,1] } MEASURED AS IN (1 12) ? \P FOR SOME RELATIVELY PRIME INTEGERS A, B; CAN WE RECOVER A AND B? THIS IS INDEED POSSIBLE IF |A|, |B| ? M/2 USING CONTINUED FRACTIONS (SEE [62], CHAPTER 4, [97], [24]) WRITE BC = A + DM FOR SOME D ?Z THEN C M ?D B = A BM ? EVALUATED AT ?, WHICH IS PRECISELY WHAT WE WANT THIS IS AN APPROXIMATION TO ? := 1 + 1 + 1 + ? 2 AN ALGEBRAIC INTEGER OF DEGREE AT MOST 8 WE TRY TO ?ND TO ?ND ITS MINIMAL POLYNOMIAL WITH ? ALGDEP(A,8) Xˆ8 - 8*Xˆ7 + 24*Xˆ6 - 32*Xˆ5 + 14*Xˆ4 + 8*Xˆ3 - 8*Xˆ2 THIS LOOKS LIKE THE CORRECT ANSWER AS THE COEF?CIENTS ARE FAIRLY SMALL AND DO NOT CHANGE IF WE RECALCULATE TO A HIGHER PRECISION IN THIS CASE IT IS IN FACT EASY TO PROVE THAT IT IS CORRECT (EX 7) IN GENERAL, AS WITH RECOGNIZE, WE CAN ONLY MAKE A GOOD GUESS FOR EXAMPLE, WE KNOW ? IS TRANSCENDENTAL; WHAT HAPPENS IF WE TRY TO A ?ND A POLYNOMIAL EQUATION WITH INTEGER COEF?CIENT FOR IT? ? ALGDEP(PI,5) 909*Xˆ5 - 3060*Xˆ4 + 1814*Xˆ3 - 3389*Xˆ2 - 723*X ? \P REALPRECISION = 57 SIGNIFICANT DIGITS ? ALGDEP(PI,5) 16352996*Xˆ5 - 41843628*Xˆ4 - 17559998*Xˆ3 - 25865436*Xˆ2 - 49411721*X + WHAT WE OBTAIN IS A FAIRLY MEANINGLESS POLYNOMIAL WITH LARGE COEF?CIENTS WHICH HAS A VERY SMALL VALUE AT X = ? IT IS A HIGHER DEGREE ANALOGUE OF TRYING TO RECOGNIZE ? AS A RATIONAL NUMBER ? \P REMARK A GOOD APPROXIMATION FOR OUR UNKNOWN NUMBER COULD ALSO BE P-ADIC FOR EXAMPLE, ? A=SQRT(-1 + O(5ˆ10)) 2 + 5 + 2*5ˆ2 + 5ˆ3 + 3*5ˆ4 + 4*5ˆ5 + 2*5ˆ6 + 3*5ˆ7 + 3*5ˆ9 + O(5ˆ10) ? ALGDEP(A,2) Xˆ2 + ? ?5) = 2(1 + ? 5) + ? ALGDEP(%,4) Xˆ4 - 2*Xˆ3 - 2*Xˆ2 - 2*X + THIS CALCULATION IS NOT A PROOF OF (1 16) WE SHOULD POINT OUT, HOW- EVER, THAT GIVEN SOME A PRIORI KNOWLEDGE ON THE NUMBER WE ARE COMPUTING 1 : BASIC EXAMPLES (A BOUND ON ITS DEGREE AND HEIGHT) ONE CAN ACTUALLY PROVE THAT THE OUTPUT POLYNOMIAL OF ALGDEP IS CORRECT (SEE [7]) IT IS OF INVALUABLE HELP TO HAVE THESE TOOLS AVAILABLE WHEN INVESTIGATING CERTAIN QUESTIONS AT THE END OF THE DAY WE MAY TOSS ALL CALCULATIONS ASIDE AND KEEP ONLY THE PROOFS WE FOUND BUT THE PROOFS MIGHT NOT HAVE BEEN FOUND WITHOUT THE INTERVENING CALCULATIONS IN THIS SITUATION OF CM ONE CAN IN PRINCIPLE ?GURE OUT EXPRESSIONS FOR ALL THE GALOIS CONJUGATES ?1, , ?N OF A NUMBER LIKE THE LEFT HAND SIDE OF (1 16) WE OFTEN ALSO KNOW IN ADVANCE THAT THE NUMBERS ARE ACTUALLY ALGEBRAIC INTEGERS IN THIS CASE IT IS THEN EASY TO COMPUTE EXACTLY WHAT THE MINIMAL POLYNOMIAL IS WITHOUT ANY GUESSWORK (GIVEN APPROXIMATIONS TO ?1, , ?N WE JUST MULTIPLY OUT I(X ??I); ITS COEF?CIENTS ARE THEN APPROXIMATIONS TO RATIONAL INTEGERS ) BUT THEN AGAIN ?NDING THE GALOIS CONJUGATES MAY NOT BE THAT SIMPLE IN ACTUAL PRACTICE HERE ARE SOME MORE EXAMPLES ANALOGOUS TO THAT OF ABEL FOR NEGATIVE DISCRIMINANTS D ?1 MOD 8 WE DE?NE UD := ?(Z0/2) ?(Z0) , Z0 := Xˆ2 - X Xˆ3 - X Xˆ3 - Xˆ2 Xˆ4 - 3*Xˆ3 - 4*Xˆ2 - 2*X Xˆ5 - Xˆ3 - 2*Xˆ2 - 2*X BERNOULLI POLYNOMIALS Xˆ4 - 2*Xˆ3 + X Xˆ4 - 8*Xˆ3 + X + Xˆ7 - 2*Xˆ6 - Xˆ5 + Xˆ4 + Xˆ3 + Xˆ2 - X Xˆ5 - 3*Xˆ4 + 2*Xˆ3 - Xˆ2 + X Xˆ6 - 13*Xˆ5 - 11*Xˆ4 + 4*Xˆ3 - 4*Xˆ2 - X Xˆ8 - 2*Xˆ7 - 2*Xˆ6 + Xˆ5 + 2*Xˆ4 - Xˆ3 + X ? = BN(X)TN N!, BN = BN(0) (1 18) HERE IS A LIST OF THE ?RST FEW B0(X) = B2(X) = X2 ?X + 2X2 + (?1)K+1 K N + (?1)J BERNOULLI(N,X)= { LOCAL(H,S,C); H=0;S=0;C=-1; FOR(K=1,N+1, C*=1-(N+2)/K; S+=XˆN; X++; H+=C*S/K); H } LET US ANALYZE THIS FUNCTION THE ?RST THING TO NOTICE IS THAT THERE IS ONLY ONE FOR LOOP WHILE THERE ARE TWO SUMMATION SIGNS IN THE FORMULA (1 23) THE POINT IS THAT THE SUMMATION OVER J IN THE FORMULA IS PERFORMED IN THE PROGRAM ONE STEP AT A TIME AS K INCREASES KEEPING THE RESULT IN THE VARIABLE S SIMILARLY, THE BINOMIAL COEF?CIENT N + (X + J)H, H = 0, 1, , N (1 24) (IT IS IN FACT IN THIS FORM, WITH F (X) = XH, THAT J BERNOULLI ENCOUNTERED HIS POLYNOMIALS IN 1713, SEE (1 19)) HERE IS HOW WE COULD DO THIS IN GP BY MODIFYING THE ROUTINES ABOVE POLSUM(F,A,B)= { LOCAL(H,S,C,N); H=0;S=0;C=-1;B++; N=POLDEGREE(F); F=INTFORMAL(F); FOR(K=1,N+1, C*=1-(N+2)/K; S+=SUBST(F,X,B)-SUBST(F,X,A); A++;B++; H+=C*S/K); H } NATURALLY, FOR B ?A OF SIZE COMPARABLE TO THE DEGREE OF F WE DO NOT NEED THIS FUNCTION AND CAN SIMPLY DO THE SUM DIRECTLY WE SHOULD POINT OUT THAT THE LIMITS A,B DO NOT HAVE TO BE CONSTANTS; FOR EXAMPLE, ? F=POLSUM(Xˆ3+X-1,0,X) 1/4*Xˆ4 + 1/2*Xˆ3 + 3/4*Xˆ2 - 1/2*X ? SUM(N=0,100,Nˆ3+N-1)-SUBST(F,X,100) PROOFS THERE ARE MANY WAYS TO PRESENT THE THEORY OF BERNOULLI POLYNOMIALS WE GIVE HERE A BRIEF SKETCH FOLLOWING THE APPROACH IN [59] GIVEN M ?N WE CONSIDER THE FOLLOWING Q-LINEAR OPERATOR ACTING ON THE SPACE OF POLYNOMIALS Q[X] TMF (X) :=