Normal form for free groups and free product of groups

Normal Form for Free Groups

Let G be a free group with generating set S . Each element in G is represented by a word w = a 1 ⋯ a n , where a j ∈ S ± , 1 ⩽ j ⩽ n .

Definition. A word is called reduced if it contains no string of the form a a − 1 , a ∈ S ± .

Definition. A normal form for a free group G with generating set S is a choice of a reduced word in S for each element of G .

Normal Form Theorem for Free Groups. A free group has a unique normal form i.e. each element in G is represented by a unique reduced word.

Proof. An elementary transformation of a word w ∈ G consists of inserting or deleting a part of the form a a − 1 with a ∈ S ± . Two words w 1 and w 2 are equivalent, w 1 ≡ w 2 , if there is a chain of elementary transformations leading from w 1 to w 2 . This is obviously an equivalence relation on G . Let G 0 be the set of reduced words. We shall show that each equivalence class of words contains exactly one reduced word. It is clear that each equivalence class contains a reduced word, since successive deletion of parts a a − 1 from any word w must lead to a reduced word. It will suffice then to show that distinct reduced words u and v are not equivalent. For each x ∈ S define a permutation x Δ of G 0 by setting w ( x Δ ) = w x if w x is reduced and w ( x Δ ) = u if w = u x − 1 . Let P be the group of permutations of G 0 generated by the x Δ , x ∈ S . Let Δ ∗ be the multiplicative extension of Δ to a map Δ ∗ : W ↦ P . If u 1 ≡ u 2 , then u 1 Δ ∗ = u 2 Δ ∗ ; moreover 1 ( u Δ ∗ ) = u 0 is reduced with u 0 ≡ u . It follows that if u 1 ≡ u 2 with u 1 , u 2 reduced, then u 1 = u 2 .

Normal Form for Free Products

Let G = A ∗ B be the free product of groups A and B . Every element w ∈ G is represented by w = g 1 ⋯ g n where g j ∈ A  or  B for 1 ⩽ j ⩽ n .

Definition. A reduced sequence is a sequence g 1 , ⋯ , g n such that for 1 ⩽ j ⩽ n we have g j ∈ A  or  B , g j ≠ e and g j , g j + 1 are not in the same factor A or B . The identity element is represented by the empty set.

Definition. A normal form for a free product of groups is a representation or choice of a reduced sequence for each element in the free product.

Normal Form Theorem for Free Product of Groups. Consider the free product A ∗ B of two groups A and B . Then the following two equivalent statements hold. (1) If w = g 1 ⋯ g n , n > 0 , where g 1 , ⋯ , g n is a reduced sequence, then w ≠ 1 in A ∗ B . (2) Each element of A ∗ B can be written uniquely as w = g 1 ⋯ g n where g 1 , ⋯ , g n is a reduced sequence.

Equivalence

The fact that the second statement implies the first is easy. Now suppose the first statement holds and let:

g 1 ⋯ g m = w = h 1 ⋯ h n .

This implies

h n − 1 ⋯ h 1 − 1 g 1 ⋯ g m = 1.

Hence by first statement left hand side cannot be reduced. This can happen only if h 1 − 1 g 1 = 1 , i.e. g 1 = h 1 . Proceeding inductively we have m = n and g i = h i for all 1 ⩽ i ⩽ n . This shows both statements are equivalent.

Proof of (2)

Let W be the set of all reduced sequences in A ∗ B and S(W) be its group of permutations. Define φ : A → S(W) as follows:

φ ( a ) ( g 1 , g 2 , ⋯ , g m ) = { ( g 1 , g 2 , ⋯ , g m ) if  a = 1 ( a , g 1 , g 2 , ⋯ , g m ) if  g 1 ∈ B ( a g 1 , g 2 , ⋯ , g m ) if  g 1 ∈ A  and  a g 1 ≠ 1 ( g 2 , g 3 , ⋯ , g m ) if  g 1 ∈ A  and  a g 1 = 1.

Similarly we define ψ : B → S(W).

It is easy to check that φ and ψ are homomorphisms. Therefore by universal property of free product we will get a unique map φ ∗ ψ : A ∗ B → S(W) such that φ ∗ ψ (id)(1) = id(1) = 1.

Now suppose w = g 1 ⋯ g n , n > 0 , where ( g 1 , ⋯ , g n ) is a reduced sequence, then ϕ ∗ ψ ( w ) ( 1 ) = ( g 1 , ⋯ , g n ) . Therefore w = 1 in A ∗ B which contradicts n > 0.