23/12/22 10:07:09.05 B/SAzY+J.net
現代数学虎の穴 河東ゼミの教え：徹底的に調べろ
URLﾘﾝｸ(ja.wikipedia.org)
群の表示
生成元と基本関係による群の表示（presentation of group）とは、群をその生成元と生成元の間に成り立つ関係によって特定することを言う。一般に群はある自由群の全射準同型像なので必ず表示を持つが、それは一意的ではない。
定義
略
よくある例
略
性質
定理
任意の群は生成元と基本関係による表示を持つ
これを見るには与えられた群 G に対し G 上の自由群 FG を作ればよい。
略
この表示は、G および K が必要以上に大きいときには極めて非効率なものとなり得ることに注意。
系
任意の有限群は有限表示を持つ
これは与えられた群の元すべてを生成元とし、乗積表を基本関係に置けばよい。
Novikov–Boone の定理
群に対する語の問題（英語版）に対する否定的な解答として、任意の有限表示 ⟨S | R⟩ に対して、与えられた二つの語 u, v がその群の同じ元を定めるか否かを決定するアルゴリズムは存在しないことが知られている。これは Pyotr Novikov（英語版）が1955年に[3]、また別証明をWilliam Boone（英語版）が1958年に[4]それぞれ得ている。
幾何学的群論
幾何学的群論の意味において、群の表示はある種の幾何を決定する。それはケイリーグラフであったり、語の距離（英語版）であったりといったものである。これらは二種類の順序（弱順序およびブリュア順序（英語版））を与え、ハッセ図と対応する。その重要な例はコクセター群である。
さらにいえば、このグラフの適当な性質（粗構造）は生成元の取り方に依らないという意味で内在的である。
URLﾘﾝｸ(en.wikipedia.org)
Word problem for groups
History
Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right,[1] together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2.[2] Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.[3][4][5]
It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable.[6] It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by William Boone in 1958.[7]
略