Hall Subgroup cannot be computed for fitting free group?

[hungaborhorvath]

Hall subgroup computation breaks for the following fitting free group.

gap> G := tpg[18]; 
Group([ (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)(13,14)(15,16)(17,18)(19,20)(21,22)
(23,24)(25,26)(27,28)(29,30), (2,3)(5,6)(8,9)(11,12)(14,15)(17,18)(20,21)
(23,24)(26,27)(29,30), (1,5)(6,10)(11,15)(16,20)(21,25)(26,30) ])
gap> TraceMethods(HallSubgroupOp); 
gap> PrimeDivisors(Size(G));
[ 2, 3, 5, 7 ]
gap> HallSubgroup(G, [5,7]);
#I  HallSubgroupOp: test trivial cases at /home/ghorvath/work/gap/lib/grp.gi:
2718
#I  trying next: HallSubgroupOp: fitting free
#I  HallSubgroupOp: test trivial cases at /home/ghorvath/work/gap/lib/grp.gi:
2718
#I  HallSubgroupOp: test trivial cases at /home/ghorvath/work/gap/lib/grp.gi:
2718
Error, Record: '<rec>.cocycleToList' must have an assigned value in
  N := ocr.cocycleToList( R ); at /home/ghorvath/work/gap/lib/onecohom.gi:1315 called from 
OCOneCocycles( ocr, true 
 ); at /home/ghorvath/work/gap/lib/fitfree.gi:1207 called from
HallsFittingFree( Image( hom ), pi 
 ) at /home/ghorvath/work/gap/lib/fitfree.gi:1278 called from
HallViaRadical( G, pi 
 ) at /home/ghorvath/work/gap/lib/fitfree.gi:1348 called from
<compiled or corrupted statement>  called from
<function "local function">( <arguments> )
 called from read-eval loop at line 5 of *stdin*
you can 'return;' after assigning a value
brk> 

Also, while we are at it, is there a function that can tell me if there will be a "no method found" error for some function and argument? Background: I want to call HallSubgroup for StructureDescription in the semidirect decomposition phase, because whenever a normal Hall subgroup exists, then (by Schur-Zassenhaus) there is automatically a complement to it, and this would speed up StructureDescription immensely. However, for some groups HallSubgroup will exit with "No method found", and for such cases I want it to fall back for the brute force complement search for every normal subgroup. How can I recognize such a situation in a graceful manner? Thank you.

[hulpke]

This is as far as I can see a duplicate of #404 and thus has been fixed in development code.

You could use ApplicableMethod to find out whether a method exists at all, but typically NoMethodFound errors arise in code called by the first function and that is something one cannot catch.

If a permutation group is finite (and does not have enormous nonabelian composition factors) HallSubgroup should work (though it might be slow). If you have any group for which it fails please send me this group and I will fix the bug.

Concerning normal Hall subgroups, I would recommend start by computing the normal closures of Sylow subgroups and then forming unions of those closures as appropriate (which also reduces on prime sets). This will be much faster than determining Hall subgroups and testing them for normality. (For groups that are not solvable, HallSubgroup is an expensive operation.)

[hungaborhorvath]

@hulpke Ugh, sorry, I forgot that I have already reported this and even forgot to merge the main master branch to my working branch. :-(

I had another (much smaller) example, but now that works, as well.

Thanks for the advice, I will probably try both methods and test them, but indeed your version sounds the faster one. I am closing this issue now.

[hungaborhorvath]

@hulpke you asked for examples where Hallsubgroup fails. "PSL(3, 2) : C2" is such an example:

gap>  HallSubgroup(SmallGroup(336, 208), [2,3]);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `ForAllOp' on 2 arguments called from
ForAllOp( C, func ) at /home/ghorvath/work/gap/lib/coll.gi:1618 called from
ForAll( cgens, function ( x )
      return Order( x ) = 1;
  end ) at /home/ghorvath/work/gap/lib/fitfree.gi:1186 called from
HallsFittingFree( Image( hom ), pi 
 ) at /home/ghorvath/work/gap/lib/fitfree.gi:1278 called from
HallViaRadical( G, pi 
 ) at /home/ghorvath/work/gap/lib/fitfree.gi:1348 called from
<compiled or corrupted statement>  called from
...  at line 1 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

[hungaborhorvath]

Another strange group is the following. I have no idea what TableOfMarksLibrary is, but I only have CRISP installed apart from the obligatory GAPDoc.....

gap> G := tpg[85]; 
Group([ (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)(13,14)(15,16)(17,18)(19,20)(21,22)
(23,24)(25,26)(27,28)(29,30), (1,3)(4,6)(7,9)(10,12)(13,15)(16,18)(19,21)
(22,24)(25,27)(28,30), (1,5)(6,10)(11,15)(16,20)(21,25)(26,30) ])
gap> PrimeDivisors(Size(G));
[ 2, 3, 5, 7, 11, 13 ]
gap> HallSubgroup(G, [ 3, 5, 7, 11, 13 ]);
Error, sorry, the GAP Tables Of Marks Library is not installed called from
TableOfMarksFromLibrary( str 
 ) at /home/ghorvath/work/gap/lib/tom.gi:942 called from
TableOfMarks( nam ) at /home/ghorvath/work/gap/lib/grplatt.gi:2739 called from
TomDataAlmostSimpleRecognition( G 
 ) at /home/ghorvath/work/gap/lib/grplatt.gi:2773 called from
TomDataMaxesAlmostSimple( G 
 ) at /home/ghorvath/work/gap/lib/maxsub.gi:527 called from
MaxesAlmostSimple( ImagesSource( act[2] ) 
 ) at /home/ghorvath/work/gap/lib/maxsub.gi:824 called from
...  at line 4 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

[hulpke]

Thank you — This is the case that already from the factor no Hall subgroup is possible. I will fix this.

Alexander

On Dec 22, 2015, at 9:08 AM, hungaborhorvath notifications@github.com wrote:

@hulpke you asked for examples where Hallsubgroup fails. "PSL(3, 2) : C2" is such an example:

gap> HallSubgroup(SmallGroup(336, 208), [2,3]); Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `ForAllOp' on 2 arguments called from ForAllOp( C, func ) at /home/ghorvath/work/gap/lib/coll.gi:1618 called from ForAll( cgens, function ( x ) return Order( x ) = 1; end ) at /home/ghorvath/work/gap/lib/fitfree.gi:1186 called from HallsFittingFree( Image( hom ), pi ) at /home/ghorvath/work/gap/lib/fitfree.gi:1278 called from HallViaRadical( G, pi ) at /home/ghorvath/work/gap/lib/fitfree.gi:1348 called from

called from ... at line 1 of _stdin_ you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> — Reply to this email directly or view it on GitHub.

[hulpke]

Ah — I did not realize that it is possible to install GAP without the table of marks library (which provides subgroup lattice data). I will put a catch to this in.

Alexander

On Dec 22, 2015, at 9:31 AM, hungaborhorvath notifications@github.com wrote:

Another strange group is the following. I have no idea what TableOfMarksLibrary is, but I only have CRISP installed apart from the obligatory GAPDoc.....

gap> G := tpg[85]; Group([ (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)(13,14)(15,16)(17,18)(19,20)(21,22) (23,24)(25,26)(27,28)(29,30), (1,3)(4,6)(7,9)(10,12)(13,15)(16,18)(19,21) (22,24)(25,27)(28,30), (1,5)(6,10)(11,15)(16,20)(21,25)(26,30) ]) gap> PrimeDivisors(Size(G)); [ 2, 3, 5, 7, 11, 13 ] gap> HallSubgroup(G, [ 3, 5, 7, 11, 13 ]); Error, sorry, the GAP Tables Of Marks Library is not installed called from TableOfMarksFromLibrary( str ) at /home/ghorvath/work/gap/lib/tom.gi:942 called from TableOfMarks( nam ) at /home/ghorvath/work/gap/lib/grplatt.gi:2739 called from TomDataAlmostSimpleRecognition( G ) at /home/ghorvath/work/gap/lib/grplatt.gi:2773 called from TomDataMaxesAlmostSimple( G ) at /home/ghorvath/work/gap/lib/maxsub.gi:527 called from MaxesAlmostSimple( ImagesSource( act[2] ) ) at /home/ghorvath/work/gap/lib/maxsub.gi:824 called from ... at line 4 of stdin you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk>

— Reply to this email directly or view it on GitHub.

[olexandr-konovalov]

@hungaborhorvath Table of Marks is the TomLib package. It's included in the GAP distribution. I would strongly recommend not to use GAP without packages, as some are loaded by default and speed up its performance (AutPGrp, FactInt, etc.).

When I am using GAP development version, I normally just have a symlink pkg pointing to the pkg from a recent GAP release.

[hungaborhorvath]

@alex-konovalov Hm, all right. I will look up which packages are installed by default.

Off topic, you could put this into a separate issue if you want: However, for example on Debian Jessie I installed the standard gap by

sudo apt-get install gap

and when I start it, this is what I get:

ghorvath@SamsungLaptop:~$ /usr/bin/gap
 ┌───────┐   GAP, Version 4.7.5 of 24-May-2014 (free software, GPL)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: small 2.1, small2 2.0, id2 3.0, trans 1.0, prim 2.1
 Packages:   GAPDoc 1.5.1
 Try '?help' for help. See also  '?copyright' and  '?authors'
gap> 

When I list the properties of the package, dependencies are listed as follows:

Depends: gap-core, gap-libs, gap-online-help
Recommends: gap-doc, gap-dev, gap-trans-groups, gap-prim-groups, gap-small-groups
Suggests: gap-small-groups-extra, gap-character-tables, gap-table-of-marks

And indeed, it installed all dependencies and recommended packages but not the suggested ones, and therefore table-of-marks would be missing on a standard debian system. I am not sure if other versions of gap are packaged differently, but I do not find it a good idea to have code based on packages that are not necessarily installed by default.

[olexandr-konovalov]

@hungaborhorvath thanks - I know this. There is no need to create an issue for this since the Debian GAP package is a third party distribution, which is updated independently by Bill Allombert. It normally takes time for the new GAP release to propagate there because of Debian's testing cycle, and it's not even listed among GAP alternative installers at the moment since it does not provide the latest GAP release. Also, GAP is redistributed now with 119 packages, and I don't even see in the list of dependencies above where all other packages are sitting. My suggestion, especially since you're now actively participating in discussions here, is to have GAP 4.7.9 installed from source in addition to your fork of this repository, and don't use Debian GAP package.

[hungaborhorvath]

Sorry for being offtopic again....

@alex-konovalov Ok, so I download from the source, run configure and make, then should I download http://www.gap-system.org/Download/InstPackages.sh and run it, or are all packages compiled?

As a practical matter: I was thinking symlinking the pkg directory to the github version, but then I would need to install newer packages to the stable release if I ever need them for the development version. This I would rather not do, because then I cannot simulate properly the stable environment. Maybe I should write a script that does all the symlinking for every directory in pkg one by one? How do you guys do it?

[ChrisJefferson]

@hungaborhorvath : By default, no packages are compiled if you download GAP from gap-system.org, you can use InstPackages.sh. In the latest git version this script is included as bin/BuildPackages.sh.

Most packages work fine in 4.7.x and 4.8.x, and ones which only work in 4.8 usually have an option in packageinfo.g which stops them being loaded in 4.7, so sharing your package directory is mostly fine.

[fingolfin]

@hungaborhorvath I recommend not being too much off-topic on issues... instead, please write to the GAP mailing list gap@gap-system.org, or join us on our IRC channel #gap-system on freenode, or open a new issue. That way, we do not end up cluttering the history of issues with unrelated stuff.

[olexandr-konovalov]

@hungaborhorvath you wrote:

As a practical matter: I was thinking symlinking the pkg directory to the github version, but then I would need to install newer packages to the stable release if I ever need them for the development version. This I would rather not do, because then I cannot simulate properly the stable environment. Maybe I should write a script that does all the symlinking for every directory in pkg one by one? How do you guys do it?

You can install newer packages in .gap/pkg directory and then when you will load gap with -r option they will be ignored - please ask in the GAP mailing list gap@gap-system.org if you need more information.

[hungaborhorvath]

Thanks for all the suggestions, I close this issue now.