Menghitung Moufang Loops

17

Loop adalah struktur aljabar yang cukup sederhana. Ini adalah tuple (G, +) di mana G adalah satu set dan + adalah operator biner G × G → G . Yaitu + mengambil dua elemen dari G dan mengembalikan elemen baru. Operator juga harus memenuhi dua properti

  • Pembatalan: Untuk setiap a dan b di G terdapat unik x dan y di G sedemikian rupa

    a + x = b
    y + a = b
    
  • Identitas: Ada e dalam G sedemikian rupa sehingga untuk setiap a dalam G

    e + a = a
    a + e = a
    

Jika Anda terbiasa dengan konsep grup, Anda mungkin memperhatikan bahwa loop hanyalah grup yang tidak memiliki properti asosiatif.

Loop sangat sederhana sehingga orang ingin menambahkan lebih banyak aturan untuk membuat struktur baru yang lebih menarik. Salah satu struktur tersebut adalah loop Moufang yang merupakan loop yang juga memenuhi empat identitas berikut untuk semua x , y dan z dalam G

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

Sebagai contoh, tabel Cayley berikut mewakili loop Moufang:

0  1  2  3
1  0  3  2
2  3  0  1
3  2  1  0

(Jika Anda tidak terbiasa tabel Cayley adalah matriks persegi M di mana M i, j sama dengan i + j . Ini adalah cara praktis untuk mewakili operator biner pada suatu set.)

Kita dapat menunjukkan bahwa ada identitas dengan mudahnya 0. Pembatalan agak sulit untuk ditunjukkan tetapi pendekatan brute force menghasilkan tabel ini

b a → 0 1 2 3
↓
0     0 1 2 3
1     1 0 3 2
2     2 3 0 1
3     3 2 1 0

Di mana elemen kami adalah solusi untuk

a + x = b = x + a

(Anda mungkin memperhatikan bahwa tabel ini identik dengan tabel Cayley kami. Saya akan membiarkannya sebagai latihan bagi pembaca untuk mencari tahu mengapa ini terjadi pada loop Moufang ini)

Sekarang kita perlu memverifikasi identitas Moufang untuk struktur kita. Ada dua cara untuk melakukan ini untuk struktur tertentu cara pertama adalah untuk menyadari bahwa itu asosiatif dan dengan demikian secara otomatis memenuhi kriteria, namun ini tidak akan berfungsi secara umum sehingga kami lebih suka dengan kasar memaksakan hasilnya. Ada 3 variabel bebas masing-masing dengan potensi 4 nilai di setiap ekspresi di sini. Ini berarti kita harus melakukan perhitungan 7 * 4 3 atau 448. Saya akan meninggalkan perhitungan mentah, tetapi di sini ada beberapa Haskell yang dapat Anda gunakan untuk memverifikasi ini .

Tugas

Diberikan bilangan bulat positif n sebagai input output jumlah loop Moufang yang memiliki urutan n . (urutan grup adalah ukuran set)

Ini adalah sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.

Uji kasus

Berikut adalah jumlah loop Moufang untuk 71 input pertama

1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1
Posting Rock Garf Hunter
sumber
1
Apa itu " G × G "?
Erik the Outgolfer
8
Saya menurunkan tantangan ini, karena matematika yang terlibat cukup lembut dan tidak dapat diakses oleh semua orang yang membaca tantangan ini. Mungkin, contoh yang berhasil akan sangat membantu (seperti, menjelaskan mengapa input ke-8 menghasilkan angka 5)? Jika Anda menambahkan satu, saya pikir saya akan menarik kembali suara saya, tetapi tentu saja itu terserah Anda.
6
@ IanGödel Bisakah Anda menjelaskan apa yang Anda maksud dengan lembut? Ini tentu saja merupakan topik matematika yang lebih maju tetapi saya tidak berpikir bahwa kita harus menghindar dari matematika di PPCG. Saya akan menambahkan contoh loop Moufang yang berhasil, tetapi menghitung seluruh input dengan tangan mungkin akan mengacaukan tantangan.
Post Rock Garf Hunter
2
@WheatWizard "Fluffy" seperti pada, mungkin, "Advanced". EDIT: Saya menarik kembali downvote, tetapi masih menunggu contoh.
1
@ Giuseppe Jangan merasa terlalu buruk, saya juga membuat kesalahan ketika mengoreksi Anda 12tidak 11. Aku seharusnya menyadari itu karena 11bilangan prima.
Post Rock Garf Hunter

Jawaban:

4

Python 3 , 475 410 byte

Terima kasih kepada Mr.Xcoder untuk menghemat beberapa byte!

Gunakan simetri rumus untuk menghemat 65 byte. Ya itu banyak.

from itertools import*
n=int(input())
P=permutations
R=[*range(n)]
u=[]
A=all
S=sorted
for T in P(P(R),n):u+=[T]*(A(A(R==S(x)for x in
t)and any([*x]==S(x)for x in t)and
A(t[z][t[x][t[z][y]]]==t[t[t[z][x]][z]][y]and
t[t[z][x]][t[y][z]]==t[t[z][t[x][y]]][z]for x in R
for y in R for z in R)for t
in(T,[*zip(*T)]))and A(A(1-A(p[T[i][j]]==U[p[i]][p[j]]for i in R
for j in R)for p in P(R))for U in u))
print(len(u))

Cobalah online!


Beberapa anddapat diganti dengan *, menghasilkan bytecount yang lebih rendah tetapi dengan biaya waktu eksekusi yang jauh lebih lambat:

Python 3 , ??? byte

[TODO menaruh kode di sini]

(tentu saja tidak semua *membuat program lebih lambat secara signifikan, hanya beberapa dari mereka yang kritis)


Tidak Disatukan:

from itertools import *
n = 4 # int(input())
rangeN = list(range(n))

def is_moufang_loop(T):
    A = tuple(zip(*T))
    return all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        and all(
                T[z][T[x][T[z][y]]] == T[T[T[z][x]][z]][y]
            and T[T[z][x]][T[y][z]] == T[T[z][T[x][y]]][z]
            for x in rangeN for y in rangeN for z in rangeN)
        for t in (T, A)
    )

def isomorphic(loop1, loop2):
    for p in permutations(rangeN):
        if all(
            p[loop1[i][j]] == loop2[p[i]][p[j]]
            for i in rangeN
            for j in rangeN
        ): return True
    return False

unique_moufang_loops = []
for x in [
        cayley_table 
        for cayley_table in permutations(permutations(rangeN), n)
        if is_moufang_loop(cayley_table)
]:
    if all(not isomorphic(x, y) for y in unique_moufang_loops):
        unique_moufang_loops.append(x)

print(len(unique_moufang_loops))

Cobalah online!

Tidak ada bilah gulir ...


Penjelasan:

Programnya cukup sederhana.

  • Setiap "operator biner" yang memungkinkan diwakili oleh tabel Cayley (pengindeksan 0).
  • Properti "identitas" menyiratkan bahwa ada esedemikian rupa sehingga ebaris e'th dan kolom' th sama dengan [0, 1, 2, ..., n-1], yang merupakan kondisi yang sama dengan

    baik array Tdan transposnya memiliki baris sama dengan [0, 1, 2, ..., n-1].

  • Properti "pembatalan" setara dengan

    Setiap baris dan setiap kolom adalah permutasi dari [0, 1, 2, ..., n-1].

Jadi, bagiannya

all(
        all(sorted(x) == rangeN for x in t) 
        and any(list(x) == sorted(x) for x in t) 
        for t in (T, A))

kode memeriksa itu. (untuk semua baris dalam array Tdan transposnya A, yang diurutkan sama dengan rangeN, dan ada satu baris di keduanya Tdan Ayang sama dengan dirinya sedang diurutkan)

Keempat kondisi loop Moufang diperiksa secara manual.

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

Dalam kode, (a + b)direpresentasikan sebagai T[a][b]. (Karena representasi sebagai tabel Cayley). Gunakan perbandingan persamaan rantai Python untuk menghindari duplikasi (z + x) + (y + z).

Namun, karena rumusnya simetris:

Jika kita mengganti operan +dalam rumus pertama, kita mendapatkan rumus kedua; dan jika kita mengganti operan +pada rumus ketiga, kita mendapatkan rumus keempat dengan xdan ybertukar tempat.

Perhatikan bahwa transposisi tabel Cayley setara dengan operator biner yang operasinya di-swap. ( x + y -> y + x)

Akhirnya, semua kandidat meja Cayley diambil dari

permutations(permutations(rangeN), n) 

sehingga setiap baris adalah permutasi rangeN(yang [0, 1, 2, ..., n-1]) dan ada nbaris yang berbeda.

pengguna202729
sumber