Конечные группы и проблема изоморфизма

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 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