How to get all algebraic associative operations on a finite set by efficient algorithm?

abstract-algebra, algorithm, c, modeling, semigroup

Solution

More than devising your own algorithm, this is a task for a mathematical model finder. For this task, I'd particularly recommend `mace4`, which part of the LADR library. It is specifically tuned to algebraic problems like this. The input (let's name it `semigroups.in`) would look like:

formulas(sos).
  (x * y) * z = x * (y * z).
end_of_list.

And then running it by `mace4 -n 4 -N 4 -m 10000 <semigroup.in` (find all 4-element models and print up to 10000 of them) produces a long output like

...

============================== MODEL =================================

interpretation( 4, [number=2331, seconds=0], [

        function(*(_,_), [
                           1, 2, 3, 3,
                           2, 3, 3, 3,
                           3, 3, 3, 3,
                           3, 3, 3, 3 ])
]).

============================== end of model ==========================

============================== STATISTICS ============================

For domain size 4.

Current CPU time: 0.00 seconds (total CPU time: 0.11 seconds).
Ground clauses: seen=64, kept=64.
Selections=2132, assignments=8520, propagations=6194, current_models=2331.
Rewrite_terms=210696, rewrite_bools=65151, indexes=11452.
Rules_from_neg_clauses=586, cross_offs=3767.

============================== end of statistics =====================

User_CPU=0.11, System_CPU=0.26, Wall_clock=0.

Exiting with 2331 models.

As you can see, it is very fast.

The library contains many other tools, such as `isofilter` that allows you to filter isomorphic variants of an algebra etc.

Problem

Number of binary operation on a set of 2 elements is `2^(2*2)=16`. Number of associative binary operation on that set is only 8. Number of binary operation on a set of 3 elements is 3^(3*3)=19683. Number of associative binary operation on that set is only 113. How to know how many associative binary operations there are on a set of n elements? Also in order to get all this 113 operations and write into file, it is necessary to write a program. if I will try to get all 19683 operations and then check it`s associative property "a*(bc)==(ab)*c" for all 19683 operations, this will work but this should take a long time for n=4 elements! How to write an efficient algorithm to solve this task? Please help me!

Original source