¿Qué grupo abeliano finito es este?

12

Descripción

Escriba una función f(m, G)que acepte como argumentos un mapeo my un conjunto / lista de enteros distintos y no negativos G.

mdebería asignar pares de enteros Ga nuevos enteros en G. ( G, m) está garantizado para formar un grupo abeliano finito , pero cualquier elemento Gpuede ser la identidad.

Hay un teorema importante que dice:

[Cada grupo abeliano finito] es isomorfo a un producto directo de grupos cíclicos de primer orden de potencia.

fdebe devolver una lista de potencias principales [p1, ... pn]en orden ascendente de modo queG es isomorfo a Z_p1 veces ... veces Z_pn

Ejemplos

  • f((a, b) → (a+b) mod 4, [0, 1, 2, 3])debería regresar [4], ya que los parámetros describen el grupo Z 4 .

  • f((a, b) → a xor b, [0, 1, 2, 3])debería regresar [2, 2], ya que los parámetros describen un grupo isomorfo a Z 2 × Z 2 .

  • f((a, b) → a, [9])debería regresar [], ya que los parámetros describen el grupo trivial; es decir, el producto de cero grupos cíclicos.

  • Definir de la msiguiente manera:

    (a, b) → (a mod 3 + b mod 3) mod 3
       + ((floor(a / 3) + floor(b / 3)) mod 3) * 3
       + ((floor(a / 9) + floor(b / 9)) mod 9) * 9

    Entonces f(m, [0, 1, ..., 80])debería regresar [3, 3, 9], ya que este grupo es isomorfo a Z 3 × Z 3 × Z 9

Reglas

  • mpuede ser una función (o un puntero de función a alguna función) Int × Int → Int, o un mapeo de diccionario se empareja G × Gcon nuevos elementos de G.

  • fpuede tomar sus parámetros en el orden opuesto, es decir, también puede implementarlos f(G, m).

  • Su aplicación debería teóricamente funciona para arbitrariamente grandes entradas, pero en realidad no necesita ser eficiente.

  • No hay limitación en el uso de incorporados de ningún tipo.

  • Se aplican reglas estándar de código de golf . El código más corto en bytes gana.

Tabla de clasificación

Para que su puntaje aparezca en el tablero, debe estar en este formato:

# Language, Bytes

Mostrar fragmento de código

code-golf math abstract-algebra Lynn
fuente
Si mse permite que sea un diccionario, ¿podría proporcionar los casos de prueba como diccionarios también?
Martin Ender
Lo consideré, pero son bastante grandes, especialmente el último caso (miles de pares clave-valor), y no puedo pensar en un formato muy bueno para ellos. Probablemente sea más fácil para los que responden copiar las definiciones de funciones y luego construir los propios diccionarios (con algo así como for a in G: for b in G: d[(a, b)] = m(a, b)).
Lynn
Creo que es correcto No puedo entender su pasta lo suficientemente bien como para verificar lo que está sucediendo, pero esto debería probarlo: bpaste.net/show/5821182a9b48
Lynn
Para ayudar a entenderlo: funciona con números ternarios con trits en el formato AABC, tratándolos como triples (A, B, C), con un módulo de suma por pares (9, 3, 3).
Lynn
Oh, me acabo de dar cuenta de mi error (muy estúpido). ¡Gracias por tu fragmento!
flawr

Respuestas:

5

Matlab, 326 bytes

Con algo de teoría de grupo, la idea es bastante simple: aquí el TL; DR Calcula todos los posibles órdenes de elementos del grupo. Luego encuentre el subgrupo más grande de un cierto orden de potencia principal y "factorícelo" fuera del grupo, enjuague, repita.

function r=c(h,l)

                            %factorize group order
N=numel(L);
f=factor(N);
P=unique(f);                %prime factors
for k=1:numel(P);
    E(k)=sum(f==P(k));    %exponents of unique factors
end;

                            %calculate the order O of each element
O=L*0-1; 
l=L;
for k=2:N+1;

    l=h(l,L);

    O(l==L & O<0)=k-1
end;

%%

O=unique(O);               % (optional, just for speedupt)
R=[];
                           % for each prime,find the highest power that
                           % divides any of the orders of the element, and
                           % each time substract that from the remaining
                           % exponent in the prime factorization of the
                           % group order
for p=1:nnz(P);                          % loop over primes
    while E(p)>1;                        % loop over remaining exponent
        for e=E(p):-1:1;                 % find the highest exponent
            B=mod(O,P(p)^e)==0;          
            if any(B)
                R=[R,P(p)^e];            % if found, add to list
                O(B)=O(B)/(P(p)^e);
                E(p)=E(p)-e;
                break;
            end;
        end;
    end;
    if E(p)==1;
        R=[R,P(p)];
    end;
end;
r=sort(R)

Entradas de ejemplo:

L = 0:3;
h=@(a,b)mod(a+b,4);
h=@(a,b)bitxor(a,b);
L = 0:80;
h=@(a,b)mod(mod(a,3)+mod(b,3),3)+mod(floor(a/3)+floor(b/3),3)*3+ mod(floor(a/9)+floor(b/9),9)*9;

Versión de golf:

function r=c(h,l);N=numel(L);f=factor(N);P=unique(f);for k=1:numel(P);E(k)=sum(f==P(k));end;O=L*0-1;l=L;for k=2:N+1;l=h(l,L);O(l==L&O<0)=k-1;end;R=[];for p=1:nnz(P);while E(p)>1;for e=E(p):-1:1;B=mod(O,P(p)^e)==0; if any(B);R=[R,P(p)^e]; O(B)=O(B)/(P(p)^e);E(p)=E(p)-e;break;end;end;end;if E(p)==1;R=[R,P(p)];end;end;r=sort(R)
falla
fuente
1

GAP , 159111 bytes

GAP nos permite simplemente construir un grupo mediante una tabla de multiplicar y calcular sus invariantes abelianos:

ai:=    # the golfed version states the function w/o assigning it
function(m,G)
  local t;
  t:=List(G,a->List(G,b->Position(G,m(a,b))));
  # t is inlined in the golfed version
  return AbelianInvariants(GroupByMultiplicationTable(t));
end;

La versión anterior

El grupo presentado finitamente con los generadores G y las relaciones a * b = m (a, b) (para todo a, b de G) es el grupo (G, m) con el que comenzamos. Podemos crearlo y calcular sus invariantes abelianos con GAP:

ai:=    # the golfed version states the function w/o assigning it
function(m,G)
  local F,n,rels;
  n:=Size(G);
  F:=FreeGroup(n);
  rels:=Union(Set([1..n],i->
                Set([1..n],j->
                  F.(i)*F.(j)/F.(Position(G,m(G[i],G[j]))) ) ));
  # rels is inlined in the golfed version
  return AbelianInvariants(F/rels);
end;

Ejemplos

m1:=function(a,b) return (a+b) mod 4; end;
# I don't feel like implementing xor
m3:=function(a,b) return 9; end;
m4:=function(a,b)
  return (a+b) mod 3 # no need for inner mod
         + ((QuoInt(a,3)+QuoInt(b,3)) mod 3) * 3
         + ((QuoInt(a,9)+QuoInt(b,9)) mod 9) * 9;
  end;

Ahora podemos hacer:

gap> ai(m1,[0..3]);
[ 4 ]

En realidad, no estamos restringidos a usar listas de enteros. Usando el dominio correcto, podemos usar el plus general:

ai(\+,List(Integers mod 4));
[ 4 ]

Así que esencialmente puedo hacer el segundo ejemplo usando que su grupo es isomorfo al grupo aditivo del espacio vectorial bidimensional sobre el campo con 2 elementos:

gap> ai(\+,List(GF(2)^2));
[ 2, 2 ]

Y los ejemplos restantes:

gap> ai(m3,[9]);
[  ]
gap> ai(m4,[0..80]);
[ 3, 3, 9 ]

Observaciones adicionales

En la versión anterior, m no necesitaba definir una composición de grupo para G. Si m (a, b) = m (a, c), eso solo dice que b = c. Entonces podríamos hacer ai(m1,[0..5])y ai(m3,[5..15]). La nueva versión fallará horrible en estos casos, al igual que ambas versiones si m devuelve valores que no están en G.

Si (G, m) no es abeliano, obtenemos una descripción de la versión abelianizada, ese es su mayor grupo de factores abelianos:

gap> ai(\*,List(SymmetricGroup(4)));
[ 2 ]

Esto es para lo AbelianInvariantsque usualmente se usa, normalmente solo llamaríamos AbelianInvariants(SymmetricGroup(4)).

La versión de golf

function(m,G)return AbelianInvariants(GroupByMultiplicationTable(List(G,a->List(G,b->Position(G,m(a,b))))));end
Christian Sievers
fuente