Определить, образует ли (*,G) ассоциативную группу в теории групп

Question

Допустим, у меня есть группа G={a,b,e}, где a, b произвольные элементы, а e обозначает нейтральный элемент. Я придумал определенную таблицу Кейли и хочу проверить, правильно ли я сделал, проверив ассоциативность.

Это означает, что я хочу проверить для произвольных x,y,z в G, что x(yz)=(xy)z, потому что вручную я должен был бы проверить 3*3*3 = 27 случаев, что является просто орехами.

Я не слишком далеко продвинулся в своем кодировании, и я был бы благодарен за некоторые подсказки или изящные способы решения этой проблемы. Я новичок в Python, но у меня есть общее представление о циклах и функциях.

Моя идея программы:

Я определяю функцию, скажем, группу, которая принимает в качестве входных данных строку. Я добавляю строку с помощью функции.extend(string) в определенный список, который позволяет мне анализировать заданные входные данные один за другим.

С помощью оператора if можно сказать:

if checklist[0] == "a" and checklist[1] == "b":
    checklist.pop[0]
    checklist[0] = "e"

Я мог бы сначала удалить первую запись в списке, а затем заменить ее на желаемое новое значение. Я продолжал в том же духе, добавляя все больше и больше операторов if, и в конце рекурсивно вызывал мою функцию снова, и она заканчивалась бы, если бы длина моего контрольного списка была равна 1.

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

---

Пример кода (не полный, но концептуальный):

checklist = []

def group(abc):
    if len(checklist) == 1:
        return checklist
    else:
        checklist.extend(abc)
        if (checklist[0] == "a" and checklist[1] == "a"):
            checklist.pop(0)
            checklist[0] = "b"
        if (checklist[0] == "a" and checklist[1] == "b"):
            checklist.pop(0)
            checklist[0] = "e"
        if (checklist[0] == "a" and checklist[1] == "e"):
            checklist.pop(0)
            checklist[0] = "a"
        if (checklist[0] == "b" and checklist[1] == "a"):
            checklist.pop(0)
            checklist[0] == "e"
        if (checklist[0] == "b" and checklist[1] == "b"):
            checklist.pop(0)
            checklist[0] = "a"
        if (checklist[0] == "b" and checklist[1] == "e"):
            checklist.pop(0)
            checklist[0] = "b"
        if (checklist[0] == "e" and checklist[1] == "a"):
            checklist.pop(0)
            checklist[0] = "a"
        if (checklist[0] == "e" and checklist[1] == "b"):
            checklist.pop(0)
            checklist[0] = "b"
        if (checklist[0] == "e" and checklist[1] == "e"):
            checklist.pop(0)
            checklist[0] = "e"
        group(checklist)
        return checklist

Answer 1

Я бы просто использовал itertools.product генерировать каждую тройку элементов x, y, z вашей группы G и проверьте, что тройка ассоциативна.

Вы можете определить функцию, которая проверяет, является ли ваша групповая операция с определенной тройкой ассоциативной, и затем по очереди проверять каждую возможную тройку в группе. Если "associativity fails..." печатается, то G не является ассоциативным в вашей групповой операции.

import itertools

G = [0, 1, 2, 3, 4, 5] # or whatever your group might be

def is_associative(x, y, z):
    if (x*y)*z == x*(y*z):
        return True
    return False

xyz = itertools.product(G, repeat=3)

for three in xyz:
    if not is_associative(*three):
         print("associativity fails for %s, %s, %s") % three

Очевидно, что в определении is_associative, вы хотите заменить * с какой бы ни была ваша групповая операция.

Answer 2

То, что вы хотите, выглядит так:

def is_associative(m, G):
    return sum( [m(m(a,b),c)!=m(a,m(b,c)) for a in G for b in G for c in G])==0

где вы кормите его функцией m и списком G, где m:(G,G)->G

Где это может пойти плохо с произвольным m и G находится в (не) равенстве теста.

Давайте посмотрим, сможем ли мы сделать эту работу с (i,j,k) векторами и перекрестными произведениями в R^ 3

import numpy

def is_associative(m, equals, G):
    # count the unassociative triplets, return true if count is zero
    return sum( [\
                     not equals(m(m(a,b),c), m(a,m(b,c)) ) \
                     for a in G for b in G for c in G\
                 ])==0


# classic non-associative example in R^3

# G is 0 vector and unit vectors
G = [ [0,0,0], [1,0,0], [0,1,0], [0,0,1] ]

# m is cross product 
def m(a,b):
    return numpy.cross(a,b)

def vector_equals(a,b):
    return (a[0]==b[0]) and (a[1]==b[1]) and (a[2]==b[2])

for a in G:
    print a

print "Associative: "+str(is_associative(m, vector_equals, G))

Выходные данные: [0, 0, 0] [1, 0, 0] [0, 1, 0] [0, 0, 1] Ассоциативно: False

Возможно, вы захотите узнать, почему конечная группа не ассоциативна, поэтому мы можем немного изменить ситуацию, чтобы выполнить это следующим образом:

Во-первых, мы определим функцию test_associative, которая возвращает не только истину / ложь, но и триплеты, которые вызывают ее ложь. Затем мы позвоним и распакуем результаты.

импорт NumPy

def test_associative(m, equals, G):
    # find the unassociative triplets
    # return (true,[]) if count is zero
    # return (false, array_of_unassociative_triplets)
    unassociative_triplets = [ (a,b,c)\
                     for a in G for b in G for c in G\
                     if not equals(m(m(a,b),c), m(a,m(b,c)) ) \
                 ]
    return (len(unassociative_triplets)==0, unassociative_triplets)


# classic non-associative example in R^3

# G is 0 vector and unit vectors
G = [ [0,0,0], [1,0,0], [0,1,0], [0,0,1] ]

# m is cross product 
def m(a,b):
    return numpy.cross(a,b)

def vector_equals(a,b):
    return (a[0]==b[0]) and (a[1]==b[1]) and (a[2]==b[2])

print "Elements of G:"

for a in G:
    print a

print "m() is the vector cross product x"

(is_associative, whynot) = test_associative(m, vector_equals, G)

print "Associative: "+str(is_associative)

if not is_associative:
    print "Non-associative triplets:"
    for triplet in whynot:
        print str(triplet)+\
            " (a*b)*c : "+str(m(m(triplet[0],triplet[1]), triplet[2]))+\
            " a*(b*c) : "+str(m(triplet[0],m(triplet[1], triplet[2])))

Выход:

Elements of G:
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
m() is the vector cross product x
Associative: False
Non-associative triplets:
([1, 0, 0], [1, 0, 0], [0, 1, 0]) (a*b)*c : [0 0 0] a*(b*c) : [ 0 -1  0]
([1, 0, 0], [1, 0, 0], [0, 0, 1]) (a*b)*c : [0 0 0] a*(b*c) : [ 0  0 -1]
([1, 0, 0], [0, 1, 0], [0, 1, 0]) (a*b)*c : [-1  0  0] a*(b*c) : [0 0 0]
([1, 0, 0], [0, 0, 1], [0, 0, 1]) (a*b)*c : [-1  0  0] a*(b*c) : [0 0 0]
([0, 1, 0], [1, 0, 0], [1, 0, 0]) (a*b)*c : [ 0 -1  0] a*(b*c) : [0 0 0]
([0, 1, 0], [0, 1, 0], [1, 0, 0]) (a*b)*c : [0 0 0] a*(b*c) : [-1  0  0]
([0, 1, 0], [0, 1, 0], [0, 0, 1]) (a*b)*c : [0 0 0] a*(b*c) : [ 0  0 -1]
([0, 1, 0], [0, 0, 1], [0, 0, 1]) (a*b)*c : [ 0 -1  0] a*(b*c) : [0 0 0]
([0, 0, 1], [1, 0, 0], [1, 0, 0]) (a*b)*c : [ 0  0 -1] a*(b*c) : [0 0 0]
([0, 0, 1], [0, 1, 0], [0, 1, 0]) (a*b)*c : [ 0  0 -1] a*(b*c) : [0 0 0]
([0, 0, 1], [0, 0, 1], [1, 0, 0]) (a*b)*c : [0 0 0] a*(b*c) : [-1  0  0]
([0, 0, 1], [0, 0, 1], [0, 1, 0]) (a*b)*c : [0 0 0] a*(b*c) : [ 0 -1  0]

Использование таблицы умножения вместо функции - это просто вопрос выражения таблицы в виде массива python и поиска m результата в массиве. Python индексирует массивы с целыми числами от 0 до length-1, и вы можете иметь массивы внутри массивов. Вам понадобится изоморфизм между вашей конечной группой G и {0,1,..., ||G||-1}