## Summer term 2022 Universal Algebra II (NMAG450)

Lecture: Monday 10:40 - 12:10, lecture room K7
Exercise classes: even weeks, Monday 12:20 - 13:50, lecture room K7, given by Kevin Berg

### Lecture notes

Syllabus:This course discusses selected topics from Universal Algebra. This includes
1. Equational logic: the equational completeness theorem, term rewriting systems, Knuth-Bendix algorithm
2. Commutator theory: Abelianness, the term condition commutator, applications
3. Finitely based algebras: McKenzie's theorem on algebras with DPC
4. Maltsev conditions: Taylor terms, polymorphism clones and CSPs, absorption theory
Evaluation:
Exercises: there will be 3 homework assignments, on which you need to score 60% to get ''Zápočet''
Lecture: oral examination (appointment by mail: michael@logic.at).

Date Topics Lecture notes Exercises Homework
14/02Equational theories, fully invariant congruences;
completeness theorem for equational logic.
Section 1.1
21/02term rewrite systems, convergence, Knuth-BendixSection 1.2, 1.3 1.2,1.3,1.4
28/02Abelian and affine algebras
Herrmann's fundamental theorem
Section 2.1, 2.2
07/03The term conditions commutator,
Examples (groups and lattices)
Section 2.3 1.2,1.3,1.4
2.12, 2.13
HW1: 1.6, 1.8 (first point) 2.10, 2.14
14/03A characterization of CD varieties
by the commutator
Section 2.4
21/03Birkhoff's theorem on Id_n
a non-finitely based algebra
Chapter 3 2.19,2.20HW1 due
28/03Park's conjecture
McKenzie's DPC theorem
Section 3.1
04/04Jonsson's lemma
DPSC varieties
Section 3.2 3.2,3.3, 3.11HW2: 3.4, 3.5, 3.6, and 4.1
11/04Baker's theorem
CSPs: Definition and Examples
Section 3.2, 4.1
18/04Easter holiday
25/04Pol-Inv revisited, clone homomorphismsSection 4.1., 4.2. HW2 due
02/05Minion homomorphisms, Taylor's theoremSection 4.2. 4.3, 4.13HW3: 4.6,4.7,4.8 and 4.12
09/05Loop lemma (for triangles)
Siggers terms
Section 4.3
16/05only Exercise class today! HW3 due

Consultation:
If you have questions on the material, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but personal meetings can be arranged. Please make also use of the exercise classes to discuss your questions.

Further reading:

## Winter term 2021/22 Algebra 1 (NMAI062)

Please register to the !! Moodle course !!

Lecture notes

Lecture: Wednesday 10:40 - 12:10, lecture room S4
Exercise classes: Tuesdays 15:40 - 17:10, lecture room S10, given by Kevin Berg
(current covid regulations)

Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 60/100 points. These can be obtained from 3 homework assignments (3*30 points), or weekly quizzed (10 points), which will be posted on the Moodle course
The final grade will be determined by a written exam. Admission to the exam requires passing the exercise class.

Syllabus:This course aims to give an introduction to algebra for computer science students. It will cover the following topics:
1. Number theory: prime factorization, congruences, Euler's theorem and RSA, the Chinese remainder theorem
2. Polynomials: rings and integral domains, polynomial rings, irreducibility, GCD, the Chinese remainder theorem and interpolation, the construction of finite fields and applications (error correcting codes, secret sharing,...)
3. Group theory: permutation groups, subgroups, Langrange's theorem, group actions and Burnsides's theorem, cyclic groups, discrete logarithm and applications in cryptography
Literature:The course has its own lecture notes, which are based on David Stanovsky's material from last year, and will be constantly updated during the semester. Complementary resources are for instance
• J. Rotman, A First Course in Abstract Algebra (available in our library),
• C. Pinter A Book of Abstract Algebra (freely available online),
• or any other undergraduate level textbook on abstract algebra.
Consultation:
If you have open questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

## Lecture notes

Grading:
Exercises: homeworks (you need to score 60% on the 3 best out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
Not available from 17.07.-27.07, 17.08-28.08

Additional literature:

Date Topics Lecture notes Exercises Homework
24/02Equational theories, fully invariant congruences;
completeness theorem for equational logic.
Section 1.1 1.1-1.3
02/03Convergent term rewriting systems Section 1.2
09/03Critical pairs, Knuth-Bendix algorithm;
Affine algebras
Section 1.2, 1.3
Section 2.1
1.4, 1.8,1.9 1.5,1.6,1.7
due on 24/03
16/03Abelian algebras
Herrmann's fundamental theorem
Section 2.1, 2.2 2.1-2.9;
in particular 2.2, 2.6
23/03Centralizer relation and commutator
Example: groups
Section 2.3 2.11, 2.12 2.10, 2.13, 2.14
due on 07/04
30/03Properties of the commutator
Characterization of CD varieties
Section 2.3, 2.4 2.15-2.20;
in particular 2.18,2.19
06/04Nilpotent algebras
and open questions
Section 2.5 Section 2.5
20/04Birkhoff's theorem on Id_n(A)
Example of a non-finitely based algebra
Chapter 3 3.1-3.4
27/04McKenzies DPC theorem Section 3.1 3.5-3.8
04/05CSPs, pp-definable relations
Pol-Inv
Section 4.1 4.1-4.5 3.5,3.6,4.3 due on 19/05
11/05 Clone and minion homomorphisms
Section 4.2 4.6-4.8
18/05Taylor operations
the CSP dichotomy conjecture/theorem
Section 4.3 4.9-4.11 4.6,4.7,4.8
until your exam

## Winter term 2019/20 Exercises in Universal Algebra I (NMAG405)

See Libor's website.

## Summer term 2019 Universal Algebra II (NMAG450)

The course will roughly follow Libor Barto's lecture from 17/18.

Lecture: Thurday 9:00 - 10:30 Seminar room of KA
Exercises: Thurday 10:40 - 12:10 Seminar room of KA (only odd semester weeks = even calendar weeks)

Grading:
Exercises: homeworks (60% from 3 best scores out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
next available dates 27/05-07/06; 17/06-20/06; 04/07-

Literature:

Date Topics Recommended reading Exercises Homework
28/02Abelian and affine algebras, Fundamental theorem. Bergman 7.3 Ex. 1
07/03Checking identities, Relational description of Abelianness;
Centralizer relation (in general and in groups)
Bergman 7.4
14/03Properties of the commutator
Characterization of CD varieties
Bergman 7.4 Ex. 2 HW 1
due 28/03
21/03Equational theories, fully invariant congruences;
completeness theorem for equational logic.
Bergman 4.6
Jezek 13
28/03Reduction order, critical pairs
Knuth-Bendix algorithm
Jezek 13Ex. 3
04/04Examples of finitely based and non finitely based algebrasBergman 5.4HW 2
due 25/04
11/04 McKenzie's result on definable principal congruencesBergman 5.5Ex. 4
18/04Constraint satisfaction problems over finite templates
Pol-Inv revisited
BKW
25/04(h1-)clone homomorphisms
Taylor terms
BKWEx. 5HW 3
due 09/05
02/05Taylor's theoremBergman 8.4.
09/05Smooth digraphs, algebraic length 1,absorptionBK
16/05Absorption, transitive termsBKEx. 6HW 4
23/05Absorption theorem, LLL (loop lemma 'light', for linked digraphs)BK

## Winter term 2018/19 Exercises in Universal Algebra I (NMAG405)

see David Stanovsky's website.