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.
[2] Let A and B be finitely generated groups and let A∗B be the free product of A and B.
It states that if M = (g1, g2, ..., gn) is an n-tuple of elements of G = A∗B such that M generates G,
A close version of Grushko's original proof is given in the 1955 book of Kurosh.
A 1965 paper of Stallings [5] gave a greatly simplified topological proof of Grushko's theorem.
A 1970 paper of Zieschang[6] 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[7] Imrich (1984)[8] gave a version of Grushko's theorem for free products with infinitely many factors.
The argument directly inspired the machinery of foldings for group actions on trees and for graphs of groups and Dicks' even more straightforward proof of Grushko's theorem (see, for example, [10][11][12]).
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).
[14] An algebraic proof of a substantial generalization of Grushko's theorem using the machinery of groupoids was given by Higgins (1966).
It asserts that any nontrivial finitely generated group G can be decomposed as a free product where each of the groups Ai is nontrivial, freely indecomposable (that is, it cannot be decomposed as a free product) and not infinite cyclic, and where Fs is a free group of rank s; moreover, for a given G, the groups A1, ..., Ar 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 = B1∗...∗Bk∗Ft is another such decomposition then k = r, s = t, and there exists a permutation σ∈Sr such that for each i=1,...,r the subgroups Ai 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[17]).
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.
Grushko decomposition theorem is a group-theoretic analog of the Kneser prime decomposition theorem for 3-manifolds which says that a closed 3-manifold can be uniquely decomposed as a connected sum of irreducible 3-manifolds.
[20] 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 [10][11][12] for complete proofs using this argument).
The graph of groups Z0 serves as an initial approximation for Y.
We now start performing a sequence of "folding moves" on Z0 (and on its Bass-Serre covering tree) to construct a sequence of graphs of groups Z0, Z1, Z2, ...., that form better and better approximations for Y.
The folding moves that take Zj to Zj+1 can be of one of two types: One sees that the folding moves do not increase complexity but they do decrease the number of edges in Zj.
It follows from the basic Bass–Serre theory considerations that Zk must in fact be equal to the edge of groups Y and that Zk 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 Zk which is therefore less than or equal to c(Z0)=n.
Stallings' proof of Grushko Theorem follows from the following lemma.
There is a one or two dimensional CW complex, Z with fundamental group F. By Van Kampen theorem, the wedge of n circles is one such space.
is a point on a one cell of X such that X1 and X2 are two complexes with fundamental groups G1 and G2 respectively.
Note that by the Van Kampen theorem, this implies that the fundamental group of X is
has only one component, by Van Kampen's theorem, we are done, as in that case, :
The general proof follows by reducing Z to a space homotopically equivalent to it, but with fewer components in
Such a reduction of Z is done by attaching discs along binding ties.
as Note that the space Z' deformation retracts to Z We first extend f to a function
Thus, by induction on m, we prove the existence of a binding tie.