MaximalSubsemigroups fails

Issue #106 resolved
Christopher Jefferson
created an issue

With current hg head in the default branch, the following code (taken from tst/maximal.tst) fails. The following shows the problem, which seems to be that RemoveSet doesn't work on however DClasses are represented (should I not be in default?)

gap> T3:=FullTransformationMonoid(3);
<full transformation semigroup on 3 pts>
gap> MaximalSubsemigroups(T3);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `RemoveSet' on 2 arguments called from
RemoveSet( A, a
 ); on line 814 of file /Users/caj/work/source/gap/gap/pkg/semigroups/gap/maximal.gi called fro\
m
<function "unknown">( <arguments> )
 called from read-eval loop at line 5 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> A;
{Transformation( [ 1, 2, 1 ] )}
brk> IsSet(A);
false
brk> DClasses(3);
[ {IdentityTransformation}, {Transformation( [ 1, 2, 1 ] )}, {Transformation( [ 1, 1, 1 ] )} ]

Comments (14)

  1. wilfwilson

    I can't seem to recreate this error. Can you James?

    I am using the current hg head of the stable-4.7 gap dev branch. Both the default and 2.2 branch of semigroups are okay for me.

    Which version of GAP are you using Chris?

  2. James Mitchell repo owner

    I also can't reproduce this. Both maximal.tst and MaximalSubsemigroups(FullTransformationMonoid(3)); return the correct answer with no error for me (in both branches).

  3. Christopher Jefferson reporter

    I went and got a fresh checkout of gap, new packages, and a new copy of semigroups and digraphs. Same error. I'm happy to look at this on Wednesday afternoon if you will be around. For completeness, here is a full log from my computer.

    (~/work/source/gap/gap)-(caj)-(jobs:0)
    🐧 (! 4625)-> hg id
    d221722b14b5 (stable-4.7)
    
    (~/work/source/gap/gap)-(caj)-(jobs:0)
    🐧 (! 4626)-> gap.sh
     β”Œβ”€β”€β”€β”€β”€β”€β”€β”   GAP, Version 4.dev of today (free software, GPL)
     β”‚  GAP  β”‚   http://www.gap-system.org
     β””β”€β”€β”€β”€β”€β”€β”€β”˜   Architecture: x86_64-apple-darwin14.0.0-gcc-default64
     Libs used:  gmp
     Loading the library and packages ...
     Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
     Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.0, AutPGrp 1.6, CRISP 1.3.8, Cryst 4.1.12, CrystCat 1.1.6, CTblLib 1.2.2, FactInt 1.5.3, FGA 1.2.0,
                 GAPDoc 1.5.1, IO 4.4.2, IRREDSOL 1.2.4, LAGUNA 3.6.5, Polenta 1.3.2, Polycyclic 2.11, RadiRoot 2.7, ResClasses 3.4.0, Sophus 1.23, SpinSym 1.5,
                 TomLib 1.2.4
     Try '?help' for help. See also  '?copyright' and  '?authors'
    gap> LoadPackage("semigroups");
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    Loading  orb 4.7.2 (Methods to enumerate orbits)
    by Juergen Mueller (http://www.math.rwth-aachen.de/~Juergen.Mueller),
       Max NeunhΓΆffer (http://www-groups.mcs.st-and.ac.uk/~neunhoef), and
       Felix Noeske (http://www.math.rwth-aachen.de/~Felix.Noeske).
    Homepage: http://gap-system.github.io/orb/
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    Loading  genss 1.6.2 (Generic Schreier-Sims)
    by Max NeunhΓΆffer (http://www-groups.mcs.st-and.ac.uk/~neunhoef) and
       Felix Noeske (http://www.math.rwth-aachen.de/~Felix.Noeske).
    Homepage: http://gap-system.github.io/genss/
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    Loading  GRAPE 4.6.1 (GRaph Algorithms using PErmutation groups)
    by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
    Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    Loading  Digraphs 0.1 (Digraphs - Methods for directed graphs)
    by J. D. Mitchell (tinyurl.com/jdmitchell),
       J. Jonusas (jj252@st-and.ac.uk),
       Markus Pfeiffer (http://www.morphism.de/~markusp/),
       M. Torpey (mct25@st-and.ac.uk), and
       W. Wilson (http://wilf-wilson.net).
    Homepage: http://www-groups.mcs.st-andrews.ac.uk/~jamesm/digraphs.php
    ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
    -----------------------------------------------------------------------------
    Loading  Semigroups 2.2 - methods for semigroups
    by J. D. Mitchell (tinyurl.com/jdmitchell)
    with contributions by:
         Manuel Delgado (http://cmup.fc.up.pt/cmup/mdelgado/),
         J. East (http://www.uws.edu.au/staff_profiles/uws_profiles/doctor_james_east),
         Attila Egri-Nagy (http://www.egri-nagy.hu),
         J. Jonusas,
         Markus Pfeiffer (http://www.morphism.de/~markusp/),
         B. Steinberg (http://www.sci.ccny.cuny.edu/~benjamin/),
         J. Smith (http://math.sci.ccny.cuny.edu/people?name=Jhevon_Smith),
         M. Torpey,
     and W. Wilson (http://wilf-wilson.net).
    -----------------------------------------------------------------------------
    true
    gap> T3:=FullTransformationMonoid(3);
    <full transformation semigroup on 3 pts>
    gap> MaximalSubsemigroups(T3);
    Error, no method found! For debugging hints type ?Recovery from NoMethodFound
    Error, no 1st choice method found for `RemoveSet' on 2 arguments called from
    RemoveSet( A, a ); called from
    <function "unknown">( <arguments> )
     called from read-eval loop at line 3 of *stdin*
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk>
    
  4. wilfwilson

    Thanks for this Chris. I will be around on Wednesday afternoon, so hopefully we'll get it cleared up then. I've gone and looked through the maximal subsemigroups code, but I can't see what is wrong.

    Your example is failing on line 814, which is:

    for a in gens{j} do RemoveSet(A, a); od;
    

    For some reason GAP thinks that the variable A is still a D-class. However the previous line is:

    A:=Difference(classes[i], Intersection(U, classes[i]));
    

    And according to the GAP manual, Difference should return a set. In this example, classes[i] is a D-class, and Intersection(U, classes[i]) is an empty list. (Perhaps it being empty is causing some weirdness).

    I'd be interested to know whether running these few lines of code gives you 'true' at the end:

    gap> T3:=FullTransformationMonoid(3);;
    gap> U := Semigroup(
    > [ Transformation( [ 2, 1 ] ), Transformation( [ 2, 3, 1 ] ) ]);;
    gap> d:=DClasses(T3)[2];
    {Transformation( [ 1, 2, 1 ] )}
    gap> A := Difference( d, Intersection( U, d ) );;
    gap> IsSet(A);
    
  5. Christopher Jefferson reporter

    This has helped. Slightly tweaked, here is (I think) showing the problem:

    TraceMethods(Difference);
    T3:=FullTransformationMonoid(3);;
    d:=DClasses(T3)[2];
    A := Difference( d, [] );;
    #I  Difference: for a domain and the empty set (ResClasses)
    

    The source code to that method, which is in pkg/resclasses/lib/resclass.gi is:

    #############################################################################
    ##
    #M  Difference( <D>, <S> ) . . . . . . . . . . . for a ring and the empty set
    ##
    InstallMethod( Difference, "for a domain and the empty set (ResClasses)",
                   ReturnTrue, [ IsDomain, IsList and IsEmpty ], SUM_FLAGS,
                   function ( D, S ) return D; end );
    
  6. James Mitchell repo owner

    Hmm, well that explains it alright. I don't auto-load ResClasses, which explains the difference. This method seems to change the behaviour of GAP, and SUM_FLAGS means that no better method can exist. Urgh.

  7. Christopher Jefferson reporter

    Unfortunately I tried fixing this in resclasses, and the package is making use of Difference on infinite sets, so replacing that method with 'return Set(D);' breaks resclasses.

    Now, resclasses shouldn't be abusing Difference at all, but there is unfortunately not a super-easy fix to resclasses.

  8. James Mitchell repo owner

    A package (and particularly not an autoloaded one) should not change the behaviour of GAP. So I guess that there should be another operation with a difference name in ResClasses. I am just about to email Stefan about this, hopefully he will agree!

  9. Alexander Konovalov

    On a side note, Semigroups lists only tst/testinstall.g as a default test in its PackageInfo.g file and should send an email to James if anything fails. Since tst/maximal.tst is not a part of this, our Jenkins tests would never encounter this error.

    You can't put all tests into tst/testinstall.g since it should not be very long to run, but 5-7 minutes would be fine.

  10. Log in to comment