フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

あるサイズの巡回置換だけで任意の置換を作る

任意の置換は互換の積に表すことができます。では同じように、3元の巡回置換(i~j~k)i,j,kは相異なる)だけを組み合わせて任意の置換を作ることはできるでしょうか?

答えはNoです。(i~j~k)=(i~k)(i~j)(置換は右から合成する)と書けるので、3元の巡回置換は偶置換です。偶置換の積は偶置換なので、この方法では偶置換しか作ることができません。

しかし、実は3元の巡回置換を使えば全ての偶置換を作ることができます。すなわち、S_nn次の対称群、A_n交代群とし、k元の巡回置換で生成されるS_nの部分群をT^{(k)}_nとすると、次が成り立ちます。

命題1. ~T^{(3)}_n=A_n.

証明. 交わる2つの互換の積は3元の巡回置換に他ならず、交わらない2つの互換の積は(i~j)(k~l)=(i~j~k)(j~k~l)なので、2つの互換の積は必ずT^{(3)}_nに入る。A_nはこれらで生成されるからA_n\subset T^{(3)}_nである。逆の包含は3元の巡回置換が偶置換であることから明らか。~~~\square

実はより一般に次が成り立ちます。

命題2. ~kが奇数のときT^{(k)}_n=A_n.

証明. 命題1より、任意のk\geq 5について(3~4~5)\in T^{(k)}_nを示せばよい(すると対称性から任意の3元の巡回置換を含む)。

(k~(k-1)~\cdots~1)^2(1~2~4~3~5~6~~\cdots~k)^2=(1~2)(3~4)

より(1~2)(3~4)\in T^{(k)}_nであり、同様に(1~2)(3~5)\in T^{(k)}_nなので(3~4~5)=(1~2)(3~5)(1~2)(3~4)\in T^{(k)}_nとなる。~~~\square

ではkが偶数のときはどうなるでしょうか。

この場合、なんと任意の置換を作ることができます!以下の証明は箱(@o_ccah)さんから教えていただきました。

命題3. ~kが偶数のときT^{(k)}_n=S_n.

証明. k=2mとする。(1~2)\in T^{(k)}_nを示せばよい。

\sigma = (2~4~6~\cdots~2m~1~3~5~\cdots~(2m-1))\\ \tau=(1~2~\cdots~2m)

と置く。\tau^2\sigma^{-1}=(1~2)なので示された。~~~\square

このように、あるタイプの置換で生成される置換の全体を求めることは、しばしば面白いパズルになります。皆さんも是非オリジナルの置換パズルを考えてみてください。