G Set improvements

[mjrodgers]

This is an overview of the outstanding issues regarding G sets, and is meant to track their current status.

• We need to improve computation of GAP orbits on Julia objects (see GAP orbits on Julia objects #722). The obstacle here is that GAP deals with Julia objects in a way that does not utilize hashes, and so defaults to slow heuristics. One proposed possibility for dealing with this is using the NewDictionary function to basically inject a wrapper around Julia.hash to use when computing orbits; in the future the NewDictionary function could be modified to turn it into an "operation" (in GAP parlance), which would then return a new type of "dictionary" object (possibly a wrapper around Julia's Dict).
• We should speed up computation of orbits on integers (see Orbits of permutation groups on integers should be faster #3287). The linked issue has some benchmarks that show that some orbit computations in OSCAR are much slower than in GAP. This is possibly related to the fact that GAP does not directly use OnPoints, but instead a wrapper function calling Julia's ^ operator, which then effectively delegates to OnPoints; in addition to the overhead created, this prevents GAP from detecting some "easy" cases.
• We should implement G sets arising from the orbit of a matrix group on subspaces of the associated vector space.
• The G-set functionality needs better documentation (see Missing docstrings for a lot of G-set functionality #3314); in particular, we are missing docstrings for is_transitive, transitivity, is_primitive, is_regular, is_semiregular, rank_action, blocks, maximal_blocks, minimal_block_reps, and all_blocks (I think this list is complete?).

[fingolfin]

Regarding the middle point, we currently do this:

    gfun = GapObj(action_function(Omega))

    # The following works only because GAP does not check
    # whether the given (dummy) group 'GapObj(G)' fits to the given generators,
    # or whether the elements of 'acts' are group elements.
    orb = Vector{S}(GAP.Globals.Orbit(GapObj(G), omega, acts, acts, gfun)::GapObj)

How about we replace the first line by

    gfun = gap_action_function(Omega)

and the new function takes care of the details. (Obviously other similar places also need to be changed, e.g. when calling GAP.Globals.Stabilizer).

At first I thought we can't just map on_tuples to GAP.Globals.OnTuples because, we want GAP to use our ^ Julia method instead of its OnPoints. But the GAP kernel function OnPoints is actually implemented by invoking the GAP kernel dispatcher POW, i.e., GAP's ^, which goes through regular GAP method dispatch. And we already have GAP methods there for the case were one argument is a Julia object, doing the right thing.

So I think we can just do something like this:

# common code
function gap_action_function(Omega::GSet)
  f = action_function(Omega)
  f == ^ && return GAP.Globals.OnPoints
  f == on_tuples && return GAP.Globals.OnTuples
  f == on_sets && return GAP.Globals.OnSets
  # etc.
  return GapObj(f) # generic fallback
end

An obvious variation (trading a way a little bit of memory for a little bit gained speed) is to compute the gap_action_function when creating the G-set and storing it, but I think overall that's a relatively minor implementation detail.

[mjrodgers]

I can't seem to get this to work, I get strange GAP errors:

julia> collect(orbit(G,1))
ERROR: Error thrown by GAP: Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `LargestMovedPoint' on 1 arguments at /Users/gek81vuf/.julia/artifacts/7a7471c3a274d605d85c06775fcb6f9962114ff7/share/gap/lib/methsel2.g:250 called from
LargestMovedPoint( gens ) at /Users/gek81vuf/.julia/artifacts/7a7471c3a274d605d85c06775fcb6f9962114ff7/share/gap/lib/grpperm.gi:204 called from
OrbitPerms( acts, pnt ) at /Users/gek81vuf/.julia/artifacts/7a7471c3a274d605d85c06775fcb6f9962114ff7/share/gap/lib/oprtperm.gi:31 called from
orbish( G, pnt, gens, acts, act ) at /Users/gek81vuf/.julia/artifacts/7a7471c3a274d605d85c06775fcb6f9962114ff7/share/gap/lib/oprt.gd:858 called from
<function "Orbit">( <arguments> )
 called from read-eval loop at *defin*:0

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] ThrowObserver(depth::Int32)
   @ GAP ~/.julia/packages/GAP/m8wkY/src/GAP.jl:91

(oddly enough it works if I don't try to collect it)

[fingolfin]

@mjrodgers without seeing the concrete code, hard to comment. Perhaps open a draft PR?

orbit(G, 1) just creates a lazy G-set object, but performs no computation. collect is one way to actually trigger the computations. So that part of it is not surprising.

Actually collect(Omega) calls into iterate which calls elements which calls orbits(Omega) which finally calls orbit(Omega,1) which does the work... talk about layers sigh.

Playing with that a bit, I had to change GapObj(gens(G)) to GapObj(gens(G); recursive=true). Then the orbit computation worked.

Of course this may not what we want if the group acting is a non-GAP group (such as the Weyl groups by @lgoettgens and co, or our finite abelian groups). That's fine in so far as I expect there to be different handling in certain places (to make use of "optimizations" in some). I'd not worry too much about it initially, but of course dealing with those correctly should also be on our road map.