892:
222:
347:
growing very quickly, namely faster than any fixed iterate of the exponential function. This example remains the fastest known growth of the Dehn function among one-relator groups. In 2011 Alexei
Myasnikov, Alexander Ushakov, and Dong Wook Won proved that
643:
1048:
455:
1500:, the blog of the Spring 2011 Berstein Seminar at Cornell, including van Kampen diagrams demonstrating subgroup distortion in the Baumslag–Gersten group and the discussion of Mitra-like examples
497:
786:
59:
753:
505:
274:
1086:
1257:
Myasnikov, Alexei; Ushakov, Alexander; Won, Dong Wook (2011). "The word problem in the
Baumslag group with a non-elementary Dehn function is polynomial time decidable".
306:
1222:
1154:
1497:
1401:
Diekert, Volker; Myasnikov, Alexei G.; Weiß, Armin (2016). "Conjugacy in
Baumslag's group, generic case complexity, and division in power circuits".
919:
is known to be decidable, but the only known worst-case upper bound estimate for the complexity of the conjugacy problem, due to Janis Beese, is
950:
378:
1513:
1315:
920:
1518:
923:. It is conjectured that this estimate is sharp, based on some reductions to power circuit division problems. There is a
900:
Myasnikov, Ushakov, and Won, using compression methods of ``power circuits" arithmetics, proved that the word problem in
464:
373:
1108:
of the
Baumslag–Gersten group, where Mitra's group possesses a rank three free subgroup that is highly distorted in
887:{\displaystyle \exp ^{\circ \log n}(1)=(\exp \underbrace {\circ \cdots \circ } _{\log n{\text{ times }}}\exp )(1)}
217:{\displaystyle G=\langle a,t\mid a^{a^{t}}=a^{2}\rangle =\langle a,t\mid (t^{-1}a^{-1}t)a(t^{-1}at)=a^{2}\rangle }
704:
924:
674:
353:
44:
20:
1101:
638:{\displaystyle G=\langle a,t\mid a^{a^{t}}=a^{2}\rangle =\langle a,b,t\mid a^{b}=a^{2},a^{t}=b\rangle .}
718:
908:
exhibits a large gap between the growth of its Dehn function and the complexity of its word problem.
230:
1122:
1112:, namely where the subgroup distortion is higher than any fixed iterated power of the exponential.
1458:
1410:
1268:
1259:
1194:
1053:
336:
51:
773:
grows faster than any fixed iterate of the exponential. Subsequently A. N. Platonov proved that
912:
328:
325:
279:
32:
1468:
1420:
1324:
1278:
1229:
1163:
1145:
697:
321:
1480:
1432:
1369:
1338:
1290:
1241:
1200:
1177:
1476:
1428:
1365:
1334:
1286:
1237:
1173:
658:
332:
36:
1507:
759:
693:
369:
344:
40:
1282:
1228:, Math. Sci. Res. Inst. Publ., vol. 23, New York: Springer, pp. 195–224,
666:
343:, despite being a one-relator group given by a rather simple presentation, has the
1446:
1233:
1226:
Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989)
1097:
1424:
1168:
1149:
1150:"A non-cyclic one-relator group all of whose finite factor groups are cyclic"
1472:
1329:
1310:
227:
Here exponential notation for group elements denotes conjugation, that is,
1498:
Distortion of finitely presented subgroups of non-positively curved groups
1463:
1043:{\displaystyle \langle a,t\mid (a^{p})^{(t^{-1}a^{k}t)}=a^{m}\rangle ,}
1353:
1093:
and generalized many of
Baumslag's original results in that context.
1415:
1273:
684:
is either an automorphism or its image is a cyclic subgroup of
450:{\displaystyle BS(1,2)=\langle a,b\mid a^{b}=a^{2}\rangle }
35:
exhibiting some remarkable properties regarding its finite
1354:"An isoparametric function of the Baumslag–Gersten group"
941:
Andrew
Brunner considered one-relator groups of the form
715:
is isomorphic to the additive group of dyadic rationals
1385:
331:
with an additional remarkable property that all finite
1387:(Diploma). Fakultät Mathematik, Universität Stuttgart.
927:
polynomial time solution of the conjugacy problem for
1203:
1056:
953:
789:
721:
508:
467:
381:
282:
233:
62:
492:{\displaystyle \langle a\rangle ,\langle b\rangle }
1216:
1080:
1042:
886:
747:
637:
491:
449:
300:
268:
216:
1449:(1998). "Coarse extrinsic geometry: a survey".
904:is solvable in polynomial time. Thus the group
1155:Journal of the Australian Mathematical Society
320:was originally introduced in a 1969 paper of
8:
1034:
954:
755:and in particular is not finitely generated.
629:
566:
560:
515:
486:
480:
474:
468:
444:
406:
211:
120:
114:
69:
360:Baumslag-Gersten group as an HNN extension
335:of this group are cyclic. Later, in 1992,
1462:
1414:
1328:
1272:
1208:
1202:
1167:
1055:
1028:
1007:
994:
986:
976:
952:
862:
852:
834:
794:
788:
731:
723:
722:
720:
649:Properties of the Baumslag–Gersten group
617:
604:
591:
554:
539:
534:
507:
466:
438:
425:
380:
281:
251:
238:
232:
205:
180:
155:
142:
108:
93:
88:
61:
1134:
1453:. Geometry & Topology Monographs.
1396:
1394:
1252:
1250:
1189:
1187:
7:
1304:
1302:
1300:
1140:
1138:
461:and two cyclic associated subgroups
1311:"On a class of one-relator groups"
14:
1224:-norms of finite presentations",
748:{\displaystyle \mathbb {Z} \left}
1316:Canadian Journal of Mathematics
19:In the mathematical subject of
1283:10.1016/j.jalgebra.2011.07.024
1016:
987:
983:
969:
881:
875:
872:
824:
818:
812:
400:
388:
269:{\displaystyle g^{h}=h^{-1}gh}
195:
173:
167:
135:
1:
356:solvable in polynomial time.
1197:(1992), "Dehn functions and
1234:10.1007/978-1-4613-9730-4_9
1081:{\displaystyle p,k,m\neq 0}
669:. In particular, the group
368:can also be realized as an
364:The Baumslag–Gersten group
316:The Baumslag–Gersten group
1535:
688:. In particular the group
50:The group is given by the
43:and the complexity of its
1425:10.1007/s00453-016-0117-z
1169:10.1017/S1446788700007783
324:, as an example of a non-
1309:Brunner, Andrew (1980).
758:Gersten proved that the
705:outer automorphism group
301:{\displaystyle g,h\in G}
1358:Moscow Univ. Math. Bull
1352:Platonov, A.N. (2004).
1514:Geometric group theory
1473:10.2140/gtm.1998.1.341
1330:10.4153/CJM-1980-032-8
1218:
1082:
1044:
888:
749:
639:
493:
451:
374:Baumslag–Solitar group
302:
270:
218:
25:Baumslag–Gersten group
21:geometric group theory
16:Geometric group theory
1383:Beese, Janis (2012).
1219:
1217:{\displaystyle l_{1}}
1083:
1045:
889:
750:
640:
494:
452:
303:
271:
219:
1519:Algebraic structures
1201:
1054:
951:
925:strongly generically
921:elementary recursive
787:
719:
506:
465:
379:
280:
231:
60:
27:, also known as the
1451:Geom. Topol. Monogr
1195:Gersten, Stephen M.
1123:Subgroup distortion
680:An endomorphism of
457:with stable letter
1260:Journal of Algebra
1214:
1078:
1040:
884:
868:
850:
745:
635:
489:
447:
298:
266:
214:
31:, is a particular
1146:Baumslag, Gilbert
913:conjugacy problem
865:
864: times
835:
833:
739:
675:residually finite
329:one-relator group
326:residually finite
33:one-relator group
1526:
1485:
1484:
1466:
1443:
1437:
1436:
1418:
1398:
1389:
1388:
1380:
1374:
1373:
1349:
1343:
1342:
1332:
1306:
1295:
1294:
1276:
1254:
1245:
1244:
1223:
1221:
1220:
1215:
1213:
1212:
1191:
1182:
1181:
1171:
1142:
1087:
1085:
1084:
1079:
1049:
1047:
1046:
1041:
1033:
1032:
1020:
1019:
1012:
1011:
1002:
1001:
981:
980:
893:
891:
890:
885:
867:
866:
863:
851:
846:
808:
807:
777:is equivalent to
754:
752:
751:
746:
744:
740:
732:
726:
644:
642:
641:
636:
622:
621:
609:
608:
596:
595:
559:
558:
546:
545:
544:
543:
498:
496:
495:
490:
456:
454:
453:
448:
443:
442:
430:
429:
322:Gilbert Baumslag
307:
305:
304:
299:
275:
273:
272:
267:
259:
258:
243:
242:
223:
221:
220:
215:
210:
209:
188:
187:
163:
162:
150:
149:
113:
112:
100:
99:
98:
97:
1534:
1533:
1529:
1528:
1527:
1525:
1524:
1523:
1504:
1503:
1494:
1489:
1488:
1464:math.DG/9810203
1445:
1444:
1440:
1400:
1399:
1392:
1382:
1381:
1377:
1351:
1350:
1346:
1308:
1307:
1298:
1256:
1255:
1248:
1204:
1199:
1198:
1193:
1192:
1185:
1144:
1143:
1136:
1131:
1119:
1102:word-hyperbolic
1052:
1051:
1024:
1003:
990:
982:
972:
949:
948:
938:
936:Generalizations
836:
790:
785:
784:
727:
717:
716:
654:
613:
600:
587:
550:
535:
530:
504:
503:
463:
462:
434:
421:
377:
376:
362:
337:Stephen Gersten
333:quotient groups
314:
278:
277:
247:
234:
229:
228:
201:
176:
151:
138:
104:
89:
84:
58:
57:
37:quotient groups
17:
12:
11:
5:
1532:
1530:
1522:
1521:
1516:
1506:
1505:
1502:
1501:
1493:
1492:External links
1490:
1487:
1486:
1438:
1409:(4): 961–988.
1390:
1375:
1344:
1323:(2): 414–420.
1296:
1246:
1211:
1207:
1183:
1133:
1132:
1130:
1127:
1126:
1125:
1118:
1115:
1114:
1113:
1091:
1090:
1089:
1088:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1039:
1036:
1031:
1027:
1023:
1018:
1015:
1010:
1006:
1000:
997:
993:
989:
985:
979:
975:
971:
968:
965:
962:
959:
956:
943:
942:
937:
934:
933:
932:
909:
897:
896:
895:
894:
883:
880:
877:
874:
871:
861:
858:
855:
849:
845:
842:
839:
832:
829:
826:
823:
820:
817:
814:
811:
806:
803:
800:
797:
793:
779:
778:
756:
743:
738:
735:
730:
725:
701:
678:
659:quotient group
653:
647:
646:
645:
634:
631:
628:
625:
620:
616:
612:
607:
603:
599:
594:
590:
586:
583:
580:
577:
574:
571:
568:
565:
562:
557:
553:
549:
542:
538:
533:
529:
526:
523:
520:
517:
514:
511:
488:
485:
482:
479:
476:
473:
470:
446:
441:
437:
433:
428:
424:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
361:
358:
313:
310:
297:
294:
291:
288:
285:
265:
262:
257:
254:
250:
246:
241:
237:
225:
224:
213:
208:
204:
200:
197:
194:
191:
186:
183:
179:
175:
172:
169:
166:
161:
158:
154:
148:
145:
141:
137:
134:
131:
128:
125:
122:
119:
116:
111:
107:
103:
96:
92:
87:
83:
80:
77:
74:
71:
68:
65:
29:Baumslag group
15:
13:
10:
9:
6:
4:
3:
2:
1531:
1520:
1517:
1515:
1512:
1511:
1509:
1499:
1496:
1495:
1491:
1482:
1478:
1474:
1470:
1465:
1460:
1456:
1452:
1448:
1442:
1439:
1434:
1430:
1426:
1422:
1417:
1412:
1408:
1404:
1397:
1395:
1391:
1386:
1379:
1376:
1371:
1367:
1363:
1359:
1355:
1348:
1345:
1340:
1336:
1331:
1326:
1322:
1318:
1317:
1312:
1305:
1303:
1301:
1297:
1292:
1288:
1284:
1280:
1275:
1270:
1266:
1262:
1261:
1253:
1251:
1247:
1243:
1239:
1235:
1231:
1227:
1209:
1205:
1196:
1190:
1188:
1184:
1179:
1175:
1170:
1165:
1161:
1157:
1156:
1151:
1147:
1141:
1139:
1135:
1128:
1124:
1121:
1120:
1116:
1111:
1107:
1103:
1100:considered a
1099:
1096:
1095:
1094:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1037:
1029:
1025:
1021:
1013:
1008:
1004:
998:
995:
991:
977:
973:
966:
963:
960:
957:
947:
946:
945:
944:
940:
939:
935:
930:
926:
922:
918:
914:
910:
907:
903:
899:
898:
878:
869:
859:
856:
853:
847:
843:
840:
837:
830:
827:
821:
815:
809:
804:
801:
798:
795:
791:
783:
782:
781:
780:
776:
772:
768:
764:
761:
760:Dehn function
757:
741:
736:
733:
728:
714:
710:
706:
702:
699:
695:
691:
687:
683:
679:
676:
672:
668:
664:
660:
657:Every finite
656:
655:
652:
648:
632:
626:
623:
618:
614:
610:
605:
601:
597:
592:
588:
584:
581:
578:
575:
572:
569:
563:
555:
551:
547:
540:
536:
531:
527:
524:
521:
518:
512:
509:
502:
501:
500:
483:
477:
471:
460:
439:
435:
431:
426:
422:
418:
415:
412:
409:
403:
397:
394:
391:
385:
382:
375:
371:
370:HNN extension
367:
359:
357:
355:
351:
346:
345:Dehn function
342:
338:
334:
330:
327:
323:
319:
311:
309:
295:
292:
289:
286:
283:
263:
260:
255:
252:
248:
244:
239:
235:
206:
202:
198:
192:
189:
184:
181:
177:
170:
164:
159:
156:
152:
146:
143:
139:
132:
129:
126:
123:
117:
109:
105:
101:
94:
90:
85:
81:
78:
75:
72:
66:
63:
56:
55:
54:
53:
48:
46:
42:
41:Dehn function
38:
34:
30:
26:
22:
1454:
1450:
1447:Mitra, Mahan
1441:
1406:
1403:Algorithmica
1402:
1384:
1378:
1364:(3): 12–17.
1361:
1357:
1347:
1320:
1314:
1264:
1258:
1225:
1159:
1153:
1109:
1105:
1092:
928:
916:
905:
901:
774:
770:
766:
762:
712:
708:
689:
685:
681:
670:
662:
650:
458:
365:
363:
354:word problem
349:
340:
339:showed that
317:
315:
226:
52:presentation
49:
45:word problem
28:
24:
18:
1457:: 341–364.
1267:: 324–342.
1162:: 497–498.
1098:Mahan Mitra
1508:Categories
1129:References
698:co-Hopfian
1416:1309.5314
1274:1102.2481
1073:≠
1035:⟩
996:−
967:∣
955:⟨
857:
848:⏟
844:∘
841:⋯
838:∘
831:
810:
802:
796:∘
630:⟩
585:∣
567:⟨
561:⟩
528:∣
516:⟨
487:⟩
481:⟨
475:⟩
469:⟨
445:⟩
419:∣
407:⟨
293:∈
253:−
212:⟩
182:−
157:−
144:−
133:∣
121:⟨
115:⟩
82:∣
70:⟨
1148:(1969).
1117:See also
352:has the
1481:1668308
1433:3567623
1370:2127449
1339:0571934
1291:2842068
1242:1230635
1178:0254127
1104:analog
694:Hopfian
673:is not
372:of the
312:History
1479:
1431:
1368:
1337:
1289:
1240:
1176:
1050:where
667:cyclic
39:, its
23:, the
1459:arXiv
1411:arXiv
1269:arXiv
769:) of
711:) of
911:The
775:f(n)
707:Out(
703:The
696:and
276:for
1469:doi
1421:doi
1325:doi
1279:doi
1265:345
1230:doi
1164:doi
915:in
870:exp
854:log
828:exp
799:log
792:exp
692:is
665:is
661:of
1510::
1477:MR
1475:.
1467:.
1429:MR
1427:.
1419:.
1407:76
1405:.
1393:^
1366:MR
1362:59
1360:.
1356:.
1335:MR
1333:.
1321:32
1319:.
1313:.
1299:^
1287:MR
1285:.
1277:.
1263:.
1249:^
1238:MR
1236:,
1186:^
1174:MR
1172:.
1160:10
1158:.
1152:.
1137:^
499::
308:.
47:.
1483:.
1471::
1461::
1455:1
1435:.
1423::
1413::
1372:.
1341:.
1327::
1293:.
1281::
1271::
1232::
1210:1
1206:l
1180:.
1166::
1110:G
1106:G
1076:0
1070:m
1067:,
1064:k
1061:,
1058:p
1038:,
1030:m
1026:a
1022:=
1017:)
1014:t
1009:k
1005:a
999:1
992:t
988:(
984:)
978:p
974:a
970:(
964:t
961:,
958:a
931:.
929:G
917:G
906:G
902:G
882:)
879:1
876:(
873:)
860:n
825:(
822:=
819:)
816:1
813:(
805:n
771:G
767:n
765:(
763:f
742:]
737:2
734:1
729:[
724:Z
713:G
709:G
700:.
690:G
686:G
682:G
677:.
671:G
663:G
651:G
633:.
627:b
624:=
619:t
615:a
611:,
606:2
602:a
598:=
593:b
589:a
582:t
579:,
576:b
573:,
570:a
564:=
556:2
552:a
548:=
541:t
537:a
532:a
525:t
522:,
519:a
513:=
510:G
484:b
478:,
472:a
459:t
440:2
436:a
432:=
427:b
423:a
416:b
413:,
410:a
404:=
401:)
398:2
395:,
392:1
389:(
386:S
383:B
366:G
350:G
341:G
318:G
296:G
290:h
287:,
284:g
264:h
261:g
256:1
249:h
245:=
240:h
236:g
207:2
203:a
199:=
196:)
193:t
190:a
185:1
178:t
174:(
171:a
168:)
165:t
160:1
153:a
147:1
140:t
136:(
130:t
127:,
124:a
118:=
110:2
106:a
102:=
95:t
91:a
86:a
79:t
76:,
73:a
67:=
64:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.