3
$\begingroup$

my question is quite simple.

If you are given the generators of a group, is there any systematic way to generate all of the elements of the group?

For example, suppose that you have the Hadamard gate and the Phase gate and you want to generate the Clifford group Clif_1 by multiplying these two matrices together. The group Clif_1 has 24 elements: how do you generate all of them systematically?

And what about Clif_2 that has 11520 elements generated by Hadamard, Phase and CNOT gate?

I have heard about the Schreier-Sims algorithm and the generalization by Knuth, but I don't know exactly how they work. I would like to implement this algorithm using Mathematica rather than GAP or MAGMA.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ The generators are not enough to determine the group. There are many groups with, say, two generators. $\endgroup$ – Dietrich Burde Mar 30 '16 at 9:48
  • $\begingroup$ Will it help to you if you will be able to interface GAP from Mathematica? You need to use SCSCP4Mathematica package developed in the SCIEnce project and run GAP as an SCSCP server using the SCSCP package for GAP. $\endgroup$ – Alexander Konovalov Mar 30 '16 at 10:00
  • $\begingroup$ you need to know also the order of the generators, if they commute or not, .. $\endgroup$ – reuns Mar 30 '16 at 10:00
3
$\begingroup$

The first question you should ask yourself is why you would want to generate all the elements of a (finite) group at all, because that is rarely necessary, and often impossible.

This is rather the point of Schreier-Sims: It computes a base and strong generating set for a group, which gives you something akin to a coordinate system to address group elements. It also gives you the size of the group without ever computing all elements via the Orbit-Stabiliser theorem. James Mitchell has described this very well here: How do Gap generate the elements in permutation groups?

Once you have a base and strong generating set you can of course also iterate over all elements of the group, you'll just find that iterating over all elements of a group the size of, say, the Monster will be a bit tedious.

There is no implementation of Schreier-Sims for matrix groups in GAP, but only for permutation groups. GAP is open source, so in principle you can take inspiration from the code that is in GAP, and available under https://github.com/gap-system/gap

For reasonably small matrix groups (over finite fields) it is worth just looking at the permutation representation of the group.

There is an implementation of Schreier-Sims for matrix groups written in GAP, but not distributed with it, which is available at https://sourceforge.net/projects/matrixss/. I do not know how well it works. The code is open as well, so in principle you can get inspiration from that.

For basic computational group theory, I recommend looking at Holt, Eick, O'Brien's "Handbook of Computational Group Theory", or Hulpke's notes: http://www.math.colostate.edu/~hulpke/lectures/m676cgt/notes.pdf

$\endgroup$

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.