The Group Isomorphism Problem: A Possible Polymath Problem?
Can we beat the “trivial” bound on group isomorphism?
William Burnside was one of the founders of modern group theory. His classic book, Theory of Groups of Finite Order, helped lay the foundations. He proved some beautiful theorems, made some great conjectures, and in general helped start the modern era of group theory.
Today Ken and I want to talk some more about group isomorphism.
There was great interest in a possible attack on this problem. Perhaps it is a candidate for a Polymath Project. In any event looking at a precise conjecture is one of the best ways to make progress in any area of theory or mathematics.
Burnside did exactly this for group theory. He stated one of the most important conjectures in group theory, which was named after him. Suppose that is a group that is generated by a finite number of elements. if there is an element such that is infinite, then obviously the group is infinite. But if all elements, not just the generators, of the group have a finite order, must the group be finite? Burnside conjectured yes.
Burnside’s Problem Specialized
Burnside found a neat way to develop his conjecture that also identified important special cases. The exponent of a group is the least common multiple of the orders of its elements, if it exists. If is finite then by Lagrange’s Theorem its exponent divides .
We can make an infinite group of exponent 2 by taking and adding these infinite binary vectors componentwise mod~2. Every vector added to itself produces the identity, the all-zero vector. However, the group has no finite generating set because the sums of -many vectors can produce at most elements. This is true of exponent-2 groups in general: they are Abelian because
for all elements . Hence at most distinct “words” can be made from generators.
The case of exponent 3 is trickier, as not every such group is Abelian. Burnside himself resolved it in the positive: if a group of exponent 3 is finitely generated, then it is finite. Burnside was emboldened to put forth his conjecture:
For all and , if is a group with generators that has finite exponent , then is finite.
This is technically weaker than the general first statement we gave, because the latter could (and did) fail by having a finitely generated group with all elements of finite order but an infinite exponent. However, Burnside himself made his special conjecture even more concrete by defining a single group such that the conjecture holds for if and only if is finite. See here for a definition of , which is analogous to a complexity class having a complete set.
Disproved and Still Kicking
Just before World War II the conjecture was proved for and all by Ivan Nikolaevich Sanov. Then Marshall Hall, Jr., proved it for and all in what was termed a “heroic calculation.” Ken served as Marshall’s official host at Merton College, Oxford, for much of 1986, even putting him up when the Fellows’ Guestrooms weren’t available. Hall co-wrote a paper making progress on in 1981, but Ken recalls only that he and Marshall talked about combinatorial designs.
However, Burnside’s original conjecture was refuted in 1964 by Evgeny Golod and Igor Shafarevich, who built an infinite group with three generators whose elements have finite orders that are unbounded powers of , where can be any given prime. Then in 1968, Pyotr Novikov and Sergei Adian refuted Burnside’s particular conjecture for all and all sufficiently large odd , originally . Later this was extended to all odd , and others gave negative answers for many even . The problem is extremely tricky, even strong group theorists have slipped: I discussed this quite a while ago here—where I talked about John Britton’s long, complex, but unfortunately incorrect proof.
The problem is still kicking, however, because of Burnside’s concrete development of it. Cases for smaller and various are still open, including . Even when is infinite, one can still pose the restricted Burnisde problem: is there a finite bound on the orders of -generator groups of exponent that are finite? Efim Zelmanov won a Fields Medal in 1994 largely for showing that in a sweeping range of cases the answer is yes.
We wish to propound a problem that has some similar ingredients and special cases. Analyzing these cases may require some “heroic calculation,” but that may be structurable in a way that is good for a Polymath project.
The Group-Isomorphism Problem, Again
Recall that a group can be presented by giving the Cayley table: if a group has elements this table is in size. The table just encodes the product function “” in the obvious way: the entry is the value of .
The problem is given two groups and , are they really the same—that is can we relabel the elements so the tables are identical? This is asking whether the groups are isomorphic, to use a more technical terminology. The current best bound, as discussed before, is that this can be done in
time by a deterministic algorithm. This method relies on the fact that any group of size has a generator set of size at most . This is a quasi-polynomial time.
A -group is a group in which every element has order for some , where is a prime. For a finite group the order of the group must likewise be a power of . Recall that the counterexamples by Golod and Shafarevich are infinite -groups. Finite -groups have many special properties that seem to make them candidates for an attack; they also have many properties that make them look impervious to attack. For more on them, start here.
Let’s denote the number of groups, up to isomorphism, of order by . This function is quite nasty, since it varies widely with the multiplicative structure of . If is a prime, then , since only the cyclic group is possible. If has many factors, then can be very large.
Related to this function is the folklore conjecture asserting that almost all finite groups are 2-groups: the fraction of isomorphism classes of 2-groups among isomorphism classes of groups of order at most is thought to tend to as tends to infinity. This leads us to ask:
Can we solve the Group Isomorphism Problem specialized to -groups in polynomial time? Or at least improve the above quasi-polynomial time?
Good News and Bad News
Several features of -groups provide structure to get a handle on, but other features forbode that calculations may have to be longwinded.
The good news: The family of -groups always have a non-trivial center. Recall the center of a group is the subgroup of elements that commute with all the other elements. In general this subgroup, , can be trivial, that is consist of just the identity element. But -groups have the wonderful property that the center is always nontrivial.
Here is a simple application of this principle. Any group of order for a prime is abelian. Let the group be , and let be the non-trivial center. We can assume that is order , else it is all of and then is abelian. Let be an element of . The group generated by and is larger than , so by Lagrange’s Theorem it has order , and thus is equal to . But also this group is abelian. This follows since commutes with all of —recall that is the center.
The bad news: They can have large generators, as large as , where . Even if the number of generators is close to the trivial isomorphism algorithm will still be supe- polynomial.
There is also the Burnside structure theorem on the generators of such a group: his theorem works for any -group. One of the cool properties is that all generator sets of such groups have the same cardinality, which is false in general for groups. For many mathematical structures the size of a minimal generator set is always the same: -dimensional vector spaces are the standard example. But for general groups, minimal generator sets can be vastly different in size. Even the symmetric group has this property—it can be generated by two elements or by many more elements. Note, we are always talking about generator sets that are minimal, meaning that removal of any single element will destroy the generator property.
A Special-Case Problem
George Pólya had a principle for working on problems: when working on a hard problem, try to find a special case that captures its essence. I suggest that the best case to look at is the class of -groups. One clear reason is that they are the worst case for the trivial time bound, since they could have as many as generators. Note that if all elements in such a group have order 2, then the group is abelian. And since isomorphism is easy for abelian groups, this is a good case.
I think what we need is another strategy besides the generator approach. Let be a 2-group. If it has a very large abelian subgroup, then it should be easy to handle. If on the other hand, it has only a small abelian subgroup, then can we show that it has some special structure that we can exploit?
Should we organize a Polymath Project? Ken and I think that we would help with one, but that we probably need at least one strong group theorist to help run such a project. Any takers?