12
$\begingroup$

Say I have 2 groups $G$ and $H$, what techniques can be used to show that they are not isomorphic?

A simple one I can think of is proving that their order is different, thus showing there cannot be a bijection in between the 2. However I am interested in other approaches as well.

$\endgroup$
  • $\begingroup$ Related : math.stackexchange.com/questions/948455/… $\endgroup$ – Arnaud D. Mar 20 '18 at 9:08
  • $\begingroup$ It's hard to answer "in general". "I have 2 groups" is quite vague: groups can be given as subgroups of "known" groups (given as?), can be given as presentations, etc etc. Groups can be nonisomorphic for some obvious reason (e.g., one and not the other has an element of order 2), but this obvious reason is not obvious to check. Also it sometimes comes as an algorithmic question and then you might want find "practical" invariants (efficient to compute). In comparison, to show that a large number is not a square, decomposing it into prime factors is certainly not the most efficient approach. $\endgroup$ – YCor Mar 20 '18 at 19:25
18
$\begingroup$

Look for any difference in the groups such as

  1. Order of the groups.
  2. One group has an element of order $n$, and the other does not have an element of order $n$.
  3. One group has a subgroup of order $n$, and the other does not.
  4. The orders of the centers of the groups are different.
  5. One group is Abelian, the other is not.
  6. One group is cyclic, the other is not.
$\endgroup$
15
$\begingroup$

The Group Isomorphism problem for finitely presentable groups is undecidable. Restricting to finite groups, the problem is certainly decidable, with the trivial algorithm of enumerating all $n!$ permutations (assuming of course, the two groups have the same order).

If the input groups $G, H$ are given by their Cayley tables (which is a generous assumption), we can improve the bound to $n^{O(\log(n))}$ in the following way. First, observe that for a group $G$ of order $n$, there exists a generating set of size $\log_{2}(G)$. To see this, we consider the following algorithm:
-Set $K := \emptyset$.
-While $\langle K \rangle \neq G$, select $g \in G \setminus \langle K \rangle$, and add $g$ to $K$.

Each new element we add to $K$ at least doubles the size of $\langle K \rangle$. So $|K| = \log_{2}(n)$.

As $\langle K \rangle = G$, we seek to map the elements of $K$ into a generating set of $H$. There are $|H|^{|K|} = n^{\log(n)}$ such functions. Accounting for some overhead in testing such functions, we achieve the $n^{O(\log(n))}$ bound. This bound has been relatively unscathed, though several classes of groups have polynomial time algorithms for the isomorphism problem. Some of these classes include abelian groups (https://www.sciencedirect.com/science/article/pii/S0022000007000293), groups without abelian normal subgroups (https://link.springer.com/chapter/10.1007%2F978-3-642-31594-7_5), and groups with abelian Sylow towers (http://drops.dagstuhl.de/opus/volltexte/2012/3400/).

$\endgroup$
  • 6
    $\begingroup$ +1 While this is almost certainly not what the OP wanted, I think mathematicians have a tendency to lose sight of what is actually doable. I also think that many students don't realize that often when mathematicians talk about having "solved" some problem or "computing" some mathematical object, they have a rather different thing in mind than a layperson or a computer scientist would. $\endgroup$ – Derek Elkins Mar 20 '18 at 5:42
10
$\begingroup$

General strategy: find some invariant that is different for one group than the other. You might look at the number of elements of each order, the orders of the upper and lower central series, etc.

$\endgroup$
5
$\begingroup$

One common way is to establish that one group has an element of some order that the other group does not.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .