シュライアーベクトル

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

Gを生成列を持つ有限群とする${\displaystyle X=\{x_{1},x_{2},...,x_{r}\}}$有限集合に作用する${\displaystyle \Omega =\{1,2,...,n\}}$計算群論における一般的な課題の一つは、ある要素の軌道を計算することである。${\displaystyle \omega \in \Omega }$Gの下で。同時に、シュライアーベクトルを記録することができます。${\displaystyle \omega }$このベクトルは、要素を見つけるために使用できます。${\displaystyle g\in G}$満足${\displaystyle \omega ^{g}=\alpha }$どのような場合でも$\alpha \in \omega ^{G}}$これを行うためにシュライアーベクトルを使用すると、これらの 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}$のために$\alpha \notin \omega ^{G}}$

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

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

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

{0, 1, …, n } のiについて:

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を返す

• Butler, G. (1991), 「順列群の基本アルゴリズム」、Lecture Notes in Computer Science、第 559巻、ベルリン、ニューヨーク：Springer-Verlag、ISBN 978-3-540-54955-0MR 1225579​ 
• Holt, Derek F. (2005), 『計算群論ハンドブック』、ロンドン：CRC Press、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-4MR 1970241​