We have a special case for VoleCon.InGroup for a symmetric group, coming from the fact that a symmetric group is the setwise stabiliser of its moved points that fixes all the other points.

Therefore we should be able to do something similar for VoleCon.InCoset for a coset of a symmetric group, using something about setwise transporters and moved points? Perhaps?

I don't like the points option any more, so I'm going to remove it. It is redundant, and can be replaced by an additional constraint Constraint.MovedPoints or Constraint.LargestMovedPoint (or by simply including an integer k in the list of constraints).

Maintaining multiple ways to do the same thing is annoying.

In addition, the GAP bug described in gap-system/gap#4510 also has the potential to cause really weird behaviour in relation to the points option. This has caught me out before. So that's an added bonus.

Before and/or after processing the given arguments, it could be the case that VoleFind.Group knows that it has (directly or indirectly) been given a single constraint of the form Constraint.InGroup(G), possibly in addition to a constraint Constraint.MovedPoints(pts), where pts = MovedPoints(G). In this case, Vole can simply return G, without having to perform a search.

We also want to be able to distinguish those refiners that can be used in a canonical image search from those that cannot.

Categories

• IsBTKitRefiner
• IsGBRefiner
• IsVoleRefiner

GraphBacktracking should take BacktrackKit refiners.
Vole should be able to take BacktrackKit and GraphBacktracking refiners.
(Should BacktrackKit be able to take certain kinds of GraphBacktracking refiners? Or just ignore this?)

Attributes/properties known at creation

• LargestRequiredPoint
• IsKnownPerfectRefiner (if we know a priori that a refiner is perfect)
• IsCanonicalCompatible

Additional attributes/properties that require computation

• IsPerfectRefiner (is it even possible to always compute the answer to the question of perfectness?)
• UnderlyingSet (the set of permutations that you are refining for, e.g. the normaliser)

This is the only significant bit of documentation that's really missing from Vole.

To a large degree, this will require writing/finish proper documentation for refiners in the BacktrackKit and GraphBacktracking packages.

I've set up code coverage for the GAP side of Vole: https://app.codecov.io/gh/peal/vole

It would be nice to eventually have this available for the Rust component too (I'm not sure how to set it up).

It seems that the default refiner for VoleCon.InGroup(AlternatingGroup(points)) is InGroup-GB, which I guess uses a stabiliser chain? This would explain why this is slow:

gap> A50 := AlternatingGroup(50);;
gap> con := VoleCon.InGroup(A50);;
gap> VoleFind.Group(con) = A50;
true
gap> time;
7228

Using a stabiliser chain for an alternating group is perhaps not the best way of refining for an alternating group. Can we even sensibly refine for an alternating group in (extended) graph backtracking?

Perhaps the refiner should not actually add anything onto the stack, but it should just check for evenness when you reach a leaf node. In particular, perhaps this is what the refiner for VoleCon.IsEven should do (#31), and then VoleCon.InGroup(AlternatingGroup(points)) can just be immediately translated to [VoleCon.IsEven(), VoleCon.MovedPoints(points)].

At some point, I think it would be a good idea to add some special cases to avoid annoying/embarrassing behaviour.

This is already quite slow:

gap> VoleFind.Group(AlternatingGroup(40));
<permutation group with 39 generators>

But surely we as the package authors should be able to immediately return the group in such cases. Somehow. Similarly:

gap> VoleFind.Coset(AlternatingGroup(40) * (1,2));
RightCoset(<permutation group with 38 generators>,(1,39,2,40)(3,38)(4,37)
(5,36)(6,35)(7,34)(8,33)(9,32)(10,31)(11,30)(12,29)(13,28)(14,27)(15,26)
(16,25)(17,24)(18,23)(19,22)(20,21))

takes over a second.

Idea: if VoleFind.Rep(con1, con2, con3, refiner1) returns a representative element (i.e. not fail), lets call it x, then Vole could set the Representative attribute for any of [con1, con2, con3, refiner1!.constraint] that do not yet have a representative set. i.e. SetRepresentative(con1, x);, and so on.

And also decide a good name for it!

In writing the documentation for VoleFind.Canonical (which I am still working on), I realised that it's quite tricky to explain what the user needs to do in order to make everything work ‘right’.

To canonise an object x in a way that involves custom refiners or constraints, a user needs to do something like:

VoleFind.Canonical(G, con/ref1(x), con/ref2(x), con/ref3(x))

where the constraints/refiners con/ref1, con/ref2, con/ref3 relate to the object x somehow (this code snippet is simplified). con/ref1 might be something like GB_Con.NormaliserSimple2.

But there's not much point in ever canonising one object in isolation; because a canonical image is essentially meaningless without another canonical image to compare it to.

So if a user does want to canonise another object y (which is possibly in the same orbit of G as x, i.e. x and y are possibly isomorphic, and we want to use VoleFind.Canonical to determine this...) then they have to do everything again in a 'consistent' way (and in the same GAP session). It would again look something like this:

VoleFind.Canonical(G, con/ref1(y), con/ref2(y), con/ref3(y))

This is a lot of typing, and there's potential for accidentally using the wrong refiner, or for giving the refiners in the wrong order, which might give the wrong answer.

Therefore I had an idea: what if you could give the group in which you wish to canonise several things (i.e. G), and the 'family' of refiners you want to use for this (con/ref1, con/ref2, con/ref3), and then would Vole return a function that makes sure that everything is done in a consistent way. You would then call this function on the individual objects that you want to canonise, without having to deal with the refiners again.

The interface would look something like:

gap> canoniser := Vole.Canoniser(G, con/ref1, con/ref2, con/ref3);
gap> res1 := canoniser(x);
rec( group := blah, canonical := blah )
gap> res2 := canoniser(y);
rec( group := blah, canonical := blah )

It will probably be a little bit fiddly to make this work properly (e.g. in my example here, we are canonising a single object, not a pair of objects, and all of the constraints/refiners apply to that object one – what if you want to canonise of a pair of different things instead?).

But that's the idea that I've had anyway.

For example, the documentation for VoleCon.Normalise should become the documentation for Constraint.Normalise.

(This is perhaps more of a GraphBacktracking issue, but since we're working on Vole at the moment I think it's better to put it here.)

Currently:

• VoleCon.InCoset translates to:
  • GB_Con.InCosetSimple in canonicalconstraints.g, rather than GB_Con.InCoset in simpleconstraints.g.
• On the other hand, VoleCon.InGroup translates to:
  • GB_Con.InGroup in simpleconstraints.g rather than GB_Con.InGroupSimple in canonicalconstraints.g.

About a month ago I switched VoleCon.InGroup to GB_Con.InGroup in the possibly-mistaken belief that GB_Con.InGroupSimple was slower (i.e. produced larger searches) than necessary, in order to be compatible with canonical images, but that since VoleCon.InGroup is not a valid constraint for a canonical image search, we didn't need to take this compatibility into account. So we could use the 'non-simple' one instead.

Note that the group refiners are just instances of the coset refiners with the representative being the identity.

Basically: I want it to be clear which refiners we should be using in Vole.

Things to do:

• Name things more clearly.
• Clearly denote (with comments) what the purpose/idea of each refiner is.
• Benchmark the search size and time taken.
  • Chris thinks that the cosets refiners should produce (on average) the same sized searches, but that the 'simple' one might be faster overall, especially if you're doing repeated searches with the same group(s).

Very similar to #40:

gap> Stabiliser(SymmetricGroup(3), [], OnSetsSets);
Group([ (2,3), (1,2,3) ])
gap> Vole.Stabiliser(SymmetricGroup(3), [], OnSetsSets);
thread 'main' panicked at 'assertion failed: extra > 0', src/vole/partition_stack.rs:126:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Error, There was a fatal error in vole: assertion failed: extra > 0 at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:316 called from
_Vole.ExecuteVole( rec(
    config := rec(
        points := points,
        find_coset := find_coset,
        find_canonical := find_canonical,
        root_search := root_search,
        search_config := rec(
            full_graph_refine := false,
            find_single := find_single ) ),
    constraints := constraints ), gapcons, canonical_group
 ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:414 called from
_Vole.Solve( points, false, false, false, constraints, false, false
 ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:455 called from
_Vole.GroupSolve( bounds.max, constraints ) at /Users/Wilf/gap/pkg/vole/gap/interface.gi:43 called from
VoleFind.Group( G, con ) at /Users/Wilf/gap/pkg/vole/gap/wrapper.gi:40 called from
<function "Vole.Stabiliser">( <arguments> )

Here is a digraph:

Something is going wrong when computing its stabiliser with Vole, and I think it's because Vole does not (cannot?) "properly" handle Digraphs with isolated vertices.

If I want to stabilise this digraph D in Sym(1) or Sym(2), then all is fine, the isolated vertex doesn't come into play. It's also fine with Sym(3), because then, all points in question are vertices of the digraph. But once I get to Sym(4), Vole is confused about the distinction between the points 3 and 4 – note that 3 is a vertex of the digraph, but that 4 is not.

gap> D := Digraph([[2], [], []]);;
gap> VoleFind.Group(1, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(2, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(3, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(4, Constraint.Stabilise(D, OnDigraphs));
thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', src/vole/refiners/digraph.rs:76:35
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Any { .. }', src/bin/vole.rs:100:53
Error, No return value from 'vole' at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:285 called from
_Vole.ExecuteVole( rec(
    config := rec(
        points := points,
        find_coset := find_coset,
        find_canonical := find_canonical,
        root_search := root_search,
        search_config := rec(
            full_graph_refine := false,
            find_single := find_single ) ),
    constraints := constraints ), gapcons, canonical_group ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:414 called from
_Vole.Solve( points, false, false, false, constraints, false, false ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:455 called from
_Vole.GroupSolve( bounds.max, constraints ) at /Users/Wilf/gap/pkg/vole/gap/interface.gi:43 called from
<function "VoleFind.Group">( <arguments> )

Note that everything is fine if the isolated vertex just isn't part of the digraph:

gap> D := Digraph([[2], []]);;
gap> VoleFind.Group(1, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(2, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(3, Constraint.Stabilise(D, OnDigraphs));
Group(())
gap> VoleFind.Group(4, Constraint.Stabilise(D, OnDigraphs));
Group([ (3,4) ])

At some point, this is a policy choice: which permutations should be considered to stabilise a digraph? Should they treat isolated vertices interchangeably with points that are not vertices in the digraph?

In my opinion, I think that a permutation should stabilise a digraph if and only if it stabilises its set of vertices, and acts in the proper way on those vertices (and it can do whatever it want to points that are not vertices). In particular, for me, the 'correct' answer to the erroring code above should be:

gap> VoleFind.Group(4, Constraint.Stabilise(D, OnDigraphs));
Group(())

Since the points 3 and 4 are not interchangeable in relation to this digraph.

We need to be careful that any change we make does not interfere with our implementation of the centraliser refiner for a permutation.

This is an administrative note, for some time in the future. It's not really relevant yet, since a GAP the next release is still some way off, and also we're not ready for it anyway. But I think there will be some stuff to do in this regard, so I'll create this issue to keep track of that.

Ultimately, I presume we want Vole to be distributed with future GAP releases, right? Especially if we want Vole to be part of the Windows installers for GAP, which I think is desirable.

As things stand, even if Vole was perfectly polished, it wouldn't be very useful if Vole was distributed with GAP releases right now, because it doesn't work without BacktrackKit and GraphBacktracking, which themselves are not (yet) distributed with GAP. Therefore, the first tasks that I see are:

• Get BacktrackKit distributed with GAP, or remove Vole's dependency on it.
• Get GraphBacktracking distributed with GAP, or remove Vole's dependency on it.

Nice to have:

• Get OrbitalGraphs distributed with GAP.

Further things that aren't as important:

• Get QuickCheck distributed with GAP.

The package builds, but then the tests don't even start to run, with the following error, see e.g. https://github.com/peal/vole/runs/3973553522?check_suite_focus=true

Run cd rust && cargo test --release -q
error: failed to parse manifest at `/home/runner/.cargo/registry/src/github.com-1ecc6299db9ec823/half-1.8.1/Cargo.toml`

Caused by:
  feature `resolver` is required

  this Cargo does not support nightly features, but if you
  switch to nightly channel you can add
  `cargo-features = ["resolver"]` to enable this feature

I don't know what this means.

Superficially, it seems that Vole is properly taking multidigraphs into account:

gap> D1 := Digraph([[2],[1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> D2 := Digraph([[2,2],[1]]);
<immutable multidigraph with 2 vertices, 3 edges>
gap> VoleFind.Rep(VoleCon.Transport(D1, D1, OnDigraphs));
(1,2)
gap> VoleFind.Rep(VoleCon.Transport(D2, D2, OnDigraphs));
()
gap> VoleFind.Rep(VoleCon.Transport(D1, D2, OnDigraphs));
fail
gap> VoleFind.Rep(VoleCon.Transport(D2, D1, OnDigraphs));
fail

However, @ChrisJefferson wasn't consciously thinking about digraphs with multiple edges when he implemented this stuff. So it's possibly that it's only coincidentally working for the cases that I've tried, and that it will not work properly in some cases.

We should look at the code and convince ourselves that it does 'the right thing' in all cases.

As we have discussed before, we are currently not really bothering to add special cases to our packages.

Nevertheless, some optimisations and special cases will naturally creep in, and indeed, some already have: for example, if both Constraint.IsOdd and Constraint.IsEven are specified, then the search doesn't even begin (since there are no even-and-odd perms).

However, for some purposes, it may be useful to be able to use Vole, while ensuring that this never happens.

One way to do this is to use the undocumented _Vole.Solve function, etc, directly (with arguments points, find_single, find_coset, find_canonical, constraints, canonical_group, root_search)...but this is difficult. Surely it would be nicer to offer the same functions as usual, but just to guarantee that nothing clever will be done before the search commences.

I think the simplest way is just to have an option to skip the 'preprocessing' steps of the various VoleFind functions, such as VoleFind.Group and VoleFind.Rep, and simply pass the arguments directly to _Vole.Solve, etc, in the appropriate way.

Perhaps this could be a value option, e.g. VoleFind.Rep(constraint1, refiner1, constraint2 : pure)

The question is: how little processing should be done? Does it still let Vole interpret constraints into refiners, or should it only allow actual refiners as arguments?

(To some extent, this issue may also apply to BacktrackKit and GraphBacktracking).

I think this is missing but it would be great to have (it lets us do ordered partitions, for example).

This subsumes what #26 was about, so I will close that issue.

• Create a clever “process constraints” function, which can make deductions about the collection of constraints/refiners that is given.

  • For example, it should be able to look at the underlying constraints and:
    • Remove duplicate constraint objects (although not duplicate refiners).
    • Notice if the collection contains Constraint.IsEven and Constraint.IsOdd.
    • Notice if the collection contains Constraint.Nothing.
    • Change an in-group constraint of a natural alternating group into is-even and in-symmetric-group constraints.
    • Combine multiple in-symmetric-group refiners into a single one.
  • This should probably be in BacktrackKit.

• Create a dummy BacktrackKit refiner that wraps any constraint for which we don't have a refiner (and warn about this).

• Create a big function that finds a Vole-appropriate list of refiners for any processed list of constraints.

• Enable all VoleFind functions to take a BacktrackKit constraint, which uses the above function to turn constraints into refiners.

• Get rid of fail as an acceptable constraint.

• Get rid of VoleCon, because it's not needed (replaced by BacktrackKit's Constraint record).

• VoleFind.Group for a single mathematical InGroup constraint returns the group immediately? (#17).

Sorry for the clickbait title.

For each constraints given to VoleFind.Rep that has its Representative attribute set, Vole could check whether the other constraints also accept that permutation. If so, this lets you bypass search and simply return that element.

I'm not sure whether this is a good idea, but it's something I've talked about and mentioned sometimes.

Currently, the Vole "constraints" functions immediately give you one refiner that refines for your constraint. But perhaps this is not always optimal: perhaps for some search instances, it would be better if the constraint was converted into a refiner differently, or maybe even converted into multiple refiners.

A use case could be normalisers: there may be refiners for normalisers that have clever tricks that don't work in 'canonical' searches. Therefore it would be nice for the normaliser constraint to translate in non-canonical searches into refiners that do these clever tricks, but for canonical searches, the normaliser constraint would be translated into canonical-safe refiners.

This could tie in with #25; where a refiner could know what constraint it was implemented for, and constraints would share some (many?) of the properties/attributes that I propose for refiners.

Perfect refiners should come first; perhaps we should have additional 'levels' of refiners beyond this.

As originally reported on MS Teams on 2021-07-30@22:45:

gap> VoleFind.Group(AlternatingGroup(4), SymmetricGroup(5));
Error, List Element: <list>[5] must have an assigned value in
  return points[x]; at /Users/Wilf/gap/pkg/graphbacktrack/gap/constraints/simpleconstraints.g:86 called from
filters[i]( x ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:129 called from
func( C[i] ) at /Users/Wilf/gap/lib/coll.gi:665 called from
List( [ 1 .. PS_Points( state!.ps ) ], function ( x )
      return HashBasic( filters[i]( x ) );
  end ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:129 called from
_Vole.CallRefiner( savedvals, refiners[result[2]], result[3], result{[ 4 .. Length( result ) ]}
 ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:326 called from
_Vole.ExecuteVole( rec(
    config := rec(
        points := points,
        find_coset := find_coset,
        find_canonical := find_canonical,
        root_search := root_search,
        search_config := rec(
            full_graph_refine := false,
            find_single := find_single ) ),
    constraints := constraints ), gapcons, canonical_group ) at /Users/Wilf/gap/pkg/vole/gap/internal/comms.gi:409 called from
...  at *stdin*:3
type 'quit;' to quit to outer loop
brk>

We should use the ideas from the paper New refiners for permutation group search to improve our in-group refiners.

In particular, in that paper we usually get better performance by only using orbital graphs the first time that they are non-futile.

gap> VoleFind.Group(VoleCon.Stabilise([[]], OnSetsSets) : points := 1);
Group([ (1,2) ])

Probably at some point, the GAP-side validation is taking a minimum of 2 and some other stuff for the number of points to use.

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);

This is a sub-problem of #26. Currently, VoleCon.None (the constraint satisfied by no permutations, although perhaps that name is confusing and could be interpreted as meaning "no constraints"...) returns fail, which itself might indicate that something has gone wrong with the creation of the constraint.

In any case, it can be easy to forget what fail means, and where it comes from.

So it might be nice if VoleCon.None(args...) returns a special object that performs the same role, but which is clearly identifiable (via its ViewString, etc) as the (Vole) constraint that is satisfied by nothing.

On https://peal.github.io/vole/ there are broken links giving 404 errors:

• https://gap-packages.github.io/QuickCheck/
• https://markuspf.github.io/OrbitalGraphs/

So I went to look for the repos but https://github.com/gap-packages/QuickCheck does not exist! But @ChrisJefferson tells me it is https://github.com/ChrisJefferson/QuickCheck

OTOH https://github.com/markuspf/OrbitalGraphs does exist but it seems to be an outdated version of https://github.com/gap-packages/OrbitalGraphs -- that repository apparently has an outdated PackageInfo.g with the old URLs listed?

Both packages probably simply need a release?

Useful for normalisers.

I'm not sure of the correct language to use here.

But @ChrisJefferson was saying that, in order to get acceptable performance in GAP-Julia, he may need to write a proper GAP-kernel-to-Vole-Rust-component connector. This would replace the forking and sockets and networking stuff that can be slow in some cases.

Currently, with the standard GAP interface, you can specify refiners for the thing that you want to canonise, but Vole does its own thing with the first argument, i.e. the group G that you are canonising in.

It would be nice if you could tell Vole which refiners it should use for the group (does that even make sense?).

The current argument checking is a bit of a hack, and can be made simpler and more effective if I instead check that all of the constraints are IsStabiliserConstraint, basically.

If we manage to add VoleCon.IsEven, then it would be nice to also have VoleCon.IsOdd.

Thoughts welcome. My thoughts below:

Currently, for any individual case, we can achieve this result by doing VoleCon.InGroup(AlternatingGroup(n)) for an appropriate n.

However, in general, we might not necessarily know what the right n should be, at the point that we instantiate the constraint. In particular, this approach does not give us a "universal" constraint for evenness. This means that we can't just translate IsEven once to an instance of VoleCon.InGroup(AlternatingGroup(n)) that we can use forevermore, because we would have to choose n = infinity for this to work all the time, and that is not possible.

One way around this would be to implement the "lazy" translation of constraints into refiners, as asked for in #26. If this was implemented, we could have a constraint VoleCon.IsEven that doesn't do anything, but is translated into the appropriate VoleCon.InGroup(AlternatingGroup(n)) once a bound for the search is known.

Perhaps the solution is that a 'refiner' for IsEven shouldn't actually be doing anything involving alternating groups... I'll create a separate issue for this.

The "ForceQuitGap" appears missing in the code and I have a warning.

Syntax warning: Unbound global variable in /Users/mathieu/opt/gap-4.11.1/pkg/vole/gap/internal/comms.gi:248
        ForceQuitGap();

This does not prevent vole from loading though.

I am working on defining these actions in the Digraphs package digraphs/Digraphs#449. (However, we do not need to wait before that is finished and merged and released before implementing this in Vole; we can conditionally define OnTuplesDigraphs and OnSetsDigraphs as dummy objects if Digraphs has not already done so.)

OnTuplesDigraphs is the easy one; we should just return a list of the appropriate OnDigraphs constraints/refiners.

OnSetsDigraphs will involve having a function that converts a set of digraphs into a single digraph with extra vertices. This turns a stabiliser/transporter problem for a set of digraphs into a stabiliser/transporter problem of a single (extended) digraph. If we want this to work nicely with canonical images, which we do, we may have to be careful about how we do this. Caution needed!

This should be particularly useful for computing normalisers.

This should result in better performance.

Is there a way we can make GAP suggest autocompleting to Constraint.Transport instead?

There are presumably other similar instances.

(Updated the issue because VoleCon has been converted into the BacktrackKit package constraint called Constraint).