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]
Lecture 5, Mar 18 2026: Characters and Fourier transformation in infinite groups. Description of $\hat{\mathbb Z}$, $\hat{\mathbb R}$ and $\hat{\mathbb T}$. Fourier analysis for $\mathbb T$ (analysis of 1-periodic functions). Poisson summation formula: just information. (It is useful though!) [KMS 3.7]
Lecture 6, Mar 25 2026: Inverse Fourier transforms -- Fourier series. The form with complex exponentials, as well as sums of sines and cosines (for real 1-periodic functions). Convergence of the series: Dirichlet's and Fejér's theorem. Fourier and differentiation. Illustration of the Dirichlet's and Fejér's theorem [KMS 3.7]
Lecture 7, Apr 1 2026: Representations of finite groups: introduction, motivation, definition, examples. Invariant subspace, irreducible representation. Every representation can be written as a sum of irreducible ones (Maschke's theorem). Weyl unitarity trick. [KMS 4.1-2]
Lecture 8, Apr 8 2026: Schur's lemma. Corollary: irreducible representations of finite abelian groups are 1.dimensional. Proposition on orthogonality of entries of matrices of two irreducible representations (without a proof). Corollary on orthogonality of characters. Proposition: formula for the number of summands in an irreducible decomposition equivalent to a given irreducible representation. Corollary: uniqueness of a decomposition; characters determine representations; and irreducibility criterion. [KMS 4.3]
Lecture 9, Apr 15 2026: Character of the regular representation. Corrolaries: every irreducible representation is in regular one with the multiplicity corresponding to the dimension; sum of the dimensions squared is the size of the group; and a formula for products of dimensions with characters. Non-commutative Foruier analysis: Fourier transform and the formula for Fourier inversion (no need to memorize the latter formula). The number of mutually nonequivalent representations is the number of conjugacy classes (without a proof). Irreducible representations of the symmetric group: Partitions; Ferrer's diagram, tableuax and tabloids. Specht module (only description of the basis); the dimeansion equals to the number of standard tableaux for a given partition. Communication complexity of a function. Motivation: log-rank conjecture. Application of representations: A function of communication complexity more than constant times log-rank. Only sketched the computation of the rank of the matrix of this function. [KMS 4.3, 4.4, 4.5]
Lecture 10, Apr 22 2026: Polynomials -- with many variables and over a general ring. Schwartz-Zippel theorem and its use for polynomial identity testing, several concrete examples (polynomial multiplication, matching in bipartite graphs). Counting monomials. [KMS 5.1-3]
Lecture 11, Apr 29 2026: Polynomial method: use polynomial interpolation and "contagious vanishing" to bound number of joints in a set of lines.
Algebraic varieties, ideals. Noetherian rings and Hilbert basis theorem (just statement). [KMS 5.4-5]
Lecture 12, May 6 2026: Hilbert basis theorem (proof). Hilbert Nullstellensatz (weak and strong). Formulations via ideals and via solving equations. Proof via resultants. [KMS 5.4-5]
Lecture 13, May 20 2026: Bézout's inequality in the plane (proof via Hilbert function). Hilbert function is eventually a polynomial (proof -- just a sketch). [KMS 5.6-7]