« 最短の置換表現について考える(9) | トップページ | あまり関係のない、ちょっとしたこと »

2009年6月29日 (月)

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

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

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

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

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

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

|

« 最短の置換表現について考える(9) | トップページ | あまり関係のない、ちょっとしたこと »

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: 最長の置換表現について考える:

« 最短の置換表現について考える(9) | トップページ | あまり関係のない、ちょっとしたこと »