I am trying to write some Magma code that, given a group $G$, returns a list of pairs $(x,y)$ with $x,y\in G$ such that $[x,y]\neq 1$ and such that every pair $(z,w)$ in the group with $[z,w]\neq 1$ is conjugate (disregarding order) to some $(x,y)$ output by the algorithm. I realized when I began that I have no idea of the computational cost of the various steps in the process. I would love to learn a lot about this, but to stay focused, I will ask a restricted question:
Which of the following three algorithm designs will more efficiently solve the above problem? And how will the answer to this be affected by the group order? By number of conjugacy classes?
- Compute the action by conjugation of $G$ on the set $Sym^2 G$ of unordered pairs of elements of $G$.
- Restrict attention to the pairs that don't commute.
- Partition $Sym^2 G$ into orbits and select a representative from each orbit. Return these selections.
Same as algorithm 1 except allow redundancy by working with the ordered pairs $G\times G$ instead of $Sym^2 G$.
- Decompose $G$ into conjugacy classes.
- Ignoring the singleton classes, select a representative $x$ from each class.
- For each representative $x$, compute the centralizer $H=Z_G(x)$.
- Compute the action of $H$ by conjugation on the complement $G\setminus H$.
- From each orbit of this action, select a $y$, and output $(x,y)$.
From a mathematical aesthetics point of view, for example if I were writing a proof, algorithm 1a would be the way to go, clearly. Both other algorithms will produce redundant lists containing $(x,y)$ and $(y',x')$ as separate outputs, where $x,x'$ and $y,y'$ are simultaneously conjugate (unless the group has a very special property). More fundamentally, the set of conjugacy orbits of unordered pairs is actually the thing I'm trying to get a hold of, so that algorithm 1a aims directly for it while the other two come at it from the side.
But OTOH, if I were to try to generate this list by hand, I would absolutely choose algorithm 2. Both other algorithms force me to take hold of the set of pairs (ordered or unordered) all at once, which is quadratic in the group order, whereas algorithm 2 never requires me to contemplate any set bigger than the group itself at any one time.
How would a computer fare with these questions? Is computing orbits of an action on a big set much harder than on a small set? How about computing all those centralizers? Does the need in algorithm 2 to partition $G$ into orbits of numerous different groups cause extra difficulties? What are the relevant issues?
Thanks in advance.