In themathematical subject ofgroup theory, theGrushko theorem or theGrushko–Neumann theorem is a theorem stating that therank (that is, the smallestcardinality of agenerating set) of afree 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^[1] and then, independently, in a 1943 article ofNeumann.^[2]

LetA andB befinitely generated groups and letA∗B be thefree product ofA andB. Then

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

It is obvious that rank(A∗B) ≤ rank(A) + rank(B) since if X is a finitegenerating set ofA andY is a finite generating set ofB thenX∪Y is a generating set forA∗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 ofNielsen equivalence. It states that ifM = (g₁,g₂, ...,g_n) is ann-tuple of elements ofG =A∗B such thatM generatesG, <g₁,g₂, ...,g_n> =G, thenM is Nielsen equivalent inG to ann-tuple of the form

M' = (a₁, ...,a_k,b₁, ...,b_n−k) where {a₁, ...,a_k}⊆A is a generating set forA and where {b₁, ...,b_n−k}⊆B is a generating set forB. In particular, rank(A) ≤k, rank(B) ≤n − k and rank(A) + rank(B) ≤k + (n − k) =n. If one takesM to be the minimal generating tuple forG, that is, withn = 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.

After the original proofs of Grushko (1940) andNeumann(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 ofKurosh.^[3]

Like the original proofs, Lyndon's proof (1965)^[4] relied on length-functions considerations but with substantial simplifications. A 1965 paper ofStallings^[5] gave a greatly simplified topological proof of Grushko's theorem.

A 1970 paper of Zieschang^[6] gave aNielsen equivalence version of Grushko's theorem (stated above) and provided some generalizations of Grushko's theorem foramalgamated free products. Scott (1974) gave another topological proof of Grushko's theorem, inspired by the methods of3-manifold topology^[7] Imrich (1984)^[8] gave a version of Grushko's theorem for free products with infinitely many factors.

A 1976 paper of Chiswell^[9] gave a relatively straightforward proof of Grushko's theorem, modelled on Stallings' 1965 proof, that used the techniques ofBass–Serre theory. The argument directly inspired the machinery offoldings for group actions on trees and forgraphs 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 ofaccessibility forfinitely generated andfinitely 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 groupG 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 iteratingsplittings of finitely generated groups over finite subgroups.Dunwoody proved that such a process must always terminate if a groupG is finitely presented^[13] but may go on forever ifG is finitely generated but not finitely presented.^[14]

An algebraic proof of a substantial generalization of Grushko's theorem using the machinery ofgroupoids was given by Higgins (1966).^[15] Higgins' theorem starts with groupsG andB with free decompositionsG = ∗_iG_i,B = ∗_iB_i andf :G →B a morphism such thatf(G_i) =B_i for alli. LetH be a subgroup ofG such thatf(H) =B. ThenH has a decompositionH = ∗_iH_i such thatf(H_i) =B_i for alli. Full details of the proof and applications may also be found in .^[10][16]

A useful consequence of the original Grushko theorem is the so-calledGrushko decomposition theorem. It asserts that any nontrivialfinitely generated groupG can be decomposed as afree product

G =A₁∗A₂∗...∗A_r∗F_s, wheres ≥ 0,r ≥ 0,

where each of the groupsA_i is nontrivial, freely indecomposable (that is, it cannot be decomposed as a free product) and not infinite cyclic, and whereF_s is afree group of ranks;moreover, for a givenG, the groupsA₁, ...,A_r are unique up to a permutation of theirconjugacy classes inG (and, in particular, the sequence ofisomorphism types of these groups is unique up to a permutation) and the numberss andr are unique as well.

More precisely, ifG =B₁∗...∗B_k∗F_t is another such decomposition thenk =r,s =t, and there exists apermutation σ∈S_r such that for eachi=1,...,r the subgroupsA_i andB_σ(i) areconjugate inG.

The existence of the above decomposition, called theGrushko decomposition ofG, 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. Positive results are available for some classes of groups such as torsion-freeword-hyperbolic groups, certain classes ofrelatively hyperbolic groups,^[18] fundamental groups of finite graphs of finitely generated free groups^[19] and others.

Grushko decomposition theorem is a group-theoretic analog of theKneser prime decomposition theorem for3-manifolds which says that a closed 3-manifold can be uniquely decomposed as aconnected 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).

LetS={g₁,....,g_n} be a finite generating set forG=A∗B of size |S|=n=rank(G). RealizeG as thefundamental group of a graph of groupsY which is a single non-loop edge with vertex groupsA andB and with the trivial edge group. Let${\displaystyle \tilde{\mathbf{Y}}}$ be theBass–Serre covering tree forY. LetF=F(x₁,....,x_n) be thefree group with free basisx₁,....,x_n and let φ₀:F →G be thehomomorphism such that φ₀(x_i)=g_i fori=1,...,n. RealizeF as thefundamental group of a graphZ₀ which is the wedge ofn circles that correspond to the elementsx₁,....,x_n. We also think ofZ₀ as agraph of groups with the underlying graphZ₀ and the trivial vertex and edge groups. Then the universal cover${\displaystyle {\tilde{Z}}_0}$ ofZ₀ and the Bass–Serre covering tree forZ₀ coincide. Consider a φ₀-equivariant map${\displaystyle r_0:{\tilde{Z}}_0\to \tilde{\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. Thegraph of groupsZ₀ serves as an initial approximation forY.

We now start performing a sequence of "folding moves" onZ₀ (and on its Bass-Serre covering tree) to construct a sequence ofgraphs of groupsZ₀,Z₁,Z₂, ...., that form better and better approximations forY. Each of the graphs of groupsZ_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. Thecomplexityc(Z_j) ofZ_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 havec(Z₀)=n.

The folding moves that takeZ_j toZ_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 identify 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 inZ_j. Therefore, the folding process must terminate in a finite number of steps with a graph of groupsZ_k that cannot be folded any more. It follows from the basicBass–Serre theory considerations thatZ_k must in fact be equal to the edge of groupsY and thatZ_k comes equipped with finite generating sets for the vertex groupsA andB. The sum of the sizes of these generating sets is the complexity ofZ_k which is therefore less than or equal toc(Z₀)=n. This implies that the sum of the ranks of the vertex groupsA andB is at mostn, that is rank(A)+rank(B)≤rank(G), as required.

Stallings' proof of Grushko Theorem follows from the following lemma.

LetF be a finitely generated free group, withn generators. LetG₁ andG₂ be two finitely presented groups. Suppose there exists a surjective homomorphism${\displaystyle \varphi :F\to G_1\ast G_2}$. Then there exists two subgroupsF₁ andF₂ ofF with${\displaystyle \varphi (F_1)=G_1}$ and${\displaystyle \varphi (F_2)=G_2}$, such that${\displaystyle F=F_1\ast F_2.}$

Proof: We give the proof assuming thatF has no generator which is mapped to the identity of${\displaystyle G_1\ast G_2}$, for if there are such generators, they may be added to any of${\displaystyle F_1}$ or${\displaystyle F_2}$.

The following general results are used in the proof.

1. There is a one or two dimensionalCW complex,Z withfundamental groupF. ByVan Kampen theorem, thewedge ofn circles is one such space.

2. There exists a two complex${\displaystyle X=X_1\cup X_2}$ where${\displaystyle \{p\}=X_1\cap X_2}$ is a point on a one cell ofX such thatX₁ andX₂ are two complexes with fundamental groupsG₁ andG₂ respectively. Note that by the Van Kampen theorem, this implies that the fundamental group ofX is${\displaystyle G_1\ast G_2}$.

3. There exists a map${\displaystyle f:Z\to X}$ such that the induced map${\displaystyle f_{\ast }}$ on the fundamental groups is same as${\displaystyle \varphi }$

For the sake of convenience, let us denote${\displaystyle f^{-1}(X_1)=:Z_1}$ and${\displaystyle f^{-1}(X_2)=:Z_2}$. Since no generator ofF maps to identity, the set${\displaystyle Z_1\cap Z_2}$ has no loops, for if it does, these will correspond to circles ofZ which map to${\displaystyle p\in X}$, which in turn correspond to generators ofF which go to the identity. So, the components of${\displaystyle Z_1\cap Z_2}$ are contractible.In the case where${\displaystyle Z_1\cap Z_2}$ has only one component, by Van Kampen's theorem, we are done, as in that case, :${\displaystyle F={\mathrm{\Pi }}_1(Z_1)\ast {\mathrm{\Pi }}_1(Z_2)}$.

The general proof follows by reducingZ to a space homotopically equivalent to it, but with fewer components in${\displaystyle Z_1\cap Z_2}$, and thus by induction on the components of${\displaystyle Z_1\cap Z_2}$.

Such a reduction ofZ is done by attaching discs along binding ties.

We call a map${\displaystyle \gamma :[0,1]\to Z}$ abinding tie if it satisfies the following properties

1. It ismonochromatic i.e.${\displaystyle \gamma ([0,1])\subseteq Z_1}$ or${\displaystyle \gamma ([0,1])\subseteq Z_2}$

2. It is atie i.e.${\displaystyle \gamma (0)}$ and${\displaystyle \gamma (1)}$ lie in different components of${\displaystyle Z_1\cap Z_2}$.

3. It isnull i.e.${\displaystyle f\circ \gamma ([0,1])}$ is null homotopic inX.

Let us assume that such a binding tie exists. Let${\displaystyle \gamma }$ be the binding tie.

Consider the map${\displaystyle g:[0,1]\to D^2}$ given by${\displaystyle g(t)=e^{it}}$. This map is ahomeomorphism onto its image. Define the space${\displaystyle Z^{\prime }}$ as

${\displaystyle Z^{\prime }=Z\coprod D^2/\sim }$ where :${\displaystyle x\sim y\text{ iff}\{\begin{array}{l}x=y,\text{ or }\\ x=\gamma (t)\text{ and }y=g(t)\text{ for some }t\in [0,1]\text{ or }\\ x=g(t)\text{ and }y=\gamma (t)\text{ for some }t\in [0,1]\end{array}}$

Note that the spaceZ' deformation retracts toZ We first extendf to a function${\displaystyle {}^{″}{f}^{″}:Z\coprod \mathrm{\partial }{D}^2/\sim }$ as

${\displaystyle f^{″}(x)=\{\begin{array}{l}f(x),x\in Z\\ p\text{ otherwise.}\end{array}}$

Since the${\displaystyle f(\gamma )}$ is null homotopic,${\displaystyle f^{″}}$ further extends to the interior of the disc, and therefore, to${\displaystyle Z^{\prime }}$.Let${\displaystyle Z_i^{\prime }=f^{\prime -1}(X_i)}$i = 1,2.As${\displaystyle \gamma (0)}$ and${\displaystyle \gamma (1)}$ lay in different components of${\displaystyle Z_1\cap Z_2}$,${\displaystyle Z_1^{\prime }\cap Z_2^{\prime }}$ has one less component than${\displaystyle Z_1\cap Z_2}$.

The binding tie is constructed in two steps.

Step 1: Constructing anull tie:

Consider a map${\displaystyle {\gamma }^{\prime }:[0,1]\to Z}$ with${\displaystyle {\gamma }^{\prime }(0)}$ and${\displaystyle {\gamma }^{\prime }(1)}$ in different components of${\displaystyle Z_1\cap Z_2}$. Since${\displaystyle f_{\ast }}$ is surjective, there exits a loop${\displaystyle \lambda }$ based at γ'(1) such that${\displaystyle f({\gamma }^{\prime })}$ and${\displaystyle f(\lambda )}$ are homotopically equivalent inX.If we define a curve${\displaystyle \gamma :[0,1]\to Z}$ as${\displaystyle \gamma (t)={\gamma }^{\prime }\ast \lambda (t)}$ for all${\displaystyle t\in [0,1]}$, then${\displaystyle \gamma }$ is a null tie.

Step 2: Making the null tiemonochromatic:

The tie${\displaystyle \gamma }$ may be written as${\displaystyle {\gamma }_1\ast {\gamma }_2\ast \cdots \ast {\gamma }_m}$ where each${\displaystyle {\gamma }_i}$ is a curve in${\displaystyle Z_1}$ or${\displaystyle Z_2}$ such that if${\displaystyle {\gamma }_i}$ is in${\displaystyle Z_1}$, then${\displaystyle {\gamma }_{i+1}}$ is in${\displaystyle Z_2}$ and vice versa. This also implies that${\displaystyle f({\gamma }_i)}$ is a loop based atp inX. So,

${\displaystyle [e]=[f(\gamma )]=[f({\gamma }_1)]\ast \cdots \ast [f({\gamma }_m)]}$

Hence,${\displaystyle [f({\gamma }_j)]=[e]}$ for somej. If this${\displaystyle {\gamma }_j}$ is a tie, then we have a monochromatic, null tie. If${\displaystyle {\gamma }_j}$ is not a tie, then the end points of${\displaystyle {\gamma }_j}$ are in the same component of${\displaystyle Z_1\cap Z_2}$. In this case, we replace${\displaystyle {\gamma }_j}$ by a path in${\displaystyle Z_1\cap Z_2}$, say${\displaystyle {\gamma }_j^{\prime }}$. This path may be appended to${\displaystyle {\gamma }_{j-1}}$ and we get a new null tie

${\displaystyle {\gamma }^{″}={\gamma }_1\ast \cdots \ast {\gamma }_{j-1}^{\prime }\ast {\gamma }_{j+1}\cdots {\gamma }_m}$, where${\displaystyle {\gamma }_{j-1}^{\prime }={\gamma }_{j-1}\ast {\gamma }_j^{\prime }}$.

Thus, by induction onm, we prove the existence of a binding tie.

Suppose that${\displaystyle G=A\ast B}$ is generated by${\displaystyle \{g_1,g_2,\dots ,g_n\}}$. Let${\displaystyle F}$ be the free group with${\displaystyle n}$-generators, viz.${\displaystyle \{f_1,f_2,\dots ,f_n\}}$. Consider the homomorphism${\displaystyle h:F\to G}$ given by${\displaystyle h(f_i)=g_i}$, where${\displaystyle i=1,\dots ,n}$.

By the lemma, there exists free groups${\displaystyle F_1}$ and${\displaystyle F_2}$ with${\displaystyle F=F_1\ast F_2}$ such that${\displaystyle h(F_1)=A}$ and${\displaystyle h(F_2)=B}$. Therefore,${\displaystyle \text{Rank }(A)\le \text{Rank }(F_1)}$ and${\displaystyle \text{Rank }(B)\le \text{Rank }(F_2)}$.Therefore,${\displaystyle \text{Rank }(A)+\text{Rank }(B)\le \text{Rank }(F_1)+\text{Rank }(F_2)=\text{Rank }(F)=\text{Rank }(A\ast B).}$

• Bass–Serre theory
• Generating set of a group

• Geometric group theory
• Geometric topology
• Theorems in group theory

• Webarchive template wayback links
• Articles with short description
• Short description matches Wikidata