Algorithm design for enumerating pairs of noncommuting elements up to conjugacy

Question

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?

Algorithm 1a

1. Compute the action by conjugation of $G$ on the set $Sym^2 G$ of unordered pairs of elements of $G$.
2. Restrict attention to the pairs that don't commute.
3. Partition $Sym^2 G$ into orbits and select a representative from each orbit. Return these selections.

Algorithm 1b

Same as algorithm 1 except allow redundancy by working with the ordered pairs $G\times G$ instead of $Sym^2 G$.

Algorithm 2

1. Decompose $G$ into conjugacy classes.
2. Ignoring the singleton classes, select a representative $x$ from each class.
3. For each representative $x$, compute the centralizer $H=Z_G(x)$.
4. Compute the action of $H$ by conjugation on the complement $G\setminus H$.
5. From each orbit of this action, select a $y$, and output $(x,y)$.

Thoughts

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.

Answer 1

If I really wanted to do this I would try programming a variety of different algorithms and thoroughly test them all on a range examples. It also provides a good sanity test of their correctness by comparing the results returned by the different methods tried.

But, from the way you have described Algorithm 1, it looks as though you would have to start by forming the set of all unordered pairs of elements of $G$, which would be impossible if $G$ was large.

I would definitely prefer the general approach of Algorithm 2. Computing the conjugacy classes of $G$ and centralizers is done all done at the same time by the $\mathtt{ConjugacyClasses}$ function, and is likely to be of negligible cost compared with the rest of the process.

I might try numbering the non-singleton classes of $G$ $X_1=x_1^G,X_2=x_2^G,\ldots,X_k=x_k^G$, with corresponding centralizers $C_i = C_G(x_i)$. You can partially avoid getting each unordered pair twice by just computing the orbits of $C_i$ on $X_j$ with $j \ge i$. You will still get some of the representatives $(x,y)$ with $x,y \in C_i$ twice, so you will have to filter those out at the end of the process.

And don't forget that you still have to put in representatives $(x,y)$ with $x$ or $y$ in a singletom class, but that is relatively easy.

Answer 2

There are a number of things you could optimize on, runtime, your own work time implementing code, or memory use. Most likely memory use will become the first obstacle when looking at larger examples (as you can't wait to hope for more memory). Thus in the end an algorithm like your #2 will get you further. (If you want a quick hack for small examples use #1.)

What I would do is however the following, which uses group conjugation to reduce the problem:

1. Determine Conjugacy classes
2. For each class representative $x$, let $C=C_G(x)$. Run (second loop) through all conjugacy classes, let $y$ be the class representative, $D=C_G(y)$.
3. Compute double cosets $C\setminus G/D$.
4. For each double coset representative $r$ let $z=y^r$. (This is the $C_i$ orbits on the class of $X_j$ Derek Holt's answer is already mentioning.)
5. Test the pair $x,z$ for your property.

These pairs $x,z$ are now enumerated only up to $G$-conjugacy. In most cases this means that you never need to store, or run through, something as large as a whole class, but the number of double cosets is significantly smaller.

If you need help with implementing this with GAP -- I cannot comment on Magma -- let me know.