# What is the fastest known algorithm for finding conjugacy classes?

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?

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
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:

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)$.
• @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}$... – Joshua Grochow Sep 3 '19 at 5:27
• @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. – Joshua Grochow Sep 10 '19 at 15:44