7
$\begingroup$

Given a finite group $G$ of size $n$ by the table representation. I want to compute the conjugacy classes of group $G$. A trivial algorithm seems to take $O(n^2)$ operation ( $b = g^{-1}a g$ type checking ). For each pair (I know I don't need to do for all pairs ) of elements in $G$ check $b = g^{-1}a g$. I tried to search on internet but did not find anything specific about it in general.

Question : What is the fastest known algorithm for finding conjugacy classes?

$\endgroup$
7
$\begingroup$

I believe this can be done on $O(n \log n)$ on a RAM, where $n=|G|$; I don't know a reference so I'll just write it down here (but surely this is not original). Nor do I know if this is the fastest known, but clearly you can't do it faster than $\Omega(n)$, so it's gotta be close.

Let's assume the group elements are denoted in the computer by the integers $1,\dotsc,n$, with $g_i \in G$ being the group element corresponding to the integer $i$. Assume WLOG that $g_1$ is the identity.

1) Find a generating set $\Gamma$ of size $\leq \log_2 n$ in $O(n \log n)$ time:

G = list of group elements
Gamma = []
Gr = new graph with vertex set G and no edges           // O(n) steps
found = new array of length n, initialized to all false // O(n) steps
for i = 2 to n: // never need to add identity to generating set
    if not found[i] then
        Gamma.append(i)
        // Now update the graph Gr by adding new edges
        // Corresponding to the new generator G[i]=g_i
        for each vertex g in Gr:
            Gr.addEdge(g,g*G[i])
        end for
        do BFS on Gr starting from 1, ignoring any vertices already found
        (for any vertex j encountered, this sets found[j]=true)
    end if
end for

2) Build the following sparse graph (that is, in the edge list representation, not the dense adjacency matrix representation): vertices are the elements of $G$, and there is an (undirected) edge $(g,h)$ if $h = \gamma g\gamma^{-1}$ for some generator $\gamma \in \Gamma$. This is a graph with $n$ vertices and maximum degree $O(\log n)$. Its connected components are the conjugacy classes, and finding them can be done by BFS (say) in time $O(v + e) = O(n + n \log n) = O(n \log n)$.

$\endgroup$
  • $\begingroup$ Are there reductions or hardness results for theses kind of problems? $\endgroup$ – aaaa Sep 2 at 8:15
  • $\begingroup$ @aaaa: Not that I know of, but I haven't though much about it / looked into it. What kind of hardness results might you be interested in for some problem that's already in quasi-linear time? e.g. parallel, but I don't think I'd be too shocked if this could be done in $\mathsf{NC}$... $\endgroup$ – Joshua Grochow Sep 3 at 5:27
  • $\begingroup$ @ Joshua Grochow Do you believe the step of your algorithm can be performed in a linear time? Is there a way to prove the hardness of such kind? $\endgroup$ – aaaa Sep 10 at 9:02
  • $\begingroup$ @aaaa: Linear-time is believable, but doing so requires more than just looking at the graph I constructed in the answer. The issue is that that graph has $\Theta(n \log n)$ edges in general, so linear-time in the size of the graph yields $O(n \log n)$ time in the group order. To beat that you'd have to use something at least a little deeper about conjugacy classes, to avoid working with this graph. As for a lower bound, you might be able to get a lower bound similar to the $\Omega(n \log n)$ sorting lower bound in the decision tree model, but the counting is more complicated. $\endgroup$ – Joshua Grochow Sep 10 at 15:44
  • $\begingroup$ @ Joshua Grochow What about the first step which is to find an $O(\log n)$ sized generating set? $\endgroup$ – aaaa Sep 10 at 15:51

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.