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

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

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

<pre><code>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
</code></pre>

<p>2) Build the following sparse graph (that is, in the edge list representation, <em>not</em> 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)$.</p>

CC BY-SA 4.0
2019-09-03T05:27:05.517Z
@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
CC BY-SA 4.0
2019-09-10T15:44:15.173Z
@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
CC BY-SA 4.0
2019-09-10T15:53:31.373Z
@aaaa: The algorithm I gave for that also involves a BFS on essentially the same graph.
Joshua Grochow
CC BY-SA 3.0
2018-03-01T07:32:00.193Z
2018-03-01T07:32:00.193Z
Joshua Grochow
<p>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.</p>

<p><strong>Question :</strong> What is the fastest known algorithm for finding conjugacy classes?</p>

<ds.algorithms>
What is the fastest known algorithm for finding conjugacy classes?
old
# What is the fastest known algorithm for finding conjugacy classes?

(Asked by: username_0 on 2018-02-27)

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?

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2018-03-01. Score: 7 | Accepted answer

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

> **Comments:**
> **username_1**: @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}$...  
> **username_1**: @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.  
> **username_1**: @aaaa: The algorithm I gave for that also involves a BFS on essentially the same graph.  

---

