[math-fun] distinguishing groups
RCS> For finite groups, I can check isomorphism in time roughly N^(log2(N)). MLB> How's that? If you're given the groups in some reasonable form how can it take more than the N^2 required to completely compare them element-wise? Perhaps this time includes making the inputs presentable? I should speak more precisely: Given two finite groups, I can decide if they are isomorphic in time roughly N^(log2(N)). Actually, N^(2+log2(N)). The hard part is finding the isomorphism. Checking a candidate isomorphism is, indeed, O(N^2), maybe less. I'm assuming the groups are given as lists of the elements, perhaps named G0, G1, ... and H0, H1, ..., and that there are black boxes G*, G/, H*, and H/ that provide products and reciprocals in time 1. I'm also assuming that the objects are indeed groups, although that could be checked in O(N^3) (or maybe less?). To search for the isomorphism I, you begin by developing a list of generators for G. First, scan the elements of G to locate the identity Gi so you can ignore it. We maintain of list of elements of G that we've already generated, and their formulas. This list starts with {Gi}. Then build a list of generators one at a time. Take the first element of G that isn't in the already-generated list, and call it a new generator. Expand the generated list with the new generator, closing under G*. (Don't need to bother with G/, it's a finite group.) Each new generator at least doubles the size of the generated set, so the total number of generators is <= log2(N). In the case of the group (Z2)^K, the formula is exact. Now that we have a list Ga,Gb,... of generators for G, we start searching for an isomorphism with H. We guess I(Ga) = Hx, and calculate the portion of I generated by Ga->Hx. For those that are consistent, we continue with a guess for Gb->Hy, and so on. I guess this comes out to N ^ (2 + log2(N)) if we include the time to check each candidate I. If we were actually making a list of all automorphisms of (Z2)^K, it's nearly N^(log2(N)). The separate puzzles, How much work to check a group given as a table is really a group? and How much work to check an isomorphism given as a table between two known-to-be groups given as tables? are also interesting. Obvious upper bounds are N^3 and N^2, but maybe we can do better. Rich rcs@cs.arizona.edu
Rich (et al), Thanks for the lucid clarification (& lurid classification?<;-) of the hard "non-canonical group isomorphism" problem vs. related other ones! I do seem to have glommed onto a somewhat different question, which appears fun in its own right:
Checking a candidate isomorphism is, indeed, O(N^2), maybe less... How much work to check an isomorphism given as a table between two known-to-be groups given as tables [is] also interesting.
This is what got me curious: exactly how much less? For some reason I'd blithely assumed that the two groups were given in a canonical form (eg maybe they got generated that way?) and that the cost was being measured at the granularity of element operations, rather than whole-group black boxes (indeed, if G/ is just O(1) then G==H ought to be pretty trivial!) In case someone else finds this interesting, let me try to restate it clearly: Given *canonically represented* groups (eg as lexicographically-least tables?): 1. How fast can one be uniquely identified? 2. How fast can two be compared for equality? (where costs are measured in element operations). While not as hard as the non-canonical problem, just comparing canonical representations the size of the Monster, say, isn't exactly trivial. And even for small N, rapidly identifying, for example, which one of those fourteen order-16 groups we were discussing sounds handy. Moreover, using fancy "global" properties, such as Rich originally cited, might very well be less effective than something based on "local" element hacking. Consider string comparison, where you can return false after comparing the first elements, and returning true requires comparing all of the elements. Contrast this with comparing canonical group representations, where you can certainly ignore the 1 row/column, and you probably don't need to compare anywhere near N^2 elements. For example, you can distinguish A4 and Z4 just by comparing the canonical 2,2 element. What strategy will most efficiently distinguish any canonical pair of order N? What procedure will most efficiently identify any canonical GN? Etc.
On Wed, 24 Sep 2003, Marc LeBrun wrote:
While not as hard as the non-canonical problem, just comparing canonical representations the size of the Monster, say, isn't exactly trivial. And even for small N, rapidly identifying, for example, which one of those fourteen order-16 groups we were discussing sounds handy.
In fact, as a practical problem, if you had a putative Monster (say) given as a set of generator names and a black-box multiplier, it's not at all hard to say whether it is or isn't the Monster. We used to do such things routinely when I was in Cambridge (we never actually did the Monster that way, but only because we didn't have the black-box multiplier, which has since become available). My feeling is that the methods we used could be converted into a formal proof that one could distinguish between any two given candidate groups of orders < N in a time bounded by some power of log N. [Note that that's weaker than saying "find which group of order < N you have".] John Conway
participants (3)
-
John Conway -
Marc LeBrun -
Richard Schroeppel