Applied Algebra (ΜΕΜ244) - Fall semester 2019-20

Department of Mathematics and Applied Mathematics, University of Crete

Évariste Galois

Basic information

Lecturer:Giorgos Kapetanakis, (gnkapet@gmail.com)
Schedule:Tuesday 11.00-13.00 and Friday 09.00-11.00 (E204)
Language:English
Grading:Final exam

Bibliography

  1. Α. Κοντογεώργης, Ι. Αντωνιάδης, Πεπερασμένα σώματα και κρυπτογραφία, Εκδόσεις Κάλλιπος.
  2. Δ. Βάρσος, Μια εισαγωγή στην αλγεβρική θεωρία κωδίκων, Εκδόσεις Κάλλιπος.
  3. R. Lidl, H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press.
  4. S. Ling, C. Xing, Coding theory: a first course, Cambridge University Press.

Announcements

Exams

Exercises

Calendar

1st week (23/09-27/09):
We went through a quick reminder of well-known algebraic concepts: rings, groups, various classes of rings, zero-divisors, integral domains, ring characteristic, units, fields, ideals, principal ideals, principal ideal domains, quotient rings, prime and irreducible elements. We proved that, in an integral domain, a prime element is irreducible. We saw an example of an integral domain element that is irreducible but not prime.
2nd week (30/09-04/10):
We defined prime and maximal ideals and we gave the corresponding characterizations of such ideals using quotient rings and we characterized prime and maximal principal ideals. We concluded that in a PID, irreducible elements are prime. The Unique Factorization Theorem in PID's was stated (without proof) and we gave the definition of a Euclidean Domain. We proved that a Euclidean domain is a PID. We then gave the basic terminology of the polynomial ring and its basic properties and we focused on the polynomial ring over a field and some of its properties. We defined the polynomial's root multiplicity and we characterized (using the derivative) polynomials with multiple roots.
3rd week (07/10-11/10):
We focused on field extensions. We defined simple extensions and prime fields and we fully described the prime fields. We mentioned that if F/K is a field extension, then F is a K-vector space and we defined the degree of an extension. We gave the definitions of algebraic and transcendental elements and extensions. Then, we defined the minimal polynomial of an algebraic element and proved its basic properties. We defined and gave the basic properties of the polynomial basis of a simple algebraic extension. We then defined the algebraic closure of a field and the splitting field of a polynomial and proved that a finite field has prime characteristic and its order is a prime power. We proved that every element α of a finite field of q elements satisfies αq=α and that a finite field of q elements is the splitting field of xq-x over some subfield. We concluded with relevant exercises.
4th week (14/10-18/10):
We solved the exercises from the first set. Then, we proved that there exists a unique (up to isomorphism) finite field of q elements for every prime power q. We then showed that the multiplicative group of a finite field is cyclic and defined primitive elements. We presented the Discrete Logarithm Problem and the Diffie-Hellman key exchange. We showed that the finite field of pn elements is a subfield of the finite field of pm elements if and only if n∣m. We saw examples.
5th week (21/10-25/10):
We described the roots of an irreducible polynomial, its splitting field and the irreducible factors of xqn-x over the finite field of q elements. We defined the conjugates of a finite field element and, by using the Möbius function, we counted the monic irreducible polynomials of given degree over a finite field. The corresponding formula for primitive polynomials was also given and some relevant examples were provided. Then, we proved that En, the n-th roots of unity form a cyclic multiplicative group of order m, the p-free part of n, where p stands for the characteristic of the base field. We concluded with the definitions of the primitive n-th roots of unity and the n-th cyclotomic polynomial.
6th week (28/10-01/11):
We discussed the the exercises of the second assignment. We proved that the n-th cyclotomic field is a simple algebraic extension over its base field. We described the factorizations of xn-1 and Ψn, the n-th cyclotomic polynomial. We proved that Ψn has coefficients in the prime subfield and described its splitting field. We proved that f, with deg(f)=n is irreducible over GF(q) iff α,αq,...,αqn-1 are distinct, where α is a root of f. As a consequence, we proved that xp-x-c is irredicible over GF(p), where c is non-zero. We moved on with the definition of the (absolute) trace function from GF(q) to GF(p), where q=pn.
7th week (04/11-08/11):
We proved that the trace function is surjective and GF(p)-linear. The definition of the (absolute) norm was given along with its basic properties. A number of revision exercises about finite fields was discussed and we did a quick introduction to coding theory. Then, we gave the basic definitions of coding theory (alphabet, word, code, codeword, information rate, (n,M)-code).
8th week (11/11-15/11):
We gave some further basic definitions of coding theory (communication channel, Hamming distance, minimum distance of a code, (n,M,d)-code etc.) and we briefly discussed Shannon's theorem. We proved that Hamming distance is a metric and we defined the maximum likelihood and the minimum distance decoding rules and we showed that they are equivalent when a symmetric communication channel is used. We then proved that a code of minimum distance d detects d-1 errors and corrects ⌊(d-1)/2⌋ errors. We answered some of the exercises of the third set.
9th week (18/11-22/11):
We finished the third set. We moved on to linear codes and defined their dimension, we introduced the [n,k]-code and [n,k,d]-code notations and we defined the dual code, self-orthogonal and self-dual codes. Finally, we concluded with some basic properties and examples. Also, we defined the Hamming weight of a word and proved some of its basic properties, we defined the minimum (Hamming) weight of a code and proved that if the code is linear it coincides with its minimum distance.
10th week (25/11-29/11):
We defined the generator and parity-check matrices of linear codes and when those matrices are in standard form. We showed the relation between the standard forms of the generator and parity-check matrices and the relation between the minimum distance of a code and its parity-check matrix. Further, we defined the code equivalency and showed the encoding procedure for a linear code, as well as the coset decoding scheme for linear codes.
11th week (02/12-06/12):
We answered the exercises of the 4th set. We defined the syndromes of a code, proved their basic properties, described the syndrome decoding scheme and saw examples. The numbers Aq(n,d) and Bq(n,d) were defined and the main coding theory problem was introduced.
12th week (09/12-13/12):
The sphere packing (Hamming) and the Singleton bounds were proven. These bounds led to the definition of perfect and MDS codes. The binary Hamming codes were defined and their parameters were computed. We saw the propagation rules for constructing new codes from old ones and in particular the (u,u+v)-construction. Finally, we defined the (first order) Reed-Muller codes.
13th week (16/12-20/12):
We answered the exercises of the fifth set. We discussed a number of revision exercises from Coding Theory.