Generating and checking Automorphisms over Finite Fields\251Mike May, S.J., maymk@slu.edu, Saint Louis University restart:This worksheet uses Maple to test examine automorphisms for finite extensions of the rationals. You should probably have worked through the worksheet on Factoring Examples and the pair of worksheets on Automorphisms before attempting this worksheet. The pair of worksheets on automorphisms (DefiningAutomorphisms.mws and AutomorphismGroups.mws) looked at automorphisms of finite extensions of the rationals. For the material on Galois Theory, that is the primary example. For simply studying automorphisms however, finite fields have several attractive features. We know from class that a finite field is generated by a single element and its Galois group is a cyclic group generated by the Frobenius automorphism. Furthermore, since finite fields are finite sets, potential automorphisms can be tested by brute force. For a finite field an automorphism is defined by the image of a generating element and extended by linearity. This worksheet is set up to allow you to define a potential automorphism, then compute all the images and see if the map is an automorphism.

BE SURE TO START THIS WORKSHEET BY EVALUATING THE FIRST THREE INPUT BLOCKS. THEY DEFINE THE FIELD AND TOOLS THAT WE NEED FOR OUR CALCULATIONS We need to start by reading in the library that does finite fields and setting up some tools that we will use.readlib(GF): `?`:= zeta: Gextension := proc() Gfunct[ConvertOut](Gfunct[extension]) end: Gorder := proc(a) Gfunct[ConvertOut] (Gfunct[order](Gfunct[ConvertIn](a))) end: F := x -> subs(zeta = x, Gextension()): Greduce := x -> sort(simplify(x) mod character, alpha, tdeg): Gredpoly := proc(poly, var) sort(collect(simplify(poly) mod character, var, Greduce), var); end: Gquo := proc(bigpoly, divpoly, var, grem) if nargs = 3 then Quo(bigpoly, divpoly, var) mod character; else Quo(bigpoly, divpoly, var, grem) mod character; fi end:The second step is to specify the finite field. We are interested in using the field NiMvJiUjR0ZHNiMpJSJwRyUiZEcqKCYlIlpHNiNGKCIiIjcjJSJ4R0YuNyMtJSJmRzYjRjAhIiI= where f(x) is a polynomial of degree d that is irreducible over NiMmJSJaRzYjJSJwRw==. We will refer to the current finite field as GF. To follow conventions from class, we want to think of elements of the field as polynomials in NiMlJmFscGhhRw== over NiMmJSJaRzYjJSJwRw== of degree less than d, where NiMlJmFscGhhRw== is a root of f(x). [A note for those interested in technical detail that can be skipped by others - We want to use the polynomial f(x) in several different ways and that gives potential for colliding names on Maple. To eliminate problems, we will set things up so that when a field is created, it is created in terms of NiMlJXpldGFH. This leaves NiMlJmFscGhhRw== to be used for the format we are interested in.] To set up our field we need two lines of code.character := 2; fzeta := zeta^3 + zeta + 1; deg := degree(fzeta, zeta); Gfunct:=GF(character,deg, fzeta):The first line of code gives the characteristic of the prime field, an irreducible polynomial over Z[p], and the degree of the polynomial. The second line functions for Gf(NiMpJSJwRyUiZEc=), the finite field of NiMpJSJwRyUiZEc= elements, by using the polynomial f(NiMlJXpldGFH) which is irreducible of degree d over NiMmJSJaRzYjJSJwRw==. As a default, we start with a field of 8 elements where the polynomial used for the extension field is NiMvLSUiZkc2IyUlemV0YUcsKCokRiciIiQiIiJGJ0YrRitGKw==. Maple will produce the irreducible polynomial if needed, so the f(NiMlJXpldGFH) is optional.TO CHANGE FIELDS, YOU NEED TO REEVALUATE BOTH OF THE LINES ABOVE AS WELL AS THE INPUT SECTIONS BELOW THAT DEFINES TOOLS. For example, if you want to change to the field of 64 = 2^6 elements, replace the two lines above with: character := 2; deg := 6 Gfunct:=GF(character, deg): IF YOU ARE GOING TO CHANGE FIELDS, YOU NEED TO REEVALUATE THE INPUT SECTION BELOW AFTER YOU CHANGE THE FIELD.Finally we need to define some functions that need to be evaluated after the field is defined. alias(alpha = RootOf(Gextension())): f := F(x); deg := degree(f, x): Int2alpha:= a -> simplify(subs(zeta = alpha, Gfunct[ConvertOut](Gfunct[input](a)))) mod character:The polynomial f(x) given above is the irreducible polynomial used in the construction of the field. Let's check that a raised to the degree of the extension reduces properly.alpha^deg; simplify(alpha^deg) mod character; print('F'(alpha) = F(alpha) ,'F'(alpha) = simplify(F(alpha)));

(Not really Brute Force) Recall that an automorphism of GF must respect both addition and multiplication. Since all the elements of GF are polynomials in a, it is clear that to specify an automorphism of GF, it suffices to specify the image of NiMlJmFscGhhRw==. We want to test which field elements could be images of NiMlJmFscGhhRw==. The first test of possible images of NiMlJmFscGhhRw== is to evaluate f(b) for all nonzero NiMlJWJldGFH in GF. Thus NiMlJWJldGFH can only be the image of a under an automorphism phi if f(b) = 0. The following loop evaluates f(b) for the nonzero b in GF. For the field elements b with f(b ) = 0, the loop prints b, f(b), and f(b) in normal form. (To print these values for all b in GF, switch the # sign from the second last line to the one above it.)for i from 0 to Gfunct[size] -1 do a := Int2alpha(i): b := F(a): c := simplify(b) mod character: if c = 0 then print(`If a = `,a,` then F(a) = `, b,` = `, c); fi; # c = 0 then print(`If a = `,a,` then F(a) = `, b,` = `, c); od: To check our work, we factor the polynomial f(x).Factor(f, alpha) mod character; As expected, b is a root of f(x) if and only if (x - b) is a factor. The roots of f(x) form a pattern that is not immediately visible, but is easy to explain. Recall that the only automorphisms of a finite field are powers of the Frobenius automorphism which raises NiMlJmFscGhhRw== to the "character" power. Compare the roots above with the values a^(character^i) computed below.for i from 1 to deg do print(`If `,'i' = i,` then `, 'character'^i = character^i, ` and `, alpha^(character^i) = simplify(alpha^(character^i)) mod character); od;Thus NiMpJSZhbHBoYUclImlH is a root of f(x) if and only if i is a power of the characteristic.

1) Change fields to the field of 125 elements using the irreducible polynomial x^3 + x + 1. Verify that the only possible automorphisms are the powers of the Frobenius map.2) Change fields to a field of 128 elements. Verify that the only possible automorphisms are the powers of the Frobenius map.

Remember to change back to your original field of 8 elements.

It is time now to try showing that the substitutions identified above are automorphisms and that any other substitution is not an automorphism. The procedure we are using, substituting a value b for a, clearly produces a group homomorphism for addition. (It is defined on linear combinations so that it respects addition.) Thus we need to focus our attention on respecting multiplication. If we name the substitution map phi, we need to show that NiMvLSUkcGhpRzYjKSUmYWxwaGFHJSJpRyktRiU2I0YoRik= with i ranging from 1 to the order of a. We now set up this method to examine potential automorphisms and refine it several times.

Specify b, the image of a, and compute f(a^i) and f(a)^i for all i. Print (i, NiQtJSRwaGlHNiMpJSZhbHBoYUclImlHKS1GJDYjRidGKA==) and visually check. (We start with beta = a + 1 as a default.)beta := alpha + 1; for i from 1 to Gfunct[size] -1 do a := simplify(alpha^i) mod character: b := simplify(subs(alpha = beta, a)) mod character: c := simplify(beta^i) mod character: print(`If `,'i' = i,` then `, alpha^i = a,` so`, phi(alpha^i) = b, ` and `, phi(alpha)^i = c); od:

3) Is the map NiMlJHBoaUc= sending NiMlJmFscGhhRw== to NiMsJiUmYWxwaGFHIiIiRiVGJQ== an automorphism? Justify your answer from the output produced above.

Specify NiMlJWJldGFH, the image of NiMlJmFscGhhRw==, and compute NiMtJSRwaGlHNiMpJSZhbHBoYUclImlH and NiMpLSUkcGhpRzYjJSZhbHBoYUclImlH with i starting at 1. Print (i, NiMtJSRwaGlHNiMpJSZhbHBoYUclImlH, NiMpLSUkcGhpRzYjJSZhbHBoYUclImlH) until either NiMtJSRwaGlHNiMpJSZhbHBoYUclImlH is not equal to NiMpLSUkcGhpRzYjJSZhbHBoYUclImlH, or until all values of i have been tested. (Once again, we start with NiMvJSViZXRhRywmJSZhbHBoYUciIiJGJ0Yn as a default.)beta := alpha + 1; for i from 1 to Gfunct[size] -1 do a := simplify(alpha^i) mod character: b := simplify(subs(alpha = beta, a)) mod character: c := simplify(beta^i) mod character: if c <> b then print(`the map `, phi, ` taking `,alpha,` to `,beta, ` is not a homomorphism since if `, 'i' = i); print( phi(alpha^i) = b,` while `, phi(alpha)^i = c); print; break; else print(i, a, b, c); fi: od:

4) Pick a different value for NiMlJWJldGFH, and either show that the map is an automorphism, or that it not an automorphism. Justify your answer.

To automate the procedure set up in the previous case we can set up a double loop to check all possible values of b. For each value of b, we compare NiMtJSRwaGlHNiMpJSZhbHBoYUclImlH and NiMpLSUkcGhpRzYjJSZhbHBoYUclImlH with i starting at 1 until either all values of i have been tested or NiMtJSRwaGlHNiMpJSZhbHBoYUclImlH is not equal to NiMpLSUkcGhpRzYjJSZhbHBoYUclImlH.for j from 1 to Gfunct[size] -1 do beta := Int2alpha(j): tst := 1: for i from 1 to Gfunct[size] -1 do a := simplify(alpha^i) mod character: b := simplify(subs(alpha = beta, a)) mod character: c := simplify(beta^i) mod character: if c <> b then print(`the map `, phi,` taking `,alpha,` to `,beta, ` is not a homomorphism since if i =`||i); print( alpha^i = a,` and `, phi(a) = b); print(`while `, phi(alpha)^i = beta^i , `and `, beta^i = c); print(` `); tst := 0; break; fi: od: if tst = 1 then print(`the map taking `,alpha,` to `, beta,` is a homomorphism`); print(` `); fi: od:Notice that in all cases where the map is not an automorphism, the problem shows up when i is the degree of the polynomial f(x) used to generate the field. This lets us simplify the procedure by eliminating one of the loops.i := deg: for j from 1 to Gfunct[size] -1 do beta := Int2alpha(j): a := simplify(alpha^i) mod character: b := simplify(subs(alpha = beta, a)) mod character: c := simplify(beta^i) mod character: if c <> b then print(`the map `, phi,` taking `,alpha,` to `,beta, ` is not a homomorphism since if i =`||i); print( alpha^i = a,` and `, phi(a) = b); print(`while `, phi(alpha)^i = beta^i , `and `, beta^i = c); else print(`the map taking `,alpha,` to `,beta,` is a homomorphism`); fi: print(` `); od:This lets us shorten the printing to only show the maps that are homomorphisms.i := deg: for j from 1 to Gfunct[size] -1 do beta := Int2alpha(j): a := simplify(alpha^i) mod character: b := simplify(subs(alpha = beta, a)) mod character: c := simplify(beta^i) mod character: if c = b then print(`the map taking `,alpha,` to `,beta,` is a homomorphism`); print(` `); end if: end do:

5) Show that the reduction above is valid. That is show that if we define a map NiMlJHBoaUc= by defining NiMtJSRwaGlHNiMlJmFscGhhRw== and extending by linearity, then we have an automorphism whenever NiMvLSUkcGhpRzYjKSUmYWxwaGFHJSJpRyktRiU2I0YoRik= when i is the degree of the polynomial used to define the field. (This is not a Maple question, but a question that lets you use Maple more efficiently.)6) Using one of the loops above find the automorphisms of the field of 125 elements.