calgorithmmodelingabstract-algebrasemigroup

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

Number of binary operation on a set of 2 elements is 2^(2*2)=16. enter image description here
Number of associative binary operation on that set is only 8.
enter image description here
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!

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.