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 and then, independently, in a 1943 article of Neumann.
Statement of the theorem.
Let "A" and "B" be finitely generated groups and let "A"∗"B" be the free product of "A" and "B". Then
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.
Grushko, but not Neumann, proved a more precise version of Grushko's theorem in terms of Nielsen equivalence. It states that if "M" = ("g"1, "g"2, ..., "g""n") is an "n"-tuple of elements of "G" = "A"∗"B" such that "M" generates "G", <"g"1, "g"2, ..., "g""n"> = "G", then "M" is Nielsen equivalent in "G" to an "n"-tuple of the form 
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.
Like the original proofs, Lyndon's proof (1965) relied on length-functions considerations but with substantial simplifications. A 1965 paper of Stallings
 gave a greatly simplified topological proof of Grushko's theorem.
A 1970 paper of Zieschang 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 Imrich (1984) gave a version of Grushko's theorem for free products with infinitely many factors.
A 1976 paper of Chiswell gave a relatively straightforward proof of Grushko's theorem, modelled on Stallings' 1965 proof, that used the techniques of Bass–Serre theory. 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,
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 but may go on forever if "G" is finitely generated but not finitely presented.
An algebraic proof of a substantial generalization of Grushko's theorem using the machinery of groupoids was given by Higgins (1966). Higgins' theorem starts with groups "G" and "B" with free decompositions "G" = ∗"i" "G""i", "B" = ∗"i" "B""i" and "f" : "G" → "B" a morphism such that "f"("Gi") = "Bi" for all "i". Let "H" be a subgroup of "G" such that "f"("H") = "B". Then "H" has a decomposition "H" = ∗"i" "H""i" such that "f"("H""i") = "B""i" for all "i". Full details of the proof and applications may also be found in 
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
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 "Fs" is a free group of rank "s";
moreover, for a given "G", the groups "A"1, ..., "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"1∗...∗"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).
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, fundamental groups of finite graphs of finitely generated free groups and others.
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.
Sketch 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"1...,"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 formula_1 be the Bass–Serre covering tree for Y. Let "F"="F"("x"1...,"x""n") be the free group with free basis "x"1...,"x""n" and let φ0:"F" → "G" be the homomorphism such that φ0("x""i")="g""i" for "i"=1...,"n". Realize "F" as the fundamental group of a graph "Z"0 which is the wedge of "n" circles that correspond to the elements "x"1...,"x""n". We also think of Z0 as a graph of groups with the underlying graph "Z"0 and the trivial vertex and edge groups. Then the universal cover formula_2 of "Z"0 and the Bass–Serre covering tree for Z0 coincide. Consider a φ0-equivariant map formula_3 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 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. Each of the graphs of groups Zj 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 "π"1("Z""j"). For the initial approximation graph we have "c"(Z0)="n".
The folding moves that take Z"j" to Z"j"+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 "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"(Z0)="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.
Sketch of Stalling's proof.
Stallings' proof of Grushko Theorem follows from the following lemma.
Lemma.
Let "F" be finitely generated free group, with "n" generators. Let "G1" and "G2" be two finitely presented groups. Suppose there exists a surjective homomorphism formula_4, then there exists two subgroups "F1" and "F2" of "F" with formula_5 and formula_6 such that formula_7.
Proof: 
We give the proof assuming that "F" has no generator which is mapped to the identity of formula_8, for if there are such generators, they may be added to any of formula_9 or formula_10.
The following general results are used in the proof.
1. 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.
2. There exists a two complex formula_11 where formula_12 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 formula_8.
3. There exists a map formula_14 such that the induced map formula_15 on the fundamental groups is same as formula_16
For the sake of convenience, let us denote formula_17 and formula_18. 
Since no generator of "F" maps to identity, the set formula_19 has no loops, for if it does, these will correspond to circles of "Z" which map to formula_20, which in turn correspond to generators of "F" which go to the identity. So, the components of formula_19 are contractible.
In the case where formula_19 has only one component, by Van Kampen's theorem, we are done, as in that case, :formula_23.
The general proof follows by reducing "Z" to a space homotopically equivalent to it, but with fewer components in formula_19, and thus by induction on the components of formula_19.
Such a reduction of "Z" is done by attaching discs along binding ties.
We call a map formula_26 a binding tie if it satisfies the following properties
1. It is monochromatic i.e. formula_27 or formula_28
2. It is a tie i.e. formula_29 and formula_30 lie in different components of formula_19.
3. It is null i.e. formula_32 is null homotopic in X.
Let us assume that such a binding tie exists. Let formula_33 be the binding tie.
Consider the map formula_34 given by formula_35. This map is a homeomorphism onto its image. Define the space formula_36 as 
Note that the space "Z' " deformation retracts to "Z" 
We first extend "f" to a function formula_39 as 
Since the formula_41 is null homotopic, formula_42 further extends to the interior of the disc, and therefore, to formula_36 ".
Let formula_44 "i = 1,2".
As formula_29 and formula_30 lay in different components of formula_19, formula_48 has one less component than formula_19.
Construction of binding tie.
The binding tie is constructed in two steps.
Step 1: Constructing a null tie:
Consider a map formula_50 with formula_51 and formula_52 in different components of formula_19. Since formula_15 is surjective, there exits a loop formula_55 based at γ'(1) such that formula_56 and formula_57 are homotopically equivalent in "X".
If we define a curve formula_26 as formula_59 for all formula_60, then formula_61 is a null tie.
Step 2: Making the null tie monochromatic:
The tie formula_61 may be written as formula_63 where each formula_64 is a curve in formula_65 or formula_66 such that if formula_64 is in formula_65, then formula_69 is in formula_66 and vice versa. This also implies that formula_71 is a loop based at "p" in "X". So,
Hence, formula_73 for some "j". 
If this formula_74 is a tie, then we have a monochromatic, null tie. 
If formula_74 is not a tie, then the end points of formula_74 are in the same component of formula_19. In this case, we replace formula_74 by a path in formula_19, say formula_80. This path may be appended to formula_81 and we get a new null tie
formula_82, where formula_83.
Thus, by induction on "m", we prove the existence of a binding tie.
Proof of Grushko theorem.
Suppose that formula_84 is generated by formula_85. Let formula_86 be the free group with formula_87-generators, viz. formula_88. Consider the homomorphism formula_89 given by formula_90, where formula_91.
By the lemma, there exists free groups formula_9 and formula_10 with formula_94 such that formula_95 and formula_96. Therefore, formula_97 and formula_98.
Therefore, formula_99