Когда-то я писал про гипотезу Эндрюса-Кёртиса. И про то, что представление Акбулата-Кирби AK(3)
< x, y | x^3 = y^4, xyx = yxy >
является потенциальным контрпримером к ней. И к стабильной версии, и к нестабильной. Используя искусственный интеллект, люди доказали, что это не контрпример к стабильной версии. Про нестабильную версию, как я понял, вопрос остаётся открытым.
https://arxiv.org/pdf/2408.15332
< x, y | x^3 = y^4, xyx = yxy >
является потенциальным контрпримером к ней. И к стабильной версии, и к нестабильной. Используя искусственный интеллект, люди доказали, что это не контрпример к стабильной версии. Про нестабильную версию, как я понял, вопрос остаётся открытым.
https://arxiv.org/pdf/2408.15332
Forwarded from (sci)Berloga Всех Наук и Технологий
🚀 @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 !
👨🔬 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 ). Может, ещё напишу об этом отдельно потом, чтобы самому подробнее разобраться.
_______________________
Гипотеза Эндрюса-Кёртиса
Допустим, что у нас есть несколько элементов 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
https://youtu.be/sQ6rRSOLX6M?si=ebfn6rRwGkXvvE5n
YouTube
С. О. Иванов "Гипотеза Эндрюса-Кёртиса"
Доклады лауреатов премии общества «Молодому математику»
http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=22778
Аннотация: Гипотеза Эндрюса-Кёртиса – это открытая гипотеза в комбинаторной теории групп, высказанная в 1965 году. Она формулируется…
http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=22778
Аннотация: Гипотеза Эндрюса-Кёртиса – это открытая гипотеза в комбинаторной теории групп, высказанная в 1965 году. Она формулируется…
Forwarded from Авва
Дима Каледин, математик (старожилы русского интернета могут знать его имя по старому ЖЖ), опубликовал 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."
Антон Капустин, у которого я прочитал об этой работе, тоже хвалит ее введение и замечает, что хорошо бы кто-то выпустил книгу, состоящую только из особенно хороших предисловий к математическим статьям или книгам. Да, такое я бы с удовольствием почитал.
Я совершенно некомпетентен в этих вопросах и не имею собственного мнения о работе Каледина (или о школе Лурье), но должен сказать, что первые 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
Комплекс Виеториса-Рипса 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
arXiv.org
The Vietoris-Rips complexes of a circle
Given a metric space X and a distance threshold r>0, the Vietoris-Rips simplicial complex has as its simplices the finite subsets of X of diameter less than r. A theorem of Jean-Claude Hausmann...
𝑙_p-комплексы Виеториса-Рипса
Мы с моим китайским другом Сяоменгом выложили препринт, в котором определяем обобщение комплекса Виеториса-Рипса, зависящее от дополнительного параметра
1≤𝑝≤∞. В этом определении используется 𝑙_p-норма. При 𝑝=∞ получается обычный комплекс Виеториса-Рипса, а при 𝑝=1 — пространство, гомологии которого — это размытые магнитудные гомологии.
Таким образом, мы объединяем эти две теории и утверждаем, что их следует изучать вместе. В частности, мы доказываем, что для компактного риманова многообразия 𝑀 при малом параметре 𝑟 этот комплекс гомотопически эквивалентен 𝑀 для любого 𝑝. Мы также приводим доказательства других свойств, которые ранее были известны для классического комплекса Виеториса-Рипса. Например, при переходе к пополнению метрического пространства гомотопический тип 𝑙_p-комплекса Виеториса-Рипса сохраняется.
Кроме того, мы доказываем свойство, которое удивило некоторых специалистов по магнитудным гомологиям. Мы показываем, что гомологии нашего 𝑙_p-комплекса Виеториса-Рипса коммутируют с фильтрующимися копределами метрических пространств. Важно отметить, что в этом доказательстве используется строгое неравенство в определении комплекса; для нестрогого неравенства это свойство не выполняется. В частности, строго размытые магнитудные гомологии коммутируют с фильтрующимися копределами, а нестрого размытые (как и обычные магнитудные) не коммутируют.
Подробности в прикреплённой далее презентации, и в архиве
https://arxiv.org/abs/2411.01857
Мы с моим китайским другом Сяоменгом выложили препринт, в котором определяем обобщение комплекса Виеториса-Рипса, зависящее от дополнительного параметра
1≤𝑝≤∞. В этом определении используется 𝑙_p-норма. При 𝑝=∞ получается обычный комплекс Виеториса-Рипса, а при 𝑝=1 — пространство, гомологии которого — это размытые магнитудные гомологии.
Таким образом, мы объединяем эти две теории и утверждаем, что их следует изучать вместе. В частности, мы доказываем, что для компактного риманова многообразия 𝑀 при малом параметре 𝑟 этот комплекс гомотопически эквивалентен 𝑀 для любого 𝑝. Мы также приводим доказательства других свойств, которые ранее были известны для классического комплекса Виеториса-Рипса. Например, при переходе к пополнению метрического пространства гомотопический тип 𝑙_p-комплекса Виеториса-Рипса сохраняется.
Кроме того, мы доказываем свойство, которое удивило некоторых специалистов по магнитудным гомологиям. Мы показываем, что гомологии нашего 𝑙_p-комплекса Виеториса-Рипса коммутируют с фильтрующимися копределами метрических пространств. Важно отметить, что в этом доказательстве используется строгое неравенство в определении комплекса; для нестрогого неравенства это свойство не выполняется. В частности, строго размытые магнитудные гомологии коммутируют с фильтрующимися копределами, а нестрого размытые (как и обычные магнитудные) не коммутируют.
Подробности в прикреплённой далее презентации, и в архиве
https://arxiv.org/abs/2411.01857
arXiv.org
On $\ell_p$-Vietoris-Rips complexes
We study the concepts of the $\ell_p$-Vietoris-Rips simplicial set and the $\ell_p$-Vietoris-Rips complex of a metric space, where $1\leq p \leq \infty.$ This theory unifies two established...