最長の置換表現について考える

タイトルを微妙に変えました。

最短とは違って、最長の方はもちろんいくらでも長くできるのですが、必要最小限ということにすれば、位数nの群の場合、n点の置換でどんな元でも表せるはずです。

これは、群の定義を考えれば大体自明だと思うのですが、たとえばある元の置換による表現は、その元を群の各元に対して左から掛けてみたものから得られます（もちろん、各元に1からnの番号を振っておく）。

ところで、この種の最長の置換でなければ表現できない群というのは確かに存在するようで、たとえばQ8、Q16、Q32などがそうです。

なぜこの種の群の場合に長い表現が必要なのか、はまだわかりません。機会があればまた考えてみたいと思います。

最短の置換表現について考える(9)

タイトル変えるつもりだったんですが、ちょっと気が変わりました。

g:=Group((1,2), (3,4)); と g:=Group((1,2)(3,4), (1,3)(2,4)); のタイプのものの合わせ技で短くできる場合もあるということで。

追加しておいた(C4 x C2 x C2) : C2 (1) がこの例になっています。記述は、

g:=Group((1,2,3,4), (5,6)(7,8), (5,7)(6,8), (2,4)(6,8));

で

a:=(1,2,3,4); b:=(5,6)(7,8); c:=(5,7)(6,8); d:=(2,4)(6,8);

と見るわけですが、関係式の方が

d^-1*a*d=a^-1, d^-1*b*d=b*c

と、aだけによる自己同型と、b,cが組み合わさった自己同型に分かれています。それで、こういう書き方ができるわけです。

C4 x C2 x C2 の部分を全部組み合わせにして書くと、生成元の3番目の式のように長くなります。ちなみに、2番目のものはたぶん偶然見つけたもので、どうしてこう書けるのかうまく解釈がつきません.。

（たぶんもう少しだけ続く）。

最短の置換表現について考える(8)

逆に、こういう感じでは短くできない例を考えましょう。例として、(C4 x C2) : C2 (1)を考えます。

C4 x C2 の側を (1,2,3,4), (5,6)と記述したとしましょう。ところが、関係式の最後の部分が

c^-1:*b*c=a^2*b

になっています。a^2*b=(1,3)(2,4)(5,6) なわけですが、これはb:=(5,6)と同じ共役類には入らないはずで、どんなcを取ってきても、上の関係式を成り立たせることはできません。

したがって、C4 x C2の側はやはり (1,2,3,4)(5,6,7,8), (1,5)(2,6)(3,7)(4,8) と記述するしかないようです。

これなどはまだ短い方ですが、位数と生成元の数が多くなると、この方法による置換による表現はとても長くなってしまします。

次回は一回タイトルを変えてみます。

最短の置換表現について考える(7)

C5 : C4（2）の話の続きです。とりあえず、

a:=(1,2,3,4,5);
b:=(6,7,8,9)(2,5)(3,4);

ということにしましょう。

b:=(6,7,8,9);

だけだったら、単に直積となり、C5 x C4 (=C20) になります。後の因子があるおかげで、

b^-1*a*b=a^-1;

が成立します。

b:=(2,5)(3,4)

だけだったら、この元の位数は2になりますし、全体としてはD10になります。

b:=(6,7,8,9)(2,5)(3,4);

なので、bが生成する部分群はC4になるわけです。

こんなところで、どうでしょう（まだまだまだまだまだまだ続く）。

最短の置換表現について考える(6)

で、その C5 : C4 の（2）なのですが、C5の方の自己同型（a -> a^-1）をあらわな形で書いたのが、2番目の生成群の置換表現です。

ではどうして最初の置換表現でもよいのか、という説明を考えてみたのですが、本業が忙しすぎて頭が回らず、うまい説明がちょっと見つかりません。また明日書いてみます（まだまだまだまだまだ続く）。

最短の置換表現について考える(5)

ある見落としに気づいて直したところ、SL(2,3)はますます短くなりました。さすがにこれ以上はないと思いますが。

さて、有限群の構造を判定して、いくつかの群の直積であることがわかったとします。このときそれぞれの直積成分は巡回群、半直積の群、分解しない拡大の群、または何かの単純群になるでしょう（これ以外の場合は何かあるかな）。

さて、このうち、巡回群については前に書きました。

半直積の群についてですが、この種の群の生成元はかなり簡潔に書ける場合があります。

前にも書いたことがありますが、2つの群の半直積を構成するには、一方の群から、もう一方の群の自己同型群への準同型写像を与えればよいわけです。この準同型写像が簡単に記述できるものであればあるほど、簡潔に書ける可能性があります。もっとも、常に単位元に写る、自明な準同型写像では、直積になってしまうわけですが。

端的な例が C5 : C4 で、C5の自己同型群自体ももC4になっているため、与えるべき準同型写像自体を同型写像にすることができます。これが (1) の方で、ごく簡潔に書けます。準同型写像としては別の可能性もあり、こちらは (2) で、いくらか長いです。

（まだまだまだまだ続きます。ご想像の通り、「まだ」はこのタイトルで続ける間、増えていきます。意味はありませんが）。

最短の置換表現について考える(4)

題とは多少の関係があることなのですが、あることに気がついて、SL(2,3)（位数24）の置換表現をだいぶ短くできたので、更新しておきました。比較のために古いものも残してあります。

さて、一般的な話に入る前に、二面体群を置換表現で生成することについて書いておきます。

二面体群Dn (n=2k) というのはつまり、正k角形の回転と裏返しからなる群なのですが、具体的に書くと、

k=2l の場合だと

g:=Group((1,...,k), (2, k)(3, k-1)...(l, l+2));

のようになります。k=2l+1の場合は少しだけ変わりますが、大体似たようなものです（まだまだまだ続く）。

最短の置換表現について考える(3)

さて、全体としてアーベル群であることが分かれば割と話は簡単で、巡回群の直積なのですから、たとえば Cl x Cm x Cn であれば、

g:=Group((1,...,l), (l+1,...,l+m), (l+m+1,...,l+m+n));

が希望する最短の置換表現であると考えてよいでしょう。ただ、C12 などは C4 x C3 に置き換えておく必要があります。

（まだまだ続く）

追記

GAPのリファレンスマニュアルを見ていたら、

『位数100以下の群（位数64の場合を除く）の構造は、計算済みのテーブルのルックアップによって判定する』という意味のことが書いてありました。

いずれにしても、構造を計算する方法はあるわけです。

最短の置換表現について考える(2)

さて、何らかの方法で有限群を定義したとして、次にその構造を判定しなければなりません。つまり、より小さな群の直積、半直積、分解しない拡大になっているのか、あるいは単純群なのか、といったことです。

これを行う方法は、私にはよくわからないのですが、確かに存在するわけで、実際GAPではStructureDescription関数が用意されています。さらに、GAPでは、半直積に対しては、一方の群から他方の群の自己同型群への準同型写像どんなものかということも判定できるようです。実際、C5 : C4と表記される半直積の群（半直積の記号は : で代用されています）は同型でないものが2つあるのですが、StructureDescription(g);では同じに表記されても、CharacterTable関数で指標表を求めてみると、はっきり別なものが出てくるので、その違いを判定しているはずです（まだ続く）。

最短の置換表現について考える(1)

本業が忙しくなったので、コンテンツそのものの更新はしばらくお休みです（CF4のJPEGも入れておきたいと思っていたのですが）。

とりあえず、これからしばらくは、タイトルのように、最短の置換表現、もう少し正確に言えば、ある有限群の（ひとつまたは複数の）生成元を、全体として最短になるような置換表現で記述するにはどうしたらいいかについて、考えてみた事を少しずつ書いておきたいと思います。

まずは、希望する有限群を記述する方法がなければなりません。

乗積表を与えるというのは論外として、やはり生成元を置換表現で与える（うまくすると短くできるかもしれない）、自由群に関係式を入れる、生成元を（標数0または有限の）体上の行列として与える、というのが考えられます。

私が知らないだけで、ほかにもあるかもしれません（続く）。

短い置換表現について、もう少し

直積の形の群の生成元の置換表現が短くなるということは昨日書きましたが、半直積でもかなり短いものがあります。たとえば、C5 : C4 (1) とかは、次のようになっています。

g:=Group((1,2,4,3,5),(1,2,3,4));

これは、C5の方の自己同型群がたまたまそうなっていたから、ということなのですが、具体的に書くと、

2^n ≡ 1 (mod 5)

になる最小の n > 0 が4 (= 5-1) だったから、ということになります。他にも似たようなものがありますが、探してみてください。

短い置換表現についてのちょっとしたこと

まあ、あまり大したことではないのですが、ちょっと書いておきます。

C12は、何も考えないと、

g:=Group((1,2,3,4,5,6,7,8,9,10,11,12));

となるわけですが、C4 x C3と同型であることに注意すれば、

g:=Group((1,2,3,4), (5,6,7));

というふうに、ずっと短く記述できるわけです。

生成元の大々的な書き換え

実行中です。

これは、昨日の「互換な置換」と関係があります。

互換な置換としては、昨日挙げたもののほかに、(1,2,3,4)と(13)(2,4)のようにべき乗関係になっているもの、そして、(1,2)(3,4)と(1,2)のような、共通番号を持たない2つの置換AとBでのA*BとA、および同様のパターンのものがあることを見落としていました。

それで、これまで(1,2)(3,4)と(1,3)(2,4)の形式で書いていた生成元の互換な置換部分を、A*BとAなどの形式で書きなおしてみたところ、ほとんどのものが短くなり、中には劇的に短くなったものもありました。

というわけで、生成元の部分を全体的に見直しています。そして、A*BとAの形のものと、(1,2)(3,4)と(1,3)(2,4)の形のもの、2つだけを残すようにしています（一部例外あり）。

これまで、偶然に見つけた生成元のうち、どうしてこれが関係式を満たすのだろうかと疑問に思っていたものが多くありましたが、今回ようやくわかりました。

ただ、どうもどちらか一方の形式でないと記述できないものが、中にはあるようです。このあたりのところも、よくチェックしてみたいと思います。

互換な置換

互換な置換について、ちょっと思い違いをしていたようです。可能なパターンとしては、

(1,2) と (3,4)

のように共通な番号を含まないものか、

(1,2)(3,4) と (1,3)(2,4)

のような組み合わせだけかと思っていたのですが、意外に自明なものを見落としていました。

説明はまた後日。

GAPの本家

今日はとりあえずここだけ紹介しておくことにします。

http://www.gap-system.org/

ダウンロード、インストールなどの入手方法は、また後ほど。

HF他追加

HFのデータを追加しました。有限群の方もいくつか追加しました。

それから、GAPの英語メーリングリストに登録してみました。まだ配信はありませんが。

O2を追加

というのは、ひさしぶりに量子化学の方のコンテンツです。O2の分子軌道のレイトレーシング画像を追加しました。

HFのデータも見つかったので、こちらもそのうちに追加しておきます。

有限群の番号付けの変更も継続中です。

番号付けの見直し

ちょっと番号付けを見直してみました。

たとえば、QD32では、最初の生成元の最初の置換を、

(7,14,5,12,3,10,1,8,15,6,13,4,11,4,9,16)

のようにしました。これはつまり、

(((1*7) mod 16), ((2*7) mod 16), ((3*7) mod 16),...,16)

のようになっているわけです。

この方が、a -> a^7 の自己同型群であることがわかりやすいと思うのですが、どうでしょうね。

QD32を追加

しました。

実は、昨日はもっといろいろやっていたのですが、最終的にうまくいったらここに書きます。

C16 : C2 を追加

しました。本日はとりあえずそれだけ。

1つ追加

群C4 . D8 = C4 . (C4 x C2)を追加しました。

また細かく修正

C4 : C8を追加、C7 : C3 を修正しました。

細かく修正

位数16のQD16、C8 : C2、C4 : C4などを修正しました。

生成元の番号付け

本日、C8 : C4 の3つ目を修正しましたが、この機会に生成元の番号付けについて考えました。

これまで、偶然見つかったりうまく構成できたり、というものを適宜載せてきたのですが、どうも統一感に欠けます。

それで、今後、半直積のものについては、自己同型写像を受ける群（半直積の左側に書かれている群）の自己同型の形がわかりやすい番号付けになるようにしたいと思います。

これから、この線で少しずつ見直していきます。ただ、これまで記述していたものも（2番目以降の生成元の例として）残しておくことにします。

（例によってわかりにくい書き方かな）。

また1つ追加

C8 : C4の3つ目を追加しました。

ただ、これだけ生成元の番号付けがほかのものと違うので、後で時間を見て直しておきたいと思います。

ひとやすみ

今日はいろいろと忙しかったので、更新はなしです。

SL(2,3)（続）

群SL(2,3)で、生成元と関係式を見比べていて、bに対応する生成元がないのはなぜだろうと、しばらく考えていたのですが、

a^-1*c*a = b

から出てくるので、必要なかったのでした。

ちなみにこの群は、Q8とC3の半直積として構成できます。

それから、生成元と関係式は、なるべく対応関係がわかりやすくなるように書いている（書き直している）のですが、必ずしも対応関係が明白でないものもあります。

SL(2,3)

のところをチェックしていて、あることに気付きました。

記述が間違いというわけではないのですが、追加した方がよい点があったので、可能であれば明日あたりまで修正します。

さらに修正

C5 : C4 (2) の関係式を、生成元に対応するように修正しました。元のものも間違っていたわけではないのですが(2番目の生成元に対応)、わかりやすくなるようにしました。