{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Geneva " 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 } {PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Geneva" 1 10 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 2 6 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 53 "A Second Look at Galois G roups: Probabalistic Methods" }}{PARA 19 "" 0 "" {TEXT -1 54 "\251Mike May, S.J., maymk@slu.edu, Saint Louis University" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 499 "In \"Abstract Algebra\" by Dummit and Foote), it is mentioned tha t \"if one could compute forever one could at least be sure of the pre cise distribution of cycle types among the elements of the Galois grou p.\" The idea is that the cycle types we get by factoring the polyno mial mod various primes shows up with a proportion that, in the limit, matches the proportion of the cycle type in the Galois group. We can 't compute forever, but we can use Maple to check lots of primes and r eport the results." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 129 "As part of the set-up we want to use the Galois command. This loads a number of other commands in that we will be interested in." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 29 "with(group):\ngalois(x^2+x+1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 183 "For a given polynomial there is some pre liminary information to gather. The information includes the degree o f the polynomial and the possible partitions associated with that degr ee." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 198 "f := x^7 + 3*x + 3; \ndeg := degree(f,x);\nd:=discrim(f,x);\nifactor(d);\nNumParts := `gal ois/encode`(`galois/initpart`(deg), deg)+1;\nfor i from 1 to NumParts \+ do\nprint(i,combinat[decodepart](deg,i));\nod;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "Recall that if a prime p divides the discriminant, \+ then our polynomial has repeated roots over the field " }{XPPEDIT 18 0 "Z[p]" "6#&%\"ZG6#%\"pG" }{TEXT -1 125 ". Thus we want the discrimi nant in factored form. The variable top tells us the number of cycle \+ types for the given degree." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Wh en the degree is less than or equal to 9, we can get a list of the tra nsitive subgroups of " }{XPPEDIT 18 0 "S[n]" "6#&%\"SG6#%\"nG" }{TEXT -1 120 " along with the cycle types involved in those groups by pullin g information from the groups table of the galois command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 502 "Possible := \{\}:\ngrps:=`galois/g roups`:\np0 := nops(grps[deg,0]):\nfor i from 1 to p0 do\n tempname \+ := `galois/groups`[deg,0][i][1];\n Possible := Possible union \{[tem pname,\n group[transgroup](tempname, names) ,grps[deg,0][i][4]]\} :\n od:\np1 := nops(grps[deg,1]):\nfor i from 1 to p1 do\n tempname := `galois/groups`[deg,1][i][1];\n Possible := Possible union \{[te mpname,\n group[transgroup](tempname, names) ,grps[deg,1][i][4]] \}:\n od:\nfor i from 1 to nops(Possible) do\nprint(Possible[i]);\nod ;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 363 "We are now ready to look at the cycle types for a given polynomial factored over lots of primes. \+ The loop in the code below is set up to print out the cases when the \+ prime divide the discriminant or when our polynomial factors to produc e a cylye type we have not seen with a smaller prime. A summary of th e distribution of cycle types is given every 100 primes." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 719 "f := x^7 + 3*x + 3;\ndeg := degree (f,x);\nd:=discrim(f,x);\nifactor(d);\ntop := `galois/encode`(`galois/ initpart`(deg), deg)+1;\ni:='i':\ndist :=linalg[vector](top,0):\nfor j from 0 to 9 do\nfor i from 1 to 100 do\n p := ithprime(i+100*j): \n if modp(d,p) = 0 then\n print(p, ` divides the discrinin ant `, d);\n else\n shape := `galois/cyclepattern`(f, x, p) :\n e := `galois/encode`(`galois/initpart`(deg), shape)+1:\n \+ dist[e] := dist[e] + 1:\n if dist[e] = 1 then\n \+ print(p,[shape], Factor(f) mod p);\n fi:\n fi:\nod:\npr int(`The distribution of cycletypes at n = `,100*(j+1),` is `, dist); \nod:\nfor i from 1 to top do\nprint(i, dist[i],combinat[decodepart](d eg,i));\nod;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 283 "Notice that the \+ distribution at 500 primes follows very closely with the distribution \+ at 1000 primes. It is pretty clear from this distribution that the gr oup is S(7). (Recall that the information in the group table does not include the trivial partition that is first on our list." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "1) List the partitions of 7 and the information on cycle structure on the transitive subgroups of " }{XPPEDIT 18 0 "S[7]" "6#& %\"SG6#\"\"(" }{TEXT -1 1 "." }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "2) Use the techniques of this worksheet to identify the Galoi s groups of three irreducible polynomials of degree 7." }}}{EXCHG }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 302 "There are a number of drawbacks t o this technique. The first obvious drawback is that it gives a defin itive answer only when the group is a symmetric group. A second probl em is the number of primes we need to test to get all the cycle types. If we have a 9th degree polynomial whose Galois group is " } {XPPEDIT 18 0 "S[9]" "6#&%\"SG6#\"\"*" }{TEXT -1 684 ", we expect to f ind a prime over which it factors into linear factors once every 9! (a bout 360,000) primes. We expect to get a transposition every 10,000 p rimes. To get an answer in a more reasonable amount of time we notice that the existence of a group element of a given cycle type implies t he existence of elements of the cycle types corresponding to powers of the element. Thus we always have a group element corresponding to th e trivial cycle type, and we get a transposition whenever we have an e lement of cycle type (7,2) or (3,3,2,1) or any other cycle type contai ning only odd numbers except for a single 2. This technique then is u seful to verify that a polynomial has " }{XPPEDIT 18 0 "S[n]" "6#&%\"S G6#%\"nG" }{TEXT -1 94 " as its Galois group. It should be noted that we expect most irreducible polynomials to have " }{XPPEDIT 18 0 "S[n] " "6#&%\"SG6#%\"nG" }{TEXT -1 54 " as their Galois group since that is the generic case." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "A second case when the technique is useful is when we ar e trying to verify that the Galois group is a known group of small siz e. (For example, if we suspect that it is cyclic or dyhedral, testing 1000 primes gives very strong confirmation.)" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 10 "Exercises:" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "3) Find an irreducible polynomial of degree 9 with Galois group " }{XPPEDIT 18 0 "S[9]" "6#&%\"SG6#\"\" *" }{TEXT -1 152 ". Justify your answer. How many primes did you hav e to consider before you became confident that you were confident that you had all the cycle types?)" }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 224 "4) Let f(x) be the 11th cyclotomic polynomial. We that the corresponding Galois group is cyclic of order 10. Find the distr ibution of cycle types produced by the first 1000 primes and compare t o the expected distribution." }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 273 "5) We also know the Galois group of polynomials of the form x ^p - q for primes p and q. (The Galois group has order p*(p-1)/2 = p \+ choose 2.) \003Compare the expected and acual distribution of cycle t ypes for the first 1000 primes for an 11th degree polynomial of this f orm." }}}{EXCHG }{EXCHG }}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }