PreImagesRepresentative returns error or wrong element when argument is not in image

[stertooy]

According to the documentation, 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."

However, the latter case does not seem to work properly for pc-groups:

gap> G := SmallGroup(2,1);
<pc group of size 2 with 1 generators>
gap> phi := GroupHomomorphismByImages(G,G,[G.1],[One(G)]);
[ f1 ] -> [ <identity> of ... ]
gap> PreImagesRepresentative(phi,G.1);
Error, List Element: <list>[1] must have an assigned value in
  DepthOfPcElement( ParentPcgs( pcgs ), elm ) at /usr/lib/gap/lib/pcgsind.gi:1285 called from
DepthOfPcElement( pa, elm ) at /usr/lib/gap/lib/pcgsind.gi:1353 called from
ExponentsOfPcElement( pcgsR, elm ) at /usr/lib/gap/lib/ghompcgs.gi:518 called from
<function "PreImagesRepresentative method for pcgs hom">( <arguments> )

For symmetric groups, a similar error can happen, or an incorrect preimage may be returned:

gap> S := SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> psi := GroupHomomorphismByImages(S,S,[S.1,S.2],[One(S),S.2]);
[ (1,2,3), (1,2) ] -> [ (), (1,2) ]
gap> PreImagesRepresentative(psi,(1,2,3));
(1,2)
gap> PreImagesRepresentative(psi,(1,3));
Error, List Element: <list>[3] must have an assigned value in
  img := opr( img, S.transimages[bimg[1]] ); at /usr/lib/gap/lib/ghomperm.gi:110 called from
ImageSiftedBaseImage( S, OnTuples( BaseStabChain( S ), elm ), S.idimage, OnRight
 ) at /usr/lib/gap/lib/ghomperm.gi:1015 called from
ImagesRepresentative( RestrictedInverseGeneralMapping( hom ), elm ) at /usr/lib/gap/lib/ghomperm.gi:1108 called from
<function "PreImagesRepresentative method">( <arguments> )

[hulpke]

That should be changed in the documentation (i.e. behavior is undefined if the element is not in the image). Testing for membership would give a very significant performance penalty in many cases where it is clear the image is in. This is not just for PC groups but also in other cases.

(Yes, one could also introduce a NC version, but given how much existing code uses PreImagesRepresentative` I would be very wary of making such a performance hit change.

[stertooy]

For purely selfish reasons, I am a fan of NC/non-NC versions, but I understand the implications of such a change would be drastic.

Just to throw an idea out there, but, rather than testing for membership a priori, perhaps PreImagesRepresentative could be changed to always returns a "preimage" (instead of throwing an error), which may be incorrect if the argument does not lie in the image. One could then compare the image of this "preimage" with the argument, and return fail if they do not match. I may be wrong here, but I would expect that to give a much smaller perfomance penalty?

Also, perhaps worthy of mentioning: the implementation of PreImagesRepresentative in the polycyclic package used to sometimes return id instead of fail when the argument did not lie in the image. This was recently fixed, but this fix seems to have broken the implementation of PreImagesSet, which may have relied on this faulty behaviour of PreImagesRepresentative. But, if this behaviour was not faulty to begin with, perhaps this "fix" should be reverted...

[fingolfin]

It seems to me that there are two separate issues here:

1. Whether we should make any guarantees as to what PreImagesRepresentative(hom, x) should do if not x in Image(hom)
2. Whether if not x in Image(hom) happens we return fail or an error.

I understand the concern by @hulpke regarding performance in point 1. However, in case 2 we trigger an error because x is not Image(hom). So in principle we should be able to instead return fail? I had a look and it involves various tweaking various other functions like DepthOfPcElement and ExponentsOfPcElement (changing them to return fail if they detect that they are in an impossible situation). It seems doable (i.e., I did it locally, to make the first example work), but to do it thoroughly might be more work than we are willing to invest? Yet if we want a useful "NC" variant, we might need it anyway? Hm. Same for the permutation groups case.

Point 1 to me seems to me more concerned with the issue of potentially returning a bogus preimage. And for that, I'd indeed greatly prefer an NC/non-NC split: while for the expert, there should be a sharp and efficient tool, the regular user should not be handed a footgun like that.

Here is the experimental patch I tried. Of course if we were (hypothetically speaking) to move in this direction, a lot more work would be needed: to catch more cases; adding tests; and perhaps the new behaviour of DepthOfPcElement and ExponentsOfPcElement should be explicitly documented (note that I think it's fine to change them from an error to fail, as even buggy code which used to run into an error there very likely will now still error, just a bit later, namely when it tries to treat fail as an exponent vector or depth.

diff --git a/lib/ghompcgs.gi b/lib/ghompcgs.gi
index d2c1acbe5..69b4a1495 100644
--- a/lib/ghompcgs.gi
+++ b/lib/ghompcgs.gi
@@ -142,6 +142,7 @@ InstallMethod( ImagesRepresentative,
 function( hom, elm )
 local exp, img, i,sp;
   exp  := ExponentsOfPcElement( hom!.sourcePcgs, elm );
+  if exp = fail then return fail; fi;
   img  := One( Range( hom ) );
   sp:=PcgsHomSoImPow(hom);
   for i in [1..Length(hom!.sourcePcgsImages)] do
@@ -516,6 +517,7 @@ function( hom, elm )
 
     pcgsR := hom!.rangePcgs;
     exp := ExponentsOfPcElement( pcgsR, elm );
+    if exp = fail then return fail; fi;
     imgs := hom!.rangePcgsPreimages;
     pre := Identity( Source( hom ) );
     for i in [1..Length(exp)] do
@@ -618,6 +620,7 @@ InstallMethod( ImagesRepresentative, FamSourceEqFamElm,
 function( hom, elm )
 local   exp;
   exp := ExponentsOfPcElement( hom!.sourcePcgs, elm );
+  if exp = fail then return fail; fi;
   return PcElementByExponentsNC( hom!.sourcePcgsImages, exp );
 end );
 
@@ -630,6 +633,7 @@ InstallMethod( PreImagesRepresentative, FamRangeEqFamElm,
 function( hom, elm )
 local   exp;
     exp := ExponentsOfPcElement( hom!.rangePcgs, elm );
+    if exp = fail then return fail; fi;
     return PcElementByExponentsNC( hom!.rangePcgsPreImages, exp );
 end );
 
diff --git a/lib/ghomperm.gi b/lib/ghomperm.gi
index 22c0a5713..60e253820 100644
--- a/lib/ghomperm.gi
+++ b/lib/ghomperm.gi
@@ -102,11 +102,12 @@ end );
 #F  ImageSiftedBaseImage( <S>, <bimg>, <h> )   sift base image and find image
 ##
 InstallGlobalFunction( ImageSiftedBaseImage, function( S, bimg, img, opr )
-    local   base;
+    local   base, elm;
     
     base := BaseStabChain( S );
     while bimg <> base  do
         while bimg[ 1 ] <> base[ 1 ]  do
+            if not IsBound( S.transimages[ bimg[ 1 ] ] ) then return fail; fi;
             img  := opr     ( img,  S.transimages[ bimg[ 1 ] ] );
             bimg := OnTuples( bimg, S.transversal[ bimg[ 1 ] ] );
         od;
@@ -1027,6 +1028,8 @@ local   S,img,img2;
       if Length(UnderlyingElement(img2))<Length(UnderlyingElement(img)) then
         return img2;
       fi;
+    elif img = fail then
+      return fail;
     fi;
     return img^-1;
   fi;
diff --git a/lib/pcgsind.gi b/lib/pcgsind.gi
index 483f94dc8..08dd3fd51 100644
--- a/lib/pcgsind.gi
+++ b/lib/pcgsind.gi
@@ -1282,7 +1280,9 @@ InstallMethod( DepthOfPcElement,
     0,
 
 function( pcgs, elm )
-    return pcgs!.depthMapFromParent[DepthOfPcElement(ParentPcgs(pcgs),elm)];
+    local d;
+    d := DepthOfPcElement(ParentPcgs(pcgs),elm);
+    return GetWithDefault( pcgs!.depthMapFromParent, d, fail );
 end );
 
 
@@ -1351,8 +1351,8 @@ function( pcgs, elm )
     ros := RelativeOrders(pa);
     while elm <> id  do
         d := DepthOfPcElement( pa, elm );
-        if not IsBound(map[d])  then
-            Error( "<elm> lies not in group defined by <pcgs>" );
+        if d = fail or not IsBound(map[d])  then
+    	  return fail;
 	elif map[d]>Length(pcgs) then
 	  return exp;
         fi;
@@ -1394,8 +1394,8 @@ function( pcgs, elm,range )
     ros := RelativeOrders(pa);
     while elm <> id  do
         d := DepthOfPcElement( pa, elm );
-	if not IsBound(map[d])  then
-	  Error( "<elm> lies not in group defined by <pcgs>" );
+	if d = fail or not IsBound(map[d])  then
+	  return fail;
 	elif map[d]>max then
 	  # we have reached the maximum of the range we asked for. Thus we
 	  # can stop calculating exponents now, all further exponents would

[hulpke]

The problem in handling case 2 cleanly is where the error is triggered, and how the method knows that that the element is not in the image. If we can fix it in a particular situations without causing other problems, we should do so, but homomorphisms are not always based on a clean membership test. (In fact, even in @fingolfin 's example, there might be a different pcgs underlying, and thus different methods for Pcgs that need to be fixed as well.)

Giving a universal promise of clean bailout (i.e. returning fail) will be an enormous endeavour.
For example

phi: [(1,2,3),(1,2)]->[(1,2,3)(4,5,6),(1,2)(4,5)]

Here the pre-image calculation should simply take the restriction of the permutation given to [1,2,3]. Now lets use it to get the pre-image of (1,2). The calculation method finds (1,2) and no error arises. We would have to map back and compare to actually be certain that the element is validly in the image. (and this is the performance penalty I fear.)

Or I pass it (2,3,4). Now RestrictedPerm needs to return a clean fail value.

More complicated, a matrix group homomorphism might take pre-images by extracting certain matrix entries, and performing arithmetic with them. If the matrix passed to it is not in the image, this arithmetic might fail (or produce a nomn-invertible matrix).

Promising to catch all such situations looks daunting, with very little payoff in terms of functionality.

[stertooy]

If the decision is to leave the functions as they are and updating the documentation instead, the documentation for the functions PreImagesSet and PreImage should be updated as well. As these functions make use of PreImagesRepresentative, they behave similarly if the given collection is not a subset of the image of the given map:

gap> S := SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> psi := GroupHomomorphismByImages(S,S,[S.1,S.2],[One(S),S.2]);
[ (1,2,3), (1,2) ] -> [ (), (1,2) ]
gap> PreImage(phi,Subgroup(S,[(1,2,3)]));
Group([ (1,2,3), (1,2) ])
gap> PreImage(phi,Subgroup(S,[(1,3)]));
Error, List Element: <list>[3] must have an assigned value in [...]

The documentation for PreImagesSet and PreImage currently refers to a subset of the range of the map, rather than the image:

• "Anything may happen if elms is not a subset of the range of map."
• "PreImage( map, coll ) is the preimage of the subset coll of the range of the general mapping map under map, i.e., the subset of the source which is mapped under map to elements of coll."
• "If the second argument is not an element or a subset of the range of the first argument, an error is signalled."

[fingolfin]

@fieker this issue explains some of the trouble we had with the direct product preimages: some of the morphisms will simply error, some return fail, and some lead to wrong behavior down the road...

[fingolfin]

The issue @fieker and me run into (well, or at least one of the issues...) is in the following method (from lib/mapphomo.gi, line 388):

InstallMethod( PreImagesSet,
    "method for injective s.p. mapping respecting mult. & inv., and group",
    CollFamRangeEqFamElms,
    [ IsSPGeneralMapping and IsMapping and IsInjective and
      RespectsMultiplication and RespectsInverses,
      IsGroup ],
    function( map, elms )
    local   pre;

    pre := SubgroupNC( Source( map ),
                    List( GeneratorsOfMagmaWithInverses( elms ),
                          gen -> PreImagesRepresentative( map, gen ) ) );
    UseIsomorphismRelation( elms, pre );
    return pre;
    end );

The problematic bit is the UseIsomorphismRelation: if elems is not a subset of Image(map) then its use here is incorrect, pre will in general just be isomorphic to a subgroup of elms.

[hulpke]

Does this mean we should have two functions, one that works for any situation, and takes the pre-image of Image\cap Set, and another (possibly faster) one that assumes without check that the set is contained in the image? Basically these seekm two different usages that go beyond a "no check".
I certainly don't want to block a more general usage, but within algorithms we need fast means to take pre-image subgroups and transfer information without having to test membership in the image first (or losing information transfer).

[ThomasBreuer]

I had not been aware of this issue, thanks to @fingolfin for making me aware of it.
Just today I observed that there is a problem, and opened issue #4809 to describe it.

The current behaviour is clearly a bug. I noticed the problem by chance when debugging some code outside the GAP library that uses PreImagesRepresentative for checking whether the given element is in the image; that code just trusts the documentation of this function.

In the sense that adjusting the documentation to the implementation would not fix such cases, it would be better to keep the current documentation, to add checks (no matter how expensive they are) to the code, and to provide alternative functions that do not perform checks.