2
$\begingroup$

I hope to write a computer program that relabels elements in finite discrete groups by comparing with some "canonical" (e.g. from some famous references or databases) multiplication (Cayley) table. The groups in my mind are 3D crystallographic point groups, so the number of elements in the group will not be too large ($|G| \le 120$).

For example, under some "canonical" labelling of elements $g_1,g_2,...$ (suppose we know that $g_1$ is always the identity), the point group $C_{3v}$ (with 6 elements, isomorphic to the symmetric group $S_3$) has the Cayley table

$$ \left( \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 1 & 6 & 4 & 5 \\ 3 & 1 & 2 & 5 & 6 & 4 \\ 4 & 5 & 6 & 1 & 2 & 3 \\ 5 & 6 & 4 & 3 & 1 & 2 \\ 6 & 4 & 5 & 2 & 3 & 1 \\ \end{array} \right) $$

The convention is: the $i$th row, $j$th column gives the element $g_i g_j$ (e.g. $g_4 g_3 = g_6$, from the 4th row and the 3rd column). But under another labelling, the Cayley table may look like

$$ \left( \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 6 & 5 & 4 & 3 \\ 3 & 4 & 5 & 6 & 1 & 2 \\ 4 & 3 & 2 & 1 & 6 & 5 \\ 5 & 6 & 1 & 2 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 \\ \end{array} \right) $$

Actually this is obtained by relabelling old $g_1,g_4,g_3,g_6,g_2,g_5$ as new $g_1,g_2,...,g_6$ ($g_1$ is always the identity, as said earlier). I want to know an algorithm that finds such a relabelling (which is general is not unique, but finding one is enough).

$\endgroup$
6
  • $\begingroup$ Isn't that basically a Caley table ? By the way, I never heard of the "point"-group. The only $6$-element groups I am aware of are the cyclic group $\mathbb Z_6$ and the symmetric group $S_3$ $\endgroup$
    – Peter
    Feb 25, 2022 at 9:30
  • 2
    $\begingroup$ These terms are used by physicists. "Multiplication table" is indeed the Cayley table. "Point group" is from crystallography, and $C_{3v}$ is isomorphic to the symmetric group $S_3$. $\endgroup$ Feb 25, 2022 at 9:44
  • $\begingroup$ Guess its at least NP-hard and so an efficient algorithm doesn't exist. $\endgroup$
    – Wuestenfux
    Feb 25, 2022 at 10:06
  • $\begingroup$ @Wuestenfux Then maybe the only way is to try all permutations of labels by brute force? Actually I do not need it for the general case. I only want to use this algorithm for 3D crystallographic point groups, the largest of which (icosahedron group $I_h$) has order 120. $\endgroup$ Feb 25, 2022 at 10:18
  • $\begingroup$ Check this, where a comment links to a GAP algorithm. The problem is not known to be NP complete (and probably not), but seems too hard to be P. $\endgroup$ Feb 25, 2022 at 10:37

0

You must log in to answer this question.

Browse other questions tagged .