群同型性問題

抽象代数学において、群同型性問題とは、与えられた 2 つの有限群表現が同型群を指すかどうかを判断する決定問題です。

同型性問題はマックス・デーン[ ^{1]によって定式化され、}単語問題および共役性問題とともに、彼が1911年に特定した群論における3つの基本的な決定問題の1つである。 ^[2]すべての有限提示群にわたるように定式化された3つの問題はすべて決定不可能である。同型性問題の場合、これは、アルゴリズムの実行にどれだけの（有限の）時間が許され、どれだけの（有限の）メモリが利用可能かに関係なく、2つの有限群の提示を取り、群が同型であるかどうかを判断するコンピュータアルゴリズムが存在しないことを意味する。実際、有限提示群が自明であるかどうかを判断する問題は決定不可能であり、^[3]セルゲイ・アディアンおよびマイケル・O・ラビンによるアディアン・ラビンの定理の結果である。

しかし、同型性問題の制限が決定可能であることが知られている有限提示群のクラスがいくつかあります。それらには、有限生成アーベル群、有限群、グロモフ双曲群^[4]、冪零放物線を持つ実質的に捩れのない相対双曲群^[5]、非自明な中心を持つ 1関係子群^[6]、および捩れを持つ2生成1関係子群^[7]が含まれます。

乗算表で与えられる群に限定された群同型問題はグラフ同型問題に還元できるが、その逆はできない。^[8]どちらも準多項式時間アルゴリズムを持っており、前者は1978年からロバート・タージャン^[9]に帰属し、後者は2015年からラースロー・ババイ[ ¹⁰ ]に帰属している。クラス2のp群の場合の小さいながらも重要な改善は、2023年にシャオルイ・サンによって得られた。^[11]^[8]

参考文献

^ マックス、デーン(1911)。「Uber unendliche discontinuierliche Gruppenn」。数学。アン。 71：116-144。土井：10.1007/BF01456932。S2CID 123478582。
^ マグナス、ウィルヘルム、カラス、アブラハム、ソリター、ドナルド(1996)。組み合わせ群論：生成子と関係の観点からの群の表現（第2版）。ニューヨーク：ドーバー出版。pp . 24–29。ISBN 04866328142022年10月14日閲覧– VDOC.PUB経由。
^ ミラー、チャールズ F. III (1992)。「グループの決定問題 - 調査と考察」(PDF) 。バウムスラッグ、ギルバート、ミラー、CF III (編)。組み合わせ群論におけるアルゴリズムと分類。数学科学研究所出版。第 23 巻。ニューヨーク: Springer-Verlag。pp. 1–59。doi : 10.1007/978-1-4613-9730-4_1。ISBN 9781461397328。（補論3.4参照）
^ Dahmani, François; Guirardel, Vincent (2011). 「すべての双曲群の同型性問題」.幾何学および機能解析. 21 (2): 223–300. arXiv : 1002.2590 . doi :10.1007/s00039-011-0120-0. S2CID 115165062.
^ ダーマニ、フランソワ;とういかん、ニコラス（2019-01-01）。「デーン充填を使用した同形性の決定、分割ケース」。数学の発明。215 (1): 81–169。土井：10.1007/s00222-018-0824-y。ISSN 1432-1297。
^ アルフレッド、ピエトロフスキ (1974-06-01)。「非自明な中心を持つ 1 関係子群の同型問題」。数学的ツァイシュリフト。136 (2): 95-106。土井：10.1007/BF01214345。ISSN 1432-1823。
^ Pride, Stephen J. (1977). 「捩れを伴う2生成子1関係子群の同型問題は解ける」.アメリカ数学会誌. 227 : 109–139. doi :10.1090/S0002-9947-1977-0430085-X. ISSN 0002-9947.
^ ab ハートネット、ケビン（2023年6月23日）。「コンピューター科学者が主要なアルゴリズムの目標に一歩近づく」。Quanta Magazine。
^ ミラー、ゲイリー L. (1978)。「nlog n 同型性技法について (予備報告)」。第 10 回 ACM コンピューティング理論シンポジウム議事録 - STOC '78 。ACMプレス。pp. 51–58。doi :10.1145/ 800133.804331。ISBN 978-1-4503-7437-8。
^ Babai、László (2017 年 1 月 9 日)、グラフ同型性の更新
^ Sun, Xiaorui (2023). 「クラス2および指数pのpグループの同型性の高速化」。arXiv ： 2303.15412 [ cs.DS ]。

ジョンソン、 DL (1997)。グループのプレゼンテーション（第2版）。ケンブリッジ：ケンブリッジ大学出版局。p. 49。doi : 10.1017/CBO9781139168410。ISBN 0521372038。

[1] マックス、デーン(1911)。「Uber unendliche discontinuierliche Gruppenn」。数学。アン。 71：116-144。土井：10.1007/BF01456932。S2CID 123478582。

[2] マグナス、ウィルヘルム、カラス、アブラハム、ソリター、ドナルド(1996)。組み合わせ群論：生成子と関係の観点からの群の表現（第2版）。ニューヨーク：ドーバー出版。pp . 24–29。ISBN 04866328142022年10月14日閲覧– VDOC.PUB経由。

[3] ミラー、チャールズ F. III (1992)。「グループの決定問題 - 調査と考察」(PDF) 。バウムスラッグ、ギルバート、ミラー、CF III (編)。組み合わせ群論におけるアルゴリズムと分類。数学科学研究所出版。第 23 巻。ニューヨーク: Springer-Verlag。pp. 1–59。doi : 10.1007/978-1-4613-9730-4_1。ISBN 9781461397328。（補論3.4参照）

[4] Dahmani, François; Guirardel, Vincent (2011). 「すべての双曲群の同型性問題」.幾何学および機能解析. 21 (2): 223–300. arXiv : 1002.2590 . doi :10.1007/s00039-011-0120-0. S2CID 115165062.

[5] ダーマニ、フランソワ;とういかん、ニコラス（2019-01-01）。「デーン充填を使用した同形性の決定、分割ケース」。数学の発明。215 (1): 81–169。土井：10.1007/s00222-018-0824-y。ISSN 1432-1297。

[6] アルフレッド、ピエトロフスキ (1974-06-01)。「非自明な中心を持つ 1 関係子群の同型問題」。数学的ツァイシュリフト。136 (2): 95-106。土井：10.1007/BF01214345。ISSN 1432-1823。

[7] Pride, Stephen J. (1977). 「捩れを伴う2生成子1関係子群の同型問題は解ける」.アメリカ数学会誌. 227 : 109–139. doi :10.1090/S0002-9947-1977-0430085-X. ISSN 0002-9947.

[:0-8] ハートネット、ケビン（2023年6月23日）。「コンピューター科学者が主要なアルゴリズムの目標に一歩近づく」。Quanta Magazine。

[9] ミラー、ゲイリー L. (1978)。「nlog n 同型性技法について (予備報告)」。第 10 回 ACM コンピューティング理論シンポジウム議事録 - STOC '78 。ACMプレス。pp. 51–58。doi :10.1145/ 800133.804331。ISBN 978-1-4503-7437-8。

[10] Babai、László (2017 年 1 月 9 日)、グラフ同型性の更新

[11] Sun, Xiaorui (2023). 「クラス2および指数pのpグループの同型性の高速化」。arXiv ： 2303.15412 [ cs.DS ]。