Some Group Factoids

Groups of Size 2n

Most finite groups are size 2n. For example, over 99% of all groups of size 2000 or less are size 1024.

How to Decompose a Group Into a Direct Product

If H and K are subgroups of G with trivial intersection, HK = G, and all elements of H commute with all elements of K, then G is isomorphic to H × K.

Kernel of Homomorphism Is Normal Subgroup

If φ: G → G’ is a homomorphism, then ker(φ) = φ-1(eG’) is a normal subgroup of G.

A homomorphism is a function from one group G to another group G’ that maintains the group structure: φ(ab) = φ(a)•φ(b). It’s similar to an isomorphism, but is not required to be one-to-one or onto (so multiple elements of G can be mapped to the same element of G’). The kernel of φ is the set of elements in G that are sent by φ to the identity in G’.

Cayley’s Theorem

Every group of size n is a subgroup of Sn, the the set of all permutations of n items. In addition, Sn contains Sm for all m < n.

This means that if you want to all groups of size 2000 or less, you just need to look at the structure of S2000 (which has 2000! elements). In some sense, then, the study of finite groups is just the study of the structure of large permutation groups.

Group Presentation Undecidability

A group presentation looks like S|R, where S is a set of generators for the group, and R is a set of relations among the generators.

For example: a | an = e is the cyclic group of size n (Zn). Another example: r,f | rn = e, f2 = e, fr = rn-1f is the dihedral group of size 2n (the set of symmetries of a regular n-gon).

A finite presentation for a group is just a presentation where S and R are both finite. All finite groups have a finite presentation (easy proof: let S contain all the members of the group, and R be its Cayley table), as do some infinite groups (for example, a | ∅⟩, the group generated by a with no constraints).

Now, you can ask whether there exists an algorithm that takes as input a finite presentation, and figures out whether the group it represents has a certain property (like, is it the trivial group? Is it a finite group? Is it abelian? Is it simple? And so on.) It turns out that for each of these, the answer is no! In addition, the question of if two arbitrary words (e.g. for Dihn, frfrfr and rfrrf) represent the same element is undecidable. So is the question of if two finite presentations represent isomorphic groups.

In general, for pretty much any non-trivial property of a group (a property that isn’t shared by all groups), there is no general algorithm that decides whether a finite presentation has that property!

Advertisements

Leave a Reply