Counting Moufang Loops

Question

A loop is a pretty simple algebraic structure. It is a tuple (G,+) where G is a set and + is a binary operator G × G → G. That is + takes two elements from G and returns a new element. The operator is also required to fulfill two properties

• Cancellation: For every a and b in G there exists unique x and y in G such that

  a + x = b
  y + a = b
  

• Identity: There is an e in G such that for every a in G

  e + a = a
  a + e = a
  

If you are familiar with the concept of a group you might notice that a loop is just a group that doesn't have an associative property.

Loops are pretty simple so people like to add more rules to make new structures that are more interesting. One such structure is a Moufang loop which is a loop that also satisfies the following four identities forall x, y and z in G

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

For example the following Cayley table represents a Moufang loop:

0  1  2  3
1  0  3  2
2  3  0  1
3  2  1  0

(If you are not familiar a Cayley table is a square matrix M where M_i,j is equal to i + j. It is a handy way for representing binary operators on a set.)

We can show that there is an identity rather easily it is 0. Cancellation is a little harder to show but a brute force approach yields this table

b a → 0 1 2 3
↓
0     0 1 2 3
1     1 0 3 2
2     2 3 0 1
3     3 2 1 0

Where our elements are the solutions to

a + x = b = x + a

(You may notice that this table is identical to our Cayley table. I'll leave it as an exercise to the reader to figure out why this is the case for this Moufang loop)

Now we need to verify the Moufang identities for our structure. There are two ways to do this for the particular structure the first way is to realize that it is associative and thus automatically fulfills the criteria, however this will not work in general so we would rather brute force the result. There are 3 free variables each with a potential of 4 values in every expression here. This means we have to perform 7*4³ or 448 computations. I'll leave out the raw computations but here is some Haskell you can use to verify this.

Task

Given a positive integer n as input output the number of Moufang loops that have order n. (the order of a group is the size of the set)

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Test cases

Here is the number of Moufang loops for the first 71 inputs

1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1

Answer 1

Python 3, 475 410 bytes

Thanks to Mr.Xcoder for saving some bytes!

Use the symmetry of the formula to save 65 bytes. Yes, that's a lot.

from itertools import*
n=int(input())
P=permutations
R=[*range(n)]
u=[]
A=all
S=sorted
for T in P(P(R),n):u+=[T]*(A(A(R==S(x)for x in
t)and any([*x]==S(x)for x in t)and
A(t[z][t[x][t[z][y]]]==t[t[t[z][x]][z]][y]and
t[t[z][x]][t[y][z]]==t[t[z][t[x][y]]][z]for x in R
for y in R for z in R)for t
in(T,[*zip(*T)]))and A(A(1-A(p[T[i][j]]==U[p[i]][p[j]]for i in R
for j in R)for p in P(R))for U in u))
print(len(u))

Try it online!

---

Some and can be replaced by *, results in lower bytecount but at the cost of significantly slower execution time:

Python 3, ??? bytes

[TODO put code here]

(of course not all * makes the program significantly slower, only some of them are critical)

---

Ungolfed:

from itertools import *
n = 4 # int(input())
rangeN = list(range(n))

def is_moufang_loop(T):
    A = tuple(zip(*T))
    return all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        and all(
                T[z][T[x][T[z][y]]] == T[T[T[z][x]][z]][y]
            and T[T[z][x]][T[y][z]] == T[T[z][T[x][y]]][z]
            for x in rangeN for y in rangeN for z in rangeN)
        for t in (T, A)
    )

def isomorphic(loop1, loop2):
    for p in permutations(rangeN):
        if all(
            p[loop1[i][j]] == loop2[p[i]][p[j]]
            for i in rangeN
            for j in rangeN
        ): return True
    return False

unique_moufang_loops = []
for x in [
        cayley_table 
        for cayley_table in permutations(permutations(rangeN), n)
        if is_moufang_loop(cayley_table)
]:
    if all(not isomorphic(x, y) for y in unique_moufang_loops):
        unique_moufang_loops.append(x)

print(len(unique_moufang_loops))

Try it online!

_{No scroll bars...}

---

Explanation:

The program is pretty simple.

• Each possible "binary operator" is represented by a Cayley table (0-indexing).
• The "identity" property implies that there exists e such that both the e'th row and the e'th column are equal to [0, 1, 2, ..., n-1], which is the same condition as

  both the array T and its transpose has a row equal to [0, 1, 2, ..., n-1].

• The "cancellation" property is equivalent to

  Every row and every column are a permutation of [0, 1, 2, ..., n-1].

So, the part

all(
        all(sorted(x) == rangeN for x in t) 
        and any(list(x) == sorted(x) for x in t) 
        for t in (T, A))

of the code checks that. (for all row in the array T and its transpose A, it being sorted is equal to rangeN, and there exists a row in both T and A that equals to itself being sorted)

The four conditions of a Moufang loops are checked manually.

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

In the code, (a + b) is represented as T[a][b]. (because of the representation as Cayley table). Use Python chaining equality comparison to avoid duplication of (z + x) + (y + z).

However, because the formula is symmetric:

If we switch the operands of + in the first formula, we get the second formula; and if we switch the operands of + in the third formula, we get the fourth formula with x and y swapped place.

Note that the transposition of the Cayley table is equivalent to the binary operators having operands swapped. (x + y -> y + x)

Finally, all the candidates Cayley table are picked from

permutations(permutations(rangeN), n) 

so that each row is a permutation of rangeN (which is [0, 1, 2, ..., n-1]) and there are n distinct rows.