Welche endliche abelsche Gruppe ist das?

12

Beschreibung

Schreiben Sie eine Funktion f(m, G), die als Argumente eine Zuordnung mund eine Menge / Liste unterschiedlicher, nicht negativer Ganzzahlen akzeptiert G.

msollte Paare von ganzen Zahlen Gauf neue ganze Zahlen in abbilden G. ( G, m) bildet garantiert eine endliche abelsche Gruppe , aber jedes Element von Gkann die Identität sein.

Es gibt einen wichtigen Satz, der besagt:

[Jede endliche abelsche Gruppe] ist isomorph zu einem direkten Produkt von zyklischen Gruppen der Primzahlordnung.

fmuss eine Liste der Hauptmächte [p1, ... pn]in aufsteigender Reihenfolge zurückgeben, so dassG ist isomorph zu Z_p1 mal ... mal Z_pn

Beispiele

  • f((a, b) → (a+b) mod 4, [0, 1, 2, 3])sollte zurückkehren [4], da die Parameter die Gruppe Z 4 beschreiben .

  • f((a, b) → a xor b, [0, 1, 2, 3])sollte zurückkehren [2, 2], da die Parameter eine Gruppe beschreiben, die zu Z 2 × Z 2 isomorph ist .

  • f((a, b) → a, [9])sollte zurückkehren [], da die Parameter die triviale Gruppe beschreiben; dh das Produkt von null cyclischen Gruppen.

  • Definieren Sie mwie folgt:

    (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

    Dann f(m, [0, 1, ..., 80])sollte zurückkehren [3, 3, 9], da diese Gruppe isomorph zu Z 3 × Z 3 × Z 9 ist

Regeln

  • mkann entweder eine Funktion (oder ein Funktionszeiger auf eine Funktion) Int × Int → Intoder ein Wörterbuch sein, das Paare G × Gauf neue Elemente von abbildet G.

  • fkann seine Parameter in umgekehrter Reihenfolge annehmen, dh Sie können auch implementieren f(G, m).

  • Ihre Implementierung sollte theoretisch für beliebig große Eingaben funktionieren, muss jedoch nicht effizient sein.

  • Es gibt keine Einschränkung für die Verwendung von integrierten Funktionen jeglicher Art.

  • Es gelten die Standardregeln für Code-Golf . Der kürzeste Code in Bytes gewinnt.

Bestenliste

Damit Ihre Partitur an der Tafel erscheint, sollte sie das folgende Format haben:

# Language, Bytes

Code-Snippet anzeigen

code-golf math abstract-algebra Lynn
quelle
Wenn mes sich um ein Wörterbuch handelt, können Sie die Testfälle auch als Wörterbücher bereitstellen?
Martin Ender
Ich habe darüber nachgedacht, aber sie sind ziemlich groß, insbesondere der letzte Fall (Tausende von Schlüssel-Wert-Paaren), und ich kann mir kein sehr gutes Format für sie vorstellen. Für die Antwortenden ist es wahrscheinlich einfacher, die Funktionsdefinitionen zu kopieren und dann die Wörterbücher selbst zu erstellen (mit so etwas wie for a in G: for b in G: d[(a, b)] = m(a, b)).
Lynn
Ich denke es ist richtig. Ich kann Ihre Paste nicht gut genug verstehen, um zu überprüfen, was los ist, aber dies sollte es beweisen: bpaste.net/show/5821182a9b48
Lynn
Um Ihren Kopf darum zu wickeln: Es verarbeitet ternäre Zahlen mit Triten im Format AABCund behandelt sie als Dreifache (A, B, C)mit paarweiser Addition modulo (9, 3, 3).
Lynn
Oh, ich habe gerade meinen (sehr dummen) Fehler bemerkt. Vielen Dank für Ihren Ausschnitt!
Fehler

Antworten:

5

Matlab, 326 Bytes

Mit etwas Gruppentheorie ist die Idee ganz einfach: Hier berechnet die TL; DR alle möglichen Ordnungen von Elementen der Gruppe. Finden Sie dann die größte Untergruppe einer bestimmten Primzahlordnung und "faktorisieren" Sie sie aus der Gruppe heraus, spülen Sie sie aus und wiederholen Sie sie.

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)

Beispieleingaben:

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;

Golfversion:

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)
fehlerhaft
quelle
1

GAP , 159 111 Bytes

Mit GAP können wir einfach eine Gruppe anhand einer Multiplikationstabelle erstellen und ihre abelschen Invarianten berechnen:

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;

Die alte Version

Die endlich präsentierte Gruppe mit den Generatoren G und den Beziehungen a * b = m (a, b) (für alle a, b von G) ist die Gruppe (G, m), mit der wir begonnen haben. Wir können es erstellen und seine abelschen Invarianten mit GAP berechnen:

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;

Beispiele

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;

Jetzt können wir tun:

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

Tatsächlich sind wir nicht darauf beschränkt, Listen von ganzen Zahlen zu verwenden. Mit der richtigen Domain können wir nur das allgemeine Plus verwenden:

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

Ich kann also im Wesentlichen das zweite Beispiel verwenden, indem ich verwende, dass seine Gruppe isomorph zu der additiven Gruppe des zweidimensionalen Vektorraums über dem Feld mit zwei Elementen ist:

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

Und die restlichen Beispiele:

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

Zusätzliche Bemerkungen

In der alten Version musste m keine Gruppenzusammensetzung für G definieren. Wenn m (a, b) = m (a, c), heißt das nur, dass b = c ist. Also konnten wir tun ai(m1,[0..5])und ai(m3,[5..15]). Die neue Version wird in diesen Fällen schrecklich fehlschlagen, ebenso wie beide Versionen, wenn m Werte zurückgibt, die nicht in G sind.

Wenn (G, m) nicht abelisch ist, erhalten wir eine Beschreibung der abelianisierten Version davon, dh der größten abelschen Faktorgruppe:

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

Dies ist, was AbelianInvariantsnormalerweise verwendet wird, wir würden normalerweise nur anrufen AbelianInvariants(SymmetricGroup(4)).

Die Golfversion

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