Group Theory Is Tough

Gödel’s Lost Letter and P=NP 2018-08-02

Some musings on group theory

Isaacs honorary conference source

Martin Isaacs is a group theorist emeritus from the University of Wisconsin, Madison. I just picked up a copy of his 2008 book, Finite Group Theory. Simple title; great book.

Today I want to make a few short comments about group theory.

I always hated group theory. Well not really hated it. But I have never been able to get decent intuition about groups.

Ken has a similar issue and puts it this way: We are “spoiled” by first learning about fields and rings with ${\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}}$ as all-pervading examples, then ${\mathbb{Z}_p}$ and ${\mathbb{Z}_m}$ for prime ${p}$ and non-prime ${m}$ . Each includes an additive group and (for the fields) a multiplicative group but is so much more. They combine to form other spaces such as ${\mathbb{R}^n}$ and ${\mathbb{Z}[x_1,\dots, x_n]}$ .

Groups alone seem neither to command such sway as individual mathematical objects nor to combine so prolifically. The group-based analogue of a vector space is called a module and feels like a similar “hole” in our intuition.

Ken remembers Martin, Marty, well having known him during Marty’s visit to Oxford in 1984. Marty was often found in the lobby or the tea room of the old Mathematical Institute animatedly talking about open problems and ideas for teaching. His “group” included Graham Higman, Peter Neumann, Hilary Priestley, Robin Gandy, and anyone who happened to stop by. Ken remembers geniality, openness, and great ways of putting things.

Groups and Complexity

Of course group theory is important in many parts of complexity theory. Here are two important examples of group theory open questions:

How hard is group isomorphism?
Are solvable groups as powerful as simple groups?

The latter is of course asking if a solvable group can be used like a non-abelian simple group in computing via bounded width programs. We have discussed both of these questions before: check out this and this.

I definitely would suggest you look at Issacs’s book if you are at all interested in getting some insight into group theory. I have been looking at it and now feel that I have intuition about groups. Not much. But some. The issue is all mine, since the book is so well written.

A Remark

Issacs makes a cool remark in his book on group theory. Suppose that ${G}$ is a group with a non-trivial normal subgroup ${N}$ . Then often we can conclude that at least one of ${N}$ or ${G/N}$ is solvable. This can be done in the case that the orders of ${N}$ and ${G/N}$ are co-prime. The proof of this is quite amusing: it depends on two theorems:

Theorem 1 If ${x}$ and ${y}$ are co-prime numbers, then at least one of ${x}$ and ${y}$ is odd.

Theorem 2 Every group of odd order is solvable.

One of these is very trivial and the other is very non-trivial. I trust you know which is which.

Another Remark

Group theory uses second order reasoning, even for elementary results, quite often. This sets it apart from other parts of mathematics. A typical group theory result is often proved by the following paradigm:

Let ${H}$ be a subgroup of ${G}$ that is largest with regard to some property ${X}$ . Then show that ${H}$ dose not exist. or that ${H}$ must also have some other property ${Y}$ .

When we are talking about finite groups then of course there are only finitely many subgroups and so the notion of “largest” involves nothing subtle. Moreover, one can transfer all this into first-order sentences about their string encodings. But the theory is really naturally second-order. For infinite groups the notion of maximal can be really tricky. For example, the group of all ${2^n}$ complex roots of unity over ${n = 1,2,3,4,\dots}$ has no maximal subgroups at all.

Open Problems

Should we teach groups and modules in a richer fashion? Is it really hard to get intuition in group theory? Or is that just an example of why mathematics is hard?

[fixed name in line 1; fixed to “N and G/N” in section 3]