StructureDescription(G:nice) breaks if group has different presentations because cannot compute centralizer in a group given by a matrix #973

hungaborhorvath · 2016-12-04T08:54:21Z

This affects current master.

Update2: The problems is really about GAP not being able to calculate a particular centralizer in a matrix group. See my third post below.

Update: The problem is really about adding list of groups to a set, and determining if a new list of groups is equal to any one of them in the set. See the comment below.

This was the original bug:
Somehow StructureDescription(G:nice) seems to break depending on the presentation of the group. Here are two particular groups with this problem:

 ┌───────┐   GAP v4.8.6-922-g46c3e87 of 2016-12-02 22:34:53 (CET)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 3.0, small* 1.0, id* 1.0
 Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.1, AutPGrp 1.6, 
             Browse 1.8.6, CRISP 1.4.4, Cryst 4.1.12, CrystCat 1.1.6, 
             CTblLib 1.2.2, FactInt 1.5.3, FGA 1.3.1, GAPDoc 1.5.1, IO 4.4.6, 
             IRREDSOL 1.3.1, LAGUNA 3.7.0, Polenta 1.3.7, Polycyclic 2.11, 
             RadiRoot 2.7, ResClasses 4.5.0, Sophus 1.23, SpinSym 1.5, 
             TomLib 1.2.6, Utils 0.43
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> testG :=
>    function ( a, b )
>      local  M1;
>       M1 := [ [ [      0, -E(a)^-1 ], [ -E(a),       0 ] ],
>               [ [      0,       -1 ], [     1,       0 ] ],
>               [ [ E(4*b),        0 ], [     0, -E(4*b) ] ],
>               [ [     -1,        0 ], [     0,      -1 ] ]];
>       return (Group(M1));
>    end;;
gap> IdGroup(testG(8,2));
[ 64, 124 ]
gap> StructureDescription(SmallGroup(64,124):nice);
"(C8 x C4) : C2"
gap> StructureDescription(testG(8,2):nice);
Error, AppendList: <list2> must be a small list (not a boolean or fail) in
  Append( resrow, Coefficients( B, entry * b ) ); at /home/ghorvath/work/gap/lib/matrix.gi:3082 called from 
BlownUpMat( Basis( iso ), mat ) at /home/ghorvath/work/gap/lib/grpmat.gi:993 called from
ImagesRepresentative( nice, elm ) at /home/ghorvath/work/gap/lib/grpnice.gi:224 called from
gen in H at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
func( elm ) at /home/ghorvath/work/gap/lib/coll.gi:1613 called from
ForAll( GeneratorsOfGroup( G ), function ( gen )
      return gen in H;
  end ) at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
...  at *stdin*:12
you can replace <list2> via 'return <list2>;'
brk>

 ┌───────┐   GAP v4.8.6-922-g46c3e87 of 2016-12-02 22:34:53 (CET)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 3.0, small* 1.0, id* 1.0
 Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.1, AutPGrp 1.6, 
             Browse 1.8.6, CRISP 1.4.4, Cryst 4.1.12, CrystCat 1.1.6, 
             CTblLib 1.2.2, FactInt 1.5.3, FGA 1.3.1, GAPDoc 1.5.1, IO 4.4.6, 
             IRREDSOL 1.3.1, LAGUNA 3.7.0, Polenta 1.3.7, Polycyclic 2.11, 
             RadiRoot 2.7, ResClasses 4.5.0, Sophus 1.23, SpinSym 1.5, 
             TomLib 1.2.6, Utils 0.43
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> testG :=
>    function ( a, b )
>      local  M1;
>       M1 := [ [ [      0, -E(a)^-1 ], [ -E(a),       0 ] ],
>               [ [      0,       -1 ], [     1,       0 ] ],
>               [ [ E(4*b),        0 ], [     0, -E(4*b) ] ],
>               [ [     -1,        0 ], [     0,      -1 ] ]];
>       return (Group(M1));
>    end;;
gap> IdGroup(testG(8,4));
[ 128, 902 ]
gap> StructureDescription(SmallGroup(128,902):nice);
"(C16 x C4) : C2"
gap> StructureDescription(testG(8,4):nice);
Error, AppendList: <list2> must be a small list (not a boolean or fail) in
  Append( resrow, Coefficients( B, entry * b ) ); at /home/ghorvath/work/gap/lib/matrix.gi:3082 called from 
BlownUpMat( Basis( iso ), mat ) at /home/ghorvath/work/gap/lib/grpmat.gi:993 called from
ImagesRepresentative( nice, elm ) at /home/ghorvath/work/gap/lib/grpnice.gi:224 called from
gen in H at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
func( elm ) at /home/ghorvath/work/gap/lib/coll.gi:1613 called from
ForAll( GeneratorsOfGroup( G ), function ( gen )
      return gen in H;
  end ) at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
...  at *stdin*:12
you can replace <list2> via 'return <list2>;'
brk>

I am trying to debug this. It looks to me that nice monomorphisms are involved here, and I have no idea about them (browsing the manual just now), so any help would be appreciated. Thanks.

The text was updated successfully, but these errors were encountered:

hungaborhorvath · 2016-12-04T09:42:20Z

Ok, I figured out the main problem, but I do not know how to resolve it.

GAP computes the normal subgroups, then for each normal subgroup N it computes its list of complements H, and then adds [N, H[i]] to the set NHs. Now, the problem is that at some point GAP cannot decide where to put the new element in this set.

gap> testG :=
>    function ( a, b )
>      local  M1;
>       M1 := [ [ [      0, -E(a)^-1 ], [ -E(a),       0 ] ],
>               [ [      0,       -1 ], [     1,       0 ] ],
>               [ [ E(4*b),        0 ], [     0, -E(4*b) ] ],
>               [ [     -1,        0 ], [     0,      -1 ] ]];
>       return (Group(M1));
>    end;;
gap> G := testG(8,2);;
gap> Ns := NormalSubgroups(G);;
gap> NHs := [];;
gap> for j in [1..6] do 
> N := Ns[j];; 
> H := ComplementClassesRepresentatives(G, N);;
> if Length(H)>0 then for i in [1..Length(H)] do 
> AddSet(NHs, [N, H[i]]);
> od; fi;
> od;
gap> N := Ns[7];; 
gap> H := ComplementClassesRepresentatives(G, N);;
gap> Length(H);
2
gap> AddSet(NHs, [N, H[1]]);
gap> AddSet(NHs, [N, H[2]]);
Error, AppendList: <list2> must be a small list (not a boolean or fail) in
  Append( resrow, Coefficients( B, entry * b ) 
 ); at /home/ghorvath/work/gap/lib/matrix.gi:3082 called from 
BlownUpMat( Basis( iso ), mat 
 ) at /home/ghorvath/work/gap/lib/grpmat.gi:993 called from
ImagesRepresentative( nice, elm 
 ) at /home/ghorvath/work/gap/lib/grpnice.gi:224 called from
gen in H at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
func( elm ) at /home/ghorvath/work/gap/lib/coll.gi:1613 called from
ForAll( GeneratorsOfGroup( G ), function ( gen )
      return gen in H;
  end ) at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
...  at *stdin*:28
you can replace <list2> via 'return <list2>;'
brk>

In particular, after going out from the break loop, this is what I find:

gap> NHs[1]=[N, H[2]];
false
gap> NHs[2]=[N, H[2]];
false
gap> NHs[3]=[N, H[2]];
false
gap> NHs[4]=[N, H[2]];
Error, AppendList: <list2> must be a small list (not a boolean or fail) in
  Append( resrow, Coefficients( B, entry * b ) 
 ); at /home/ghorvath/work/gap/lib/matrix.gi:3082 called from 
BlownUpMat( Basis( iso ), mat 
 ) at /home/ghorvath/work/gap/lib/grpmat.gi:993 called from
ImagesRepresentative( nice, elm 
 ) at /home/ghorvath/work/gap/lib/grpnice.gi:224 called from
gen in H at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
func( elm ) at /home/ghorvath/work/gap/lib/coll.gi:1613 called from
ForAll( GeneratorsOfGroup( G ), function ( gen )
      return gen in H;
  end ) at /home/ghorvath/work/gap/lib/grp.gi:3242 called from
...  at *stdin*:52
you can replace <list2> via 'return <list2>;'
brk>

The strange thing is that the other way around GAP has no problem determining that the two are different:

gap> [N, H[2]]=NHs[4];
false

I have no idea how to resolve this.

hulpke · 2016-12-04T16:46:33Z

What is happening is that the nice monomorphism for a subgroup (defined over a smaller field) -- the `nice' in the example -- does not test fully whether an element of the whole group is in its domain.

The reason behind this problem is the use of a set of subgroups in the code -- unless groups are permutation group (and thus naturally subsets of one larger group) the implementation of the < order will not work for groups with different nice monomorphisms. (In general, sorting groups is a potentially expensive operation and I would not use it simply to eliminate duplicates.)

As an aside: Does this output of structure description really help a user? I think it would be far more helpful (if it really is intended to call StructureDescription for groups of order 64) to give a description of the semidirect action, e.g. a presentation based on the decomposition:

 <a,b,c|a8,b4,a^c=A,b^c=B>

This of course will not work for all groups either and not scale well.

olexandr-konovalov · 2016-12-04T18:35:04Z

In case it may be useful to know where this test comes from: this is the test for the bug reported by Nilo de Roock (http://mail.gap-system.org/pipermail/forum/2006/001338.html ) and fixed by @Stefan-Kohl on 14 Feb 2006. Description of the fix:

"For certain matrix groups, the function StructureDescription raised an error message. The reason for this was that a trivial method for IsGeneralLinearGroup for matrix groups in lib/grpmat.gi which is ranked higher than the nontrivial method for generic groups in lib/grpnames.gi called the operation IsNaturalGL, for which currently no nontrivial method is available."

So the test was not checking for a specific structure description for the group, but was in fact checking that it works without an error (unrelated to StructureDescription). There were practical suggestions to convert the group to permutation or pc presentation first and apply StructureDescription after that. Perhaps the test can be simplified somehow to don't run extra calculations.

hungaborhorvath · 2016-12-04T19:30:39Z

@alex-konovalov Thank you. Well, it helps knowing how these groups arise, but this is still an error. For such groups StructureDescription(G:nice) should still work.

@hulpke Thank you, what you say about sets is indeed problematic. For now I have replaced all of my AddSet with the following command:

InstallGlobalFunction( AddSetIfCanEasilySortElements,

  function( list, obj )

    if CanEasilySortElements( list ) and IsSet( list ) then
      AddSet( list, obj );
    else
      Add( list, obj );
    fi;
  end);

However, there still seems to be some other glitch, because the error still occurs. (In fact, it even occurs if I only use Add everywhere....) I will need to investigate it more.

About good descriptions: it has been already challenged (e.g. in #160) that for p-groups this may not be a usable description. I do not mind opening an issue about discussing how StructureDescription should look like in the future. I remember trying to send a message about this to the forum, but I must have messed something up, because nobody replied, and then I completely forgot about it.

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973 Impies subsequent fix in test file

hungaborhorvath · 2016-12-04T21:17:58Z

Ok, I think I have found the culprit. GAP cannot compute the centralizer of a subgroup in another one for this example:

 ┌───────┐   GAP v4.8.6-922-g46c3e87 of 2016-12-02 22:34:53 (CET)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 3.0, small* 1.0, id* 1.0
 Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.1, AutPGrp 1.6, 
             Browse 1.8.6, CRISP 1.4.4, Cryst 4.1.12, CrystCat 1.1.6, 
             CTblLib 1.2.2, FactInt 1.5.3, FGA 1.3.1, GAPDoc 1.5.1, IO 4.4.6, 
             IRREDSOL 1.3.1, LAGUNA 3.7.0, Polenta 1.3.7, Polycyclic 2.11, 
             RadiRoot 2.7, ResClasses 4.5.0, Sophus 1.23, SpinSym 1.5, 
             TomLib 1.2.6, Utils 0.43
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> testG :=
>    function ( a, b )
>      local  M1;
>       M1 := [ [ [      0, -E(a)^-1 ], [ -E(a),       0 ] ],
>               [ [      0,       -1 ], [     1,       0 ] ],
>               [ [ E(4*b),        0 ], [     0, -E(4*b) ] ],
>               [ [     -1,        0 ], [     0,      -1 ] ]];
>       return (Group(M1));
>    end;;
gap> G := testG(8,2);
Group([ [ [ 0, E(8)^3 ], [ -E(8), 0 ] ], [ [ 0, -1 ], [ 1, 0 ] ], 
  [ [ E(8), 0 ], [ 0, -E(8) ] ], [ [ -1, 0 ], [ 0, -1 ] ] ])
gap> N := NormalSubgroups(G)[7];
Group([ [ [ E(8), 0 ], [ 0, -E(8) ] ], [ [ E(4), 0 ], [ 0, E(4) ] ], 
  [ [ E(8)^3, 0 ], [ 0, E(8) ] ], [ [ -E(4), 0 ], [ 0, E(4) ] ], 
  [ [ -1, 0 ], [ 0, -1 ] ] ])
gap> H := ComplementClassesRepresentatives(G, N)[2];
Group([ [ [ 0, -E(4) ], [ E(4), 0 ] ] ])
gap> Centralizer(H, N);
Error, AppendList: <list2> must be a small list (not a boolean or fail) in
  Append( resrow, Coefficients( B, entry * b ) 
 ); at /home/ghorvath/work/gap/lib/matrix.gi:3082 called from 
BlownUpMat( Basis( iso ), mat 
 ) at /home/ghorvath/work/gap/lib/grpmat.gi:993 called from
ImagesRepresentative( nice, elm 
 ) at /home/ghorvath/work/gap/lib/grpnice.gi:224 called from
gen in G at /home/ghorvath/work/gap/lib/grp.gi:3303 called from
func( elm ) at /home/ghorvath/work/gap/lib/coll.gi:1613 called from
ForAll( GeneratorsOfGroup( H ), function ( gen )
      return gen in G;
  end ) at /home/ghorvath/work/gap/lib/grp.gi:3303 called from
...  at *stdin*:13
you can replace <list2> via 'return <list2>;'
brk>

Is this intended behaviour or a bug? (Note that I updated the title once again to reflect this.)

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973 Impies subsequent fix in test file Instead of testing for the explict structure (which might be x or :), test whether the Struct.Desc. command runs thorugh.

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973 Implies subsequent fix in test file -- do not test for explicit string value of `StructureDescription` (which can change) but only whether the function succeeds (which is after all what this test was supposed to do).

…ethod selection. Also nice method for Struct.Desc. This fixes gap-system#973 Implies subsequent fix in test file -- do not test for explicit string value of `StructureDescription` (which can change) but only whether the function succeeds (which is after all what this test was supposed to do).

This splits the current general StructureDescription code for an abelian for a finite and for a finite simple method, with redispatches. Further, it adds nice monomorphism in the proper way (into grpnice.gi), while removes it from grpnames.gi. Corrects problematic tests, and fixes the StructureDescription part of #973. Added some more tests to increase the code coverage of grpnames.gi. Now most lines are covered for StructureDescription, DirectFactors and SemidirectDecompositions. Manual entries are cleaned up in these three functions and in some of the functions they use in grpnames.gd (for easier future documentation).

hungaborhorvath · 2017-01-06T14:43:30Z

Fixed by #985

hungaborhorvath changed the title ~~StructureDescription(G:nice) breaks if group has different presentations~~ StructureDescription(G:nice) breaks if group has different presentations because cannot decide if list of subgroups is already in a set Dec 4, 2016

hungaborhorvath mentioned this issue Dec 4, 2016

Add more examples into the manual for StructureDescription #969

Merged

hulpke added a commit to hulpke/gap that referenced this issue Dec 4, 2016

FIX: Ensure finiteness test in defalut method for Struct.Desc. does n…

44ca2d7

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973

hulpke added a commit to hulpke/gap that referenced this issue Dec 4, 2016

FIX: Ensure finiteness test in defalut method for Struct.Desc. does n…

8a723f6

…ot avoid method selection. Also nice method for Struct.Desc. This fixes gap-system#973 Impies subsequent fix in test file

hungaborhorvath mentioned this issue Dec 4, 2016

Performance improvements and Corrections (in code used by group automorphisms) #968

Merged

This was referenced Dec 5, 2016

StructureDescriptions fix #985

Merged

Cannot compute centralizers in matrix group #988

Open

hungaborhorvath closed this as completed Jan 6, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

StructureDescription(G:nice) breaks if group has different presentations because cannot compute centralizer in a group given by a matrix #973

StructureDescription(G:nice) breaks if group has different presentations because cannot compute centralizer in a group given by a matrix #973

hungaborhorvath commented Dec 4, 2016 •

edited

Loading

hungaborhorvath commented Dec 4, 2016

hulpke commented Dec 4, 2016

olexandr-konovalov commented Dec 4, 2016

hungaborhorvath commented Dec 4, 2016

hungaborhorvath commented Dec 4, 2016

hungaborhorvath commented Jan 6, 2017

StructureDescription(G:nice) breaks if group has different presentations because cannot compute centralizer in a group given by a matrix #973

StructureDescription(G:nice) breaks if group has different presentations because cannot compute centralizer in a group given by a matrix #973

Comments

hungaborhorvath commented Dec 4, 2016 • edited Loading

hungaborhorvath commented Dec 4, 2016

hulpke commented Dec 4, 2016

olexandr-konovalov commented Dec 4, 2016

hungaborhorvath commented Dec 4, 2016

hungaborhorvath commented Dec 4, 2016

hungaborhorvath commented Jan 6, 2017

hungaborhorvath commented Dec 4, 2016 •

edited

Loading