On Tue, 23 Sep 2003, Richard Schroeppel wrote:

Can two non-isomorphic groups always be distinguished by some extrinsic property?

In my view, this is an odd use of "extrinsic" - I'd actually describe most of the properties you give below as "intrinsic"!

For any group, we can find a number of derived objects: The order, the collection of element orders, the center, the commutator subgroup, the diagonal subgroup (generated by squares), &c. This process can be carried quite a ways, defining some pretty fancy concepts. Bill Henneman once explained the Frattini subgroup to me as "the set of useless generators". If you write out a notion like this in primitives, you are soon knee- deep in quantifiers.

My question can be restated as: If two groups have enough of these concepts matching, are they isomorphic? Can the matchings be used to compute an isomorphism?

There might actually be a true statement of this type, but in the present state of knowledge there's no provable one.

For finite groups, I can check isomorphism in time roughly N^(log2(N)). The extrinsic properties might give a faster check.

I shouldn't waste time hoping! It seems that p-groups give the toughest examples. This is because for them most of your invariants will be distinctly smaller p-groups, and the number of groups of order p^n grows quite rapidly with n, so you're quite likely to get repetitions. To illustrate the way this happens, let's take the groups of order 16 and the invariant "center". The center of a non-abelian group is always "at least two primes down", making it have order at most 4 (and at least 2, since it's non-trivial) in the order 16 case. This gives only 3 centers for 9 groups. Of course you can compensate by taking more invariants, but they tend to be highly dependent, and even when things seem likely to be true, you can't prove them, dammit.

Similar questions exist for graphs & other math objects.

...where, as you know, they seem equally intractable. John Conway