Grupos
En álgebra abstracta, un grupo es una tupla , donde es un conjunto y es una función tal que se cumple lo siguiente:
Para todos los en , .
Existe un elemento en G tal que para todas las x en G , x ∗ e = x .
Para cada en G , existe un elemento y en G tal que x ∗ y = e .
El orden de un grupo se define como el número de elementos de G .
Para cada entero estrictamente positivo , existe al menos un grupo de orden n . Por ejemplo, ( C n , + n ) es un grupo tal, donde C n = { 0 , . . . , n - 1 } y x + n y = ( x + y ) .
Grupos isomorfos
Deje y defina ∗ por x ∗ y = ( x × y ) . Entonces 1 ∗ 1 = 1 = 2 ∗ 2 y 1 ∗ 2 = 2 = 2 ∗ 1 .
Del mismo modo, y 0 + 2 1 = 1 = 1 + 2 0 .
Aunque los elementos y las operaciones de los grupos y ( C 2 , + 2 ) tienen nombres diferentes, los grupos comparten la misma estructura.
Se dice que dos grupos y ( G 2 , ∗ 2 ) son isomórficos si existe una biyección ϕ : G 1 → G 2 tal que ϕ ( x ∗ 1 y ) = ϕ ( x ) ∗ 2 ϕ ( y ) para todo x , y en G 1 .
No todos los grupos del mismo orden son isomorfos. Por ejemplo, el grupo Klein es un grupo de orden 4 que no es isomorfo a .
Tarea
Escriba un programa o función que acepte un número entero no negativo n como entrada e imprima o devuelva el número de grupos no isomórficos de orden n .
Casos de prueba
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
(tomado de OEIS A000001 )
Reglas adicionales
No hay límites en tiempo de ejecución o uso de memoria.
FiniteGroupCount
No se permiten las funciones integradas que trivializan esta tarea, como las de Mathematica .Aplican reglas estándar de código de golf .
fuente
monkeys_on_typewriters
cubre todo lo que no está cubierto por los documentos documentados.Respuestas:
CJam,
189187 bytesEsto va a ser difícil de explicar ... La complejidad del tiempo está garantizada
O(scary)
.Si eres lo suficientemente valiente, pruébalo en línea . En mi horrible computadora portátil, puedo obtener hasta 6 con el intérprete de Java o 5 en el intérprete en línea.
Explicación
No tengo una gran experiencia en matemáticas (acabo de terminar la escuela secundaria, comenzando CS en la universidad la próxima semana). Así que tengan paciencia conmigo si cometo errores, digo lo obvio o hago las cosas de maneras terriblemente ineficaces.
Mi enfoque es una fuerza bruta, aunque traté de hacerlo un poco más inteligente. Los pasos principales son:
Antes de ver cómo se realiza cada paso, eliminemos un código trivial:
El siguiente algoritmo no funciona correctamente con n <4 , los casos de 0 a 3 se manejan con una doble negación.
De ahora en adelante, los elementos de un grupo se escribirán como {1, a, b, c, ...} , donde 1 es el elemento de identidad. En la implementación de CJam, los elementos correspondientes son {0, 1, 2, 3, ...} , donde 0 es el elemento de identidad.
Comencemos por el paso 1. Escribir todos los operadores posibles para un grupo de orden n es equivalente a generar todas las tablas n × n Cayley válidas . La primera fila y la columna son triviales: ambas son {1, a, b, c, ...} (de izquierda a derecha, de arriba a abajo).
Saber que una tabla de Cayley también es un cuadrado latino reducido (debido a la propiedad de cancelación) permite generar las posibles tablas fila por fila. A partir de la segunda fila (índice 1), generamos todas las permutaciones únicas para esa fila, manteniendo la primera columna fija en el valor del índice.
No todas esas permutaciones son válidas, por supuesto: cada fila y columna debe contener todos los elementos exactamente una vez. Se utiliza un bloque de filtro para este propósito (un valor verdadero mantiene la permutación, un valor falso lo elimina):
Tenga en cuenta que estoy filtrando dentro del ciclo de generación: esto hace que el código sea un poco más largo (en comparación con la generación y el filtrado distintos), pero mejora enormemente el rendimiento. El número de permutaciones de un conjunto de tamaño. n es n! , por lo que la solución más corta requeriría mucha memoria y tiempo.
Una lista de tablas de Cayley válidas es un gran paso para enumerar los operadores, pero al ser una estructura 2D, no puede verificar la asociatividad, que es una propiedad 3D. Entonces, el siguiente paso es filtrar las funciones no asociativas.
¡Uf! Mucho trabajo, pero ahora hemos enumerado todos los grupos de orden n (o mejor, las operaciones en él, pero el conjunto es fijo, por lo que es lo mismo). Siguiente paso: encontrar isomorfismos. Un isomorfismo es una biyección entre dos de esos grupos de modo que φ (x ∗ y) = φ (x) ∗ φ (y) . Generar esas biyecciones en CJam es trivial:
Ne!
lo hará. ¿Cómo podemos verificarlos? Mi solución comienza con dos copias de la tabla de Cayley para x ∗ y . En una copia, φ se aplica a todos los elementos, sin tocar el orden de las filas o columnas. Esto genera la tabla para φ (x ∗ y) . En el otro, los elementos se dejan como están, pero las filas y columnas se asignan a través de φ . Es decir, la fila / columnax se convierte en la fila / columna φ (x) . Esto genera la tabla para φ (x) ∗ φ (y) . Ahora que tenemos las dos tablas, solo tenemos que compararlas: si son iguales, hemos encontrado un isomorfismo.Por supuesto, también necesitamos generar los pares de grupos para probar el isomorfismo. Necesitamos todas las 2 combinaciones de los grupos. Parece que CJam no tiene operador para las combinaciones. Podemos generarlos tomando cada grupo y combinándolo solo con los elementos que lo siguen en la lista. Dato curioso: el número de 2 combinaciones es n × (n - 1) / 2 , que también es la suma de los primeros n - 1 números naturales. Dichos números se llaman números triangulares: pruebe el algoritmo en papel, una fila por elemento fijo, y verá por qué.
El código anterior corrige el primer elemento del par, L [X] , y lo combina con otros grupos (llamemos a cada uno de esos Y ). Pasa el par a un bloque de prueba de isomorfismo que mostraré en un momento. El bloque devuelve una lista de valores de Y para los que L [X] es isomorfo a Y . Entonces L [X] se agrega a esta lista. Antes de entender por qué las listas están configuradas de tal manera, veamos la prueba de isomorfismo:
Genial, ahora tenemos una lista de conjuntos como [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . La idea aquí es que, por propiedad transitiva, si dos conjuntos tienen al menos un elemento en común, entonces todos los grupos en los dos conjuntos son isomórficos. Se pueden agregar en un solo conjunto. Como L [X] nunca aparecerá en las combinaciones generadas por L [X + ...] , después de agregar cada conjunto de isomorfismos tendrá un elemento único. Entonces, para obtener el número de isomorfismos, es suficiente contar cuántos grupos aparecen exactamente una vez en todos los grupos de grupos isomórficos. Para hacer esto, desenvuelvo los conjuntos para que se vean como [L [0], Y1, Y2, ..., L [1], Y1, ...] , clasifico la lista para crear grupos del mismo grupo y finalmente RLE-codificarlo.
Eso es todo amigos.
fuente
CJam, 73 bytes
La complejidad temporal del código anterior es peor que O (n! N ) .
La entrada n = 4 ya es demasiado para el intérprete en línea .
Usando el intérprete de Java , la entrada n = 5 podría ser posible, si tiene suficiente RAM y paciencia.
Encontrar grupos
Dado un grupo (G, ∗) de orden n , podemos elegir una biyección arbitraria φ: G -> C n tal que φ (e) = 0 .
φ se convertirá en un isomorfismo de (G, ∗) y (C n , ∗ ') si definimos ∗' por x ∗ 'y = φ (φ -1 (x) ∗ φ -1 (y)) .
Esto significa que es suficiente estudiar todos los operadores de grupo en C n de modo que 0 sea el elemento neutral.
Representaremos un operador de grupo ∗ en C n por una matriz rectangular T de dimensiones n × n tal que T [x] [y] = x ∗ y .
Para generar tal matriz, podemos comenzar eligiendo una permutación de C n para cada una de sus n filas.
De esta forma, 0 estará presente en todas las filas (pero no necesariamente en todas las columnas ), lo que significa que se cumplirá la tercera condición (existencia de un inverso), sea cual sea e .
Podemos arreglar e = 0 al requerir que la primera columna de T sea igual a C n . En particular, se mantendrá la segunda condición (existencia de un elemento neutral).
Para verificar que T corresponde a un operador de grupo, todo lo que queda por hacer es verificar que se cumpla la primera condición (asociatividad). Esto se puede hacer exhaustivamente comprobando que T [T [x] [y]] [z] == T [x] [T [y] [z]] para todos x, y, z en C n .
Contando grupos no isomórficos
El método anterior para encontrar grupos producirá algunos grupos isomórficos. En lugar de identificar cuáles son isomórficos, generamos la familia de todos los grupos isomórficos para cada uno de ellos.
Esto se puede lograr iterando sobre todas las biyecciones φ: C n -> C n , y determinando la matriz asociada Tφ , definida por Tφ [x] [y] = φ -1 (T [φ (x)] [φ (y )]) .
Todo lo que queda por hacer es contar el número de familias distintas.
Lo que hace el código
fuente
Python 2 ,
515507 bytesPruébalo en línea!
Usando la equivalencia entre el número de subgrupos de orden no isomórficosnorte de Σnorte y el número de clases de equivalencia isomorfas de grupos finitos de orden norte .
Enlace a la versión detallada .
fuente
s
y sonG
importantes? Si no, puede usardef f(k,*s):...f(~-k,j,*s)...
ydef c(k,*G):...c(~-k,s,*G)....
.