In general, what techniques can be used to show that 2 groups are not isomorphic?

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.

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/).


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.


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