Grupos

Na álgebra abstrata, um grupo é uma tupla $(G,\ast)$ , onde $G$ é um conjunto e $\ast$ é uma função $G\times G\rightarrow G$ modo que o seguinte vale:

• Para todos os $x, y, z$ em $G$ , $(x\ast y)\ast z=x\ast(y\ast z)$ .

• Existe um elemento em L de tal modo que para todos os x em L , X * E = x .$e$$G$$x$$G$$x\ast e=x$

• Para cada em G , existe um elemento y em G tal que x ∗ y = e .$x$$G$$y$$G$$x\ast y=e$

A fim de um grupo é definido como o número de elementos de L .$(G,\ast)$$G$

Para cada número inteiro estritamente positivo , existe pelo menos um grupo da ordem n . Por exemplo, ( C n , + n ) é um tal grupo, onde C n = { 0 , . . . , n - 1 } e x + n y = ( x + y $n$$n$$(C_n,+_n)$$C_n=\{0,...,n-1\}$ .$x+_ny=(x+y)\mod n$

Grupos isomórficos

Seja e defina ∗ por x ∗ y = ( x × y $G:=\{1,2\}$$\ast$ . Em seguida, 1 * 1 = 1 = 2 * 2 e 1 * 2 = 2 = 2 * 1 .$x\ast y=(x\times y)\mod3$$1\ast1=1=2\ast2$$1\ast2=2=2\ast1$

Da mesma forma, e 0 + 2 1 = 1 = 1 + 2 0 .$0+_20=0=1+_21$$0+_21=1=1+_20$

Embora os elementos e as operações de grupos e ( C 2 , + 2 ) ter nomes diferentes, os grupos partilham a mesma estrutura.$(G,\ast)$$(C_2,+_2)$

Dois grupos e ( G 2 , * 2 ) são referidos como sendo isomorfos se existe um bijeç~ao φ : G 1 → L 2 de tal modo que φ ( x * 1 y ) = φ ( x ) * 2 ϕ ( y ) para todos os x , y em G 1 .$(G_1,\ast_1)$$(G_2,\ast_2)$$\phi:G_1\rightarrow G_2$$\phi(x\ast_1y)=\phi(x)\ast_2\phi(y)$$x,y$$G_1$

Nem todos os grupos da mesma ordem são isomórficos. Por exemplo, o grupo Klein é um grupo de ordem 4 que não é isomórfico para .$(C_4,+_4)$

Tarefa

Escreva um programa ou função que aceite um número inteiro não negativo n como entrada e imprima ou retorne o número de grupos não isomórficos da ordem n .

Casos de teste

Input   Output
0       0
1       1
2       1
3       1
4       2
5       1
6       2
7       1
8       5
9       2
10      2
11      1
12      5
13      1
14      2
15      1
16      14
17      1
18      5
19      1
20      5

(extraído do OEIS A000001 )

Regras adicionais

• Não há limites para o tempo de execução ou uso da memória.

• Built-ins que trivializam essa tarefa, como o Mathematica FiniteGroupCount, não são permitidos.

• Aplicam-se as regras padrão de código de golfe .

CJam, 189 187 bytes

Será difícil explicar isso ... A complexidade do tempo é garantida O(scary).

qi:N_3>{,aN*]N({{:L;N,X)-e!{X)_@+L@@t}%{X2+<z{_fe=:(:+}%:+!},}%:+}fX{:G;N3m*{_~{G@==}:F~F\1m>~F\F=}%:*},:L,({LX=LX)>1$f{\_@a\a+Ne!\f{\:M;~{M\f=z}2*\Mff==}:|{;}|}\a+}fX]:~$e`{0=1=},,}{!!}?

Se você é corajoso o suficiente, tente online . No meu laptop de baixa qualidade, consigo até 6 com o interpretador Java ou 5 no interpretador online.

Explicação

Eu não tenho um grande conhecimento em matemática (acabei de terminar o ensino médio, começando o CS na universidade na próxima semana). Portanto, tenha paciência comigo se eu cometer erros, declarar o óbvio ou fazer coisas de maneiras terrivelmente ineficientes.

Minha abordagem é uma força bruta, embora eu tenha tentado torná-la um pouco mais inteligente. Os principais passos são:

1. Gere todos os operandos possíveis ∗ para um grupo de ordem n (ou seja, enumere todos os grupos de ordem n );
2. Gere todas as possíveis bijections φ entre dois grupos de ordem n ;
3. Usando os resultados das etapas 1 e 2, determine todos os isomorfismos entre dois grupos de ordem n ;
4. Usando o resultado da etapa 3, conte o número de grupos até o isomorfismo.

Antes de analisar como cada etapa é executada, vamos obter um código trivial:

qi:N_             e# Get input as integer, store in N, make a copy
     3>{...}    ? e# If N > 3, do... (see below)
            {!!}  e# Else, push !!N (0 if N=0, 1 otherwise)

O algoritmo a seguir não funciona corretamente com n <4 , os casos de 0 a 3 são tratados com uma dupla negação.

A partir de agora, os elementos de um grupo serão escritos como {1, a, b, c, ...} , onde 1 é o elemento de identidade. Na implementação do CJam, os elementos correspondentes são {0, 1, 2, 3, ...} , em que 0 é o elemento de identidade.

Vamos começar da etapa 1. Escrever todos os operadores possíveis para um grupo de pedidos n é equivalente a gerar todas as tabelas n × n Cayley válidas . A primeira linha e coluna são triviais: ambas são {1, a, b, c, ...} (da esquerda para a direita, de cima para baixo).

      e# N is on the stack (duplicated before the if)
,a    e# Generate first row [0 1 2 3 ...] and wrap it in a list
  N*  e# Repeat row N times (placeholders for next rows)
    ] e# Wrap everything in a list
      e# First column will be taken care of later

Saber que uma tabela Cayley também é um quadrado latino reduzido (devido à propriedade de cancelamento) permite gerar as tabelas possíveis linha por linha. A partir da segunda linha (índice 1), geramos todas as permutações exclusivas para essa linha, mantendo a primeira coluna fixa ao valor do índice.

N({                                 }fX e# For X in [0 ... N-2]:
   {                            }%      e#   For each table in the list:
    :L;                                 e#     Assign the table to L and pop it off the stack
       N,                               e#     Push [0 ... N-1]
         X)                             e#     Push X+1
           -                            e#     Remove X+1 from [0 ... N-1]
            e!                          e#     Generate all the unique permutations of this list
              {         }%              e#     For each permutation:
               X)_                      e#       Push two copies of X+1
                  @+                    e#       Prepend X+1 to the permutation
                    L@@t                e#       Store the permutation at index X+1 in L
                          {...},        e#     Filter permutations (see below)
                                  :+    e#   Concatenate the generated tables to the table list

Nem todas essas permutações são válidas, é claro: cada linha e coluna deve conter todos os elementos exatamente uma vez. Um bloco de filtro é usado para esse fim (um valor verdadeiro mantém a permutação, um falso remove-o):

X2+                 e# Push X+2
   <                e# Slice the permutations to the first X+2 rows
    z               e# Transpose rows and columns
     {        }%    e# For each column:
      _fe=          e#   Count occurences of each element
          :(        e#   Subtract 1 from counts
            :+      e#   Sum counts together
                :+  e# Sum counts from all columns together
                  ! e# Negate count sum:
                    e#   if the sum is 0 (no duplicates) the permutation is kept
                    e#   if the sum is not zero the permutation is filtered away

Observe que estou filtrando dentro do loop de geração: isso torna o código um pouco mais longo (comparado à geração e filtragem distintas), mas melhora muito o desempenho. O número de permutações de um conjunto de tamanho n é n!, portanto, a solução mais curta exigiria muita memória e tempo.

Uma lista de tabelas Cayley válidas é um ótimo passo para enumerar os operadores, mas, sendo uma estrutura 2D, ela não pode verificar a associatividade, que é uma propriedade 3D. Portanto, o próximo passo é filtrar as funções não associativas.

{                                 }, e# For each table, keep table if result is true:
 :G;                                 e#   Store table in G, pop it off the stack
    N3m*                             e#   Generate triples [0 ... N-1]^3
        {                     }%     e#   For each triple [a b c]:
         _~                          e#     Make a copy, unwrap top one
           {    }:F                  e#     Define function F(x,y):
            G@==                     e#       x∗y (using table G)
                   ~F                e#     Push a∗(b∗c)
                     \1m>            e#     Rotate triple right by 1
                         ~           e#     Unwrap rotated triple
                          F\F        e#     Push (a∗b)∗c
                             =       e#     Push 1 if a∗(b∗c) == (a∗b)∗c (associative), 0 otherwise
                                :*   e#   Multiply all the results together
                                     e#   1 (true) only if F was associative for every [a b c]

Ufa! Muito trabalho, mas agora enumeramos todos os grupos de ordem n (ou melhor, as operações nele - mas o conjunto é fixo, por isso é a mesma coisa). Próximo passo: encontre isomorfismos. Um isomorfismo é uma bijeção entre dois desses grupos, de modo que φ (x ∗ y) = φ (x) ∗ φ (y) . Gerar essas bijections no CJam é trivial: Ne!fará isso. Como podemos verificá-los? Minha solução começa com duas cópias da tabela Cayley para xy . Em uma cópia, φ é aplicado a todos os elementos, sem tocar na ordem das linhas ou colunas. Isso gera a tabela para φ (x ∗ y) . Por outro, os elementos são deixados como estão, mas as linhas e colunas são mapeadas através de φ . Ou seja, a linha / colunax se torna a linha / coluna φ (x) . Isso gera a tabela para φ (x) ∗ y (y) . Agora que temos as duas tabelas, basta compará-las: se são iguais, encontramos um isomorfismo.

Obviamente, também precisamos gerar os pares de grupos para testar o isomorfismo. Precisamos de todas as 2 combinações dos grupos. Parece que o CJam não tem operador para combinações. Podemos gerá-los pegando cada grupo e combinando-o apenas com os elementos a seguir na lista. Curiosidade: o número de 2 combinações é n × (n - 1) / 2 , que também é a soma dos primeiros n - 1 números naturais. Esses números são chamados de números triangulares: tente o algoritmo no papel, uma linha por elemento fixo, e você verá o porquê.

:L                          e# List of groups is on stack, store in L
  ,(                        e# Push len(L)-1
    {                  }fX  e# For X in [0 ... len(L)-2]:
     LX=                    e#   Push the group L[X]
        LX)>                e#   Push a slice of L excluding the first X+1 elements
            1$              e#   Push a copy of L[X]
              f{...}        e#   Pass each [L[X] Y] combination to ... (see below)
                            e#   The block will give back a list of Y for isomorphic groups
                    \a+     e#   Append L[X] to the isomorphic groups
                          ] e# Wrap everything in a list

O código acima corrige o primeiro elemento do par, L [X] , e o combina com outros grupos (vamos chamar cada um desses Y ). Passa o par para um bloco de teste de isomorfismo que mostrarei em um momento. O bloco dá uma lista de valores de Y para o qual L [X] é isomorfa a Y . Então L [X] é anexado a esta lista. Antes de entender por que as listas são configuradas dessa maneira, vejamos o teste de isomorfismo:

\_@                                      e# Push a copy of Y
   a\a+                                  e# L[X] Y -> [L[X] Y]
       Ne!                               e# Generate all bijective mappings
          \f{                    }       e# For each bijection ([L[X] Y] extra parameter):
             \:M;                        e#   Store the mapping in M, pop it off the stack
                 ~                       e#   [L[X] Y] -> L[X] Y
                  {     }2*              e#   Repeat two times (on Y):
                   M\f=                  e#     Map rows (or transposed columns)
                       z                 e#     Transpose rows and columns
                                         e#     This generates φ(x) ∗ φ(y)
                           \Mff=         e#   Map elements of L[X], generates φ(x ∗ y)
                                =        e#   Push 1 if the tables are equal, 0 otherwise
                                  :|     e#   Push 1 if at least a mapping was isomorphic, 0 otherwise
                                    {;}| e#   If no mapping was isomorphic, pop the copy of Y off the stack

Ótimo, agora temos uma lista de conjuntos como [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . A idéia aqui é que, por propriedade transitiva, se quaisquer dois conjuntos tiverem pelo menos um elemento em comum, todos os grupos nos dois conjuntos serão isomórficos. Eles podem ser agregados em um único conjunto. Como L [X] nunca aparecerá nas combinações geradas por L [X + ...] , após a agregação de cada conjunto de isomorfismos haverá um elemento único. Portanto, para obter o número de isomorfismos, basta contar quantos grupos aparecem exatamente uma vez em todos os conjuntos de grupos isomórficos. Para fazer isso, desembrulhei os conjuntos para que eles se pareçam com [L [0], Y1, Y2, ..., L [1], Y1, ...] , classifique a lista para criar agrupamentos do mesmo grupo e, finalmente, Codifique-RLE.

:~            e# Unwrap sets of isomorphic groups
  $           e# Sort list
   e`         e# RLE-encode list
     {    },  e# Filter RLE elements:
      0=      e#   Get number of occurrences
        1=    e#   Keep element if occurrences == 1
            , e# Push length of filtered list
              e# This is the number of groups up to isomorphism

Isso é tudo, pessoal.

CJam, 73 bytes

0ri:Re!Rm*{:Tz0=R,=[R,Te_]m!{~ff{T==}e_}/=&},{:T,e!{:PPff{T==P#}}%$}%Q|,+

A complexidade de tempo do código acima é pior que O (n! ^N ) .

A entrada n = 4 já é demais para o intérprete online .

Usando o interpretador Java , a entrada n = 5 pode ser possível se você tiver RAM e paciência suficientes.

Localizando grupos

Dado um grupo (G, ∗) de ordem n , podemos escolher uma bijeção arbitrária φ: G -> C _{n de} modo que φ (e) = 0 .

φ irá tornar-se um isomorfismo de (L, *) e (C _n , * ') se definirmos *' por x *' y = φ (φ ^-1 (x) * φ ^-1 (y)) .

Isso significa que basta estudar todos os operadores do grupo em C _{n, de} modo que 0 seja o elemento neutro.

Representaremos um operador de grupo ∗ em C _n por uma matriz retangular T de dimensões n × n, de modo que T [x] [y] = x ∗ y .

Para gerar essa matriz, podemos começar escolhendo uma permutação de C _n para cada um de seus n linhas.

Dessa forma, 0 estará presente em todos os linhas (mas não necessariamente em todas as colunas ), o que significa que a terceira condição (existência de uma inversa) será atendida, qualquer que seja e .

Podemos corrigir e = 0 exigindo que a primeira coluna de T seja igual a C _n . Em particular, a segunda condição (existência de um elemento neutro) será mantida.

Para verificar se T corresponde a um operador de grupo, basta verificar se a primeira condição (associatividade) é válida. Isso pode ser feito exaustivamente, verificando se T [T [x] [y]] [z] == T [x] [T [y] [z]] para todos x, y, z em C _n .

Contando grupos não isomórficos

O método acima para encontrar grupos produzirá alguns grupos isomórficos. Em vez de identificar quais são isomórficos, geramos a família de todos os grupos isomórficos para cada um deles.

Isso pode ser feito iterando sobre todas as bijections φ: C _n -> C _n e determinando a matriz associada Tφ , definida por Tφ [x] [y] = φ ^-1 (T [φ (x)] [φ (y )]) .

Tudo o que resta a fazer é contar o número de famílias distintas.

O que o código faz

0         e# Push 0. For input 0, the remaining code will crash, leaving
          e# this 0 on the stack.
ri:R      e# Read an integer from STDIN and save it in R.
e!        e# Push all permutations of [0 ... R-1].
Rm*       e# Push all arrays of 6 permutations of [0 ... R-1].
{         e# Filter; for each array:
  :T      e#   Save it in T.
  z0=R,=  e#   Check if the first column equals [0 ... R-1].
  [R,Te_] e#   Push [0 ... R-1] and a flattened T.
  m!{     e#   For both pairs (any order):
    ~     e#     Unwrap the pair.
    ff{   e#     For each X in the first: For each Y in the second:
      T== e#       Push T[X][Y].
    }     e#
  }/      e#
  =       e#   Check for equality, i.e., associativity.
  &       e#   Bitwise AND with the previous Boolean
},        e# Keep T iff the result was truthy.
{         e# For each kept array:
  :T      e#   Save it in T
  ,e!     e#   Push all permutations of [0 ... R-1].
  {       e#   For each permutation:
    :PP   e#     Save it in P. Push a copy.
    ff{   e#     For each X in P: For each Y in P:
      T== e#       Push T[X][Y].
      P#  e#       Find its index in P.
    }     e#
  }%      e#
  $       e#   Sort the results.
}%        e#
Q|,       e# Deduplicate and count.
+         e# Add the result to the 0 on the stack.

Python 2 , 515 507 bytes

• Economizou oito bytes graças a Dennis .

def F(n):
 def f(k,*s):n==len(set(s))and S.add(s);{k and f(~-k,j,*s)for j in I}
 def c(k,*G):k and{s in G or c(~-k,s,*G)for s in S}or(I in G)&all((o(x,y)in G)&any(I==o(z,x)for z in G)for x in G for y in G)and A.add(G)
 S=set();A=S-S;I=tuple(range(n));o=lambda x,y:tuple(y[x[j]]for j in I);i=lambda G,H:any(all(o(H[B[i]],H[B[j]])==H[B[[k for k in I if G[k]==o(G[i],G[j])][0]]]for i in I for j in I)for B in S);f(n);c(n);K=list(A);[G in K and{G!=H and i(G,H)and K.remove(H)for H in K}for G in A];return len(K)

Experimente online!

Utilizando a equivalência entre o número de subgrupos não isomórficos de ordem $n$ do $\ \Sigma_n$ e o número de classes de equivalência isomórfica de grupos finitos de ordem $n$.

Link para a versão detalhada .