0
$\begingroup$

Let A and B be two sets of tables (from multiplication tables of a group, 24 by 24 as rows by columns), how can we effectively (and possibly also efficiently) find a way to map between them, if two groups are indeed isomorphism, under the relabelling of group elements?

Based on the strategy given in this post

A={{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
  20, 21, 22, 23, 24}, {2, 1, 4, 3, 6, 5, 8, 7, 12, 11, 10, 9, 14, 13,
   16, 15, 18, 17, 20, 19, 22, 21, 24, 23}, {3, 4, 1, 2, 7, 8, 5, 6, 
  10, 9, 12, 11, 16, 15, 14, 13, 20, 19, 18, 17, 24, 23, 22, 21}, {4, 
  3, 2, 1, 8, 7, 6, 5, 11, 12, 9, 10, 15, 16, 13, 14, 19, 20, 17, 18, 
  23, 24, 21, 22}, {5, 7, 6, 8, 1, 3, 2, 4, 18, 17, 20, 19, 24, 21, 
  22, 23, 10, 9, 12, 11, 14, 15, 16, 13}, {6, 8, 5, 7, 2, 4, 1, 3, 17,
   18, 19, 20, 23, 22, 21, 24, 11, 12, 9, 10, 13, 16, 15, 14}, {7, 5, 
  8, 6, 3, 1, 4, 2, 19, 20, 17, 18, 21, 24, 23, 22, 9, 10, 11, 12, 15,
   14, 13, 16}, {8, 6, 7, 5, 4, 2, 3, 1, 20, 19, 18, 17, 22, 23, 24, 
  21, 12, 11, 10, 9, 16, 13, 14, 15}, {9, 12, 11, 10, 23, 24, 21, 22, 
  1, 4, 3, 2, 20, 19, 17, 18, 15, 16, 14, 13, 7, 8, 5, 6}, {10, 11, 
  12, 9, 22, 21, 24, 23, 3, 2, 1, 4, 17, 18, 20, 19, 14, 13, 15, 16, 
  5, 6, 7, 8}, {11, 10, 9, 12, 21, 22, 23, 24, 4, 1, 2, 3, 18, 17, 19,
   20, 13, 14, 16, 15, 6, 5, 8, 7}, {12, 9, 10, 11, 24, 23, 22, 21, 2,
   3, 4, 1, 19, 20, 18, 17, 16, 15, 13, 14, 8, 7, 6, 5}, {13, 15, 16, 
  14, 19, 17, 18, 20, 22, 23, 21, 24, 1, 4, 2, 3, 6, 7, 5, 8, 11, 9, 
  10, 12}, {14, 16, 15, 13, 20, 18, 17, 19, 21, 24, 22, 23, 2, 3, 1, 
  4, 5, 8, 6, 7, 10, 12, 11, 9}, {15, 13, 14, 16, 17, 19, 20, 18, 24, 
  21, 23, 22, 4, 1, 3, 2, 7, 6, 8, 5, 9, 11, 12, 10}, {16, 14, 13, 15,
   18, 20, 19, 17, 23, 22, 24, 21, 3, 2, 4, 1, 8, 5, 7, 6, 12, 10, 9, 
  11}, {17, 20, 19, 18, 15, 14, 13, 16, 6, 7, 5, 8, 10, 9, 11, 12, 21,
   24, 22, 23, 1, 3, 2, 4}, {18, 19, 20, 17, 16, 13, 14, 15, 5, 8, 6, 
  7, 11, 12, 10, 9, 22, 23, 21, 24, 2, 4, 1, 3}, {19, 18, 17, 20, 13, 
  16, 15, 14, 7, 6, 8, 5, 12, 11, 9, 10, 23, 22, 24, 21, 4, 2, 3, 
  1}, {20, 17, 18, 19, 14, 15, 16, 13, 8, 5, 7, 6, 9, 10, 12, 11, 24, 
  21, 23, 22, 3, 1, 4, 2}, {21, 23, 22, 24, 11, 9, 10, 12, 14, 13, 15,
   16, 7, 6, 5, 8, 1, 4, 3, 2, 17, 19, 20, 18}, {22, 24, 21, 23, 10, 
  12, 11, 9, 13, 14, 16, 15, 8, 5, 6, 7, 2, 3, 4, 1, 18, 20, 19, 
  17}, {23, 21, 24, 22, 9, 11, 12, 10, 16, 15, 13, 14, 6, 7, 8, 5, 4, 
  1, 2, 3, 19, 17, 18, 20}, {24, 22, 23, 21, 12, 10, 9, 11, 15, 16, 
  14, 13, 5, 8, 7, 6, 3, 2, 1, 4, 20, 18, 17, 19}};
B = FiniteGroupData[{"SymmetricGroup", 4}, "MultiplicationTable"];
n = Length@A;
perms = Permutations[Range@n];
FlB = Flatten[B];
subst[list_] := Table[A[[list[[i]], list[[j]]]], {i, n}, {j, n}]
lnght[A$_] := Length@Union@Transpose@{Flatten[A$], FlB}
Min[lnght[subst[#]] & /@ perms]

There is a limitation of the Permutations[Range[24]], perhaps the system size is too large? This results in an output: enter image description here

question 1. Can we still find a way out to do Permutations[Range[24]]? Or is there a more efficient way to find the group isomorphism?

question 2. How do we suggest a map between the two tables, say from {1 to 1}, {2 to ...}, {3 to ...}? If the map can be found?

Note: This will be the table look like in Grid: enter image description here

$\endgroup$
  • $\begingroup$ p.s. There is so far not yet a complete answer. $\endgroup$ – wonderich Apr 13 '18 at 3:43
4
$\begingroup$

For a start, the order of an element is invariant under group isomorphisms. This boils the number of permutations to test from $24! = 620448401733239439360000$ down to $6! \, 8! \, 9! = 10534551552000$. The order of the $i$th element can actually determined from row A[[i]] alone. The following function getGroupElementOrder does that for you:

getGroupElementOrders = Compile[{{a, _Integer, 1}, {g, _Integer}},
   Block[{i = g, c = 1},
    While[i != 1, c++; i = Compile`GetElement[a, i]];
    c
    ],
   RuntimeAttributes -> {Listable},
   Parallelization -> True
   ];

n = Length[A];
ordersA = getGroupElementOrders[A, Range[n]];
ordersB = getGroupElementOrders[B, Range[n]];
elementsInAOfOrder = GroupBy[Transpose[{ordersA, Range[n]}], First -> Last]
elementsInBOfOrder = GroupBy[Transpose[{ordersB, Range[n]}], First -> Last]

<|1 -> {1}, 2 -> {2, 3, 4, 5, 8, 9, 12, 13, 16}, 4 -> {6, 7, 10, 11, 14, 15}, 3 -> {17, 18, 19, 20, 21, 22, 23, 24}|>

<|1 -> {1}, 2 -> {2, 3, 6, 7, 8, 15, 17, 22, 24}, 3 -> {4, 5, 9, 12, 13, 16, 20, 21}, 4 -> {10, 11, 14, 18, 19, 23}|>

No, you are "only" left to match members of elementsInAOfOrder[k] with elementsInBOfOrder[k] for $k = 2,3,4$ ...

$\endgroup$
  • $\begingroup$ @ Henrik Schumacher, thanks, +1, indeed I was thinking about the diagonal, too. However, there are still many choices, how can we pin down precisely to a single mapping? [there is at least a single mapping if it exists, and one can find perhaps 4!=24 distinct mapping in total. If we restrict 1 maps to 1, then there should be at most 3!=6 mappings.] $\endgroup$ – wonderich Apr 12 '18 at 21:07
  • $\begingroup$ Oh, pinning down to one unique isomorphism is in general impossible. There are groups with nontrivial automorphisms, you know... $\endgroup$ – Henrik Schumacher Apr 12 '18 at 21:12
  • $\begingroup$ yes, just give any one is fine, as said, there are 24 possible mappings. Does your algorithm give any map for checking isomorphism? (in order to accept as an answer) $\endgroup$ – wonderich Apr 12 '18 at 21:19
  • $\begingroup$ That's not a complete answer at all, sorry. $\endgroup$ – Henrik Schumacher Apr 12 '18 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.