Skip to content

Group Theory Is Tough

July 18, 2018

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]


You Cannot Do That

July 11, 2018

How hard is it to prove certain theorems?

Maruti Ram Murty is a famous number theorist at Queen’s University in Kingston, Canada. He is a prolific author of books. His webpage has thumbnails of over a dozen. He has an Erdős number of 1 from two papers—very impressive.

Today Ken and I want to talk about a not-so-recent result of his that is also a “lower bound” type result.
Read more…

Local Hams in La Jolla

July 2, 2018

A workshop on quantum computing at UCSD

Cropped from workshop poster

Dorit Aharonov, David Gosset, and Thomas Vidick did standup for three-and-a-half days in La Jolla earlier this year. They are not listed among the many distinguished actors who have performed at the La Jolla Playhouse on the UCSD campus. Nor were they observed by any of the Hollywood talent-search agencies in town, at least not that we know. But they were applauded by numerous computer science and physics students attending the the March 19–22 UCSD “Spring School on Quantum Computation” which they led.

Today we report on the meeting and discuss an important problem springing from condensed matter physics: the Local Hamiltonian (LH) problem.
Read more…

Muffins and Integers

June 21, 2018

A novel cake-cutting puzzle reveals curiosities about numbers

Alan Frank introduced the “Muffins Problem” nine years ago. Erich Friedman and Veit Elser found some early general results. Now Bill Gasarch along with John Dickerson of the University of Maryland have led a team of undergraduates and high-schoolers (Guangqi Cui, Naveen Durvasula, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo) in writing two new papers that develop a full theory.

Today we discuss the problem and how it plays a new game with integers.
Read more…

Hilbert’s Irreducibility Theorem

June 8, 2018

A pretty neat paper about a pretty neat theorem

[ GLL edited ]

Mark Villarino, William Gasarch, and Kenneth Regan are terrific writers. Bill is a co-author of a famous blog located here. Ken is a co-author of another blog that we will not mention.

Today I would like to talk about one of their recent articles that just appeared in the Math Monthly.
Read more…

Princeton Is Invariant

June 6, 2018

Workshop happening this week—anyone can view it live

IAS Weyl bio source

Hermann Weyl was one of the first members of the Institute for Advanced Study in Princeton. He made important contributions to many fields and even more contributions to groups. His work in group representation theory and polynomial invariant theory is being employed in a workshop being held this week at the Institute on “Optimization, Complexity, and Invariant Theory.” Weyl wrote a lovely book called Levels Of Infinity. One of the interesting chapters is on “Why is the world four-dimensional?” Indeed. Today we discuss some topics from the workshop. The talks are free and readers are invited to follow the remaining proceedings via the live link provided by IAS. Read more…

Almost Fermat Primes

June 1, 2018

A possible source of interesting primes source

Pierre de Fermat was fluent in six languages. Yes I thought we would talk about Fermat today. Something I did not know about him is: he was fluent in French, Latin, Greek, Italian, Spanish, and Occitan. I am impressed since I never could handle another language, though Ken speaks several. Occitan is a relative of Catalan and some of its constituent dialects may be more-familiar names: Langue d’Oc, Provençal, Gascon, and Limousin.

Today Ken and I thought we would discuss something named for Fermat: Fermat primes. A Fermat prime is any prime of the form {2^n + 1}.
Read more…