Orbits

[fieker]

I have

julia> D.s[1]
Group([ (2,3)(5,6), (1,3,2), (4,6,5) ])

yielding

julia> Oscar.GaloisGrp.orbits(D.s[1])
2-element Array{Any,1}:
 Any[1, 3, 2]
 Any[4, 6, 5]

Questions:

• orbits appear to be Arrays (of Any) rather than
  • Set{Int}
  • Array{Int}
• unsorted which makes comparison difficult. Is GaloisGrp/Group.jl using an outdated interface or is this as intended?

[fingolfin]

Yeah it should be at least an Array{Int}. The algorithm produces something unsorted at first, together with an (implicit) Schreier tree; turning the array into a Set{Int} looses that; but of course you can do Set(orbits(x). Also, when using a GSet object, which caches the orbit(s) etc., we could think about also caching such a set, if we find it useful enough to do so.

Anyway, I hope @ThomasBreuer can take a look at this, and of course he may have his own views on this :-)

[ThomasBreuer]

The function Oscar.GaloisGrp.orbits calls GAP's Orbits function and converts the result to Julia. The GAP functions Orbit and Orbits do not promise anything about an ordering of the points. As @fingolfin writes, the ordering of the points reflects the order in which the points were added; however, this fact is not used anywhere, and it is not documented, thus one cannot rely on it.

Several functions in GaloisGrp.jl apply setdiff to the results of orbits calls for different groups. This makes sense only if Sets of the orbits are compared.

In the approach via G-sets, the points can be arbitrary objects such as subgroups; would it be a good idea to promise that such an orbit is sorted? Concerning the idea to regard an orbit as a Set, this has the disadvantage that one has to provide also an ordered variant as soon as one writes down the induced permutation of the points by a group element.

The question seems to be the interface: Sometimes I need an orbit as a Set of points, sometimes I am interested in an array structure, sometimes I want the G-set structure (with certain precomputed/cached values). If orbit returns a G-set, should there be orbit_as_set returning a Set and perhaps orbit_as_array returning a plain array of points?

(For the moment, I will change Oscar.GaloisGrp.orbits to return an Array{Array{Int,1},1} (see #357). And I will change the function such that the orbits on the points 1:degree(G) are returned. The GAP function Orbits returns the orbits on the set of moved points of the given group.)