Last semester, for an algebra homework, I was trying to prove that there exist only 2 groups of order 6 (namely and ). The usual argument uses the classification of groups with order (with and prime), which itself uses Sylow theorems, but I wondered if I could prove it computationally. Here's my attempt.
Definition: a magma is a pair where is a non-empty set and is a binary operation on . A quasigroup is a magma in which the equations and , with , always have a unique solution for and in . A group is a magma in which is associative, modulative and invertive.
Another way of defining a quasigroup is as a magma in which the left and right cancellation laws hold. Note that we're not asking to be associative in a magma (let alone in a quasigroup).
All there is to know about a finite magma is encoded in its Cayley table: a matrix that shows how the elements in operate among themselves. In general, if , the Cayley table looks like this:
That is, the element in the -th position is the result of multiplying with in that order.
You can tell a lot about a magma and its operation just by looking at its Cayley table. For example, consider Klein's 4 group :
You can immediately tell its commutative (because the matrix is symmetric), you can tell there is an identity (namely ) and that each element is its own inverse. You could also tell if the binary operation is associative from its Cayley table using Light's test, although it isn't any better, computationally speaking, that just verifying every case by hand.
We will use Cayley tables as the bridge between algebra and combinatorics.
Definition: a matrix of different entries is called a latin square if no element appears more than once in any row or column. This property is called the latin square property.
We will deal with latin squares of size whose entries are the integers from to . For example
is a latin square of size . We will also start indexing by 0.
Theorem 1: if is a quasigroup, then its Cayley table is a latin square.
Proof: Suppose and that an element appears twice in row (say, in columns and ), by the definition of the Cayley table, this means that
and because is a quasigroup, the left cancellation law implies that , which is absurd because we assumed that and were different. Analogously, the right cancellation law implies that no element appears twice in any column. Q.E.D.
This theorem has a reciprocal of some sort:
Theorem 2: Given a latin square , one can construct a quasigroup whose Cayley table is .
Proof: Let and denote . Define by
by definition, is well defined (that is, it is closed in the set). We need to check that the equations and have unique solutions. Consider , because is a latin square, appears somewhere in row , call the column it appears in , then is a solution to . It is unique, because if there existed such that , then would appear twice in row , which contradicts the fact that is a latin square. Analogously, now arguing with columns, has a unique solution in . Q.E.D.
So now we're set!, we only need to find all latin squares of size and to verify if they represent a valid binary operation for a group. Moreover, we could force the existence of an identity by focusing on finding normalized (or reduced) latin squares (that is, latin squares where the first row and column are ).
I use a depth-first-search style algorithm, starting with a normalized matrix
where the unvisited locations are labeled with a . We also start with an empty stack . The algorithm goes as follows:
Here's the algorithm implemented in python:
def dfs_in_matrix(A): # First we create an empty stack and we put the initial matrix # in it. list_of_solutions =  stack = LifoQueue() stack.put(A) while not stack.empty(): # We pop a matrix from the stack B = stack.get() # We check if it's finished. if is_finished(B): list_of_solutions.append(B) continue # We find an unvisited position position = find_first_unvisited_position(B) if position == None: continue span = span_of_position(position, B) for k in range(len(B)): if k not in span: C = B.copy() C[position] = k stack.put(C) return list_of_solutions def find_normalized_latin_squares(number): A = np.zeros((number, number)) for k in range(number): A[0, k] = k A[k, 0] = k for i in range(1, number): for j in range(1, number): A[i, j] = -1 list_of_solutions = dfs_in_matrix(A) return list_of_solutions
span_of_position are auxiliary, check this jupyter notebook for all the code discussed in this post). It checks out with the literature on the topic1, saying that there are 9408 normalized latin squares of size 6.
Once we have all the normalized latin squares, we can build up a
Magma class in python and we can write a verification function to find which of these correspond to associative operations (and thus to groups).
class Magma: def __init__(self, _matrix): self.cayley_table = _matrix self.set = set(range(0, len(_matrix[0,:]))) def mult(self, a, b): return int(self.cayley_table[a, b]) def is_magma_associative(mag): ''' This function verifies if magma `mag` is associative by brute force. ''' n = len(mag.cayley_table) _flag = True for a in range(n): for b in range(n): for c in range(n): _flag = _flag and (mag.mult(a, mag.mult(b,c)) == mag.mult(mag.mult(a,b),c)) return _flag def find_groups(number): latin_squares = find_normalized_latin_squares(number) associative_magmas = [sol for sol in latin_squares if is_magma_associative(Magma(sol))] return associative_magmas
After running this
is_magma_associative in all 9408 reduced latin squares of order 6 we're left with 80 reduced latin squares such that, when interpreted as quasigroups, are associative. That is, only 80 of the original 9408 reduced latin squares of size 6 can be interpreted as Cayley tables for groups.
We're trying to prove the following theorem:
Theorem 3: There are only 2 groups of order 6, namely and .
It is useful, then, to cleary state what we interpret as and . are the usual integers modulo 6 with sum modulo 6, but note that can also be interpreted in the following way: its a group of six elements such that
(note that we just changed for ). We can use this information to find an isomorphism between a latin-square-generated group and .
is usually interpreted as the group of symmetries of a triangle (where is the reflection that fixes vertex and is a rotation of degrees, but we prefer the following presentation:
In this presentation, the 6 different elements are and .
So, to prove theorem 3, we will follow this strategy: we will give an isomorphism from either or to each of the 80 groups found using latin squares:
Proof (of Theorem 3): Theorem 1 and 2 show that all possible groups of a certain order are restricted by the amount of normalized latin squares of said order. After filtering the normalized latin squares of size 6 by verifying which represent an associative binary operation, we're left with 80 Cayley tables for groups. In this jupyter notebook we show an explicit isomorphism between each of these 80 latin square generated groups and either or , but for the sake of completeness we show how these isomorphisms were constructed with explicit examples for and . Consider the following normalized latin square:
and call the group it induces . After inspecting it, we can tell that the orders of their elements are either or , so it is a candidate for being isomorphic to . Choose and , and note that that is, this group obeys the presentation given for . The isomorphism would then be given by
Now consider the group given by the following reduced latin square:
because the elements of have order either 2, 3 or 6, we will construct an isomorphism between and using the identification stated before. First note that is an element of order 2, have order 6 and have order 3. Because and , we construct the following isomorphism