Matematics++

Matematics++, spring semester 2022/2023

Ida Kantorová, Robert Šámal, Martin Tancer

There is no lecture on February 14!

Topic

Modern computer science often uses mathematical tools that reach beyond the scope of standard mathematical courses in the bachelor program. This course will present a (somewhat condensed) introduction to several fields of mathematics that proved especially useful in computer science and in discrete mathematics. Computer science applications will be shown as well. This course is suitable for master's or PhD students of computer science. The students are assumed to have prior knowledge in the extent of mandatory courses of the bachelor program in computer science. For illustration, see topics of past lectures.

This year we will focus on

Fourier transform -- mostly discrete -- and its many applications.
Representation theory -- noncommutative version of Fourier transform.
Polynomials in many variables -- properties of their null sets (called varieties). And their usage for surprising proofs in discrete mathematics and geometry.

Will be taught in English if some of the audience needs it.

Schedule

Lecture is every Tuesday at 12:20 in room S7. We start on February 21.

Prerequisites

Interest in mathematics, knowledge roughly in the extend of cs bachelor degree at MFF UK. We will mostly build upon analysis, probability and linear algebra.

Extent

Two hours of lectures and two hours of tutorials weekly (2/2). Credit and exam.

Tutorials

A substantial part of the class will consist of independent solving of homework problems. Credit will be given for solving a sufficient number of problems. The exercises will be led by Denys Bulavka and Petr Chmel. Here is the exercise webpage.

Exam

Will be oral, containing both theory and problems. For the arrangement of time, email the lecturers. (Ideally all of them, the one with similar time preferences as you will reply.) Note: each of us will examine you from anything that was being taught, not just his/her third!

Literature

[KMS] I. Kantor, J. Matoušek, R. Šámal: Mathematics++ (should be available in the library)
More for the first part:

Kurz Hameda Hatamiho
Audrey Terras: Fourier Analysis on Finite Groups and Applications (London Mathematical Society Student Texts)
Kurz Irit Dinur a Ehuda Friedguta
Kurz Ryana O'Donnella
Kurz Guye Kindlera
T. W. Körner: Fourier Analysis, Cambridge University Press, 1989
Y. Katznelson: An Introduction to Harmonic Analysis, Cambridge University Press, 2004

Probraná témata

1. přednáška 21. 2. 2023: Diskrétní Fourierova transformace = převod funkcí definovaných na konečné abelově grupě do šikovné báze. Definice charakterů a jejich vlastnosti. (Pontrjaginův duál, střední hodnota netriviálního charakteru, charaktery tvoří bázi prostoru komplexních funkcí z abelovské grup). Podle knížky kapitola 3.1.
2. přednáška 28. 2. 2023: Fourierova transformace, definice. Inverzní Fourierova transformace. Základní vlastnosti: Plancherelova a Parsevalova věta. Aplikace: testování linearity booleovské funkce. Kapitoly 3.2 a 3.3.1 podle knihy.
3. přednáška 7. 3. 2023: Aritmetické posloupnosti v $\mathbb Z_3^n$. Konvoluce (zatím jenom definice a lemma o násobení Fourierových koeficientů vzhledem ke konvoluci; lemma zatím bez důkazu). Kapitoly 3.3.2 a 3.4 podle knihy.
4. přednáška 14. 3. 2023: Důkaz lemma z minule. Násobení polynomů pomocí konvoluce. KKL věta (důkaz jen velmi hrubý nástin; neočekává se, že se ho budete učit podrobně). Součet charakterů přes podgrupu a Poissonova sumační formule (bez dk.). Kapitoly 3.4, 3.5 a 3.6 z knihy (pouze velmi stručně).