Another IsPrimitive issue

[ThomasBreuer]

(Issue #3329 also deals with IsPrimitive.)

A student in Aachen has noticed the following behavior, which happens in the GAP master branch as well as in released versions.

gap> G:= MathieuGroup( 12 );;
gap> omega:= RightTransversal( G, SylowSubgroup( G, 11 ) );;
gap> IsPrimitive( G, omega, OnRight );  time;
false
5140
gap> act:= Action( G, omega, OnRight );;  time;
93
gap> IsPrimitive( act );  time;
false
49

Should we add some statements to the documentation, saying that IsPrimitive is more efficient when it is called with a permutation group in its natural action on points?

Or should an IsPrimitive method for non-natural actions be installed, which calls first Action and then IsPrimitive for the image under the action?

[fingolfin]

The problem with explaining this in the documentation is that in practice people won't read it anyway.... So in this sense, I'd prefer the second approach. But I wonder if there are situations where that in turn might be slower?

Perhaps @hulpke has some thoughts on this?

[james-d-mitchell]

I've been looking at this a little during the GAP days in St Andrews. It seems that the issue is with IsTransitive and not with IsPrimitive per say:

gap> G:= MathieuGroup( 12 );;
gap> omega:= RightTransversal( G, SylowSubgroup( G, 11 ) );;
gap> IsPrimitive( G, omega, OnRight );  time;
false
925
gap> G:= MathieuGroup( 12 );;
gap> omega:= RightTransversal( G, SylowSubgroup( G, 11 ) );;
gap> Blocks(G, omega, OnRight);;
gap> time;
86
gap> IsTransitive(G, omega, OnRight) and Length(Blocks(G, omega, OnRight)) <= 1;
false
gap> time;
933
gap> IsTransitive(G, omega, OnRight);
false
gap> time;
918

I'm going to dig a bit deeper.

[ThomasBreuer]

This looks interesting.

I had thought the whole thing is about performance, but the false result of IsTransitive(G, omega, OnRight) shows that the problem is conceptual.

The object returned by RightTransversal is a wrapped list of group elements. The group does in general not act on this list by multiplication from the right, but it acts on the right cosets in question. The function Action works like this, by identifying an image element "in the list" via the function PositionCanonical not via Position.
(This is documented functionality, don't ask whether this is beautiful magic or just an ugly hack.)

Apparently IsTransitive and thus IsPrimitive do not know about this interpretation of the right transversal: The false result of IsTransitive just means that the group does not act at all on the given list of elements, which is correct.

Hence the IsPrimitive call with which this discussion started is simply wrong.
I guess that Action is the only function that does the magic sketched above.
What shall we do in order to avoid this kind of misunderstanding?

[ThomasBreuer]

I see several ways to deal with the problem.

• Just change the documentation:
  Warn users not to call IsTransitive, IsPrimitive, etc. for the "action" (for which it depends on the interpretation by GAP whether it is really an action) on right transversal objects.
  State explicitly that the PositionCanonical magic is restricted to the functions ActionHomomorphism and Action.
• Use the PositionCanonical magic also in IsTransitive, IsPrimitive, etc., for right transversal objects.
• Try to get rid of the PositionCanonical magic.
  As a first step, we could introduce and advertise a special new RightCosets object that really is a list of right cosets, and that does not suffer from the inherent inconsistency of RightTransversal objects (in principle, these are lists of group elements, but in some situations, they behave as if they were lists of right cosets). As long as such RightCosets objects are used just in Action, ActionHomomorphism, IsTransitive, etc., there is no performance loss; RightCosets objects become expensive as soon as users start to access their entries, and we can document this.

@james-d-mitchell @hulpke @fingolfin Any thoughts on this?

[hulpke]

I think the PositionCanonical magic is built in so deep and used in so many places that we need to keep it. The extra cost is nil if it defaults to Position. Thus, my inclination would be to go the second path, i.e. modify IsTransitive &c.