同じパターンのシャフルの固有多項式（q=110706の続き）

質問

http://oshiete1.goo.ne.jp/kotaeru.php3?q=110706
の回答に感動して、ネタを続けるための質問なので、あんまり良い質問ではありませんがよろしくお願いします。

N枚のトランプに同じパターンのシャフル操作Sをk回繰り返したとき(S^kと表す)、そのうち元に戻ります(トランプの並べ方のパターンがN! しかないから）。そこで、順番を入れ換えないシャフル(=1=S^n)を与える回数nを求めたいと思います。

まず、カードの軌道のようなものを考えて分類します。１つのカードに着目して、S^n1でもとの位置に戻るとします。そのときできる軌道上にはn1個のカードの位置があり、それらはすべてS^n1でもとの位置に戻るのが分かります。こうやって、カードの位置を、n1のグループ、n2のグループ、・・・で分けて、それらの最小公倍数 n でS^n=1となるはずです。（実際の計算ではこれで済むと思うのですが、q=110706のように一般的な式で表すとするとこれじゃだめなんでしょうね。）すると、n>Nとなる場合が多々ある気がします。一方、 行列Aの (m, n) 成分 (m,n = 0,1,2,...,N-1) を、シャフル前に n 番目にあったカードがシャフルで m 番目に移されるとき：1 、それ以外：0 として表現して固有多項式f(x)を求めると、Ｎ次式になります。さてさて、n>Nの場合はx^n-1= g(x)f(x)となる多項式があるということだと思うのですが、そうすると、f(x)ってそうとう形が限られると思うのですが、どうなると思われますか？・・・力不足で質問がつまんない・・・ですが、質問とは関係なく一般のシャフルについて計算するための良い方法があれば教えてください。

回答No.2

jun1038

こんばんは。junです。今日は２０回くらいのログインで、やっと回答のところに来ました。ＩＥ４との相性は最悪みたいですね。新しくなったｇｏｏのコンテンツでもこのことについて書いてありましたが、２回でログインできるというのは少なくとも私の場合あてはまりません。本題と関係ない話を長々とすみません。
　motsuanさんの質問のしかたが悪いのではなく、やはりこの問題が難しすぎるのでは？一枚ずつ交互にという比較的単純な場合でも多くの人が悩みましたよね。離散対数問題なんて言葉も出てきたし。一般化した場合なんてさらに難しくなるのでしょう？
　あるいはこの問題は、「群」に関する典型的な問題になる可能性があり、こんな匿名の掲示板よりも、きちんとした一本の論文に仕上げた方が得だと皆さん思っているのかしら。大学の数学の先生のような、「プロ」の方の意見を聞きたいものです。
　私の個人的な意見を少し。motsuanさんの補足の内容は少しは分かりましたが、１２・３４５の場合というのは、何というか周期が２と周期が３の「独立」したシャッフルが同調するのはどういうタイミングか、という、いわば単純な最小公倍数の問題になっているのではありませんか。
　私が考えていたのは、むしろ１つ１つの独立したシャッフルが何回で元に戻るかという議論です。各「細胞」の周期が分かればあとは最小公倍数でしょうから。
　１つのまとまりのカードの列が、どんな操作（置換）をするときに何回の操作で元に戻るか、ということのほうがより問題の本質だと思うのです。
　またまた生意気なことを言ってしまって大変申しわけありません。私は本当に数学に弱いので、motsuanさん始め多くの皆さんのお力が無いとどう考えて行ったらよいかすらよく分からないのです。よろしくお願いします。

お礼

どうもありがとうございます。
補足の表記が間違っていて趣旨を汲んでいただけるか心配だったのですが、その心配はなかったようで、ありがとうございました。

ところで、
>「群」に関する典型的な問題になる可能性があり、
についてですが、
質問の部分的な周期の最大公約数になるという部分については
ごく普通の有限アーベル群は巡回部分群の直積に分解されるという事情を表しているのだと思います。
あちこち漫然と書き散らして申し訳ありませんがよろしくお願いします。

補足

ごめんなさいややこしくしてしまって。

例示が間違っていて真に恐縮なのですが
（自分で自分の質問に答えられない＝訂正できないのです）、
本質的に、こういう周期列のあつまりに分けられるという主張です。
>最小公倍数の問題になっているのではありませんか。
というより、そういう具合い必ず分けることができるという主張です。
１２・３４５
２１・５３４（と書こうとおもっていました）
というふうに単純にみえなくっても
１２３４５
５４２３１、
あるいは
１２３４５
４５２１３
でもおなじですよね。なんでおなじかというと同じ周期でかつその入れ換えの集合見たいのが同じだからです。そういう意味です。
実際の場合は１つのカードを追い掛けてn1回でもとにもどれば、N-n1枚のカードから更に１枚選んで、その軌跡を追い掛けてn2回でもとにもどるとするとN-n1-n2枚のカードから一つ選んでそのカードの軌跡を追い掛けるという方法なので、効率としては現実的な範囲かなと思ったわけです。
１２３４５
１４２５３
でつづけて
１５４３２
１３５２４
１２３４５
でもいいのですが、そのときは
１枚目が周期１
２枚目が軌道として
２、３、５、４、繰り返し
３枚目が軌道として
５，４、２，３、繰り返し
という具合にすべてのカードが同じ周期で同じ軌道上にありますよね。
こういう状態を使えば少し計算が楽になりますが、もっと良い方法はないかと考えています。
シャフルのイメージが違うのでしょうか？

というわけでみなさまアドバイスなどよろしくお願いいたします。

回答No.1

jun1038

こんばんは。jun1038です。質問を受け継いで頂き、大変ありがとうございます。もっと早くお礼を言いたかったのですが、なぜがなかなかきちんとログインできませんでした。（今日はなぜかすんなりログインできた）
　私、数学にはほとんど素人なので、行列とか固有多項式についての話にはあまりコメントできません。すみません。
　素人の強み（？）で、q=110706 のときの様子からの「カン」をいくつか書かせていただきます。
　・すべてのカードは一斉に元に戻るのでは。もし反する例があれば撤回します。
　・ｎ＞Ｎとなる場合はなく、すべてｎ＜Ｎとなるのでは。（これもあくまでq=110706 のときがもとですが）
　・任意の操作（例えば最後の２枚を１枚目と２枚目の間に入れる）をいかに数学的に表現するか、そしてその操作の結果カードがどのように置換されるか、といった考え方の方が良いのでは。

　生意気なことを言ってすみませんが、皆さまどうぞよろしくお願いします。

お礼

どうもありがとうございます。110706の回答がとてもよかったので質問をあげさせていただきました。
質問がちょっとわかりにくくなってしまったのはよくなかったかなとちょっとお詫びいたします。

補足

どうも変な質問にして、かえって回答が付き難くなってしまったかも知れません。
シャフルのイメージなのですが私のイメージとしては以下のようなものもシャフルと考えています。
たとえば、置換の周期が二つある場合、簡単な例として
１２・３４５
を並べ換えて
２１・５４３
というシャフルを考えます（点は見やすいように入れました。１，２枚目の入れ換えと３，４，５枚目の循環の二つの周期を考えます）。これを繰り返すと
１２・３４５
２１・５４３
１２・４５３
２１・３４５
１２・５４３
２１・４５３
１２・３４５
となって、６回でもとに戻ります。
こういうシャフルを考えていたのですが、ちょっとイメージが違うのかな？