#############################################################################
##
#W  companion.gi
#Y  Copyright (C) 2011                                   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. 

# new for dev! - IsAlwaysIdempotentGenerated  - "for a perm. group"
############################################################################
# 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.

InstallMethod(IsAlwaysIdempotentGenerated, "for a perm. group",  
[IsPermGroup], 
function(G)
  local n, gens, count, kers, imgs, ker, img, sym, idem, next, S, idems, T, 
   classes, i, orbit1, orbit2, t, e, g, h;

  n:=NrMovedPoints(G);
  gens:=List(SmallGeneratingSet(G), x-> AsTransformation(x, n));
  count:=0;

  for i in [1..n-1] do    
    kers:=GradedKernelsOfTransSemigroup(FullTransformationSemigroup(n));
    kers:=Orbs(G, kers[i], OnCTSK);
    imgs:=Orbs(G, Combinations([1..n], i), OnSets);

    Info(InfoCompan, 1, "##################################################");
    Info(InfoCompan, 1, "TESTING TRANSFORMATIONS OF RANK ", i);

    for orbit1 in kers do 
      for orbit2 in imgs do
        Info(InfoCompan, 1, "###########################", 
         "#######################");
        ker:=orbit1[1];
        Info(InfoCompan, 1, "kernel : ", ker);
        img:=First(orbit2, x-> IsInjectiveTransOnList(ker, x));
        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:=IdempotentNC(ker, img);

        for t in sym do
          next:=idem*t;
          S:=Semigroup(Concatenation(gens, [next]));

          count:=count+1;

          idems:=Idempotents(S, RankOfTransformation(next));
          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);

# new for dev! - IsUniversalTransversalGroup  - "for a perm. group"
#############################################################################
# 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.

InstallMethod(IsUniversalTransversalGroup, "for a permutation group", 
[IsPermGroup], 
function(G)
  local n, sets, partitions, set, orb, i, x;

  n:=LargestMovedPoint(G);

  for i in [1..n] do 
    sets:=Combinations([1..n], i);
    partitions:=GradedKernelsOfTransSemigroup(
     FullTransformationSemigroup(n))[i];
    repeat
      set:=sets[1];
      orb:=Orbit(G, set, OnSets);
      for x in partitions do 
	if not ForAny(orb, y-> IsInjectiveTransOnList(x,y)) then 
	  return [x, First(orb, y-> not IsInjectiveTransOnList(x,y))];
	fi;
      od;
      sets:=Difference(sets, orb);
    until sets=[];
  od;
  return true;
end);

# new for dev! - OnCTSK - "for a transformation image list and perm"
#############################################################################
# Notes: OnCanonicalTransformationSameKernel.

InstallGlobalFunction(OnCTSK,
function(ker, g)
  local a, b;
  
  a:=OnTuples([1..Length(ker)], g^-1);
  b:=OnTuples(ker, g);
  return CanonicalTransSameKernel(b{a});
end);

# new for dev! - Orbs - "for a group or semigroup, set, and action"
#############################################################################
# Notes: an analogue of Orbits from the library but for orb package.

InstallGlobalFunction(Orbs, 
function(g, x, act)
  local m, i, j, o, l;
  
  m:=Length(x); i:=2; j:=1;
  o:=[Orb(g, x[1], act)]; Enumerate(o[1]);

  repeat 
    l:=First([i..m], k-> not ForAny(o, y-> x[k] in y));
    if not l=fail then 
      i:=l+1; 
      j:=j+1;
      o[j]:=Orb(g, x[l], act); Enumerate(o[j]);
    fi;
  until i=m+1 or l=fail;

  return o;
end);

# new for dev! - SemigroupByGenerators - for a perm. gp. and transformation
#############################################################################

InstallOtherMethod(SemigroupByGenerators, "for a perm. gp. and transformation",
[IsPermGroup, IsTransformation],
function(g, f)
  local n;

  n:=Degree(f);

  return Semigroup(Concatenation(List(GeneratorsOfGroup(g), x->
    AsTransformation(x, n)), [f]));
end);

#EOF