シュライアーベクトル

数学、特に計算群論の分野において、シュライアーベクトルは、順列群の軌道を計算するために必要な時間と空間の複雑さを軽減するためのツールです。

概要

G が有限集合 に作用する生成系列を持つ有限群であるとする。計算群論における一般的な課題は、 G のもとで何らかの元の軌道を計算することである。同時に、 のシュライエベクトルを記録することができる。このベクトルは、任意の に対してを満たす元を見つけるために使用できる。シュライエベクトルを用いてこの処理を実行すると、これらの g を明示的に保存するよりも、必要な記憶領域と計算時間が少なくて済む。 ${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$ ${\displaystyle \Omega =\{1,2,...,n\}}$ ${\displaystyle \omega \in \Omega }$ ${\displaystyle \omega }$ ${\displaystyle g\in G}$ ${\displaystyle \omega ^{g}=\alpha }$ ${\displaystyle \alpha \in \omega ^{G}}$

正式な定義

ここで使用されるすべての変数は概要で定義されています。

のシュライアベクトルは次のようになるベクトルです。 ${\displaystyle \omega \in \Omega }$ ${\displaystyle \mathbf {v} =(v[1],v[2],...,v[n])}$

1. ${\displaystyle v[\omega ]=-1}$
2. （どのように選択されるかは次のセクションで明らかにされます）${\displaystyle \alpha \in \omega ^{G}\setminus \{{\omega }\},v[\alpha ]\in \{1,...,r\}}$ ${\displaystyle v[\alpha ]}$
3. ${\displaystyle v[\alpha ]=0}$ のために${\displaystyle \alpha \notin \omega ^{G}}$

アルゴリズムでの使用

ここでは擬似コードを使用して、2つのアルゴリズムにおけるシュライエベクトルの使用法 を示します。

• Gのもとでのωの軌道とそれに対応するシュライエベクトルを計算するアルゴリズム

入力: Ωのω、${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$

i が{ 0, 1, …, n } の場合:

v [ i ] = 0 に設定する

軌道を設定= { ω }、v [ ω ] = −1

αが軌道にあり、iが{1, 2, …, r }にある場合：

軌道上にない場合: ${\displaystyle \alpha^{x_{i}}}$

軌道に追加${\displaystyle \alpha^{x_{i}}}$

セット${\displaystyle v[\alpha ^{x_{i}}]=i}$

帰還軌道、v

• 最初のアルゴリズムのv^を用いて、Ω内のαに対してωg = αとなるようなG内のgを見つけるアルゴリズム

入力: v , α , X

v [ α ] = 0 の 場合:

falseを返す

g = e、k = v [ α ] と設定する（ここでeはGの単位元）

k ≠−1 の場合:

セット${\displaystyle g={x_{k}}g,\alpha =\alpha ^{x_{k}^{-1}},k=v[\alpha ]}$

gを返す

参考文献

• バトラー、G.（1991）、順列群の基礎アルゴリズム、コンピュータサイエンスの講義ノート、第559巻、ベルリン、ニューヨーク：シュプリンガー・フェアラーグ、ISBN 978-3-540-54955-0、MR  1225579
• ホルト、デレク F. (2005)、『計算群論ハンドブック』、ロンドン：CRCプレス、ISBN 978-1-58488-372-2
• Seress, Ákos (2003), Permutation group algorithms , Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press , ISBN 978-0-521-66103-4、MR  1970241