{VERSION 3 0 "IBM INTEL LINUX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 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 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "FINITE FIELDS AND DESIGN THEORY WITH MAPLE, Math 149 B, \+ UC Davis. Prof. J. A. De Loera " }}{PARA 0 "" 0 "" {TEXT -1 84 "___ ______________________________________________________________________ ___________" }}{PARA 0 "" 0 "" {TEXT -1 92 "We show how MAPLE can be used to construct fields and handle polynomial computations." }} {PARA 0 "" 0 "" {TEXT -1 93 "REMEMBER: You can always get detailed \+ information about a certain command by typing" }}{PARA 0 "" 0 " " {TEXT -1 19 "help(command_name);" }}{PARA 0 "" 0 "" {TEXT -1 52 "A \+ window will the pop out with the information." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "EXAMPLE 1: Suppose you \+ wish to construct a field with 9 elements." }}{PARA 0 "" 0 "" {TEXT -1 87 "What are the ingredients? Since 9=3^2 we need a n irreducible polynomial of" }}{PARA 0 "" 0 "" {TEXT -1 22 "degree \+ 2 in Z_3[x]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "f:= x-> x^2+x+2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fGR6#%\"xG6\"6$%)operatorG%&arrowGF(,(*$ )9$\"\"#\"\"\"\"\"\"F/F2F0F2F(F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 " Is this polynomial irreducible?" }{XPPEDIT 18 0 "" "6#%#%?G " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Irreduc(f(x)) mod 3;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "How to construct the elements of Z_3[x]/? Remember that they are essentially " }}{PARA 0 "" 0 "" {TEXT -1 68 "the same \+ as the set of polynomials of degree LESS than degree(f)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 77 "But we wish to \+ have a way to decide questions such as (x+3)*(2x+1)=???" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "Powmod((x+3)*(2*x+1),1, f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"#F%\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "THEOREM: The multiplicative group U(F_q) of a finite fie ld F_q is a cyclic group." }}{PARA 0 "" 0 "" {TEXT -1 20 "with \+ q-1 elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "Suppose we wish to find a generator of U(F_9), how to do that?" }}{PARA 0 "" 0 "" {TEXT -1 31 "Using the a bove command :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod( (x+3),2,f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"# \"\"\"F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),3, f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"#F%\"\"\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),4,f(x),x) \+ mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),5,f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$%\"xG\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),6,f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"\"\"#F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),7,f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Powmod((x+3),8,f(x),x) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "We conc lude that (x+3) is a generator for the group U(F_9). Generato rs receive the" }}{PARA 0 "" 0 "" {TEXT -1 38 "name PRIMITIVE ELEMENTS of the field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 "Let's try again: Is x a primitive element of F_9? Here is a short cut for what we" }}{PARA 0 "" 0 "" {TEXT -1 10 "did above:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 1 to 8 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " temp:=Powmod(x,i,f(x ),x) mod 3;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 " print(x^i,` Corres ponds to field element`, temp);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "o d:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%\"xG%>~Corresponds~to~field~ele mentGF#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\"#\"\"\"%>~Corre sponds~to~field~elementG,&F%F&\"\"\"F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\"$\"\"\"%>~Corresponds~to~field~elementG,&F%\"\"#F*\" \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\"%\"\"\"%>~Correspo nds~to~field~elementG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG \"\"&\"\"\"%>~Corresponds~to~field~elementG,$F%\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\"'\"\"\"%>~Corresponds~to~field~elementG, &F%\"\"\"\"\"#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\"(\"\" \"%>~Corresponds~to~field~elementG,&F%\"\"\"F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%*$)%\"xG\"\")\"\"\"%>~Corresponds~to~field~elementG\"\" \"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "YES! x is indeed a pr imitive element. This is a very special situation and does no t" }}{PARA 0 "" 0 "" {TEXT -1 107 "always happen!! WHEN it hap pens we say that f(x), the polynomial used for building F_9, \+ is" }}{PARA 0 "" 0 "" {TEXT -1 38 "a PRIMITIVE IRREDUCIBLE polynomi al." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 103 "L uckily, MAPLE offers a command that decides for you whether y our irreducible polynomial is " }}{PARA 0 "" 0 "" {TEXT -1 23 "primi tive irreducible:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Primi tive(f(x)) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Irreduc(x^5+2*x+1) mod 3;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Primitive(x^5+2*x+1) mod 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 119 "We have learned so far lots of b eautiful algebraic concepts (Fields, irreducible polynomials, etc). We wish" }}{PARA 0 "" 0 "" {TEXT -1 100 "to go back to the origina l combinatorial motivation we had: LATIN SQUARES and t-DESIG NS:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 98 "Re call that we were interested on constructing pairs of orthogon al n-by-n Latin squares?" }}{PARA 0 "" 0 "" {TEXT -1 122 "We can \+ generalize the theorem that we saw in class for Z_p, p \+ prime to an arbitrary finite field" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 123 "THEOREM: Whenever q is a prime power it is possible \+ to construct q-1 mutually orthogonal latin squares" }}{PARA 0 "" 0 "" {TEXT -1 13 "of order q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 122 "Here is the way to do it: F or each t in U(F_q) (t is non-zero) construct the q-by-q array of " }}{PARA 0 "" 0 "" {TEXT -1 130 "numbers. Its entries \+ are labeled by pairs of elements in F_q. For the i,j e ntry is given by the formula:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 " L_t (i , j)= t* i+j " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "GOAL: To build the seven 9-by-9 mutually orthogonal latin squa res using MAPLE. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "FIRST STEP: Build and store the eleme nts of Z_3[x]/ where f is an irreducible polynomial" }}{PARA 0 "" 0 "" {TEXT -1 59 "We do this using the above exa mple f(x)=x^2+x+2 ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 119 "Now we store the elements of the field in \+ an array, the entries are labeled by the power of x" }} {PARA 0 "" 0 "" {TEXT -1 28 "that gives that element." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for i from 1 to 8 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 " fieldEIGHT[i]:=Powmod(x,i,f(x),x) mod 3:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "fieldEIGHT[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"#\"\"\"F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "fieldEIGHT[3];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"#F%\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 " Now we wish to display at least a couple of thos e tables! L_a=L_(x+1) and L_(2x) " }}}}{MARK "27 0 0" 105 } {VIEWOPTS 1 1 0 3 2 1804 }