Зимняя студенческая школа по математике и теоретической информатике. 29 января - 03 февраля 2021 года

П.И. Дунин-Барковский (НИУ ВШЭ): Различные виды чисел Гурвица и их производящие функции

Числа Гурвица изучались с 19-го века. Исходные числа, введенные Адольфом Гурвицем (сейчас их называют "простые числа Гурвица") имеют очень простое комбинаторное определение: число Гурвица соответствует количеству способов представить перестановку данного циклического типа в виде произведения заданного количества транспозиций. Для Гурвица мотивировкой для изучения этих чисел было то, что они возникают в геометрическом контексте как количества разветвленных накрытий двумерной сферы.
Существует много интересных обобщений и модификаций понятия чисел Гурвица, включая двойные числа Гурвица, монотонные и строго монотонные числа Гурвица, числа Буске-Мелу--Шеффера и многие другие. Как выясняется, все эти виды чисел Гурвица приходят из т.н. тау-функций гипергеометрического типа иерархии Кадомцева-Петвиашвили (КП).
В рамках курса будут обсуждены основные определения и свойства различных типов чисел Гурвица (как с чисто комбинаторной, так и с геометрической стороны), с примерами. Затем будет кратко упомянута связь с иерархией КП (для этого от слушателей не потребуется никакого предварительного знания теории интегрируемых иерархий, все необходимые понятия будут объяснены). После этого будут обсуждены интересные свойства производящих функций чисел Гурвица. В частности, оказывается, что для максимально общего вида чисел Гурвица их естественные производящие функции можно представить в виде конечных рациональных выражений от небольшого количества базовых функций.

Комплексные неприводимые представления симметрической группы S_n нумеруются разбиениями числа n (т.е. диаграммами Юнга из n клеток), а размерности этих представлений равны количеству стандартных заполнений соответствующей диаграммы Юнга (т.е. количеству стандартных таблиц такой формы). Согласно общей теореме, сумма квадратов размерностей неприводимых представлений равна порядку группы. Таким образом, множество пар стандартных n-клеточных таблиц Юнга одинаковой формы  и множество всех перестановок n-элементного множества равномощны. Соответствие Робинсона-Шенстеда-Кнута (RSK) - это чисто комбинаторный алгоритм, устанавливающий взаимно-однозначное соответствие между этими множествами. С другой стороны, то же самое соответствие возникает из двух разных способов индексации клеток Шуберта на многообразии полных флагов: при помощи перестановок и при помощи пар стандартных таблиц. Я постараюсь подробно разобрать перечисленные выше сюжеты: 1. описание неприводимых представлений симметрической группы, 2. конструкция биекции RSK и 3. клетки Шуберта на многообразии полных флагов), рассказать как они связаны и (если останется время) что-то сказать об их дальнейших обобщениях. Для понимания требуется хорошее знание линейной алгебры и начальные сведения из теории представлений и алгебраической геометрии.

Д.М. Столяров (СПбГУ) Об изоморфизме некоторых банаховых пространств

Я расскажу два классических, но полу-забытых сюжета из функционального анализа, более точно, из теории банаховых пространств. Первый — это теорема Милютина (1952), которая гласит, что для всяких несчётных метрических компактов $K_1$ и $K_2$ банаховы пространства $C(K_1)$ и $C(K_2)$ изоморфны (то есть, существует линейный гомеоморфизм между ними). Второй — теорема Хенкина (1967) о том, что между пространствами $C^1([0,1]^2)$ и $C([0,1]^2)$ такого изоморфизма нет.

 Параллельные вычисления, еще относительно недавно бывшие узкоспециализированной темой, стремительно входят в мейнстрим современной компьютерной науки. Новый уровень сложности, привносимый параллелизмом в вычислительный процесс, создает потребность в его теоретическом осмыслении. Наряду с временем, затраченным на собственно вычисления, в качестве ограниченных ресурсов при параллельных вычислениях должны рассматриваться также межпроцессорная коммуникация и синхронизация; кроме того, особое значение приобретает эффективное использование памяти и отказоустойчивость. В курсе будут рассмотрены основные существующие модели параллельных вычислений; основное внимание будет уделено модели bulk-synchronous parallelism (BSP), предложенной Лесли Вэлиантом (Leslie Valiant) в 1990 г. Вычислительный процесс BSP представляет из себя последовательность блоков асинхронных локальных вычислений, чередующихся с блоками коммуникации и барьерной синхронизации. Вэлиант доказал, что этот класс параллельных вычислений может быть эффективно реализован при помощи чрезвычайно простого вероятностного алгоритма маршрутизации. При этом данный класс достаточно широк, чтобы служить основой для разработки эффективных параллельных алгоритмов. Мы изучим основные принципы разработки BSP алгоритмов на примере нескольких классических задач: сортировка и выбор порядковой статистики, быстрое преобразование Фурье, ранжирование списка, вычисления на решетке, умножение матриц, решение системы линейных уравнений, сравнение строк, поиск кратчайших путей в графе. Для большинства этих задач возможно наивное распараллеливание вычислений, однако оптимальные решения, с учетом затрат на коммуникацию и синхронизацию, зачастую нетривиальны и поучительны.

Континуум-гипотеза утверждает, что любое бесконечное подмножество вещественных чисел равномощно либо натуральным числам, либо вещественным.  В 1963-м году Коэн показал, что это утверждение не зависимо от стандартной аксиоматики теории множеств ZFC, то есть ни оно, ни его отрицание не могут быть из неё выведены. Пучок на топологическом пространстве X − это локальный гомеоморфизм из некого пространства в X. Категория пучков на пространстве является моделью для теории множеств, поэтому вопросы независимости гипотез можно решать, доказывая утверждения о пучках. Развитие этой идеи позволяет передоказать результат Коэна. В этом курсе планируется разобрать эти идеи и это доказательство и, если останется время, обсудить вкратце теорию типов.