Разбиения. Семинар 1

Пусть $p(n)$ — число разбиений, т.е. количество способов представить натуральное число $n$ в виде суммы неупорядоченных натуральных слагаемых. Несмотря на простоту определения, эта последовательность: $1, 1, 2, 3, 5, 7, 11, 15...$ — оказывается весьма загадочной. Так, явную замкнутую формулу для $p(n)$ написать не удается — получается только выписать производящую функцию. Зато из нее можно получить рекуррентное соотношение для $p(n)$ — это утверждает знаменитая пентагональная теорема Эйлера.

Мы начнем с того, что обсудим эту теорему, разные способы ее доказательства и некоторые ее обобщения — тройное тождество Якоби и тождества Роджерса-Рамануджана. Далее мы поговорим про теоретико-числовые свойства функции $p(n)$. Например, Рамануджан заметил, что $p(5k+4)$ всегда делится на $5$. Это само по себе загадочное утверждение также оказывается первым в серии утверждений подобного рода.

Наконец, если останется время, мы поговорим про асимптотику последовательности $p(n)$ при больших n. Теорема, принадлежащая Рамануждану и Харди, утверждает, что
$$ p(n)\sim \dfrac{1}{4 n \sqrt{3}} \exp\left( \pi \sqrt{\dfrac{2n}{3}} \right). $$


Этот результат технически очень сложен и требует тонкого применения комплексно-аналитических методов; в 1942 году Эрдёш получил его «элементарное» (т.е. не использующее этих методов — но при этом совсем непростое!) доказательство. Если получится, мы докажем более слабую версию этой теоремы: покажем, что $\log p(n)$ растет как $O(\sqrt n)$.