Transcription
Computing with MagmaDavid A. CravenJune 9, 2008
Contents1 The First Steps11.1Arithmetic and Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2Sets, Subsets, and Belonging. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.3Other Types of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.4Boolean Values and Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Iteration and Function Building182.1Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2Procedures Versus Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3Writing Functions and Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4Saving and Loading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5Outputting to Screens and Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Combinatorics and Graph Theory343.1General Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2Partition Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.4Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Number Theory and Linear Algebra514.1Real and Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.4Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.5Mappings and Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.6Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.7Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 Group Theory745.1Producing Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.2Producing Particular Subgroups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77i
5.3Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.4The Datatypes of Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.5Power-Conjugate and Polycyclic Presentations5.6More Hard-Coded Groups and Commands . . . . . . . . . . . . . . . . . . . . . . . . 915.7Extensions and Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946 Representation Theory. . . . . . . . . . . . . . . . . . . . . 88986.1Character Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986.2Constructing and Working with Modules . . . . . . . . . . . . . . . . . . . . . . . . . 1006.3Submodules and Quotient Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106A Managing Errors110A.1 Throwing an Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110A.2 Catching an Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111B More on Functions113B.1 Variadic Functions and Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113B.2 Intrinsics and Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114ii
Chapter 1The First StepsTo start Magma, type magma into a terminal window. After doing this, one of two things willhappen: either the screen will display something likeMagma V2.13-15Wed Jan2 2008 20:09:11 on crazylegs-craneType ? for help.Type Ctrl -D to quit.[Seed 255043391] and you may begin, or you will see something likeMagma is not authorised for use on this machine.This host has the following MAC address(es):00:1d:60:9a:7f:ddPlease contact Magma at magma@maths.usyd.edu.au on the Internet.and you need to log in to a different computer. [This is due to the licensing restrictions imposedon Magma by its creators.]The Magma on-line help can be found gma.htm.1.1Arithmetic and Data TypesNow we are all at the same place, let us try a few commands. We begin with simple arithmetic: 2 4;6 3*7;21 5/7;5/71
3 2;9 31 mod 5;1[Note that each individual command is ended with a semicolon; this is essential for Magma tounderstand where the command ends, as Magma does not assume that a pressed ‘Enter’ keysignifies the end of a command.]Magma believes that values like 2, 4, 0, and so on, are integers, and will treat them as such,until you give it a command that makes it treat them as something else, like 5/7, which makesMagma turn them into another thing, rationals. Suppose that you actually want to know thedecimal expansion of 5/7: then you need to turn it into a real number, which requires a decimalsomewhere, such as 5/7.0;0.714285714285714285714285714285We can assign numbers to letters, and do arithmetic with the letters like we did with thenumbers. x: 2; x 2;4 x: x 1; x;3 x : 1; x;4 3*x;12(Note here that to return 3x, you must input 3*x.) The last but one command is a (slightly)quicker way of altering a variable already in memory. There are similar commands for the otherarithmetic operations. x: 10; x-: 2; x;8 x/: 4; x;2 y: 7;2
x*: y; x;14[Here more than one command has been entered on one line, to save space: this is perfectlyacceptable.]Now we come to our first function, the Type function. This tells you what type of object youhave. Earlier, we said that Magma stored 4 as an integer, 5/7 as a rational, and 5.0 as a realnumber. We can test this claim using the Type function. x: 4; Type(x);RngIntElt x: 5/7; Type(x);FldRatElt x: 5.0; Type(x);FldReEltThis can cause problems, as the next example shows. x: 10/3; y: 3/2; x*y;5 5 mod 4;1 x*y mod 4; x*y mod 4;Runtime error in ’mod’: Bad argument typesArgument types given: FldRatElt, FldRatEltWhat went wrong? The answer is that mod can only work with integers, but Magma thinksthat since x and y are rationals—objects with type FldRatElt—the product x*y is also a rational,even though it is displayed as an integer. This is why it’s important to understand what the typesof objects are. Getting around this problem of Magma storing integers as rationals will be tackledin the next section.This can also occur for simple integer division. x: 4; y: 2; Type(x/y);FldRatEltSuppose that we know that y divides x; in this case, we can do integer division using the commanddiv.3
4 div 2;2 5 div 2;2This finishes off the obvious arithmetic operations that are used. Later on, we will look atprimes, factorizations, and rings that are not Z, but for now this will do. Ending this section, weought to learn how to end Magma; this can be done with either quit; or exit;.1.2Sets, Subsets, and BelongingIn the previous section, we learnt about data types.We saw three data types: RngIntElt;FldRatElt; and FldReElt. There is one more type of number conspicuously absent from thatlist. Sqrt(-1);1.00000000000000000000000000000* .1 Type(Sqrt(-1));FldComEltThus we now have four types of objects. There are many more types of objects, and we willencounter some of them during the course. Types have another name in Magma, that of categories.It is the type of data types, so to speak. Type(RngIntElt);CatSo the type of types is Cat.We have constructed all types of numbers that we care about, so now let’s construct the rings ofnumbers to which they belong. The integers are constructed using the command IntegerRing()or Integers(), the rationals by RationalField() or Rationals(), the reals by RealField(), andthe complexes by ComplexField(). Z: IntegerRing(); Q: Rationals(); R: RealField(); C: ComplexField(); Z;Integer Ring Type(Z);RngInt Type(Q), Type(R), Type(C);FldRat FldRe FldCom[Here we see that if one separates commands with commas, the outputs are displayed on the sameline.]4
There should be a way of testing whether an object is an element of a set, and this can beaccomplished with the command in. The command A in B tests whether A is an element of B, andreturns a Boolean value—true or false—depending on the outcome. 1 in Z;true (10/3 * 3/2) in Q;true (10/3 * 3/2) in Z;true 10/3 in Z;falseThe values true and false can be used in programs as conditions, i.e., if hconditioni thenhcommandi. We will encounter commands like if and for later, but for now we will concentrateon sets.We return to the problem encountered in the previous section. Above we are confidently assuredthat 10/3 * 3/2 is an element of Z, which represents the integers. However, we still cannot usemod on it, and we have to tell Magma to cast this rational number as an integer. Casting is onlyallowed when the object would actually make sense as an element of the set into which you aretrying to cast it. Z: Integers(); Q: Rationals(); x: 10/3; y: 3/2; z: x*y;We can now cast z as an integer, an element of Z, and take it modulo 4. z in Z;true Z!z mod 4;1 Z!x mod 4; Z!x mod 4; Runtime error in ’!’: Rational argument is not a whole integerLHS: RngIntRHS: FldRatElt5
The last example was given to show what happens when you try to perform an incorrect casting.This can be checked by performing the command IsCoercible, and we will see it in action now. IsCoercible(Integers(),4/2);true 2 IsCoercible(Integers(),4/3);falseSomething interesting happened when we successfully coerced 4/2 into an integer: the commandreturned two values. To set a variable to be the output of a function, we have seen that one usesthe : assignment operator. For example, bool: IsCoercible(Integers(),4/3); bool;falseNotice that if the : operator is used, then no output is produced on the screen. To assign twovalues, like those that were produced by IsCoercible when it can coerce the element into the set,we use the following syntax. bool,val: IsCoercible(Integers(),4/2); val;2If Magma gets nothing back from this command for val, then it doesn’t give an error, butdeletes val. val: 2; bool,val: IsCoercible(Integers(),4/3); val; val; User error: Identifier ’val’ has not been declared or assignedWe end this piece on assignment by noting what happens if you try to assign more variablesthan there should be: a,b,c: IsCoercible(Integers(),4/2); a,b,c: IsCoercible(Integers(),4/2); Runtime error in : : Expected to assign 3 value(s) but only computed 2 value(s)6
Now we will move on to sets. A set is constructed in Magma exactly as it is written in mathematics, using braces. X: {1,2,3}; X;{ 1, 2, 3 }Sets in Magma perform exactly as they do in mathematics, as in the set {1, 2, 3} is the same as theset {1, 2, 3, 3}. The command eq tests whether two objects are equal. X: {1,2,3}; Y: {1,2,3,3}; Z: {2,3,4}; X eq Y;true X eq Z;false X join Z;{ 1, 2, 3, 4 } X meet Z;{ 2, 3 } X diff Z;{ 1 } X sdiff Z;{ 1, 4 } 1 in X;trueNotice that, in Magma, if the sets contain integers, then Magma naturally orders them with theusual ordering.To find out how many elements a set contains, one uses the # symbol. Finally, there is ashorthand for producing the set of numbers in an arithmetic progression. A: {1.10}; #A;10 6 in A;true A;{ 1 . 10 } B: {1,2,3,4,5,6,7,8,9,10}; A eq B;true7
C: {1.9 by 2}; 3 in C;true 4 in C;falseAn extremely useful method of generating sets of numbers is exhibited in the following example. XX: {x 2: x in {1.10}}; XX;{ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }The syntax is clear, and this can be used to create a variety of useful sets.We end this section with a few other commands that are useful when dealing with sets ofnumbers. A: {4,2,16,-3,0}; Maximum(A);16 Minimum(A);-3 Random(A);0These three commands (also Min and Max can be used instead of Minimum and Maximum) are concerned with selecting elements of a set. We can also include and throw out elements of a set. set: {1,4,6,10,-3}; Include(set,17);{ -3, 1, 4, 6, 10, 17 } Exclude(set,10);{ -3, 1, 4, 6 } set2: Exclude(set,10); set2;{ -3, 1, 4, 6 }We now end with a few exercises to attempt before moving on to the next section. At the endof the chapter, we will have a list of more involved exercises to test the skills.Exercise 1.1 Calculate the first fifty powers of 2.Exercise 1.2 Using Magma, calculate how many numbers of the form x2 3x 1 with x between0 and 1000 are also multiples of 5.8
Exercise 1.3 What is the maximal element of the image of the function f (x) 25x x2 x3 2x4defined over Z?1.3Other Types of SetsSets such as {1,2,3} can be thought of as unordered lists not allowing repetitions. There are threeobvious ways to generalize this: to ordered lists; to unordered lists allowing repetitions; and toordered lists allowing repetitions. All of these possibilities are implemented in Magma.We will begin with unordered lists allowing repetitions, or multisets. These can be defined byusing {* *} instead of { }. X: {* 1,1,2,3 *}; X;{* 1 2, 2, 3 *}These are different objects to normal sets, as can be seen from their types. A: {1,2,3}; B: {* 4,5,6 *}; Type(A), Type(B);SetEnum SetMulti A join B; A join B; Runtime error in ’join’: Bad argument typesArgument types given: SetEnum[RngIntElt], SetMulti[RngIntElt]Multisets can be manipulated in the same way as normal sets, except that one can no longeruse the notation {* 1.4 *}, and differences can no longer be taken. A: {*1,2,3*}; B: {* 4,5,6 *}; A join B;{* 1, 2, 3, 4, 5, 6 *} A join A;{* 1 2, 2 2, 3 2 *} C: {*1,2,4,5*}; A meet C;{* 1, 2 *} B diff C;9
B diff C; Runtime error in ’diff’: Bad argument typesArgument types given: SetMulti[RngIntElt], SetMulti[RngIntElt] D: {*1.4*}; D: {*1.4*}; User error: bad syntax D: {* x 2: x in {-2.2} *}; D;{* 0, 1 2, 4 2 *} Maximum(D);4 Multiplicity(D,4);2Here we introduced the comman
Magma V2.13-15 Wed Jan 2 2008 20:09:11 on crazylegs-crane [Seed 255043391] Type ? for help. Type Ctrl -D to quit. and you may begin, or you will see something like Magma is not authorised for use on this machine. This host has the following MAC address(es): 00:1d:60:9a:7f:dd Please contact Magma at magma@maths.usyd.edu.au on the Internet.File Size: 310KBPage Count: 119
