1

HANDBOOK OF MAGMA FUNCTIONS

2

M A G M A

C O M P U T E R • A L G E B R A

HANDBOOK OF MAGMA FUNCTIONS volume A

Wieb Bosma John Cannon

4

CONTENTS

I MAGMA . . . . . . . . . . . . . . . . . . . . 19

1 MAGMA LANGUAGE . . . . . . . . . . . . . . . . . . . . . 20

1.1  Introduction  22
1.2  Interaction with the Environment  22
1.2.1  Starting and Terminating  22
1.2.2  Interruption  23
1.2.3  Input and Output  23
1.2.4  Forcing errors  26
1.2.5  Timing and Alarm  27
1.2.6  Environment Variables  27
1.3  Assignment  28
1.3.1  Identifiers  28
1.3.2  Assignment and Deletion  29
1.4  Automatic Printing  32
1.4.1  Semantics  32
1.4.2  The Previous Value Buffer  34
1.5  The where … is construction  34
1.6  Conditional Statements and Expressions  36
1.7  Iterative Statements  39
1.8  Functions and Procedures  42
1.8.1  The forward Declaration  45
1.9  Packages  47
1.9.1  Introduction  47
1.9.2  Intrinsics  48
1.9.3  Attaching/Detaching package files  50
1.9.4  Related files  50
1.9.5  Importing constants  50
1.9.6  Argument checking  51
1.9.7  Spec files  52
1.9.8  User startup spec file list  53
1.10  Comments and Continuation  54
1.11  Logical values  54
1.11.1  Creation of Booleans  55
1.11.2  Boolean Operators  55
1.11.3  Functions on Booleans  55
1.11.4  Iteration  56
1.12  Equality testing  56
1.13  Strings  57
1.13.1  Creation of Strings  58
1.13.2  Integer-Valued Functions  59
1.13.3  Conversion Functions  59
1.13.4  Boolean Functions  60

CONTENTS 6

2 MAGMA SEMANTICS . . . . . . . . . . . . . . . . . . . . . 63

2.1  Introduction  64
2.2  Terminology  64
2.3  Assignment  65
2.4  Uninitialized Identifiers  65
2.5  Evaluation in Magma  66
2.5.1  Call by Value Evaluation  66
2.5.2  Magma’s Evaluation Process  67
2.5.3  Function Expressions  68
2.5.4  Function Values Assigned to Identifiers  69
2.5.5  Recursion and Mutual Recursion  69
2.5.6  Function Application  70
2.5.7  The Initial Context  71
2.6  Scope  71
2.6.1  Local Declarations  71
2.6.2  The ‘first use’ Rule  72
2.6.3  Identifier Classes  73
2.6.4  The Evaluation Process Revisited  73
2.6.5  The ‘single use’ Rule  74
2.7  Procedure Expressions  74
2.8  Reference Arguments  76
2.9  Dynamic Typing  76
2.10  Traps for Young Players  77
2.10.1  Trap 1  78
2.10.2  Trap 2  78

II SETS, SEQUENCES, AND MAPPINGS . . . . . . 80

3 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . 81

3.1  Restrictions on Sets and Sequences  82
3.1.1  Universe of a Set or Sequence  82
3.1.2  Modifying the Universe of a Set or Sequence  84
3.1.3  Parents of Sets and Sequences  85
3.2  Nested Aggregates  87
3.2.1  Multi-indexing  87

4 SETS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.1  Introduction  91
4.1.1  Enumerated Sets  91
4.1.2  Formal Sets  91
4.1.3  Indexed Sets  91
4.1.4  Multisets  91
4.1.5  Compatibility  92
4.1.6  Notation  92
4.2  Creating Sets  92
4.2.1  The Formal Set Constructor  92
4.2.2  The Enumerated Set Constructor  93
4.2.3  The Indexed Set Constructor  95
4.2.4  The Multiset Constructor  96
4.2.5  The Arithmetic Progression Constructors  98
4.3  Power Sets  99
4.3.1  The Cartesian Product Constructors  100
4.4  Sets from Structures  100
4.5  Accessing and Modifying Sets  100

7 CONTENTS

4.5.1  Accessing Sets and their Associated Structures  100
4.5.2  Selecting Elements of Sets  102
4.5.3  Modifying Sets  104
4.6  Operations on Sets  106
4.6.1  Boolean Functions and Operators  107
4.6.2  Binary Set Operators  108
4.7  Quantifiers  109
4.8  Reduction and Iteration over Sets  111

5 SEQUENCES . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.1  Introduction  116
5.1.1  Enumerated Sequences  116
5.1.2  Formal Sequences  116
5.1.3  Compatibility  116
5.2  Creating Sequences  117
5.2.1  The Formal Sequence Constructor  117
5.2.2  The Enumerated Sequence Constructor  117
5.2.3  The Arithmetic Progression Constructors  118
5.2.4  Literal Sequences  119
5.3  Power Sequences  119
5.4  Operators on Sequences  120
5.4.1  Access Functions  121
5.4.2  Selection Operators on Enumerated Sequences  121
5.4.3  Modifying Enumerated Sequences  122
5.4.4  Creating New Enumerated Sequences from Old Ones  127
5.5  Predicates on Sequences  128
5.5.1  Membership Testing  129
5.5.2  Testing Order Relations  130
5.6  Recursion, Reduction, and Iteration  130
5.6.1  Recursion  131
5.6.2  Reduction  131
5.7  Iteration  132

6 TUPLES AND CARTESIAN PRODUCTS . . . . . . . . . . . . 134

6.1  Introduction  135
6.2  The Cartesian Product Constructor  135
6.3  Creating a Tuple  135
6.4  Access Functions  136
6.5  Equality  137

7 LISTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

7.1  Introduction  139
7.2  Construction of Lists  139
7.3  Creation of New Lists  139
7.4  Access Functions  140
7.5  Assignment Operator  140

8 COPRODUCTS . . . . . . . . . . . . . . . . . . . . . . . . 141

8.1  Introduction  142
8.2  Creation Functions  142
8.2.1  Creation of Coproducts  142
8.2.2  Creation of Coproduct Elements  142
8.3  Accessing functions  142
8.4  Retrieve  143
8.5  Flattening  143
8.6  Universal Map  144

CONTENTS 8

9 RECORDS . . . . . . . . . . . . . . . . . . . . . . . . . . 145

9.1  Introduction  146
9.2  The Record Format Constructor  146
9.3  Creating a Record  147
9.4  Access and Modification Functions  147

10 MAPPINGS . . . . . . . . . . . . . . . . . . . . . . . . . 150

10.1  Introduction  151
10.1.1  The Map Constructors  151
10.1.2  The Graph of a Map  152
10.1.3  Rules for Maps  152
10.1.4  Homomorphisms  152
10.1.5  Checking of Maps  152
10.2  Creation Functions  153
10.2.1  Creation of Maps  153
10.2.2  Creation of Partial Maps  153
10.2.3  Creation of Homomorphisms  154
10.2.4  Coercion Maps  154
10.3  Operations on Mappings  154
10.3.1  Composition  155
10.3.2  (Co)Domain and (Co)Kernel  155
10.3.3  Function  155
10.4  Images and Preimages  155

III SEMIGROUPS AND GROUPS . . . . . . . . . . 157

11 FINITELY PRESENTED SEMIGROUPS . . . . . . . . . . . . 158

11.1  Introduction  159
11.2  The Construction of Free Semigroups and their Elements  159
11.2.1  Structure Constructors  159
11.2.2  Element Constructors  160
11.3  Elementary Operators for Words  160
11.3.1  Multiplication and Exponentiation  160
11.3.2  The Length of a Word  160
11.3.3  Equality and Comparison  161
11.4  Specification of a Presentation  161
11.4.1  Relations  162
11.4.2  Presentations  162
11.4.3  Accessing the Defining Generators and Relations  163
11.5  Subsemigroups, Ideals and Quotients  163
11.5.1  Subsemigroups and Ideals  164
11.5.2  Quotients  164
11.6  Extensions  165
11.7  Elementary Tietze Transformations  165
11.8  String Operations on Words  166

9 CONTENTS 12 GROUPS . . . . . . . . . . . . . . . . . . . . . . . . . . 168

12.1  Introduction  171
12.1.1  The Categories of Finite Groups  171
12.2  Construction of Elements  171
12.2.1  Construction of an Element  172
12.2.2  Coercion  172
12.2.3  Homomorphisms  172
12.2.4  Arithmetic with Elements  173
12.3  Construction of a General Group  175
12.3.1  The General Group Constructors  175
12.3.2  Construction of Subgroups  178
12.3.3  Construction of Quotient Groups  179
12.4  Standard Groups and Extensions  180
12.4.1  Construction of a Standard Group  181
12.4.2  Construction of Extensions  183
12.5  Transfer Functions Between Group Categories  184
12.6  Basic Operations  187
12.6.1  Accessing Group Information  188
12.7  Operations on the Set of Elements  189
12.7.1  Order and Index Functions  189
12.7.2  Membership and Equality  190
12.7.3  Set Operations  191
12.7.4  Action on a Coset Space  193
12.8  Standard Subgroup Constructions  194
12.8.1  Abstract Group Predicates  196
12.9  Characteristic Subgroups and Normal Structure  197
12.9.1  Characteristic Subgroups and Subgroup Series  197
12.9.2  The Abstract Structure of a Group  199
12.10  Conjugacy Classes of Elements  200
12.11  Conjugacy Classes of Subgroups  205
12.11.1  Conjugacy Classes of Subgroups  205
12.11.2  The Poset of Subgroup Classes  208
12.11.3  Creating the Poset of Subgroup Classes  209
12.11.4  Operations on Subgroup Class Posets  210
12.11.5  Operations on Poset Elements  212
12.11.6  Class Information from a Conjugacy Class Poset  213
12.12  Cohomology  213
12.13  Representation Theory  214
12.13.1  Character Theory  215
12.13.2  Modular Representations  215

CONTENTS 10

13 ABELIAN GROUPS . . . . . . . . . . . . . . . . . . . . . 218

13.1  Introduction  220
13.2  Construction of Free Abelian Group and its Elements  220
13.2.1  Structure Constructors  220
13.2.2  Construction of an Element  220
13.2.3  Deconstruction of an Element  221
13.3  Arithmetic with Elements  221
13.3.1  Addition and Subtraction  221
13.3.2  Relations  222
13.4  Construction of Subgroups and Quotient Groups  222
13.4.1  Construction of Subgroups  223
13.4.2  Construction of Quotient Groups  223
13.5  Specification of a Presentation  223
13.5.1  Accessing the Defining Generators and Relations  225
13.6  Standard Constructions  225
13.7  Operations on Elements  225
13.7.1  Order of an Element  226
13.7.2  Equality and Comparison  226
13.8  Invariants of an Abelian Group  226
13.9  Canonical Decomposition  226
13.10  Set-Theoretic Operations  227
13.10.1  Functions Relating to Group Order  227
13.10.2  Membership and Equality  227
13.10.3  Set Operations  228
13.11  Coset Spaces  229
13.12  The Subgroup Structure  229
13.13  General Group Properties  230
13.13.1  General Properties of Subgroups  231
13.13.2  Coercions Between Groups and Subgroups  232
13.14  Normal Structure and Characteristic Subgroups  232
13.14.1  Characteristic Subgroups and Subgroup Series  232
13.14.2  Subgroup Structure  233
13.15  Conjugacy  233
13.16  Representation Theory  235

14 FINITELY PRESENTED GROUPS . . . . . . . . . . . . . . . 236

14.1  Introduction  239
14.1.1  Overview of Facilities  239
14.1.2  The Construction of Finitely Presented Groups  239
14.2  The Construction of Finitely Presented Groups  240
14.2.1  Construction of a Free Group  240
14.2.2  Elementary Operators for Words  241
14.2.3  Creation and Manipulation of Relations  242
14.2.4  Construction of a Quotient: Specification of a Presentation  243
14.2.5  Modification of a Presentation  246
14.3  Standard Groups and Extensions  249
14.3.1  Construction of a Standard Group  249
14.3.2  Construction of Extensions  250
14.4  Basic Operations  251
14.4.1  Accessing the Defining Generators and Relations  251
14.5  Specialised Operations on Words  251
14.5.1  Comparison of Words  252
14.5.2  Elementary Functions for Words  252
14.6  Subgroups  255
14.6.1  Specification of a Subgroup  255
14.6.2  Index of a Subgroup: The Todd-Coxeter Algorithm  257
14.7  Subgroup Constructions  261

14.7.1  Properties of Subgroups  264
14.8  Coset Spaces and Tables  266
14.8.1  Coset Tables  267
14.8.2  Coset Spaces: Construction  269
14.8.3  Accessing Information  272
14.8.4  Coset Spaces: Elementary Operations  274
14.8.5  Coset Spaces: Selection of Cosets  275
14.8.6  Coset Spaces: Induced Homomorphism  276
14.9  Computing Quotients of Finitely Presented Groups  278
14.9.1  Abelian Quotients  279
14.9.2  p-Quotients  280
14.9.3  The Construction of p-Quotients  280
14.9.4  The p-Quotient Process  283
14.9.5  Using p-Quotient Interactively  283
14.10  Constructing a Presentation for a Subgroup  291
14.10.1  Introduction  291
14.10.2  Rewriting  292
14.11  Simplification  293
14.12  Low Index Subgroups  299

15 SOLUBLE GROUPS . . . . . . . . . . . . . . . . . . . . . 306

15.1  Power-conjugate Presentations  309
15.1.1  Introduction  309
15.1.2  Power-conjugate Presentations  309
15.2  Definition of Soluble Groups using Power-conjugate Presentations  310
15.2.1  Specification of Elements  310
15.2.2  Arithmetic Operations on Elements  311
15.2.3  Operators for Elements  312
15.2.4  Comparison Operators for Elements  312
15.2.5  Specification of a Power-conjugate Presentation  312
15.3  Subgroups, Quotient Groups and Extensions  314
15.3.1  Construction of Subgroups  314
15.3.2  Construction of Quotient Groups  314
15.3.3  Construction of Extensions  315
15.3.4  Construction of Standard Groups  317
15.4  Conversion between Categories  317
15.5  Access Functions for PC-Groups  317
15.6  Set-Theoretic Operations in a Group  318
15.6.1  Functions Relating to Group Order  318
15.6.2  Membership and Equality  319
15.6.3  Set Operations  319
15.7  Coset Spaces  320
15.8  The Subgroup Structure  320
15.8.1  General Subgroup Constructions  321
15.9  General Group Properties  321
15.9.1  General Properties of Subgroups  322
15.9.2  Coercions Between Groups and Subgroups  323
15.10  Hall π-Subgroups and Sylow Systems  323
15.11  Normal Structure and Characteristic Subgroups  324
15.11.1  Characteristic Subgroups and Subgroup Series  325
15.11.2  Subgroup Structure  327
15.12  Conjugacy  327
15.13  Automorphisms and Isomorphisms  328
15.13.1  Standard Presentation Algorithm  329
15.13.2  Automorphism Group Algorithm  335
15.14  Representation Theory  336
15.15  Conditioned Presentations  336

15.15.1  Structure Operations  337
15.15.2  Element Operations  337
15.16  Power Groups  338
15.17  Generating p-groups  338
15.18  Optimizing Magma Code  346
15.18.1  PowerGroup  347
15.18.2  CompactPresentation  347

HANDBOOK OF MAGMA FUNCTIONS volume B

Wieb Bosma John Cannon

CONTENTS 350

CONTENTS

III SEMIGROUPS AND GROUPS . . . . . . . . . . 365

16 PERMUTATION GROUPS . . . . . . . . . . . . . . . . . . 365

16.1  Introduction  370
16.1.1  Terminology  370
16.1.2  The Category of Permutation Groups  370
16.1.3  The Construction of a Permutation Group  370
16.2  Creation of the Symmetric Group and Arithmetic with Permutations  370
16.2.1  Construction of the Symmetric Group  371
16.2.2  Construction of a Permutation  372
16.2.3  Coercion  373
16.2.4  Arithmetic with Permutations  373
16.3  Construction of a General Permutation Group  375
16.3.1  The General Permutation Group Constructor  376
16.3.2  Construction of Subgroups  377
16.3.3  Construction of Quotient Groups  379
16.4  Standard Groups and Extensions  379
16.4.1  Construction of a Standard Permutation Group  380
16.4.2  Construction of Extensions  381
16.5  Basic Operations  383
16.5.1  Accessing Group Information  383
16.6  Operations on the Set of Elements  384
16.6.1  Order and Index Functions  385
16.6.2  Membership and Equality  386
16.6.3  Set Operations  386
16.7  The Finitely Presented Group Associated with a Permutation Group  389
16.8  G-Sets  389
16.8.1  The Concept of a G-Set  389
16.8.2  Creating a G-Set  390
16.8.3  Images, Orbits and Stabilizers  391
16.8.4  The Homomorphism Induced by a G-Set Action  396
16.8.5  Action on Orbits  397
16.8.6  Action on a G-invariant Partition  398
16.8.7  Natural Actions for Primitive Groups  404
16.8.8  Action on a Coset Space  405
16.9  Standard Subgroup Constructions  406
16.10  Properties of a Permutation Group  409
16.10.1  Permutation Group Predicates  409
16.10.2  Abstract Group Predicates  410
16.11  Characteristic Subgroups and Normal Structure  411
16.11.1  Characteristic Subgroups and Subgroup Series  412
16.11.2  The Normal Structure of a Primitive Group  416
16.11.3  The Abstract Structure of a Group  418
16.12  Conjugacy  420
16.13  Cohomology  424
16.14  Representation Theory  425
16.15  Permutation Representations of Linear Groups  426
16.16  Base and Strong Generator Functions  432
16.16.1  Introduction  432
16.16.2  Construction of a Base and Strong Generating Set  432
16.16.3  Defining Values for Attributes  435

16.16.4  Modifying a Base and Strong Generating Set  436
16.16.5  Accessing the Base and Strong Generating Set  436
16.16.6  Functions for Working with a Base and Strong Generating Set  438

17 MATRIX GROUPS . . . . . . . . . . . . . . . . . . . . . . 440

17.1  Introduction  444
17.1.1  Introduction to Matrix Groups  444
17.1.2  The Support  444
17.1.3  The Category of Matrix Groups  444
17.1.4  The Construction of a Matrix Group  444
17.2  Creation of the General Linear Group and its Elements  444
17.2.1  Construction of the General Linear Group  445
17.2.2  Construction of a Matrix  445
17.2.3  Deconstruction of a Matrix  446
17.3  Matrix Operations  446
17.3.1  Arithmetic with Matrices  447
17.3.2  Predicates for Matrices  448
17.3.3  Matrix Invariants  449
17.3.4  Coercion between Matrix Structures  452
17.4  General Constructions  452
17.4.1  The General Matrix Group Constructor  452
17.4.2  Construction of Subgroups  453
17.4.3  Construction of Quotient Groups  454
17.5  Standard Groups and Extensions  455
17.5.1  Construction of a Classical Matrix Group  456
17.5.2  Construction of Extensions  458
17.6  Changing Rings  460
17.7  Basic Operations  460
17.7.1  Accessing Group Information  461
17.8  Operations on the Set of Elements  461
17.8.1  Order and Index Functions  462
17.8.2  Membership and Equality  463
17.8.3  Set Operations  464
17.9  The Finitely Presented Group Associated with a Matrix Group  466
17.10  Images, Orbits and Stabilizers  466
17.10.1  The Homomorphism Induced by G-action on Orbits  469
17.10.2  Action on a Coset Space  471
17.11  Standard Subgroup Constructions  472
17.12  Properties of a Matrix Group  473
17.12.1  Matrix Group Predicates  474
17.12.2  Abstract Group Predicates  474
17.13  Characteristic Subgroups and Normal Structure  475
17.13.1  Characteristic Subgroups and Subgroup Series  475
17.13.2  The Abstract Structure of a Group  477
17.14  Conjugacy  477
17.15  Soluble Matrix Groups  479
17.15.1  Conversion to a PC-Group  480
17.15.2  Soluble Group Functions  480
17.15.3  p-group Functions  480
17.16  Representation Theory  480
17.17  Base and Strong Generator Functions  482
17.17.1  Introduction  482
17.17.2  Construction of a Base and Strong Generating Set  482
17.17.3  Defining Values for Attributes  483
17.17.4  Accessing the Base and Strong Generating Set  484
17.17.5  Decomposition of Matrix Groups of Large Degree  484
17.17.6  Introduction  484

17.17.7  Matrix Group Tuples  486
17.17.8  Accessing the data items in a MatGpTup  486
17.17.9  Decompositions with Respect to a Normal Subgroup  489
17.17.10  Testing for Semilinearity and Imprimitivity  494

18 CHARACTERS OF FINITE GROUPS . . . . . . . . . . . . . 497

18.1  Creation Functions  498
18.1.1  Structure Creation  498
18.1.2  Element Creation  498
18.1.3  The Table of Irreducible Characters  499
18.2  Structure Operations  500
18.2.1  Related Structures  500
18.2.2  Numerical Invariants  500
18.2.3  Ring Predicates and Booleans  501
18.3  Element Operations  501
18.3.1  Arithmetic  501
18.4  Predicates and Booleans  501
18.4.1  Accessing Class Functions  502
18.4.2  Conjugation of Class Functions  503
18.4.3  Functions Returning a Scalar  503
18.4.4  Attribute  504
18.4.5  Induction, Restriction, Extension  504
18.4.6  Symmetrization  504
18.4.7  Permutation Character  505
18.4.8  Composition and Decomposition  505

IV RINGS AND FIELDS . . . . . . . . . . . . . . 508

19 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . 509

19.1  Overview  511
19.2  The World of Rings  512
19.2.1  New Rings from Old Ones  512
19.2.2  Attributes  513
19.3  Coercion  513
19.3.1  Automatic Coercion  514
19.3.2  Forced Coercion  516
19.4  Generic Ring Functions  517
19.4.1  Related Structures  518
19.4.2  Numerical Invariants  518
19.4.3  Predicates and Boolean Operations  519
19.5  Generic Element Functions  520
19.5.1  Parent and Category  520
19.5.2  Creation of Elements  520
19.5.3  Arithmetic Operations  521
19.5.4  Equality and Membership  522
19.5.5  Predicates on Ring Elements  522
19.5.6  Comparison of Ring Elements  523
19.6  Ideals and Quotient Rings  524
19.6.1  Defining Ideals and Quotient Rings  524
19.6.2  Arithmetic Operations on Ideals  524
19.6.3  Boolean Operators on Ideals  525
19.7  Other Ring Constructions  525
19.7.1  Residue Fields  525
19.7.2  Localization  525
19.7.3  Completion  526
19.7.4  Transcendental Extension  526

CONTENTS 354

20 RATIONAL FIELD . . . . . . . . . . . . . . . . . . . . . . 527

20.1  Introduction  528
20.1.1  Representation  528
20.1.2  Coercion  528
20.1.3  Homomorphisms  529
20.2  Creation Functions  529
20.2.1  Creation of Structures  529
20.2.2  Creation of Elements  530
20.3  Structure Operations  530
20.3.1  Related Structures  531
20.3.2  Numerical Invariants  531
20.3.3  Ring Predicates and Booleans  532
20.4  Element Operations  532
20.4.1  Parent and Category  532
20.4.2  Arithmetic Operators  532
20.4.3  Numerator and Denominator  532
20.4.4  Equality and Membership  533
20.4.5  Predicates on Ring Elements  533
20.4.6  Comparison  533
20.4.7  Conjugates, Norm and Trace  533
20.4.8  Absolute Value and Sign  534
20.4.9  Rounding and Truncating  534
20.4.10  Rational Reconstruction  534

21 RING OF INTEGERS . . . . . . . . . . . . . . . . . . . . . 536

21.1  Introduction  538
21.1.1  Representation  538
21.1.2  Coercion  538
21.1.3  Homomorphisms  538
21.2  Creation Functions  539
21.2.1  Creation of Structures  539
21.2.2  Creation of Elements  539
21.2.3  Element Conversions  540
21.3  Structure Operations  540
21.3.1  Related Structures  541
21.3.2  Numerical Invariants  541
21.3.3  Ring Predicates and Booleans  541
21.4  Element Operations  541
21.4.1  Arithmetic Operations  542
21.4.2  Equality and Membership  542
21.4.3  Parent and Category  542
21.4.4  Predicates on Ring Elements  542
21.4.5  Comparison of Ring Elements  543
21.4.6  Conjugates, Norm and Trace  544
21.4.7  Other Elementary Functions  544
21.5  Common Divisors and Common Multiples  545
21.6  Arithmetic Functions  546
21.7  Combinatorial Functions  548
21.8  Primes and Primality Testing  548
21.8.1  Primes  549
21.8.2  Primality  549
21.8.3  Prime Certificate  551
21.9  Factorization  552
21.10  Factorization Sequences  557
21.10.1  Creation and Conversion  557
21.10.2  Arithmetic  558
21.10.3  Divisors  558

21.10.4  Predicates  558
21.11  Modular Arithmetic  558
21.11.1  The Solution of Modular Equations  559

22 RESIDUE CLASS RINGS . . . . . . . . . . . . . . . . . . . 561

22.1  Introduction  562
22.1.1  Representation  562
22.1.2  Coercion  562
22.1.3  Homomorphisms  563
22.2  Creation Functions  563
22.2.1  Creation of Structures  563
22.2.2  Creation of Elements  563
22.3  Structure Operations  563
22.3.1  Related Structures  564
22.3.2  Numerical Invariants  564
22.3.3  Ring Predicates and Booleans  564
22.4  Elements Operations  565
22.4.1  Arithmetic Operators  565
22.4.2  Equality and Membership  565
22.4.3  Parent and Category  565
22.4.4  Predicates on Ring Elements  565
22.4.5  Other Element Functions  566
22.4.6  Solving Linear Equations in Z/mZ  566
22.5  Ideal Operations  566
22.5.1  Generic Ideal Functions  567
22.5.2  Ideal Arithmetic  567

23 FINITE FIELDS . . . . . . . . . . . . . . . . . . . . . . . 568

23.1  Introduction  570
23.1.1  Representation of Finite Fields  570
23.1.2  Ground Field and Relationships  570
23.1.3  Homomorphisms  571
23.1.4  Special Options  571
23.2  Creation Functions  572
23.2.1  Creation of Structures  572
23.2.2  Creating Relations  575
23.2.3  Creation of Elements  575
23.2.4  Special Elements  576
23.2.5  Sequence Conversions  576
23.3  Structure Operations  577
23.3.1  Related Structures  577
23.3.2  Numerical Invariants  579
23.3.3  Polynomials for Finite Fields  579
23.3.4  Ring Predicates and Booleans  580
23.3.5  Roots  580
23.4  Element Operations  580
23.4.1  Arithmetic Operators  581
23.4.2  Equality and Membership  581
23.4.3  Parent and Category  581
23.4.4  Predicates on Ring Elements  581
23.4.5  Minimal and Characteristic Polynomial  582
23.4.6  Norm and Trace  582
23.4.7  Log, Order and Roots  583

CONTENTS 356

24 UNIVARIATE POLYNOMIAL RINGS . . . . . . . . . . . . . . 584

24.1  Introduction  586
24.1.1  Representation  586
24.1.2  Homomorphisms  586
24.1.3  Print Options  587
24.2  Creation Functions  587
24.2.1  Creation of Structures  587
24.2.2  Creation of Elements  587
24.3  Structure Operations  589
24.3.1  Related Structures  589
24.3.2  Changing Rings  589
24.3.3  Numerical Invariants  590
24.3.4  Ring Predicates and Booleans  590
24.4  Element Operations  590
24.4.1  Parent and Category  591
24.4.2  Arithmetic Operators  591
24.4.3  Equality and Membership  591
24.4.4  Predicates on Ring Elements  591
24.4.5  Coefficients and Terms  592
24.4.6  Degree  592
24.4.7  Roots  593
24.4.8  Derivative, Integral  593
24.4.9  Evaluation, Interpolation  593
24.4.10  Quotient and Remainder  594
24.4.11  Modular Arithmetic  594
24.5  Common Divisors and Common Multiples  594
24.5.1  Common Divisors and Common Multiples  595
24.5.2  Content and Primitive Part  595
24.6  Polynomials over the Integers  595
24.7  Factorization  596
24.7.1  Factorization and Irreducibility  596
24.7.2  Resultant and Discriminant  597
24.7.3  Hensel Lifting  598
24.8  Ideals and Quotient Rings  599
24.8.1  Creation of Ideals and Quotients  599
24.8.2  Ideal Arithmetic  599
24.8.3  Other Functions on Ideals  600
24.8.4  Other Functions on Quotients  600

25 MULTIVARIATE POLYNOMIAL RINGS . . . . . . . . . . . . 601

25.1  Introduction  604
25.1.1  Representation  604
25.1.2  Homomorphisms  604
25.1.3  Print Options  605
25.2  Monomial Orders  605
25.2.1  Lexicographical Order (lex)  606
25.2.2  Graded Lexicographical Order (glex)  606
25.2.3  Graded Reverse Lexicographical Order (grevlex)  607
25.2.4  Elimination (k) Order (elim)  607
25.2.5  Elimination List Order (elim)  607
25.2.6  Inverse Block Order (invblock)  607
25.2.7  Univariate Order (univ)  608
25.2.8  Weight Order (weight)  608
25.3  Creation of Polynomial Rings and Polynomials  608
25.3.1  Creation of Polynomial Rings  608
25.3.2  Creation of Polynomials  610
25.4  Structure Operations  611

25.4.1  Related Structures  611
25.4.2  Numerical Invariants  611
25.4.3  Ring Predicates and Booleans  611
25.5  Element Operations  612
25.5.1  Parent and Category  612
25.5.2  Arithmetic Operators  612
25.5.3  Equality and Membership  612
25.5.4  Predicates on Ring Elements  613
25.5.5  Coefficients, Monomials and Terms  613
25.5.6  Degrees  617
25.5.7  Derivative, Integral  618
25.5.8  Evaluation, Interpolation  618
25.5.9  Quotient and Reductum  619
25.6  Common Divisors  620
25.6.1  Common Divisors and Common Multiples  620
25.6.2  Content and Primitive Part  620
25.7  Polynomials over the Integers  621
25.8  Factorization  621
25.8.1  Factorization and Irreducibility  621
25.9  Resultant and Discriminant  624
25.10  Creation of Ideals and Gröbner Bases  624
25.10.1  Creation of Ideals  625
25.10.2  Ideal Bases  625
25.11  Basic Operations on Ideals  630
25.11.1  Construction of New Ideals  630
25.11.2  Ideal Predicates  631
25.11.3  Operations on Elements of Ideals  634
25.12  Computation of Varieties  634
25.13  Elimination  636
25.13.1  Construction of Elimination Ideals  637
25.13.2  Univariate Elimination Ideal Generators  637
25.13.3  Relation Ideals  640
25.14  Changing Coefficient Ring  641
25.15  Changing Order  641
25.16  Variable Extension of Ideals  642
25.17  Extension and Contraction of Ideals  643
25.18  Radical and Decomposition of Ideals  644
25.19  Dimension, Hilbert Series and Hilbert Polynomial  651
25.20  Syzygy Modules  653
25.21  Quotient Rings  654
25.21.1  Creation of Quotient Rings  655
25.21.2  Operations on Quotient Rings  655
25.21.3  Finite dimensional Quotient Rings  655
25.22  Symmetric Polynomials  656
25.23  Group Actions  657
25.23.1  Permutation Group Actions  657
25.23.2  Matrix Group Actions  657

CONTENTS 358

26 RATIONAL FUNCTION FIELDS . . . . . . . . . . . . . . . . 659

26.1  Introduction  660
26.1.1  Representation  660
26.1.2  Options  660
26.2  Creation Functions  660
26.2.1  Creation of Structures  660
26.2.2  Creation of Elements  661
26.3  Structure Operations  661
26.3.1  Related Structures  661
26.3.2  Invariants  662
26.3.3  Ring Predicates and Booleans  662
26.4  Element Operations  662
26.4.1  Arithmetic  662
26.4.2  Equality and Membership  662
26.4.3  Numerator and Denominator  663
26.4.4  Predicates on Ring Elements  663
26.4.5  Evaluation  663

27 VALUATION RINGS . . . . . . . . . . . . . . . . . . . . . 664

27.1  Introduction  665
27.2  Creation Functions  665
27.2.1  Creation of Structures  665
27.2.2  Creation of Elements  665
27.3  Structure Operations  665
27.3.1  Related Structures  666
27.3.2  Numerical Invariants  666
27.4  Element Operations  666
27.4.1  Arithmetic Operations  666
27.4.2  Equality and Membership  666
27.4.3  Parent and Category  666
27.4.4  Predicates on Ring Elements  667
27.4.5  Other Element Functions  667

28 QUADRATIC FIELDS . . . . . . . . . . . . . . . . . . . . 668

28.1  Introduction  670
28.1.1  Representation  670
28.1.2  Coercion  670
28.1.3  Homomorphisms  671
28.1.4  Special Options  671
28.2  Creation Functions  672
28.2.1  Creation of Structures  672
28.2.2  Creation of Elements  672
28.2.3  Creation of Forms  674
28.3  Structure Operations  674
28.3.1  Related Structures  674
28.3.2  Basis  675
28.3.3  Ideal Class Group  675
28.3.4  Unit Group  675
28.3.5  Numerical Invariants  676
28.3.6  Predicates and Boolean Operators  677
28.4  Element Operations  677
28.4.1  Parent and Category  677
28.4.2  Arithmetic  677
28.4.3  Equality and Membership  677
28.4.4  Predicates on Elements  677
28.4.5  Conjugates, Minimal Polynomial  678

28.4.6  Norm Equations  678
28.4.7  Other Element Functions  679
28.5  Functions on Forms  679
28.5.1  Numerical Invariants  680
28.5.2  Arithmetic  680
28.5.3  Matrix Action on Forms  681

29 CYCLOTOMIC FIELDS . . . . . . . . . . . . . . . . . . . . 683

29.1  Introduction  684
29.2  Creation Functions  684
29.2.1  Creation of Cyclotomic Fields  684
29.2.2  Creation of Elements  684
29.3  Structure Operations  685
29.3.1  Related Structures  686
29.3.2  Invariants  686
29.3.3  Ring Predicates and Booleans  686
29.4  Element Operations  687
29.4.1  Parent and Category  687
29.4.2  Arithmetic  687
29.4.3  Equality and Membership  687
29.4.4  Predicates on Ring Elements  687
29.4.5  Conjugates, Minimal Polynomial  687

30 NUMBER FIELDS AND THEIR ORDERS . . . . . . . . . . . . 690

30.1  Introduction  693
30.1.1  Special Options  693
30.1.2  Homomorphisms  694
30.2  Creation Functions  695
30.2.1  Creation of General Number Fields  695
30.2.2  Creation of Orders in Number Fields  699
30.2.3  Creation of Elements  701
30.2.4  Creation of Ideals in Orders  702
30.3  Structure Operations  703
30.3.1  Category and Parent  703
30.3.2  Related Structures  704
30.3.3  Galois group  704
30.3.4  Subfields  705
30.3.5  Invariants  705
30.3.6  Basis Representation  707
30.3.7  Ring Predicates  709
30.3.8  Ideal Class Groups  710
30.3.9  Unit Groups  712
30.4  Element Operations  714
30.4.1  Parent and Category  714
30.4.2  Arithmetic  714
30.4.3  Equality and Membership  715
30.4.4  Predicates on Elements  715
30.4.5  Finding Special Elements  715
30.4.6  Real and Complex Valued Functions  716
30.4.7  Norm, Trace, and Minimal Polynomial  717
30.4.8  Other Functions  718
30.5  Solving equations  719
30.5.1  Norm Equations  719
30.5.2  Thue Equations  719
30.6  Ideals and Quotients  720
30.6.1  Ideal Arithmetic  720

30.6.2  Two-Element Presentations  720
30.6.3  Invariants  721
30.6.4  Factorization and Primes  721
30.6.5  Basis Representation  722
30.6.6  Predicates on Ideals  722

31 REAL AND COMPLEX FIELDS . . . . . . . . . . . . . . . . 724

31.1  Introduction  726
31.1.1  Fixed Precision Real Numbers  726
31.1.2  Free Real Numbers  727
31.1.3  Coercion  728
31.1.4  Homomorphisms  728
31.1.5  Special Options  729
31.2  Creation Functions  730
31.2.1  Creation of Structures  730
31.2.2  Creation of Elements  731
31.3  Structure Operations  733
31.3.1  Related Structures  733
31.3.2  Numerical Invariants  733
31.3.3  Ring Predicates and Booleans  733
31.3.4  Other Structure Functions  733
31.4  Element Operations  733
31.4.1  Generic Element Functions and Predicates  734
31.4.2  Comparison of and Membership  734
31.4.3  Other Predicates  734
31.4.4  Arithmetic  735
31.4.5  Conversions  735
31.4.6  Rounding  736
31.4.7  Precision  736
31.4.8  Constants  737
31.4.9  Simple Element Functions  737
31.4.10  Roots  738
31.4.11  Continued Fractions  743
31.4.12  Algebraic Dependencies  743
31.5  Transcendental Functions  744
31.5.1  Exponential, Logarithmic and Polylogarithmic Functions  744
31.5.2  Trigonometric Functions  746
31.5.3  Inverse Trigonometric Functions  747
31.5.4  Hyperbolic Functions  749
31.5.5  Inverse Hyperbolic Functions  750
31.5.6  Elliptic and Modular Functions  751
31.5.7  Gamma, Bessel and Associated Functions  752
31.5.8  Other Special Functions  755
31.6  Numerical Functions  756
31.6.1  Summation of Infinite Series  757
31.6.2  Integration  757

361 CONTENTS 32 POWER SERIES AND LAURENT SERIES . . . . . . . . . . . 759

32.1  Introduction  760
32.1.1  Laurent Series and Power Series  760
32.1.2  Precision  761
32.1.3  Free and Fixed Precision  761
32.1.4  Equality  761
32.1.5  Coercion  761
32.1.6  Homomorphisms  761
32.1.7  Special Options  762
32.2  Creation Functions  762
32.2.1  Creation of Structures  762
32.2.2  Changing Default Precision  763
32.2.3  Creation of Elements  763
32.3  Structure Operations  764
32.3.1  Related Structures  764
32.3.2  Invariants  764
32.3.3  Ring Predicates and Booleans  764
32.4  Element Operations  764
32.4.1  Parent and Category  765
32.4.2  Arithmetic Operators  765
32.4.3  Equality and Membership  765
32.4.4  Predicates on Ring Elements  765
32.4.5  Precision  765
32.4.6  Coefficients and Degree  766
32.4.7  Square Root  766
32.4.8  Evaluation and Derivative  766
32.4.9  Composition and Convolution  767
32.4.10  Transcendental Functions  768

33 LOCAL FIELDS . . . . . . . . . . . . . . . . . . . . . . . 769

33.1  Introduction  770
33.2  p-Adics  770
33.2.1  Precision  770
33.2.2  Arbitrary versus fixed precision  771
33.2.3  Equality  771
33.2.4  Coercion  771
33.2.5  Homomorphisms  771
33.3  Creation of Structures  771
33.4  Creation of Elements  773
33.4.1  Generic Element Constructions  773
33.4.2  Element Constructors and Selectors  773
33.4.3  Sequence Conversions  774
33.5  Functions on p-Adic Structures  774
33.6  Operations on p-adic Elements  775
33.6.1  Generic Functions on Elements  775
33.6.2  Generic Predicates  775
33.6.3  Other Functions  775

34 INDEX OF SIGNATURES . . . . . . . . . . . . . . . . . . . 776

HANDBOOK OF MAGMA FUNCTIONS volume C

Wieb Bosma John Cannon

775 CONTENTS

CONTENTS

V MODULES . . . . . . . . . . . . . . . . . . . 796

35 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . 797

35.1  Overview  798
35.2  General Modules  798
35.3  The Presentation of Submodules  799

36 VECTOR SPACES . . . . . . . . . . . . . . . . . . . . . . 800

36.1  Introduction  802
36.1.1  Vector Space Categories  802
36.1.2  The Construction of a Vector Space  802
36.2  Creation of Vector Spaces and Arithmetic with Vectors  802
36.2.1  Construction of a Vector Space  803
36.2.2  Construction of a Vector  804
36.2.3  Deconstruction of a Vector  805
36.2.4  Arithmetic with Vectors  805
36.2.5  Indexing Vectors and Matrices  807
36.3  Subspaces, Quotient Spaces and Homomorphisms  809
36.3.1  Construction of Subspaces  809
36.3.2  Construction of Quotient Vector Spaces  811
36.4  Changing the Coefficient Field  813
36.5  Basic Operations  814
36.5.1  Accessing Vector Space Invariants  814
36.5.2  Membership and Equality  815
36.5.3  Operations on Subspaces  815
36.6  Bases  815
36.7  Operations with Linear Transformations  818
36.8  Row and Column Operations  820
36.9  Solution of a System of Linear Equations  821
36.10  Quadratic Forms and Inner Products  822
36.10.1  Defining a Quadratic Form  822
36.10.2  Properties of the Form  822
36.10.3  Structure of Inner Product Spaces  823

777 CONTENTS 37 GENERAL MODULES . . . . . . . . . . . . . . . . . . . . 824

37.1  Introduction  826
37.1.1  Taxonomy of Modules  826
37.1.2  Presentation of Submodules  826
37.1.3  Module Categories  827
37.1.4  Notations  827
37.2  Definition of a Module  827
37.2.1  Construction of a Free Module  827
37.3  Construction of an R[G]-Module  829
37.4  Accessing Module Information  835
37.5  Standard Constructions  838
37.5.1  Standard Constructions for General Modules  838
37.5.2  Changing the Coefficient Ring  840
37.5.3  Standard Constructions for R[G]-Modules  841
37.6  Elements Construction and Operations  843
37.6.1  Construction of Module Elements  843
37.6.2  Deconstruction Module Elements  844
37.6.3  Operations on Module Elements  844
37.7  Submodules, Quotient Modules and Homomorphisms  847
37.7.1  Construction of Submodules  847
37.7.2  Construction of Quotient Modules  848
37.8  Operations on Submodules  848
37.8.1  Membership and Equality  849
37.8.2  Operations on Submodules  849
37.9  Free Modules  850
37.9.1  Bases for Free Modules  850
37.10  Structure of a Module  851
37.10.1  Splitting a Module  852
37.10.2  Properties of a Module  853
37.10.3  Composition Series  853
37.10.4  Minimal Submodules and Socle Series  855
37.10.5  Complements of Submodules  857
37.11  Homomorphisms of Modules  857
37.12  Submodule Lattices  861
37.12.1  Creating Lattices  861
37.12.2  Operations on Lattices  862
37.12.3  Operations on Lattice Elements  863

38 THE MODULES Hom_{R}(M, N) AND End(M) . . . . . . . . . . . 866

38.1  Introduction  867
38.2  Construction of Hom_{R}(M, N)  867
38.3  Construction of a Matrix  868
38.4  Element Operations  868
38.5  Accessing and Modifying a Matrix  871
38.5.1  Indexing  871
38.5.2  Extracting and Inserting Blocks  872
38.6  Row and Column Operations  873
38.7  Canonical Forms for Elements  874
38.8  Solutions of Systems of Linear Equations  876

VI ALGEBRAS . . . . . . . . . . . . . . . . . . 878

CONTENTS 778

39 MATRIX ALGEBRAS . . . . . . . . . . . . . . . . . . . . . 879

39.1  Introduction  881
39.2  Construction of Matrix Algebras and their Elements  881
39.2.1  Construction of the Complete Matrix Algebra  881
39.2.2  Construction of a Matrix  881
39.2.3  Constructing a General Matrix Algebra  882
39.2.4  The Invariants of a Matrix Algebra  884
39.3  Construction of Subalgebras, Ideals and Quotient Rings  885
39.4  The Construction of Extensions and their Elements  886
39.4.1  The Construction of Direct Sums and Tensor Products  886
39.4.2  Construction of Elements of Direct Sums and Tensor Products  888
39.5  Changing Rings  889
39.6  Elementary Operations on Elements  889
39.6.1  Arithmetic  889
39.6.2  Predicates  890
39.6.3  Comparison  890
39.6.4  Properties of Elements  890
39.7  Determinant, Trace, Transpose and Order  891
39.8  Elements of M_{n} as Homomorphisms  892
39.9  Elementary Operations on Subalgebras and Ideals  892
39.9.1  Bases  892
39.9.2  Intersection of Subalgebras  893
39.9.3  Membership and Equality  893
39.10  Accessing and Modifying a Matrix  894
39.10.1  Indexing  894
39.10.2  Extracting and Inserting Blocks  895
39.10.3  Row and Column Operations  895
39.11  Canonical Forms  896
39.11.1  Canonical Forms for Matrices over Euclidean Domains  896
39.11.2  Canonical Forms for Matrices over a Field  897
39.12  Solutions of Systems of Linear Equations  900

40 FINITELY PRESENTED ALGEBRAS . . . . . . . . . . . . . 902

40.1  Introduction  903
40.2  Construction of a Free Algebra  903
40.2.1  Accessing an Algebra  904
40.3  Specification of a Word  904
40.3.1  Elementary Operators for Elements  904
40.3.2  Boolean Operators for Elements  905
40.3.3  Elementary Functions for Elements  905
40.4  Specification of a Relation  905
40.5  Construction of a Quotient: Specification of a Presentation  906
40.6  Construction of a Subalgebra  906
40.7  Editing Defining Relations  907
40.7.1  Accessing the Defining Generators and Relations  907
40.8  Vector Enumeration  908
40.8.1  Finitely Presented Modules  908
40.8.2  S-algebras  908
40.8.3  Finitely Presented Algebras  909
40.8.4  Vector Enumeration  909
40.8.5  The Isomorphism  910
40.8.6  Sketch of the Algorithm  911
40.8.7  Weights  911
40.9  The Quotient Module Command  911
40.9.1  Structuring Presentations  912
40.9.2  Options and Controls  913
40.9.3  Weights  913

779 CONTENTS

40.9.4  Limits  913
40.9.5  Logging  914
40.9.6  Miscellaneous  916

VII ALGEBRAIC GEOMETRY . . . . . . . . . . . . 919

41 ELLIPTIC CURVES . . . . . . . . . . . . . . . . . . . . . 920

41.1  Introduction  921
41.2  Creation Functions  921
41.2.1  Creation of an Elliptic Curve  921
41.2.2  Creation of Points  922
41.3  Structure Operations  923
41.3.1  Related Structures  923
41.3.2  Change Ground Ring  923
41.3.3  Alternative Models  923
41.3.4  Invariants  924
41.3.5  Special Invariants for Integral Curves  925
41.3.6  Mordell-Weil group  926
41.3.7  Predicates and Boolean Operators  928
41.4  Operations on Points  928
41.4.1  Arithmetic  928
41.4.2  Order  928
41.4.3  Height  929
41.4.4  Access Operations  929
41.4.5  Predicates on Points  929
41.5  Kodaira Symbols  929

VIII FINITE INCIDENCE STRUCTURES . . . . . . . 932

42 GRAPHS . . . . . . . . . . . . . . . . . . . . . . . . . . 933

42.1  Introduction  936
42.2  The Vertex-Set and Edge-Set of a Graph  936
42.2.1  Introduction  936
42.2.2  Creating Edges and Vertices  936
42.2.3  Operations on Edges and Vertices  937
42.3  Construction of Graphs and Digraphs  938
42.3.1  Construction of a General Graph  938
42.3.2  Construction of a General Digraph  940
42.3.3  Construction of a Standard Graph  941
42.3.4  Construction of a Standard Digraph  942
42.4  General Graph Theoretic Constructions  942
42.4.1  Subgraphs, Quotient Graphs, and Supergraphs  942
42.4.2  Constructing Complements, Line Graphs; Contraction, Switching  944
42.5  Unions and Products of Graphs  945
42.5.1  Converting between Graphs and Digraphs  946
42.6  Construction of Graphs from Groups, Codes and Designs  947
42.6.1  Graphs Constructed from Groups  947
42.6.2  Graphs Constructed from Codes and Designs  948
42.7  Elementary Invariants of a Graph  948
42.8  Elementary Graph Predicates  949
42.9  Adjacency, Degree and Distance  950
42.9.1  Adjacency, Degree and Distance Functions for a Graph  951
42.9.2  Adjacency and Degree Functions for a Digraph  952

42.10  Connectedness, Paths and Circuits  954
42.10.1  Connectedness, Paths and Circuits in a Graph  954
42.10.2  Connectedness, Paths and Circuits in a Digraph  956
42.11  Matrices and Vector Spaces Associated with a Graph or Digraph  956
42.12  Spanning Trees of a Graph or Digraph  956
42.13  Independent Sets, Cliques, Colourings  957
42.14  Automorphism Group of a Graph or Digraph  958
42.14.1  The Automorphism Group Function  959
42.14.2  Variants of Automorphism Group  960
42.15  Automorphism Group of a Design or Set System  960
42.16  Action of Automorphisms  963
42.17  Stabilizers of Vertices and Edges  965
42.18  Symmetry and Regularity Properties of Graphs  965

43 INCIDENCE STRUCTURES AND DESIGNS . . . . . . . . . . 968

43.1  Introduction  970
43.2  Construction of Incidence Structures and Designs  971
43.3  The Point-Set and Block-Set of an Incidence Structure  975
43.3.1  Introduction  975
43.3.2  Creating Point-Sets and Block-Sets  975
43.3.3  Creating Points and Blocks  976
43.4  General Design Constructions  977
43.4.1  The Construction of Related Structures  978
43.4.2  The Witt Designs  980
43.4.3  Hadamard Matrices and their 3-Designs  981
43.4.4  Difference Sets and their Development  982
43.5  Elementary Invariants of an Incidence Structure  984
43.6  Elementary Invariants of a Design  985
43.7  Operations on Points and Blocks  986
43.8  Properties of Incidence Structures and Designs  988
43.9  Conversion Functions  990
43.10  Identity and Isomorphism  991
43.11  The Automorphism Group of an Incidence Structure  991
43.11.1  The Automorphism Group Function  991
43.11.2  Action of Automorphisms  991
43.11.3  Stabilizers of Points and Blocks  993
43.11.4  Transitivity Properties  993
43.12  Incidence Structures, Graphs and Codes  995

44 FINITE PLANES . . . . . . . . . . . . . . . . . . . . . . . 996

44.1  Introduction  998
44.2  Construction of a Plane  998
44.3  The Point-Set and Line-Set of a Plane  1000
44.3.1  Introduction  1001
44.3.2  Creating Point-Sets and Line-Sets  1001
44.3.3  Using the Point-Set and Line-Set to Create Points and Lines  1001
44.3.4  Retrieving the Plane from Points, Lines, Point-Sets and Line-Sets  1002
44.4  The Point Set and Line Set  1002
44.5  The Structures Associated with a Plane  1005
44.6  Subplanes  1005
44.7  The Dual Plane  1007
44.8  Numerical Invariants of a Plane  1007
44.9  Operations on Points and Lines  1007
44.10  Properties of Planes  1009
44.11  The Connection between Projective and Affine Planes  1009
44.12  Conversions  1009

781 CONTENTS

44.13  Arcs  1010
44.14  Unitals  1011
44.15  Identity and Isomorphism  1012
44.16  The Collineation Group of a Plane  1012
44.16.1  The Collineation Group Function  1012
44.16.2  Central Collineations  1013
44.16.3  Action of Collineations  1014
44.16.4  Stabilizers of Points and Lines  1015
44.16.5  Transitivity Properties  1017
44.17  Planes, Graphs and Codes  1017

45 ERROR-CORRECTING CODES . . . . . . . . . . . . . . . . 1018

45.1  Introduction  1020
45.2  Definition of a Code  1020
45.2.1  Construction of General Linear Codes  1020
45.2.2  Construction of Standard Linear Codes  1022
45.2.3  Construction of General Cyclic Codes  1023
45.2.4  Construction of BCH Codes and their Generalizations  1024
45.2.5  Construction of Quadratic Residue Codes  1027
45.3  Access Functions  1028
45.4  Construction of Subcodes of Linear Codes  1029
45.4.1  The Subcode Constructor  1030
45.4.2  Sum, Intersection and Dual  1030
45.5  Constructing New Codes from Old  1030
45.6  Changing the Alphabet of a Code  1031
45.7  Operations on Codewords  1032
45.7.1  Construction of a Codeword  1032
45.7.2  Elementary Operations on Codewords and Vectors  1033
45.7.3  Accessing Components of a Codeword  1034
45.8  Boolean Predicates  1034
45.9  Coset Leaders  1035
45.10  The Standard Form  1036
45.11  Structural Properties of Codes  1037
45.11.1  The Minimum Weight  1037
45.11.2  The Weight Distribution  1038
45.11.3  The MacWilliams Transform  1038
45.11.4  The Weight Enumerator  1038
45.11.5  Words  1039
45.11.6  Other Structural Properties  1039
45.12  Group Actions on Codes  1040

IX APPENDIX . . . . . . . . . . . . . . . . . 1043

46 SYSTEM FEATURES . . . . . . . . . . . . . . . . . . . . . 1044

46.1  System Calls  1046
46.2  External Files  1046
46.3  Set and Get  1049
46.4  History  1053
46.5  The Magma Line Editor  1054
46.5.1  Key Bindings (Emacs and VI mode)  1054
46.5.2  Key Bindings in Emacs mode only  1056
46.5.3  Key Bindings in VI mode only  1057

CONTENTS 782

47 PRECEDENCE . . . . . . . . . . . . . . . . . . . . . . . . 1060 48 RESERVED WORDS . . . . . . . . . . . . . . . . . . . . . 1061 49 INDEX OF SIGNATURES . . . . . . . . . . . . . . . . . . . 1062