Posts Tagged ‘symmetric groups’

Every subgroup of an abelian group generated by n elements, can be generated by at most n elements

Posted: March 12, 2022 in Basic Algebra, Groups
Tags: , , ,
0

One of the first things we learn in group theory is that every subgroup of a cyclic group is cyclic. How do we prove that? Well, let G=\langle x \rangle be a cyclic group, and let H be a subgroup of G. If H=(1), there’s nothing to prove. For H \ne (1), choose m to be the smallest positive integer such that x^m \in H. We claim that H=\langle x^m\rangle. It is clear that \langle x^m \rangle \subseteq H because x^m \in H. Now suppose that y=x^k \in H. Dividing k by m, we get k=sm+r for some integers s, 0 \le r < m. Then y=x^k=x^{sm}x^r and so x^r=x^{-sm}y \in H. Hence r=0, by minimality of m. Thus y=x^{sm} \in \langle x^m\rangle and so H \subseteq \langle x^m\rangle, which proves H=\langle x^m\rangle.

We now extend the above to any finitely generated abelian group. Note that if G=\langle x_1, \cdots , x_n\rangle and G is abelian, then

G=\{x_1^{k_1} \cdots x_n^{k_n}: \ \ k_1, \cdots ,k_n \in \mathbb{Z}\}.

Problem 1. Let G be an abelian group generated by n elements. Show that every subgroup of G can be generated by at most n elements.

Solution. The proof is by induction over n. If n=1, then G is cyclic and, as we already showed at the beginning of this post, every subgroup of G is cyclic. Now let G=\langle x_1, \cdots , x_n\rangle, \ n \ge 2, be a finitely generated abelian group, and suppose that the claim is true for any abelian group generated by n-1 elements. Let H be a subgroup of G. If H \subseteq \langle x_1, \cdots , x_{n-1}\rangle, we are done by the induction hypothesis. Otherwise, there exists x_1^{k_1} \cdots x_n^{k_n} \in H such that k_n \ne 0. Choose

y=x^{k_1} \cdots x_{n-1}^{k_{n-1}}x_n^m \in H

such that m > 0 is minimal. Note that we can assume that m > 0 because if y \in H, then y^{-1} \in H. Now let h=x_1^{\ell_1} \cdots x_n^{\ell_n} \in H. Dividing \ell_n by m, we get \ell_n=sm+r for some integers s, 0 \le r < m. Hence

h=x_1^{\ell_1} \cdots x_{n-1}^{\ell_{n-1}}x_n^{\ell_n}=x_1^{\ell_1} \cdots x_{n-1}^{\ell_{n-1}}x_n^{sm+r}

and so

x_1^{\ell_1-sk_1} \cdots x_{n-1}^{\ell_{n-1}-sk_{n-1}}x_n^r=hy^{-s} \in H,

which gives r=0, by minimality of m. The above now gives

hy^{-s}=x_1^{\ell_1-sk_1} \cdots x_{n-1}^{\ell_{n-1}-sk_{n-1}} \in H \cap \langle x_1, \cdots ,x_{n-1}\rangle

and hence

h \in y^s(H \cap \langle x_1, \cdots ,x_{n-1}\rangle) \subseteq \langle y, H \cap \langle x_1, \cdots ,x_{n-1}\rangle\rangle.

Thus we have shown that H \subseteq \langle y, H \cap \langle x_1, \cdots ,x_{n-1}\rangle\rangle and so

H = \langle y, H \cap \langle x_1, \cdots ,x_{n-1}\rangle\rangle \ \ \ \ \ \ \ \ (*)

because clearly \langle y, H \cap \langle x_1, \cdots ,x_{n-1}\rangle\rangle \subseteq H. Now, by the induction hypothesis, H \cap \langle x_1, \cdots ,x_{n-1}\rangle can be generated by at most n-1 elements and hence, by (*), the subgroup H can be generated by at most n elements, which completes the induction and the solution. \ \Box

We now show that the result given in Problem 1 does not hold for non-abelian groups. But before that, we need to recall a well-known fact about symmetric groups.

Problem 2. Show that the symmetric group S_n, \ n \ge 3, can be generated by 2 elements.

Solution. We claim that S_n=\langle \alpha, \beta\rangle, where \alpha=(1 \ 2), \ \beta= (1 \ 2 \ \cdots \ n). Since the set of transpositions generates S_n, we only need to show that \langle \alpha, \beta \rangle contains every transposition. To do that, first use induction over k to show that

\beta^k \alpha \beta^{-k}=(k+1 \ k+2)

for all 0 \le k \le n-1, where, at k=n-1, by (n \ n+1) we mean (n \ 1)=(1 \ n). So we have shown that (k+1 \ k+2) \in \langle \alpha, \beta \rangle for all 0 \le k \le n-1. Now, the identity

(i \ i+k)(i+k \ \ i+k+1)(i \ i+k)=(i \ \ i+k+1)

proves, inductively, that (i \ j) \in \langle \alpha, \beta \rangle for all i,j. \ \Box

Problem 3. Show that the result given in Problem 1 is not always true for non-abelian groups.

Solution. Let H = \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2. By Cayley’s theorem, H can be embedded into the symmetric group \text{Sym}(H) \cong S_8. By Problem 2, S_8 can be generated by 2 elements, but clearly H, which is a subgroup of S_8, cannot be generated by less than 3 elements. \ \Box

Nilpotent groups (1)

Posted: January 11, 2022 in Basic Algebra, Groups
Tags: , , , , , , , , ,
0

Throughout this post, Z(G), G' are, respectively, the center and the commutator subgroup of a group G.

Let G be a group. In this post, we defined a normal series in G as a finite ascending chain of subgroups (1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G such that G_i is a normal subgroup of G for all 0 \le i \le n. Then we showed that G is solvable if and only if the normal series has this property that G_{i+1}/G_i is abelian. We are now interested in a special class of solvable groups called nilpotent groups.

Definition 1. Let G be a group. A normal series (1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G is said to be a central series if G_{i+1}/G_i \subseteq Z(G/G_i) for all 0 \le i \le n-1.

Definition 2. A group G is said to be nilpotent if it has a central series.

Remark 1. Every nilpotent group G is solvable.

Proof. Let (1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G be a central series. Since Z(G/G_i), the center of G/G_i, is abelian and G_{i+1}/G_i \subseteq Z(G/G_i), we get that G_{i+1}/G_i is abelian too. So the series is solvable, and hence G is solvable. \Box

Let G be a group, and let H,K be two subgroups of G. Recall that [H,K] is defined to be the subgroup generated by all the commutators [x,y]=xyx^{-1}y^{-1}, \ x \in H, y \in K. So, for example, G'=[G,G].

Remark 2. A group G is nilpotent if and only if it has a normal series (1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G such that [G_{i+1},G] \subseteq G_i for all 0 \le i \le n-1.

Proof. We just need to show that the conditions G_{i+1}/G_i \subseteq Z(G/G_i) and [G_{i+1},G] \subseteq G_i are equivalent. More generally, if H \subseteq K are subgroups of G and H is normal in G, then K/H \subseteq Z(G/H) if and only if [K,G] \subseteq H. That’s because K/H \subseteq Z(G/H) if and only if every element of K/H commutes with every element of G/H if and only if [K/H,G/H] is the trivial subgroup if and only if [K,G] \subseteq H. \ \Box

Remark 3. If G is a nilpotent group and (1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G is a central series, then we have G_1 \subseteq Z(G) and G' \subseteq G_{n-1}.

Proof. So we have G_{i+1}/G_i \subseteq Z(G/G_i) for all 0 \le i \le n-1. Choosing i=0,n-1, give, respectively, G_1 \subseteq Z(G) and G/G_{n-1} \subseteq Z(G/G_{n-1}), which means that G/G_{n-1} is abelian and so G' \subseteq G_{n-1}. This also follows from Remark 2, if we again choose i=0, n-1. \ \Box

Remark 4. Let G be a nilpotent group, and let N \ne (1) be a normal subgroup of G. Then N \cap Z(G) \ne (1), and so, in particular, if G \ne (1), then Z(G) \ne (1).

Proof. Suppose, to the contrary, that N \cap Z(G)=(1). Let

(1)=G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n=G

be a central series of G. We prove, by induction over i, that N \cap G_i=(1) for all i which then gives the contradiction N=N \cap G_n=(1). We have N \cap G_0=(1). Now suppose that N \cap G_i=(1). Let x \in N \cap G_{i+1}, \ g \in G. Then since G_{i+1}/G_i \subseteq Z(G/G_i), we have

G_ixg=G_ixG_ig=G_igG_ix=G_igx,

which gives y:=xgx^{-1}g^{-1} \in G_i. But since x \in N and N is normal, we also have y \in N and therefore y \in N \cap G_i=(1). So y=1 and hence xg=gx, i.e. x \in Z(G). But then x \in N \cap Z(G)=(1), and so x=1. Thus we have shown that N \cap G_{i+1}=(1), which completes the induction. \Box

Example 1. Every abelian group G is nilpotent because (1) \subseteq G is clearly a central series.

Example 2. If G is a group such that G/Z(G) is abelian, then G is nilpotent. In particular, D_8, the dihedral group of order eight, and the quaternion group Q_8 are nilpotent.

Proof. Clearly (1) \subseteq Z(G) \subseteq G is a central series, and so G is nilpotent. Now, by this post, |Z(D_8)|=2 and clearly Z(Q_8)=\{1,-1\} and so |Z(Q_8)|=2. Thus |D_8/Z(D_8)|=|Q_8/Z(Q_8)|=4, which implies that both D_8/Z(D_8) and Q_8/Z(Q_8) are abelian. So both D_8, Q_8 are nilpotent. \Box

Example 3. The symmetric group S_n is solvable if and only if n \le 4 and it is nilpotent if and only if n \le 2.

Proof. It is easy to show that the center of S_n, \ n \ge 3, is trivial (see the Exercise below) and so, by Remark 4, S_n is not nilpotent for n \ge 3. For n=1,2, \ S_n is abelian hence nilpotent, by Example 1. In this post (see Example 4, and the Exercise), we showed that S_n is solvable for n \le 4 and not solvable for n \ge 5. \ \Box

Exercise. We mentioned in Example 3 that the center of the symmetric group S_n, \ n \ge 3, is trivial. Prove it!
Hint/Proof. Suppose, to the contrary, that Z(S_n) \ne (1) and choose \text{id} \ne \alpha \in Z(S_n). Since n \ge 3, we can choose three distinct numbers 1 \le i,j,k \le n such that \alpha(i)=j. Let \beta:=(i \ k) \in S_n. Then

\alpha \beta(i)=\alpha(k) \ne \alpha(i)=j=\beta(j) =\beta \alpha(i),

and so \alpha \beta \ne \beta \alpha, contradicting \alpha \in Z(S_n).

In the second part of this post, we define the so-called lower central series of a group and we show how that series is related to central series and nilpotent groups.