Randomly generating associative operations

Question

In abstract algebra, the notion of a group is fairly fundamental. To get a group, we need a set of objects, and an binary operation with 3 properties (4 if you count closure). If we want to randomly generate a group given a finite set, (that is, randomly generate a table giving the result of every possible combination of elements in the set), then it's pretty easy to hack in an identity element, and hack in inverses, but it seems very hard to randomly generate an operation that is associative.

My question is whether there is some (efficient) way to randomly generate an associative operation. I've tried randomly generating an operation, then perturbing non-associative relationships so that they are associative one at a time, but this doesn't really seem to converge. Any ideas?

Answer 1

This depends only on what is considered "random". One option is to, instead of generating the actual group operation matrix randomly, to pick randomly an associative group from a family of groups that are known to be associative by construction.

For example:

• Group of integers {0...n-1} with addition modulo n is an associative group
• Group of integers {1..p-1} with multiplication modulo n is an associative group when p is prime
• If G and H and two associative groups, then the group (G,H) with group operation (g,h) * (g',h') = (g*g',h*h') is associative
• if G is a group with group operation * and c is a constant in G, then also the operation @ defined as g @ g' = (g * c) * g' is associative as (g @ g') @ g'' = g * c * g' * c * g'' = g @ (g' @ g'')

So, for example, in order to generate a random group of size N, get a factorization of N into primes N = (p1, ..., pk) (same prime can appear multiple times in that list), then build random products q1, ..., qn from them so that N = q1 * ... * qn, and then for every qi, pick an additive or multiplicative integer group, add random constants, and then use the resulting product group as a random associative group. It won't generate all the associative groups with the same probabilities, but it is still a random process to get a random additive group, and might be much better than filling a matrix randomly especially if you need bigger groups.

Answer 2

Associativity of binary operations is defined for triples (a, b, c) to be (a * (b * c)) = ((a * b) * c). Therefore, when you go to define a * b randomly, you could simply select at random one of assignments to a * b that doesn't cause associativity to be violated; if there aren't any such assignments, back up and choose a different assignment at the last step. So...

  MakeRandomAssociative(table[1..N, 1..N], elements[1..N], n)
  0. if n = N + 1 return true
  1. a := elements[n mod N]
  2. b := elements[n // N]
  3. candidates = []
  4. for each c in elements do
  5.    table[n mod N,n // N] = c
  6.    if not violates_associativity(table) then candidates.add(c)
  7. if empty(candidates) return false
  8. else then
  9.    c := remove_random(candidates)
  A.    table[n mod N,n // N] = c
  B.    if MakeRandomAssociative(table, elements, n+1) then
  C.       return true
  D.    else goto 7

That's ugly and brute-force, but (the implementation given here might be buggy) it should conceptually find an associative operator which should be "random" in some sense.

Answer 3

You could try Knuth-Bendix completion.

In essence this means that you force your group to be associative by repeatedly identifying the two sides of the associativity equation.

So your group will become smaller than your initial size, but you can again add some elements and continue.

Answer 4

Here are some Prolog predicates that generates all binary functions on a give set:

gen_binop(A,BinOp):-
    cartesian(A,Cart),
    gen_func(Cart,A,BinOp).gen_func(Dom,Rng,Func) :-
    is_set(Dom),
    is_set(Rng),
    gen_func(Dom,Rng,[],Tmp),
    reverse(Tmp,Func).

cartesian(A,B,Cart):-
    findall([X,Y],(member(X,A),member(Y,B)),L),
    list_to_set(L,Cart),!.

gen_func([],_,Func,Func).
gen_func([H|T],Rng,Func1,Func) :-
    member(Y,Rng),
    Func2=[[H,Y]|Func1],
    gen_func(T,Rng,Func2,Func).

Finally, we test to see if any given binary operation is non-associative (and then negate that to find the associative ones):

non_assoc_binop(BinOp):-
    domain(BinOp,D),
    flatten(D,A),
    cartesian3(A,A,A,Cart),
    member([X,Y,Z],Cart),
    eval(BinOp,[X,Y],X1),
    eval(BinOp,[Y,Z],Y2),
    eval(BinOp,[X1,Z],U),
    eval(BinOp,[X,Y2],V),
    U\=V.

eval(F,X,Y) :-
    function(F),
    member([X,Y],F).

function(PL) :-
    pair_list(PL),
    forall(image(PL,_,ImgX),func_image(PL,ImgX)).

image(PL,X,ImgX) :-
    pair_list(PL),
    domain(PL,Dom),
    member(X,Dom),
    findall(Y,member([X,Y],PL),L),
    list_to_set(L,ImgX).

func_image(PL,ImgX) :-
    image(PL,_,ImgX),
    length(ImgX,1).

pair_list([]).
pair_list([[_,_]|T]) :-
    pair_list(T).