Как стать автором
Поиск
Написать публикацию
Обновить

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

Время на прочтение4 мин
Количество просмотров4.1K
Big Data*Python*Математика*
Совсем немного теории

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

$A$ $B$ $C$
$B$ $C$ $A$
$C$ $A$ $B$


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

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

$A$ $B$ $C$
$C$ $A$ $B$
$B$ $C$ $A$


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

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

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

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

$012=A$, $120=B$, $201=C$, $021=D$, $210=E$, $102=F$.

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

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\}$  — подгруппа. Элементы $D$, $E$ и $F$ обладают свойством $D^2 = E^2 = F^2=A$ (элемент $A$ является единицей группы). Осталось заметить, что если на множестве $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

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

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 символах. Программа выдает следующий список перестановок (перестановки со свойством $X^2 = E$ будем называть инволюциями).

[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')

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

image

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

Кое-что еще я рассказываю здесь и здесь.
Теги:
Хабы:
Всего голосов 5: ↑3 и ↓2+4
Комментарии8
0
Карма
0
Рейтинг
Дмитрий @dfedchenko

Пользователь

Отправить сообщение

Публикации

Работа

Data Scientist
48 вакансий
Django разработчик
19 вакансий
Python разработчик
66 вакансий

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

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr