Qual é o exemplo mais difícil do problema de isomorfismo de grupo?

Diz-se que dois grupos $(G,\cdot)$ e $(H, \times)$ são isomórficos se existir um homomorfismo de $G$ a $H$ que seja bijetivo. O problema do isomorfismo do grupo é o seguinte: dados dois grupos, verifique se são isomórficos ou não. Existem diferentes maneiras de inserir um grupo, os dois mais usados ​​são por uma tabela Cayley e por um grupo gerador. Aqui, estou assumindo que os grupos de entrada são fornecidos pela tabela de Cayley. Mais formalmente:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ Dois grupos$(G,\cdot)$ e$(H,\times)$ .

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

Vamos supor que $n = |G| = |H|$

O problema de isomorfismo de grupo quando os grupos de entrada são fornecidos pela tabela de Cayley não é conhecido por estar em $\textbf{P}$ em geral. Embora existam classes de grupo, como a classe de grupo abeliana, para a qual se sabe que o problema ocorre no tempo polinomial, grupos que são a extensão de um grupo abeliano, grupos simples etc. conhecido.

Um algoritmo de força bruta para isomorfismo de grupo é dado por Tarjan, que é o seguinte. Deixe $G$ e $H$ são dois grupos de entrada, e deixá- $S$ ser um grupo gerador do grupo $G$ . É um fato bem conhecido que todo grupo finito admite um conjunto gerador de tamanho $\mathcal{O}(\log n)$ e que pode ser encontrado em tempo polinomial. O número de imagens do grupo gerador $S$ no homomorfismo de $G$ a $H$ é $n^{\log n}$ muitos. Agora, verifique se cada homomorfismo possível é bijetivo ou não. O tempo de execução geral será $n^{\log n + \mathcal{O}(1)}$ .

Deixe-me primeiro definir o centro do grupo $G$ :

$Z(G)$ indica os elementos do grupo$G$ que comuta com todos os outros elementos do grupo$G$ . Grupos para os quais$G/Z(G)$ (/ usado para quociente) é abeliano são conhecidos como grupos nilpotentes da classe dois. Para mim, parece que os grupos nilpotentes da classe dois são os casos mais difíceis de resolver o problema do isomorfismo do grupo. O significado de "instâncias mais difíceis" é: resolver esse caso permitirá que pesquisadores que trabalham na teoria de grupos resolvam o problema de isomorfismo de um grande número de grupos.

Inicialmente, pensei que os grupos simples são as instâncias mais difíceis à medida que são blocos de construção de todos os grupos, mas mais tarde vim a saber que o problema isomorfismo de grupos simples está em $\textbf{P}$ .

Pergunta : Qual é a instância mais difícil para o problema de isomorfismo de grupo?

$p$Acredita-se que osgrupos p da classe 2 e expoente$p$ sejam o caso mais difícil do isomorfismo do grupo ($p > 2$ ). (Para$p=2$ , precisamos considerar o expoente 4, pois todos os grupos do expoente 2 são abelianos - exercício fácil para o leitor.) Embora ainda não haja redução do GpIso geral para essa classe de grupos (embora veja o ponto 0.5 abaixo) ), há várias razões para essa crença. Deixe-me descrever alguns deles aqui.

0) Experiência prática (ver artigos de Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... que fornecem os algoritmos implementados no GAP e no MAGMA).

0.5) [EDIT: added 8/7/19] Reduções. Quando tais $p$ -Grupos são dadas através da geração de conjuntos de matrizes mais de $\mathbb{F}_p$ , o problema é $\mathsf{TI}$ -completo [ G.-Qiao '19 ]. Além disso (cf. ponto (4) abaixo), o isomorfismo dos grupos $p$ do expoente $p$ classe $c < p$ reduz no tempo de poli ao isomorfismo dos grupos $p$ do expoente $p$ classe 2 (ibid.).

1) Estrutura (reduza para solucionável e depois para o grupo $p$ ). Cada grupo finito contém um subgrupo único solúvel máxima normal, chamado o radical solúvel, denotado $Rad(G)$ . $G/Rad(G)$ não contém subgrupos normais abelianos, e o isomorfismo desses grupos pode ser tratado com eficiência na prática ( Cannon-Holt J. Symb. Comput. 2003 ) e na teoria ( Babai-Codenotti-Qiao ICALP 2012 ). Mesmo para os grupos em que $Rad(G)$ é abeliano, alguns destes podem ser manipulados em $n^{O(\log \log n)}$ (G-Qiao CCC '14, SICOMP '17) - portanto, não muito polinomial, mas muito mais próximo que$n^{\log n}$ . O principal obstáculo, portanto, parece ser um grupo solucionável (sub) normal. Agora, dentro de grupos solucionáveis, há muita estrutura - começando com o fato de que todo grupo solucionável é umproduto tricotadode seus subgrupos Sylow$p$- e parece que os casos mais difíceis são osgrupos$p$.

2) Contando. O número de grupos da ordem $n$ é $\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$, onde$\mu(n)$é o maior expoente de qualquer divisão principal$n$(Pyber 1993). O número degrupos$p$de ordem$n=p^m$é pelo menos$p^{(\frac{2}{27} + o(1))m^2}$(Higman 1960). Então você vê que o coeficiente dos termos principais nos expoentes corresponde. Nesse sentido, "a maioria" dos grupos são grupos-$p$(mesmo da classe 2 e expoente$p$). Existe uma conjectura de longa data que diz que "a maioria" no sentido fraco anterior pode ser fortalecida para dizer que a proporção de grupos de ordem$\leq n$que sãogrupos$p$tende a 1 como$n \to \infty$.

3) Universalidade (/ selvageria). Dar uma classificação de grupos $p$ implicaria uma classificação de todas as representações modulares de qualquer grupo finito (ou mesmo álgebra artiniana) na característica $p$ ( Sergeichuk, 1977 ).

4) flexibilidade. Por que grupos $p$ da classe 2 e não da classe superior? (Note-se que $p$ -Grupos de classe quase-máxima, os chamados "pequenos coclass", essencialmente, foram classificados, Eick & Leedham-Verde de 2006 , ver também algumas das respostas aqui .) Para qualquer $p$- o grupo 1 pode associar um anel de Lie graduado, onde o suporte no anel de Lie corresponde ao comutador no grupo. A associatividade no grupo implica a identidade Jacobi para o suporte, dando origem a um verdadeiro anel de Lie. No entanto, observe que quando o grupo é da classe 2, a identidade Jacobi é trivialmente satisfeita (todos os seus termos são automaticamente 0), portanto, isso não impõe restrições adicionais à estrutura. Basicamente, corresponde apenas a um mapa bilinear simétrico assimétrico e arbitrário. Para os grupos $p$ do expoente $p$ , há até uma redução da classe $c < p$ para a classe 2.