dfedchenko 31 мая 2020 в 14:58

Как мужик квазигруппы искал (или Учи Python, а то будешь руками работать)

4 мин

3.9K

Совсем немного теории

Латинский квадрат — табличка, заполненная буквами так, что в каждой строке и в каждом столбце никакая не повторяется дважды.

$inline$	$inline$	$inline$
$inline$	$inline$	$inline$
$inline$	$inline$	$inline$

Такую таблицу называют еще таблицей умножения.Таким образом мы определили операцию умножения на упорядоченном множестве $\{A, B, C\}$ . Например, $A \times B = B$ или $B \times C = A$ . Умножение, заданное с помощью такой таблицы, как правило некоммутативно ( $A\times B \neq B \times A$ ). В дальнейшем, определяя элемент $A\times B$ по таблице, я буду смотреть пересечение сроки с порядковым номером элемента $inline$ и столбца с порядковым номером элемента $inline$ .

Латинский квадрат будем называть группой, если операция $\times$ ассоциативна, т.е. $A\times (B\times C) = (A\times B)\times C$ для всех возможных троек элементов. Приведенная выше таблица является групповой (хотите верьте, хотите проверьте). А вот латинский квадрат

$inline$	$inline$	$inline$
$inline$	$inline$	$inline$
$inline$	$inline$	$inline$

свойством ассоциативности не обладает (неассоциативный латинский квадрат будем называть квазигруппой). Действительно, $C\times (B\times A) = A$ , а $(C\times B)\times A = B$ . Далее идет сказ о том как мужик квазигруппы искал.

И совсем мало практики

Дальше изложение ведется с огромными пробелами, т.к. хочется показать нечто, не отвлекаясь пока на технические подробности. Внимание ко всем деталям потребует не одной статьи.

Рассмотрим множество перестановок на трех символах $\{0,1,2\}$ (вышмат, привет):

$inline$ , $inline$ , $inline$ , $inline$ , $inline$ , $inline$ .

Выпишем таблицу умножения (это всем хорошо известная группа $inline$ )

A B C D E F
B C A F D E
C A B E F D
D E F A B C
E F D C A B
F D E B C A

Напомню лишь как получить, например, элемент $B\times D$

$B\times D = 120\times 021 = 102=F$

0>0 0>1 0>0>1
1>2 1>2 1>2>0
2>1 2>0 2>1>2

Множество $\{A, B, C, D, E, F\}$ — группа, а $\{A, B, C\}$ — подгруппа. Элементы $inline$ , $inline$ и $inline$ обладают свойством $inline$ (элемент $inline$ является единицей группы). Осталось заметить, что если на множестве $Q = \{D, E, F\}$ ввести умножение по правилу

$X\circ Y = {\rm proj}(X\times Y), \,\, X, Y \in Q,$

${\rm proj}: A\mapsto D, B\mapsto E, C\mapsto F,$

то мы получим квазигруппу

D E F
F D E
E F D

Ура! Маленькая удача: у нас в кармане вполне конкретная квазигруппа, элементы которой составляют подмножество группы $inline$ . Идем дальше. Рассмотрим группу $inline$ . Давайте найдем все перестановки $X \in S_6$ со свойством $inline$ , где $inline$ — тождественная перестановка.

F=[]
A=[]
B=[]
C=[]
for i in range(720):
        A=list(G[i])
        B=list(Q[i])
        for k in range(6):
                C.append(A[B[k]])
        if C==[0, 1, 2, 3, 4, 5]:
                F.append(list(A))
                C=[]
        else:
                C=[]
d=len(F)
for j in range(d):
        print(str(F[j]))

Здесь G и Q — одинаковые списки, содержащие все 720 перестановок на 6 символах. Программа выдает следующий список перестановок (перестановки со свойством $inline$ будем называть инволюциями).

[3, 4, 5, 0, 1, 2]
[5, 1, 2, 3, 4, 0]
[0, 1, 2, 3, 4, 5]
[1, 0, 2, 3, 4, 5]
[0, 4, 5, 3, 1, 2]
[3, 1, 2, 0, 4, 5]
[2, 5, 0, 3, 4, 1]
[5, 3, 4, 1, 2, 0]
[0, 3, 4, 1, 2, 5]
[4, 1, 2, 5, 0, 3]
[0, 1, 4, 5, 2, 3]
[1, 0, 4, 5, 2, 3]
[4, 5, 2, 3, 0, 1]
[2, 3, 0, 1, 4, 5]
[0, 5, 2, 4, 3, 1]
[2, 4, 0, 3, 1, 5]
[0, 3, 5, 1, 4, 2]
[0, 4, 2, 5, 1, 3]
[0, 5, 3, 2, 4, 1]
[4, 1, 5, 3, 0, 2]
[4, 1, 3, 2, 0, 5]
[0, 1, 3, 2, 5, 4]
[1, 0, 3, 2, 5, 4]
[5, 2, 1, 4, 3, 0]
[0, 2, 1, 4, 3, 5]
[2, 1, 0, 4, 3, 5]
[0, 5, 4, 3, 2, 1]
[5, 4, 3, 2, 1, 0]
[0, 4, 3, 2, 1, 5]
[4, 3, 2, 1, 0, 5]
[0, 3, 2, 1, 5, 4]
[3, 2, 1, 0, 5, 4]
[0, 2, 1, 5, 4, 3]
[2, 1, 0, 5, 4, 3]
[0, 1, 5, 4, 3, 2]
[1, 0, 5, 4, 3, 2]
[4, 2, 1, 3, 0, 5]
[0, 2, 1, 3, 5, 4]
[2, 1, 0, 3, 5, 4]
[3, 5, 4, 0, 2, 1]
[5, 2, 1, 3, 4, 0]
[0, 2, 1, 3, 4, 5]
[2, 1, 0, 3, 4, 5]
[4, 5, 3, 2, 0, 1]
[5, 3, 2, 1, 4, 0]
[0, 3, 2, 1, 4, 5]
[3, 2, 1, 0, 4, 5]
[0, 1, 5, 3, 4, 2]
[1, 0, 5, 3, 4, 2]
[3, 4, 2, 0, 1, 5]
[4, 2, 1, 5, 0, 3]
[2, 4, 0, 5, 1, 3]
[5, 1, 3, 2, 4, 0]
[0, 1, 3, 2, 4, 5]
[1, 0, 3, 2, 4, 5]
[5, 1, 4, 3, 2, 0]
[0, 1, 4, 3, 2, 5]
[1, 0, 4, 3, 2, 5]
[3, 5, 2, 0, 4, 1]
[0, 5, 2, 3, 4, 1]
[3, 1, 4, 0, 2, 5]
[5, 4, 2, 3, 1, 0]
[0, 4, 2, 3, 1, 5]
[2, 3, 0, 1, 5, 4]
[3, 1, 5, 0, 4, 2]
[5, 1, 2, 4, 3, 0]
[0, 1, 2, 4, 3, 5]
[1, 0, 2, 4, 3, 5]
[4, 3, 5, 1, 0, 2]
[3, 1, 2, 0, 5, 4]
[0, 1, 2, 5, 4, 3]
[1, 0, 2, 5, 4, 3]
[2, 5, 0, 4, 3, 1]
[4, 1, 2, 3, 0, 5]
[0, 1, 2, 3, 5, 4]
[1, 0, 2, 3, 5, 4]

На этом мой программистский запал почти иссякает и я продолжаю работу в полуручном режиме. Из 76 инволюций я оставил только 36 (на то были свои причины). Перемножил их

#G*Q
Q=[[5, 2, 1, 3, 4, 0],
[0, 2, 1, 3, 4, 5],
[2, 1, 0, 3, 4, 5],
[4, 5, 3, 2, 0, 1],
[5, 3, 2, 1, 4, 0],
[0, 3, 2, 1, 4, 5],
[3, 2, 1, 0, 4, 5],
[0, 1, 5, 3, 4, 2],
[1, 0, 5, 3, 4, 2],
[3, 4, 2, 0, 1, 5],
[4, 2, 1, 5, 0, 3],
[2, 4, 0, 5, 1, 3],
[5, 1, 3, 2, 4, 0],
[0, 1, 3, 2, 4, 5],
[1, 0, 3, 2, 4, 5],
[5, 1, 4, 3, 2, 0],
[0, 1, 4, 3, 2, 5],
[1, 0, 4, 3, 2, 5],
[3, 5, 2, 0, 4, 1],
[0, 5, 2, 3, 4, 1],
[3, 1, 4, 0, 2, 5],
[5, 4, 2, 3, 1, 0],
[0, 4, 2, 3, 1, 5],
[2, 3, 0, 1, 5, 4],
[3, 1, 5, 0, 4, 2],
[5, 1, 2, 4, 3, 0],
[0, 1, 2, 4, 3, 5],
[1, 0, 2, 4, 3, 5],
[4, 3, 5, 1, 0, 2],
[3, 1, 2, 0, 5, 4],
[0, 1, 2, 5, 4, 3],
[1, 0, 2, 5, 4, 3],
[2, 5, 0, 4, 3, 1],
[4, 1, 2, 3, 0, 5],
[0, 1, 2, 3, 5, 4],
[1, 0, 2, 3, 5, 4]]
#
G=[[5, 2, 1, 3, 4, 0],
[0, 2, 1, 3, 4, 5],
[2, 1, 0, 3, 4, 5],
[4, 5, 3, 2, 0, 1],
[5, 3, 2, 1, 4, 0],
[0, 3, 2, 1, 4, 5],
[3, 2, 1, 0, 4, 5],
[0, 1, 5, 3, 4, 2],
[1, 0, 5, 3, 4, 2],
[3, 4, 2, 0, 1, 5],
[4, 2, 1, 5, 0, 3],
[2, 4, 0, 5, 1, 3],
[5, 1, 3, 2, 4, 0],
[0, 1, 3, 2, 4, 5],
[1, 0, 3, 2, 4, 5],
[5, 1, 4, 3, 2, 0],
[0, 1, 4, 3, 2, 5],
[1, 0, 4, 3, 2, 5],
[3, 5, 2, 0, 4, 1],
[0, 5, 2, 3, 4, 1],
[3, 1, 4, 0, 2, 5],
[5, 4, 2, 3, 1, 0],
[0, 4, 2, 3, 1, 5],
[2, 3, 0, 1, 5, 4],
[3, 1, 5, 0, 4, 2],
[5, 1, 2, 4, 3, 0],
[0, 1, 2, 4, 3, 5],
[1, 0, 2, 4, 3, 5],
[4, 3, 5, 1, 0, 2],
[3, 1, 2, 0, 5, 4],
[0, 1, 2, 5, 4, 3],
[1, 0, 2, 5, 4, 3],
[2, 5, 0, 4, 3, 1],
[4, 1, 2, 3, 0, 5],
[0, 1, 2, 3, 5, 4],
[1, 0, 2, 3, 5, 4]]
#
F=[]
H=[]
A=[]
B=[]
C=[]
q=len(Q)
for i in range(36):
        A=list(G[i])
        for j in range(q):
                B=list(Q[j])
                for k in range(6):
                        C.append(A[B[k]])
                F.append(list(C))
                C=[]
        H.append(list(F))
        F=[]

#for i in range(36):
for j in range(36):
        print(str(H[j]))
        #print('New line')

Самым сложным было запихать все в электронную таблицу. И вот! Он! Долгожданный результат!

Цветом отмечены квазигруппы. Я не комментирую более результат, т.к. получен он на коленке, по принципу «Пойди туда, не зная куда. Принеси то, не зная что (ну т.е. квазигруппу)». Далее можно брать группы $inline$ , где $inline$ — большое число. Однако, без теории вся эта деятельность бесперспективна.

Кое-что еще я рассказываю здесь и здесь.

Теги:

Хабы:

Как мужик квазигруппы искал (или Учи Python, а то будешь руками работать)

Публикации

Истории

Работа

Ближайшие события