КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 24-11-00127
НазваниеКонечные группы и проблема изоморфизма
Руководитель Васильев Андрей Викторович, Доктор физико-математических наук
Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Новосибирский национальный исследовательский государственный университет" , Новосибирская обл
Конкурс №92 - Конкурс 2024 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-102 - Алгебра
Ключевые слова конечная группа, замыкание группы подстановок, граф, проблема изоморфизма, порядок элементов, полный класс групп, класс Фиттинга, ширина класса, многомерная когерентная конфигурация, размерность Вейсфейлера-Лемана
Код ГРНТИ27.17.17
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Проблемы изоморфизма графов и изоморфизма групп относятся к наиболее актуальным задачам современной математики и computer science. Несмотря на значительные усилия многих математиков в последние 50 лет, время работы лучших из предложенных алгоритмов остается по существу экспоненциальным. Прорывом в этой области стал результат Бабаи (2016), представленный на приглашенном докладе на Международном конгрессе математиков в Рио-де-Жанейро в 2018 году, о существовании квазиполиномиального алгоритма проверки изоморфизма графов (о существовании квазиполиномиального алгоритма для проверки изоморфизма групп известно давно: в статье Миллера 1978 г. изложен алгоритм, разработанный Тарджаном). Основная цель проекта состоит в разработке теоретико-групповых методов решения этих проблем. В рамках проекта планируется сосредоточиться на следующих направлениях исследований.
Замыкания конечных групп подстановок. По определению $m$-замыкание группы подстановок $G$ есть наибольшая группа подстановок, у которой орбиты индуцированного действия на множестве $m$-кортежей такие же, как у группы $G$. Иными словами, $m$-замыкание --- это полная группа автоморфизмов $m$-арной дискретной структуры, индуцированной группой $G$. Основные проблемы в теории $m$-замыканий состоят в описании строения $m$-замыкания данной группы и построении эффективного алгоритма его поиска. В рамках проекта предполагается изучить структуру замыканий различных классов групп подстановок и предложить новые алгоритмы для их нахождения. Основное внимание при этом будет уделено группам с ограниченными неабелевыми композиционными факторами.
С вычислительной точки зрения решение проблемы изоморфизма состоит в том, чтобы построить наиболее эффективный (в идеале полиномиальный) алгоритм, проверяющий изоморфизм двух данных графов (групп). Полиномиальный алгоритм всегда существует, когда эти графы (группы) имеют небольшую размерность Вейсфейлера-Лемана, то есть однозначно идентифицируются $m$-мерным алгоритмом Вейсфейлера-Лемана для небольшого $m$. Напомним, что класс конечных групп $X$ называется полным, если он замкнут относительно взятия подгрупп, фактор-групп и расширений. Оказывается, что если $X$ - полный класс, то $X$-радикал конечной группы может быть отслежен с помощью $m$-мерного алгоритма Вейсфейлера-Лемана (является $m$-WL-detectable в терминологии Брахтера и Швайцера), где число $m$ ограничено в терминах так называемой ширины Бэра-Сузуки класса $X$. Мы планируем доказать, что любой полный класс групп имеет конечную ширину Бэра-Сузуки и найти верхние оценки на эту ширину в некоторых наиболее интересных случаях.
Как показали Брахтер и Швайцер (2022), конечные группы, различаемые 5-мерным алгоритмом Вейсфейлера-Лемана, обязаны иметь различное композиционное строение, то есть факторы их композиционных рядов должны различаться (с учетом кратностей). Существенным моментом в доказательстве этого утверждения является использование следующего общего теоретико-группового результата, полученного участниками проекта Васильевым и Гречкосеевой совместно с Мазуровым (2009): если конечная простая группа и конечная группа одного порядка имеют одинаковые множества порядков элементов, то они изоморфны. Дело в том, что алгоритм позволяет отслеживать порядки элементов соответствующей группы, а значит, и восстановить все множество таких порядков, которое, следуя Адяну, принято назвать спектром группы. В рамках проекта будет исследоваться вопрос о характеризации неабелевых простых групп по спектру, в котором открытым остается лишь случай, когда простая группа является классической матричной группой размерности от 5 до 36.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Аннотация результатов, полученных в 2024 году
Одной из главных целей проекта является изучение свойств групп, сохраняемых при $m$-замыканиях, и построение полиномиальных алгоритмов вычисления замыканий некоторых классов групп. В 2024 г. участниками проекта А.В. Васильевым и С.В. Скресановым в соавторстве с И.Н. Пономаренко (ПОМИ РАН) была установлена связь между строением композиционных факторов группы подстановок и её $m$-замыкания для $m\geq 4$. Было показано, что если данная группа подстановок не содержит секцию, изоморфную знакопеременной группе степени $d$, $d\geq 25$, то и $m$-замыкание этой группы для $m\geq 4$ тоже не содержит такой секции. В ходе доказательства устанавливаются и несколько более точные ограничения на строение композиционных факторов рассматриваемой группы, что позволяет показать замкнутость естественных классов групп относительно операции m-замыкания.
Еще одно направление проекта связано с изучением BS-ширины полных классов групп. В 2024 г. участником проекта Д.О. Ревиным было доказано, что BS-ширина любого полного класса групп конечна и получена верхняя оценка на эту ширину в терминах наибольшего $d$ такого, что полная симметрическая группа степени $d$ лежит в данном классе. Этот результат обобщает классическую теорему Бэра-Сузуки, которая в терминах BS-ширины гласит, что BS-ширина класса $p$-групп для любого простого числа $p$ равна 2, а также теорему о том, что BS-ширина класса разрешимых групп равна 4, доказанную независимо Гордеевым, Груневальдом, Кунявским, Плоткиным с одной стороны и Флейвеллом, Гэстом, Гуралником с другой стороны.
Третье направление проекта связано с изучением конечных групп, изоспектральных конечным простым классическим группам (группы изоспектральны, если у них одинаковые множества порядков элементов). Известно, что любая конечная группа, изоспектральная простой классической группе $L$ размерности не менее 37, очень близка к $L$, а именно, является почти простой группой с цоколем $L$. Существует гипотеза, что данным свойством обладают и классические группы много меньших размерностей. В 2024 г. участниками проекта М.А. Гречкосеевой и В.В. Паньшиным было доказано, что этим свойством обладают простые группы $PSL_6(q)$, $PSU_5(q)$ и $PSU_6(q)$. В ходе доказательства также был получен общий результат о конечных группах, изоспектральных простым классической группам: такие группы не могут иметь в качестве композиционного фактора исключительную группу лиева типа.
Публикации
1.
Гречкосеева М.А., Паньшин В.В.
On recognition of low-dimensional linear and unitary groups by spectrum
Siberian Mathematical Journal, Том: 65, Номер: 5, Страницы: 1074-1095 (год публикации - 2024)
10.1134/s0037446624050094
2.
Пономаренко И.Н., Скресанов С.В., Васильев А.В.
Closures of permutation groups with restricted nonabelian composition factors
Bulletin of Mathematical Sciences, том 15, номер 2, номер статьи 2550012, 26 страниц (год публикации - 2025)
10.1142/S1664360725500122
3. Ревин Д.О. Ширина Бэра-Сузуки полного класса конечных групп конечна Алгебра и анализ, Том: 37, Номер: 1, Год: 2025, Страницы: 141-176 (год публикации - 2025)
Аннотация результатов, полученных в 2025 году
Одной из основных задач проекта является построение полиномиального алгоритма нахождения замыкания для любой группы $G$ подстановок с ограниченными неабелевыми композиционными факторами. В текущем году решение основной задачи было сведено к очень ограниченной ситуации, когда $G$ - примитивная базисная аффинная группа, а стабилизатор точки $G_0$, который в данном случае является линейной группой, содержит по модулю подгруппы скалярных матриц единственную минимальную нормальную подгруппу $L$, которая действует абсолютно неприводимо. Это позволяет утверждать, что общая задача будет полностью решена в следующем, третьем году работы по проекту.
Одной из целей проекта является изучение вычислительной сложности проблемы изоморфизма групп, в частности, изучение полиномиальных сведений между различными вариантами проблемы изоморфизма и связанными проблемами. В 2025 г. участник проекта С.В. Скресанов показал, что проблема изоморфизма групп сводится за полиномиальное время к проблеме вычисления полной группы автоморфизмов. Более того, доказывается, что и ряд других вычислительных задач на группах тоже сводится за полиномиальное время к проблеме вычисления автоморфизмов. Полученный результат является групповым аналогом классических полиномиальных сведений в проблеме изоморфизма графов.
Теорема Бэра-Сузуки дает критерий принадлежности элемента конечной группы ее $p$-радикалу для любого фиксированного простого числа $p$. Это утверждение играет в теории конечных групп важную роль, являясь одновременно признаком непростоты группы и инструментом локального анализа. Обобщения этой теоремы занимают умы многих специалистов, включая таких корифеев, как Фишер, Тиммесфельд, Гуральник, Малле и другие. Естественным направлением обобщений является перенесение данного результата с простого числа $p$ на произвольное множество $\pi$ простых чисел. В 2025 году получено существенное продвижение в изучении неулучшаемого аналога теоремы Бэра-Сузуки для $\pi$-радикала. Этот аналог шаг за шагом доказывается для конечных групп с запретом на определенные композиционные факторы, и шаг в доказательстве состоит в снятии запрета на те или иные композиционные факторы. В 2025 году удалось снять запрет на наличие композиционных факторов, изоморфным симплектическим группам. В настоящее время аналог теоремы Бэра-Сузуки для $\pi$-радикала доказан для конечных групп, не имеющих композиционных факторов, изоморфных простым ортогональным группам размерности не меньше 7, и некоторым "большим" исключительным группам.
Одной из целей проекта является доказательство следующей гипотезы: конечная группа, имеющая такое множество порядков элементов, как конечная простая классическая группа $L$ не очень маленькой размерности, очень близка к $L$, а именно, является почти простой группой с цоколем $L$. В 2025 г. М.А. Гречкосеева и В.М. Родионов показали, что указанным свойством обладают простые группы $PSL_8(q)$, $PSU_8(q)$, $P\Omega_10^+(q)$, $P\Omega_10^-(q)$ и $P\Omega_12^+(q)$. В.В. Паньшин доказал, что указанным свойством обладают все простые линейные и унитарные группы над полями нечетной характеристики размерностей от 7 до 24 с несвязным графом простых чисел. Результат В.В. Паньшина завершил изучение проблемы распознаваемости по спектру для простых групп с несвязным графом простых чисел.
Публикации
1.
Гречкосеева М.А., Паньшин В.В.
On recognition of low-dimensional linear and unitary groups by spectrum
Siberian Mathematical Journal, Том: 65, Номер: 5, Страницы: 1074-1095 (год публикации - 2024)
10.1134/s0037446624050094
2.
Пономаренко И.Н., Скресанов С.В., Васильев А.В.
Closures of permutation groups with restricted nonabelian composition factors
Bulletin of Mathematical Sciences, том 15, номер 2, номер статьи 2550012, 26 страниц (год публикации - 2025)
10.1142/S1664360725500122
3. Ревин Д.О. Ширина Бэра-Сузуки полного класса конечных групп конечна Алгебра и анализ, Том: 37, Номер: 1, Год: 2025, Страницы: 141-176 (год публикации - 2025)