🚀 @SBERLOGASCI webinar on mathematics and data science:
👨‍🔬 Sergei Gukov "What makes math problems hard for reinforcement learning: a case study"
⌚️ 19 September, Thursday 19.00 Moscow time

Add to Google Calendar

Can AI solve hard and interesting research-level math problems? While there is no mathematical definition of what makes a mathematical problem hard or interesting, we can provisionally define such problems as those that are well known to an average professional mathematician and have remained open for N years. The larger the value of N, the harder the problem. Using examples from combinatorial group theory and low-dimensional topology, in this talk I will explain that solving such hard long-standing math problems holds enormous potential for AI algorithm development, providing a natural path toward Artificial General Intelligence (AGI).

The talk is based on a recent paper: https://arxiv.org/abs/2408.15332

О докладчике: Сергей Гуков - профессор КалТех, выпускник МФТИ и Принстона, один из наиболее известных специалистов по теории струн и математической физике, в последние годы занимающийся применением методов Reinforcement Leaning к задачам математики и физики.

Zoom link will be in @sberlogabig just before start. Video records: https://www.youtube.com/c/SciBerloga and in telegram: https://www.group-telegram.com/sberlogasci/19688 - subscribe !

Анонс на твиттер:
https://x.com/sberloga/status/1835702457260765359
Ваши лайки и репосты - очень welcome !

Копия поста из контакта (22 июля 2018 г).
_______________________

Гипотеза Эндрюса-Кёртиса

Допустим, что у нас есть несколько элементов r_1, ...,r_n какой-то группы. Тогда преобразования этого набора
(1) r_i —> r_ir_j для i≠j;
(2) r_i —> r_i^{-1};
(3) r_i —> r_i^g, где g любой элемент;
не меняют нормальную группу, которую порождают эти элементы. Если один такой набор элементов можно получить из другого при помощи преобразований (1)-(3), то мы назовём их эквивалентными. Легко проверить, что при помощи этих преобразований можно получить любую перестановку исходного набора. Поэтому можно добавить перестановку в качестве ещё одного преобразования, а можно не добавлять.

Гипотеза Эндрюса-Кёртиса говорит, что для любого сбалансированного копредставления (т.е. количество порождающих равно количеству соотношений) тривиальной группы
< x_1,...,x_n | r_1,...,r_n >=1
набор элементов r_1,...,r_n эквивалентен "стандартному" набору x_1,...,x_n. Иначе говоря, все такие наборы эквивалентны. Гипотеза открыта. Люди не верят, что она верна. Причём, есть много потенциальных контрпримеров, про которые ничего не удаётся доказать. Даже для n=2.

Гипотеза возникла из топологии, которую я не хочу объяснять. Смотри в их прикреплённой статье 65-ого года.

Компьютерными методами проверено, что для любого копредставления тривиальной группы
<x,y | r,s>=1
такой, что |r|+|s|<13, где модуль обозначает длину слова, гипотеза верна. А в случае |r|+|s|=13 проверили, что любое такое копредставление либо эквивалентно тривиальному, либо копредставлению
<x,y | xyx=yxy, x^4=y^3 >
(Havas,Ramsay'03).
Поэтому это копредставление <x,y | xyx=yxy, x^4=y^3 > сейчас наиболее подозрительно на контрпример.
Более того, это всё посчитали люди в 2003, а потом другие люди обратились к этому копредставлению в 2016 (Panteleev, Ushakov) и тоже не смогли доказать, что оно эквивалентно стандартному.

Доказано (Bridson'15), что при n=4 можно построить последовательность примеров P_k, где сумма длин соотношений будет расти линейно по k, но минимальное количество необходимых элементарных движений к тривиальному будет расти очень быстро, быстрее любых экспонент; больше чем 2^(2^(2^(...^2)...) где количество возведений равно log(k).

Как можно пробовать доказать, что она неверна? Свободная группа слишком сложна. Можно спроектироваться на более понятые группы, в которых уже можно разобраться с тем, какие наборы эквивалентны, посмотреть на проекции потенциальных контрпримеров и показать, что они не эквивалентны стандартному. Какие более-менее понятные группы мы знаем? Первое, что приходит в голову: разрешимые и конечные. Для разрешимых так не получится (Мясников'85), для конечных — тоже (Borovik, Lubotzky,Myasnikov'03). А именно, аналоги гипотезы Эндрюса-Кёртиса верны для разрешимых групп и для конечных групп.

Можно ещё попробовать спроектроваться на группу Григорчука и тоже обломаться: https://arxiv.org/pdf/1304.2668.pdf .

В статье Burns,Macedonska'93 года даётся понятие M-преобразования, которое в какой-то степени заменяет преобразования (1)-(3). Мне не очень важно, что можно использовать только его, мне просто нравится, что его можно использовать. Оно более "крупное" (одно M-преобразование содержит много преобразований типа (1),(3)). И очень интуитивно понятное. Именно про помощи него проще всего доказывать руками, что какие-то примеры эквивалентны стандартному. Вот определение

(M) r_i —> r'_i, где r_i ≡ r'_i mod « r_1,...,r_{i-1},r_{i+1},...,r_n».

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

Есть ещё "стабильная" версия этой гипотезы, которая связана с теорией простых гомотопий (Simple-homotopy theory). И всякие её варианты, которые были недавно решены при помощи того, что GL_2 не равно GE_2 для кольца многочленов Лорана (см. https://arxiv.org/pdf/1806.11493.pdf ). Может, ещё напишу об этом отдельно потом, чтобы самому подробнее разобраться.

вот ещё видео моего старого доклада про гипотезу Эндрюса-Кёртиса

https://youtu.be/sQ6rRSOLX6M?si=ebfn6rRwGkXvvE5n

Дима Каледин, математик (старожилы русского интернета могут знать его имя по старому ЖЖ), опубликовал 600-страничную статью , в которой описывает новый подход к абстрактной теории гомотопии, над которым он работал много лет. Он предлагает этот подход в качестве альтернативы популярной в последние 20 лет теории категорий бесконечных порядков Джейкоба Лурье.

Я совершенно некомпетентен в этих вопросах и не имею собственного мнения о работе Каледина (или о школе Лурье), но должен сказать, что первые 40 страниц статьи Каледина - введение - прочел с огромным интересом; что-то понял, другое пропустил, и все равно интересно. Рекомендую.

Очень понравились слова Каледина о силе нарратива, это что-то, в чем я неоднократно убеждаюсь в своей жизни и своих мыслях снова и снова:

"I still remember a talk in Tokyo, in 2008, after which a prominent algebraic geometer came to me and said something like this: “I liked your talk; of course, the last thing the world needs are new foundations for homological algebra, but at least, there was a story”. This was one of the best pieces of advice I ever had: no matter what you do, people will listen if there is a story."

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

Комплекс Виеториса-Рипса окружности

Комплекс Виеториса-Рипса VR(X,r) метрического пространства X — это (абстрактный) симплициальный комплекс, симплексы которого — это конечные непустые подмножества Х диаметра строго меньше r, где r — это положительный вещественный параметр. Этот комплекс используется в геометрической теории групп, метрической геометрии, и топологическом анализе данных. Например, в геометрической теории групп они пользуются тем, что для гиперболической группы G и для любого выбора конечного набора порождающих в ней, комплекс Виеториса-Рипса графа Кэли стягиваем для любого достаточно большого параметра r.

Есть теорема о том, что для компактного Риманова многообразия M и достаточно малого параметра r>0 геометрическая реализация VR(M,r) гомотопически эквивалентна M. То есть при малых r гомотопический тип VR(M,r) не зависит от метрики, а зависит только от гомотопического типа M. Что происходит с гомотопическим типом VR(M,r) при больших значениях параметра r — это загадочный вопрос.

Например, если взять окружность периметра один S^1 с внутренней метрикой, то все сферы нечётных размерностей S^1, S^3, S^5,... появляются как гомотопические типы VR(S^1,r).

Например,

0 < r ≤ 1/3 ⇒ |VR(S^1,r)| ≃ S^1;

1/3 < r ≤ 2/5 ⇒ |VR(S^1,r)| ≃ S^3;

2/5 < r ≤ 3/7 ⇒ |VR(S^1,r)| ≃ S^5;

....

1/2 ≤ r ⇒ |VR(S^1,r)| стягиваемо.

Таким вот необычным способом можно получить все нечётные сферы из окружности.

Есть гипотеза, что для любого компактного Риманова многообразия M связность |VR(M,r)| возрастает с ростом r.

Есть так же какие-то вычисления для эллипсов с Евклидовой метрикой.

https://arxiv.org/abs/1503.03669

https://publish.illinois.edu/ymb/files/2020/03/Hausmann-1995-On-the-Vietoris-Rips-complexes-and-a-cohomology-th.pdf

https://arxiv.org/abs/1704.04956

𝑙_p-комплексы Виеториса-Рипса

Мы с моим китайским другом Сяоменгом выложили препринт, в котором определяем обобщение комплекса Виеториса-Рипса, зависящее от дополнительного параметра
1≤𝑝≤∞. В этом определении используется 𝑙_p-норма. При 𝑝=∞ получается обычный комплекс Виеториса-Рипса, а при 𝑝=1 — пространство, гомологии которого — это размытые магнитудные гомологии.

Таким образом, мы объединяем эти две теории и утверждаем, что их следует изучать вместе. В частности, мы доказываем, что для компактного риманова многообразия 𝑀 при малом параметре 𝑟 этот комплекс гомотопически эквивалентен 𝑀 для любого 𝑝. Мы также приводим доказательства других свойств, которые ранее были известны для классического комплекса Виеториса-Рипса. Например, при переходе к пополнению метрического пространства гомотопический тип 𝑙_p-комплекса Виеториса-Рипса сохраняется.

Кроме того, мы доказываем свойство, которое удивило некоторых специалистов по магнитудным гомологиям. Мы показываем, что гомологии нашего 𝑙_p-комплекса Виеториса-Рипса коммутируют с фильтрующимися копределами метрических пространств. Важно отметить, что в этом доказательстве используется строгое неравенство в определении комплекса; для нестрогого неравенства это свойство не выполняется. В частности, строго размытые магнитудные гомологии коммутируют с фильтрующимися копределами, а нестрого размытые (как и обычные магнитудные) не коммутируют.

Подробности в прикреплённой далее презентации, и в архиве

https://arxiv.org/abs/2411.01857

Коммутативные квадраты абелевых групп часто появляются в математике. Полезно знать их базовые свойства. Если вы знаете спектральную последовательность бикомплекса, и рассмотрите коммутативный квадрат как бикомплекс, то вы сможете доказать эти свойства c закрытыми глазами, без листочка бумаги.

Следующие утверждения эквивалентны:
1) центральный квадрат — пулбэк;
2) последовательность
0 → A → A'⊕B → B'
точна;
3) α' — изоморфизм и β' — мономорфизм.

Двойственные утверждения тоже эквивалентны
1) центральный квадрат — пушаут;
2) последовательность
A → A'⊕B → B' → 0
точна;
3) α' — эпиморфизм и β' — изоморфизм.

Получаем, что и следующие утверждения эквивалентны.
1) центральный квадрат — пулбэк и пушаут;
2) последовательность
0 → A → A'⊕B → B' → 0
точна;
3) α' и β' — изоморфизмы.

Конечно, здесь всё симметрично относительно замены (α, β) на (φ,ψ). Поэтому α' и β' изоморфизмы тогда и только тогда, когда
φ' : Ker(α) → Ker(β)
ψ' : Coker(α) → Coker(β)
изоморфизмы.

Это работает в любой абелевой категории.

Теорема Акса-Гротендика и ультрафильтры.

1/2

Гриша Папаянов мне тут интересную тему рассказал. Есть такая теорема Акса-Гротендика, которая говорит, что любое инъективное полиномиальное отображение из n-мерного комплексного пространства в себя
ℂ^n → ℂ^n
сюръективно.

Интересна мне эта теорема не сама по себе, а методом доказательства, который рассказал мне Гриша, и которое можно найти по ссылке. Это абсолютно прозрачное доказательство, в котором используются конечные поля и ультрафильтры.

В доказательстве используется понятие фильтра, ультрафильтра, ультрапроизведения и предложения первого порядка, которые я напомню в следующих скрытых кусочках и гиперссылки сделаю (если знаете, можно не читать).

Фильтры.

Фильтр на множестве X — это такое множество F подмножеств X, что выполняются следующие аксиомы:
1) пустое множество не является элементом F;
2) F замкнуто относительно конечных пересечений;
3) F замкнуто относительно взятия надмножеств,
то есть если A ∈ F и A⊆B⊆X, то B ∈ F.

Например, окрестности какой-то точки в топологическом пространстве образуют фильтр. А ещё, если X бесконечно, то дополнения конечных множеств образуют фильтр.

Ультрафильтры.

Фильтры образуют упорядоченное множество по включению. Ультрафильтр — это максимальный по включению фильтр. Эквивалентно можно определить ультрафильтр как фильтр F, у которого для любого подмножества A⊆X, либо A∈F, либо X\A∈F.

Например, для любого x_0 ∈ X, все подмножества содержащие x_0, образуют ультрафильтр. Такие ультрафильтры называются главными. Если X конечно, то все ультрафильтры главные. Все остальные ультрафильтры явно не строятся, а строятся при помощи следующего утверждения, которое доказывается при помощи леммы Цорна: для любого фильтра существует ультрафильтр, который его содержит. В частности, для фильтра дополнений конечных множеств есть ультрафильтр, который его содержит, и он не главный.

Ультрапроизведение.

Если есть семейство множеств (X_i)_{i∈I}, проиндексированное множеством I, и задан ультрафильтр F на I, то можно взять произведение этого семейства и профакторизовать по такому отношению эквивалентности: два элемента произведения x,y эквивалентны, если
{ i : x_i = y_i } ∈ F.
Фактор произведения по этому отношению эквивалентности называется ультрапроизведением этого семейства.

Когда все X_i равны, то это называется ультрастепенью. Например, гипервещественные числа из нестандартного анализа — это ультрастепень поля вещественных чисел относительно не главного ультрафильтра.

Предложения первого порядка.

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

Фундаментальная теорема об ультрапроизведениях (Теорема Łoś'a) говорит, что если у вас есть семейство моделей X_i над какой-то сигнатурой, и какое-то предложение первого порядка, то оно выполняется для их ультрапроизведения относительно ультрафильтра F тогда и только тогда, когда множество индексов i, что оно выполняется для X_i, лежит в F.

В частности, если какое-то предложение первого порядка верно для всех X_i, то оно верно и для их ультрапроизведения.

Отсюда получаем, что ультрапроизведение полей — это поле. И ультрапроизведение алгебраически замкнутых полей — это алгебраически замкнутое поле.

2/2

Дальше при помощи этого всего добра доказываем теорему Акса-Гротендика.

Можно задаться вопросом, для каких полей F утверждение
"любое инъективное полиномиальное отображение из F^n в себя сюръективно"
верно?

Заметим, что если фиксировать n и степени всех n полиномов от n переменных, то это утверждение можно записать в виде предложения первого порядка.

Для конечных полей F это утверждение верно.

Если K_p — алгебраическое замыкание поля из p элементов, то из того, что любое его конечно порождённое подполе конечно, тоже получается, что это верно.

Значит оно верно и для ультрапроизведения K всех K_p по всем p относительно не главного ультрафильтра на множестве простых чисел.

Это ультрапроизведение K, так же как и все сомножители, является алгебраически замкнутым полем. И его характеристика равна нулю.

Обычное произведение всех K_p, понятное дело, имеет континуальную мощность. Можно показать, что и ультрапроизведение K имеет континуальную мощность. Это обычная задачка на теорию множеств: (Для этого достаточно заметить, что есть континуальное семейство функций ℕ → ℕ, разные члены которого совпадают только на конечном числе элементов. Чтобы построить такое семейство, нужно для каждой последовательности
a : ℕ → {0,1}
определить функцию
f_a : ℕ → ℕ
по формуле
f_a (n) = a(0)*2^0 + a(1)* 2^1 + ... +a(n)*2^n.)

Теорема Штайница говорит, что любое алгебраически замкнутое поле характеристики ноль и континуальной мощности изоморфно полю комплексных чисел. То есть K изоморфно ℂ. Теорема доказана.