Groups: G-sets

[fingolfin]

In order to properly support thing like stabilizer, orbit, orbit_stabilizer, all_blocks, maximal_blocks, isregular, istransitive etc. for arbitrary group actions (see also Chapter 41 "Group Actions in the GAP reference manual). To this end, I suggest introduce an abstraction somewhat similar to Magma's G-sets resp. GAP's external sets.

Unlike Magma GSet, I do not think we should restrict this to permutation groups either.

Also, I explicitly do not want use GAP's ExternalSet to implement this, as it has too much overhead (and perhaps also other baggage). Rather, I'd implement this as a Julia type with ideally little overhead in the general situation.

That is, a type GSet which represents a set together with an action by a group G, and multiple constructors for it. The functions listed above can then be applied to such G-sets. The code could be in src/Groups/GSets.jl.

I'd imagine that we'd use (subtypes of) GSet to represent all kinds of things, potentially including conjugacy classes, cosets (xH is the orbit of x under H), and more...

I need to fill in more details later but I keep not getting to this, so I'd rather file this as an incomplete issue than forget it.

Ping @GDeFranceschi

[fingolfin]

We need to make progress on this. Perhaps @ThomasBreuer can also help out.

It would be very nice if one could write this (but careful, there is already Hecke.orbit, and I think it has slightly different conventions than GAP, so we need to coordinate with them):

julia> G = symmetric_group(4)
Sym( [ 1 .. 4 ] )

julia> orbit(G, [1,2,3,4])
...

julia> orbit(G, [1,2,3,4], on_tuples)  # GAP style order
...

julia> orbit(G, on_tuples, [1,2,3,4])  # hecke style order?!? I think?
...

What should the return values? It could be the orbit as a vector; but better would be a GSet, which also knows the acting group and action. it could compute the orbit lazily or not, and should ideally be easy to convert to a vector or allow iteration...

[thofma]

I don't think we have a strong opinion on the order of the arguments. But maybe there was a specific reason @fieker?

I like the idea of doing X = GSet(G, f) and then letting orbit(X, a) be an iterator on which one call collect etc. For convenience we could define orbit(G, a, f) = orbit(GSet(G, f), a)?

[fieker]

On Sat, Feb 13, 2021 at 03:27:49AM -0800, thofma wrote: I don't think we have a strong opinion on the order of the arguments. But maybe there was a specific reason @fieker?

No reason...

I like the idea of doing `X = GSet(G, f)` and then letting `orbit(X, a)` be an iterator on which one call `collect` etc. For convenience we could define `orbit(G, a, f) = orbit(GSet(G, f), a)`?

OK, then lets try that

…

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #108 (comment)

[ThomasBreuer]

Here is a first proposal for the setup (in Groups/gsets.jl).

mutable struct PermGroup_GSet_on_points <: GSet{PermGroup}
    group::PermGroup
    seeds::Set{<:Base.Integer}
    AbstractAlgebra.@declare_other  # we want to store the orbits, the set of elements etc. if known

    function PermGroup_GSet_on_points(G::PermGroup, seeds::Set{<:Base.Integer})
        gset = new(G, seeds, Dict{Symbol,Any}())
        @assert length(seeds) > 0
        return gset
    end
end

gset(G::PermGroup, Omega::Set{T}) where T<:Base.Integer = PermGroup_GSet_on_points(G, Omega)

function gset(G::PermGroup)
    omega = gset(G, Set(1:G.deg))
    AbstractAlgebra.set_special(omega, :elements => omega.seeds)
    return omega
end

function orbits(Omega::PermGroup_GSet_on_points)
    orbits = AbstractAlgebra.get_special(Omega, :orbits)
    if orbits == nothing
      G = Omega.group
      orbits = Set{Set{Int}}(GAP.Globals.Orbits(G.X, GAP.GapObj(collect(Omega.seeds))))
      AbstractAlgebra.set_special(Omega, :orbits => orbits)
    end
    return orbits
end

function elements(Omega::PermGroup_GSet_on_points)
    elements = AbstractAlgebra.get_special(Omega, :elements)
    if elements == nothing
      orbits = orbits(Omega)
      elements = union(orbits...)
      AbstractAlgebra.set_special(Omega, :elements => elements)
    end
    return elements
end

orbit(G::PermGroup, pt::T) where {T<:Base.Integer} = PermGroup_GSet_on_points(G, Set(pt))

Base.length(C::GSet) = length(elements(C))

representative(C::GSet) = first(C.seeds)

If this is reasonable then I will provide an analogous variant for matrix groups.

[fieker]

On Mon, Mar 01, 2021 at 07:32:43AM -0800, ThomasBreuer wrote: Here is a first proposal for the setup (in `Groups/gsets.jl`). ``` mutable struct PermGroup_GSet_on_points <: GSet{PermGroup} group::PermGroup seeds::Set{<:Base.Integer} ***@***.***_other # we want to store the orbits, the set of elements etc. if known function PermGroup_GSet_on_points(G::PermGroup, seeds::Set{<:Base.Integer}) gset = new(G, seeds, Dict{Symbol,Any}()) @Assert length(seeds) > 0 return gset end end gset(G::PermGroup, Omega::Set{T}) where T<:Base.Integer = PermGroup_GSet_on_points(G, Omega) function gset(G::PermGroup) omega = gset(G, Set(1:G.deg)) AbstractAlgebra.set_special(omega, :elements => omega.seeds) return omega end function orbits(Omega::PermGroup_GSet_on_points) orbits = AbstractAlgebra.get_special(Omega, :orbits) if orbits == nothing G = Omega.group orbits = Set{Set{Int}}(GAP.Globals.Orbits(G.X, GAP.GapObj(collect(Omega.seeds)))) AbstractAlgebra.set_special(Omega, :orbits => orbits) end return orbits end function elements(Omega::PermGroup_GSet_on_points) elements = AbstractAlgebra.get_special(Omega, :elements) if elements == nothing orbits = orbits(Omega) elements = union(orbits...) AbstractAlgebra.set_special(Omega, :elements => elements) end return elements end orbit(G::PermGroup, pt::T) where {T<:Base.Integer} = PermGroup_GSet_on_points(G, Set(pt)) Base.length(C::GSet) = length(elements(C)) representative(C::GSet) = first(C.seeds) ``` If this is reasonable then I will provide an analogous variant for matrix groups.

I'd automatically always also supplement this for T = fmpz, or, where this makes sense, RingElem

…

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #108 (comment)

[ThomasBreuer]

@fieker
O.k., if fmpz shall be supported as points on which permutation groups act then we have to start one layer below, and define fmpz(1)^perm for a permutation perm.
The next question is then what the default shall be: Which type shall the points in gset(symmetric_group(5)) have?

[fieker]

On Mon, Mar 01, 2021 at 08:06:26AM -0800, ThomasBreuer wrote: @fieker O.k., if `fmpz` shall be supported as points on which permutation groups act then we have to start one layer below, and define `fmpz(1)^perm` for a permutation `perm`. The next question is then what the default shall be: Which type shall the points in `gset(symmetric_group(5))` have?

Small Int I'd say (or UInt if you can tolerate hex printing), but Integer goes up to BigInt, thus my call for fmpz...

…

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #108 (comment)

[ThomasBreuer]

For the next iteration (general case of G-sets), I will create a pull request.

From my point of view, the current situation is as follows.

• If we want to use GAP functionality then we run into problems with GAP's method selection, because it is not "friendly to external objects": We want to act on many different kinds of objects for which we do not want to create corresponding GAP objects. However, it seems that we cannot get into the GAP methods for example of OrbitOp, already because the Julia function which implements the action is not recognized as an object in GAP's IsFunction filter.
  (Note that in a GAP session, JuliaFunction( "sqrt" ) yields an object in IsFunction, whereas in a Julia session, GAP.Globals.JuliaFunction(g"sqrt") yields the Julia function itself, which is not in GAP's IsFunction. Did I miss something?)
• If we do not want to use GAP functionality then we have to write a lot of Julia code. This is no problem if only orbits are concerned, but as soon as we need stabilizers, transversals, etc., it would make sense to use the machinery that is already in GAP.
• It might be worth a try to change the GAP side such that our Julia objects about group elements, action functions, etc. can be passed to the GAP code.

[fingolfin]

This still needs a lot of work. Let's work on it today. To make it concrete:

• there is code in experimental/GaloisGrp/GaloisGrp.jl for computing stabilizers etc. by calling into GAP. All of that code should be replaced by calls to "official" code (which of course first needs to be written where missing).
• Note that for a function like stabilizer, my vision would be that the most powerful version is stabilizer(gset) where gset can be constructed in many ways; but there should also be a version stabilizer(G, x) where G has an "obvious" implied action (e.g.: G is a permutation group and x an Int or a tuple/set/... of ints; or G is a matrix group and x a vector or subspace or...). But unlike GAP, for the more powerful variants with additional arguments (like Stabilizer(G, Omega, x, gens, acts, act), I'd say we should simplify our lives by having all of these be G-set constructors.

But let's not get lost in details and fancy options! For today, really, the application in the Galois groups code should work, and perhaps also matrix group stabilizers (@thofma had a concrete question about that recently).

[fingolfin]

Another candidate for a g-set is the return value of right_cosets