ライトの結合性テスト

数学において、ライトの結合性テストは、ケイリー乗算表によって有限集合で定義された二項演算が結合的であるかどうかをテストするために、FW ライトによって発明された手順です。ケイリー表によって指定された二項演算の結合性を検証する単純な手順は、各要素の 3 つから形成できる 2 つの積を比較するもので、扱いにくいものです。ライトの結合性テストにより、場合によってはタスクが簡素化されます (ただし、単純なアルゴリズムの最悪ケースの実行時間、つまりサイズ の集合については、改善されません)。 ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$${\displaystyle n}$

二項演算 ' · ' をケイリー表によって有限集合Aで定義します。 A内の何らかの要素aを選択すると、次のように 2 つの新しい二項演算がAで定義されます。

x y = x ⋅ ( a ⋅ y )${\displaystyle \star}$

x y = ( x ⋅ a ) ⋅ y${\displaystyle \circ}$

これらの演算のケイリー表が構築され、比較されます。表が一致する場合、すべてのxとyについてx · ( a · y ) = ( x · a ) · y が成立します。これは、集合Aのすべての要素について繰り返されます。

以下の例は、演算 ' ' および ' 'の Cayley 表の構築と比較の手順をさらに簡略化したものです。 ${\displaystyle \star}$${\displaystyle \circ}$

Aのすべての要素に対して' ' と ' 'のケイリー表を作成する必要はありません。 Aの適切な生成サブセット内の要素に対応する' ' と ' 'のケイリー表を比較するだけで十分です。 ${\displaystyle \star}$${\displaystyle \circ}$${\displaystyle \star}$${\displaystyle \circ}$

演算 ' . ' が可換である場合、x y = y x となります。結果として、x x = x x が常に成り立ち、x y = x y は y x = y x を意味するため、各ケイリー表の一部のみを計算する必要があります。 ${\displaystyle \star}$${\displaystyle \circ}$${\displaystyle \star}$${\displaystyle \circ}$${\displaystyle \star}$${\displaystyle \circ}$${\displaystyle \star}$${\displaystyle \circ}$

単位元eがある場合、 x と y の少なくとも 1 つが e に等しい場合は x y = x y が常に成立するため、ケイリー表に含める必要はありません。${\displaystyle \star}$${\displaystyle \circ}$

次のケイリー表（表1）で定義される 集合A = { a、b、c、d、e }内の二項演算「·」を考えます。

集合 { c , e } は、上記の表で定義された二項演算 ( a = e · e、b = c · c、d = c · e )の下での集合Aの生成集合です。したがって、 cに対応する二項演算 ' ' と ' ' が一致すること、およびeに対応する二項演算 ' ' と ' ' が一致することを検証すれば十分です。 ${\displaystyle \star}$${\displaystyle \circ}$${\displaystyle \star}$${\displaystyle \circ}$

cに対応する二項演算 ' ' と ' ' が一致することを確認するには、表 1 で要素cに対応する行を選択します。 ${\displaystyle \star}$${\displaystyle \circ}$

この行は新しいテーブル (表 3) のヘッダー行としてコピーされます。

ヘッダーaの下に表 1 の対応する列をコピーし、ヘッダーbの下に表 1 の対応する列をコピーするなどして、表 4 を作成します。

表 4 の列ヘッダーを削除すると、表 5 のようになります。

要素cに対応する二項演算 ' ' のケイリー表は表 6 で与えられます。 ${\displaystyle \star}$

次に、表 1 のc列を選択します。

この列をインデックス列にコピーすると、表 8 が得られます。

表 8 の索引エントリaに対して表 1 の対応する行をコピーし、索引エントリbに対して表 1 の対応する行をコピーするなどして、表 9 を作成します。

表 9 の最初の列のインデックス エントリを削除すると、表 10 のようになります。

要素cに対応する二項演算「 」のケーリー表は表11に示されています。 ${\displaystyle \circ}$

表 6 のさまざまなセルのエントリが、表 11 の対応するセルのエントリと一致していることを確認できます。これは、Aのすべてのxとyについて、 x · ( c · y ) = ( x · c ) · y であることを示しています。矛盾がある場合は、 Aのすべてのxとyについて、 x · ( c · y ) = ( x · c ) · yは真ではありません。

A内のすべてのxとyについてx · ( e · y ) = ( x · e ) · yであることは、次の表(表12と表13)を作成することによって同様の方法で検証できます。

二項演算 ' ' および ' 'の Cayley 表 (表 6 および表 11) を作成する必要はありません。表 1 のヘッダーcに対応する列を 表 5 のインデックス列にコピーして次の表 (表 14) を作成し、表 14 のa行が表 1 のa行と同じであること、表 14 のb行が表 1 のb行と同じであることなどを確認するだけで十分です。これは、 Aの生成セットのすべての要素に対して必要な変更を加えて繰り返されます。 ${\displaystyle \star}$${\displaystyle \circ}$

ライトの結合性テストを実行するためのコンピュータソフトウェアを書くこともできる。KehayopuluとArgyrisはMathematica用にそのようなプログラムを開発しました。^[1]

ライトの結合性テストは、より一般的な文脈での結合性をテストするように拡張することができます。^{[2] [3]}

T = { t ₁ , t ₂ , , t _m }を、演算が並置で表わされるマグマとする。X = { x ₁ , x ₂ , , x _n } を集合とする。直積T × XからXへの写像が( t , x ) ↦ txで表わされ、この写像が次の性質を持つかどうかをテストする必要があるとする。 ${\displaystyle \ldots}$${\displaystyle \ldots}$

( st ) x = s ( tx ) であり、すべてのs、t はTに含まれ 、すべてのx はXに含まれる。

ライトの結合性テストの一般化は、上記の性質が成り立つかどうかを検証するために適用することができる。数学的記法では、一般化は次のように実行される。Tの各tについて、L ( t )を、i番目の行が

( ( t _i t ) x ₁ , ( t _i t ) x ₂ , , ( t _i t ) x _n ) ただしi = 1, , m${\displaystyle \ldots}$${\displaystyle \ldots}$

R ( t ) をXのm × n要素の行列とし、そのj番目の列 の要素は

( t ₁ ( tx _j ) 、 t ₂ ( tx _j ) 、、 t _m ( tx _j ) ) ただしj = 1、、n。${\displaystyle \ldots}$${\displaystyle \ldots}$

一般化されたテスト（Bednarek による）によれば、検証されるプロパティは、T内のすべてのtに対してL ( t ) = R ( t )である場合にのみ成立します。X = Tの場合、 Bednarekのテストは Light のテストに簡略化されます。

ラジャゴパランとシュルマンによるランダム化アルゴリズムがあり、入力サイズに比例した時間で結合性をテストします。(この方法は、他の特定の恒等式のテストにも使用できます。) 具体的には、実行時間はテーブルで、エラー確率です。アルゴリズムを変更して、のトリプル(存在する場合) を時間 で生成できます。^[4]${\displaystyle O(n^{2}\log {\frac {1}{\delta }})}$${\displaystyle n\times n}$${\displaystyle \delta}$${\displaystyle \langle a,b,c\rangle }$${\displaystyle (ab)c\neq a(bc)}$${\displaystyle O(n^{2}\log n\cdot \log {\frac {1}{\delta }})}$

• クリフォード、アルフレッド・ホブリツェル、プレストン、ゴードン・バンフォード（1961）。半群の代数理論。第1巻。数学概論、第7号。プロビデンス、ロードアイランド州：アメリカ数学協会。ISBN 978-0-8218-0272-4. MR  0132791。(p.7～9)