374:), a straightforward combinatorial proof is given that finitely generated subgroups of free groups are free. A generating set is called Nielsen reduced if there is not too much cancellation in products. The paper shows that every finite generating set of a subgroup of a free group is (singularly) Nielsen equivalent to a Nielsen reduced generating set, and that a Nielsen reduced generating set is a free basis for the subgroup, so the subgroup is free. This proof is given in some detail in (
669:
391:
340:
487:
taking the presentation to the trivial presentation if and only if the group is trivial. A special case is that of "balanced presentations", those finite presentations with equal numbers of generators and relators. For these groups, there is a conjecture that the required transformations are quite a
628:
The generating set used during the course of this algorithm can be proved to vary uniformly over all
Nielsen equivalent generating sets. However, this algorithm has a number of statistical and theoretical problems. For instance, there can be more than one Nielsen equivalence class of generators.
488:
bit simpler (in particular, do not involve adding or removing relators). If one allows taking the set of relators to any
Nielsen equivalent set, and one allows conjugating the relators, then one gets an equivalence relation on ordered subsets of a relators of a finitely presented group. The
448:
For a given generating set of a given finitely generated group, it is not necessarily true that every automorphism is given by a
Nielsen transformation, but for every automorphism, there is a generating set where the automorphism is given by a Nielsen transformation,
223:. Transformations of the first two kinds are analogous to row swaps, and cyclic row permutations. Transformations of the third kind correspond to scaling a row by an invertible scalar. Transformations of the fourth kind correspond to row additions.
269:
being an element of order 5, the two classes of generating sets are represented by and , and each class has 15 distinct elements. A very important generating set of a dihedral group is the generating set from its presentation as a
499:, pp. 131–132), an application of Nielsen transformations is given to solve the generalized word problem for free groups, also known as the membership problem for subgroups given by finite generating sets in free groups.
229:
When dealing with groups that are not free, one instead applies these transformations to finite ordered subsets of a group. In this situation, compositions of the elementary transformations are called
226:
Transformations of the first two types suffice to permute the generators in any order, so the third type may be applied to any of the generators, and the fourth type to any pair of generators.
253:
if there is a
Nielsen transformation taking one to the other. If the generating sets have the same size, then it suffices to consider compositions of regular Nielsen transformations.
300:
Unlike and , the generating sets and are equivalent. A transforming sequence using more convenient elementary transformations (all swaps, all inverses, all products) is:
947:
492:
is that the relators of any balanced presentation of the trivial group are equivalent to a set of trivial relators, stating that each generator is the identity element.
555:
methods to generate random generating sets of the group. The "product replacement algorithm" simply uses randomly chosen
Nielsen transformations in order to take a
274:. Such a generating set for a dihedral group of order 10 consists of any pair of elements of order 2, such as . This generating set is equivalent to via:
624:
Every time a new random element is desired, repeat the previous two steps, then return one of the generating elements as the desired random element
918:
885:
848:
818:
1255:
1250:
737:
426:
99:
is an automorphism of a free group, but this was not their original definition. The following gives a more constructive definition.
841:
Groups—Korea '94: Proceedings of the
International Conference Held at Pusan National University, Pusan, Korea, August 18–25, 1994
1260:
589:
514:
472:
489:
462:
1151:
1128:
1047:
1027:
36:
760:
Indeed all 840 ordered generating sets of size three are equivalent. This is a general feature of
Nielsen equivalence of
330:
64:
942:
802:
544:
538:
522:
68:
28:
234:. If one allows removing elements of the subset that are the identity element, then the transformation is called
220:
777:
476:
434:
103:
468:
241:
The image under a
Nielsen transformation (elementary or not, regular or not) of a generating set of a group
651:
uniformly at random, and replace the additional element by the product of the additional element with the
425:), it is shown that the automorphism defined by the elementary Nielsen transformations generate the full
261:
The dihedral group of order 10 has two
Nielsen equivalence classes of generating sets of size 2. Letting
1156:
1098:
Lustig, Martin; Moriah, Yoav (1993), "Generating systems of groups and
Reidemeister-Whitehead torsion",
1039:
732:
644:
In addition to the generating set, store an additional element of the group, initialized to the identity
484:
559:
on the graph of generating sets of the group. The algorithm is well studied, and survey is given in (
700:
508:
629:
Also, the elements of generating sets need be uniformly distributed (for instance, elements of the
483:. This is known to be intractable in general, even though there is a finite sequence of elementary
567:
Take any ordered generating set and append some copies of the identity element, so that there are
1222:
1004:
974:
910:
518:
438:
40:
914:
881:
844:
814:
720:
630:
1191:, Ohio State Univ. Math. Res. Inst. Publ., vol. 8, Walter de Gruyter, pp. 301–347,
836:
1212:
1173:
1165:
1140:
1107:
1079:
1051:
994:
966:
956:
806:
773:
636:
Most of these problems are quickly remedied in the following modification called "rattle", (
430:
24:
1234:
1196:
1121:
1091:
1063:
1016:
928:
895:
858:
828:
1230:
1192:
1177:
1144:
1117:
1087:
1059:
1012:
970:
924:
891:
877:
854:
824:
633:
can never occur in a generating set of minimal size, but more subtle problems occur too).
1131:(1921), "Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien",
1023:
902:
795:
1034:, De Gruyter Studies in mathematics, vol. 29, Berlin: Walter de Gruyter & Co.
668:
390:
339:
1244:
480:
271:
48:
869:
761:
552:
548:
865:
556:
76:
20:
1083:
1055:
44:
810:
1044:
Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001)
1112:
1184:
708:
72:
60:
711:
formulation of the obstruction to Nielsen equivalence was described in (
1226:
1169:
1070:
Lustig, Martin (1991), "Nielsen equivalence and simple-homotopy type",
1008:
978:
575:
1203:
Rapaport, Elvira Strasser (1959), "Note on Nielsen transformations",
723:
of the group ring and the Nielsen equivalence classes of generators.
1217:
1187:(2001), "What do we know about the product replacement algorithm?",
999:
961:
521:, which can be solved using Nielsen transformations and a method of
16:
Set of mathematical functions concerning algebraic group isomorphism
699:
To understand Nielsen equivalence of non-minimal generating sets,
1042:; Murray, Scott H. (2002), "Variants of product replacement",
985:
Evans, Martin J. (1989), "Primitive elements in free groups",
835:
Fine, Benjamin; Rosenberger, Gerhard; Stille, Michael (1995),
663:
385:
334:
574:
Repeat the following for a certain number of times (called a
801:, London Mathematical Society Student Texts, vol. 14,
67:), but are now used in a variety of mathematics, including
1032:
Discontinuous groups of isometries in the hyperbolic plane
441:
of free groups. This is also described in the textbook (
51:
and one of the main tools used in studying free groups, (
680:
402:
351:
87:) devotes all of chapter 3 to Nielsen transformations.
1154:(1924), "Die Isomorphismengruppe der freien Gruppen",
563:). One version of the algorithm, called "shake", is:
945:(1928), "Topological invariants of knots and links",
517:
concerns the fundamental groups of three-dimensional
427:
automorphism group of a finitely generated free group
52:
839:, in Kim, Ann Chi; Kim, A.C.; Johnson, D.L. (eds.),
837:"Nielsen transformations and applications: a survey"
526:
496:
442:
375:
106:
free group with ordered basis can be factored into
84:
1046:, Contemp. Math., vol. 298, Providence, R.I.:
772:+ 1 are equivalent. There are similar results for
719:). These show an important connection between the
637:
547:, it is important to generate random elements of a
797:Combinatorial group theory: a topological approach
794:
948:Transactions of the American Mathematical Society
1205:Proceedings of the American Mathematical Society
1189:Groups and computation, III (Columbus, OH, 1999)
987:Proceedings of the American Mathematical Society
219:These transformations are the analogues of the
1072:Proceedings of the London Mathematical Society
768:generators, then all generating sets of size
513:A particularly important special case of the
8:
905:; Karrass, Abraham; Solitar, Donald (2004),
716:
647:Every time a generator is replaced, choose
1216:
1111:
998:
960:
764:. If a finite group can be generated by
703:investigations have been useful, as in (
450:
47:which are a non-commutative analogue of
753:
551:. Popular methods of doing this apply
422:
371:
56:
843:, Walter de Gruyter, pp. 69–105,
712:
704:
607:th generator with the product of the
95:One of the simplest definitions of a
7:
560:
53:Fine, Rosenberger & Stille 1995
738:Automorphism group of a free group
600:uniformly at random from { 1, -1 }
527:Magnus, Karrass & Solitar 2004
497:Magnus, Karrass & Solitar 2004
467:A particularly simple case of the
443:Magnus, Karrass & Solitar 2004
376:Magnus, Karrass & Solitar 2004
249:. Two generating sets are called
108:elementary Nielsen transformations
85:Magnus, Karrass & Solitar 2004
14:
1030:(2003), Schmidt, Asmus L. (ed.),
707:). Continuing in these lines, a
315:, multiply 2nd generator into 3rd
312:, multiply 2nd generator into 3rd
309:, multiply 3rd generator into 2nd
306:, multiply 2nd generator into 3rd
667:
389:
338:
638:Leedham-Green & Murray 2002
515:isomorphism problem for groups
473:isomorphism problem for groups
265:be an element of order 2, and
102:A Nielsen transformation on a
1:
1048:American Mathematical Society
539:product replacement algorithm
533:Product replacement algorithm
63:of a free group is free (the
245:is also a generating set of
55:). They were introduced in (
23:, especially in the area of
615:th generator raised to the
1277:
1256:Computational group theory
1251:Combinatorial group theory
907:Combinatorial Group Theory
874:Combinatorial group theory
803:Cambridge University Press
545:computational group theory
536:
506:
460:
328:
81:Combinatorial Group Theory
69:computational group theory
29:combinatorial group theory
793:Cohen, Daniel E. (1989),
778:finitely generated groups
490:Andrews–Curtis conjecture
463:Andrews–Curtis conjecture
433:used these ideas to give
221:elementary row operations
1084:10.1112/plms/s3-62.3.537
811:10.1017/CBO9780511565878
717:Lustig & Moriah 1993
477:finitely presented group
445:, p. 131, Th 3.2).
331:Nielsen–Schreier theorem
325:Nielsen–Schreier theorem
110:of the following sorts:
65:Nielsen–Schreier theorem
469:word problem for groups
33:Nielsen transformations
1261:Combinatorics on words
1113:10.1006/jabr.1993.1096
1056:10.1090/conm/298/05116
485:Tietze transformations
429:. Nielsen, and later
97:Nielsen transformation
59:) to prove that every
1157:Mathematische Annalen
787:Textbooks and surveys
733:Tietze transformation
611:th generator and the
1040:Leedham-Green, C. R.
776:, and certain other
509:Alexander polynomial
435:finite presentations
1050:, pp. 97–104,
590:uniformly at random
571:elements in the set
503:Isomorphism problem
439:automorphism groups
382:Automorphism groups
130:Cyclically permute
1170:10.1007/BF01556078
1133:Math. Tidsskrift B
1100:Journal of Algebra
911:Dover Publications
679:. You can help by
401:. You can help by
350:. You can help by
251:Nielsen equivalent
104:finitely generated
920:978-0-486-43830-6
887:978-3-540-41158-1
850:978-3-11-014793-3
820:978-0-521-34133-2
774:polycyclic groups
697:
696:
631:Frattini subgroup
495:In the textbook (
419:
418:
368:
367:
1268:
1237:
1220:
1199:
1180:
1164:(3–4): 169–209,
1147:
1124:
1115:
1094:
1066:
1035:
1019:
1002:
981:
964:
943:Alexander, J. W.
931:
898:
870:Lyndon, Roger C.
861:
831:
800:
781:
758:
701:module theoretic
692:
689:
671:
664:
581:Choose integers
431:Bernhard Neumann
414:
411:
393:
386:
363:
360:
342:
335:
79:. The textbook
25:abstract algebra
1276:
1275:
1271:
1270:
1269:
1267:
1266:
1265:
1241:
1240:
1218:10.2307/2033582
1202:
1183:
1150:
1127:
1097:
1069:
1038:
1024:Fenchel, Werner
1022:
1000:10.2307/2048805
984:
962:10.2307/1989123
941:
938:
936:Primary sources
921:
903:Magnus, Wilhelm
901:
888:
878:Springer-Verlag
866:Schupp, Paul E.
864:
851:
834:
821:
792:
789:
784:
759:
755:
751:
746:
729:
721:Whitehead group
693:
687:
684:
677:needs expansion
662:
541:
535:
523:J. W. Alexander
511:
505:
465:
459:
415:
409:
406:
399:needs expansion
384:
364:
358:
355:
348:needs expansion
333:
327:
322:
259:
215:
208:
201:
192:
185:
175:
168:
159:
152:
143:
136:
127:
120:
93:
17:
12:
11:
5:
1274:
1272:
1264:
1263:
1258:
1253:
1243:
1242:
1239:
1238:
1211:(2): 228–235,
1200:
1181:
1152:Nielsen, Jakob
1148:
1129:Nielsen, Jakob
1125:
1106:(1): 170–198,
1095:
1078:(3): 537–562,
1074:, 3rd Series,
1067:
1036:
1028:Nielsen, Jakob
1020:
982:
955:(2): 275–306,
937:
934:
933:
932:
919:
899:
886:
862:
849:
832:
819:
788:
785:
783:
782:
752:
750:
747:
745:
742:
741:
740:
735:
728:
725:
695:
694:
674:
672:
661:
658:
657:
656:
645:
626:
625:
622:
621:
620:
601:
572:
537:Main article:
534:
531:
507:Main article:
504:
501:
461:Main article:
458:
455:
417:
416:
396:
394:
383:
380:
366:
365:
345:
343:
329:Main article:
326:
323:
321:
318:
317:
316:
313:
310:
307:
304:
298:
297:
294:
291:
288:
285:
282:
279:
258:
255:
217:
216:
213:
206:
199:
193:
190:
183:
177:
173:
164:
157:
148:
141:
134:
128:
125:
118:
92:
89:
39:, are certain
35:, named after
15:
13:
10:
9:
6:
4:
3:
2:
1273:
1262:
1259:
1257:
1254:
1252:
1249:
1248:
1246:
1236:
1232:
1228:
1224:
1219:
1214:
1210:
1206:
1201:
1198:
1194:
1190:
1186:
1182:
1179:
1175:
1171:
1167:
1163:
1160:(in German),
1159:
1158:
1153:
1149:
1146:
1142:
1138:
1135:(in Danish),
1134:
1130:
1126:
1123:
1119:
1114:
1109:
1105:
1101:
1096:
1093:
1089:
1085:
1081:
1077:
1073:
1068:
1065:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1033:
1029:
1025:
1021:
1018:
1014:
1010:
1006:
1001:
996:
992:
988:
983:
980:
976:
972:
968:
963:
958:
954:
950:
949:
944:
940:
939:
935:
930:
926:
922:
916:
912:
908:
904:
900:
897:
893:
889:
883:
879:
875:
871:
867:
863:
860:
856:
852:
846:
842:
838:
833:
830:
826:
822:
816:
812:
808:
804:
799:
798:
791:
790:
786:
779:
775:
771:
767:
763:
762:finite groups
757:
754:
748:
743:
739:
736:
734:
731:
730:
726:
724:
722:
718:
714:
710:
706:
702:
691:
682:
678:
675:This section
673:
670:
666:
665:
659:
655:th generator.
654:
650:
646:
643:
642:
641:
639:
634:
632:
623:
618:
614:
610:
606:
602:
599:
596:, and choose
595:
591:
588:
584:
580:
579:
577:
573:
570:
566:
565:
564:
562:
558:
554:
550:
546:
540:
532:
530:
528:
524:
520:
516:
510:
502:
500:
498:
493:
491:
486:
482:
481:trivial group
478:
474:
470:
464:
456:
454:
452:
451:Rapaport 1959
446:
444:
440:
436:
432:
428:
424:
413:
404:
400:
397:This section
395:
392:
388:
387:
381:
379:
377:
373:
362:
353:
349:
346:This section
344:
341:
337:
336:
332:
324:
319:
314:
311:
308:
305:
303:
302:
301:
295:
292:
289:
286:
283:
280:
277:
276:
275:
273:
272:Coxeter group
268:
264:
256:
254:
252:
248:
244:
239:
237:
233:
227:
224:
222:
212:
205:
198:
194:
189:
182:
178:
172:
167:
163:
156:
151:
147:
140:
133:
129:
124:
117:
113:
112:
111:
109:
105:
100:
98:
90:
88:
86:
82:
78:
74:
70:
66:
62:
58:
54:
50:
49:row reduction
46:
42:
41:automorphisms
38:
37:Jakob Nielsen
34:
30:
26:
22:
1208:
1204:
1188:
1161:
1155:
1136:
1132:
1103:
1099:
1075:
1071:
1043:
1031:
993:(2): 313–6,
990:
986:
952:
946:
906:
873:
840:
796:
769:
765:
756:
698:
685:
681:adding to it
676:
652:
648:
635:
627:
616:
612:
608:
604:
603:Replace the
597:
593:
586:
582:
568:
553:markov chain
549:finite group
542:
512:
494:
466:
457:Word problem
447:
423:Nielsen 1924
420:
407:
403:adding to it
398:
372:Nielsen 1921
369:
356:
352:adding to it
347:
320:Applications
299:
266:
262:
260:
250:
246:
242:
240:
235:
231:
228:
225:
218:
210:
203:
196:
187:
180:
170:
165:
161:
154:
149:
145:
138:
131:
122:
115:
107:
101:
96:
94:
80:
57:Nielsen 1921
32:
18:
713:Lustig 1991
709:K-theoretic
557:random walk
529:, Ch 3.4).
378:, Ch 3.2).
91:Definitions
77:knot theory
21:mathematics
1245:Categories
1178:50.0078.04
1145:48.0123.03
971:54.0603.03
744:References
705:Evans 1989
592:from 1 to
475:asks if a
45:free group
1185:Pak, Igor
1139:: 78–94,
780:as well.
688:July 2008
410:July 2008
359:July 2008
27:known as
872:(2001),
727:See also
660:K-theory
619:th power
561:Pak 2001
471:and the
296:, type 3
293:, type 1
290:, type 3
287:, type 4
284:, type 3
281:, type 1
278:, type 3
257:Examples
236:singular
195:Replace
179:Replace
73:k-theory
61:subgroup
1235:0104724
1227:2033582
1197:1829489
1122:1219664
1092:1095232
1064:1929718
1017:0952315
1009:2048805
979:1989123
929:0207802
896:0577064
859:1476950
829:1020297
715:) and (
576:burn in
479:is the
437:of the
232:regular
160:, ...,
144:, ...,
114:Switch
1233:
1225:
1195:
1176:
1143:
1120:
1090:
1062:
1015:
1007:
977:
969:
927:
917:
894:
884:
857:
847:
827:
817:
75:, and
1223:JSTOR
1005:JSTOR
975:JSTOR
749:Notes
519:knots
202:with
186:with
153:, to
43:of a
1137:1921
915:ISBN
882:ISBN
845:ISBN
815:ISBN
585:and
421:In (
370:In (
121:and
1213:doi
1174:JFM
1166:doi
1141:JFM
1108:doi
1104:157
1080:doi
1052:doi
995:doi
991:106
967:JFM
957:doi
807:doi
683:.
640:):
543:In
453:).
405:.
354:.
19:In
1247::
1231:MR
1229:,
1221:,
1209:10
1207:,
1193:MR
1172:,
1162:91
1118:MR
1116:,
1102:,
1088:MR
1086:,
1076:62
1060:MR
1058:,
1026:;
1013:MR
1011:,
1003:,
989:,
973:,
965:,
953:30
951:,
925:MR
923:,
913:,
909:,
892:MR
890:,
880:,
876:,
868:;
855:MR
853:,
825:MR
823:,
813:,
805:,
578:)
238:.
169:,
137:,
71:,
31:,
1215::
1168::
1110::
1082::
1054::
997::
959::
809::
770:d
766:d
690:)
686:(
653:k
649:k
617:e
613:j
609:i
605:i
598:e
594:n
587:j
583:i
569:n
525:(
449:(
412:)
408:(
361:)
357:(
267:y
263:x
247:G
243:G
214:2
211:x
209:·
207:1
204:x
200:1
197:x
191:1
188:x
184:1
181:x
176:.
174:1
171:x
166:n
162:x
158:2
155:x
150:n
146:x
142:2
139:x
135:1
132:x
126:2
123:x
119:1
116:x
83:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
