Applied Algebra (ΜΕΜ244) - Fall semester 2018-19

Department of Mathematics and Applied Mathematics, University of Crete

Évariste Galois

Basic information

Lecturer:Giorgos Kapetanakis, (gnkapet@gmail.com)
Schedule:Monday 15.00-17.00 and Wednesday 13.00-15.00 (Α208)
Language:English
Grading:Final exam with optional assignments

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

Assignments

Calendar

1st week (01/10/18-05/10/18):
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.
2nd week (08/10/18-12/10/18):
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.
3rd week (15/10/18-19/10/18):
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 a relevant exercise.
4th week (22/10/18-26/10/18):
We proved that, if a, b are in a field of prime characteristic p then (a±b)p = ap±bp. 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 called its generators primitive. We presented the Discrete Logarithm Problem and the Diffie-Hellman key exchange. We then discussed the exercises from the first assignment and 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 some examples.
5th week (29/10/18-02/11/18):
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 and we concluded with the definitions of the primitive n-th roots of unity and the n-th cyclotomic polynomial.
6th week (05/11/18-09/11/18):
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 discussed the the exercises of the second assignment. 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. Finally, we proved that the trace function is surjective and GF(p)-linear.
7th week (12/11/18-16/11/18):
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.
8th week (19/11/18-23/11/18):
We gave the basic definitions of coding theory (alphabet, word, code, codeword, information rate, (n,M)-code, 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 if a code has minimum distance d, it detects d-1 errors and it corrects ⌊(d-1)/2⌋ errors. 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.
9th week (26/11/18-30/11/18):
We solved the exercises of the third assignment, as well as a few more revision exercises on finite fields. Also, we defined the Hamming weight of a word and proved some of its basic properties.
10th week (03/12/18-07/12/18):
We defined the minimum (Hamming) weight of a code and proved that if the code is linear it coincides with the minimum distance. 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.
11th week (10/12/18-14/12/18):
We defined the cosets and syndromes of a code, proved their basic properties, described the coset and syndrome decoding schemes and saw examples. The numbers Aq(n,d) and Bq(n,d) were defined and the main coding theory problem was introduced. The sphere packing (Hamming) and the Singleton bounds were proven. These bounds led to the definition of perfect and MDS codes. After a short mention of the MDS conjecture, the binary Hamming codes were defined and their parameters were computed.
12th week (17/12/18-21/12/18):
We discussed a number of revision exercises from Coding Theory. Also, the RSA cryptosystem was briefly discussed.