Две группы и называются изоморфными, если существует гомоморфизм из в который является биективным. Проблема группового изоморфизма заключается в следующем: для двух групп проверьте, изоморфны они или нет. Существует несколько способов ввода группы, два из которых в основном используются таблицей Кейли и генерирующим набором. Здесь я предполагаю, что входные группы задаются их таблицей Кэли. Более формально:
Две группы и .
Является ли ?
Предположим, что
Проблема группового изоморфизма, когда входные группы задаются таблицей Кэли, в общем случае неизвестна в . Хотя существуют групповые классы, такие как класс абелевых групп, для которых известно, что проблема существует за полиномиальное время, группы, являющиеся продолжением абелевой группы, простые группы и т. Д. Даже для нильпотентных классов из двух групп нет алгоритма, лучше, чем грубая сила. известный.
Алгоритм перебора для группового изоморфизма дан Тарьяном, который заключается в следующем. Пусть и две входные группы, и пусть порождающее множество группы . Хорошо известно, что каждая конечная группа допускает порождающий набор размером который можно найти за полиномиальное время. Число образов порождающего множества в гомоморфизме из в равно много. Теперь проверьте, является ли каждый возможный гомоморфизм биективным или нет. Общее время выполнения будет .
Позвольте мне сначала определить центр группы :
обозначает элементы группы , перестановочный со всеми другими элементами группы . Группы, для которых (/ используется для частного) является абелевой, известны как нильпотентные группы двух классов. Мне кажется, что нильпотентные группы второго класса - самые трудные примеры для решения проблемы изоморфизма групп. Значение «самых сложных случаев» таково: решение этого случая позволит исследователям, работающим в теории групп, решить проблему изоморфизма большого числа групп.
Первоначально я думал, что простые группы являются самыми сложными примерами, поскольку они являются строительными блоками для всех групп, но позже узнал, что проблема изоморфизма простых групп находится в .
Вопрос : Какой самый сложный пример для проблемы группового изоморфизма?
Ответы:
0) Практический опыт (см. Статьи Ньюмана, Эйка, О'Брайена, Холта, Кэннона, Уилсона, ... которые дают алгоритмы, которые реализованы в GAP и MAGMA).
0,5) [ПРАВКА: добавлено 8/7/19] Сокращения. Когда такие -группы задаются порождающими наборами матриц над , проблема является -полной [ G.-Qiao '19 ]. Также (см. Пункт (4) ниже) изоморфизм -групп экспоненты и класса сводится за многократное время к изоморфизму -групп экспоненты и класса 2 (там же).p Fp TI p p c<p p p
1) Структура (сводится к разрешимой, затем к -группе). Каждая конечная группа содержит единственную максимально разрешимую нормальную подгруппу, называемую разрешимым радикалом, обозначаемую . содержит абелевых нормальных подгрупп, и изоморфизм таких групп может быть эффективно обработан на практике ( Cannon-Holt J. Symb. Comput. 2003 ) и в теории ( Babai-Codenotti-Qiao ICALP 2012 ). Даже для групп, где абелева, некоторые из них могут быть обработаны за время ( G-Qiao CCC '14, SICOMP '17 ) - так что не совсем многочлен, но гораздо ближе, чемp Rad(G) G/Rad(G) Rad(G) nO(loglogn) nlogn , Таким образом, основным препятствием являются разрешимые (нормальные подгруппы). В настоящее время в разрешимых группах существует много структур - начиная с того факта, что каждая разрешимая группа является вязким произведением своих силовских подгрупп, и, по-видимому, наиболее сложными являются .p p
2) Подсчет. Число групп порядка равно , где - наибольший показатель любого простого числа деление ( Pyber 1993 ). Число -групп порядка составляет не менее ( Higman 1960 ). Итак, вы видите, что коэффициент ведущих членов в показателях степени совпадает. В этом смысле «большинство» групп являются -группами (даже класса 2 и степени ). Существует давняя гипотеза, которая говорит, что «большинство» в предыдущем слабом смысле может быть усилено, чтобы сказать, что пропорция групп порядкаn ≤n(227+o(1))μ(n)2 μ(n) n p n=pm p(227+o(1))m2 p p ≤n которые являются -группами, стремится к 1 при .p n→∞
3) Универсальность (/ дикость). Определение классификации -групп подразумевает классификацию всех модулярных представлений любой конечной группы (или даже артиновой алгебры) в характеристике ( Сергейчук, 1977 ).p p
4) Гибкость. Почему группы класса 2, а не высшего класса? (Обратите внимание, что -группы почти максимального класса, так называемого «малого кокласса», по существу, были классифицированы, Eick & Leedham-Green 2006 , см. Также некоторые ответы здесь .) Для любогоp p p -группе можно связать градуированное кольцо Ли, где скобка в кольце Ли соответствует коммутатору в группе. Ассоциативность в группе подразумевает тождество Якоби для скобки, что приводит к подлинному кольцу Ли. Тем не менее, обратите внимание, что когда группа относится к классу 2, тождество Якоби удовлетворяется тривиально (все ее члены автоматически равны 0), поэтому это не накладывает дополнительных ограничений на структуру. Это в основном просто соответствует произвольному кососимметричному билинейному отображению. Для -групп экспоненты , есть даже сокращение от класса к классу 2.p p c<p
источник