Вычислимая функция f:N→N называется доказуемо рекурсивной в данной формальной теории T, если существует алгоритм её вычисления такой, что в T можно доказать утверждение «для любого x существует y такой, что f(x)=y». В математической логике такие функции изучаются по двум причинам. Во-первых, для данной программы нас часто интересует доказательство её корректности, в частности вопрос о том, завершает ли она работу при любых исходных данных. С другой стороны, варьируя функцию f мы можем ставить для теории T сколь угодно сложные (вплоть до невыполнимости) задачи на доказательство. Тем самым, доказуемо рекурсивные функции могут быть использованы для изучения различных формальных теорий. Такой подход приводит к наиболее впечатляющим на сегодняшний день примерам недоказуемых комбинаторных утверждений. Мы начнем с понятия машины Тьюринга и вычислимой функции. Разберемся, как формальная арифметика может говорить о вычислениях. Поймем, что для любых разумных систем аксиом T их запас доказуемо рекурсивных функций никак не может исчерпывать все вычислимые всюду определенные функции. Отсюда выведем первую теорему Гёделя о неполноте.

Если представлять себе выдающиеся произведения научной литературы как горные маршруты, уводящие в небо, то наш небольшой курс — не более чем прогулка с видом на далекие белоснежные вершины. Мы собираемся просмотреть видимые начала одного из красивейших маршрутов, уводящего далеко за облака, к высоким перевалам и вершинам классической механики. Очень скоро вчерашние школьники сами выйдут на этот маршрут, а пока… давайте немного потренируемся.

Я приведу два весьма важных с прикладной точки зрения примера задач, которые тесно связаны с фундаментальными теоретическими вопросами. 1. Равномерное распределение точек в многомерном единичном кубе. Как понимать «равномерное»? Существует несколько подходов. Подход, который мы обсудим в деталях, ведет к понятию дискрепанса. Оказывается, что это понятие тесно связано с численным интегрированием функции многих переменных. 2. Экономное представление функций. В реальной жизни многие сигналы могут быть приближенно представлены в виде линейной комбинации небольшого числа базисных функций. Например, это относится к музыке, где можно использовать тригонометрическую систему в качестве источника базисных функций. Такие представления называются «разреженными». Возникает естественный вопрос. Как строить разреженные приближения?

Общая постановка такова. Пусть P(x_1,…,x_n) — некоммутативный многочлен от матриц порядка n. Каким может быть множество его значений? И. Капланский и И. В. Львов поставили вопрос о том, что множество значений полилинейного многочлена есть векторное пространство (в этом случае оно совпадает либо с нулем, либо с пространством всех матриц, либо с пространством бесследовых матриц, либо со скалярными матрицами). Решение проблемы Капланского для матриц второго порядка над квадратично замкнутым полем оказалось весьма нетривиальным и глубоким. Вопросы, связанные с уравнениями в матрицах, помимо прикладного значения имеют отношение к конструкции алгебраически замкнутого тела, к теореме о свободе: если добавить новую некоммутативную переменную и соотношение, где та участвует, то это не приведет к появлению новых соотношений. Имеется ряд глубоких проблем, относящихся к множеству значений слов в группе — в частности, в матрицах второго порядка.

Рассматривается дискретный аналог броуновского движения. Именно свойства этого блуждания являются целью лекций с последующим переходом к броуновскому движению (винеровскому процессу). Применяя вероятностный подход мы вводим прежде всего основные характеристики: вероятностное пространство (Ω,F,P), случайные величины, математические ожидания и др. Далее рассматриваются фундаментальные свойства случайных блужданий: закон больших чисел, теорема Муавра-Лапласа, усиленный закон больших чисел, закон повторного логарифма и др. На примерах будет показано как вероятностная комбинаторика и свойства случайных блужданий приводят к результатам, слабо поддающихся интуиции.

Приставляя тетраэдры друг к другу по граням можно получать примеры симплициальных комплексов — важного математического объекта. Раскрасим треугольники такого сооружения в чёрный и белый цвета и назовём раскраску хорошей, если каждый тетраэдр имеет поровну чёрных и белых граней. Оказывается, что в случае (стандартно симплициально разбитых) маломерных сфер множество белых треугольников оказывается объектом, достойным изучения: листом Мёбиуса или проективной плоскостью. При описании того, как именно эти объекты разбиты на треугольники у нас естественным образом возникнет икосаэдр — замечательный правильный многогранник. Исследование группы его самосовмещений позволит понять, сколько существует хороших раскрасок. По пути нам встретятся такие важные базовые понятия математики, как вышеупомянутые симплициальный комплекс и группа симметрий, действие и пр.

В этом курсе изучается такой замечательный и вполне элементарный объект, как конечномерные коммутативные ассоциативные алгебры над комплексными числами. Здесь достаточно легко доказать первые структурные результаты, но получить полную классификацию едва ли возможно. Мы обсудим различные техники работы с конечномерными алгебрами (максимальные идеалы и локальные алгебры, фильтрации и градуировки, последовательность Гильберта-Самюэля и цоколь) и получим явное описание алгебр малых размерностей. Оказывается, конечномерные алгебры тесно связаны с действиями с открытой орбитой коммутативных групп матриц на аффинных и проективных пространствах. Мы объясним эту связь. В процессе объяснения естественно возникнут такие понятия как экспонента линейного оператора, представление группы и циклический модуль, алгебра Ли и ее универсальная обертывающая.

Целью этого элементарного курса, рассчитанного на школьников, является познакомить слушателей с некоторыми основными и очень красивыми идеями современной абстрактной алгебры. Начиная с элементарных примеров, мы введем понятия группы, кольца, и поля, и заодно посмотрим на некоторые неожиданные свойства простых уравнений в кольцах. После этого мы рассмотрим разные примеры групп, таких как группы симметрий правильных многоугольников и многогранников, или группы перестановок. Мы увидим как можно записать операцию в группе с помощью таблиц Кэли, и посмотрим на более наглядное представление структуры группы с помощью диаграмм Кэли. Мы также рассмотрим примеры действия групп и связанные с этим понятия, а также некоторые красивые приложения (такие как счетная лемма Бернсайда).

Теория игр — наука, изучающая принятие решений, особенно принятие решений в условиях зависимости достигаемого результата от действий других участников процесса. При этом «счастье для всех, даром и пусть никто не уйдёт обиженным» как правило невозможно по правилам — хотя ещё обиднее, когда оно возможно, но заведомо не случится. Изучаются же в каком-то смысле «достижимые» и «устойчивые» ситуации — так называемые равновесия. В интересующих нас играх часто можно выписать все сценарии развития событий, но после этого всё равно ещё остаются вопросы. С этой точки зрения шахматы одновременно слишком сложны — много позиций — и слишком просты — полный перебор сразу определил бы оптимальную стратегию для каждой позиций. Так как курс не построен вокруг одного понятия или утверждения, по пожеланиям слушателей возможны значительные изменения программы.

В этом курсе мы познакомимся с замечательной теорией NP-полных задач. Проблема (не)равенства классов P и NP — одна из «задач тысячелетия», за каждую из которых объявлен приз в миллион долларов. Мы разберемся в определении класса NP и научимся доказывать NP-полноту различных комбинаторных задач (классические теоремы Кука–Левина и Карпа). Особое внимание уделим задаче выполнимости булевых формул SAT. Мы поиграем с программами, решающими эту задачу, разберем какие алгоритмы они используют, как результатом их работы может быть доказательство, допускающее автоматическую проверку. Научимся сводить логические головоломки и математические задачи к SAT, поговорим о судоку, задачах теории Рамсея, недавнем продвижении в задаче о хроматическом числе плоскости и о «самом большом математическом доказательстве».

В первой половине лекции мы обсудим наблюдаемые, дающие представление о составе и истории развития Вселенной и познакомимся со Стандартной космологической моделью. Вторая половина лекции будет посвящена обсуждению разных аномалий и нестыковок при попытках дальнейшего уточнения физических параметров, с чем пришлось столкнуться в последние годы. Означает ли это, что мы подошли к следующей ступени понимания физики и космологии, или это рубеж, определяемый систематическими погрешностями используемых экспериментальных методов, пока неизвестно. Я постараюсь показать, какие математические задачи возникают в космологии.

Я постараюсь объяснить базисные проблемы и идеи гомологической алгебры и современную их интерпретацию с помощью производных категорий. Затем расскажу как надо думать об алгебраических многообразиях, чтобы применять методы гомологической алгебры и теории категорий к алгебраической геометрии. В качестве примера, объясню как можно описывать расслоения на проективных пространствах с помощью разбиений вещественного тора.

Рассмотрим квадратичную форму Q от двух переменных с целыми коэффициентами и зададимся вопросом, какие значения она может принимать на целочисленной решетке. В частном случае стандартной евклидовой формы это классический вопрос о том, когда заданное натуральное число представляется как сумма двух квадратов, исследованный Гауссом. Около 20 лет назад английский математик Джон Конвей предложил геометрический подход к этому вопросу, используя плоское бинарное дерево. Получаемое описание называется топографом формы. В случае когда форма принимает как положительные, так и отрицательные значения, они разделяются бесконечным путем на этом дереве, называемым рекой Конвея. Я расскажу, как река Конвея связана с парусом Арнольда из геометрической теории цепных дробей на целочисленной решетке, восходящей к Клейну.

Классическая теорема Бойяи–Гервина (1830-е годы) утверждает, что любые два многоугольника равной площади равносоставлены друг с другом: первый многоугольник можно разрезать на конечное число многоугольных частей и затем сложить из этих частей второй многоугольник. Ещё Гаусс задавал вопрос, верно ли аналогичное утверждение для многогранников. А именно, его интересовало, можно ли доказать стандартную формулу для объёма пирамиды (одна треть произведения длины высоты на площадь основания) без использования предельного перехода, то есть разбив пирамиду на конечное число кусков, из которых можно сложить прямоугольный параллелепипед.

Если у (обычного плоского) квадрата склеить противолежащие стороны, то получится тор с плоской метрикой, то есть каждый достаточно малый участок тора будет устроен как кусочек евклидовой плоскости. Если квадрат заменить на прямоугольник или параллелограмм, аналогичная склейка тоже даст тор с плоской метрикой, но про него разумно сказать — это другой тор, не изометричный первому. Здесь история о поверхностях с плоской метрикой заканчивается, так как никакую другую поверхность (с плоской метрикой) кроме этих торов из куска евклидовой плоскости склеить нельзя. Поэтому мы евклидову плоскость заменим на плоскость Лобачевского (с ней больше свободы!) и определим пространство Тейхмюллера как пространство, элементы которого суть все возможные способы склеить поверхность рода g (т.е. сфера с g ручками) из гиперболической развертки, то есть, из некоторого куска гиперболической плоскости.

Иногда мы хотим доказать, что какой-нибудь объект существует. Разумеется, можно медленно и методично объект построить. Но это что-то делать надо, а хочется получить кое-что задаром. Поэтому мы просто возьмём случайный объект и заметим, что он подходит с ненулевой вероятностью. Это позволяет избежать занудной конструкции. Заодно можно спрятать в доказательстве незаметную ошибку. Для понимания курса нужно будет знать определение независимых событий. Понимать, что это такое, не обязательно, всё равно в ходе курса такое понимание (или только его иллюзию?) можно будет утратить.

Пользуясь цифрами 0 и 1, несложно записать натуральное число. Сложение в столбик позволяет прибавить к этому числу единицу. Такой способ записи и изменения числа требует в некоторых ситуациях прочитать и изменить все цифры. А если число большое и мы хотим читать и писать поменьше цифр, но можем быстро запросить любые цифры числа «вразбивку»? Разумеется, придётся изменить представление числа. С середины 20-го века известны коды Грея; нам всё равно потребуется иногда читать число целиком, зато менять надо будет лишь по одной цифре за раз. А можно ли прибавить к числу единицу, не читая всего числа? Оказывается, можно.

Лекцию читает Клепцын Виктор Алексеевич. Летняя школа «Современная математика», г. Дубна. 29 июля 2017 г.

Лекцию читает Веселов Александр Петрович. Летняя школа «Современная математика», г. Дубна. 22 июля 2017 г.

В каждой точке плоскости нарисуем вектор. Получилось векторное поле. Будем считать, что по плоскости течёт вода, а векторы — её скорости течения в разных точках. Теперь бросим в воду несколько щепок и нарисуем траектории их движения. Получится фазовый портрет векторного поля. По картинке стало видно, что происходит со щепками: некоторые приближаются к внешнему предельному циклу, от другого цикла все щепки отдаляются. Куда ещё могут накапливаться траектории щепок (теорема Пуанкаре-Бендиксона). Как ещё могут быть устроены фазовые портреты. Также мы обсудим бифуркации: перестройки фазовых портретов, когда векторное поле слегка меняется. Будут свежие результаты и открытые вопросы.