Matematics++

Matematics++, spring semester 2025/2026

Robert Šámal, Martin Tancer

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 Wednesday at 15:40 in room S9.

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 Ondřej Chwiedziuk. Here is the exercise webpage.

Literature

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

A course of Hamed Hatami
Audrey Terras: Fourier Analysis on Finite Groups and Applications (London Mathematical Society Student Texts)
A course of Ryan O'Donnell
A course of Guy Kindler
T. W. Körner: Fourier Analysis, Cambridge University Press, 1989
Y. Katznelson: An Introduction to Harmonic Analysis, Cambridge University Press, 2004

Lectures

Lecture 1, Feb 18 2026: Motivation for the discrete Fourier transform. Characters and their properties: Pontryagin dual; expected value of a nontrivial charactes; characters form a basis of the space of complex functions from an Abelian group. A first version of Fourier transform. [KMS 3.1, 3.2]
Lecture 2, Feb 25 2026: Fourier transform (traditional version). Inverse Fourier transform. Plancherel's and Parseval's theorems. Aplication: linearity testing of Boolean functions. [KMS 3.2, 3.3.1]
Lecture 3, Mar 4 2026: Arithmetic progressions in $\mathbb Z_3^n$. [KMS 3.3.2]
Lecture 4, Mar 11 2026: Convolution. The Fourier coefficient of the convolution is the product of the Fourier coefficients of the two functions. Quick multiplication of polynomials using convolution. KKL theorem (Sketch of the proof; it is not expected that you would know technical formulas from the sketch during the exam). Sum of characters over a subgroup. Poisson summation formula. [KMS 3.4, 3.5, 3.6.1]