{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "In the previous worksheet we looked at a prime number p, and then defined the p-adic integers a s follows:" }}{PARA 0 "" 0 "" {TEXT -1 19 "A = (A_1, A_2, ...)" }} {PARA 0 "" 0 "" {TEXT -1 41 "where each A_i is in the range 0..p^i -1, " }}{PARA 0 "" 0 "" {TEXT -1 38 "and where (if j>i) A_i is A_j mod p^i ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 204 "We \+ can write A_j = sum a.i * p^i where the sum is taken for i from 0 to j -1 and where a.i are in the range 0..p-1. Then we can think of the p-a dic integer A as an infinite sum: A = sum a.i p^i, i=0,1,2..." }} {PARA 0 "" 0 "" {TEXT -1 58 "because this infinite sum converges in th e p-adic numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 137 "So in this construction \+ we started with the ring of integers Z, and then we considered Z modul o p^1, then modulo p^2, then p^3, etcetera." }}{PARA 0 "" 0 "" {TEXT -1 272 "Lets do the same construction for the ring Q[x] of polynomials in x with rational numbers as coefficients. Instead of a prime number p we will now take an irreducible polynomial p, in fact, we will just take p=x (it would also work with other irreducible polynomials p). " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "So c onsider Q[x]. Elements modulo x^n can be represented as sum a.i x^i wh ere i=0..n-1. If we now do the same construction as we did for the p-a dic numbers, then we will obtain a set that we will denote by Q[[x]]. " }}{PARA 0 "" 0 "" {TEXT -1 99 "An element A of Q[[x]] can be represe nted by an infinite power series A = sum a.i x^i, i=0,1,2,...." }} {PARA 0 "" 0 "" {TEXT -1 255 "Of course, like with p-adic numbers, in \+ practise we can only compute with approximations of elements of Q[[x]] . An approximation with accuracy n of the element A will simply be: A \+ modulo x^n, which can be represented by the polynomial sum a.i x, i=0. .n-1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 297 "We call the elements of Q[[x]] formal power series with rational coef ficients. The word \"formal\" refers to the fact that there are no con ditions on convergence (so formal power series are in a way easier tha n convergent power series). For example, the formal power series: sum i!*x^i, i=0,1,2,..." }}{PARA 0 "" 0 "" {TEXT -1 118 "does not converg e but it is still an element of Q[[x]]. Convergent power series are of course also elements of Q[[x]]." }}{PARA 0 "" 0 "" {TEXT -1 151 "Note that if we had taken another p, say p=x-15, then we would have obtain ed the ring Q[[x-15]], the ring of all formal power series at the poin t x=15." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 177 "Q[[x]] is a much larger ring than Q[x], for example sin(x) can be viewed as an element of Q[[x]]. We can compute approximations of sin( x) of accuracy n by the following command:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 6 "n:=15;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "taylor(sin(x),x=0,n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 271 "Now co nsider again the ring Z. In the previous worksheet we took a monic pol ynomial f in Z[x] and factored it (up to some accuracy) in the ring Z_ p[x]. When the accuracy of these monic factors is high enough, then we could use them to find all monic factors of f in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 212 "Now we will do the \+ same, but instead of Z we take Q[x]. So we take polynomials that have \+ their coefficients in Q[x]. Lets use the variable y for these polynomi als. So then we will look at polynomials f in Q[x,y]." }}{PARA 0 "" 0 "" {TEXT -1 72 "We will assume that f is monic as a polynomial in y, i .e. lcoeff(f,y)=1." }}{PARA 0 "" 0 "" {TEXT -1 427 "Then we can comput e all monic factors of f in Q[[x]][y], so we compute all monic irredu cible polynomials in y with coefficients in Q[[x]] that are factors of f. If we compute them sufficiently accurate (it is easy to see that i f the accuracy n is larger than degree(f,x) then the accuracy is suffi cient) then we can use them to reconstruct the monic (in y) factors of f in Q[x,y], in the same way as in the previous worksheet." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "f := y^4-4*x*y^3-5*y^2+6*x^2 *y^2+2*x*y^2+10*x*y-4*x^3*y-4*x^2*y+4+x^4+2*x^3-4*x^2-5*x;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "f modulo x^1 is the same as rem(f,x,x), w hich is the same as subs(x=0,f)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "subs(x=0,f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L:=factors(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "L:= [seq(i[1],i=L[2])];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1006 "Li ft_L:=proc(f,L,x,y,n)\n # Inpute f in Q[x,y] monic in y.\n # L a l ist of factors of f mod x^1\n # (so the elements in L have accuracy \+ 1).\n # The elements in L must have gcd 1.\n #\n # Note: this pr ocedure will only work if all\n # factors have degree 1.\n # n a p ositive integer.\n\n local i,j,c,Li;\n Li:=L;\n for i from 1 to \+ n-1 do\n # we add an unknown constant c[j] times\n # x^i to \+ the elements of Li, then we find\n # equations for the c[j], solv e them, and\n # substitute the result in Li, thereby\n # inc reasing the accuracy of the factors in\n # Li by 1.\n Li:=[s eq(Li[j]+c[j]*x^i,j=1..nops(Li))];\n j:=normal((convert(Li,`*`)-f )/x^i);\n # Now j should be 0 modulo x, so this:\n j:=expand (subs(x=0,j));\n # this j should be the zero polynomial,\n # which means that the following coeffs\n # should be zero:\n \+ j:=\{coeffs(j,y)\};\n # Solve j and increase the accuracy of Li \+ to i+1:\n Li:=subs(solve(j),Li)\n od;\n Li\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "n:=degree(f,x)+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "L:=Lift_L(f,L,x,y,n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Lets check if we did the Hensel lifting correctly :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "expand( f - convert(L, `*`));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 182 "Hmm, that doesn't look like 0. Of course we can't expect 0 because we computed L only up to \+ accuracy n. So we can only expect this f minus product(factors) to be 0 up to accuracy n:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rem (%, x^n, x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 220 "Now we have dete rmined all 4 monic irreducible factors of f in Q[[x]][y]. Lets now det ermine all the possible products of these factors, so that we get all \+ (not just the irreducible ones) monic factors of f in Q[[x]][y]." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 214 "subsets:=proc(L)\n # Input : list or set.\n # Output: list of all subsets.\n local e,R,i;\n if nops(L)=0 then\n [ \{\} ]\n else\n e:=L[1]:\n R:=procnam e(L[2..-1]);\n [op(R), seq(i union \{e\},i=R)]\n fi\nend;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(L);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "map(convert,%,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "map(expand,%);" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 17 "map(rem,%,x^n,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "map(gcd,%,f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "\{ op(%) \} minus \{1,f\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(%,`*`);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Now we have factored f in Q[x,y] into irreducible factors, usin g:" }}{PARA 0 "" 0 "" {TEXT -1 42 "1) Maple's factorization for the ri ng Q[y]" }}{PARA 0 "" 0 "" {TEXT -1 18 "2) Hensel lifting." }}{PARA 0 "" 0 "" {TEXT -1 44 "3) Constructing all combinations of factors." }} {PARA 0 "" 0 "" {TEXT -1 51 "4) reducing the factors modulo p^n (p=x, n was 5)." }}{PARA 0 "" 0 "" {TEXT -1 54 "5) Taking gcd's to find out which factors are correct." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Let's verify the correctness of our computation :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "28" 0 }{VIEWOPTS 1 1 0 1 1 1803 }