Jaki jest najtrudniejszy przykład problemu grupowego izomorfizmu?

Mówi się, że dwie grupy $(G,\cdot)$ i $(H, \times)$ są izomorficzne, jeśli istnieje homomorfizm od $G$ do $H$ który jest bijectywny. Problem z izomorfizmem grupowym jest następujący: biorąc pod uwagę dwie grupy, sprawdź, czy są izomorficzne, czy nie. Istnieją różne sposoby wprowadzania grupy, dwa najczęściej używane są przez tabelę Cayleya i przez zestaw generacyjny. Zakładam, że grupy danych wejściowych podano w tabeli Cayleya. Bardziej formalnie:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ dwie grupy$(G,\cdot)$ i$(H,\times)$ .

$\textbf{Decide : }$ Czy$G \cong H$ ?

Załóżmy, że $n = |G| = |H|$

Grupowy problem z izomorfizmem, gdy grupy wejściowe są podane w tabeli Cayleya, nie jest ogólnie znany jako $\textbf{P}$Chociaż istnieją klasy grup, takie jak klasa grupy abelowej, dla których wiadomo, że problem występuje w czasie wielomianowym, grupy, które są rozszerzeniem grupy abelowej, grupy proste itp. Nawet w przypadku grup nilpotentnych dwóch grup nie ma algorytmu lepszego niż brutalna siła znany.

Algorytm brutalnej siły dla izomorfizmu grupowego podaje Tarjan, który jest następujący. Niech $G$ i $H$ są dwie grupy wejściowe, i pozwolić $S$ być zestawem do generowania grupy $G$ . Jest dobrze znanym faktem, że każda skończona grupa przyjmuje zestaw generujący wielkość $\mathcal{O}(\log n)$ który można znaleźć w czasie wielomianowym. Liczba obrazów zespołu prądotwórczego $S$ w homomorfizmie od $G$ do $H$ wynosi $n^{\log n}$ wiele. Teraz sprawdź, czy każdy możliwy homomorfizm jest bijectywny, czy nie. Całkowity czas działania wyniesie $n^{\log n + \mathcal{O}(1)}$ .

Pozwól mi najpierw zdefiniować środek grupy $G$ :

$Z(G)$ oznacza elementów grupy$G$ która dojazdy ze wszystkimi innymi elementami z grupy$G$ . Grupy, dla których$G/Z(G)$ (/ używane do ilorazu) jest abelowa, są znane jako grupy zerowe o dwóch potęgach. Wydaje mi się, że nilpotentne dwie grupy klasy są najtrudniejszymi przypadkami do rozwiązania problemu izomorfizmu grupowego. Znaczenie „najtrudniejszych przypadków” jest takie: rozwiązanie tego przypadku pozwoli badaczom pracującym w teorii grup rozwiązać problem izomorfizmu dużej liczby grup.

Początkowo myślałem, że proste grupy są najtrudniejsze przypadki, ponieważ są one bloki każdego budynku, ale później dowiedział się, że problem izomorfizmem dla grup prostych jest w $\textbf{P}$ .

Pytanie : Jaki jest najtrudniejszy przypadek problemu grupowego izomorfizmu?

$p$$p$$p > 2$$p=2$

0) Praktyczne doświadczenie (patrz artykuły Newmana, Eicka, O'Briena, Holta, Cannona, Wilsona ..., które podają algorytmy zaimplementowane w GAP i MAGMA).

$p$$\mathbb{F}_p$$\mathsf{TI}$$p$$p$$c < p$$p$$p$

$p$$Rad(G)$$G/Rad(G)$$Rad(G)$$n^{O(\log \log n)}$$n^{\log n}$$p$$p$

$n$$\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$$\mu(n)$$n$$p$$n=p^m$$p^{(\frac{2}{27} + o(1))m^2}$$p$$p$$\leq n$$p$$n \to \infty$

$p$$p$

$p$$p$$p$$p$$p$$c < p$