Applied abstract algebra (draft)

Applied Abstract Algebra - D. Joyner, R. Kreminski, J. Turisco - 2-1-2003......Page 1
Contents......Page 3
Preface......Page 10
1.1 Introduction......Page 13
1.2 Divisibility......Page 14
1.2.1 Division algorithm......Page 17
1.2.2 The greatest common divisor and least common multiple......Page 19
1.3 Binary and m-ary notation......Page 24
1.3.1 Application: Divisibility criteria......Page 25
1.3.2 Application: Winning the game of Nim......Page 27
1.4.1 Ideals......Page 30
1.4.2 The Euclidean algorithm......Page 31
1.4.3 Linear diophantine equations......Page 33
1.4.4 The extended Euclidean algorithm......Page 34
1.4.5 Euler's phi function......Page 36
1.5 Primes......Page 38
1.5.2 The Fundamental Theorem of Arithmetic......Page 40
1.5.3 Primality testing......Page 43
1.6 Multiplicative Functions......Page 45
1.6.1 Perfect numbers and Mersenne primes......Page 49
1.7 Congruences......Page 50
1.7.2 Aside on equivalence relations......Page 51
1.7.3 Properties of = (mod m)......Page 52
1.7.4 Repeated squaring algorithm......Page 54
1.7.5 Fermat's little theorem......Page 55
1.7.6 Linear recurrence equations......Page 56
1.7.7 Application: Two ciphers......Page 58
1.7.8 Feedback with carry shift register ciphers......Page 61
1.7.9 Application: calendar calculations......Page 62
1.7.10 The Chinese remainder theorem......Page 64
1.7.11 An application to Euler's \phi -function......Page 65
1.8.1 Fermat's Little Theorem, revisited......Page 68
1.8.2 Euler's theorem......Page 69
1.8.3 Application: Decimal expansions of rational numbers......Page 70
1.8.4 Application: RSA encryption......Page 72
1.8.6 Application: Dife-Hellman key exchange......Page 74
1.8.7 Application: ElGamal encryption......Page 75
1.9 Arithmetic properties of Z/nZ: a summary......Page 78
1.10 Special project: continued fractions (optional)......Page 80
1.11 Number theory exercises using GAP......Page 82
1.12 Number theory exercises using MAGMA......Page 85
2 Polynomials, rings and felds......Page 91
2.1 Fields: basic examples......Page 92
2.1.1 Quadratic number fields......Page 95
2.1.2 A construction of finite fields......Page 98
2.1.3 Matrix constructions of finite fields......Page 100
2.2 Polynomials......Page 105
2.2.2 Roots......Page 107
2.2.3 The division algorithm......Page 108
2.2.4 The Euclidean algorithm......Page 109
2.2.5 Extended Euclidean Algorithm......Page 112
2.3.1 Motivation......Page 115
2.3.2 The ring F[x]......Page 116
2.4 Factoring polynomials......Page 118
2.4.2 General principles in factoring......Page 119
2.4.3 Factoring x^n ? 1 over F_p......Page 120
2.4.4 Factoring over a finite field......Page 121
2.5 Modular arithmetic with polynomials......Page 123
2.6 Arithmetic properties of F[x]/(m(x))......Page 125
2.6.1 Constructing finite extensions of fields......Page 126
2.6.2 Kronecker's theorem......Page 129
2.7 Companion matrices and extension fields......Page 130
2.8.1 Monomials......Page 132
2.8.2 Leading terms......Page 133
2.8.3 Grobner bases......Page 135
2.8.4 Buchburger's algorithm......Page 136
2.8.5 Applications......Page 137
2.9 Special project: Nimbers......Page 139
2.10 Special project: factoring over C......Page 145
2.10.1 Explicit formulas for the roots......Page 146
2.10.2 Factoring xn - 1 over C......Page 148
2.12 Special Project: Factoring over Q or Z......Page 150
2.12.1 Primitive polynomials......Page 151
2.12.2 Factoring strategies......Page 152
2.12.3 Factoring x^n - 1 over Q......Page 153
2.13.1 Finite felds......Page 155
2.13.2 Some vector spaces......Page 157
2.13.3 Rings......Page 158
2.13.4 Polynomials......Page 159
2.13.5 Grabner bases......Page 160
2.14.1 Finite felds......Page 163
2.14.4 RSA for polynomials in MAGMA......Page 165
3.1 Background on vector spaces......Page 171
3.2.1 Binary symmetric channel......Page 175
3.2.2 Uncertainty......Page 176
3.3 Motivation and notation for codes......Page 177
3.3.1 Basic defnitions......Page 178
3.3.2 The Hamming metric......Page 179
3.3.3 Properties of the minimum distance......Page 182
3.4 [n, k, d]-codes and error correction......Page 183
3.4.1 The generator matrix......Page 185
3.4.2 The binary Hamming [7, 4, 3] code......Page 189
3.5 Bounds on the parameters of a code......Page 191
3.5.1 Question: What is "the best" code......Page 194
3.6 The dual code......Page 195
3.7 Computing the check matrix and the encoding matrix......Page 196
3.8 Syndrome decoding......Page 198
3.9.1 Binary hamming codes......Page 201
3.9.2 q-ary Hamming codes......Page 202
3.10  Cyclic codes......Page 204
3.10.1 Quadratic residue codes......Page 208
3.11 Application: The hats problem......Page 211
3.12 Application: Searching with lies......Page 212
3.12.1 The case of one lie......Page 213
3.13 Some unsolved problems in coding theory......Page 214
3.14.1 Background on finite fields......Page 215
3.14.2 Some vector spaces......Page 217
3.14.3 Some simple codes......Page 218
3.14.4 Hamming codes......Page 220
3.14.5 Reed-Muller codes......Page 221
3.14.6 Cyclic codes......Page 222
3.15.2 Hamming codes......Page 223
3.15.3 Reed-Muller codes......Page 225
3.15.4 Cyclic codes......Page 226
4.1 Functions......Page 227
4.2 Permutations......Page 232
4.3 Inverses......Page 236
4.4 Cycle notation......Page 239
4.5 An algorithm to list all the permutations......Page 246
4.6 Application: The rotation game......Page 250
4.7 Application: Bell ringing......Page 251
4.8 Application: Rubik's cubes......Page 255
4.8.1 2 x 2 Rubik's cube......Page 256
4.8.2 3 x 3 Rubik's cube......Page 257
4.9 Special project: Tiling with groups......Page 259
4.10 Special project: Latin squares......Page 260
5.1 Cyclic groups......Page 265
5.2 The dihedral group......Page 266
5.3 The symmetric group......Page 268
5.4 General defnitions......Page 270
5.5 The general linear group......Page 271
5.5.1 m x n matrices......Page 272
5.5.2 Multiplication and inverses......Page 273
5.5.3 Determinants......Page 274
5.5.4 The definition of GL(n)......Page 276
5.6 Application: The automorphism group of a code......Page 279
5.7 Abelian groups......Page 281
5.8 Permutation groups......Page 283
5.9 Subgroups......Page 285
5.10 Puzzling examples......Page 288
5.10.1 Example: The Verhoeff check digit scheme......Page 289
5.10.2 Example: The two squares group......Page 290
5.11 Commutators......Page 293
5.12 Conjugation......Page 294
5.13 Cosets......Page 298
5.14 Functions between two groups......Page 301
5.15 Application: Campanology, revisited......Page 306
5.16.1 Graphs......Page 307
5.16.2 Cayley graphs......Page 309
5.16.3 Application: God's algorithm......Page 311
5.17 Kernels are normal, some subgroups are not......Page 313
5.17.1 The alternating group......Page 314
5.18 Quotient groups......Page 315
5.19.1 Permutations......Page 318
5.19.2 Permutation groups......Page 319
5.19.3 GAP project: Why Steinhaus' algorithm works......Page 321
5.20.2 Permutation groups......Page 322
5.20.3 MAGMA project: Why Steinhaus' algorithm works......Page 325
6.1 Alternant codes......Page 327
6.2.1 The construction......Page 328
6.3 Tanner graph of a code......Page 332
6.4 A brief guide to Goppa codes......Page 333
6.4.1 Examples of curves......Page 334
6.4.2 Examples of points and divisors......Page 335
6.4.3 Examples of Riemann-Roch spaces......Page 337
6.4.4 Examples of Goppa codes......Page 339
6.5.1 Sparse check matrix definition......Page 341
6.5.2 Graph-theoretic definition......Page 342
6.5.3 Other constructions......Page 344
6.6.1 Introduction......Page 347
6.6.2 Background......Page 348
6.6.3 S(5, 6, 12)......Page 351
6.6.4 The algorithm......Page 355
7.1.1 Introduction......Page 357
7.1.2 Input-output......Page 358
7.1.3 Polynomials and other functions......Page 360
7.1.4 Lists......Page 361
7.1.5 Vectors and matrices......Page 362
7.1.6 Using for loops......Page 363
7.1.7 Sets......Page 364
7.1.9 GAP functions and procedures......Page 365
7.2.1 Introduction......Page 366
7.2.2 Input-output......Page 368
7.2.3 Polynomials and other functions......Page 369
7.2.4 Common data structures......Page 371
7.2.5 Lists, sequences, via for loops......Page 372
7.2.6 Removing elements from a list......Page 374
7.2.7 Cartesian products......Page 375
7.2.9 Adding numbers in a list......Page 376
7.2.10 Membership......Page 377
7.2.11 More complicated sets......Page 378
7.2.12 for loops......Page 379
7.2.13 if then statements......Page 380
7.2.14 MAGMA functions and procedures......Page 381
7.2.15 Printing......Page 382
7.2.21 Plane curves......Page 383
7.2.22 Solutions to exercises......Page 384