pythonpython-3.xmathabstract-algebrafinite-group-theory

Group theory and Python


How do you write a Python code to check if the operation ∗ on the set {0,1,..,n−1} defined by a Cayley table is associative or not.

My attempted code is:

def is_associative_cayley_table(table):
    if not is_cayley_table(table):
        return False

    for i in range (0,len(table)):
        for j in range (0,len(table)):
            for k in range (0,len(table)):
                if (table[table[i][j])][k])==(table[i][(table[j][k])]):
                   print("Okay")
                else
                   return False

Solution

  • Instead of printing "Okay" n^3 times, you might just want to return the bool.

    def is_associative_cayley_table(table):
        if not is_cayley_table(table):
            return False
    
        for i in range (0,len(table)):
            for j in range (0,len(table)):
                for k in range (0,len(table)):
                    if (table[table[i][j])][k])!=(table[i][(table[j][k])]):
                       return False
        return True
    

    Also, there is no algorithm to check the associativity of a set, yet.
    You have to use brute-force.

    The best you can do is use Light's Associativity Test, which "does not improve the worst case runtime of O(n^3). It just simplifies the task in some cases."