# Analytická a kombinatorická teorie čísel (Analytic and Combinatorial Number Theory) NDMI045, LS 2017/18

Místo a čas přednášky (place and time of the lecture): Monday 15:40 - 17:10, lecture room K358MUUK in Karlín building.
Výuka tohoto předmětu v minulých letech (past lectures): zde .
Plán letošní přednášky (plan of the course). 1st part. I begin with my favorite Dirichlet's theorem on primes in arithmetic progression. 2nd part. Something on integer partitions, for example Rogers-Ramanujan identities. 3rd part. Something from results of J. Beck on applications of Fourier analysis to kinetic theory of gases (see this or this or this article).
Exam: 1. Give general overview (without going into details) of the proof of Dirichlet's theorem on primes in arithmetic progression. 2. Prove Schur's asymptotics for the restricted partition function p_A(n). 3. Prove an upper bound on the partition function, of the form  p(n) <= e^{cn^{1/2}}(either by induction or by Euler's generating function).

lecture 1, February 27, 2018. I started with the proof that for every integer m > 0 there are infinitely many primes of the form 1 + mn; it is based on cyclotomic polynomials. See my lecture notes from the last year.

lecture 2, March 5, 2018. Proof of the lemma that every cyclotomic polynomial has integral coefficients. Dirichlet's theorem on primes in arithmetic progression. Theorem 8 - Proposition 13 from my lecture notes from the last year.

lecture 3, March 12, 2018. Proposition 14 (proof postponed) - proof of Proposition 20 (proofs of Lemmas 21 and 22 postponed to the next lecture) from my lecture notes from the last year.

lecture 4, March 19, 2018. Proposition 23 - Proposition 26 (but I skipped the proof of Proposition 25) from my lecture notes from the last year.

lecture 5, March 26, 2018. Finishing the proof of Dirichlet's theorem. Next we start with Partitions of integers.

April 2, 2018. Easter Monday.

lecture 6, April 9, 2018. General remarks on compositions and partitions of a natural number n (the former are ordered, the latter are not). Formulas  for numbers of compositions: 2^{n-1}(total number) and B(n-1, k-1) (with k parts). Efficient computation of p(n) (the number of partitions of n) by recurrence: p(n) = p_1(n) + p_2(n) + ... + p_n(n), p_k(n) = p_{k-1}(n-1) + p_k(n-k), p_1(n) = p_n(n) = 1, p_k(n) = 0 for n < k (here p_k(n) counts partitions of n with k parts). Let p_A(n) be the number of partitions of n with parts in a finite set (of natural numbers) A. Theorem (Bell, 1943): p_A(n) is a (rational) quasipolynomial in n, with period equal to a common multiple of the numbers in A. Proof after the preprint of Robins and Vignat.

lecture 7, April 16, 2018. Schur's asymptotics for p_A(n), by partial fractions decomposition of the GF for the numbers p_A(n). An upper bound p(n) <= e^{cn^{1/2}}, c = pi(2/3)^{1/2}, by induction on n. It is all in Theorem 29 - Proposition 33 (the 2nd proof) of my lecture notes from the last year.

lecture 8, April 23, 2018. An upper bound p(n) < pi.e^{cn^{1/2}}/(6(n-1))^{1/2}, c = pi(2/3)^{1/2}, by generating function. See  Proposition 33 (the 1st proof) of my lecture notes from the last year. The Rogers--Ramanujan--Schur identities: the number of partitions of n in parts that are 1 or 4 (resp. 2 and 3) modulo 5 is the same as the number of partitions of n in parts differing by at least 2 (resp. in parts differing by at least 2 and no part 1) - see my lecture notes in Czech from 16 years ago (yes...), beginning of the proof.

lecture 9, April 30, 2018. Proof of  the Rogers--Ramanujan--Schur identities (Věta 227 in my lecture notes in Czech).

lecture 10, May 7, 2018. I stated Theorem 4 from this Beck's article. It says: Let A be any Lebesgue measurable subset of the unit square I^2, then for all ep > 0 and all T > 100 the measure M of the set

{ (y, alpha) in I^2 times S_2} |  |m({ t in [0, T] | x(t) in A }) - T.mju(A)| < (10/ep)sqrt{mju(A)(1 - mju(A))}sqrt{log_2T}log_2log_2T }

is greater than 1 - ep. Here M(.) is the normed product measure on the space I^2 times S_2 of initial conditions of the billiard ball, S_2 is the unit circle, m(.) is the 1-dimensional L. measure (it measures the time the ball spends in A), mju(.) is the 2-dimensional L. measure (it measures the area of  the test set A), and x(t) = (y_1 + alpha_1.t, y_2 + alpha_2.t) (mod 1) is the billiard ball trajectory ( y = (y_1, y_2) is the starting point and alpha = (alpha_1, alpha_2) is the starting direction of the ball that moves with unit speed ) in the unit square. This theorem I will attempt to prove. I also stated Theorem 2 but did not have time to state Theorem 1. It would take maybe 1 hour to copy all these theorems on the blackboard.

lecture 11, May 14, 2018. Something less than 1/2 of the proof of Theorem 4, in Beck's paper it takes about 7 pages which is a rather short proof by his standards, mainly Lemma 6.1 and statement of Lemma 6.2.

lecture 12, May 21, 2018. The rest of the proof of Theorem 4: conclusion and then overview of the proof Lemma 2. Here are the relevant parts of Beck's paper, few initial pages (statement of Theorem 1), statement of Theorem 4 and its proof (a short detour in the much longer proof of Theorem 1).

May 2018