Grushko theorem

In the mathematical subject of group theory, the Grushko theorem or the Grushko-Neumann theorem is a theorem stating that the rank (that is, the smallest cardinality of a generating set) of a free product of two groups is equal to the sum of the ranks of the two free factors. The theorem was first obtained in a 1940 article of Grushko [I. A. Grushko, "On the bases of a free product of groups", Matematicheskii Sbornik, vol 8 (1940), pp. 169–182. ] and then, independently, in a 1943 article of Neumann. [B. H. Neumann. "On the number of generators of a free product." Journal of the London Mathematical Society, vol 18, (1943), pp. 12–20.]

tatement of the theorem

Let "A" and "B" be finitely generated groups and let "A"∗"B" be the free product of "A" and "B". Then

:rank("A"∗"B") = rank("A") + rank("B").

It is obvious that rank("A"∗"B") ≤ rank("A") + rank("B") since if X is a finite generating set of "A" and "Y" is a finite generating set of "B" then "X"∪"Y" is a generating set for "A"∗"B" and that |"X"∪"Y"|≤|"X"| + |"Y"|. The opposite inequality, rank("A"∗"B") ≥ rank("A") + rank("B"), requires proof.

There is a more precise version of Grushko's theorem in terms of Nielsen equivalence. It states that if "M" = ("g"₁, "g"₂, ..., "g"_"n") is an "n"-tuple of elements of "G" = "A"∗"B" such that "M" generates "G", <"g"₁, "g"₂, ..., "g"_"n"> = "G", then "M" is Nielsen equivalent in "G" to an "n"-tuple of the form :"M"' = ("a"₁, ..., "a"_"k", "b"₁, ..., "b"_"n"−"k") where {"a"₁, ..., "a"_"k"}⊆"A" is a generating set for "A" and where {"b"₁, ..., "b"_"n"−"k"}⊆"B" is a generating set for "B". In particular, rank("A") ≤ "k", rank("B") ≤ "n" − "k" and rank("A") + rank("B") ≤ "k" + ("n" − "k") = "n". If one takes "M" to be the minimal generating tuple for "G", that is, with "n" = rank("G"), this implies that rank("A") + rank("B") ≤ rank("G"). Since the opposite inequality, rank("G") ≤ rank("A") + rank("B"), is obvious, it follows that rank("G")=rank("A") + rank("B"), as required.

History and generalizations

After the original proofs of Grushko (1940) and Neumann(1943), there were many subsequent alternative proofs, simplifications and generalizations of Grushko's theorem. A close version of Grushko's original proof is given in the 1955 book of Kurosh. [A. G. Kurosh, "The theory of groups. Vol. I." Translated and edited by K. A. Hirsch. Chelsea Publishing Co., New York, N.Y., 1955]

Like the original proofs, Lyndon's proof (1965) [, Roger C. Lyndon, "Grushko's theorem." Proceedings of the American Mathematical Society, vol. 16 (1965), pp. 822&ndash;826.] relied on length-functions considerations but with substantial simplifications. A 1965 paper of Stallings [John R. Stallings. "A topological proof of Grushko's theorem on free products." Mathematische Zeitschrift, vol. 90 (1965), pp. 1&ndash;8.] gave a greatly simplified topological proof of Grushko's theorem. An algebraic proof and a generalization of Grushko's theorem using the machinery of groupoids was given by Higgins (1966). [P. J. Higgins. "Grushko's theorem." Journal of Algebra, vol 4 (1966), pp. 365&ndash;372]

A 1970 paper of Zieschang [Heiner Zieschang. "Über die Nielsensche Kürzungsmethode in freien Produkten mit Amalgam." Inventiones Mathematicae, vol. 10 (1970), pp. 4&ndash;37] gave a Nielsen equivalence version of Grushko's theorem (stated above) and provided some generalizations of Grushko's theorem for amalgamated free products. Scott (1974) gave another topological proof of Grushko's theorem, inspired by the methods of 3-manifold topology [Peter Scott. "An introduction to 3-manifolds." Department of Mathematics, University of Maryland, Lecture Note, No. 11. Department of Mathematics, University of Maryland, College Park, Md., 1974 ] Imrich (1984) [Wilfried Imrich "Grushko's theorem." Archiv der Mathematik (Basel), vol. 43 (1984), no. 5, pp. 385-387] gave a version of Grushko's theorem for free products with infinitely many factors.

Modern techniques of Bass-Serre theory, particularly the machinery of "foldings" for group actions on trees and for graphs of groups provide a relatively straightforward proof of Grushko's theorem (see, for example John R. Stallings. "Foldings of G-trees." Arboreal group theory (Berkeley, CA, 1988), pp. 355&ndash;368, Mathematical Sciences Research Institute Publications, 19. Springer, New York, 1991; ISBN: 0-387-97518-7] Ilya Kapovich, Richard Weidmann, and Alexei Miasnikov. "Foldings, graphs of groups and the membership problem." International Journal of Algebra and Computation, vol. 15 (2005), no. 1, pp. 95&ndash;128] ).

Grushko's theorem is, in a sense, a starting point in Dunwoody's theory of "accessibility" for finitely generated and finitely presented groups. Since the ranks of the free factors are smaller than the rank of a free product, Grushko's theorem implies that the process of iterated splitting of a finitely generated group "G" as a free product must terminate in a finite number of steps (more precisely, in at most rank("G") steps). There is a natural similar question for iterating splittings of finitely generated groups over finite subgroups. Dunwoody proved that such a process must always terminate if a group "G" is finitely presented [Martin J. Dunwoody. "The accessibility of finitely presented groups." Inventiones Mathematicae, vol. 81 (1985), no. 3, pp. 449&ndash;457] but may go on forever if "G" is finitely generated but not finitely presented. [Martin J. Dunwoody. "An inaccessible group." Geometric group theory, Vol. 1 (Sussex, 1991), pp. 75&ndash;78, London Mathematical Society Lecture Notes Series, 181, Cambridge University Press, Cambridge, 1993. ISBN: 0-521-43529-3]

Grushko decomposition theorem

A useful consequence of the original Grushko theorem is the so-called Grushko decomposition theorem. It asserts that any nontrivial finitely generated group "G" can be decomposed as a free product

:"G" = "A"₁∗"A"₂∗...∗"A"_"r"∗"F"_"s" , where "s" ≥ 0, "r" ≥ 0,

where each of the groups "A"_"i" is nontrivial, freely indecomposable (that is, it cannot be decomposed as a free product) and not infinite cyclic, and where "F_s" is a free group of rank "s";moreover, for a given "G", the groups "A"₁, ..., "A"_"r" are unique up to a permutation of their conjugacy classes in "G" (and, in particular, the sequence of isomorphism types of these groups is unique up to a permutation) and the numbers "s" and "r" are unique as well.

More precisely, if "G" = "B"₁∗...∗"B"_"k"∗"F"_"t" is another such decomposition then "k" = "r", "s" = "t", and there exists a permutation σ∈"S"_"r" such that for each "i"=1,...,"r" the subgroups "A"_"i" and "B"_σ("i") are conjugate in "G".

The existence of the above decomposition, called the Grushko decomposition of "G", is an immediate corollary of the original Grushko theorem, while the uniqueness statement requires additional arguments (see, for example [John Stallings. [http://www.numdam.org/numdam-bin/fitem?id=SB_1975-1976__18__167_0 "Coherence of 3-manifold fundamental groups."] Séminaire Bourbaki, 18 (1975-1976), Exposé No. 481.] ).

Algorithmically computing the Grushko decomposition for specific classes of groups is a difficult problem which primarily requires being able to determine if a given group is freely decomposable. Positive results are available for some classes of groups such as torsion-free word-hyperbolic groups, certain classes of relatively hyperbolic groups [François Dahmani and Daniel Groves. [http://www.ams.org/tran/0000-000-00/S0002-9947-08-04486-3/ "Detecting free splittings in relatively hyperbolic groups".] Transactions of the American Mathematical Society. Posted online July 21, 2008.] , fundamental groups of finite graphs of finitely generated free groups [Guo-An Diao and Mark Feighn. [http://msp.warwick.ac.uk/gt/2005/09/p041.xhtml "The Grushko decomposition of a finite graph of finite rank free groups: an algorithm".] Geometry and Topology. vol. 9 (2005), pp. 1835&ndash;1880] and others.

Grushko decomposition theorem is a group-theoretic analog of the Kneser decomposition theorem for 3-manifolds which says that a closed 3-manifold can be uniquely decomposed as a connected sum of irreducible 3-manifolds. [H. Kneser, "Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten." Jahresber. Deutsch. Math. Verein., vol. 38 (1929), pp. 248&ndash;260]

ketch of the proof using Bass-Serre theory

The following is a sketch of the proof of Grushko's theorem based on the use of foldings techniques for groups acting on trees (see for complete proofs using this argument).

Let "S"={"g"₁,....,"g"_"n"} be a finite generating set for "G"="A"∗"B" of size |"S"|="n"=rank("G"). Realize "G" as the fundamental group of a graph of groups Y which is a single non-loop edge with vertex groups "A" and "B" and with the trivial edge group. Let $ilde\; mathbf\; Y$ be the Bass-Serre covering tree for Y. Let "F"="F"("x"₁,....,"x"_"n") be the free group with free basis "x"₁,....,"x"_"n" and let φ₀:"F" → "G" be the homomorphism such that φ₀("x"_"i")="g"_"i" for "i"=1,...,"n". Realize "F" as the fundamental group of a graph "Z"₀ which is the wedge of "n" circles that correspond to the elements "x"₁,....,"x"_"n". We also think of Z₀ as a graph of groups with the underlying graph "Z"₀ and the trivial vertex and edge groups. Then the universal cover $ilde\; Z\_0$ of "Z"₀ and the Bass-Serre covering tree for Z₀ coincide. Consider a φ₀-equivariant map $r\_0:\; ilde\; Z\_0\; o\; ilde\; mathbf\; Y$ so that it sends vertices to vertices and edges to edge-paths. This map is non-injective and, since both the source and the target of the map are trees, this map "folds" some edge-pairs in the source. The graph of groups Z₀ serves as an initial approximation for Y.

We now start performing a sequence of "folding moves" on Z₀ (and on its Bass-Serre covering tree) to construct a sequence of graphs of groups Z₀, Z₁, Z₂, ...., that form better and better approximations for Y. Each of the graphs of groups Z_j has trivial edge groups and comes with the following additional structure: for each nontrivial vertex group of it there assigned a finite generating set of that vertex group. The "complexity" "c"(Z_"j") of Z_"j" is the sum of the sizes of the generating sets of its vertex groups and the rank of the free group "π"₁("Z"_"j"). For the initial approximation graph we have "c"(Z₀)="n".

The folding moves that take Z_"j" to Z_"j"+1 can be of one of two types:
*folds that identify two edges of the underlying graph with a common initial vertex but distinct end-vertices into a single edge; when such a fold is performed, the generating sets of the vertex groups and the terminal edges are "joined" together into a generating set of the new vertex group; the rank of the fundamental group of the underlying graph does not change under such a move.
*folds that indentify two edges, that already had common initial vertices and common terminal vertices, into a single edge; such a move decreases the rank of the fundamental group of the underlying graph by 1 and an element that corresponded to the loop in the graph that is being collapsed is "added" to the generating set of one of the vertex groups.

One sees that the folding moves do not increase complexity but they do decrease the number of edges in "Z"_"j". Therefore the folding process must terminate in a finite number of steps with a graph of groups Z_"k" that cannot be folded any more. It follows from the basic Bass-Serre theory considerations that Z_"k" must in fact be equal to the edge of groups Y and that Z_"k" comes equipped with finite generating sets for the vertex groups "A" and "B". The sum of the sizes of these generating sets is the complexity of Z_"k" which is therefore less than or equal to "c"(Z₀)="n". This implies that the sum of the ranks of the vertex groups "A" and "B" is at most "n", that is rank("A")+rank("B")≤rank("G"), as required.

References

ee also

*Bass-Serre theory
*Generating set of a group