Documentation for IsPrimitive is confusing

[PaulaHaehndel]

Today I have been experimenting with primitve groups in GAP and I am confused by the documentation.
I have copy and pasted the current documentation below.

To me it is not clear what an "xset" is especially as IsPrimitive returns something if it has only a permutation group as input, even though permutations groups are not external sets (for which xset seems to stand).
Therefore I am not sure what GAP does if IsPrimitive is called for a permutation group.

 41.10-7 IsPrimitive

  ‣ IsPrimitive( G, Omega[, gens, acts][, act] ) ─────────────────────────────────────────────────────────── operation
  ‣ IsPrimitive( xset ) ───────────────────────────────────────────────────────────────────────────────────── property

  returns true if the action implied by the arguments is primitive, or false otherwise.

  An action is primitive if it is transitive and the action admits no nontrivial block systems. See 41.11.

  ────────────────────────────────────────────────────  Example  ─────────────────────────────────────────────────────
    gap> IsPrimitive(g,Orbit(g,(1,2)(3,4)));
    true

And related I assumed that if IsPrimitive returns an output for some input also Block should return something for the same input. But it doesn't for the below example. (And I'm aware that the definition for primitive matrix group is different from the definiton of primitive permutation groups. Perhaps this should be written in the documentation too?)

gap> IsPrimitive(GL(2,5),GF(5)^2);
false
gap> Blocks(GL(2,5),GF(5)^2);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `BlocksOp' on 5 arguments at /mnt/c/gap-4.10.0/lib/methsel2.g:250 called from
orbish( G, pnt, gens, acts, act ) at /mnt/c/gap-4.10.0/lib/oprt.gd:863 called from
<function "Blocks">( <arguments> )
 called from read-eval loop at *stdin*:20
type 'quit;' to quit to outer loop

[fingolfin]

Hi @PaulaHaehndel xset is short for ExternalOrbitExternalSet; hm, I see that there is no index entry for xset, we definitely should add one, so that ?xset points to ExternalOrbitExternalSet.

That said, it actually is a red herring here: You are not calling IsPrimitive with a single argument, so the relevant entry of the manual is the first one: you are specifying a group G and a domain Omega. For an explanation of what those mean, please read the intro section of Chapter 41: Group Actions. To be honest, I can't think of a good way to make this clearer other than to insert a phrase similar to the following everywhere:

For an explanation of the meaning of these inputs, please refer to the introduction of this chapter

As to your second question: That looks to me like a bug (or unimplemented feature, depending on how one wants to call this) in Blocks. I guess we should indeed either add a generic fallback method for it; or else document that only permutation groups are supported (and then install a fallback method which prints a more helpful error message if something else is used as input).

[wilfwilson]

Thanks @fingolfin. I was talking to @PaulaHaehndel about this on Wednesday – I don't think that the xset thing is a complete red herring. It's true that the code included at the bottom of the issue uses the two-argument version. But what she meant here...

To me it is not clear what an "xset" is especially as IsPrimitive returns something if it has only a permutation group as input, even though permutations groups are not external sets

...is that she was confused by the following:

gap> IsPrimitive(SymmetricGroup(4));
true
gap> IsExternalSet(SymmetricGroup(4));
false

Using the single argument IsPrimitive with the symmetric group gives an answer, even though it doesn't seem to be an external set, which the line IsPrimitive( xset ) implies is required in the 1-argument version. Therefore, the fact that this worked at all in this case seems to be undocumented behaviour (even though it is, admittedly, the answer that you would hope to get). And, since it seems to be undocumented behaviour, a user can't have complete trust in what it is doing.

In other words, it's at least not totally clearly documented under IsPrimitive that, for a single argument that is a permutation group G, IsPrimitive assumes the action to be that of G on MovedPoints(G) via OnPoints. This holds for other pieces of documentation in the chapter (Transitivity, RankAction...).

In fact, now, I have just gone to look at the documentation for IsTransitive, and I see that it avoids this issue:

  41.10-1 IsTransitive

  ‣ IsTransitive( G, Omega[, gens, acts][, act] ) ────────────────── operation
  ‣ IsTransitive( G ) ─────────────────────────────────────────────── property
  ‣ IsTransitive( xset ) ──────────────────────────────────────────── property

  returns  true if the action implied by the arguments is transitive, or false
  otherwise.

  We  say  that  a  group G acts transitively on a domain D if and only if for
  every pair of points d, e ∈ D there is an element g in G such that d^g = e.

  For  permutation  groups,  the  syntax IsTransitive(G) is also permitted and
  tests whether the group is transitive on the points moved by it, that is the
  group ⟨ (2,3,4),(2,3) ⟩ is transitive (on 3 points).

I think we should include a similar line for IsPrimitive (and anywhere else that seems relevant); I believe that would solve @PaulaHaehndel's first question. I also agree that some text like...

For an explanation of the meaning of these inputs, please refer to the introduction of this chapter

...in these pieces of documentation would also be useful.

Perhaps this is something that @PaulaHaehndel might like to help with at GAP Days 🙂

[fingolfin]

@wilfwilson OK, it was not clear to me from reading this issue that IsPrimitive(GROUP) was involved.

This report seems to describe at least three separate issues. Might I suggest that in the future, you file one separate report for each separate issue? This both simplifies tracking the status of them for us, and also ensures we won't miss any of the multiple issues.

[fingolfin]

As to the issue: this is, depending on view point, either another oversight in the documentation, or a bug (misfeature). The immediate cause why IsPrimitive works if only a permutation group is given as input is this code from OrbitsishOperation (which is used to declare IsPrimitive and many other orbit based operations):

    # 2. `op( <permgrp> )'
    InstallOtherMethod( op,
        "for a permutation group",
        true,
        [ IsPermGroup ], 0,
        function( G )
        local gens;
        gens:= GeneratorsOfGroup( G );
        return op( G, MovedPoints( G ), gens, gens, OnPoints );
        end );

As it turns out, the signature IsPrimitive( G, Omega[, gens, acts][, act] ) really should be IsPrimitive( G[, Omega[, gens, acts][, act]] ) which of course is somewhat confusing, so yeah, adding a separate row for just a single input would be better. But this really affects all operations declared via OrbitsishOperation

[wilfwilson]

Thanks for looking into it. If you call IsPrimitive(<permgroup>), then the true/false answer is stored for the group:

gap> G := Group((1,2,3,4));;
gap> HasIsPrimitive(G);
false
gap> IsPrimitive(G);
false
gap> HasIsPrimitive(G);
true

Therefore I would have thought it was a property (sorry, I haven't looked at the code properly), so it feels right that it should be documented separately from the IsPrimitive( G, Omega[, gens, acts][, act] ) thing, which is documented as an operation.

[PaulaHaehndel]

The documentation actually says that the action for that Blocks is used has to be transitive. So the documentation indicates that
gap> Blocks(GL(2,5),GF(5)^2);
should not be used.