############################################################################# ## #W companion.g #Y Copyright (C) 2011-14 James D. Mitchell ## ## Licensing information can be found in the README file of this package. ## ############################################################################# ## # this file contains everything required to verify the computations in the # paper: # ‘Groups that together with any transformation generate regular semigroups or # idempotent generated semigroups’ by J. Araujo, J. D. Mitchell, and Csaba # Schneider. DeclareInfoClass("InfoCompan"); # Notes: an analogue of Orbits from the library but for orb package. Orbs:=function(g, x, act) local ht, i, nr, seen, out, y; ht:=HTCreate(x[1]); for i in [1..Length(x)] do HTAdd(ht, x[i], i); od; i:=0; nr:=0; seen:=BlistList([1..Length(x)], []); out:=[]; while true do i:=Position(seen, false, i); if i=fail then break; fi; nr:=nr+1; out[nr]:=Orb(g, x[i], act); Enumerate(out[nr]); for y in out[nr] do seen[HTValue(ht, y)]:=true; od; od; return out; end; GradedKernels:=function(S) local rho, kers, i; rho:=AsList(Enumerate(RhoOrb(S))); kers:=List([1..DegreeOfTransformationSemigroup(S)], x-> []); for i in [2..Length(rho)] do Add(kers[MaximumList(rho[i])], rho[i]); od; return kers; end; # Notes: tests if the semigroup generated by a perm. group with the universal # transversal property and every transformation is idempotent generated. # Details of this algorithm can be found in the paper. IsAlwaysIdempotentGenerated:=function(G) local n, gens, count, kers, orbits1, orbits2, ker, img, sym, idem, next, S, idems, T, classes, i, orbit1, orbit2, t, e, g, h; n:=NrMovedPoints(G); gens:=List(SmallGeneratingSet(G), AsTransformation); count:=0; kers:=GradedKernels(FullTransformationSemigroup(n)); for i in [1..NrMovedPoints(G)-1] do orbits1:=Orbs(G, kers[i], function(ker, x) return ON_KERNEL_ANTI_ACTION(ker, AsTransformation(x), n); end); orbits2:=Orbs(G, Combinations([1..n], i), OnSets); Info(InfoCompan, 1, "##################################################"); Info(InfoCompan, 1, "TESTING TRANSFORMATIONS OF RANK ", i); for orbit1 in orbits1 do for orbit2 in orbits2 do Info(InfoCompan, 1, "###########################", "#######################"); ker:=orbit1[1]; Info(InfoCompan, 1, "kernel : ", ker); img:=First(orbit2, x-> IsInjectiveListTrans(x, ker)); Info(InfoCompan, 1, "image : ", img); sym:=SymmetricGroup(Length(img)); sym:=RightTransversal(sym, Action(Stabilizer(G, img, OnSets), img)); Info(InfoCompan, 1, "transversal of stabilizer of image has length ", Length(sym)); idem:=Idempotent(img, ker); for t in sym do next:=idem*t; S:=Semigroup(gens, next); count:=count+1; idems:=Idempotents(S, RankOfTransformation(next, NrMovedPoints(G))); T:=Semigroup(idems); classes:=[]; for e in idems do if not ForAny(classes, x-> e in x) then Add(classes, RClass(T, e)); fi; od; for g in G do for h in G do if not ForAny(classes, x-> g*next*h in x) then return next; fi; od; od; od; Info(InfoCompan, 1, "all ", Length(sym), " semigroups are ", "idempotent generated"); od; od; Info(InfoCompan, 1, "##################################################"); od; return [true, count]; end; # Notes: returns true if the perm. gp. has the universal transversal property, # and otherwise returns a partition and a set which is not mapped to # a transversal of that partition by any element of the perm. gp. IsUniversalTransversalGroup:=function(G) local n, kers, sets, partitions, set, orb, i, x; n:=LargestMovedPoint(G); kers:=GradedKernels(FullTransformationSemigroup(n)); for i in [1..n] do sets:=Combinations([1..n], i); partitions:=kers[i]; repeat set:=sets[1]; orb:=Orbit(G, set, OnSets); for x in partitions do if not ForAny(orb, y-> IsInjectiveListTrans(y,x)) then return [x, orb[1]]; fi; od; sets:=Difference(sets, orb); until sets=[]; od; return true; end; # InstallOtherMethod(SemigroupByGenerators, "for a perm. gp. and transformation", [IsPermGroup, IsTransformation], function(g, f) return Semigroup(List(GeneratorsOfGroup(g), AsTransformation), f); end); #EOF