Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Computation of Comm() of two free group automorphisms invokes coset enumeration #3898

Open
ignatsoroko opened this issue Feb 15, 2020 · 3 comments · May be fixed by #5906
Open

Computation of Comm() of two free group automorphisms invokes coset enumeration #3898

ignatsoroko opened this issue Feb 15, 2020 · 3 comments · May be fixed by #5906

Comments

@ignatsoroko
Copy link

ignatsoroko commented Feb 15, 2020 •
edited by fingolfin
Loading

Observed behaviour

EDITED to make it easier to copy&paste input for testing

gap> F1:=FreeGroup("x1","x2","x3","x4");'
gap> AssignGeneratorVariables(F1);
gap> A1:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x1,x1*x2^-1*x1,x3,x4]);;
gap> B1:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x2*x1^-1*x2,x2,x3,x4]);;
gap> A2:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x1,x2,x2*x3^-1*x2,x4]);;
gap> B2:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x1,x3*x2^-1*x3,x3,x4]);;
gap> A3:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x1,x2,x3,x3*x4^-1*x3]);;
gap> B3:=GroupHomomorphismByImages(F1,F1,[x1,x2,x3,x4],[x1,x2,x4*x3^-1*x4,x4]);;
gap> Comm((A2*B2)^B1,(A2*B2)^A3);
Error, the coset enumeration has defined more than 4096000 cosets
 at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1229 called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1063 calfrom
CosetTableFromGensAndRels( fgens, grels, fsgens ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1345 called fro
TryCosetTableInWholeGroup( H ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1358 called from
CosetTableInWholeGroup( ImagesSet( iso, U ) ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:5315 called from
oper( super, sub ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/domain.gd:439 called from
...  at *stdin*:90
type 'return;' if you want to continue with a new limit of 8192000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk> quit;
#I  Options stack has been reset

On the other hand, if we denote these automorphisms with variables and compute explicitly the images of the free group generators under the first argument of Comm(), then the Comm() computes correctly. Note that this doesn't work if we just compute the images under the second argument of Comm() only:

gap> q1:=(A2*B2)^B1;
[ x2*x1^-1*x2, x2, x3, x4 ] -> [ x2*x1^-1*x2, x3*x2^-1*x3, (x3*x2^-1)^2*x3, x4 ]
gap> q2:=(A2*B2)^A3;
[ x1, x2, x3, x3*x4^-1*x3 ] -> [ x1, x3*x2^-1*x3, (x3*x2^-1)^2*x3, x3*x4^-1*x3 ]
gap> List([x1,x2,x3,x4],i->i^(q2));
[ x1, x3*x2^-1*x3, (x3*x2^-1)^2*x3, (x3*x2^-1)^2*x4*(x2^-1*x3)^2 ]
gap> Comm(q1,q2);
Error, the coset enumeration has defined more than 4096000 cosets
 at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1229 called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1063 called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1345 called from
TryCosetTableInWholeGroup( H ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:1358 called from
CosetTableInWholeGroup( ImagesSet( iso, U ) ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/grpfp.gi:5315 called from
oper( super, sub ) at /proc/cygdrive/C/gap-4.10.0-x86_64/lib/domain.gd:439 called from
...  at *stdin*:26
type 'return;' if you want to continue with a new limit of 8192000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk> quit;
#I  Options stack has been reset
gap> Comm(q2,q1);
CompositionMapping( CompositionMapping( [ x2*x1^-1*x2, x2, x3, x4 ] -> [ x2*x1^-1*x2, x3*x2^-1*x3, (x3*x2^-1)^2*x3,
  x4 ], [ x1, x2, x3, x3*x4^-1*x3 ] -> [ x1, x3*x2^-1*x3, (x3*x2^-1)^2*x3, x3*x4^-1*x3 ] ),
[ x3*x2^-1*x3*x1^-1*x3*x2^-1*x3, (x3*x2^-1)^3*x3, (x3*x2^-1)^4*x3, (x3*x2^-1)^2*x4*(x2^-1*x3)^2 ] ->
[ x2*x1^-1*x2, x2, x3, x4 ] )
gap> List([x1,x2,x3,x4],i->i^(last));
[ x1, x2, x3, x4 ]

further:

gap> List([x1,x2,x3,x4],i->i^(q1));
[ (x3*x2^-1)^2*x1*(x2^-1*x3)^2, x3*x2^-1*x3, (x3*x2^-1)^2*x3, x4 ]
gap> Comm(q1,q2);
[ (x3*x2^-1)^2*x1*(x2^-1*x3)^2, (x3*x2^-1)^3*x3, (x3*x2^-1)^4*x3, (x3*x2^-1)^2*x3*x4^-1*(x3*x2^-1)^2*x3 ] ->
[ (x3*x2^-1)^2*x1*(x2^-1*x3)^2, (x3*x2^-1)^3*x3, (x3*x2^-1)^4*x3, (x3*x2^-1)^2*x3*x4^-1*(x3*x2^-1)^2*x3 ]
gap> List([x1,x2,x3,x4],i->i^(last));
[ x1, x2, x3, x4 ]

Expected behaviour

[ x1, x2, x3, x4 ] -> [ x1, x2, x3, x4 ]

or

[ (x3*x2^-1)^2*x1*(x2^-1*x3)^2, (x3*x2^-1)^3*x3, (x3*x2^-1)^4*x3, (x3*x2^-1)^2*x3*x4^-1*(x3*x2^-1)^2*x3 ] ->
[ (x3*x2^-1)^2*x1*(x2^-1*x3)^2, (x3*x2^-1)^3*x3, (x3*x2^-1)^4*x3, (x3*x2^-1)^2*x3*x4^-1*(x3*x2^-1)^2*x3 ]

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP 4.10.0 of 01-Nov-2018
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-unknown-cygwin-default64
 Configuration:  gmp 6.1.0, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.1, Alnuth 3.1.0, AtlasRep 1.5.1, AutoDoc 2018.09.20, AutPGrp 1.10, Browse 1.8.8, CRISP 1.4.4,
             Cryst 4.1.18, CrystCat 1.1.8, CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, GAPDoc 1.6.2, IO 4.5.4,
             IRREDSOL 1.4, LAGUNA 3.9.0, Polenta 1.3.8, Polycyclic 2.14, PrimGrp 3.3.2, RadiRoot 2.8,
             ResClasses 4.7.1, SmallGrp 1.3, Sophus 1.24, SpinSym 1.5, TomLib 1.2.7, TransGrp 2.0.4, utils 0.59
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
@fingolfin
Copy link
Member

fingolfin commented Feb 16, 2020 •
edited
Loading

Here is what happen: Let f:=(A2*B2)^B1; g:=(A2*B2)^A3;. Internally, Comm(f,g) by default is implemented as LQUO(g*f,f*g)- and LQUO in turn by default (for groups that don't implement it directly) computes the inverse of the first argument, i.e., (g*f)^-1; and then GAP doesn't "know" this is an injective map, and tries hard (and fails) to prove it.

If one asks for f^-1 * f^g, then this works fine.
Also, if one first asks GAP to compute f^-1; then afterwards, GAP "knows" f is bijective and also its inverse. Asking for Comm(f,g) then suddenly works fine.

Looking closer, part of the issue is that while asking f and g for an inverse, of whether they are injective, works instantly. Why? Well, asking IsInjective(g) dispatches to this method:

InstallMethod( IsInjective,
    "for GHBI",
    true,
    [ IsGroupGeneralMappingByImages ], 0,
    hom -> IsSingleValued( RestrictedInverseGeneralMapping( hom ) ) );

And then we have specialized IsSingleValued methods for free groups, and this works beautifully.

But when we ask for whether g*f is injective, this map is a composite map, so different methods can be (and are!) selected for it. In particular, asking IsInjective(g*f) triggers this method:

InstallMethod( IsInjective,
    "method for a gen. mapping that respects mult. and one",
    [ IsGeneralMapping and RespectsMultiplication and RespectsInverses ],
    map -> IsTrivial( KernelOfMultiplicativeGeneralMapping( map ) ) );

And asking a composite map for its kernel triggers this:

InstallMethod( KernelOfMultiplicativeGeneralMapping,
    "for a composition mapping that resp. mult. and inv.",
    true,
    [ IsGeneralMapping and IsCompositionMappingRep
      and RespectsMultiplication and RespectsInverses ], 0,
    function( com )
    if IsInjective( com!.map2 ) then
      return KernelOfMultiplicativeGeneralMapping( com!.map1 );
    else
      return PreImagesSet( com!.map1,
                 KernelOfMultiplicativeGeneralMapping( com!.map2 ) );
    fi;
    end );

Unfortunately, asking f or g for their kernel results in this:

gap> KernelOfMultiplicativeGeneralMapping(g);
Group(<free, no generators known>)

And then to check IsTrivial for this kernel, GAP tries to determine generators, and that leads to a coset enumeration of the trivial group in a free group, which of course won't work.

There are several ways to tackle this issue, not mutually exclusive. It's not clear to me right now which one(s) we should pursue..

  • we could change the kernel function CommDefault(f,g) from LQUO(PROD(g,f), PROD(f,g)) to LQUO(f, POW(f, g)).

    • pro: would solve this particular issue
    • almost pro: would also be faster for permutations (but those already have a dedicated Comm implementation
    • con: might be less efficient for other cases; might even change other examples from "works instantly" to "does not work because it starts to perform a hopeless coset enumeration"

  • we could provide a dedicated Comm method for group homomorphisms that somehow does something clever (although I don't know what that ought to be)

  • ensure that KernelOfMultiplicativeGeneralMapping returns a trivial group in the above case

  • ensure that IsTrivial works w/o an infinite coset enumeration for the kind of group returned by KernelOfMultiplicativeGeneralMapping

  • there is an IsInjective method for composite maps which first checks if both maps are injective as a special case; but it currently is not ranked high enough. So, we could just increase its rank (and that of its various counterparts) to rank higher, and the issue would go away (but who knows, other issues might pop up? though I don't really expect that to happen)

  • ... probably various more things could be done ...

@hulpke
Copy link
Contributor

hulpke commented Feb 18, 2020

I suspect the right thing will be to have their own method for Comm for homomorphisms, in particular is they are from one group to itself.
The reason is that it is easier to translate properties of f and g to f^-1 and to f^g, than to the products fg and gf.
I suspect the definition LQUO(gf,fg) had pc groups and collection in mind, and tried to split the longer product "in the middle", and to use only one inversion instead of two.

@fingolfin
Copy link
Member

I am not so sure about that explanation for why Comm works the way it does; after all, we have dedicated Comm methods for pc groups. Anyway, it might be that there are multiple things we should change here. Adding a custom Comm method for homomorphisms sounds sensible; but I still think that this IsInjective method for composite maps should be ranked higher so that it gets used here; after all, this would also fix further scenarios in which a coset enumeration is triggered needlessly.

@fingolfin fingolfin linked a pull request Jan 16, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Ensure Comm for group automorphisms does not trigger a coset enumeration gap-system/gap
3 participants
@fingolfin @hulpke @ignatsoroko