11

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!

IremadzeArchil19910311
  • 916
  • 4
  • 10
  • 27
  • 2
    your question is way to broad, and probably also not very well focused for SO. SO is about programming and not about Combinatorics. – Jens Gustedt Jul 09 '14 at 16:39
  • 1
    @JensGustedt This problem is more about algorithms than combinatorics. Sure, you need the combinatorics to analyze the algorithm (a naive implementation would be something like `O(n^(n^2))` in complexity), but it isn't about combinatorics. I would agree that this post might be better suited [programmers SE](http://programmers.stackexchange.com), since they mention algorithms specifically in [their FAQ](http://programmers.stackexchange.com/tour). – bheklilr Jul 09 '14 at 16:43
  • 4
    @bheklilr: Well, SO at least has an [algorithm tag](http://stackoverflow.com/tags/algorithm/info) (and a tag for abstract algebra and even one for semigroups). But I think, it's too broad, a good answer would probably be very long. Last, there is nothing OP has tried so far (it's a "gimme teh algo" question). IremadzeArchil: Maybe http://math.stackexchange.com/? Actually, you're asking “how many semigroups with n elements do exist?” – mafso Jul 09 '14 at 16:53
  • 1
    See http://mathoverflow.net/q/110211. – chepner Jul 09 '14 at 17:45
  • 2
    You might be able to find some good resources following http://oeis.org/A023814 – bheklilr Jul 09 '14 at 18:18
  • Notice that every associative operation exhibits one or more of a couple types of symmetry, but the non-associative ones don't... – twalberg Jul 09 '14 at 20:22

1 Answers1

6

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.

Petr
  • 62,528
  • 13
  • 153
  • 317