# Course Identification

## Lecturers and Teaching Assistants

## Course Schedule and Location

## Field of Study, Course Type and Credit Points

## Comments

## Prerequisites

A knowledge of linear algebra

## Restrictions

## Language of Instruction

## Attendance and participation

## Grade Type

## Grade Breakdown (in %)

## Evaluation Type

**Take-home exam**

## Scheduled date 1

## Estimated Weekly Independent Workload (in hours)

## Syllabus

__Syllabus: Finite Algebraic Structures for CS __

Josephine Shamash

Fall 2022

This course is intended for computer science students who have not taken advanced algebra courses as part of their first degree. The course focuses on the theory of finite structures which are important in applications of algebra to computer science, especially for error-correcting codes. Detailed examples will be investigated.

1. **Basics:** Fields, rings, groups, vector spaces and their substructures. Homomorphisms of rings, ideals, quotient rings.

2. Polynomial rings over fields and their properties. The Chinese remainder Theorem and its corollary for the structure of *Z/mZ*,

3. **Finite Group theory**: Introduction, finite cyclic groups and their properties, the fundamental theorem of finite abelian groups.

4. Sylow's theorems and applications to examples. (Solvability and Rips exercise of numbers up to 100)

5. The symmetric groups: their conjugacy classes and structure. Simplicity of the alternating group for .

6. Finite Simple groups and the classification theorem – survey.

7. Introduction to complex characters and representations of finite groups

8. **Finite Field theory:** Basic extension theorem, Finite fields, their structure and properties. Existence and uniqueness of finite fields of order *q* for any prime power *q*. Detailed examples and arithmetic in finite fields.

9. Factorization of polynomials over finite fields.

10. Wedderburn's theorem that finite division rings are finite fields.

11. Counting irreducible polynomials over finite fields. Finding irreducible polynomials for error-correcting codes over finite fields using the Berlekamp algorithm. (skipped 2019)

12. The structure of some classical matrix groups over finite fields, conjugacy classes in finite matrix groups, detailed examples.

13.** Vector spaces over finite fields and error-correcting codes**: Bilinear forms and orthogonality in finite dimensional vector spaces over fields of characteristic 2.

14. The theory of linear codes over finite fields of characteristic 2.

Examples: Hamming codes, using the structure of the field of 16 elements to define the BCH double-error correcting code.

**Bibliography:**

Nathan Jacobson: Basic Algebra I & II

I. Martin Isaacs: Algebra: A Graduate Course (Chapter 21 on finite fields)

Serge Lang: Algebra

Vera Pless.: Error-correcting Codes

Ian Stewart: Galois Theory

- online:

## Learning Outcomes

A general knowledge of finite algebraic structures, and detailed finite examples relevant to computer scientists.