FINDING FINITE GROUPS

Developed by the Association for Conceptual Studies

Presented by F Richard Singer III http://www.conceptualstudy.org

Edition Date 1/2009

Overview: This is an individualized constructivist learning resource. It is designed to help a learner bridge the gap between group concepts that seem manifest and those that seem remote. It is intended primarily for a learner who finds the prerequisites below fairly manifest but feels that cosets and LaGrange’s Theorem are somewhat remote. For a discussion of what is meant by an individualized constructivist learning resource and other aspects of concept construction, see the paper Constructivist Learning Resources.

Prerequisites:

¨ how the defining laws for a group are those common to addition, multiplication, composition

¨ how these are the laws provide the tools need to solve simple equations

¨ how the defining laws imply the cancellation laws, and why this means each element of a group occurs exactly once in each row and exactly once in each column of its table

¨ how to organize the group tables to show an isomorphism

¨ the distinction between abelian and non-abelian groups and some of the basic laws which depend on commutivity, such as (xy)² = x²y²

¨ specific examples of finite groups, such as cyclic groups, dihedral groups, groups of units in Z_n, direct products of these groups.

¨ the concept of order; that the order of x is n implies that {1,x,…,x^n-1} are distinct and form a subgroup.

Remark: This resource does not assume that you know any of the main theorems about groups, however you are encouraged make conjectures. You may use any these as an intuitive guide to solving the Exercises, but unless you prove a conjecture, you cannot use it in validating your solution.

Background Work: Write tables for some groups you know, including at least 3 from each of the types mentioned in the prerequisites. Give order of each element in the group. Specify a set of generators and generator relations for each group.

Notation: We use multiplicative notation for groups, with 1 for the identity, /x for the inverse of x, exponents for repeated multiplication. The direct product of groups G₁ and G₂ is denoted as G₁ÄG₂. C_n denotes the cyclic group of order n. D_n denotes the dihedral group of order 2n. U_n denotes the group of units from Z_n. G denotes a group. ôG denotes the number of elements in G. Letters a, b, c, d denote different specific elements of G other than 1. General group laws use letters at the end of the alphabet as variables for the group. ôx denotes the order of the element x. ĝ{x} denotes {1,x,…,x^ôx-1} and is called the subgroup generated by x.

Note that ôĝ{x} = ôx.

Cancellation: Many useful results follow the cancellation and identity laws, such as y ¹ 1 Þ y² ¹ y. This can be proved as follows.

Assume y² = y. Then by the definition of exponents and the identity law, we have y·y = 1·y. Cancellation gives y = 1, so y² = y Þ y = 1. This is logically equivalent to y ¹ 1 Þ y² ¹ y.

Any such results will be referenced as cancel. Some examples of cancel that will be useful in this resource are those listed below.

y ¹ 1 Þ yx ¹ x & xy ¹ x y ¹ x Þ yx ¹ x² & xy ¹ x² y ¹ x² Þ yx ¹ x³ & xy ¹ x³

In general, if y is not a power of x then neither is yx nor xy

Instructions: This resource consists of the exercise below in which you are to find all finite groups G that satisfy certain conditions. Some of these conditions are stated in terms of specific group elements, usually denoted as c or b. However G may also have additional element not mentioned in these conditions. These conditions may determine exactly one group or several groups. If there is one or more answers for G then show that your solution contains all such answers. In some cases there is no group that satisfies the conditions. If there is no such group then show that these conditions result in a contradiction. This is demonstrated by providing solutions to the exercise 1 thru 5. Compare your solutions to these Exercises with ours. Also read our comment.

1: ôG = 1. 2: ôG = 2 3: ôG = 3. 4a: ôG = 4, ôc = 3. 4b: ôG = 4.

5a: ôG = 5, ôc = 4. 5b: ôG = 5, ôc = 3. 5c: ôG = 5, ôc = 2. 5d: ôG = 5.

6a: ôG = 6, ôc = 4. 6b: ôG = 6, ôc > 4 6c: ôG = 6, ôc = 3, ôb = 2, cb = bc.

6d: ôG = 6, G is abelian. 6e: ôG = 6, ôc = 3, xÏ{1, c, c²} Þ x² = 1.

6f: ôG = 6, G is not abelian. 6g: ôG = 6.

7a ôG = 7, ôc > 3. 7b: ôG = 7, ôc = 3. 7c: ôG = 7, "x(ôx < 3). 7d: ôG = 7, G is abelian.

7e: ôG = 7, G is not abelian. 7f: ôG = 7.

8a: ôG = 8, ôc > 4. 8b: ôG = 8, ôc = 3. 8c: ôG = 8, "_x(ôx < 4).

8d: ôG = 8, ôc = 4, "x(ôx < 8), G is abelian.

8e: ôG = 8, ôc = 4, ôb = 2, bÏĝ{c}, G is not abelian.

8f: ôG = 8, ôc = 4, bÏĝ{c} Þ ôb = 4, G is not abelian. 8g: ôG = 8.

9a: ôG = 9, G abelian. 9b: ôG = 9, G not abelian. 9c: ôG = 9

10: ôG = 10. 11: ôG = 11.

12a: ôG = 12, G is abelian. 12b: ôG = 12, G is not abelian (this is the most challenging exercise).

13: ôG = 13. 14: ôG = 14. 15: ôG = 15.

Suggestion: Since there are 14 groups of order 16, I terminated these exercises at order 15.
However there is only one group of order 17. You might want to find some groups whose orders
are larger than 15. You might also want to make some conjectures.

Cosets: Suppose H is any subgroup of G. The left coset of H determined by x is the set obtained by taking xh for each h in H. Right cosets are defined in a similar manner. Since multiplication of H by 1 gives H, H is both a left and a right coset of itself. Furthermore, if xÎH, xH = H & Hx = H. In an abelian groups the left coset xH and the right coset Hx are identical. This is not always the case in a non-abelian group. For some subgroups H we may have xH = Hx. For other we may have xH ¹ Hx. To go further in finding groups (or in any other study of groups), you should make sure you understand the concept of a coset and how the cosets of a group form a partition seems manifest. To focus on cosets, you might want to draw some partial tables like the ones below for a group G with ôG = 6 & ôc = 3 & ôb = 2. G must

have the subgroup ĝ{c} = {1,c,c^2} of order 3 indicated by the white row and column labels. That this is a subgroup can be seen by observing the 3´3 white square inside the table. The element b, forces G to have 3 elements in the left coset bĝ{c} = {b,bc,bc^2}, indicated by the blue row labels. This partitions G partition G into 2 sets of size 3, G = ĝ{c}Èbĝ{c}. G must also have the left coset ĝ{c}b with the elements indicated by the green column labels. Since ôG = 6, the right and left coset must be the same. So cb = bc or cb = bc^2. Either of these determines the table, using names from either coset. This gives two groups of order 6.	·	1	c	c^2	b	cb	c^2b
	1	1	c	c^2	b	cb	c^2b
	c	c	c^2	1	cb	c^2b	b
	c^2	c^2	1	c	c^2b	b	cb
	b	b	bc	bc^2
	bc	bc	bc^2	b
	bc^2	bc^2	b	bc

Altho G has 6 elements we can use to form cosets of ĝ{c}, we only obtain the 2 left cosets above. This is because each of the 3 elements in ĝ{c} determines coset which is ĝ{c}. t, i.e.1ĝ{c} = cĝ{c} = c²ĝ{c}. This can be seen by observing the white square. Likewise each of {b,bc,bc²} determines the same coset, namely bĝc. This can be seen by observing the blue square. A similar remark applies to right coset.

To see that left and right coset may differ, focus on the cosets of {1,b}. G has a subgroup ĝ{b} = {1,b}, indicated by observing the upper 2 by 2 white square. Given another element b, forces G to have at least 2 more elements in the left coset {c,cb} indicated by the blue row labels. Since ôc = 3, we must use c^2 to form the pink left coset. This partition G into 3 sets of size 2, G = ĝ{b}Ècĝ{b}Èc^2ĝ{b}. We can also use the right cosets, indicated in green and yellow, to partition G as G = ĝ{b}Èĝ{b}cÈc^2ĝ{b}c. If cb ¹ bc this is a different is a different partition, but it is still a partition into 3 disjoint sets of size 2.	·	1	b	c	bc	c^2	bc^2
	1	1	b	c	bc	c^2	bc^2
	b	b	1	bc	c	bc^2	C^2
	c	c	cb
	cb	cb	c
	c^2	c^2	c^2b
	c^2b	c^2b	c^2

Solutions

1: G = C₁, where 1·1 = 1. 2: G = {1, c}. By Cancel, c² ¹ c, so c² = 1. Thus G is C_2.

3: Let G = {1, c, b}, where these are distinct. By closure, bcÎG. Since b ¹ 1, bc ¹ c. Likewise bc ¹ b. Thus bc = 1. Since bc = 1 and c^2 ¹ bc, we have c^2 ¹ 1. Since c^2 ¹ c, we must have c^2 = b. Thus G = {1, c, c^2}. By cancellation c^3Ï{c, c^2}, so c^3 = 1. Thus G is C3.	·	1	c	c^2
	1	1	c	c^2
	c	c	c^2	1
	c^2	c^2	1	c

4a: Since ôc = 3; 1, c, c² are distinct elements of G, and any other power of c is one of these. Call the other element b. By cancel bcÏ{1, c, c²} and bc ¹ b. This eliminates all possible values for bc, and hence there is no such group.

This analysis can also be given by trying to complete this partial table below. The entry for bc must be in {1, c, c^2, b}. The column for bc contains 1, c, c^2. The row for bc contains b. Thus any answer for bc contradicts cancel. Hence there is no such group G.	·	1	c	c^2	b
	1	1	c	c^2	b
	c	c	c^2	1
	c^2	c^2	1	c
	b	b	?

4b: By Exercise 4a, G does not contain an element of order 3. So it either contains an element of order 4 or every element except 1 has order 2.

In the first case G is C₄. = {1, c, c², c³}

In the other case let G = {1, c, b, a}, where c² = 1, b² = 1, a² = 1. This gives a partial table for G.

·

1

c

b

a

By cancel a is the only possible entry for bc and for cb.

·

1

c

b

a

There is only one way to complete this table

·

1

c

b

a

1

1

c

b

a

1

1

c

b

a

1

1

c

b

a

c

c

1

?

?

c

c

1

a

?

c

c

1

a

b

b

b

?

1

?

b

b

a

1

?

b

b

a

1

c

a

a

?

?

1

bc

a

?

?

1

a

a

b

c

1

Since bc = a, we can use bc as the name for a, and hence. this group is C₂ÅC₂. This group is also isomorphic to both D₂ and U₈.

C₂ÅC₂ D₂ U₈

·	1	c	b	bc	·	1	t	f	ft	·	1	3	5	7
1	1	c	b	bc	1	1	t	f	ft	1	1	3	5	7
c	c	1	bc	b	t	t	1	ft	f	3	3	1	7	5
b	b	bc	1	c	f	f	ft	1	t	5	5	7	1	3
bc	bc	b	c	1	ft	ft	f	t	1	7	7	5	3	1

Comment: In solving Exercise 3 we first named the elements as 1, c, b. When we saw that b = c², we decided it was better to name them as 1, c, c². Note, that we did this automatically in Exercise 4 in the case where ôG = 4. In the other part of the exercise we named the element 1, c, b, a. Later when we saw that a = bc, we named them as 1, c, b, bc. Had we observed that bc must be different from 1 and c and b, it would have made the exercise easier to solve by using this naming system from the start. In general, it is a good idea to find as few basic elements as possible, and use these help name other group elements. A set of elements which can be used to name all the rest of the elements in a group is called a set of generators for the group. Care must be taken in using this method. If c and b are in your group then so are bc and cb; however these may or may not be two distinct elements.

5a: Since ôc = 4; G = {1, c, c^2, c^3, b}. By cancel, cb cannot be a power of c, nor can it be b. Thus there is no such group. This analysis can also be given by trying to complete the partial table to he right.	·	1	c	c^2	c^3	b	ß no available entry for cb
	1	1	c	c^2	c^3	b
	c	c	c^2	c^3	1
	c^2	c^2	c^3	1	c
	c^3	c^3	1	c	c^2
	b	b

5b: Suppose ôc = 3. Let 1, c, c^2 be 3 distinct elements of G. Call one of the other elements b. By cancel, bc cannot be any of these 4 elements, so it must be the remaining one. This gives a partial table. However there is no available entry for b·c^2	·	1	c	c^2	b	bc
	1	1	c	c^2	b	bc
	c	c	c^2	1	bc
	c^2	c^2	1	c
	b	b	bc	?
	bc	bc

Comment: Suppose ôG > ôx > n for some x.. Let yÏ{1, x, x², ..., x^n-1}. Cancel shows that 1, x, ..., x^n-1, y, xy, ..., x^n-1y are all distinct. This shows that you ôG ³ 2n. Thus a group cannot have an element x whose order is more than half its order unless x generates the whole group.

5c: Let b be another element of G. By cancel, bcÎ{1, c, b}, giving bc as another element of G. Call the remaining element a, so G = {1, c, b, bc, a} Using c^2 gives bc·c = b, so we know the first four entries in the column under c in a partial table for G. There is no way to complete the table.	·	1	c	b	bc	a
	1	1	c	b	bc	a
	c	c	1
	b	b	bc
	bc	bc	b
	a	a

5d: Combining Exercises 5a 5b 5c gives C₅ as the only solution.