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

11

Diz-se que dois grupos (G,) e (H,×) 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:

Group Isomorphism Problem

Input :  Dois grupos(G,) e(H,×) .

Decide :  IsGH ?

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 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 O(logn) e que pode ser encontrado em tempo polinomial. O número de imagens do grupo gerador S no homomorfismo de G a H é nlogn muitos. Agora, verifique se cada homomorfismo possível é bijetivo ou não. O tempo de execução geral será nlogn+O(1) .

Deixe-me primeiro definir o centro do grupo G :

Z(G)={gGag=ga,aG}

Z(G) indica os elementos do grupoG que comuta com todos os outros elementos do grupoG . Grupos para os quaisG/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 P .

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

aaaa
fonte
Olá, você poderia considerar expandir sua pergunta um pouco para recapitular a definição do problema de isomorfismo de grupo (qual é a entrada, qual é a saída) e / ou uma referência? Você também poderia recapitular a definição do centro de um grupo? Por fim, você poderia esclarecer se "permitir como resolver" ("nós"?) É uma alegação sobre a existência de uma redução?
a3nm

Respostas:

15

pAcredita-se que osgrupos p da classe 2 e expoentep sejam o caso mais difícil do isomorfismo do grupo (p>2 ). (Parap=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 Fp , o problema é 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 nO(loglogn) (G-Qiao CCC '14, SICOMP '17) - portanto, não muito polinomial, mas muito mais próximo quenlogn . 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 Sylowp- e parece que os casos mais difíceis são osgruposp.

2) Contando. O número de grupos da ordem n é n(227+o(1))μ(n)2, ondeμ(n)é o maior expoente de qualquer divisão principaln(Pyber 1993). O número degrupospde ordemn=pmé pelo menosp(227+o(1))m2(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 expoentep). 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 ordemnque sãogruposptende a 1 comon.

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.

Joshua Grochow
fonte
Você pode editar a definição da classe 2? A página da Wikipedia nos grupos- menciona apenas a classe nilpotency, é a mesma noção de classe que você tem em mente? p
1300 Vincent
Sim, classe sem potência.
Joshua Grochow
Obrigado pelo esclarecimento!
1400 Vincent