群ですか？

Are you a group?

​

kinaba

群 (Group)

集合 G と二項演算 ☆ が以下の３条件を満たしてたら群と呼ぶ

​

• [UNIT] ある e ∈ G があって、すべての a ∈ G に対し� e☆a  =  a☆e  =  a
• [INVERSE] すべての a ∈G に対し、�a☆z  =   z☆a  =  e�              を満たす z ∈G がある
• [ASSOCIATIVITY] すべての a,b,c ∈ G に対し�(a☆b)☆c   =    a☆(b☆c)

問題

N × N の表が渡されたときに

群になってるかどうか�判定してね

自明な解法

   G.any? { |e|

       G.all? { |a|  e☆a==a && a☆e==a }

   }

&&

   G.all? { |a|

       G.any? { |z| a☆z==e && z☆a==e }

   }

&&

   G.all? { |a|

       G.all? { |b|

          G.all? { |c| (a☆b)☆c == a☆(b☆c) }�       }

   }

​

O(N³)

よんだ論文

• Determining Whether a Groupoid is a Group
• Robert E. Tarjan
• Information Processing Letters, vol. 1, 1972
• http://dx.doi.org/10.1016/0020-0190(72)90012-9
• それ O( N² log N ) でできるよ

• Verifying Identities
• Sridhar Rajagopalan and Leonard J. Schulman
• FOCS 1996
• http://doi.ieeecomputersociety.org/10.1109/SFCS.1996.548520 
• それrandomized algorithmなら O( N² ) でできるよ

O(N² log N)

  B = a set of generators of G

  G.all? { |a|

       B.all? { |b|

            G.all? { |c| (a☆b)☆c == a☆(b☆c) }}}

​

• Set of generator とは
• Bの元だけを☆したり逆元とったりしまくったらGが全部作れる
• 足し算なら { 1 } など
• 置換群なら { 隣同士をswap } など
• 群ならば、極小のgeneratorのサイズは
• |B| ≦ log₂ |G|
• B は適当に貪欲にやれば O(N²) で求まる

おまけスライド： technical detail

• 「真ん中はgeneratorだけ考えればよい」
• 任意の x は generator の積 x = b₁☆b₂☆b₃☆...☆b_k  で書けるので
• (a☆x)☆c = (a☆(b₁☆b₂☆b₃☆...☆b_k))☆c�= ...(generatorが真ん中の結合則を利用した式変形)...�= a☆((b₁☆b₂☆b₃☆...☆b_k)☆c)�= a☆(x☆c)
• 「Gが群ならば、極小 generator のサイズは log₂|G| 以下」
• B = {b₁, b₂, b₃, ..., b_k} が generator とする
• b₁☆「b₂ から b_k を適当に組合せて作った値」 は b₂ から b_k だけの組合せでは作れない
• 理由：仮に b₁ ☆ X = Y だとすると、群なので逆元をとって b₁ = Y ☆ X^-1 なので�b₁ が他から作れてしまう。これは B の極小性に反する
• 同様にどの b_i も、「b_i を1回だけ使って作った値」は「b_i を1個も使わない値」と必ず異なる
• よって、b₁ を使う/使わない、b₂を使う/使わない、… の組合せで全部違う値が作れるので
• 2^|B| ≦ |G|
• 「適当に貪欲にやれば O(N²) でgenerator 求まる」
• 単位元じゃない元 b₁ を適当に選ぶ。その1乗、2乗、3乗、…、-1乗、-2乗、…を求める
• まだ作れなかった元を b₂ として選ぶ {b₁, b₂} で作れる元を全部求める
• 以下繰り返すだけ。（点数 N 辺数 N² のグラフの幅優先探索するのと同じ計算量）

O(N²) randomized

注： 群の判定ではなく、結合性の判定のみを行う手法

　（ "群じゃなさそうだったら（結合性があっても）捨て！"

　　ができないので、こちらの方が難しい！）

​

   十分な回数のループ  {

　   if(  (結合則が成り立つなら必ず true 

　          成り立たないなら、1/8 以上の確率で false

　          を返す O(N²) アルゴリズム)  == false )

          return false;

   }

   return true;

​

確率 1/8

  Random に X = {a₁, a₂, ..., a_x} ⊆ G を選ぶ�  Random に Y = {b₁, b₂, ..., b_y}⊆ G を選ぶ�  Random に Z = {c₁, c₂, ..., c_z} ⊆ G を選ぶ�  (X☆Y)☆Z = X☆(Y☆Z) かどうか確かめる�

ただし集合同士の ☆ は xor っぽい雰囲気で定義

• X☆Y = { d  |  a_i☆b_j=d になる組(i,j)が奇数個 }
• これらでAssociativityが成り立つ iff  要素ごとのAssociativityが成り立つ

​

確率 1/8 であることの証明の雰囲気

• 結合則が成り立たない要素の組を (a,b,c) とする
• Xにaを足したり引いたり,  Yにbを足したり引いたり, Zにcを足したり引いたり
• してできる８通りの３つ組のうちどれか一つは、結合則が成り立たない
• （詳細は次のページ）

おまけスライド： technical detail

• 集合の xor を A xor B = {c | c は A か B のどちらか一方にだけ入っている} で定義
• A={a₁, ..., a_x} と B={b₁, ..., b_y} に対して、A☆B = {a₁☆b₁} xor ... xor {a_x☆b_y} と定義
• 分配則が成り立つ
• A☆(B xor C) = (A☆B) xor (A☆C)
• (A xor B)☆C = (A☆C) xor (B☆C) 
• 「集合に対する☆に結合則が成り立つ if and only if 要素毎の☆に結合則が成り立つ」
• → : {(a☆b)☆c} = ({a}☆{b})☆{c} = {a}☆({b}☆{c}) = {a☆(b☆c)}
• ← : (A☆B)☆C = (a☆b)☆c ただしa∈A,b∈B,c∈Cの元を全部xorしたもの�       = a☆(b☆c) ただしa∈A,b∈B,c∈Cの元を全部xorしたもの = A☆(B☆C)
• A xor {a}のことをAaなどと書くことにすると
• (A☆B)☆C    xor   A☆(B☆C)�xor (A☆B)☆Cc    xor   A☆(B☆Cc)�xor (A☆Bb)☆C    xor   A☆(B☆C)�xor (A☆Bb)☆Cc    xor   A☆(B☆Cc)�xor (Aa☆B)☆C    xor   Aa☆(B☆C)�xor (Aa☆B)☆Cc    xor   Aa☆(B☆Cc)�xor (Aa☆Bb)☆C    xor   Aa☆(Bb☆C)�xor (Aa☆Bb)☆Cc    xor   Aa☆(Bb☆Cc)   =  ({a}☆{b})☆{c} xor {a}☆({b}☆{c}) である。
• 証明は分配法則を使いまくって式を整理。
• 前のページのように (a☆b)☆c ≠ a☆(b☆c) の場合、右辺が空でないので、�左辺の８行のどれかは空ではない。よって、A(a) B(b) C(c) の組み合わせどれかは�結合則が成り立たない。つまり集合の3つ組の、8個に1つは結合則が成り立たない

Further Reading

• 読んだ論文に他に載ってる話題
• [Tarjan72] 可解群かどうかの判定は O(N²)
• [RS96] 結合性に限らず、条件の式の両辺に全変数が一度ずつ現れる条件ならなんでも同じ手法が使えるよ

​

• Fast Recognition of Rings and Lattices (未読)
• http://dx.doi.org/10.1007/3-540-10854-8_14
• 環 (ring) の判定は O(N²)
• 束 (lattice) の判定は O(N^2.5)

​

• 群の定義ゴルフ
• http://twitter.com/#!/masahiro_sakai/status/60039258802634752