直線プログラム

コンピュータサイエンスにおいて、直線プログラムとは、非公式には、ループやテストを含まず、以前に計算された要素に各操作を適用する一連のステップによって形成されるプログラムです。

この記事は、許可される演算が群の演算、つまり乗算と逆演算である場合について取り上げます。より具体的には、有限群G = ⟨ S ⟩ の直線計画( SLP ) は、 Gの要素の有限シーケンスLであり、 Lのすべての要素はSに属するか、前の要素の逆であるか、または 2 つの前の要素の積です。 SLP L は、 g がSとその逆のワードでエンコードされている場合、 g  ∈  Lであれば、群の要素g  ∈  Gを計算すると言われています。

直感的には、何らかのg  ∈  Gを計算する SLP は、g をS上のグループワードとして格納する効率的な方法です。 g がiステップで構築される場合、 gのワード長はiについて指数関数的である可能性がありますが、対応する SLP の長さは iについて線形であることに注意してください。 これは、 SLP を使用してグループ要素を特定の生成セット上のワードとして効率的にエンコードすることにより、 計算群論で重要な用途があります。

直線計画法は、1984年にババイとセメレディによって、特定の行列群の特性の計算の複雑さを研究するためのツールとして導入されました^{[1] 。ババイとセメレディは、有限群}Gのすべての要素には、すべての生成集合において長さO (log ² | G |)の直線計画法があることを証明しました。

構成的帰属問題に対する効率的な解法は、多くの群論的アルゴリズムにとって重要です。これは、SLP の観点から次のように述べることができます。有限群G  = ⟨ S ⟩ およびg  ∈  Gが与えられたとき、 S上で g を計算する直線プログラムを見つけます。構成的帰属問題は、ブラックボックス群の設定でよく研究されます。要素は、固定長のビット文字列によってエンコードされます。乗算、反転、および恒等式との等価性のチェックという群論的機能に対して、3 つのオラクルが提供されます。ブラックボックス アルゴリズムは、これらのオラクルのみを使用するアルゴリズムです。したがって、ブラックボックス群の直線プログラムはブラックボックス アルゴリズムです。

オンラインのATLAS of Finite Groupsでは、豊富な有限単純群に対する明示的な直線プログラムが提供されています。

Gを有限群、S をGのサブセットとします。Gの要素のシーケンスL = ( g ₁ ,..., g _m ) は、各g _{i が}次の 3 つの規則のいずれかによって取得できる 場合、 S上の直線プログラムです。

1. g _i ∈ S
2. g _i = g _j g _k（あるjに対して、k < i）${\displaystyle \cdot}$
3. g _i = g⁻¹
   _秒あるj < iに対して。

要素g ∈ Gの直線コスト c ( g | S ) は、 gを計算するS上の最短直線プログラムの長さです。 gがSによって生成されるサブグループにない場合、コストは無限大です。

直線プログラムは述語論理における導出に似ています。S の要素は公理に対応し、グループ演算は推論規則に対応します。

Gを有限群、S をGのサブセットとします。あるg ∈ Gを計算するS上の長さmの直線プログラムは、各iに対してw iが_Sの何らかの要素の記号であるか、ある_j < i に対してw _i = ( w _j ,-1) であるか、あるj、k < iに対してw _i = ( w _j、w _k ) であるか、_Gで明白な方法で評価されるとw _mが値gをとるような一連の式( w 1 、... 、 w m )です。

^[2]に出てくる元の定義では、G =⟨ S ⟩であることが要求されます。上記の定義は、これを一般化したものです。

計算の観点から見ると、直線プログラムの正式な定義にはいくつかの利点があります。まず、抽象表現のシーケンスは、生成セット上の項よりもメモリが少なくて済みます。次に、直線プログラムをGの 1 つの表現で構築し、別の表現で評価することができます。これは、いくつかのアルゴリズムの重要な機能です。^[2]

二面体群D 12_{は六角形の対称性の群です。これは 60 度回転 ρ と 1 回の反射 λ によって生成できます。次の左端の列は λρ} ³の直線プログラムです。

6文字の順列群S ₆では、α=(1 2 3 4 5 6)とβ=(1 2)を生成元として取ることができます。ここで左端の列は、(1 2 3)(4 5 6)を計算する直線プログラムの例です。

有限群の短い記述。直線プログラムは、 一階述語論理による有限群の圧縮を研究するために使用できます。直線プログラムは、 G を記述する「短い」文(つまり、| G | よりもはるかに短い) を作成するためのツールを提供します。より詳細には、直線プログラムは、すべての有限単純群が長さO (log| G |)の一次記述を持ち、すべての有限群Gが長さO (log ³ | G |)の一次記述を持つことを証明するために使用されます。^[3]

有限単純群の最大部分群の生成集合を計算する直線プログラム。オンラインATLAS of Finite Group Representations ^[4]は、多数の有限単純群の最大部分群の生成集合を計算するための抽象的な直線プログラムを提供している。

例:スズキ群の無限族に属する群 Sz(32) は、生成元aとbによって階数 2 を持ちます。ここで、aは位数 2、bは位数 4、abは位数 5、ab ²は位数 25、abab ² ab ^{3は位数 25 です。以下は、最大部分群 E} ₃₂ ·E ₃₂ ⋊C ₃₁の生成集合を計算する直線プログラムです。この直線プログラムは、オンラインの有限群表現の ATLAS にあります。

到達可能性定理は、Sによって生成された有限群Gが与えられた場合、各g ∈ Gの最大コストは(1 + lg| G |) ²であると述べています。これは、生成元から群の要素を生成するのがどれだけ難しいかについての境界として理解できます。

ここで関数lg( x )は対数関数の整数値バージョンです。k ≥ 1の場合、lg ( k ) = max{ r  : ^2r≤k }とします。

証明の考え方は、新しい生成セットとして機能するセットZ = { z ₁ ,..., z _s } を構築することです ( s はプロセス中に定義されます)。これは通常Sよりも大きくなりますが、 Gの任意の要素はZ上の最大で長さ2| Z |の単語として表現できます。セットZ は、増加するセットのシーケンスK ( i ) を帰納的に定義することによって構築されます。

K ( i ) = { z ₁ ^{α ₁} · z ₂ ^{α ₂} ·...· z _i ^{α _i}  : α _j ∈ {0,1}} とします。ここで、z _iはi番目のステップでZに追加されるグループ要素です。c ( i ) は、 Z ( i ) = { z ₁ ,..., z _i }を含む最短直線プログラムの長さを表します。K (0) = {1 _G }、c (0)=0 とします。集合Z を再帰的に定義します。

• K ( i ) ⁻¹ K ( i ) = Gの場合、s が値iを取ることを宣言して停止します。
• それ以外の場合は、 「コスト増加」 c ( i +1)−c ( i )を最小化するzi _{+ 1∈G} \ K ( i ) ^−1K ( i ) （空でない）を選択します。

このプロセスにより、Z は任意のg ∈ G をK ( i ) ⁻¹ K ( i )の要素として記述できるように定義され、 Zから生成するのが実質的に容易になります。

ここで、プロセスが lg(| G |) ステップ以内に終了することを確認するために、次の主張を検証する必要があります。

次の主張は、すべてのグループ要素のコストが必要な境界内にあることを示すために使用されます。

g ₁ ∈ K ( i ) ⁻¹ K ( i ) を生成するには、最大で 2 iステップかかります。最大長の要素は恒等元なので、生成する意味はありません。したがって、 2 i −1ステップで十分です。g 1 · g ₂ ∈ G \ K ( i ) ⁻¹ K ( i ) を生成するには、 2 iステップ_で十分です。

これで定理は完成です。K ( s ) −1 K ( s ) = G^なので、任意のg ∈ Gはkの形で表すことができます。⁻¹
₁· k ₂とk⁻¹
₁, k ₂ ∈ K ( s )。系2により、Z ( s ) = Zを生成するには最大でs ² − sステップが必要であり、 Z ( s )からgを生成するには2 s − 1ステップ以下で済みます。

したがってc ( g | S ) ≤ s ² + s − 1 ≤ lg ² | G | + lg| G | − 1 ≤ (1 + lg| G |) ^{2 です}。