MaximalSubsemigroups fails

james-d-mitchell commented 10 years ago

Originally reported by: ChrisJefferson (Bitbucket: ChrisJefferson, GitHub: ChrisJefferson)

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 ] )} ]

Bitbucket: https://bitbucket.org/james-d-mitchell/semigroups/issue/106

james-d-mitchell commented 9 years ago

Original comment by James Mitchell (Bitbucket: james-d-mitchell, GitHub: james-d-mitchell):

Removing milestone: 2.3 (automated comment)

james-d-mitchell commented 9 years ago

Original comment by wilfwilson (Bitbucket: wilfwilson, GitHub: wilfwilson):

Resolves issue #106. WW

james-d-mitchell commented 10 years ago

Original comment by Alexander Konovalov (Bitbucket: alex_konovalov, GitHub: Unknown):

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.

james-d-mitchell commented 10 years ago

Original comment by James Mitchell (Bitbucket: james-d-mitchell, GitHub: james-d-mitchell):

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!

james-d-mitchell commented 10 years ago

Original comment by ChrisJefferson (Bitbucket: ChrisJefferson, GitHub: ChrisJefferson):

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.

james-d-mitchell commented 10 years ago

Original comment by James Mitchell (Bitbucket: james-d-mitchell, GitHub: james-d-mitchell):

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.

james-d-mitchell commented 10 years ago

Original comment by ChrisJefferson (Bitbucket: ChrisJefferson, GitHub: ChrisJefferson):

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 );

james-d-mitchell commented 10 years ago

Original comment by wilfwilson (Bitbucket: wilfwilson, GitHub: 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:

#!gap
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:

#!gap
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

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);

james-d-mitchell commented 10 years ago

Original comment by ChrisJefferson (Bitbucket: ChrisJefferson, GitHub: ChrisJefferson):

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>

james-d-mitchell commented 10 years ago

Original comment by James Mitchell (Bitbucket: james-d-mitchell, GitHub: james-d-mitchell):

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).

james-d-mitchell commented 10 years ago

Original comment by wilfwilson (Bitbucket: wilfwilson, GitHub: 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?

james-d-mitchell commented 10 years ago

Original comment by ChrisJefferson (Bitbucket: ChrisJefferson, GitHub: ChrisJefferson):

Same error occurs in 2.2 branch.

semigroups / Semigroups

MaximalSubsemigroups fails #104