4

抽象代数では、グループの概念はかなり基本的です。グループを取得するには、オブジェクトのセットと、3つのプロパティ（クロージャーを数える場合は4）を持つ2項演算が必要です。有限集合が与えられたグループをランダムに生成したい場合（つまり、集合内の要素のすべての可能な組み合わせの結果を与えるテーブルをランダムに生成したい場合）、単位元をハックし、逆元をハックするのは非常に簡単です。 、しかし、連想的である操作をランダムに生成することは非常に難しいようです。

私の質問は、結合法則をランダムに生成するための（効率的な）方法があるかどうかです。ランダムに操作を生成してから、非結合関係を摂動させて、一度に1つずつ結合するようにしましたが、これは実際には収束していないようです。何か案は？

4

4 に答える 4

3

これは、「ランダム」と見なされるものにのみ依存します。1 つのオプションは、実際の群演算行列をランダムに生成する代わりに、構築により結合性があることが知られている群のファミリーから結合性群をランダムに選択することです。

例えば：

  • n を法とする加算を伴う整数 {0...n-1} のグループは連想グループです
  • n を法とする乗算による整数群 {1..p-1} は、p が素数の場合、連想群です
  • G と H および 2 つの連想群の場合、群操作 (g,h) * (g',h') = (g*g',h*h') を持つ群 (G,H) は結合的です
  • G が群演算 * を持つ群であり、c が G の定数である場合、g @ g' = (g * c) * g' として定義された演算 @ も (g @ g') @ g'' として結合されます。 = g * c * g' * c * g'' = g @ (g' @ g'')

したがって、たとえば、サイズ N のランダム グループを生成するには、N を素数 N = (p1, ..., pk) (同じ素数がそのリストに複数回出現する可能性があります) に因数分解してから、ランダム積を作成します。 N = q1 * ... * qn となるようにそれらから q1, ..., qn を計算し、すべての qi について加法的または乗法的整数グループを選択し、ランダム定数を追加して、結果の積グループをランダム連想として使用します。グループ。同じ確率ですべての連想グループを生成するわけではありませんが、ランダムな追加グループを取得するのはランダムなプロセスであり、特に大きなグループが必要な場合は、マトリックスをランダムに埋めるよりもはるかに優れている可能性があります。

于 2011-11-10T20:16:06.037 に答える
3

Knuth-Bendix 補完を試すことができます。

本質的に、これは、結合方程式の 2 つの側面を繰り返し識別することによって、グループを強制的に結合させることを意味します。

したがって、グループは最初のサイズよりも小さくなりますが、いくつかの要素を追加して続行できます.

于 2011-11-11T08:08:25.887 に答える
1

以下は、特定のセットですべてのバイナリ関数を生成する Prolog 述語の一部です。

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).
于 2012-03-12T23:50:48.120 に答える
1

二項演算の結合性は、トリプル (a, b, c) に対して (a * (b * c)) = ((a * b) * c) と定義されます。したがって、a * b をランダムに定義しようとすると、結合性に違反しない a * b への割り当ての 1 つをランダムに選択するだけで済みます。そのような割り当てがない場合は、バックアップして、最後のステップで別の割り当てを選択します。そう...

  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

これは醜い力ずくの方法ですが (ここで示す実装にはバグがある可能性があります)、概念的には、ある意味で「ランダム」である連想演算子を見つける必要があります。

于 2011-11-10T19:42:02.357 に答える