Randomly Generating Associative Operations

Question

In abstract algebra, the concept of group is quite fundamental. To get a group, we need a set of objects and a binary operation with 3 properties (4 if you consider closure). If we want to randomly generate a group defined by a finite set (i.e., to randomly generate a table , giving the result of any possible combination of elements in the set), then it is quite easy to hack the identification element and crack the inverse, but it is very difficult to randomly generate an associative operation.

My question is whether there is a (efficient) way to randomly generate an associative operation. I tried to randomly generate the operation, and then outraged the non-associative relationships so that they were associative one at a time, but in reality it does not seem to converge. Any ideas?

Answer 1

It only depends on what is considered "random." One option is to randomly randomly generate the actual matrix of group operations in order to randomly select an associative group from a family of groups that are known to be associative by construction.

For instance:

• The integer group {0 ... n-1} with the addition of modulo n is an associative group
• The 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 the group operation (g, h) * (g ', h') = (g * g ', h * h') is associative
• if G is a group with a 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, to create a random group of size N, we get the factorization of N into prime numbers N = (p1, ..., pk) (the same number can appear several times in this list), then build random products q1 from them , ..., qn so that N = q1 * ... * qn, and then for each qi we select an additive or multiplicative whole group, add random constants and then use the resulting product group as a random associative group. It will not generate all associative groups with the same probabilities, but it is still a random process of getting a random additive group and can be much better than filling the matrix randomly, especially if you need large groups.

Answer 2

You can try to complete Knut Bendix.

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

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

Answer 3

The associativity of binary operations is defined for triples (a, b, c) as (a * (b * c)) = ((a * b) * c). Therefore, when you go to determine a * b randomly, you can simply randomly select one of the * b assignments, which does not lead to a violation of associativity; if there are no such assignments, back up and select another task in the last step. So that...

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 

This ugly and brute force, but (the implementation given here may be a mistake), it should conceptually find an associative operator, which should be "random" in a sense.

Answer 4

Here are some Prolog predicates that generate all binary functions in a job 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).