problem with PreImagesRepresentative

[ThomasBreuer]

The following happens in GAP 4.11 as well as in the current master branch.

gap> G:= SymmetricGroup( 4 );;  H:= SylowSubgroup( G, 2 );;
gap> gens:= GeneratorsOfGroup( H );;
gap> f:= GroupHomomorphismByImages( H, G, gens, gens );;
gap> x:= (1,2,3,4);;
gap> x in Range( f );
true
gap> x in Image( f );
false
gap> PreImagesRepresentative( f, x );
(1,2)(3,4)
gap> y:= (1,2,3);;
gap> y in Range( f );
true
gap> y in Image( f );
false
gap> PreImagesRepresentative( f, y );
Error, List Element: <list>[2] must have an assigned value in
  img := opr( img, S.transimages[bimg[1]] )
[...]

The documentation of PreImagesRepresentative says:

‣ PreImagesRepresentative( map, elm ) ──────────────────────────── operation

If elm is an element of the range of the general mapping map then
PreImagesRepresentative returns either a representative of the set of
preimages of elm under map or fail, the latter if and only if elm has no
preimages under map.

Anything may happen if elm is not an element of the range of map.

Thus I want to get fail for each of the inputs PreImagesRepresentative( f, x ), PreImagesRepresentative( f, y ).

[fingolfin]

See also #4088

[fingolfin]

Also perhaps vaguely relevant, at least on a long-term scaler: #574

[hulpke]

I understand where the request comes from, but simply enforcing a membership test is going to slow a lot of calculations down. Can we

1. Create a NC version first
2. Go through the library and packages and see that they use the NC version whenever possible
3. Only then change the current version to enforce tests.

The same issuemight hold in some cases for ImagesRepresentative

[ThomasBreuer]

@hulpke Thanks.

I understand your step 1 as follows: Copy the existing methods for PreImagesRepresentative, install them for a new operation PreImagesRepresentativeNC, and document this new operation such that the second argument is assumed to be an element in the image of the first argument.

Concerning step 2, I think that the only places where one cannot replace PreImagesRepresentative calls by calls of PreImagesRepresentativeNC are those where the return value gets compared with fail. Any piece of code that does not check the result for fail but admits a group element outside the image of the map contains a bug.

Step 3 then means to add checks to all PreImagesRepresentative methods, or to replace each old method by a check followed by a call of PreImagesRepresentativeNC.

Is this what you want to propose?

[hulpke]

@ThomasBreuer

Basically yes. There is no harm if a method already does a test and returns fail -- such a method can be installed for both operations.

Step 3 then means to add checks to all PreImagesRepresentative methods, or to replace each old method by a check followed by a call of PreImagesRepresentativeNC.

One could start by installing a single method for PreImagesRepresentative that tests and then calls PreImagesRepresentativeNC and then fill in more specific methods where the test can be done cheaper (say as part of mapping), or only once for composition mappings.

What do we do with PreImagesElm, PreImagesSet and PreImage?

[cdwensley]

It seems that this is an issue I could have a go at: fairly tedious, but not particularly tricky.
The following steps appear to be required:
(1) Convert PreImagesRepresentative to PreImagesRepresentativeNC throughout the library and tests and introduce a new PreImagesRepresentative which just calls PreImagesRepresentativeNC. Include this first step in 4.12.1.
(2) Once 4.12.1 is out, arrange for packages to use PreImagesRepresentativeNC.
(3) Then change the new PreImagesRepresentative method to test for validity.
Any objections to my attempting this?

[cdwensley]

Just as we have an error in the example above:
gap> PreImagesRepresentative( f, x );
(1,2)(3,4)
so a similar error occurs with PreImages:
gap> PreImages(f,x);
RightCoset(Group(()),(1,2)(3,4))

[ThomasBreuer]

@cdwensley Yes, PreImages (and also PreImagesElm, PreImagesSet) have the same problem. When we decide to change the documentation of PreImagesRepresentative then also the documentation of these functions has to be adjusted, and if we change the behaviour of PreImagesRepresentative then also the behaviour of these functions changes.

[cdwensley]

PR #5073 attempts to address this issue, and has been sitting awaiting a review for some weeks while so much else has been happening (GAPDays, 4.12.1, etc.). But who would want the hassle of reviewing a PR with 77 files changed?

[fingolfin]

Maybe this issue is something we can work on during the upcoming GAP days (I don't know if either @ThomasBreuer or @cdwensley plan to come, but we could also work on it without you, or with you connected

[cdwensley]

Earlier in this issue @hulpke suggested that the same concerns might apply to ImagesRepresentative (and Images, ImagesElm, ImagesSet). If it was thought worthwhile, I'd be willing to start a new PR for GAP and for the various packages listed in PR#5073. Then this could also be worked on at the GAP days in March. Any comment on this @fingolfin ?