Konjugationsproblem
I abstrakt algebra är konjugationsproblemet för en grupp G med en given presentation beslutsproblemet att bestämma , givet två ord x och y i G , huruvida de representerar konjugerade element av G eller inte . Det vill säga, problemet är att avgöra om det finns ett element z i G så att
Konjugationsproblemet är också känt som transformationsproblemet .
Konjugationsproblemet identifierades av Max Dehn 1911 som ett av de grundläggande beslutsproblemen inom gruppteorin; de andra två är ordproblemet och isomorfismproblemet . Konjugationsproblemet innehåller ordproblemet som ett specialfall: om x och y är ord, är det att bestämma om de är samma ord lika med att bestämma om är identiteten, vilket är detsamma som att bestämma om det är konjugerat till identiteten. 1912 gav Dehn en algoritm som löser både ord- och konjugationsproblemet för de grundläggande grupperna av slutna orienterbara tvådimensionella grenrör av släktet större än eller lika med 2 (fallen av släktet 0 och släktet 1 är triviala).
Det är känt att konjugationsproblemet är oavgörbart för många klasser av grupper. Klasser av grupppresentationer för vilka det är känt att vara lösligt inkluderar:
- fria grupper (inga definierande släktingar)
- en-relator grupper med torsion
- flätgrupper
- knutgrupper
- ändligt presenterade konjugationsseparerbara grupper
- ändligt genererade abelska grupper (relatorer inkluderar alla kommutatorer)
- Gromov-hyperboliska grupper
- biautomatiska grupper
- CAT(0) -grupper
- Grundläggande grupper av geometriserbara 3-grenrör
- Magnus, Wilhelm ; Abraham Karrass; Donald Solitar (1976). Kombinatorisk gruppteori. Presentationer av grupper i termer av generatorer och relationer . Dover Publikationer . sid. 24 . ISBN 0-486-63281-4 .
- Johnson, DL (1990). Presentationer av grupper . Cambridge University Press . sid. 49. ISBN 0-521-37203-8 .
- Cohen, Daniel E. (1989). Kombinatorisk gruppteori: en topologisk ansats . Cambridge University Press. ISBN 0-521-34936-2 .
- Dehn, Max (1911). "Öber unendliche diskontinuierliche Gruppen". Matematik. Ann . 71 (1): 116–144. doi : 10.1007/BF01456932 . S2CID 123478582 .
- Dehn, Max (1912). "Transformation der Kurven auf zweiseitigen Flächen" . Matematik. Ann . 72 (3): 413–421. doi : 10.1007/BF01456725 . S2CID 122988176 .
- Newman, BB (1968). "Några resultat på en-relatorgrupper" . Tjur. Amer. Matematik. Soc . 74 (3): 568–571. doi : 10.1090/S0002-9904-1968-12012-9 .
- Bridson, Martin; Andre Haefliger (1999). Metriska utrymmen för icke-positiv krökning . Springer-Verlag. ISBN 978-3-540-64324-1 .
- Préaux, Jean-Philippe (2006). "Konjugationsproblem i grupper av orienterade geometriserbara 3-grenrör". Topologi . 45 (1): 171–208. arXiv : 1308.2888 . doi : 10.1016/j.top.2005.06.002 . S2CID 14602585 .