17
\$\begingroup\$

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 Mi,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*43 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 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
\$\endgroup\$
  • 1
    \$\begingroup\$ What is "G × G"? \$\endgroup\$ – Erik the Outgolfer Jan 2 '18 at 21:01
  • 8
    \$\begingroup\$ I downvoted this challenge, because the mathematics involved is quite fluffy and not accessible to everyone who reads this challenge. Perhaps, a worked example would be helpful (like, explaining why the the 8th input results in 5)? If you add one I think I will retract my vote, but of course that is up to you. \$\endgroup\$ – user74686 Jan 2 '18 at 21:09
  • 6
    \$\begingroup\$ @IanGödel Could you clarify what you mean by fluffy? It is certainly a more advanced mathematical topic but I don't think that we should shy away from math on PPCG. I'll add a worked example of a Moufang loop, but calculating an entire input by hand would probably clutter the challenge. \$\endgroup\$ – Wheat Wizard Jan 2 '18 at 21:15
  • 2
    \$\begingroup\$ @WheatWizard "Fluffy" as in, perhaps, "Advanced". EDIT: I retracted the downvote, but still awaiting an example. \$\endgroup\$ – user74686 Jan 2 '18 at 21:16
  • 1
    \$\begingroup\$ @Giuseppe Don't feel too bad, I also made a mistake when correcting yours it's 12 not 11. I should have realized that because 11 is prime number. \$\endgroup\$ – Wheat Wizard Jan 2 '18 at 21:30
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.