Possible example: two closure

[ChrisJefferson]

I did this for something else, but thought it could be turned into a nice example (although it needs the orbital graphs package..)

---

How can we find the two closure of a group?

g := WreathProductImprimitiveAction(PrimitiveGroup(40,3), PrimitiveGroup(40,2));

We can ask GAP for the two closure:

TwoClosure(g);  # It takes 185 seconds.

Let's try to do this from first principles instead:

Get the orbital graphs (using the OrbitalGraphs package):

o := OrbitalGraphs(g);  # It takes 10 milliseconds and gives us 6 graphs.

We can ask for the automorphism groups of all those graphs

l := List(o, x -> AutomorphismGroup(x));;  # It takes 5 seconds.

We can then ask GAP to intersect all those groups

CallFuncList(Intersection, l);   # This takes longer than 600 seconds!

Vole solves this in 30 seconds -- by finding (in a single step) the intersection of the automorphism groups of all the orbital graphs.

h := VoleFind.Group(List(OrbitalGraphs(g), d -> VoleCon.Stabilize(d, OnDigraphs)): points := 1600);

[wilfwilson]

@ChrisJefferson have you maybe done something wrong here? Admittedly on a very old machine, I get:

gap> o := OrbitalGraphs(g);
[ <immutable digraph with 1600 vertices, 19200 edges>,
  <immutable digraph with 1600 vertices, 43200 edges>,
  <immutable digraph with 1600 vertices, 768000 edges>,
  <immutable digraph with 1600 vertices, 1728000 edges> ]
gap> time;
8013

i.e. only four orbital graphs (not 6), and nearly 3 orders of magnitude slower.

[wilfwilson]

It's probably just your comment about "It takes 10 milliseconds and gives us 6 graphs." that's wrong (if I've not done something wrong on my end), although since OrbitalGraphs is an attribute and it takes a nontrivial amount of time, that would mean that your timing for the last calculation is a little unfair.

[ChrisJefferson]

Ah, I forgot it was an attribute. I'll also double-check my experiment.

[ChrisJefferson]

I was partially cheating, because the TwoClosure has built a stabilizer chain (Which takes 3.3 seconds), after that it only takes 480 milliseconds (still more than I was getting before). I think at some point I changed group, let me make it consistent.

[ChrisJefferson]

Let me give an updated example :)

Native GAP:

gap> g := WreathProductImprimitiveAction(PrimitiveGroup(36,1), PrimitiveGroup(36,1));
<permutation group of size 9770793807380369574073717845253697703739508399273408623931251748901910434078207772135794575130230784 with 6 generators>
gap> StabChain(g);;
gap> time;
757
gap> TwoClosure(g);;
gap> time;
53833

Vole (with a regenerated group):

gap> g := WreathProductImprimitiveAction(PrimitiveGroup(36,1), PrimitiveGroup(36,1));
gap> o := OrbitalGraphs(g);;
gap> time;
678
gap> h := VoleFind.Group(List(o, d -> VoleCon.Stabilize(d, OnDigraphs)): points := 36*36);;
gap> # ( this I time with a stopwatch, because GAP doesn't include vole time -- 6.5 seconds)
gap> h = TwoClosure(g);
true

[wilfwilson]

Thanks for clearing it up 🙂 I think it's a nice example.

(Why points := 31*31? Do you mean 36*36? I guess any integer value <= 36*36 will give the right answer since Vole will take the maximum of that with the 'largest required point' of the digraph constraints, which themselves are 36*36).

i.e. even including points := 0 works fine too 😁...

h := VoleFind.Group(List(o, d -> VoleCon.Stabilize(d, OnDigraphs)): points := 0);;

By the way I've added Vole.TwoClosure which just does what your code does (and it errors if OrbitalGraphs isn't available, so I've not added a proper dependency to the OrbitalGraphs package at this point).

[ChrisJefferson]

Yes, I definately did mean 36*36, I was earlier trying with 31, then realised 36 had a lot more interesting primitive groups :)