Que grupo abeliano finito é esse?

12

Descrição

Escreva uma função f(m, G)que aceite como argumentos um mapeamento me um conjunto / lista de números inteiros distintos e não negativos G.

mdeve mapear pares de números inteiros Gpara novos números inteiros em G. ( G, m) é garantido para formar um grupo abeliano finito , mas qualquer elemento de Gpode ser a identidade.

Existe um teorema importante que diz:

[Cada grupo abeliano finito] é isomórfico para um produto direto de grupos cíclicos de ordem de potência principal.

fdeve retornar uma lista de poderes principais [p1, ... pn]em ordem crescente, de modo queG é isomorfo a Z_p1 vezes ... vezes Z_pn

Exemplos

  • f((a, b) → (a+b) mod 4, [0, 1, 2, 3])deve retornar [4], pois os parâmetros descrevem o grupo Z 4 .

  • f((a, b) → a xor b, [0, 1, 2, 3])deve retornar [2, 2], pois os parâmetros descrevem um grupo isomórfico para Z 2 × Z 2 .

  • f((a, b) → a, [9])deve retornar [], pois os parâmetros descrevem o grupo trivial; isto é, o produto de grupos cíclicos zero.

  • Defina da mseguinte maneira:

    (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

    Em seguida, f(m, [0, 1, ..., 80])deve retornar [3, 3, 9], pois esse grupo é isomórfico para Z 3 × Z 3 × Z 9

Regras

  • mpode ser uma função (ou ponteiro de função para alguma função) Int × Int → Intou um mapeamento de dicionário associado G × Ga novos elementos de G.

  • fpode levar seus parâmetros na ordem oposta, ou seja, você também pode implementar f(G, m).

  • Teoricamente, sua implementação deve funcionar com entradas arbitrariamente grandes, mas na verdade não precisa ser eficiente.

  • Não há limitação no uso de built-ins de qualquer tipo.

  • Aplicam-se as regras de código-golfe padrão . O código mais curto em bytes vence.

Entre os melhores

Para que sua pontuação apareça no quadro, ela deve estar neste formato:

# Language, Bytes

Mostrar snippet de código

code-golf math abstract-algebra Lynn
fonte
Se mé permitido ser um dicionário, você também pode fornecer os casos de teste como dicionários?
Martin Ender
Eu considerei isso, mas eles são bem grandes, especialmente o último caso (milhares de pares de valores-chave), e não consigo pensar em um formato muito bom para eles. Provavelmente é mais fácil para os respondentes copiar as definições de função e construir os próprios dicionários (com algo parecido for a in G: for b in G: d[(a, b)] = m(a, b)).
21415 Lynn
Eu acho que está correto. Eu não posso fazer o sentido de sua pasta bem o suficiente para verificar o que está acontecendo, mas isso deve provar que: bpaste.net/show/5821182a9b48
Lynn
Para ajudar a entender: ele opera com números ternários com trits no formato AABC, tratando-os como triplos (A, B, C), com módulo de adição par a par (9, 3, 3).
21415 Lynn
Acabei de perceber meu erro (muito estúpido). Obrigado pelo seu snippet!
flawr

Respostas:

5

Matlab, 326 bytes

Com alguma teoria de grupo, a idéia é bastante simples: aqui o TL; DR Calcula todas as ordens possíveis de elementos do grupo. Em seguida, encontre o maior subgrupo de uma determinada ordem de potência principal e "fatorize" fora do grupo, enxágue e 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)

Exemplo de entradas:

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;

Versão Golfed:

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)
flawr
fonte
1

GAP , 159 111 bytes

O GAP nos permite simplesmente construir um grupo por uma tabela de multiplicação e calcular seus 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;

A versão antiga

O grupo finitamente apresentado com os geradores G e as relações a * b = m (a, b) (para todos a, b de G) é o grupo (G, m) com o qual começamos. Podemos criá-lo e calcular seus invariantes abelianos com o 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;

Exemplos

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;

Agora podemos fazer:

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

Na verdade, não estamos restritos a usar listas de números inteiros. Usando o domínio correto, podemos apenas usar o plus geral:

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

Então, eu posso essencialmente fazer o segundo exemplo usando que seu grupo é isomórfico ao grupo aditivo do espaço vetorial bidimensional sobre o campo com 2 elementos:

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

E os exemplos restantes:

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

Observações adicionais

Na versão antiga, m não precisava definir uma composição de grupo para G. Se m (a, b) = m (a, c), isso apenas indica que b = c. Então nós poderíamos fazer ai(m1,[0..5])e ai(m3,[5..15]). A nova versão falhará horrivelmente nesses casos, assim como as duas versões se m retornar valores que não estão em G.

Se (G, m) não é abeliano, obtemos uma descrição da versão abelianizada, que é seu maior grupo de fatores abelianos:

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

É para isso que AbelianInvariantsgeralmente é usado, normalmente chamaríamos apenas AbelianInvariants(SymmetricGroup(4)).

A versão golfada

function(m,G)return AbelianInvariants(GroupByMultiplicationTable(List(G,a->List(G,b->Position(G,m(a,b))))));end
Peneiradores cristãos
fonte