De quel groupe abélien fini s'agit-il?

12

La description

Écrivez une fonction f(m, G)qui accepte comme arguments un mappage met un ensemble / liste d'entiers distincts et non négatifs G.

mdoit mapper des paires d'entiers dans Gde nouveaux entiers dans G. ( G, m) est garanti pour former un groupe abélien fini , mais tout élément de Gpeut être l'identité.

Il existe un théorème important qui dit:

[Chaque groupe abélien fini] est isomorphe à un produit direct de groupes cycliques d'ordre de puissance premier.

fdoit renvoyer une liste des principaux pouvoirs [p1, ... pn]dans l'ordre croissant de telle sorte queG est isomorphe à Z_p1 fois ... fois Z_pn

Exemples

  • f((a, b) → (a+b) mod 4, [0, 1, 2, 3])devrait revenir [4], car les paramètres décrivent le groupe Z 4 .

  • f((a, b) → a xor b, [0, 1, 2, 3])devrait revenir [2, 2], car les paramètres décrivent un groupe isomorphe à Z 2 × Z 2 .

  • f((a, b) → a, [9])devrait revenir [], car les paramètres décrivent le groupe trivial; c'est-à-dire le produit de groupes cycliques nuls.

  • Définissez mcomme suit:

    (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

    Puis f(m, [0, 1, ..., 80])devrait revenir [3, 3, 9], car ce groupe est isomorphe à Z 3 × Z 3 × Z 9

Règles

  • mpeut être soit une fonction (ou un pointeur de fonction vers une fonction) Int × Int → Int, soit un dictionnaire mappant des paires G × Gvers de nouveaux éléments de G.

  • fpeut prendre ses paramètres dans l'ordre inverse, c'est-à-dire que vous pouvez également l'implémenter f(G, m).

  • Votre implémentation devrait théoriquement fonctionner pour des entrées arbitrairement grandes, mais n'a pas besoin d'être réellement efficace.

  • Il n'y a aucune limitation à l'utilisation de modules intégrés de quelque nature que ce soit.

  • Les règles de code-golf standard s'appliquent. Le code le plus court en octets gagne.

Classement

Pour que votre score apparaisse sur le tableau, il doit être dans ce format:

# Language, Bytes

Afficher l'extrait de code

code-golf math abstract-algebra Lynn
la source
Si mest autorisé à être un dictionnaire, pourriez-vous également fournir les cas de test sous forme de dictionnaires?
Martin Ender
Je l'ai considéré, mais ils sont assez gros, en particulier le dernier cas (des milliers de paires clé-valeur), et je ne peux pas penser à un très bon format pour eux. Il est probablement plus facile pour les répondeurs de copier les définitions de fonction, puis de construire les dictionnaires eux-mêmes (avec quelque chose comme for a in G: for b in G: d[(a, b)] = m(a, b)).
Lynn
Je pense que c'est correct. Je n'arrive pas à comprendre votre pâte assez bien pour vérifier ce qui se passe, mais cela devrait le prouver: bpaste.net/show/5821182a9b48
Lynn
Pour vous aider à envelopper votre tête autour de lui: il fonctionne sur des nombres ternaires avec des trits au format AABC, les traitant comme des triplets (A, B, C), avec un module d'addition par paire (9, 3, 3).
Lynn
Oh, je viens de réaliser mon erreur (très stupide). Merci pour votre extrait!
flawr

Réponses:

5

Matlab, 326 octets

Avec une théorie de groupe, l'idée est assez simple: ici le TL; DR Calculer tous les ordres possibles des éléments du groupe. Ensuite, trouvez le plus grand sous-groupe d'un certain ordre de puissance principale et "factorisez" le groupe, rincez, répétez.

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)

Exemples d'entrées:

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;

Version golfée:

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
la source
1

GAP , 159 111 octets

GAP nous permet de construire simplement un groupe par une table de multiplication et de calculer ses invariants abéliens:

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;

L'ancienne version

Le groupe fini avec les générateurs G et les relations a * b = m (a, b) (pour tout a, b de G) est le groupe (G, m) avec lequel nous avons commencé. Nous pouvons le créer et calculer ses invariants abéliens avec 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;

Exemples

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;

Maintenant, nous pouvons faire:

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

En fait, nous ne sommes pas limités à l'utilisation de listes d'entiers. En utilisant le domaine correct, nous pouvons simplement utiliser le plus général:

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

Je peux donc essentiellement faire le deuxième exemple en utilisant que son groupe est isomorphe au groupe additif de l'espace vectoriel bidimensionnel sur le terrain avec 2 éléments:

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

Et les exemples restants:

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

Remarque additionnelle

Dans l'ancienne version, m n'avait pas besoin de définir une composition de groupe pour G. Si m (a, b) = m (a, c), cela signifie simplement que b = c. Nous pourrions donc faire ai(m1,[0..5])et ai(m3,[5..15]). La nouvelle version échouera horriblement dans ces cas, tout comme les deux versions si m renvoie des valeurs qui ne sont pas en G.

Si (G, m) n'est pas abélien, nous obtenons une description de sa version abélianisée, c'est son plus grand groupe de facteurs abéliens:

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

C'est ce qui AbelianInvariantsest habituellement utilisé, nous appellerions normalement AbelianInvariants(SymmetricGroup(4)).

La version golfée

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