Kelompok abelian terbatas mana ini?

12

Deskripsi

Tulis fungsi f(m, G)yang menerima pemetaan sebagai argumen m, dan satu set / daftar bilangan bulat yang tidak negatif G.

mharus memetakan pasangan bilangan bulat Gke bilangan bulat baru di G. ( G, m) dijamin untuk membentuk grup abelian yang terbatas , tetapi elemen apa pun Gmungkin identitasnya.

Ada teorema penting yang mengatakan:

[Setiap grup abelian terbatas] adalah isomorfik untuk produk langsung dari grup siklik dari urutan daya prima.

fharus mengembalikan daftar kekuatan utama [p1, ... pn]dalam urutan naik sedemikian rupa sehinggaG isomorfik hingga Z_p1 kali ... kali Z_pn

Contohnya

  • f((a, b) → (a+b) mod 4, [0, 1, 2, 3])harus kembali [4], sebagai parameter menggambarkan kelompok Z 4 .

  • f((a, b) → a xor b, [0, 1, 2, 3])harus kembali [2, 2], karena parameter menggambarkan grup isomorfik hingga Z 2 × Z 2 .

  • f((a, b) → a, [9])harus kembali [], karena parameter menggambarkan kelompok sepele; yaitu, produk dari kelompok nol siklik.

  • Tetapkan msebagai berikut:

    (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

    Maka f(m, [0, 1, ..., 80])harus kembali [3, 3, 9], karena grup ini isomorfik hingga Z 3 × Z 3 × Z 9

Aturan

  • mdapat berupa fungsi (atau penunjuk fungsi ke beberapa fungsi) Int × Int → Int, atau pemetaan kamus berpasangan G × Gdengan elemen baru dari G.

  • fdapat mengambil parameternya dalam urutan yang berlawanan, yaitu Anda juga dapat menerapkan f(G, m).

  • Implementasi Anda secara teoritis harus bekerja untuk input besar secara sewenang-wenang, tetapi sebenarnya tidak perlu menjadi efisien.

  • Tidak ada batasan untuk menggunakan built-in dalam bentuk apa pun.

  • Aturan standar kode-golf berlaku. Kode terpendek dalam byte menang.

Papan peringkat

Agar skor Anda muncul di papan tulis, itu harus dalam format ini:

# Language, Bytes

Tampilkan cuplikan kode

code-golf math abstract-algebra Lynn
sumber
Jika mdiizinkan menjadi kamus, dapatkah Anda memberikan kasus uji sebagai kamus juga?
Martin Ender
Saya mempertimbangkannya, tetapi mereka cukup besar, terutama kasus terakhir (ribuan pasangan nilai kunci), dan saya tidak bisa memikirkan format yang sangat baik untuk mereka. Mungkin lebih mudah bagi penjawab untuk menyalin definisi fungsi, dan kemudian membangun kamus sendiri (dengan sesuatu seperti for a in G: for b in G: d[(a, b)] = m(a, b)).
Lynn
Saya pikir itu benar. Saya tidak dapat memahami pasta Anda dengan cukup baik untuk memverifikasi apa yang sedang terjadi, tetapi ini harus membuktikannya: bpaste.net/show/5821182a9b48
Lynn
Untuk membantu membungkus kepala Anda di sekitarnya: itu beroperasi pada nomor ternary dengan trit dalam format AABC, memperlakukan mereka sebagai tiga kali lipat (A, B, C), dengan tambahan modulo berpasangan (9, 3, 3).
Lynn
Oh, saya baru menyadari kesalahan (sangat bodoh) saya. Terima kasih atas cuplikan Anda!
flawr

Jawaban:

5

Matlab, 326 byte

Dengan beberapa teori grup, idenya cukup sederhana: Di sini TL; DR Hitung semua pesanan elemen yang mungkin dari grup. Kemudian temukan subkelompok terbesar dari urutan kekuatan utama tertentu dan "pisahkan" dari kelompok, bilas, ulangi.

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)

Input contoh:

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 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)
cacat
sumber
1

GAP , 159 111 byte

GAP memungkinkan kita untuk hanya membangun grup dengan tabel perkalian dan menghitung invarian abeliannya:

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;

Versi lama

Grup yang disajikan dengan generator G dan hubungan a * b = m (a, b) (untuk semua a, b dari G) adalah grup (G, m) yang kita mulai. Kita bisa membuatnya dan menghitung invarian abeliannya dengan 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;

Contohnya

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;

Sekarang kita bisa melakukan:

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

Sebenarnya, kami tidak dibatasi untuk menggunakan daftar bilangan bulat. Menggunakan domain yang benar, kita bisa menggunakan plus umum:

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

Jadi pada dasarnya saya dapat melakukan contoh kedua dengan menggunakan bahwa grupnya isomorfik ke grup aditif dari ruang vektor 2 dimensi di atas lapangan dengan 2 elemen:

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

Dan sisa contohnya:

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

Tanda tambahan

Dalam versi lama, m tidak perlu mendefinisikan komposisi grup untuk G. Jika m (a, b) = m (a, c), itu hanya mengatakan bahwa b = c. Jadi kita bisa melakukan ai(m1,[0..5])dan ai(m3,[5..15]). Versi baru akan gagal mengerikan dalam kasus ini, karena akan kedua versi jika m mengembalikan nilai yang tidak dalam G.

Jika (G, m) bukan abelian, kami mendapatkan deskripsi versi abelianasinya, itu adalah grup faktor abelian terbesarnya:

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

Ini AbelianInvariantsbiasanya digunakan untuk apa, biasanya kita sebut saja AbelianInvariants(SymmetricGroup(4)).

Versi golf

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