Introduction

The Magma package introduced in Maple 15 includes the command Enumerate. This routine allows you to count, or list, isomorphism class representatives of magmas of a given (small) order satisfying a selection of properties that you can specify. A large number of predefined properties are built in to the Enumerate command and are selected by passing a keyword option to the Enumerate command. (See the help page ?Enumerate for a complete list.) In addition, there is an option that allows you to specify your own custom conditions that magmas found by the Enumerate command must satisfy.

For example, the command

> with( Magma ):
> Enumerate( 5, 'loop' );
                                      6

counts the number of isomorphism classes of loops of order 5. To actually get the Cayley tables of these six loops, use the output = list option.

> L := Enumerate( 5, 'loop', 'output' = 'list' ):
> nops( L );
                                      6

Now we can eliminate the group from this list to see the five non-associative loops of order 5.

> remove( IsAssociative, L );
 [1    2    3    4    5]  [1    2    3    4    5]  [1    2    3    4    5]
 [                     ]  [                     ]  [                     ]
 [2    1    4    5    3]  [2    1    4    5    3]  [2    1    4    5    3]
 [                     ]  [                     ]  [                     ]
[[3    4    5    1    2], [3    4    5    2    1], [3    5    1    2    4],
 [                     ]  [                     ]  [                     ]
 [4    5    2    3    1]  [4    5    1    3    2]  [4    3    5    1    2]
 [                     ]  [                     ]  [                     ]
 [5    3    1    2    4]  [5    3    2    1    4]  [5    4    2    3    1]

    [1    2    3    4    5]  [1    2    3    4    5]
    [                     ]  [                     ]
    [2    1    4    5    3]  [2    3    1    5    4]
    [                     ]  [                     ]
    [3    5    2    1    4], [3    4    5    1    2]]
    [                     ]  [                     ]
    [4    3    5    2    1]  [4    5    2    3    1]
    [                     ]  [                     ]
    [5    4    1    3    2]  [5    1    4    2    3]

Similarly, a combination of properties can be passed to the Enumerate command to cause it to search for all magmas of the given order satisfying all the listed properties. Since a loop is Moufang if, and only if, it is left and right Bol, the command

> Enumerate( 5, 'loop', 'leftbol', 'rightbol' );
                                      1

shows that there is only one Moufang loop of order 5. To see it, you can again use the output = list option.

> Enumerate( 5, 'loop', 'leftbol', 'rightbol', 'output' = 'list' );
                           [1    2    3    4    5]
                           [                     ]
                           [2    3    4    5    1]
                           [                     ]
                          [[3    4    5    1    2]]
                           [                     ]
                           [4    5    1    2    3]
                           [                     ]
                           [5    1    2    3    4]

The command

> Enumerate( 5, 'quandle', 'commutative' );
                                      1

shows that there is an unique commutative quandle of order 5, and the commands

> Enumerate( 9, 'quandle', 'commutative' );
                                      2

> Enumerate( 9, 'kei', 'commutative' );
                                      1

show that, of the two commutative quandles of order 9, only one is a kei (a quandle satisfying the identity (X•Y)•Y = X).

Enumerating Szasz Magmas

A Szasz magma is one which is as close to being a semigroup as possible, without actually being associative. It is a theorem of G. Szasz (1953) that, for any set S with at least four members, there is a binary operation • on S such that exactly one triple (a,b,c) of members of S is non-associative: (a•b)•c ≠ a•(b•c). For any other triple (x,y,z) of members of S, we have (x•y)•z = x•(y•z). (See G. Szasz, Die Unabhängigkeit der Assoziativitätsbedingungen, Acta Sci. Math. Szeged 15 (1953), 20--28.) The clever construction is fairly simple, and the verification that it works is elementary. Given a set S with four distinct elements a, u, v and w, define the binary operation • on S by putting a•a = u, a•u = v and, for any pair (x,y) other than (a,a) and (a,u), define x•y = w. By considering the various cases that arise, it is then straightforward to check that (a•a)•a = w ≠ v = a•(a•a), but that (x•y)•z and x•(y•z) coincide, for any triple (x,y,z) of members of S other than (a,a,a).

It turns out that there are, in fact, Szasz magmas of order three, but none with just two elements.

> Enumerate( 2, 'szasz' );
                                      0

> Enumerate( 3, 'szasz' );
                                      10

In fact, rather than being anomalous, Szasz magmas are really quite abundant. The following table, computed using the Enumerate command, shows the numbers of isomorphism classes of Szasz magmas of small orders.

Order    No. of Szasz Magmas
  1             0
  2             0
  3             10
  4             124
  5             2064
  6             39961
  7             1194828

The Enumerate command actually began life as a special purpose program to compute these numbers.

How Does it Work?

The Enumerate command is essentially a search algorithm which employs backtracking and pruning to avoid searching the entire space of magmas of a given order. In order to avoid producing isomorphic replicas, the algorithm checks whether each new magma discovered might be completed to one which is lexicographically least in its isomorphism class. Thus, the list of isomorphism class representatives generated by the algorithm consists of the lexicographically least representative of each isomorphism class. In this way, only one representative from each isomorphism class of magmas satisfying the specified constraints is produced.

Visualising the Enumeration

The attached application worksheet provides a mechanism through which you can visualise the enumeration of small magmas by the Enumerate command. While this is not the best way to perform a large, long-running enumeration, the patterns that emerge in the Cayley tables of the enumerated magmas can provide insight into the structure of magmas in the enumerated class.

To use the worksheet, select the magma order from the list box, and check off whatever combination of properties are of interest. Then press the Enumerate button to start the enumeration. As each isomorphism class representative is discovered, its Cayley table is displayed with colours representing the distinct magma elements.

Because enumerations for very small orders tend to complete very quickly, there is a slider control that allows you to slow down the enumeration by pausing it after each magma is discovered.

You can save the results of the enumeration when it has completed by using the button provided.

MagmaEnumerator.mw