Quelle setup.gi Sprache: unbekannt

###########################################################################
##
##  main/setup.gi
##  Copyright (C) 2013-2022                              James D. Mitchell
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

###############################################################################
# Setup - install the basic things required for specific acting semigroups    #
###############################################################################

# IsGeneratorsOfActingSemigroup

InstallMethod(IsGeneratorsOfActingSemigroup, "for a list or collection",
[IsListOrCollection], ReturnFalse);

# In the below can't do ReturnTrue, since GAP insists that we use
# InstallTrueMethod.
#
# InstallTrueMethod(IsGeneratorsOfActingSemigroup, IsTransformationCollection);
#
# can't do InstallTrueMethod for the above since this is not picked up
# if Semigroups is loaded after any transformation semigroup has been created.
# It seems that since IsTransformationCollection has had its implied filters
# installed, if we add an additional implied filter
# IsGeneratorsOfActingSemigroup, then this is ignored. I think this is a bug.

InstallMethod(IsGeneratorsOfActingSemigroup, "for a transformation collection",
[IsTransformationCollection], x -> true);  # gaplint: disable=W036

InstallMethod(IsGeneratorsOfActingSemigroup, "for a partial perm collection",
[IsPartialPermCollection], x -> true);  # gaplint: disable=W036

InstallMethod(IsGeneratorsOfActingSemigroup, "for a bipartition collection",
[IsBipartitionCollection], x -> true);  # gaplint: disable=W036

InstallMethod(IsGeneratorsOfActingSemigroup,
"for a Rees 0-matrix semigroup element collection",
[IsReesZeroMatrixSemigroupElementCollection],
function(coll)
  local R;
  R := ReesMatrixSemigroupOfFamily(FamilyObj(Representative(coll)));
  return IsPermGroup(UnderlyingSemigroup(R)) and IsRegularSemigroup(R);
end);

InstallMethod(IsGeneratorsOfActingSemigroup,
"for a McAlister triple element collection",
[IsMcAlisterTripleSemigroupElementCollection],
function(coll)
  return
  IsPermGroup(McAlisterTripleSemigroupGroup(MTSEParent(Representative(coll))));
end);

InstallMethod(IsGeneratorsOfActingSemigroup,
"for an ffe coll coll coll",
# TODO(MatrixObj-later) is this the best way to recognise a collection of
# MatrixObj?
[IsFFECollCollColl],
function(coll)
  return IsGeneratorsOfSemigroup(coll)
    and (IsEmpty(coll) or ForAll(coll, IsMatrixObjOverFiniteField));
end);

InstallTrueMethod(IsGeneratorsOfActingSemigroup,
IsMatrixOverFiniteFieldSemigroup);

# the largest point involved in the action

InstallMethod(ActionDegree, "for a transformation",
[IsTransformation], DegreeOfTransformation);

InstallMethod(ActionDegree, "for a partial perm",
[IsPartialPerm], x -> Maximum(DegreeOfPartialPerm(x),
                              CodegreeOfPartialPerm(x)));

InstallMethod(ActionDegree, "for a bipartition",
[IsBipartition], DegreeOfBipartition);

InstallMethod(ActionDegree, "for a Rees 0-matrix semigroup element",
[IsReesZeroMatrixSemigroupElement],
function(x)
  if x![1] = 0 then
    return 0;
  fi;
  return NrMovedPoints(x![2]) + 1;
end);

InstallMethod(ActionDegree, "for a McAlister semigroup element",
[IsMcAlisterTripleSemigroupElement],
x -> 0);

InstallMethod(ActionDegree, "for a matrix obj", [IsMatrixObj],
function(m)
  if not IsMatrixObjOverFiniteField(m) then
    TryNextMethod();
  fi;
  return NrRows(m);
end);

InstallMethod(ActionDegree, "for a transformation collection",
[IsTransformationCollection], DegreeOfTransformationCollection);

InstallMethod(ActionDegree, "for a partial perm collection",
[IsPartialPermCollection], x -> Maximum(DegreeOfPartialPermCollection(x),
                                        CodegreeOfPartialPermCollection(x)));

InstallMethod(ActionDegree, "for a bipartition collection",
[IsBipartitionCollection], DegreeOfBipartitionCollection);

InstallMethod(ActionDegree, "for a Rees 0-matrix semigroup element collection",
[IsReesZeroMatrixSemigroupElementCollection],
function(coll)
  local R;
  if ForAny(coll, x -> x![1] <> 0) then
    R := ReesMatrixSemigroupOfFamily(FamilyObj(Representative(coll)));
    return NrMovedPoints(UnderlyingSemigroup(R)) + 1;
  fi;
  return 0;
end);

InstallMethod(ActionDegree, "for a ffe coll coll coll",
[IsFFECollCollColl],
function(coll)
  Assert(1, ForAll(coll, IsMatrixObjOverFiniteField));
  return NrRows(Representative(coll));
end);

InstallMethod(ActionDegree, "for a McAlister semigroup element collection",
[IsMcAlisterTripleSemigroupElementCollection],
coll -> MaximumList(List(coll, ActionDegree)));

InstallMethod(ActionDegree, "for a transformation semigroup",
[IsTransformationSemigroup], DegreeOfTransformationSemigroup);

InstallMethod(ActionDegree, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> Maximum(DegreeOfPartialPermSemigroup(x),
                                       CodegreeOfPartialPermSemigroup(x)));

InstallMethod(ActionDegree, "for a partial perm inverse semigroup",
[IsPartialPermSemigroup and IsInverseSemigroup], DegreeOfPartialPermSemigroup);

InstallMethod(ActionDegree, "for a bipartition semigroup",
[IsBipartitionSemigroup], DegreeOfBipartitionSemigroup);

InstallMethod(ActionDegree, "for a Rees 0-matrix subsemigroup with generators",
[IsReesZeroMatrixSubsemigroup and HasGeneratorsOfSemigroup],
function(R)
  local parent;
  if ForAny(GeneratorsOfSemigroup(R), x -> x![1] <> 0) then
    parent := ReesMatrixSemigroupOfFamily(ElementsFamily(FamilyObj(R)));
    return NrMovedPoints(UnderlyingSemigroup(parent)) + 1;
  fi;
  return 0;
end);

InstallMethod(ActionDegree, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
S -> 0);

InstallMethod(ActionDegree, "for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> ActionDegree(Representative(S)));

# the number of points in the range of the action

InstallMethod(ActionRank, "for a transformation and integer",
[IsTransformation, IsInt], RANK_TRANS_INT);

InstallMethod(ActionRank, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> f -> RANK_TRANS_INT(f, DegreeOfTransformationSemigroup(S)));

InstallMethod(ActionRank, "for a partial perm and integer",
[IsPartialPerm, IsInt],
{f, n} -> RankOfPartialPerm(f));

InstallMethod(ActionRank, "for a partial perm semigroup",
[IsPartialPermSemigroup],
S -> RankOfPartialPerm);

InstallMethod(ActionRank, "for a bipartition and integer",
[IsBipartition, IsInt], BIPART_RANK);

InstallMethod(ActionRank, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> RankOfBipartition);

InstallMethod(ActionRank,
"for a Rees 0-matrix semigroup element and integer",
[IsReesZeroMatrixSemigroupElement, IsInt],
function(f, _)
  local parent;
  if f![1] = 0 then
    return 0;
  fi;
  parent := ReesMatrixSemigroupOfFamily(FamilyObj(f));
  return NrMovedPoints(UnderlyingSemigroup(parent)) + 1;
end);

InstallMethod(ActionRank, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup],
function(R)
  return function(x)
    local parent;
    if x![1] = 0 then
      return 0;
    else
      parent := ReesMatrixSemigroupOfFamily(ElementsFamily(FamilyObj(R)));
      return NrMovedPoints(UnderlyingSemigroup(parent)) + 1;
    fi;
  end;
end);

InstallMethod(ActionRank, "for a McAlister triple semigroup element and int",
[IsMcAlisterTripleSemigroupElement, IsInt],
{f, n} -> f[1]);

InstallMethod(ActionRank, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
S -> x -> ActionDegree(S));

InstallMethod(ActionRank, "for a matrix object and integer",
[IsMatrixObj, IsInt],
function(x, _)
  if not IsMatrixObjOverFiniteField(x) then
    TryNextMethod();
  fi;
  return Rank(RowSpaceBasis(x));
end);

InstallMethod(ActionRank, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> x -> Rank(RowSpaceBasis(x)));

# the minimum possible rank of an element

InstallMethod(MinActionRank, "for a transformation semigroup",
[IsTransformationSemigroup], x -> 1);

InstallMethod(MinActionRank, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> 0);

InstallMethod(MinActionRank, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> 0);

InstallMethod(MinActionRank, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], x -> 0);

InstallMethod(MinActionRank, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], x -> 1);

InstallMethod(MinActionRank, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], x -> 0);

# options passed to LambdaOrb(S) when it is created

InstallMethod(LambdaOrbOpts, "for a transformation semigroup",
[IsTransformationSemigroup], S -> rec(forflatplainlists := true));

InstallMethod(LambdaOrbOpts, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> rec(forflatplainlists := true));

InstallMethod(LambdaOrbOpts, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> rec());

InstallMethod(LambdaOrbOpts, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S -> rec());

InstallMethod(LambdaOrbOpts, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> rec());

InstallMethod(LambdaOrbOpts, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S -> rec());

InstallMethod(RhoOrbOpts, "for a transformation semigroup",
[IsTransformationSemigroup], S -> rec(forflatplainlists := true));

InstallMethod(RhoOrbOpts, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> rec(forflatplainlists := true));

InstallMethod(RhoOrbOpts, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> rec());

InstallMethod(RhoOrbOpts, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S -> rec());

InstallMethod(RhoOrbOpts, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> rec());

InstallMethod(RhoOrbOpts, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S -> rec());

# the lambda and rho acts
InstallMethod(LambdaAct, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> {set, f} -> OnPosIntSetsTrans(set, f, DegreeOfTransformationSemigroup(S)));

InstallMethod(LambdaAct, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> OnPosIntSetsPartialPerm);

InstallMethod(LambdaAct, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> BLOCKS_RIGHT_ACT);

InstallMethod(LambdaAct, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], x -> function(pt, x)
  if x![1] = 0 or pt = 0 then
    return 0;
  elif pt = -1 or x![4][pt][x![1]] <> 0 then
    return x![3];
  else
    return 0;
  fi;
end);

InstallMethod(LambdaAct, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
function(S)
  local act, digraph;
  S := MTSEParent(Representative(S));
  act     := McAlisterTripleSemigroupAction(S);
  digraph := McAlisterTripleSemigroupPartialOrder(S);
  return
  function(pt, x)
    if pt = 0 then
      return act(x[1], x[2] ^ -1);
    fi;
    return PartialOrderDigraphJoinOfVertices(digraph,
                                             act(pt, x[2] ^ -1),
                                             act(x[1], x[2] ^ -1));
  end;
end);

InstallMethod(LambdaAct, "for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> {vsp, mat} -> MatrixOverFiniteFieldRowSpaceRightAction(S, vsp, mat));

InstallMethod(RhoAct, "for a transformation semigroup",
[IsTransformationSemigroup],
S ->
{set, f} -> ON_KERNEL_ANTI_ACTION(set, f, DegreeOfTransformationSemigroup(S)));

InstallMethod(RhoAct, "for a partial perm semigroup",
[IsPartialPermSemigroup], S ->
{set, f} -> OnPosIntSetsPartialPerm(set, f ^ -1));

InstallMethod(RhoAct, "for a partial perm semigroup",
[IsBipartitionSemigroup], x -> BLOCKS_LEFT_ACT);

InstallMethod(RhoAct, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], x -> function(pt, x)
  if x![1] = 0 or pt = 0 then
    return 0;
  elif pt = -1 or x![4][x![3]][pt] <> 0 then
    return x![1];
  else
    return 0;
  fi;
end);

InstallMethod(RhoAct, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
function(S)
  local act, digraph;
  S := MTSEParent(Representative(S));
  act     := McAlisterTripleSemigroupAction(S);
  digraph := McAlisterTripleSemigroupPartialOrder(S);
  return
    function(pt, x)
      if pt = 0 then
        return x[1];
      fi;
      return PartialOrderDigraphJoinOfVertices(digraph,
                                               act(pt, x[2]),
                                               x[1]);
    end;
end);

InstallMethod(RhoAct, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> {vsp, mat} -> LambdaAct(S)(vsp, TransposedMat(mat)));

# the seed or dummy start point for LambdaOrb

InstallMethod(LambdaOrbSeed, "for a transformation semigroup",
[IsTransformationSemigroup], S -> [0]);

InstallMethod(LambdaOrbSeed, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> [0]);

InstallMethod(LambdaOrbSeed, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> BLOCKS_NC([[1 .. DegreeOfBipartitionSemigroup(S) + 1]]));

InstallMethod(LambdaOrbSeed, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S -> -1);

InstallMethod(LambdaOrbSeed, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> 0);

InstallMethod(LambdaOrbSeed,
"for a matrix over finite field semigroup",
[IsMatrixOverFiniteFieldSemigroup],
function(S)
    local deg;
    deg := NrRows(Representative(S)) + 2;
    return NewRowBasisOverFiniteField(IsPlistRowBasisOverFiniteFieldRep,
                                      BaseDomain(S),
                                      NullMat(deg, deg, BaseDomain(S)));
end);

# the seed or dummy start point for RhoOrb

InstallMethod(RhoOrbSeed, "for a transformation semigroup",
[IsTransformationSemigroup], S -> [0]);

InstallMethod(RhoOrbSeed, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> [0]);

InstallMethod(RhoOrbSeed, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> BLOCKS_NC([[1 .. DegreeOfBipartitionSemigroup(S) + 1]]));

InstallMethod(RhoOrbSeed, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S -> -1);

InstallMethod(RhoOrbSeed, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> 0);

InstallMethod(RhoOrbSeed, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], LambdaOrbSeed);

# the function calculating the lambda or rho value of an element

InstallMethod(LambdaFunc, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> f -> IMAGE_SET_TRANS_INT(f, DegreeOfTransformationSemigroup(S)));

InstallMethod(LambdaFunc, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> IMAGE_SET_PPERM);

InstallMethod(LambdaFunc, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> BIPART_RIGHT_BLOCKS);

InstallMethod(LambdaFunc, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], R -> function(x)
  if x![1] <> 0 then
    return x![3];
  fi;
  return 0;
end);

InstallMethod(LambdaFunc, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
function(S)
  local act;
  act := McAlisterTripleSemigroupAction(MTSEParent(Representative(S)));
  return x -> act(x[1], x[2] ^ -1);
end);

# a function that returns the row space
InstallMethod(LambdaFunc, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S -> RowSpaceBasis);

InstallMethod(RhoFunc, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> f -> FLAT_KERNEL_TRANS_INT(f, DegreeOfTransformationSemigroup(S)));

InstallMethod(RhoFunc, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> DOMAIN_PPERM);

InstallMethod(RhoFunc, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> BIPART_LEFT_BLOCKS);

InstallMethod(RhoFunc, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], R -> x -> x![1]);

InstallMethod(RhoFunc, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> x -> x[1]);

# a function that returns the column space
InstallMethod(RhoFunc, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> mat -> LambdaFunc(S)(TransposedMat(mat)));

# The function used to calculate the rank of lambda or rho value

InstallMethod(LambdaRank, "for a transformation semigroup",
[IsTransformationSemigroup], x -> Length);

InstallMethod(LambdaRank, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> Length);

InstallMethod(LambdaRank, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> BLOCKS_RANK);

InstallMethod(LambdaRank, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], R ->
function(x)
  local parent;
  if x = 0 then
    return 0;
  else
    parent := ReesMatrixSemigroupOfFamily(ElementsFamily(FamilyObj(R)));
    return NrMovedPoints(UnderlyingSemigroup(parent)) + 1;
  fi;
end);

InstallMethod(LambdaRank, "for a McAlister subsemigroup",
[IsMcAlisterTripleSubsemigroup], S ->
function(x)
  local T;
  if x = 0 then
    return 0;
  fi;
  T := MTSEParent(Representative(S));
  return ActionRank(MTSE(T, x, One(McAlisterTripleSemigroupGroup(T))), 0);
end);

# Why are there row spaces and matrices passed in here?
InstallMethod(LambdaRank, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], x -> Rank);

InstallMethod(RhoRank, "for a transformation semigroup",
[IsTransformationSemigroup], S -> function(x)
  if IsEmpty(x) then
    return 0;
  else
    return MaximumList(x);
  fi;
end);

InstallMethod(RhoRank, "for a partial perm semigroup",
[IsPartialPermSemigroup], x -> Length);

InstallMethod(RhoRank, "for a bipartition semigroup",
[IsBipartitionSemigroup], x -> BLOCKS_RANK);

InstallMethod(RhoRank, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], LambdaRank);

InstallMethod(RhoRank, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], LambdaRank);

InstallMethod(RhoRank, "for a McAlister subsemigroup",
[IsMcAlisterTripleSubsemigroup], LambdaRank);

# if g=LambdaInverse(X, f) and X^f=Y, then Y^g=X and g acts on the right
# like the inverse of f on Y.

InstallMethod(LambdaInverse, "for a transformation semigroup",
[IsTransformationSemigroup], S -> INV_LIST_TRANS);

InstallMethod(LambdaInverse, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> {x, f} -> f ^ -1);

InstallMethod(LambdaInverse, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> {x, f} -> f ^ -1);

InstallMethod(LambdaInverse, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BLOCKS_INV_RIGHT);

InstallMethod(LambdaInverse, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S ->
function(k, x)
  local i;
  if x![1] = 0 or k = 0 then
    return x;
  fi;
  i := First([1 .. Length(x![4][x![3]])], i -> x![4][x![3]][i] <> 0);
  return Objectify(FamilyObj(x)!.type,
                   [i,
                    (x![4][k][x![1]] * x![2] * x![4][x![3]][i]) ^ -1,
                    k,
                    x![4]]);
end);

# if g = RhoInverse(X, f) and f ^ X = Y (this is a left action), then
# g ^ Y = X and g acts on the left like the inverse of f on Y.

InstallMethod(LambdaInverse, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
{rsp, mat} -> MatrixOverFiniteFieldLocalRightInverse(S, rsp, mat));

InstallMethod(RhoInverse, "for a transformation semigroup",
[IsTransformationSemigroup], S -> INV_KER_TRANS);

InstallMethod(RhoInverse, "for a partial perm semigroup",
[IsPartialPermSemigroup], S ->
  {dom, f} -> f ^ -1);

InstallMethod(RhoInverse, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> {x, f} -> f ^ -1);

# JDM better method for this!!

InstallMethod(RhoInverse, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S ->
function(k, x)
  local i;
  if x![1] = 0 or k = 0 then
    return x;
  fi;
  i := First([1 .. Length(x![4])], i -> x![4][i][x![1]] <> 0);
  return Objectify(FamilyObj(x)!.type,
                   [k,
                    (x![4][i][x![1]] * x![2] * x![4][x![3]][k]) ^ -1,
                    i,
                    x![4]]);
end);

InstallMethod(RhoInverse, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BLOCKS_INV_LEFT);

InstallMethod(RhoInverse, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
function(rsp, mat)
  return TransposedMat(MatrixOverFiniteFieldLocalRightInverse(S,
                          rsp, TransposedMat(mat)));
end);

SEMIGROUPS.DefaultLambdaBound := _ ->
function(r)
  if r < 100 then
    return Factorial(r);
  else
    return infinity;
  fi;
end;

InstallMethod(LambdaBound, "for a transformation semigroup",
[IsTransformationSemigroup], SEMIGROUPS.DefaultLambdaBound);

InstallMethod(RhoBound, "for a transformation semigroup",
[IsTransformationSemigroup], LambdaBound);

InstallMethod(LambdaBound, "for a partial perm semigroup",
[IsPartialPermSemigroup], SEMIGROUPS.DefaultLambdaBound);

InstallMethod(RhoBound, "for a partial perm semigroup",
[IsPartialPermSemigroup], LambdaBound);

InstallMethod(LambdaBound, "for a bipartition semigroup",
[IsBipartitionSemigroup], SEMIGROUPS.DefaultLambdaBound);

InstallMethod(RhoBound, "for a bipartition semigroup",
[IsBipartitionSemigroup], LambdaBound);

InstallMethod(LambdaBound, "for a Rees 0-matrix semigroup",
[IsReesZeroMatrixSubsemigroup], SEMIGROUPS.DefaultLambdaBound);

InstallMethod(RhoBound, "for a Rees 0-matrix semigroup",
[IsReesZeroMatrixSubsemigroup], LambdaBound);

InstallMethod(LambdaBound, "for a McAlister subsemigroup",
[IsMcAlisterTripleSubsemigroup], S ->
function(r)
  local G;
  G := McAlisterTripleSemigroupGroup(MTSEParent(Representative(S)));
  return Size(Stabilizer(G, r, McAlisterTripleSemigroupAction(S)));
end);

InstallMethod(RhoBound, "for a McAlister subsemigroup",
[IsMcAlisterTripleSubsemigroup], LambdaBound);

InstallMethod(LambdaBound, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
function(r)
  if r = 0 then
    return 1;
  elif r < 100 then
    return Size(GL(NrRows(Representative(S)), BaseDomain(S)));
  else
    return infinity;
  fi;
end);

InstallMethod(RhoBound, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], LambdaBound);

# LamdaIdentity(S) returns a function that returns
# the identity element of the Schutzenberger group
# elements produced by LambdaPerm

# TODO(later) these functions don't need the argument <r> any more

InstallMethod(LambdaIdentity, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> r -> ());

InstallMethod(RhoIdentity, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> r -> ());

InstallMethod(LambdaIdentity, "for a partial perm semigroup",
[IsPartialPermSemigroup],
S -> r -> ());

InstallMethod(RhoIdentity, "for a partial perm semigroup",
[IsPartialPermSemigroup],
  S -> r -> ());

InstallMethod(LambdaIdentity, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> r -> ());

InstallMethod(RhoIdentity, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> r -> ());

InstallMethod(LambdaIdentity, "for a Rees 0-matrix semigroup",
[IsReesZeroMatrixSubsemigroup],
S -> r -> ());

InstallMethod(RhoIdentity, "for a Rees 0-matrix semigroup",
[IsReesZeroMatrixSubsemigroup],
S -> r -> ());

InstallMethod(LambdaIdentity, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
S -> r -> ());

InstallMethod(RhoIdentity, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], LambdaIdentity);

InstallMethod(LambdaIdentity, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
r -> IdentityMat(r, BaseDomain(Representative(S))));

InstallMethod(RhoIdentity, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
r -> IdentityMat(r, BaseDomain(Representative(S))));

# LambdaPerm(S) returns a permutation from two acting semigroup elements with
# equal LambdaFunc and RhoFunc. This is required to check if one of the two
# elements belongs to the schutz gp of a lambda orb.

InstallMethod(LambdaPerm, "for a transformation semigroup",
[IsTransformationSemigroup], S -> PermLeftQuoTransformationNC);

InstallMethod(LambdaPerm, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> PERM_LEFT_QUO_PPERM_NC);

InstallMethod(LambdaPerm, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BIPART_PERM_LEFT_QUO);

InstallMethod(LambdaPerm, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S ->
function(x, y)
  if x![1] = 0 or y![1] = 0 then
    return ();
  fi;
  return x![2] ^ -1 * y![2];
end);

InstallMethod(LambdaPerm, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
S -> {x, y} -> x[2] ^ -1 * y[2]);

InstallMethod(LambdaPerm, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
{x, y} -> MatrixOverFiniteFieldSchutzGrpElement(S, x, y));

# Returns a permutation mapping LambdaFunc(S)(x) to LambdaFunc(S)(y) so that
# yx ^ -1(i) = p(i) when RhoFunc(S)(x) = RhoFunc(S)(y)!!

InstallMethod(LambdaConjugator, "for a transformation semigroup",
[IsTransformationSemigroup], S -> TRANS_IMG_CONJ);

InstallMethod(LambdaConjugator, "for a partial perm semigroup",
[IsPartialPermSemigroup], S ->
{x, y} -> MappingPermListList(IMAGE_PPERM(x), IMAGE_PPERM(y)));

InstallMethod(LambdaConjugator, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BIPART_LAMBDA_CONJ);

InstallMethod(LambdaConjugator, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S ->
# FIXME(later) is this right???? This is not right!!
{x, y} -> ());

InstallMethod(LambdaConjugator, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
function(S)
  local T, G, act;
  T := MTSEParent(Representative(S));
  G := McAlisterTripleSemigroupGroup(T);
  act := MTSUnderlyingAction(T);  # MTSAction is not an action, causes problems
  return {x, y} -> RepresentativeAction(G,
                                        LambdaFunc(S)(x),
                                        LambdaFunc(S)(y),
                                        act);
end);

InstallMethod(LambdaConjugator, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
{x, y} -> MatrixOverFiniteFieldLambdaConjugator(S, x, y));

# the function used to test if there is an idempotent with the specified
# lambda and rho values.

InstallMethod(IdempotentTester, "for a transformation semigroup",
[IsTransformationSemigroup], S ->
function(img, ker)
  if IsEmpty(img) then
    return IsEmpty(ker);
  fi;
  return IsInjectiveListTrans(img, ker) and Length(img) = MaximumList(ker);
end);

InstallMethod(IdempotentTester, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> \=);

InstallMethod(IdempotentTester, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BLOCKS_E_TESTER);

InstallMethod(IdempotentTester, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], R ->
function(j, i)
  local parent;
  if i = 0 and j = 0 then
    return true;
  fi;
  parent := ReesMatrixSemigroupOfFamily(ElementsFamily(FamilyObj(R)));
  return Matrix(parent)[j][i] <> 0;
end);

InstallMethod(IdempotentTester, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S -> {x, y} -> x = y);

InstallMethod(IdempotentTester, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> {x, y} -> MatrixOverFiniteFieldIdempotentTester(S, x, y));

# the function used to create an idempotent with the specified lambda and rho
# values.

InstallMethod(IdempotentCreator, "for a transformation semigroup",
[IsTransformationSemigroup], S -> IDEM_IMG_KER_NC);

InstallMethod(IdempotentCreator, "for a partial perm semigp",
[IsPartialPermSemigroup], S -> PartialPermNC);

InstallMethod(IdempotentCreator, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BLOCKS_E_CREATOR);

InstallMethod(IdempotentCreator, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], R ->
function(j, i)
  local mat;
  if i = 0 and j = 0 then
    return Objectify(TypeReesMatrixSemigroupElements(R), [0]);
  fi;
  mat := Matrix(ReesMatrixSemigroupOfFamily(ElementsFamily(FamilyObj(R))));
  return Objectify(TypeReesMatrixSemigroupElements(R),
                   [i, mat[j][i] ^ -1, j, mat]);
end);

InstallMethod(IdempotentCreator, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S ->
function(x, _)
  local T;
  T := MTSEParent(Representative(S));
  return MTSE(T, x, One(McAlisterTripleSemigroupGroup(T)));
end);

InstallMethod(IdempotentCreator, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> {x, y} -> MatrixOverFiniteFieldIdempotentCreator(S, x, y));

# the action of elements of the stabiliser of a lambda-value on any element of
# the semigroup with that lambda-value

# StabilizerAction will be \* for transformation and partial perm semigroups
# and something else for semigroups of bipartitions.

InstallMethod(StabilizerAction, "for a transformation semigroup",
[IsTransformationSemigroup], S -> OnRight);

InstallMethod(StabilizerAction, "for a partial perm semigroup",
[IsPartialPermSemigroup], S -> OnRight);

InstallMethod(StabilizerAction, "for a bipartition semigroup",
[IsBipartitionSemigroup], S -> BIPART_STAB_ACTION);

InstallMethod(StabilizerAction, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup], S ->
function(x, p)
  if x![1] = 0 then
    return x;
  fi;
  return Objectify(TypeObj(x), [x![1], x![2] * p, x![3], x![4]]);
end);

InstallMethod(StabilizerAction, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup], S ->
function(x, p)
  local T;
  T := MTSEParent(x);
  return MTSE(T, x[1], x[2] * p);
end);

InstallMethod(StabilizerAction, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup], S ->
{x, y} -> MatrixOverFiniteFieldStabilizerAction(S, x, y));

# IsActingSemigroupWithFixedDegreeMultiplication should be <true> if and only
# if it is only possible to multiply elements of the type in the semigroup with
# equal degrees.

InstallMethod(IsActingSemigroupWithFixedDegreeMultiplication,
"for a transformation semigroup",
[IsTransformationSemigroup and IsActingSemigroup], ReturnFalse);

InstallTrueMethod(IsActingSemigroupWithFixedDegreeMultiplication,
IsBipartitionSemigroup and IsActingSemigroup);

InstallMethod(IsActingSemigroupWithFixedDegreeMultiplication,
"for an acting partial perm semigroup",
[IsPartialPermSemigroup and IsActingSemigroup], ReturnFalse);

# this is not really relevant here.
InstallMethod(IsActingSemigroupWithFixedDegreeMultiplication,
"for an acting Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup and IsActingSemigroup], ReturnFalse);

InstallMethod(IsActingSemigroupWithFixedDegreeMultiplication,
"for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup and IsActingSemigroup], ReturnFalse);

InstallTrueMethod(IsActingSemigroupWithFixedDegreeMultiplication,
                  IsMatrixOverFiniteFieldSemigroup);

InstallMethod(SchutzGpMembership, "for a transformation semigroup",
[IsTransformationSemigroup],
S -> {stab, x} -> SiftedPermutation(stab, x) = ());

InstallMethod(SchutzGpMembership, "for a partial perm semigroup",
[IsPartialPermSemigroup],
S -> {stab, x} -> SiftedPermutation(stab, x) = ());

InstallMethod(SchutzGpMembership, "for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup],
S -> {stab, x} -> SiftedPermutation(stab, x) = ());

InstallMethod(SchutzGpMembership, "for a McAlister triple subsemigroup",
[IsMcAlisterTripleSubsemigroup],
S -> {stab, x} -> SiftedPermutation(stab, x) = ());

InstallMethod(SchutzGpMembership, "for a bipartition semigroup",
[IsBipartitionSemigroup],
S -> {stab, x} -> SiftedPermutation(stab, x) = ());

InstallMethod(SchutzGpMembership, "for a matrix semigroup",
[IsMatrixOverFiniteFieldSemigroup],
S -> {stab, x} -> x in stab);

# One or a fake one for those types of object without one.

InstallMethod(FakeOne, "for a transformation collection",
[IsTransformationCollection], One);

InstallMethod(FakeOne, "for a partial perm collection",
[IsPartialPermCollection], One);

InstallMethod(FakeOne, "for a bipartition collection",
[IsBipartitionCollection], One);

InstallMethod(FakeOne, "for a Rees 0-matrix semigroup element collection",
[IsReesZeroMatrixSemigroupElementCollection], R -> SEMIGROUPS.UniversalFakeOne);

InstallMethod(FakeOne, "for a McAlister triple semigroup element collection",
[IsMcAlisterTripleSemigroupElementCollection],
S -> SEMIGROUPS.UniversalFakeOne);

# Matrix semigroup elements
InstallMethod(FakeOne, "for an FFE coll coll coll",
[IsFFECollCollColl],
function(coll)
  Assert(1, ForAll(coll, IsMatrixObjOverFiniteField));
  Assert(1, ForAll(coll, x -> NrRows(x) = NrRows(Representative(coll))));
  return One(Representative(coll));
end);

# missing hash functions

SEMIGROUPS.HashFunctionRZMSE := function(x, data, func)
  if x![1] = 0 then
    return 1;
  fi;
  # Use some big primes that are near the default hash table size
  if IsNBitsPcWordRep(x![2]) then
    return (104723 * x![1] + 104729 * x![3] + func(x![2], data))
      mod data[2] + 1;
  else
    return (104723 * x![1] + 104729 * x![3] + func(x![2], data)) mod data + 1;
  fi;
end;

InstallMethod(ChooseHashFunction,
"for a Rees 0-matrix semigroup element and integer",
[IsReesZeroMatrixSemigroupElement, IsInt],
function(x, hashlen)
  local R, data, under, func;

  R := ReesMatrixSemigroupOfFamily(FamilyObj(x));
  if IsMultiplicativeZero(R, x) then
    x := EmptyPlist(3);
    x[2] := Representative(UnderlyingSemigroup(R));
  fi;
  if IsNBitsPcWordRep(x![2]) then
    under := ChooseHashFunction(x![2], hashlen).func;
    data := ChooseHashFunction(x![2], hashlen).data;
  else
    under := ChooseHashFunction(x![2], hashlen).func;
    data := ChooseHashFunction(x![2], hashlen).data;
  fi;
  if data = fail then
    data := hashlen;
  fi;

  func := {x, hashlen} -> SEMIGROUPS.HashFunctionRZMSE(x, data, under);

  return rec(func := func, data := data);
end);

# fallback method for hashing

InstallMethod(ChooseHashFunction, "for an object and an int",
[IsObject, IsInt],
{p, hashlen} -> rec(func := {v, data} -> 1, data := fail));

# The next two methods are more general than might seem necessary but
# apparently ReesZeroMatrixSemigroup'S satisfying IsWholeFamily are not in
# IsActingSemigroup but their ideals are, and we still require a method for
# ConvertToInternalElement as a result.

InstallMethod(ConvertToInternalElement,
"for a semigroup and mult. elt.",
[IsSemigroup, IsMultiplicativeElement],
{S, x} -> x);

InstallMethod(ConvertToExternalElement,
"for a semigroup and mult. elt.",
[IsSemigroup, IsMultiplicativeElement],
{S, x} -> x);

InstallMethod(ConvertToInternalElement,
"for an acting matrix over ff semigroup and matrix obj",
[IsActingSemigroup and IsMatrixOverFiniteFieldSemigroup, IsMatrixObj],
function(S, mat)
  local bd, n;

  Assert(1, IsMatrixObjOverFiniteField(mat));
  if NrRows(mat) = NrRows(Representative(S)) + 1 then
    return mat;
  fi;
  Assert(1, NrRows(mat) = NrRows(Representative(S)));

  bd  := BaseDomain(mat);
  n   := NrRows(mat);
  mat := List([1 .. n],
              i -> Concatenation(mat[i], [Zero(bd)]));
  Add(mat, ZeroMatrix(bd, 1, n + 1)[1]);
  mat[n + 1, n + 1] := One(bd);
  return Matrix(bd, mat);
end);

InstallMethod(ConvertToExternalElement,
"for an acting matrix over ff semigroup and matrix obj",
[IsActingSemigroup and IsMatrixOverFiniteFieldSemigroup, IsMatrixObj],
function(S, mat)
  local n;

  Assert(1, IsMatrixObjOverFiniteField(mat));
  if NrRows(mat) = NrRows(Representative(S)) then
    return mat;
  fi;
  Assert(1, NrRows(mat) = NrRows(Representative(S)) + 1);

  n := NrRows(mat) - 1;
  return Matrix(Unpack(mat){[1 .. n]}{[1 .. n]}, mat);
end);

InstallMethod(WeakInverse, "for a transformation",
[IsTransformation], InverseOfTransformation);

InstallMethod(WeakInverse, "for a partial perm",
[IsPartialPerm], InverseMutable);

InstallMethod(WeakInverse, "for a bipartition",
[IsBipartition], Star);

Quelle setup.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.14 Sekunden (vorverarbeitet) ]