Математические байки

Скажем, вот такой пример приводят Эрдёш, Рубин и Тэйлор в своей статье: возьмём 6 вершин, соответствующих графу карты, которую образуют клетки прямоугольника 2x3 — этот граф очевидно, двудольный, их можно раскрасить «шахматным» образом. Так что хроматическое число такого графа равно 2.

Но этот граф не является 2-выбираемым! Действительно, сопоставим каждой из двух клеток центрального столбца наборы {1,2}, так что при правильной раскраске одна из них должна быть раскрашена в цвет 1, а другая в цвет 2.
Теперь пусть в левом столбце верхней клетке соответствует набор {1,3}, нижней {2,3}, а в правом — наоборот. Тогда левый столбец нам помешает раскрасить центральный как « 1 над 2 » (потому что тогда для обеих клеток левого останется только цвет 3), а правый — помешает « 2 над 1 » (потому что тогда такая же проблема будет в правом).

Image credit: P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference in Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer. XXVI, p. 125-157, Utilitas Math., Winnipeg, Man., 1980.

Про формулу Лефшеца у меня в планах ещё два рассказа, но пока я их пишу — напишу чуть-чуть про другое.

Вот есть проблема 4 красок. Ну и наверное, все знают, что она решена, и решена с заметным применением компьютера для перебора вариантов.

А что, если поменять формулировку вопроса? Раньше у картографа был один набор из 4 цветов, и он пытается раскрасить все страны в эти цвета так, чтобы не было соседних стран, раскрашенных одним цветом.

Представим себе, что сначала картограф спрашивает у каждой страны набор из k цветов, которые эту страну устраивают. А то раскрасишь тут Тридевятое королевство в оранжевый цвет, а король возмутится, что это-де цвет любимой виверны кого-то из его родственников, которая у него все пряники как-то раз сожрала. И всё, несдобровать картографу.

Так что лучше уж опросить королей и королев заранее — а потом бедный картограф попытается раскрасить карту так, чтобы каждая страна была окрашена в один из выбранных ею цветов, и опять же, чтобы соседние страны не были окрашены одинаково.

Ну и вопрос тот же самый — какое число вариантов цветов k нужно спрашивать картографу, чтобы уж точно получилось раскрасить карту?

Собственно, совершенно необязательно работать именно с картой — такой же вопрос можно задать про любой граф. А именно:

Определение. Граф называется k-выбираемым (k-choosable), если для любого способа сопоставить каждой его вершине набор из k «разрешённых» цветов его вершины можно раскрасить так, чтобы каждая вершина была раскрашена в один из соответствующих цветов, и соседние вершины были бы раскрашены в разные цвета.

Рассматривать такие вопросы предложили в конце 1970-ых Визинг и Эрдёш, Рубин и Тэйлор; см. P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs и В. Г. Визинг, Раскраска вершин графа в предписанные цвета, 1976.

На первый взгляд (особенно, если начинать с задачи четырёх красках) может показаться, что это лишнее усложнение: ведь если наборы цветов в разных вершинах разные, казалось бы, раскрасить будет даже проще? Не будет ли наихудшей ситуацией, если списки цветов во всех вершинах просто одинаковы (ну и тогда наименьшее k будет просто хроматическим числом графа)?

Но оказывается, что нет — наименьшее k может быть (сильно) больше хроматического числа!

https://www.shawprize.org/laureates/2024-mathematical-sciences/

The Shaw Prize in Mathematical Sciences 2024 is awarded to Peter Sarnak, Gopal Prasad Professor, School of Mathematics, Institute for Advanced Study and Eugene Higgins Professor of Mathematics, Princeton University, USA, for his development of the arithmetic theory of thin groups and the affine sieve, by bringing together number theory, analysis, combinatorics, dynamics, geometry and spectral theory.

О, и есть запись: https://www.youtube.com/watch?v=XicGYyhC9CQ

А ещё я хочу воспользоваться этим случаем, чтобы посыпать голову пеплом. Все эти годы, когда я хотел найти что-то конкретное из вышедшего в Квантике, я просто пытался гуглить — а если знал год, то переходил по ссылке «Архив» на их главной странице. Что было совсем не всегда удобно.
И все эти годы, на самом виду, там висела ссылка на рубрикатор! По которой я почему-то скользил взглядом… и не пытался посмотреть, «а что там?».

То есть, если хочется перечитать (отличный!) цикл статей Валерии Сироты про экскурсию по Солнечной системе, или найти рассказ Ивана Высоцкого про количество блюд из курицы и рыбы на борту самолёта (1 + 2, применение центральной предельной теоремы, если говорить на языке высокой науки!) — это делается в пару кликов. Кстати, я заодно обнаружил, что в цикле-экскурсии есть и статья про Землю, Луну и приливы — которую я почему-то тогда пропустил.
В общем — пользуйтесь!

В пятницу 17 мая в 19:00 мск мы побеседуем в прямом эфире с Сергеем Александровичем Дориченко!

Сергей Александрович является председателем жюри международной олимпиады «Турнир городов», преподавателем математики 179-й школы, создателем журнала «Квантик» и потрясающим популяризатором математики. Мы уверены, что разговор будет интересный 🙂

Узнаем у Сергея Александровича:
— как заинтересовать ребёнка математикой,
— откуда ежегодно на «Турнире городов» так много классных задач, а на «Летней конференции Турнира городов» — так много классных проектов,
— тяжело ли работать в редколлегии журнала «Квант»,
— как в 2011-м году родилась идея создать журнал «Квантик» и как он развился за эти 13 лет,
— действительно ли математика похожа на музыку,
— важно ли интересоваться не только математикой и быть разносторонним человеком,
— и многое другое.

Ссылка на эфир появится в нашем канале в пятницу. Оставляйте в комментариях под этим постом интересующие Вас вопросы!

Подписаться на «Математические кружки»

#мт_интервью

Ответ на этот вопрос даёт формула Лефшеца.

Выглядит она так. Раз отображение f действует на многообразии M — оно действует и на всех k-мерных гомологиях
H_k(M,\R)
(которые мы будем рассматривать с вещественными коэффициентами, так что это векторное пространство).

Слово «гомологии» заслуживает отдельного комментария, но если вы с ними не сталкивались — давайте временно ограничимся тем, что это какие-то векторные пространства, сопоставленные многообразию, и измеряющие, насколько в нём есть что-то нетривиальное «в размерности k». Например, у сферы с g ручками нуль-мерные гомологии это одномерное пространство (порождённое «точкой»), двумерные гомологии это тоже одномерное пространство (порождённое «всей поверхностью»), а вот одномерные гомологии это пространство размерности 2g (порождённые обходами «вдоль» и «поперёк» каждой из ручек — или, что то же самое, «параллелями» и «меридианами» каждого из g торов, как связную сумму которых можно представить поверхность).

Так вот — отображение f действует на каждом из пространств k-мерных гомологий как линейное преобразование. А с линейным преобразованием много чего связано — в частности, можно рассмотреть след
tr (f_* , H_k(M,\R))

Давайте посмотрим на знакопеременную сумму таких следов. Оказывается, это и есть ответ!

Теорема (формула Лефшеца).
\sum_{f(p)=p} ind_f(p) = \sum_{k=0}^n tr(f_* , H_k(M,\R)).

То есть — сумма индексов неподвижных точек отображения определяется тем, как именно оно «перекручивает» многообразие. Красиво, правда?

Пример. Возьмём векторное поле v и «проедем» вдоль него небольшое время t_0 — получив диффеоморфизм f. Его неподвижные точки это в точности особые точки v (если время было достаточно малым, чтобы ни одну периодическую орбиту мы не успели полностью проехать). И индексы у них для отображения и для векторного поля одни и те же. Так что по теореме Пуанкаре–Хопфа сумма их индексов равна эйлеровой характеристике.

С другой стороны, заметим, что f гомотопно тождественному отображению (что f в тождественное отображение «можно перетянуть»). Действительно, достаточно рассмотреть семейство сдвигов вдоль того же векторного поля v за разные времена t. При t=0 это тождественное отображение, а при t=t_0 — наше f. Вот мы непрерывно и перетянули f в id.

А гомотопные отображения одинаково действуют на гомологиях. Так что для такого f его действие на каждых гомологиях просто тождественно, и значит, каждый след это просто размерность соответствующего пространства гомологий. А знакопеременная сумма размерностей пространств гомологий действительно равна эйлеровой характеристике!

P.S. Несколько ссылок про гомологии:
- курс В. А. Васильева «Гомологии, наборы плоскостей и формула включений-исключений» в ЛШСМ-2011: https://www.mathnet.ru/present3568
- книга В. В. Прасолова «Элементы теории гомологий», МЦНМО, 2006 https://old.mccme.ru/free-books/prasolov/homol.pdf
- курс Г. Ю. Паниной в ЛШСМ-2023: https://old.mccme.ru//dubna//2023/courses/panina.html

Warning/disclaimer: уровень сложности начинает повышаться.

Итак, для векторных полей на (замкнутых ориентированных) многообразиях сумма индексов особых точек всегда равна эйлеровой характеристике. А нельзя ли что-то подобное сделать для отображений?

Пусть у нас есть отображение f:M->M, и у него есть изолированная неподвижная точка p. Тогда рядом с ней можно взять локальные координаты (карту) и рассмотреть векторное поле v_f, «соединяющее» каждую точку x с f(x). У этого поля p будет изолированной особой точкой => можно рассмотреть его индекс.

Определение. Индекс изолированной неподвижной точки p для отображения f — это её индекс для этого векторного поля v_f:
ind_f (p) := ind_{v_f}(p).

Несложно убедиться, что это определение корректно — если мы используем другую карту, индекс будет тем же самым.

Но у нас уже нет глобального векторного поля: если x и f(x) «далеко» друг от друга, то неясно, как именно их соединять. Скажем, если мы на торе — обходить ли «по» или «против» меридиана?

Так что сумма индексов неподвижных точек отображения f уже не обязана быть равна эйлеровой характеристике. А чему она будет равна?

(Построение векторного поля по триангуляции поверхности)

Продолжим?

Представим себе, что у нас векторное поле v задано не на плоскости, а на какой-то ориентированной поверхности S — сфере, торе, кренделе, и т. д. То есть нам дана поверхность S, и в каждой точке p\in S задан вектор v(p), касательный к S в этой точке. Если брать аналогию с векторным полем как набором скоростей ветра — то ветер не дует ни вверх, ни вниз, а в каждой точке по касательной к Земле в этой точке.

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

Так вот, есть такое замечательное утверждение:

Предложение. Сумма индексов особых точек векторного поля на S, у которого особых точек конечное число — от выбора такого поля не зависит.
Набросок доказательства. Если деформировать поля друг в друга, оставаясь в классе полей с изолированными особыми точками, то сумма остаётся постоянной в процессе деформации. Действительно, в любой момент разрежем поверхность на маленькие кусочки, границы которых в текущий момент не проходят через особые точки поля. Тогда, в силу теоремы о сумме индексов, вся сумма равна сумме индексов по границам кусочков (закрываемых картами, содержащими кусочки целиком). А каждый из таких индексов при малом возмущении не меняется. Так что сумма индексов — локально-постоянная функция; а значит, она и просто константа.

Остаётся убедиться, что любые два поля перетаскиваются одно в другое. Ну и для этого можно сначала соединить любые два векторных поля u и v просто отрезком
u_t(p)=t*u(p) + (1-t)*v(p), t\in [0,1].
А потом, если этот путь от u_0=u к u_1=v не работает (в какой-то момент t у поля u_t есть неизолированные особые точки), возмутить его, заменив на близкий, но «типичный»: наличие неизолированной особой точки это очень, очень сильное вырождение.

А чему равна эта сумма? Ответ очень красивый:

Теорема Пуанкаре-Хопфа. Сумма индексов особых точек векторного поля с изолированными особыми точками на замкнутом ориентированном многообразии M равна эйлеровой характеристике многообразия χ(M).

(Она справедлива для любой размерности M, но у нас пока что индекс точки определён только для поверхности, так что давайте я пока продолжу, как будто M это поверхность.)

Доказательство. Мы уже убедились, что сумма не зависит от выбора поля. Остаётся построить поле, у которого ответ будет точно равен χ(M). Давайте триангулируем M и возьмём поле, у которого особые точки — по одному источнику в центре каждого треугольника, по седловой точке в середине каждого ребра, и по стоку в каждой вершине триангуляции (см. рис. ниже).
Индексы источника и стока равны по +1, у седловой точки он (-1), так что сумма индексов как раз и будет равна эйлеровой характеристике,
В-Р+Г= χ(M).

Собственно, мы только что доказали теорему о причёсывании ежа: эйлерова характеристика сферы равна 2 (классическая формула Эйлера для многогранников, В-Р+Г=2 !), так что сумма индексов особых точек должна быть равна 2. И значит, хотя бы одна особая точка должна быть (сумма пустого множества равна 0).

Ещё одно применение логики деформации — это
Теорема о даме с собачкой: если для двух векторных полей u, v в любой точек кривой γ выполнено |u(x)|>|v(x)|, то
ind_γ u = ind_γ (u+v).

Действительно, соединим поля u и u+v путём u_t=u+tv, где «время» t\in [0,1]. Ни в какой момент на γ нет особых точек u_t (ибо |u|>|v|), так что индекс при деформации не меняется. Значит, индексы начального поля u и конечного u+v равны.


Кстати, на этом пути можно доказать основную теорему алгебры. Действительно, комплексный многочлен P(z) тоже можно рассматривать как векторное поле: в точке z\in C = R^2 ставим вектор P(z)\in C = R^2.

Рассмотрим теперь огромную окружность γ_R = { |z|=R }.
На ней старший моном z^n сильно больше, чем все остальные. Значит, можно применить теорему о даме с собачкой: индексы вдоль γ_R полей, задаваемых z^n и полным многочленом P, совпадают.
Но \arg z^n = n \arg z, так что индекс z^n равен n.
Значит, особые точки — корни многочлена P — внутри γ_R есть!

Собственно, индекс особой точки такого поля равен её кратности как нуля P, так что сумма кратностей корней сразу получается равной n.

Вот тут у Г. А. Мерзона выложен листок с задачами про всё это —
см. https://dev.mccme.ru/~merzon/v14/pscache/31d-vector_fields.pdf

Пусть теперь у векторного поля в какой-то области D все особые точки изолированные. Посмотрим на его индекс вдоль границы \gamma=∂D этой области.

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

Теорема. Индекс векторного поля по [положительно ориентированной] границе области равен сумме индексов его особых точек в этой области,
ind_{∂D} v = \sum_{p: v(p)=0} ind_p v.

А раз индекс — целое число, то к нему применим общий топологический принцип: «пока целое число меняется непрерывно — оно остаётся постоянным».

Поэтому, если непрерывно менять \gamma и v — так, чтобы ни в какой момент на \gamma не попадали особые точки v — то индекс меняться не будет.

В частности, у каждой изолированной особой точки p этого поля тоже есть индекс
\ind_p v:
это индекс векторного поля при обходе вокруг особой точки по маленькой окружности в положительном направлении. И поскольку такие обходы можно продеформировать друг в друга, не задевая других особых точек v (на то и условие малости и изолированности), индекс от выбора маленькой окружности обхода не зависит.

Давайте я (для начала) вспомню совсем классический сюжет: векторые поля на плоскости, их особые точки и индексы.

Пусть задано какое-то векторное поле v на плоскости: в каждой её точке x\in R^2 непрерывным образом выбран вектор v(x)\in R^2.

Пусть у нас есть замкнутая ориентированная кривая \gamma, не проходящая через нули поля v — их называют особыми точками. Тогда мы можем определить индекс векторного поля v вдоль этой кривой,
ind_\gamma (v).
А именно: пойдём вдоль \gamma и будем смотреть, сколько оборотов (с учётом знака) сделает вектор v(.) к моменту, когда мы пройдём всю кривую и вернёмся в исходную точку.

Можно себе представить, что векторное поле v показывает, как в этой области дует ветер, а мы ходим по нашему любимому маршруту \gamma с флюгером и смотрим, сколько оборотов он сделает. Важно, что это — целое число: при обходе мы вернулись в исходную точку, значит, вектор вернулся в исходное положение.

Упражнение: найдите индекс векторного поля вдоль синей кривой на картинке.
Ответ: 2.

К сегодняшней лекции Нины Зубрилиной — давайте я напишу пару слов про эллиптические кривые.

Пусть на плоскости нарисована кривая, задаваемая уравнением третьей степени, F(x,y)=0. И пусть эта кривая гладкая: без особых точек, как у «клюва»
y^2=x^3,
или точек самопересечения, как у
y^2=x^2(x+1).
Будем называть такую кривую эллиптической. Точнее, лучше рассматривать её не на обычной плоскости, а на проективной — добавив к ней точки на бесконечности.

На эллиптической кривой есть точки перегиба; если унести одну из них проективным преобразованием на бесконечность, переведя её в точку [0:1:0], а касательную в бесконечно удалённую прямую, то в уравнении из мономов степени 3 останется только x^3. После этого уже несложно (выделяя квадрат) перевести кривую в кривую вида
y^2= P(x),
где P — многочлен третьей степени, а потом и вида
y^2= x^3 + Ax+ B. (*)
Условие гладкости кривой превращается в отсутствие у P кратных корней — то есть в то, что его дискриминант ненулевой (да, дискриминант есть не только у квадратного уравнения!):
4A^3 + 27B^2 \neq 0.

Собственно, при первом знакомстве можно вообще взять (*) за определение [вообще-то, для замен выше нужно, чтобы характеристика поля была отлична от 2 и 3; но это можно пока замести под ковёр].

Я уже писал про эллиптические кривые несколько лет назад — см. тут и ниже. Первое, и самое основное — что точки на эллиптической кривой можно складывать, что они образуют коммутативную группу(!). И правило сложения очень простое: сумма трёх точек, лежащих на одной прямой, равна нулю. Как только ноль выбран — правильнее всего взять точку на бесконечности — сумма двух точек выглядит так: проводя прямую через две точки P и Q, мы находим третью точку пересечения -(P+Q); после этого, проведя прямую через эту точку и 0, находим третью точку пересечения — искомую сумму P+Q.

См. тут + брошюру Цфасмана и Острика (которую я очень люблю) https://www.mccme.ru/mmmf-lectures/books/#book-8 + статью Н. Васильева в Кванте http://kvant.mccme.ru/1987/08/geksagrammy_paskalya_i_kubiche.htm

Если у эллиптической кривой целые коэффициенты — то можно то же самое уравнение рассмотреть «по модулю p», получив эллиптическую кривую над полем F_p из p элементов. И тут оказывается, что это не только очень красивая геометрия, но и [около]прикладная вещь тоже — есть не только реализация протокола Диффи-Хеллмана обмена ключами через эллиптические кривые, но и алгоритм Ленстры разложения больших чисел на множители (я помню, как меня эта идея в своё время поразила: до того момента я наивно считал, что можно только делить, делить и делить, а тут — какая-то магия рациональных вычислений по модулю N, и вдруг из неё выпадает делитель!).

А ещё — доказательство теоремы Ферма тоже основано на эллиптических кривых!
В общем — эллиптические кривые это очень, очень важный и красивый объект, и с ними точно стоит познакомиться.

Лекция про мурмурации эллиптических кривых уже завтра, 19:00 МСК!

🌼Речь пойдет о недавно открытом и активно исследуемом феномене в теории чисел. Хочется поподробнее написать, о чем это и для кого. Я не специалист и, хоть и консультировался с Ниной, мог что-то напутать)

⭐️Самый главный параметр эллиптической кривой — ее ранг. Для вычисления ранга по коэффициентам нету общего алгоритма. Кстати, с этим связана одна из проблем тысячелетия — гипотеза Бёрча — Свиннертон-Дайера.

🔥 Во время Ковида математики He, Lee, Oliver, Pozdnyakov обработали базу из трёх миллионов эллиптических кривых, для которых ранг уже известен, методами анализа данных.

✨ Так нашли корреляции, визуально напоминающие мурмурации — синхронные движения скворцов или других птиц. Вот препринт 22 года.

🌿 Пришло время математического осмысления этой закономерности. Ключевой результат получен в прошлогодней статье Нины, ставшей основой ее диссертации.

📖 Лекция начнётся со введения в эллиптические кривые и модулярные формы. Это будет ликбез, доступный студенту или смелому школьнику. Нет цели все объяснить — это краткий обзор/напоминание про эти объекты.

НАЧАЛО завтра в 19:00 МСК. Ссылка на зум.

До встречи завтра!
PS. Нина защитилась в Принстоне в эту среду. Поздравляем!!!

#анонс #открытые_лекции #день_женщин

https://youtu.be/QNznD9hMEh0

большое видеоинтервью Саймонса

https://www.simonsfoundation.org/2024/05/10/simons-foundation-co-founder-mathematician-and-investor-jim-simons-dies-at-86/

Jim Simons (25.04.1938–10.05.2024)

«Jim (as he preferred to be called) was an award-winning mathematician, a legend in quantitative investing, and an inspired and generous philanthropist…»